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

1.线性表

我们在C语言当中学过数组，其实呢，数组可以实现线性表，线性表理解上类似于数组，那么什么是线性表呢？线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使 用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储。下面我们就将介绍顺序表和链表。

2.顺序表

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

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

静态数据表呢，其实就是给一个数组，我们对这个数组进行增删查改，只不过，数据结构的意思把这一系列的操作封装了起来，我们在使用的使用直接调用相应的接口。顺序表的静态存储相对简单，我们不在此实现。

动态顺序表的意思就是，可以根据需要及时的进行扩容，从而满足要求，我们之前实现过通讯录，其实这里和通讯录的原理是类似的，接下来我们实现相应的接口。

typedef struct SeqList 
{SLDataType *a;//指向这块空间的起始地址int size;//存放的有效数据int capacity;//容量
}SL ;//通过typedef将它重命名为SL方便我们以后使用
//初始化顺序表
void SeqListInit(SL* ps);
//扩容
void SeqListCheck(SL* ps);
//打印
void SeqListPrint(SL* ps);
// 尾插尾删
void SeqListPushBack(SL* ps, SLDataType x);
void SeqListPopBack(SL* ps);
//头插头删
void SeqListPushFront(SL* ps, SLDataType x);
void SeqListPopFront(SL* ps);
//任意位置插入删除
void SeqListInsert(SL* ps, size_t pos, SLDataType x);
void SeqListErase(SL* psl, size_t pos);

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

//任意位置插入
void SeqListInsert(SL* ps, size_t pos, SLDataType x)
{assert(ps);//如果ps=NULL，则终止程序if (ps->size == ps->capacity)//扩容{SeqListCheck(ps);}int end = ps->size - 1;while (pos <= end){ps->a[end + 1] = ps->a[end];end--;}ps->a[pos] = x;ps->size++;
}

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

//任意位置删除
void SeqListErase(SL* ps, size_t pos)
{assert(ps);for (int start = pos; start < ps->size - 1; start++){ps->a[start] = ps->a[start + 1];}ps->size--;
}

任意位置的删除，实际上就是把后面的数据逐个往前挪，把目标位置的数据覆盖掉，便达到了删除的目的了，注意这是从前往后挪，头删也是这样的道理，头删可以直接调用该接口，来实现头删。

补充知识：

realloc增容是一般取2倍，为什么呢？因为如果增的越多的话，有可能空间的浪费就越多，如果增的越少，虽然空间越省，但是如果我们存放的数据相对增容是比较大的，这就面临着频繁增容的情况，这消耗代价也是蛮大的，所以我们取折中的方法增2倍。

3.链表

上面我们介绍了顺序表，但是大家敏锐的发现了问题没有，我们在任意位置插入的时候，就加入在头部插入时间复杂度是多少？是不是O（N），而且它在扩容的时候面临着扩的过大，扩的过小的问题，那有没有一种结构让我们可以不挪动其它数据直接插入，而且需要多少我们申请多少，当然也是存在这样的一种数据结构的，这就是我们的链表。

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

注意：

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

一个数据结构，我们一般对它进行的操作就是进行增删查改，所以下面将对链表的一些接口进行实现。主要涉及以下接口：

typedef int SListDataType;
typedef struct SListNode
{SListDataType data;struct SListNode* next;
}SListNode;// 动态申请一个结点
SListNode* BuySListNode(SListDataType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SListDataType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SListDataType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SListDataType x);
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
// 因为单链表只能找到它后面的节点，找不到它前面的节点，双链表可以
void SListInsertAfter(SListNode* pos, SListDataType x);
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
// 删除了之后，pos后面位置的内容上哪找，会造成内存泄露
void SListEraseAfter(SListNode* pos);

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

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

上面所介绍的顺序表由于在通讯录当中已经介绍了大部分内容，所以只将部分接口进行实现，链表是一个新的知识点，因此进行详细的介绍，前面我们已经了解单链表它的一种形式，所以我们在开辟一个新节点时，要注意pList->next = NULL，不置为空，系统会随机生成一个地址，那如果我们不小心调用了就会造成越界访问。

