【数据结构】顺序表和链表

1.线性表

我们在C语言当中学过数组，实在呢，数组可以实现线性表，线性表理解上类似于数组，那么什么是线性表呢？线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在现实中广泛使 用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储。下面我们就将先容顺序表和链表。

2.顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一样平常环境下采用数组存 储。在数组上完成数据的增删查改。一样平常环境下顺序表可以分为静态顺序表和动态顺序表

• 静态顺序表：利用定长数组存储元素。
  
• 动态顺序表：利用动态开辟的数组存储。
  

静态数据表呢，实在就是给一个数组，我们对这个数组举行增删查改，只不外，数据结构的意思把这一系列的利用封装了起来，我们在利用的利用直接调用相应的接口。顺序表的静态存储相对简单，我们不在此实现。
动态顺序表的意思就是，可以根据必要及时的举行扩容，从而满意要求，我们之前实现过通讯录，实在这里和通讯录的原理是类似的，接下来我们实现相应的接口。

1. typedef struct SeqList
2. {
3.         SLDataType *a;//指向这块空间的起始地址
4.         int size;//存放的有效数据
5.         int capacity;//容量
6. }SL ;//通过typedef将它重命名为SL方便我们以后使用
7. //初始化顺序表
8. void SeqListInit(SL* ps);
9. //扩容
10. void SeqListCheck(SL* ps);
11. //打印
12. void SeqListPrint(SL* ps);
13. // 尾插尾删
14. void SeqListPushBack(SL* ps, SLDataType x);
15. void SeqListPopBack(SL* ps);
16. //头插头删
17. void SeqListPushFront(SL* ps, SLDataType x);
18. void SeqListPopFront(SL* ps);
19. //任意位置插入删除
20. void SeqListInsert(SL* ps, size_t pos, SLDataType x);
21. void SeqListErase(SL* psl, size_t pos);

复制代码

这是顺序表整个工程文件的头文件，包罗告终构体的声明，和各种接口的声明。结构体的定义中我们定义了一个指向我们目的空间的起始地址，这是用来指向我们所开辟的空间的，固然能不能定义一个数组呢？也是可以，但是这样就变成了静态顺序表的实现了。size的定义是为了及时的显示空间内的有用数据巨细，固然一个空间是不是有它的巨细，那capacity就是它的容量。接下来将对恣意位置插入删除的函数举行实现。

1. //任意位置插入
2. void SeqListInsert(SL* ps, size_t pos, SLDataType x)
3. {
4.         assert(ps);//如果ps=NULL，则终止程序
5.         if (ps->size == ps->capacity)//扩容
6.         {
7.                 SeqListCheck(ps);
8.         }
9.         int end = ps->size - 1;
10.         while (pos <= end)
11.         {
12.                 ps->a[end + 1] = ps->a[end];
13.                 end--;
14.         }
15.         ps->a[pos] = x;
16.         ps->size++;
17. }

复制代码

恣意位置的插入，现实上是把数据整体往后挪动，终极把目的位置空出来，把目的数据放进去，留意这是从后往前挪，我们的头插也是这样的道理，事实上头插就是一种特殊的恣意位置插入，因此，恣意位置插入实现之后可以在头插直接调用该接口就可实现。

1. //任意位置删除
2. void SeqListErase(SL* ps, size_t pos)
3. {
4.         assert(ps);
5.         for (int start = pos; start < ps->size - 1; start++)
6.         {
7.                 ps->a[start] = ps->a[start + 1];
8.         }
9.         ps->size--;
10. }

复制代码

恣意位置的删除，现实上就是把背面的数据逐个往前挪，把目的位置的数据覆盖掉，便达到了删除的目的了，留意这是从前去后挪，头删也是这样的道理，头删可以直接调用该接口，来实现头删。
   补充知识：
  realloc增容是一样平常取2倍，为什么呢？由于如果增的越多的话，有可能空间的浪费就越多，如果增的越少，虽然空间越省，但是如果我们存放的数据相对增容是比力大的，这就面对着频仍增容的环境，这斲丧代价也是蛮大的，所以我们取折中的方法增2倍。
  3.链表

上面我们先容了顺序表，但是大家敏锐的发现了题目没有，我们在恣意位置插入的时候，就加入在头部插入时间复杂度是多少？是不是O（N），而且它在扩容的时候面对着扩的过大，扩的过小的题目，那有没有一种结构让我们可以不挪动别的数据直接插入，而且必要多少我们申请多少，固然也是存在这样的一种数据结构的，这就是我们的链表。
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

留意：

• 链式结构在逻辑上是连续的，但是在物理上不一定连续
  
