顺序表与链表_顺序表是链表吗

思维导图：

 

顺序表与链表都是两种线性表，但是两者之间又有着许多的不同。顺序表是一种连续的空间，实际上就是数组。链表是不连续的空间，链表的空间是一块一块的开辟出来的。

两者的优点与缺点：

顺序表：

优点：1.顺序表的空间是连续的，所以能够支持下标的随机访问。

缺点：2.顺序表的空间是连续的容易造成空间的浪费。

链表：

优点：1.空间不连续，要用时才申请所以不会造成空间的浪费。

缺点：2.空间不连续不能支持下标的随机访问。

一，顺序表的操作

1.顺序表的结构

顺序表的本质是数组，所以要定义一个有数组的结构体。并且，这个顺序表是动态的。所以我们又需要一个表示顺序表内元素个数的变量size和一个表示顺序表容量的变量capacity。结构体定义如下：

 代码：

typedef  int dataType;
typedef struct List
{
	dataType* a;//数组
	int size;//个数
	int capacity;//容量
}List;

2.顺序表的初始化

 顺序表的初始化是一个必要的操作，数组指针先初始化为NULL，size初始化为0，capacity初始化为0.代码如下：

void ListInit(List* list)
{
	assert(list);//防止传入NULL
	list->a = NULL;
	list->size = 0;
	list->capacity = 0;
}

 3.顺序表的前插操作

顺序表的插入操作都要先判断顺序表内的空间是否够用，所以在插入数据到顺序表之前得先对顺序表的容量是否已满进行判断。先写一个判断容量的函数，代码如下：

代码：

