顺序表和链表【数据结构】【基于C语言实现】【一站式速通】

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使

用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...

线性表和链表的物理结构：

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，

线性表在物理上存储时，通常以数组和链式结构的形式存储。画出它们的物理结构只是为了方便我们理解它们各自的特性。

---

顺序表

在计算机科学中，顺序表是一种常见且重要的数据结构。顾名思义，顺序表是一种按照元素在内存中的物理顺序进行存储和访问的数据结构。它可以看作是一段连续的内存空间，用于存储相同类型的元素。?

顺序表的优点

1.支持随机访问：由于顺序表在内存中是连续存储的，因此可以通过下标直接访问任何一个元素。这使得顺序表具有高效的随机访问能力，时间复杂度为O(1)。

2.有序存储：顺序表中的元素按照其在数组中的位置顺序存储，因此保持了元素的逻辑顺序。这使得顺序表适用于需要保持元素有序性的场景，例如排序、查找等操作。

3.内存紧凑：顺序表中的元素在内存中是连续存储的，不需要额外的指针来连接各个元素，因此可以更好地利用内存空间。这使得顺序表相对于链表等动态数据结构来说，具有更小的存储空间和更高的存取效率。

顺序表的实现

顺序表一般都是靠数组来进行存储，如果在栈上开辟一块空间，我们需要指定数组的元素个数，如果指定个数过少，我们的数据没有办法进行存储；如果指定个数过多，又会造成资源的浪费。所以，我们选择在堆上开辟空间，这样我们可以实现一个动态存储的数据表，按需分配空间。下面我们来着手实现一个顺序表：

1.结构体的定义

因为要实现一个动态增长的版本，所以我们要给定一个数组的指针，一个记录有效数据个数的变量，和一个代表数组容量的变量，用以在我们空间不足时候进行扩容操作。

//实现一个顺序表
typedef struct Sequence
{
	Seqtype* a;
	int size;
	int capacity;
}SeqList;

2.初始化数组

这里要传的是结构体的指针，因为我们需要改变结构体里面的值，需要传址调用

当我们只定义而不进行初始化的时候，我们的指针会是野指针，size和capacity都会是随机数，因此我们要进行一下初始化

void SeqListInit(SeqList* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

?3.插入数据

当插入数据的时候，我们就要考虑空间够不够的问题了，经过思考其实可以发现,size是有效数据的个数,capacity是容量，当有效数据的个数刚好等于容量的时候其实就是要扩容的时候。刚开始时，我们还没有分配空间，所以我们先给定容量为4，后期空间不足再调整即可

void SeqListPushBack(SeqList* ps, Seqtype x)
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		//扩容---三目操作符
		int newcapacity = ps->capacity > 0 ? ps->capacity * 2 : 4;
		Seqtype* newsapce = (Seqtype*)realloc(ps->a ,sizeof(Seqtype) * newcapacity);
		if (newsapce == NULL)                                                      
		{
			printf("malloc fail\n");
			exit(-1);
		}
		ps->a = newsapce;
		ps->capacity = newcapacity;
	}
	ps->a[ps->size++] = x;
}

注意：在分配空间时，我们一定要使用realloc，而不是malloc。当使用realloc时，如果给定一个空指针，那他此时就是malloc的功能。realloc与malloc的一个重要的区别就是：realloc在堆上申请空间的时候，会返回申请到的空间的指针，并把原先的内容按字节拷贝到该指针指向的数组中，而malloc不会拷贝，切记切记！！！

4.其余接口函数的实现

//接口函数
void SeqListPrint(SeqList* ps);
void SeqListInit(SeqList* ps);
void SeqListPushBack(SeqList* ps, Seqtype x);
void SeqListPushFront(SeqList* ps, Seqtype x);
void SeqListPopBack(SeqList* ps);
void SeqListDestroy(SeqList* ps);
void SeqListPopFront(SeqList* ps);
int SeqListFind(SeqList* ps, Seqtype x);
void SeqListInsert(SeqList* ps, Seqtype x, int pos);
void SeqListCheckCapacity(SeqList* ps);

这里的接口函数太多，不再一一赘述，只把几个接口函数的思想进行分析

