对于顺序表的学习-开发者社区

一.顺序表的概念

顺序表（Sequential List）是一种基于数组实现的线性数据结构，它可以用来存储一组有序的元素。顺序表是最常见的线性表之一，其特点是元素在内存中是连续存储的。顺序表中的每个元素都可以通过索引直接访问，因此它提供了高效的随机访问功能。

二.顺序表的结构

三.顺序表的实现

我们有两种方式来实现顺序表，但是最常用的肯定是动态申请的所以在这里只给出静态的形式不给出详细函数，我们来详细说一说动态的实现

1.静态（固定大小）

定义

typedefintSLDataType;#defineN1000//静态顺序表（开多了浪费，开少了不够用）structSeqList{SLDataType a[N];intsize;};

2.动态（按需申请）（详细讲）

定义

typedefintSLDataType;#defineINIT_CAPACITY4//动态顺序表 -- 按需申请typedefstructSeqList{SLDataType*a;intsize;//有效数据个数intcapacity;//空间容量}SL;

增删查改的各接口

voidSeqInit(SL*ps);voidSeqDestory(SL*ps);voidSeqPrint(SL*ps);voidSLCheckCapacity(SL*ps);voidSeqPushBack(SL*ps,SLDataType x);voidSeqPopBack(SL*ps);voidSeqPushFront(SL*ps,SLDataType x);voidSeqPopFront(SL*ps);voidSLInsert(SL*ps,intpos,SLDataType x);voidSLErase(SL*ps,intpos);intSLfind(SL*ps,SLDataType x);

2.1初始化

初始化给定一定的容量

voidSeqInit(SL*ps){//assert(ps);ps->a=(SLDataType*)malloc(sizeof(SLDataType)*INIT_CAPACITY);if(ps->a==NULL){perror("malloc fail");return;}ps->size=0;ps->capacity=INIT_CAPACITY;}

2.2销毁

voidSeqDestory(SL*ps){assert(ps);free(ps->a);ps->a==NULL;ps->capacity=ps->size=0;}

2.3打印

voidSeqPrint(SL*ps){assert(ps);for(inti=0;i<ps->size;i++){printf("%d\n",ps->a[i]);}}

2.4检查容量

当容量不够时将容量扩大为原来的2倍最合适，不会太大也不会太小

voidSLCheckCapacity(SL*ps){assert(ps);if(ps->size==ps->capacity){SLDataType*tmp=(SLDataType*)realloc(ps->a,sizeof(SLDataType)*ps->capacity*2);if(tmp==NULL){perror("realloc fail");return;}ps->a=tmp;ps->capacity*=2;}}

2.5尾插尾删

voidSeqPushBack(SL*ps,SLDataType x){assert(ps);// SLCheckCapacity(ps);// ps->a[ps->size++] = x;SLInsert(ps,ps->size,x);}voidSeqPopBack(SL*ps){assert(ps);//assert(ps->size > 0);if(ps->size==0){return;}ps->size--;}

2.6头插头删

voidSeqPushFront(SL*ps,SLDataType x){// assert(ps);// SLCheckCapacity(ps);// int end = ps->size - 1;// while(end >= 0)// {// ps->a[end+1] = ps->a[end];// --end;// }// ps->a[0] = x;// ps->size++;SLInsert(ps,0,x);}voidSeqPopFront(SL*ps){assert(ps);intbegin=1;while(begin<ps->a[begin]){ps->a[begin-1]=ps->a[begin];++begin;}ps->size--;}

2.7查找

intSLfind(SL*ps,SLDataType x){assert(ps);for(inti=0;i<ps->size;i++){if(ps->a[i]==x){return1;}}}

2.8任意位置插删

这里基于查找函数来实现

voidSLInsert(SL*ps,intpos,SLDataType x){assert(ps);assert(pos>=0&&pos<=ps->size);SLCheckCapacity(ps);intend=ps->size-1;while(end>=pos){ps->a[end+1]=ps->a[end];--end;}ps->a[pos]=x;ps->size++;}voidSLErase(SL*ps,intpos){assert(ps);assert(pos>=0&&pos<ps->size);intbegin=pos+1;while(begin<ps->size){ps->a[begin-1]=ps->a[begin];++begin;}ps->size--;}

四.总结比较

或许大家对于顺序表还有疑问，明明链表更加的好用但是为什么还要学习顺序表。
最后我来总结一下链表和顺序表的优缺点

顺序表的优缺点：

优点：
- 支持快速随机访问，时间复杂度 O(1)。
- 结构简单，实现容易。
- 内存使用较为高效，没有额外的指针开销。
缺点：
- 插入和删除操作效率低，尤其是中间位置的插入和删除需要 O(n) 时间。
- 扩展时需要 O(n) 的时间来重新分配和复制数组。
- 需要预设容量，如果容量不足需要扩展，可能浪费空间。

链表的优缺点：

优点
- 动态分配内存，能够有效利用内存空间。
- 插入和删除操作非常高效，特别是在头部和中间位置，时间复杂度 O(1)。
- 可以在任何位置进行插入和删除，操作灵活。
缺点：
- 不支持快速的随机访问，需要 O(n) 时间逐个访问节点。
- 每个节点除了存储数据外，还需要存储指针，因此内存开销较大。
- 实现相对复杂，尤其是在指针管理方面容易出错。

8.适用场景

顺序表适用场景：
- 当需要频繁进行随机访问时，顺序表是一个很好的选择。
- 元素个数相对固定或不经常改变，或者修改主要发生在末尾时，顺序表的表现非常好。
- 适合存储大量静态数据，如查找表、缓存等。
链表适用场景：
- 当需要频繁插入和删除元素时，链表表现优异，特别是在需要在中间位置插入或删除时。
- 元素的数量动态变化较大，不确定的场景下，链表更具优势。
- 适用于实现栈、队列等需要频繁插入和删除的应用场景。

这篇文章之前忘记发了现在补上，并且添加了和链表的比较方便大家更好的理解二者之间的区别
有不足之处希望大家可以指出来，我们一起学习一起进步。