补充知识：

链表在堆区开辟空间时，有可能缠绕在一起，为什么呢？因为堆区虽然向上生长的，但是存在下面的空间被释放掉，之后开辟在下面了。

// 单链表尾插
void SListPushBack(SListNode** pplist, SListDataType x)
{if (*pplist == NULL)//分情况，如果这种情况没有，下面cur->next就会导致对NULL访问的错误{*pplist = BuySListNode(x);}else{SListNode* cur = *pplist;while (cur->next != NULL){cur = cur->next;}cur->next = BuySListNode(x);//这里通过cur可以改外部变量的值，需要注意一下}
}

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

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

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

// 单链表的头插
void SListPushFront(SListNode** pplist, SListDataType x)
{SListNode* NewNode = BuySListNode(x);NewNode->next = *pplist;*pplist = NewNode;
}
// 单链表头删
void SListPopFront(SListNode** pplist)
{if (*pplist == NULL)//分情况，如果这种情况没有，下面cur->next就会导致对NULL访问的错误{return;//空就是没有要删的，直接返回}else{SListNode* cur = *pplist;*pplist = (*pplist)->next;free(cur);cur = NULL;//别忘记置成NULL，防止成为野指针}
}

头插相对比较简单，把我们新的节点中存放原先第一个节点的地址，然后把头指针的地址链接到我们所建立的新的节点上，时刻应该注意到链表的数据别丢失。

头删，建立一个临时的指针变量cur是一个关键，如果不建立，第一个节点已释放，找不到了之后的数据，把头指针指向第二个节点，那第一个节点的空间又无法释放，因此建立一个临时指针变量去存储其中一个地址，两个方法都可以。

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

任意位置之后插入的原理其实和头删是一样的，就是要注意临时指针变量的建立，防止内存泄漏和野指针的问题，需要把插入位置的两头连上。唯一需要注意的是，如果没有*pos==NULL的情况，就不需要传二级指针，其实*pos==NULL就是尾插，可以直接调用尾插接口就可以了。

// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{if (pos == NULL){return;}else if (pos->next == NULL){printf("你所要删除的位置之后没有数据\n");return;}else{SListNode* next = pos->next;pos->next = next->next;free(next);}
}

pos位置之后的删除也是同样的道理， 需要注意，就是说我们只能删除指定位置的后一个数据，插入也一样，因为我们都不知道这个位置的前一个节点的地址，这不是双链表，因此只能删除和插入pos之后的节点。

4.顺序表与链表区别

顺序表：可动态增长的数组，数据在数组中存储时必须是连续的。优点：可以随机访问，缓存命中率比较高。缺点：中间或者头部的插入删除很慢，需要挪动数据，时间复杂度是O(N)。空间不够时，增容会有一定消耗和空间浪费。

链表：逻辑上连续，物理上不一定连续。优点：头部插入只需修改指针指向即可，不需要挪动数据。缺点：缓存命中率比较低，不支持随机访问。

补充知识：

顺序表的缓存命中率比较高，为什么呢？因为顺序表的数据在物理上是连续的，因此cpu读取数据会从缓冲器上拿，第一次拿的时候，缓冲器没有我们在内存中存储的数据，因此缓冲器会去内存里拿，拿的时候会连续拿好几个数据，当cpu读取数据的时候就会先在缓冲器上拿，这样就会拿到数据，这就是缓冲命中率。

而链表物理上不是连续的因此缓冲器拿的时候拿不到连续的我们自己的数据，因此导致cpu每次在缓冲器上都拿不到数据，都会是缓冲器去内存上加载，再cpu在缓冲器上拿，而且也会导致缓冲器的污染，因为链表可能这一个那一个，缓冲器加载时候会把旁边不是它的数据也会捎带拿着，就会导致不是我们想要的数据也被加载到缓冲器。