• 现实中的结点一样平常都是从堆上申请出来的
  
• 从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续
  

一个数据结构，我们一样平常对它举行的利用就是举行增删查改，所以下面将对链表的一些接口举行实现。主要涉及以下接口：

1. typedef int SListDataType;
2. typedef struct SListNode
3. {
4.         SListDataType data;
5.         struct SListNode* next;
6. }SListNode;
8. // 动态申请一个结点
9. SListNode* BuySListNode(SListDataType x);
10. // 单链表打印
11. void SListPrint(SListNode* plist);
12. // 单链表尾插
13. void SListPushBack(SListNode** pplist, SListDataType x);
14. // 单链表的头插
15. void SListPushFront(SListNode** pplist, SListDataType x);
16. // 单链表的尾删
17. void SListPopBack(SListNode** pplist);
18. // 单链表头删
19. void SListPopFront(SListNode** pplist);
20. // 单链表查找
21. SListNode* SListFind(SListNode* plist, SListDataType x);
22. // 单链表在pos位置之后插入x
23. // 分析思考为什么不在pos位置之前插入？
24. // 因为单链表只能找到它后面的节点，找不到它前面的节点，双链表可以
25. void SListInsertAfter(SListNode* pos, SListDataType x);
26. // 单链表删除pos位置之后的值
27. // 分析思考为什么不删除pos位置？
28. // 删除了之后，pos后面位置的内容上哪找，会造成内存泄露
29. void SListEraseAfter(SListNode* pos);

复制代码

这是链表整个工程文件的头文件，包罗告终构体的声明，和各种接口的声明。结构体的定义中我们定义了节点的数据，以及节点所存放下一个节点的地址，这个地址就是用来指向下一个节点的，从而实现链表的逻辑连续。在链表接口声明中，下面将举行一一的实现。

1. // 动态申请一个结点
2. SListNode* BuySListNode(SListDataType x)
3. {
4.         SListNode* pList = (SListNode*)malloc(sizeof(SListNode));
5.         if (pList == NULL)
6.         {
7.                 printf("开辟新节点失败");
8.                 exit(-1);
9.         }
10.         pList->data = x;
11.         pList->next = NULL;//这点很重要，如果不置为NULL，极有可能越界访问
12.         return pList;
13. }

复制代码

上面所先容的顺序表由于在通讯录当中已经先容了大部分内容，所以只将部分接口举行实现，链表是一个新的知识点，因此举行详细的先容，前面我们已经了解单链表它的一种形式，所以我们在开辟一个新节点时，要留意pList->next = NULL，不置为空，体系会随机生成一个地址，那如果我们不小心调用了就会造成越界访问。
   补充知识：
  链表在堆区开辟空间时，有可能缠绕在一起，为什么呢？由于堆区虽然向上生长的，但是存在下面的空间被释放掉，之后开辟在下面了。

1. // 单链表尾插
2. void SListPushBack(SListNode** pplist, SListDataType x)
3. {
4.         if (*pplist == NULL)//分情况，如果这种情况没有，下面cur->next就会导致对NULL访问的错误
5.         {
6.                 *pplist = BuySListNode(x);
7.         }
8.         else
9.         {
10.                 SListNode* cur = *pplist;
11.                 while (cur->next != NULL)
12.                 {
13.                         cur = cur->next;
14.                 }
15.                 cur->next = BuySListNode(x);//这里通过cur可以改外部变量的值，需要注意一下
16.         }
17. }

复制代码

尾插整体的思路就是我们应该首先找到尾，固然这里就分了环境，如果一开始就是尾，直接插入数据，不是的话我们就必要遍历整个链表，找到尾，然后将数据插入，遍历唯一必要留意的就是cur = cur->next，这是链表的关键，所以单链表的利用就两点，一是头指针的创建与利用，二是节点中存放着下一个节点的地址。

1. // 单链表的尾删
2. void SListPopBack(SListNode** pplist)
3. {
4.         if (*pplist == NULL)//分情况，如果这种情况没有，下面cur->next就会导致对NULL访问的错误
5.         {
6.                 return;//空就是没有要删的，直接返回
7.         }
8.         else
9.         {
10.                 SListNode* cur = *pplist;
11.                 SListNode* tail = *pplist;//设置该指针变量唯一目的就是，为了是新的尾节点的next置成NULL，防止成为野指针
12.                 while (cur->next != NULL)
13.                 {
14.                         tail = cur;//最后一次执行的时候会把cur之前那个节点即最终结果的尾赋给tail
15.                         cur = cur->next;
16.                 }
17.                 free(cur);
18.                 tail->next = NULL;//别忘记置成NULL，防止对NULL造成访问
19.         }
20. }

