【C语言之线性表链式存储结构】

C语言之线性表链式存储结构

前言

线性表存在不足的解决办法：`
线性表最大的缺点就是插入和删除时需要移动大量元素，这需要耗费大量时间；因此就引出链式存储结构，用任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续。

一、线性表链式存储结构定义

定义：
以前顺序结构中，每个数据元素只需要存数据元素就可以了，但链式结构中，为了将链表连接起来，每个元素不仅要存储数据元素信息，还需要存储它的后继元素的存储地址。

二、相关概念

1.结点

链表结点由数据域（存放本身信息）和指针域（指向后继结点的指针）构成。如下图所示：

1.头指针

对于线性表来说，总得有个头有个尾，链表也不例外，我们把链表中的第一个结点的存储位置叫做头指针，整个链表的存取就必须是从头指针开始进行了。
最后一个结点的指针为空（NULL）。
有时候我们为了更方便的对链表进行操作，会在单链表的第一个结点前附设一个结点，称为头结点。
头结点的数据域可以不存储任何信息，也可以存储如线性表长度等附加信息。

空链表：

带头结点的单链表：

不带头结点的单链表：

三、代码描述

1.单链表结点定义

typedef int ElemType;可以随着数据元素类型不用，自己定义
链表的结构体
struct Node
{
	ElemType data;
	struct Node* next;
}Node;

typedef  struct Node* LinkList;链表指针别名

总这个结构定义中，我们也可以知道，结点由存放数据元素的数据域和存放后继结点地址的指针域组成。假设p是指向线性表第i个元素的指针，则该结点ai的数据域，可以用p->data来表示，结点ai的指针域，可以用p->next来表示。p->next指向（意思就是存储第i个元素的地址）第i+1个元素。也就是说，如果p->data=ai，p->next->data=ai+1;

1.单链表的创建

单链表创建算法思路：

• 初始化空链表L-创建头结点
• 声明中间变量指向头结点，用于遍历链表
• 循环
• 生成新的结点
• 新的结点指针指向头结点（指针）
• 头结点指针指向新结点

头插法
LinkList CreatListHead(int len)
{
	LinkList L = (LinkList)malloc(sizeof(Node));//创建个头节点
	LinkList temp=L;                   //声明一个中间变量，指向头结点，用于遍历链表（曾因没有这个中间变量而出错）
	temp->next = NULL;

	for (int i=0;i<len;i++)
	{
		LinkList p= (LinkList)malloc(sizeof(Node)); 
		scanf_s("%d",&p->data);
		p->next = temp->next;     //新结点的next指针,指向开始结点（temp->next是头结点的地址）
		temp->next = p;                //头结点的next指针指向新结点
	}
	return (LinkList)L;
}

解释说明：p->next是下一个结点指针的地址
p是结点指针

尾插法

链表的创建,建立带头节点的单链线性表L，随机产生Ｎ个元素值
LinkList CreatListTail(int len)
{
	LinkList L = (LinkList)malloc(sizeof(Node));创建个头节点
	LinkList temp = L;                   声明一个中间变量，指向头结点，用于遍历链表（曾因没有这个中间变量而出错）
	temp->next = NULL;
	for (int i = 0; i < len; i++)
	{
		LinkList p = (LinkList)malloc(sizeof(Node));
		scanf_s("%d", &p->data);
		temp->next = p;   头结点指向新的结点（存储新结点地址）
		temp = p;                将新结点变成头结点等待下一个新结点插入
	}
	temp->next = NULL;将最后一个结点的NEXT结点为空，表示链表结束
	return (LinkList)L;
}

2.单链表的查找

因为链表不支持随机访问，即链表的存取方式是顺序存取的（注意“存储”与“存取”是两个不一样的概念），所以要查找某结点，必须通过遍历的方式查找。例如：如果想查找第3个结点，必须先遍历走过第1~2个结点，才能得到第3个结点。
单链表查找算法思路：

• 链表存在，输入要查找的值
• 声明中间变量指向头结点，用于遍历链表
• 循环
• 指针后移遍历链表
• 将链表中与查找值相等的数据返回

int SearchList(LinkList L,int elem)
{
	LinkList temp;
	temp = L;
	int position = 0;用于返回数据在链表中的位置
	while (temp->next)
	{   
		position++;
		temp = temp->next;指针后移遍历链表
		if (elem == temp->data)
		{
			printf_s("Searchdata=%d,postion=%d\n", temp->data, position);
		}
		return position;
	}
	return 0;
}

3.在单链表中，替换某一个位置的数据

单链表替换算法思路：

• 链表存在，输入要替换的位置，要替换的数值
• 声明中间变量指向头结点，用于遍历链表
• 循环
• 指针后移遍历链表，到要替换的位置，跳出循环
• 将要替换的值，赋值到数据域
• 返回链表的头结点

LinkList  ReplaceList(LinkList L,int pos,int elem)
{
	LinkList temp = L;
	temp = temp->next;指向开始结点（注意头结点与开始结点区别）头结点的后继结点为开始结点
	for (int i = 0; i < pos; i++)
	{
		temp = temp->next;
	}
	temp->data = elem;
	return L;
}

4.在单链表中，某一个位置插入数据

单链表插入算法思路：

• 链表存在，输入要插入的位置，要插入的数值
• 声明中间变量指向头结点，用于遍历链表
• 循环
• 指针后移遍历链表，找到插入位置前的结点
• 新建结点，将要插入的数据，赋值到新建结点的数据域
• 返回链表的头结点
  

LinkList InsertList(LinkList L,int pos,int elem)
{
	LinkList temp = L;
	int i = 0;
	temp = temp->next;指向开始结点

	for (i = 0; i < pos-1; i++)
	{
		if ((temp == NULL) || (i > pos - 1))
		{
			printf("%s:Insert false!\n", __FUNCTION__);
			return L;
		}
		temp = temp->next;
	}
	LinkList new = (LinkList)malloc(sizeof(Node));
	new->data = elem;
	new->next = temp->next;新建结点指向插入的下个结点
	temp->next = new;插入位置的结点指针指向新建结点
	return L;

}
第二种写法

LinkList InsertList(LinkList L, int pos, int elem)
{
	LinkList temp = L;	//引入一个中间变量，用于循环变量链表
	int i = 0;
	/* 首先找到插入结点的上一结点，即第pos-1个结点 */
	while( (temp!=NULL)&&(i<pos-1) )
	{
		temp = temp->next;
		++i;
	}
	/* 错误处理：链表为空或插入位置不存在 */
	if( (temp==NULL)||(i>pos-1) )		
	{
		printf("%s:Insert false!\n",__FUNCTION__);
		return (LNode*)temp;
	}
	LinkList new = (LinkList)malloc(sizeof(Node));	//创建新结点new
	new->data = elem;		插入的新结点的数据域
	new->next = temp->next; 新结点的next指针指向插入位置后的结点
	temp->next = new;		插入位置前的结点的next指针指向新结点
	return L;返回头结点

4.在单链表中，某一个位置删除数据

单链表插入算法思路：

• 链表存在，输入要插入的位置，要插入的数值
• 声明中间变量指向头结点，用于遍历链表
• 循环
• 指针后移遍历链表，找到插入位置前的结点
• 新建结点，将要插入的数据，赋值到新建结点的数据域
• 返回链表的头结点
  

LinkList DeleteList(LinkList L, int pos, int *elem)
{
	LinkList temp = L;
	int i = 0;
	temp = temp->next;指向开始结点
	LinkList del;新建结点

	for (i = 0; i < pos - 1; i++)
	{
		if ((temp == NULL) || (i > pos - 1))
		{
			printf("%s:Insert false!\n", __FUNCTION__);
			return L;
		}
		temp = temp->next;
	}

	del = temp->next; 结点指向被删除结点
	*elem = del->data; 结点数据域存储到elem中
	temp->next = del->next;要删除位置前的结点指向要删除结点后的结点
	free(del);释放内存
	del = NULL;防止野指针
	return L;

}
第二种写法

LinkList Delete(LinkList L, int pos, int *elem)
{
	LinkList temp = L;	//引入一个中间变量，用于循环变量链表
	int i = 0;
	/* 首先找到删除结点的上一结点，即第pos-1个结点 */
	while( (temp!=NULL)&&(i<pos-1) )
	{
		temp = temp->next;
		++i;
	}
	/* 错误处理：链表为空或删除位置不存在 */
	if( (temp==NULL)||(i>pos-1) )
	{
		printf("%s:Delete false!\n",__FUNCTION__);
		return temp;
	}
	LinkList del = temp->next;	//定义一个del指针指向被删除结点
	*elem = del->data;			//保存被删除的结点的数据域
	temp->next = del->next;		/*删除结点的上一个结点的指针域指向删除结点的下一个结点，
								  也可写为“temp->next = temp->next->next”*/
	free(del);					//手动释放该结点，防止内存泄露
	del = NULL;					//防止出现野指针
	return L;