24/07/08数据结构(2.1203)顺序表实现_开发测试

24/07/08数据结构(2.1203)顺序表实现

创始人

2025-01-15 13:34:28

0次

size属于结构体的作用域

如果要访问一个结构体的指针用->

如果要访问一个结构体的变量用. 点操作

#include
#include
#include
#include"seqlist.h"

//typedef struct seqList{
//   SLDataType* _data; //需要动态开辟的数组
//   size_t _size; //有效元素的个数
//   size_t _capacity; //挡枪可以存放的最大元素个数
//}seqList;

void initSeqList(seqList* sl){
sl->_data = NULL;
sl->_size = sl->_capacity = 0;
}

//尾插一个数据o(1)
void pushBack(seqList* sl, SLDataType val){
   //检查容量
   checkCapacity(sl);
   sl->_data[sl->_size] = val;
   ++sl->_size;
}

void checkCapacity(seqList* sl){
   //如果元素个数和容量相同,说明空间满了,需要扩容空间
   if (sl->_size == sl->_capacity){
       int newCapacity = sl->_capacity == 0 ? 1 : 2 * sl->_capacity;
       //开一个更大的空间,拷贝已有数据,释放原有空间
       SLDataType* tmp = (SLDataType*)malloc(sizeof(SLDataType)* newCapacity);
       memcpy(tmp, sl->_data, sizeof(SLDataType)* sl->_size);
       free(sl->_data);
       //更新
       sl->_data = tmp;
       sl->_capacity = newCapacity;
   }
}

void printSeList(seqList* sl){
   for (int i = 0; i < sl->_size; ++i){
       printf("%d", sl->_data[i]);
   }
   printf("\n");
}

void popBack(seqList* sl){
   if (sl == NULL)
       return;
   if (sl->_size>0)
       sl->_size--;
}

//头插给顺序表的第一个位置插入元素o(n)
//一般不进行头插:效率低
void pushFront(seqList* sl, SLDataType val){
   if (sl == NULL)
       return;
   //0.检查容量
   checkCapacity(sl);
   //1.移动元素:从后向前移动
   int end = sl->_size;
   while (end > 0){
       sl->_data[end] = sl->_data[end - 1];
       --end;
   }
   //2.头插
   sl->_data[0] = val;

   sl->_size++;
}
//头删: 移动元素:[1,size)全部向前移动一个位置
void popFront(seqList* sl){
   if (sl == NULL || sl->_size == 0)
       return;
   int start = 1;
   while (start < sl->_size){
       sl->_data[start - 1] = sl->_data[start];
       ++start;
   }

--sl->_size;
}

//插入
void insert(seqList* sl, int pos, SLDataType val){
   //检查容量
   if (sl == NULL)
       return;
   checkCapacity(sl);
   //移动元素
   int end = sl->_size;
   while (end > pos){
       sl->_data[end] = sl->_data[end - 1];
       --end;
   }
   //插入数据
   sl->_data[pos] = val;
   //更新
   sl->_size++;
}

void test(){
   seqList sl;
   initSeqList(&sl);
   pushBack(&sl, 1);
   pushBack(&sl, 2);
   pushBack(&sl, 3);
   pushBack(&sl, 4);
   pushBack(&sl, 5);
   insert(&sl, 1, 10);
   insert(&sl, 2, 20);
   printSeList(&sl);
   insert(&sl, 0, -1);
   printSeList(&sl);
   insert(&sl, sl._size, 3);
   printSeList(&sl);

}
int main(){

   test();
   system("pause");
   return 0;
}

完整的代码:

.h头文件

typedef int SLDataType;

typedef struct seqList{
   SLDataType* _data; //需要动态开辟的数组
   size_t _size; //有效元素的个数
   size_t _capacity; //当前可以存放的最大元素个数
}seqList;

void initSeqList(seqList* sl);

//尾插一个数据
void pushBack(seqList* sl, SLDataType val);

void checkCapacity(seqList* sl);

void printSeList(seqList* sl);

void popBack(seqList* sl);

.c文件

#include
#include
#include
#include"seqlist.h"

//typedef struct seqList{
//   SLDataType* _data; //需要动态开辟的数组
//   size_t _size; //有效元素的个数
//   size_t _capacity; //挡枪可以存放的最大元素个数
//}seqList;

void initSeqList(seqList* sl){
sl->_data = NULL;
sl->_size = sl->_capacity = 0;
}

//尾插一个数据o(1)
void pushBack(seqList* sl, SLDataType val){
   //检查容量
   checkCapacity(sl);
   sl->_data[sl->_size] = val;
   ++sl->_size;
}

void printSeList(seqList* sl){
   for (int i = 0; i < sl->_size; ++i){
       printf("%d", sl->_data[i]);
   }
   printf("\n");
}

void popBack(seqList* sl){
   if (sl == NULL)
       return;
   if (sl->_size>0)
       sl->_size--;
}

--sl->_size;
}

//删除的操作
void erase(seqList* sl, int pos){
   if (sl == NULL || sl->_size == 0)
       return;
   //有效位置:[0,size)
   if (pos >= 0 && pos < sl->_size){
       //1.移动元素:(pos,size),从pos + 1开始,从前往后依次移动
       int start = pos + 1;
       while (start < sl-> _size){
           sl->_data[start - 1] = sl->_data[start];
           ++start;
       }
       --sl->_size;
   }
}

int empty(seqList* sl){
   if (sl = NULL || sl->_size == 0)
       return 1;
   else
       return 0;
}

int size(seqList* sl){
   if (sl == NULL)
       return 0;
   else
       return sl->_size;
}

int findIdx(seqList* sl, SLDataType val){
   int i = 0;
   for (; i < sl->_size; ++i){
       if (sl->_data[i] == val)
           return i;
   }
   return -1;
}

SLDataType getIdx(seqList* sl, int pos){

return sl->_data[pos];
}

void destorySeqList(seqList* sl){
   if (sl){
       //释放堆上申请的空间
       if (sl->_data){
           free(sl->_data);
           sl->_data = NULL;
       }
   }
}

void test(){
   seqList sl;
   initSeqList(&sl);
   pushBack(&sl, 1 );
   pushBack(&sl, 2 );
   pushBack(&sl, 3 );
   pushBack(&sl, 4 );
   pushBack(&sl, 5 );
   erase(&sl, 3);
   erase(&sl, 2);
   erase(&sl, 0);
   printSeList(&sl);
}

//void test(){
//   seqList sl;
//   initSeqList(&sl);
//   pushBack(&sl, 1);
//   pushBack(&sl, 2);
//   pushBack(&sl, 3);
//   pushBack(&sl, 4);
//   pushBack(&sl, 5);
//   insert(&sl, 1, 10);
//   insert(&sl, 2, 20);
//   printSeList(&sl);
//   insert(&sl, 0, -1);
//   printSeList(&sl);
//   insert(&sl, sl._size, 3);
//   printSeList(&sl);
//
//
//}
int main(){

   test();
   system("pause");
   return 0;
}

由此可以看出顺序表的一些特性:

1.空间联系

2.支持随机访问

3.尾插,尾删效率高:O(1)

4.空间利用率高,不容易造成内存碎片

5.其他位置插入,删除效率低:O(n) ---> 移动元素

6.增容代价比较大

上一篇：HTML5表单的自动验证、取消验证、自定义错误信息

下一篇：如何使一个盒子水平垂直居中（常用的）

24/07/08数据结构(2.1203)顺序表实现

相关内容

热门资讯