【数据结构】顺序表和单链表的区别

向右看齐 2022-03-15 11:40 244阅读 0赞

little fairy 的第x篇博客。

顺序表和链表都是常见的线性结构。

顺序表和链表最基本的差异为：顺序表，逻辑相邻，物理也相邻（可以直接访问其前驱和后继）。链表，逻辑相邻，物理不相邻（需要通过辅助信息才能访问其前驱和后继）。

顺序表：储存在连续空间中。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2lmaXdlcmU_size_16_color_FFFFFF_t_70][]

（1）结构体//本例为不定长的顺序表。定长的顺序表相当于一个给定长度的数组，储存数据个数有限。

typedef struct  
\{  
int \*elem;//指向动态内存的指针  
int length;//有效数据个数 //用于判断是否为满表  
int listsize;//总单元个数 //若有效数据个数==总单元个数，则表满，若想继续往其中添加数据，则需要对顺序表进行扩容  
\}DSeqList,\*PDSeqList;

2）可以通过下标访问元素，时间复杂度为O(1)。

eg:ps->elem\[pos\];//ps为传入的参数名（PDSeqList ps），pos为所要访问的位置

3）进行插入和删除操作时，即需要修改已有结构时，需要同时对后续数据进行相应处理。（改变了部分数据的地址）

//判断顺序表是否为满

static bool IsFull(PDSeqList ps)  
\{  
return GetLength(ps) == ps->listsize;  
\}

//对顺序表进行扩容，扩大为原来的二倍

static void IncDSeqlist(PDSeqList ps)  
\{  
ps->listsize \*= 2;  
ps->elem = (int \*)realloc(ps->elem,ps->listsize\*sizeof(int));//用realloc进行扩容，保存已有数据并增容。  
\}

//将val插入在ps表中的pos位置  
bool Insert(PDSeqList ps,int val,int pos)  
\{  
assert(ps != NULL); //断言

if(pos < 0 || pos > ps->length) //判断需要插入的pos位置是否合法。pos必须在顺序表已有位置上，不能小于0，也不能大于顺序表的有效位置。  
\{  
return false;  
\}  
if(IsFull(ps)) //如果当前顺序表已经满了，则需要对其进行扩容后进行相应操作。  
\{  
IncDSeqlist(ps);  
\}

for(int i = ps->length;i >= pos;i--) //需要将pos及pos之后的数据向后移一位，使pos位置空余，后插入数据。  
\{  
ps->elem\[i+1\] = ps->elem\[i\];  
\}

ps->elem\[pos\] = val;  
ps->length ++; //数据插入或删除后，要对其有效长度进行相应处理。

return true;  
\}  
（4）逆置顺序表时只需将前后相对位置交换数据。

单链表：可以储存在连续空间中，也可以在不连续的空间中。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2lmaXdlcmU_size_16_color_FFFFFF_t_70 1][]

（1）结构体  
typedef struct Node //本例以单链表  
\{  
int data; //数据  
struct Node \*next;//后继指针 //储存后一个节点的地址  
\}Node,\*List; //List=Node\*

（2）只能通过后继指针访问节点,每次访问都要遍历链表。时间复杂度为O(n);

for(Node \*p = plist,int i = 0;p->next != NULL && i<pos;p = p->next;i++);

（3）进行插入和删除操作时，即需要修改已有结构时，只需要对插入位置进行相应处理，不改变其他数据的地址。

//头插，将数据插入到链表的第一个位置 时间复杂度为O(1)  
bool Insert\_head(List plist,int val)  
\{  
assert(plist != NULL);  
  
Node \*p = (Node \*)malloc(sizeof(Node)); //动态申请内存以保存新插入的结点  
p->data = val;

p->next = plist->next; //连接新节点与原有链表插入位置的后续结点  
plist->next = p; //断开原有链表，与新节点相连接。 \*\*\*必须先连接再断开。

return true;  
\}

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2lmaXdlcmU_size_16_color_FFFFFF_t_70 2][]

如果先断开再插入，则plist->next被断开，即没有办法找到plist的后继。

尾插需要找到最后一个结点，然后在节点后进行插入，需要遍历链表时间复杂度为O(n)。

4）逆置单链表。利用头插完成逆置

void Reverse(List plist)  
\{  
assert(plist != NULL);

Node \*p = plist->next; //定义一个节点保存第一个数据节点，以新节点来遍历全部数据节点  
plist->next = NULL; //将链表置空

while(p != NULL) //新节点不为空时，进入循环  
\{  
Node \*q = p->next; //每次都以旧节点的后继为新节点，以便便利后续链表

p->next = plist->next; //将旧节点以头插方式插入链表，以完成链表逆置  
plist->next = p;

p = q;  
\}  
\}

注意：

1、顺序表插入删除时间复杂度均为O(n)，但其在尾部进行操作时时间复杂度为O(1)，通过下标方式访问节点，时间复杂度为O(1)。当应用更多为查询操作时，使用顺序表。

2、顺序表要防止其数据溢出，需要进行判满、扩容等操作。gcc扩容为两倍，微软STL为1.5倍。

3、单链表插入删除时间复杂度为O(n),但其在头部进行操作时时间复杂度为O(1),通过后继指针访问节点，时间复杂度为O(n)。当应用更多为在头部进行插入删除操作时，用单链表。

4、单链表不需要进行判满操作，每次进行插入操作时要动态申请内存，删除时要释放删除的节点内存，防止内存泄漏。

5、顺序表的清空和销毁相同，清空数据域即可。

6、单链表的清空只需释放数据域内存，销毁则需要对头节点进行销毁。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2lmaXdlcmU_size_16_color_FFFFFF_t_70]: /images/20220315/57ec40f1224340c7a2ae5648e7d9c959.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2lmaXdlcmU_size_16_color_FFFFFF_t_70 1]: /images/20220315/b6f83b0a43bc4d05b8cf125e22e42796.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2lmaXdlcmU_size_16_color_FFFFFF_t_70 2]: /images/20220315/89073ffdf3594504895c4160320afb9b.png