void SeqListPrint(SeqList* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

void SeqListCheckCapacity(SeqList* ps)
{
	if (ps->size == ps->capacity)
	{
		//扩容
		int newcapacity = ps->capacity > 0 ? ps->capacity * 2 : 4;
		Seqtype* newsapce = (Seqtype*)realloc(ps->a, sizeof(Seqtype) * newcapacity);
		if (newsapce == NULL)                                                       
		{
			printf("malloc fail\n");
			exit(-1);
		}
		ps->a = newsapce;
		ps->capacity = newcapacity;
	}
}

void SeqListPopBack(SeqList* ps)
{
	assert(ps);
	assert(ps->size > 0);
	ps->size--;
}

void SeqListPushFront(SeqList* ps, Seqtype x)
{
	assert(ps);
	SeqListCheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->a[end+1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;
	ps->size++;
}

void SeqListPopFront(SeqList* ps)
{
	assert(ps);
	assert(ps->size > 0);
	int begin = 1;
	while (begin < ps->size)
	{
		ps->a[begin -1] = ps->a[begin];
		begin++;
	}
	ps->size--;
}

int SeqListFind(SeqList* ps, Seqtype x)
{
	assert(ps);
	//遍历数组
	int i = 0;
	for ( i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			break;
		}
	}
	return i;
}

void SeqListInsert(SeqList* ps, Seqtype x, int pos)
{
	assert(ps);
	assert(pos < ps->size);
	SeqListCheckCapacity(ps);

	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}

我们发现在插入数据的时候，不管是头插还是为尾插，只要是插入数据，都需要进行判断空间是否充足的处理，因此我们决定把这个检查空间的功能封装成一个函数，方便我们后续的调用，这里其实就是代码复用。

void SeqListCheckCapacity(SeqList* ps)
{
	if (ps->size == ps->capacity)
	{
		//扩容
		int newcapacity = ps->capacity > 0 ? ps->capacity * 2 : 4;
		Seqtype* newsapce = (Seqtype*)realloc(ps->a, sizeof(Seqtype) * newcapacity);
		if (newsapce == NULL)                                                       
		{
			printf("malloc fail\n");
			exit(-1);
		}
		ps->a = newsapce;
		ps->capacity = newcapacity;
	}
}

其实，在实现完Insert函数和Erase函数之后，我们就会发现，头删尾删都可以进行代码复用了，我们的代码能够得到极大的简化。大家可以试着实现一下。

5.释放内存

因为我们的数组是开辟在堆上面的，所以我们需要在使用完之后释放掉这块内存，否则就会造成内存泄漏。

void SeqListDestroy(SeqList* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

顺序表的缺陷

1.空间不够了，需要扩容，扩容是有消耗的，会产生很多内存碎片。

2.头部/中间位置的插入删除，需要挪动数据，时间复杂度为O(N)，挪动数据也是有消耗的

3.为避免重复扩容，一次一般都是按倍数去扩容（一般是二倍），还可能存在一定的空间浪费

?针对顺序表的缺陷，设计出了链表。按需申请空间，不用了就释放空间（更加合理的使用了空间）

头部中间插入删除数据，不需要挪动数据。

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

单向链表的优点

因为链表是根据顺序表的缺陷进行设计的，所以链表的优势就在于，它里面的数据不是连续存储的，而是通过一个个的指针链接起来的。因此不存在会浪费空间，造成空间碎片的问题。

1.动态性：链表的大小可以动态地进行调整，不需要事先预留固定的内存空间。在插入或删除节点时，只需要调整指针的指向，而不需要移动其他节点。这使得链表适用于频繁进行插入和删除操作的场景。

2.灵活性：相比于顺序表，链表的结构更加灵活。链表可以根据实际需求设计成单向链表、双向链表或循环链表。单向链表只有一个指针指向下一个节点，双向链表则同时具有前向和后向指针，而循环链表的尾节点指针指向头节点。根据实际需求，我们可以选择合适的链表类型。

3.内存利用率高：链表在内存中不要求连续存储，因此可以更好地利用内存空间。相比于顺序表，链表可以动态地分配内存，并且不会产生内存碎片的问题。

单向链表的实现

1.链表的定义?

我们可以根据链表的物理结构来设计链表，我们首先要定义一个变量来存储数据，因为我们还要存储下一个数据的地址，所以我们还要定义一个指针。

typedef struct Slist
{
	SLtype data;
	struct Slist* next;
}SLTnode;

2.链表的初始化

因为我们不直接把所需空间直接全部初始化完成，而是一个一个地存储，通过该结构体中指向下一个数据的指针找到下一个数据，所以链表的初始化就是先创建一个新节点，并让其中的指针指向空，防止野指针。

SLTnode* CreatListNode(SLtype x)
{
	//创建一个新的节点
	SLTnode* newnode = malloc(sizeof(SLtype));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

3.插入数据

插入数据时我们写的是二级指针，有些人可能不理解。在此进行说明：

为什么要传二级指针？

类比int类型的数据，我们在传址调用的时候,&该变量，我们在函数中用的是(int *)指针进行接受。我们如果要传址调用(int *)类型的变量，就要用二级指针(int **)来进行接收。

void SLTpushback(SLTnode** pphead, SLtype x)
{
	SLTnode* newnode = CreatListNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找到尾节点
		SLTnode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		//链接
		tail->next = newnode;
	}
}

3.其余接口函数的实现

void SLTprint(SLTnode* phead);
void SLTpushback(SLTnode** phead, SLtype x);
void SLTpushfront(SLTnode** phead, SLtype x);
void SLTpopback(SLTnode** phead);
void SLTpopfront(SLTnode** phead);
SLTnode* SLTfind(SLTnode* phead, SLtype x);
void SLTinsert(SLTnode** phead, SLTnode* pos , SLtype x);
void SLTDestory(SLTnode** phead);

?其余接口函数的实现不再一一赘述，只挑选重点部分进行说明

void SLTprint(SLTnode* phead)
{
	SLTnode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

void SLTpushback(SLTnode** pphead, SLtype x)
{
	SLTnode* newnode = CreatListNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找到尾节点
		SLTnode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		//链接
		tail->next = newnode;
	}
	
}

void SLTpushfront(SLTnode** pphead, SLtype x)
{
	SLTnode* newnode = CreatListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

void SLTpopback(SLTnode** pphead)
{
	assert(*pphead != NULL);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTnode* tail = *pphead;
		SLTnode* previous = *pphead;
		while (tail->next)
		{
			previous = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		previous->next = NULL;//注意：previous是一个指针，指向的是尾节点的前一个节点的地址，
		                      //我们的目的是要把该内存块中指向下一内存的地址给置空
	}
	//错误方法
	/*SLTnode* tail = *pphead;
	while (tail->next)
	{
		tail = tail->next;
	}
	free(tail);
	tail = NULL;*/   //这种方式没办法使新链表指向原最后一个数据的指针置空，造成野指针
}

void SLTpopfront(SLTnode** pphead)
{
	assert(*pphead != NULL);
	SLTnode* next = (*pphead)->next;
	free(*pphead);
	*pphead = NULL;
}
SLTnode* SLTfind(SLTnode* phead, SLtype x)
{
	assert(phead != NULL);
	//遍历链表，找到要查找的值
	SLTnode* tail = phead;
	while (tail->next)
	{
		if (tail->data == x)
		{
			return tail;
		}
		tail = tail->next;
	}
	return NULL;
}

void SLTinsert(SLTnode** phead, SLTnode* pos, SLtype x)
{
	assert(*phead != NULL);
	SLTnode* newnode = CreatListNode( x );
	if (*phead == pos)
	{
		SLTpushfront(phead , x);
	}
	else
	{
		SLTnode* previous = *phead;
		while (previous->next != pos)
		{
			previous = previous->next;
		}
		previous->next = newnode;
		newnode->next = pos;
	}
}

我们在删除尾部的数据时，不能只把最后一个数据的空间free掉，还要把它的前一个数据中指向该数据的指针给置成NULL，而在单向链表中，我们可以轻松取得链表的头和尾，但是如果要访问倒数第二个值，还需要额外的指针，这也是单向链表的一个弊端！

5.释放内存

链表的节点是malloc出来的，为了防止内存泄漏，我们在使用完之后，要进行内存释放。

链表的内存释放有点特殊，因为它们不是连续存放的，开辟了多个节点，每个节点都保留着指向下一个节点的指针，所以我们要把这些节点全部free掉。

//销毁链表
void SLTDestory(SLTnode** phead)
{
	SLTnode* cur = *phead;
	while (cur != NULL)
	{
		SLTnode* next = cur->next;
		free(cur);
		cur = next;
	}
	*phead = NULL;
}

单向链表的缺陷

1.不支持随机访问：在删除数据时，我们发现了，每一个数据，都要存一个指针去链接后面的数据节点，不支持随机访问（用下标直接访问第i个）【顺序表支持】

2.删除节点需谨慎：删除链表中的某个节点时，需要修改前一个节点的指针，将其指向下一个节点，然后释放被删除节点的内存。如果不仔细处理指针的更新，可能会导致内存泄漏或者链表断裂。

双向链表

双向链表的优点

?双向链表的设计可以看做是单向链表的扩展，每个节点除了存储数据外，还需要存储前继节点和后继节点的指针。这种设计使得双向链表具有以下优点：

1.可以双向遍历：由于每个节点都有前继节点和后继节点的指针，因此可以从任意一个节点开始，顺着前继节点或后继节点进行遍历。这使得双向链表在某些场景下具有比单向链表更高的遍历效率。

2.方便进行插入和删除操作：在双向链表中插入或删除节点时，只需要修改相邻节点的指针即可，不需要像单向链表那样找到前一个节点来修改指针。这使得双向链表在插入和删除操作方面更加方便。

双向链表的实现

1.双向链表的初始化

双向链表基于单向链表，只不过是又加入了一个指针，我们注意命名规范，直接定义即可。

typedef struct ListNode
{
	DLtype data;
	struct ListNode* prev;
	struct ListNode* next;
}DL;

2.链表的初始化

?初始化时需要注意的是，当链表中只有一个数据的时候，这时候的两个指针都指向自己。

DL* ListInit(DL* phead)
{
	DL* newnode = (DL*)malloc(sizeof(DL));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->prev = newnode;
	newnode->next = newnode;
	return newnode;
}

3.其余接口函数的实现

DL* ListInit(DL* phead);
void Listprint(DL* phead);
void Listpushfront(DL* phead, DLtype x);
void Listpushback(DL* phead, DLtype x);
void Listpopfront(DL* phead);
void Listpopback(DL* phead);
void ListInsert(DL* pos,DLtype x);
void Listpop(DL* pos);
void Listfind(DL* phead);

这里跟单向链表的逻辑其实相差不多，只是过程比较繁琐，在这里我就挑选其中的几个进行实现?

void Listprint(DL* phead)
{
	assert(phead);
	DL* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

void Listpushfront(DL* phead, DLtype x)
{
	ListInsert(phead->next, x);
}

void Listpushback(DL* phead, DLtype x)
{
	ListInsert(phead, x);
}

void ListInsert(DL* pos, DLtype x)
{
	DL* newnode = (DL*)malloc(sizeof(DL));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;

	DL* prev = pos->prev;
	if (prev == NULL) // 如果pos是头节点
	{
		newnode->next = pos;
		pos->prev = newnode;
	}
	else // 正常情况
	{
		prev->next = newnode;
		newnode->prev = prev;
		newnode->next = pos;
		pos->prev = newnode;
	}
}

?4.释放内存

我们在释放current的内存之前保存下一个空间的地址，然后cur一直往后面走，free掉经过的空间，当cur指向NULL的时候，所有的空间都被free完了?

void ListFree(DL** phead)
{
    DL* current = phead;

    while (current != NULL)
    {
        DL* next = current->next;
        free(current);
        current = next;
    }
   *phead = NULL;
}

?双向链表的缺陷

1.需要更多的存储空间：相比于单向链表，双向链表需要多存储一个指针，因此需要更多的存储空间。这对于需要大量使用链表的应用程序来说可能会成为内存限制的瓶颈。

2.实现较为繁琐：相比于单向链表，双向链表需要同时操作两个指针，很容易把人绕晕。

---

总结

通过上面的分析，我们发现不管是线性表还是单向链表，甚至是双向链表，都有自己的优缺点，我们要根据实际的使用场景来选择要使用哪一种方式来进行存储数据，快捷、高效地处理问题。

今天的分享到这里就结束了，欢迎讨论交流~