void checkCapacity(List* list)
{
	assert(list);
	if (list->size == list->capacity)
	{
		int newcapacity = list->capacity==0 ? 4: 2 * list->capacity;
		dataType* tmp = (dataType*)realloc(list->a, sizeof(dataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail!");
			return;
		}
		list->a = tmp;
		list->capacity = newcapacity;
	}
	
}

 然后便是对顺序表的头插操作，头插操作插入的位置都是数组下标为0的位置。为了实现这一操作，我们就必须在数组不为空的条件下对数据进行后移然后将下标为0的位置腾出来。代码如下：

代码：

void LishPushFront(List* list, dataType x)
{
	assert(list);
	checkCapacity(list);//判断容量是否已满
	if (list->size == 0)//当数组为空时直接插入
	{
		list->a[0] = x;
	}
	else//数组不为空时要将原有数据后移将下标为0的位置腾出
	{
		int end = list->size - 1;
		for (int i = end;i >= 0;i--)
		{
			list->a[i + 1] = list->a[i];
		}
		list->a[0] = x;
	}
	list->size++;//插入后数组元素个数增加
	
}

4，顺序表的尾插操作

顺序表的尾插操作也是一个插入操作，所以尾插操作的第一步便是对数组的容量进行检查。然后才是数据的尾插操作。尾插不需要数据的移动，只需要在size的位置上插入数据即可。

代码如下：

代码：

void ListPushBack(List* list, dataType x)
{
	assert(list);
	checkCapacity(list);
	list->a[list->size] = x;
	list->size++;
}

5.顺序表的头删

顺序表的头删操作是一个移动数据覆盖然后将size减1的过程。说是删除数据其实就是覆盖掉数组下标为0的位置的数据。注意要对数组是否为空进行判断，当数组为空时不能够对这个顺序表进行删除！！代码如下：

代码：

void ListPopFront(List* list)
{
	assert(list);
	assert(list->size > 0);//对顺序表是否为空进行判断
	for (int i = 1;i < list->size;i++)
	{
		list->a[i - 1] = list->a[i];
	}
	list->size--;
}

 6.顺序表的尾删

顺序表的尾删操作比起顺序表的头删操作就显得更加简单。顺序表的尾删操作不需要覆盖只需要让数组的最后一个数据访问不到便可，也就是将size减1。注意要对数组是否为空进行判断，当数组为空时不能够对这个顺序表进行删除操作！！代码如下：

代码：

void ListPopBack(List* list)
 {
	 assert(list);
	 assert(list->size > 0);
	 list->size--;
 }

 7.顺序表的中间插入

顺序表的中间插入操作实现的功能就是将要插入的数据插入到要插入的下标pos位置处。中间插入的操作能够被头插1和尾插复用进而实现头插与尾插。中间插入操作代码如下：

代码：

void ListInsert(List* list, int pos, dataType x)
 {
	 assert(list);
	 assert(0 <= pos && pos <= list->size);//对pos的值进行判断以免造成越界
	 checkCapacity(list);
	 for (int i = list->size;i >= pos;i--)
	 {
		 list->a[i] = list->a[i - 1];
	 }
	 list->a[pos] = x;
	 list->size++;
 }

 8.顺序表的中间删除操作

顺序表的中间删除操作就是将下标为pos的位置上的数据删除的操作。也能被其他两个删除操作进行复用从而实现头删和尾删。和前两个操作一样中间删除的操作的删除就是覆盖下标pos位置上的1数据或者让pos数据上的数据不可访问。中间删除操作代码如下:

代码：

void ListErase(List* list, int pos)
 {
	 assert(list);
	 assert(list->size>0);
	 assert(0 <= pos && pos < list->size);
	 for (int i = pos;i < list->size-1;i++)
	 {
		 list->a[i] = list->a[i + 1];
	 }
	 list->size--;
 }

9.顺序表内数据的寻找

在顺序表内寻找某个数据其实并不难，不过就是遍历顺序表内的数组然后看看有没有匹配的数据。如果有便返回数据的下标，没有便返回不存在的下标-1。代码如下：

 代码：

int ListFind(List* list, dataType x)
 {
	 assert(list);
	 for (int i = 0;i < list->size;i++)
	 {
		 if (list->a[i] == x)
			 return i;
	 }
	 return -1;
 }

10，顺序表数据的修改

 顺序表内数据的修改这一操作是和上一个查找操作配合着使用的。只有要查找的元素存在才能替换。否则便不能。代码如下：

代码：

void ListModify(List* list,int i,dataType x)
 {
	 assert(list);
	 if (i == -1)//i这个值是通过ListFind函数找到的下标
	 {
		 printf("要修改的值不存在！\n");
		 return;
	 }
	 else
	 {
		 list->a[i] = x;
	 }
 
 }

11.顺序表的销毁

太简单了，直接上代码：

代码：

 void ListDestory(List* list)
 {
	 assert(list);
	 free(list->a);
	 list->a = NULL;
	 list->size = list->capacity = 0;
 }

二，链表的创建与操作

1.链表的创建

链表是一种不连续的空间，但是又要将一个一个的节点联系起来并且链表里还要放置一些数据。所以链表的结构里就要有两个变量，一个是存下一个链表节点的指针，一个是存当前节点内数据的变量。链表节点的结构代码如下：

代码：

typedef int  dataType;
typedef struct listNode
{
	dataType val;//存放当前节点内的数据
	struct listNode* next;//存放下一个节点的地址
}listNode;

 2.链表的头插操作

链表的头插操作在执行时要分两种情况。第一种情况是链表为NULL时，你需要让链表的头节点头节点指向newnode。当链表不为NULL时，newnode指向的next就是原来的头节点，然后让头节点指向新的头节点。代码如下：

代码：

void SlistPushFront(SListNode** pphead, dataType x)
{
	assert(pphead);
	assert(pphead);//防止传入空指针
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		perror("malloc fail\n");
		return;
	}
	newnode->val = x;
	newnode->next = NULL;
	//当链表为NULL
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	//当链表不为NULL时
	else
	{
		newnode->next = *pphead;
		*pphead = newnode;
	}
}

 3.链表的尾插操作

链表的尾插操作其实与头插操作差不多。最主要的是当链表不是NULL时需要去找到尾节点，然后让尾节点的next指向newnode。代码如下：

代码：