复制代码

尾删的整体思路和尾插是一样的，唯一的区别就在于多定义了一个tail指针变量，设置该指针变量唯一目的就是，为了是新的尾节点的next置成NULL，防止成为野指针。

1. // 单链表的头插
2. void SListPushFront(SListNode** pplist, SListDataType x)
3. {
4.         SListNode* NewNode = BuySListNode(x);
5.         NewNode->next = *pplist;
6.         *pplist = NewNode;
7. }
8. // 单链表头删
9. void SListPopFront(SListNode** pplist)
10. {
11.         if (*pplist == NULL)//分情况，如果这种情况没有，下面cur->next就会导致对NULL访问的错误
12.         {
13.                 return;//空就是没有要删的，直接返回
14.         }
15.         else
16.         {
17.                 SListNode* cur = *pplist;
18.                 *pplist = (*pplist)->next;
19.                 free(cur);
20.                 cur = NULL;//别忘记置成NULL，防止成为野指针
21.         }
22. }

复制代码

头插相对比力简单，把我们新的节点中存放原先第一个节点的地址，然后把头指针的地址链接到我们所创建的新的节点上，时候应该留意到链表的数据别丢失。
头删，创建一个暂时的指针变量cur是一个关键，如果不创建，第一个节点已释放，找不到了之后的数据，把头指针指向第二个节点，那第一个节点的空间又无法释放，因此创建一个暂时指针变量去存储此中一个地址，两个方法都可以。

1. // 单链表在pos位置之后插入x
2. void SListInsertAfter(SListNode** pos, SListDataType x)
3. {
4.         if (*pos == NULL)
5.         {
6.                 SListPushBack(pos, x);//这就是该接口也使用二级指针的原因，如果不使用，把&pos传过去
7.         }                         //最终改变不了test.c中的pList，只能改变pos的地址，因为一级指针pos只能改变pList所指向的空间内容
8.         else                      //1.要改变量内容传变量地址  
9.         {                         //2.要改变变量地址需要传变量地址的地址
10.                 SListNode* next = BuySListNode(x);
11.                 next->next = (*pos)->next;
12.                 (*pos)->next = next;
13.         }
14. }

复制代码

恣意位置之后插入的原理实在和头删是一样的，就是要留意暂时指针变量的创建，防止内存走漏和野指针的题目，必要把插入位置的两头连上。唯一必要留意的是，如果没有*pos==NULL的环境，就不必要传二级指针，实在*pos==NULL就是尾插，可以直接调用尾插接口就可以了。

1. // 单链表删除pos位置之后的值
2. void SListEraseAfter(SListNode* pos)
3. {
4.         if (pos == NULL)
5.         {
6.                 return;
7.         }
8.         else if (pos->next == NULL)
9.         {
10.                 printf("你所要删除的位置之后没有数据\n");
11.                 return;
12.         }
13.         else
14.         {
15.                 SListNode* next = pos->next;
16.                 pos->next = next->next;
17.                 free(next);
18.         }
19. }

复制代码

pos位置之后的删除也是同样的道理， 必要留意，就是说我们只能删除指定位置的后一个数据，插入也一样，由于我们都不知道这个位置的前一个节点的地址，这不是双链表，因此只能删除和插入pos之后的节点。
4.顺序表与链表区别

顺序表：可动态增长的数组，数据在数组中存储时必须是连续的。优点：可以随机访问，缓存掷中率比力高。缺点：中间或者头部的插入删除很慢，必要挪动数据，时间复杂度是O(N)。空间不够时，增容会有一定斲丧和空间浪费。
链表：逻辑上连续，物理上不一定连续。优点：头部插入只需修改指针指向即可，不必要挪动数据。缺点：缓存掷中率比力低，不支持随机访问。

   补充知识：
  顺序表的缓存掷中率比力高，为什么呢？由于顺序表的数据在物理上是连续的，因此cpu读取数据会从缓冲器上拿，第一次拿的时候，缓冲器没有我们在内存中存储的数据，因此缓冲器会去内存里拿，拿的时候会连续拿好几个数据，当cpu读取数据的时候就会先在缓冲器上拿，这样就会拿到数据，这就是缓冲掷中率。
  而链表物理上不是连续的因此缓冲器拿的时候拿不到连续的我们自己的数据，因此导致cpu每次在缓冲器上都拿不到数据，都会是缓冲器去内存上加载，再cpu在缓冲器上拿，而且也会导致缓冲器的污染，由于链表可能这一个那一个，缓冲器加载时候会把旁边不是它的数据也会捎带拿着，就会导致不是我们想要的数据也被加载到缓冲器。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。