void SlistPushBack(SListNode** pphead, dataType x)
{
	assert(pphead);//防止传入空指针
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		perror("malloc fail\n");
		return;
	}
	newnode->val = x;
	newnode->next = NULL;
	//当链表为NULL
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
    //找尾插入值
	else
	{
		SListNode* tail = *pphead;
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

以上两个代码能复用的地方：生成节点的地方

代码：

SListNode* BuyNode(dataType x)
{
	SListNode* node = (SListNode*)malloc(sizeof(SListNode));
	if (node == NULL)
	{
		perror("malloc fail\n");
		return;
	}
	node->val = x;
	node->next = NULL;
	return node;
}

改进后的代码：

头插：

void SlistPushFront(SListNode** pphead, dataType x)
{
	assert(pphead);
	assert(pphead);//防止传入空指针
	SListNode* newnode = BuyNode(x);
	if (newnode == NULL)
	{
		perror("malloc fail\n");
		return;
	}
	newnode->val = x;
	newnode->next = NULL;
	//当链表为NULL
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	//当链表不为NULL时
	else
	{
		newnode->next = *pphead;
		*pphead = newnode;
	}
}

尾插：

void SlistPushBack(SListNode** pphead, dataType x)
{
	assert(pphead);//防止传入空指针
	SListNode* newnode = BuyNode(x);
	if (newnode == NULL)
	{
		perror("malloc fail\n");
		return;
	}
	newnode->val = x;
	newnode->next = NULL;
	//当链表为NULL
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SListNode* tail = *pphead;
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

四，链表的头删操作

链表的头删操作也是一个简单的操作，这个操作就是将头节点给销毁掉然后再让头指针指向第二个节点。这也要分两种情况来删除，第一种情况是链表为NULL不能删，第二种情况便是当链表内只有一个头节点时直接删除这个节点然后置空便可以了。第三种情况是当链表内有多个节点时需要将第二个节点的地址保存下来然后再将头节点删掉并置空。代码如下：

代码：

void SListPopFront(SListNode** pphead)
{
	assert(pphead);
	//当链表为空时不能够继续删除
	assert(*pphead);
	//只有一个节点时
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//有两个节点时
	else
	{
		SListNode* next = (*pphead)->next;
		free(*pphead);
		*pphead = next;
	}
 
}

五，链表的尾删

链表的尾删操作就是一个将链表的尾节点删除的操作。这个操作也得分三种情况：

1.链表为NULL不删   2.链表内只有一个节点，直接删除第一个节点  3.链表内有多个节点，找到最后一个节点删除置空。代码如下：

 代码：

void SListPopBack(SListNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	//只有一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SListNode* tail = *pphead;
		SListNode* prev = NULL;//记录尾节点的前一个节点
		while (tail->next)//找尾节点
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);//去尾
		tail = NULL;//将尾节点置空
		prev->next = NULL;//尾节点的前一个节点的next指向NULL,消除野指针问题
	}
}

六，链表的中间插入

链表的中间插入操作讲的是在链表的某个数据的位置处插入一个操作者想要插入的值。这个操作的关键点就在于找到要插入位置的前一个位置然后将这个位置的nex指向给改掉，改成指向我们想要插入的值。代码如下：

代码：

void SListInsert(SListNode** pphead,dataType target ,dataType x)
{
	assert(pphead);
	SListNode* cur = *pphead;//表示当前节点
	SListNode* prev = NULL;//表示当前节点的前一个节点
	while (cur)
	{
		SListNode* newnode = BuyNode(x);
		if (cur->val == target)
		{
			if (prev == NULL)//当第一个节点就是目标值所在节点时
			{
				newnode->next = *pphead;
				*pphead = newnode;
			}
			else//当其他节点才是目标值所在节点时
			{
				prev->next = newnode;
				newnode->next = cur;
 
			}
			return ;
	   }
		prev = cur;
		cur = cur->next;
	}
//当链表循环完以后链表内便没有数据为目标值的节点
	printf("链表内没有要找的目标值\n");
	return ;
}

七，链表的中间删除

链表的中间删除操作的作用是将目标值所在节点删除，释放掉。这个操作的代码和中间插入的代码有异曲同工之妙，都要找到要删除的节点的前一个节点然后再执行下列的操作。也有两种情况要讨论——1，当第一个节点为目标节点   2，当其它节点为目标节点。

void SListErase(SListNode** pphead, dataType target)
{
	assert(pphead);
	assert(*pphead);
	SListNode* cur = *pphead;
	SListNode* prev = NULL;
	while (cur)
	{
		SListNode* next = cur->next;
		if (cur->val == target)
		{
			if (prev == NULL)
			{
				free(cur);
				cur = next;
			}
			else
			{
				free(cur);
				prev->next = next;
 
			}
			return ;
		}
		prev = cur;
		cur = cur->next;
 
	}
	printf("链表内没有要删除的目标节点\n");
	return;
}

当然，中间删除与插入的代码的写法不止这一种，我们还可以通过寻找某个值所在的节点来对链表进行中间插入与删除。这里读者可以自己思考一下该如何写代码。 如果要写这样一个代码的话还需要写一个find函数来找到这个节点然后利用这个函数来与中间插入，中间删除函数配合着使用。

八，链表的销毁

 这个代码比较简单，但是一定要记得在删除掉当前节点的时候要记录一下之后的节点。代码如下：

代码：

void SListDestory(SListNode** pphead)
{
	SListNode* cur = *pphead;
	while (cur)//一个一个节点销毁
	{
		SListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;//最后将外面的list置空
}