c语言线性表的链式存储结构是什么
这篇文章主要讲解了“c语言线性表的链式存储结构是什么”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“c语言线性表的链式存储结构是什么”吧!
10年积累的成都网站建设、网站制作经验,可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你,你也不认识我。但先网站设计后付款的网站建设流程,更有莆田免费网站建设让你可以放心的选择与我们合作。
头指针:链表中第一个节点的存储位置叫头指针。
头结点:第一个结点前放的一个不存储任何数据的结点。
头结点与头指针的区别:
1、头指针是指链表指向第一个结点的指针,若链表有头结点,则是指向头结点的指针;
2、头指针具有标识作用,所以常用头指针冠以链表的名字;
3、无论链表是否为空,头指针均不为空。头指针是链表的必要元素。
4、头结点是为了操作的统一和方便而设立的,放在第一元素的借点之前,其数据域一般无意义(也可存储链表的长度);
5、有了头结点,对在第一个元素节点点之前插入结点和删除第一个结点,其他操作与其他结点的操作统一了;
6、头结点不一定是链表的必要元素
文字描述还是很抽象,让我们来看图,这样更直观:
理清了这几个概念,接下来我们开始用c语言实现单链表的基本操作(这里会把带头结点与不带头结点分别实现并区别两者的异同):
准备工作:定义节点类型,一些声明:
#pragma once
#define ElemType int
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int Status;
typedef int DataType;
//定义结点类型
typedef struct Node
{
ElemType data;
struct Node *next;
}SeqNode;
typedef struct Node *LinkList; //定义指针类型
初始化:
//带头结点的初始化,建立一个只有头结点的空链表,头结点的数据域记录表长,并且头结点不计入长度。
//初始化成功返回OK,失败返回ERROR
Status Init_Head_SeqNode(LinkList *Head)
{
*Head = (LinkList)malloc(sizeof(SeqNode));
if((*Head) == NULL)
{
printf("out of memory\n");
return ERROR;
}
(*Head)->next = NULL;
(*Head)->data = 0;
return OK;
}
//不带头结点的初始化,建立一个只有头结点的空链表
Status Init_SeqNode(LinkList *Head)
{
*Head = NULL;
return TRUE;
}
头插:下边分别是带头结点与不带头结点的头插方式,直接上代码,可能有些抽象,我自己画了一些图,来帮助理解,希望可以也可以帮助大家理解:
带头结点的头插:
不带头结点的头插:
头插代码:
//带头结点头插,插入成功返回TRUE,失败返回ERROR
Status Insert_Head_Fr(LinkList Head,ElemType x)
{
LinkList new_node; //保存新申请的结点
new_node = (LinkList)malloc(sizeof(Node));
if(NULL == new_node)
{
printf("out of memory\n");
return FALSE;
}
new_node->data = x; //把要插入的值赋值给新申请的结点的数据域
new_node->next = Head->next; //第一步:把头结点的下一元素即就是首元结点地地址赋给新的结点
Head->next = new_node; //第二步:把新申请的结点赋值給头结点
(Head->data)++; //带头结点的头节点的数据域用来保存链表的个数,每添加一个元素加1
return TRUE;
}
//不带头结点的头插,插入成功返回TRUE,失败返回FALSE
Status Isert_No_Head_Node(LinkList *Head,ElemType x)
{
LinkList new_node; //保存新申请的结点
new_node = (LinkList)malloc(sizeof(Node));
if(NULL == new_node)
{
printf("out of memory\n");
return FALSE;
}
new_node->data = x;
new_node->next = (*Head);
//第一步:先让新申请的结点指向首元结点,因为不带头结点的链表头指针保存首元结点的地址,那么就需要这样赋值
(*Head) = new_node; //第二步:让头指针指向新申请的结点。
return TRUE;
}
尾插:同样我也给出一些我自己绘的图:
带头结点的尾插:
不带头结点的尾插:
尾插代码:
/*不带头结点的与带头结点的进行尾插的时候,有人会认为两者是没有区别的,
**我想你可能忽略了当链表中没有元素时两着的插入还是有区别的。
*/
//带头结点尾插,插入成功返回TRUE,失败返回ERROR
Status Insert_Head_Ba(LinkList Head,ElemType x)
{
LinkList new_node; //保存新申请的结点
LinkList temp = Head; //找到尾结点
new_node = (LinkList)malloc(sizeof(Node));
if(NULL == new_node )
{
printf("out of memory\n");
return FALSE;
}
//利用临时变量遍历所有链表,找到尾结点,因为temp本身是指向当前节点的next的,所以当temp等于NULL时就到了链表的最后一个结点
while(NULL != temp->next)
{
temp = temp->next;
}
new_node->data = x;
new_node->next = NULL;
temp->next = new_node;
Head->data++; //带头结点的头节点的数据域用来保存链表的个数,每添加一个元素加1
return TRUE;
}
//不带头结点尾插,插入成功返回TRUE,失败返回ERROR
Status Insert_No_Head_Ba(LinkList *Head,ElemType x)
{
LinkList new_node;
LinkList temp = (*Head); //保护头指针
new_node = (LinkList)malloc(sizeof(Node)); //为新申请的结点分配空间
if(NULL == new_node)
{
printf("out of menory\n");
return FALSE;
}
if(NULL == (*Head)) //空链表
{
new_node->next = NULL;
new_node->data = x;
(*Head) = new_node;
return TRUE;
}
else
{
//利用临时变量遍历所有链表,找到尾结点,因为temp本身是指向当前节点的next的,所以当temp等于NULL时就到了链表的最后一个结点了
while(NULL != temp->next)
{
temp = temp->next;
}
new_node->data = x;
new_node->next = NULL;
temp->next = new_node;
return TRUE;
}
}
按照位置插入:同样先看图:
带头结点的按位置插入:
不带头结点按照位置插入:
//带头结点的按照位置插入如元素,头节点不计入位置,插入时分为空链表和非空链表,由于带头结点所以所有操作是一样的
//插入成功返回TRUE,并且头结点的数据元素加1,插入失败返回FALSE。
Status Insert_Head_Pos_SeqNode(LinkList Head, ElemType x, int pos)
{
LinkList temp = Head; //保护头指针
LinkList temp_pre = Head; //保存定位的pos位置地址
LinkList new_node;
new_node = (LinkList)malloc(sizeof(Node)); //为新申请的结点分配空间
if(NULL == new_node)
{
printf("out of memory\n");
return FALSE;
}
if(pos > Head->data)
{
printf("插入位置出错,%d不能插入\n",x);
return FALSE;
}
//通过遍历找到要放数据位置的结点,但是由于单链表的当前结点只能找到下一个结点,
//而插入数据时,需要知道当前结点的位置,所以就需要定义一个变量来保存当前前结点的前一个结点
for(int i = 0; i < pos;i++)
{
temp = temp->next;
temp_pre = temp_pre->next;
}
new_node->data = x; //为新申请的节点的数据域赋值
new_node->next = temp;
//第一步:首先让新结点指向要插入的位置,也就是当前结点的前一个结点保存的位置
temp_pre->next = new_node; //第二步:让当前结点的前一个结点指向指向新结点
Head->data++; //插入成功,链表个数加1
return TRUE;
}
//不带头结点的按位置插入,分为两种情况,如果是空链表,就要修改头指针的指向,那么修改指针的指向,就要用二级指针接收
//如果不是空链表,只需要遍历链表,找到位置,这两种情况都要考虑插入位置是否正确
//插入成功返回TRUE,插入失败返回FALSE。
Status Inser_No_Head_Pos_SeqNode(LinkList *Head, int pos, ElemType x)
{
int Num = 0; //计算链表一共多少个结点
LinkList temp = (*Head); //保护头指针
LinkList temp_pre = (*Head); //保存pos 位置的地址
LinkList new_node;
new_node = (LinkList)malloc(sizeof(Node)); //为新申请的结点分配空间
if(NULL == new_node ) //防止开辟内存失败
{
printf("out of memory\n");
return FALSE;
}
//处理空链表的情况
if(NULL == (*Head) )
{
if(pos > 0)
{
printf("插入位置出错,%d不能插入\n",x);
return FALSE;
}
else
{
new_node->data = x; //为开辟的新结点赋值
new_node->next = NULL; //第一步:先让新申请的节点指向要插入 的结点的下一个结点
(*Head) = new_node; //让头指针指向新结点
return TRUE;
}
}
//处理非空链表的情况
else
{
//通过遍历找到要放数据位置的结点,但是由于单链表的当前结点只能找到下一个结点,
//而插入数据时,需要知道当前结点的位置,所以就需要定义一个变量来保存当前前结点的前一个结点
while(NULL != temp)
{
Num++;
temp = temp->next;
}
if(pos+1 > Num) //如果插入位置出错直接跳出
{
printf("插入位置出错,%d不能插入\n",x);
return FALSE;
}
else if(0 == pos)
{
new_node->data = x; //为开辟的新结点赋值
new_node->next = (*Head);
(*Head) = new_node;
}
else
{
//当遍历确定pos位置正确后,此时几个指针的指向已经发生改变,需要重新指向头指针,遍历找到需要插入的结点
temp = *Head;
for(int i = 0; i < pos - 1; i++) //定位到要删除的结点的前一个结点
{
temp = temp->next;
}
new_node->data = x; //给新结点的数据域赋值
new_node->next = temp->next;
//第一步:首先让新结点指向要插入的位置,也就是当前结点的前一个结点保存的位置
temp->next = new_node; // 第二步:让当前结点的前一个结点指向指向新结点
}
}
return TRUE;
}
头删:对与删除操作,与插入操作类比,不在画图,两者是类同的。
//不带头结点的头删,需要考虑链表是否为空链表,或者或一个元素的时候,当只有一个元素的时候,头删除就需要,修改头指针的指向,其他地方的删除,顺序都一样,用x放回删除的数据
//删除成功返回TRUE,失败返回FALSE
Status Delite_No_Head_SeqNode(LinkList *Head,ElemType *x)
{
LinkList temp_node = (*Head); //防止头指针被修改
if(NULL == temp_node)
{
printf("链表已空,已经没有元素可以删除了\n");
return FALSE;
}
if(NULL == temp_node->next)
{
*x = temp_node->data; //把要删除的结点的值保存的x中去
(*Head) = NULL;
free(temp_node); //释放删除的结点,防止内存泄露
temp_node = NULL;
return TRUE;
}
else //处理链表中有一个以上的结点的删除
{
*x = temp_node->data; //把要删除的结点的值保存的x中去
*Head = temp_node->next; //修该头指针的指向
free(temp_node); //释放删除的结点,防止内存泄露
temp_node = NULL;
return TRUE;
}
}
//带头结点的头删,不论是有一个元素还是多和元素,删除操作都不需要修该头指针指向,因而也就不需要修该头指针指向,用x放回删除的数据
//删除成功返回TRUE,失败返回FALSE;
Status Delite_Head_Fr_SeqList(LinkList Head,ElemType *x)
{
LinkList temp = Head->next; //定义临时变量防止头指针被修改
if(NULL == temp->next)
{
printf("链表已空,已经没有元素删除\n");
return FALSE;
}
*x = temp->next->data; //把要删除的结点的值保存的x中去
temp = temp->next; //第一步:让临时结点指向要删除的结点的下一个结点
free(Head->next); //第二步:释放首元结点的内存,防止内存泄露
Head->next = temp; //第三步:修改头指针的指向
return TRUE;
}
尾删:同样也不在给出示意图:对比尾插的图。
//带头结点的尾删,因为有头结点所有操作都一样
Status Delite_Head_Br_SeqNode(LinkList Head,ElemType *x)
{
//定义临时变量防止头指针被修改 ,首先让指向首元结点,尾删用它来定位最后一个结点,
//由于单链表,只知道当前节点的下一个结点的位置,那么,就需要定义一个变量保存当前结点的地址
LinkList temp = Head->next; //定位最后一个指针
LinkList temp_node_pre = Head; //保存最后一个结点的地址
if(NULL == temp)
{
printf("链表已空,已经没有元素删除\n");
return FALSE;
}
while(NULL != temp->next)
{
temp = temp->next;
temp_node_pre = temp_node_pre->next;
}
*x = temp->data; //保存最后一个结点的数据域的值
temp_node_pre->next = NULL; //修改原来结点的倒数第二个结点的指向
free(temp); //此时temp_node指向最后一个结点,防止内存泄露,释放最后一个结点的内存
temp =NULL;
return TRUE;
}
//不带头结点的尾删,由于当链表只有一个元素时,删除最后一个结点就要修改指针指向,因而就要用二级指针接收头指针,用x放回删除的数据
//删除成功返回TRUE,失败返回FALSE;
Status Delite_No_Head_Br_SeqNode(LinkList *Head,ElemType *x)
{
//定义临时变量防止头指针被修改 ,首先让指向首元结点,尾删用它来定位最后一个结点,
//由于单链表,只知道当前节点的下一个结点的位置,那么,就需要定义一个变量保存当前结点的地址
LinkList temp_node = (*Head)->next;
LinkList temp_node_pre = (*Head);
if(NULL == (*Head))
{
printf("链表已空,已无元素可以删除\n");
return FALSE;
}
while(NULL != temp_node->next)
{
temp_node = temp_node->next;
temp_node_pre = temp_node_pre->next;
}
*x = temp_node->data; //保存最后一个结点的数据域的值
temp_node_pre->next = NULL; //修改原来结点的倒数第二个结点的指向
free(temp_node); //此时temp_node指向最后一个结点,防止内存泄露,释放最后一个结点的内存
return TRUE;
}
//带头结点的按照位置删除,首先要考虑删除的位置是否存在,然后由于带头结点,所以无论是一个元素,还是多个元素删除操作都一样
Status Delite_Head_Pos_SeqNode(LinkList Head,int pos, ElemType *x)
{
//定义临时变量防止头指针被修改 ,首先让指向首元结点,尾删用它来定位最后一个结点,
//由于单链表,只知道当前节点的下一个结点的位置,那么,就需要定义一个变量保存当前结点的地址
LinkList temp = Head->next; //定位最后一个指针需要删除的结点的前一个结点
LinkList temp_node_pre = Head; //保存即将删除的结点的地址
if(NULL == temp)
{
printf("链表已空,已经没有元素删除\n");
return FALSE;
}
if(pos > temp_node_pre->data ) //判断删除的位置是否存在
{
printf("删除位置出错\n");
return FALSE;
}
for(int i = 0; i < pos-1;i++) //遍历链表找到链表要删除的结点的前一个结点
{
temp = temp->next; //定位要删除的位置
}
*x = temp->next->data; //用x返回需要删除结点的值
temp_node_pre = temp->next;
temp->next = temp->next->next; //让删除的前一个结点指向要删除的下一个结点
free(temp_node_pre); //此时temp_node指向删除的结点,防止空间泄露,释放内存
temp_node_pre = NULL;
Head->data--; //头结点保存着链表的长度,删除以后减去一个
return TRUE;
}
按照位置删除:同样也不在给出示意图:对比按照位置删除的图。
//不带头结点按照位置删除,由于当只有一个结点的删除需要修改头指针指向需要特别处理
Status Delite_No_Head_Pos_SeqNode(LinkList *Head, int pos, ElemType *x)
{
int NUM = 0; //统计一共链表一共多少个结点
//定义临时变量防止头指针被修改 ,首先让指向首元结点,尾删用它来定位最后一个结点,
//由于单链表,只知道当前节点的下一个结点的位置,那么,就需要定义一个变量保存当前结点的地址
LinkList temp = (*Head);
if(NULL == temp)
{
printf("链表已空,已无元素可以删除\n");
return FALSE;
}
else if(NULL == temp->next) //处理只有一个结点的情况
{
*x = temp->data; //用x返回需要删除结点的值
(*Head) = NULL; //头结点置空
free(temp); //释放第一个结点的空间,防止内存泄露
temp = NULL; //防止指向非法空间
return TRUE;
}
else
{
while(NULL != temp)
{
NUM++;
temp = temp->next;
}
if(pos > NUM)
{
printf("删除位置出错");
return FALSE;
}
if(0 == pos)
{
temp = *Head;
*x = temp->data;
*Head = temp->next;
free(temp);
temp = NULL;
}
else
{
//当遍历确定pos位置正确后,此时几个指针的指向已经发生改变,需要重新指向头指针,遍历找到需要插入的结点
temp = *Head;
for(int i = 0; i < pos-1; i++)
{
temp = temp->next;
}
*x = temp->next->data; //用x返回需要删除结点的值
LinkList free_node = temp->next; //free_node用与保存即将删除的结点
temp->next = temp->next->next;
free(free_node); //释放第一个结点的空间,防止内存泄露
free_node = NULL;
}
}
return TRUE;
}
打印输出所有数据:
//带头结点打印输出所有数据
Status Show_Node(LinkList Head)
{
LinkList temp = Head->next;
while(NULL != temp)
{
printf("%d ",temp->data);
temp = temp->next;
}
printf("\n");
return TRUE;
}
//不带头结点打印输出所有数据
Status Show_Node_No_Head(LinkList Head)
{
LinkList temp = Head;
while(NULL != temp)
{
printf("%d ",temp->data);
temp = temp->next;
}
printf("\n");
return TRUE;
}
清空链表:释放所有有效结点,对于带头结点链表,要把头结点的 数据域置0
//不带头结点的清空链表,释放所有的结点
Status Clean_No_Head_SeqNode(LinkList *Head )
{
LinkList temp_node = *Head;
LinkList temp_node_pre = *Head;
*Head = NULL;
while(NULL != temp_node)
{
temp_node = temp_node->next; //因为头结点不空,让临时指针指向下一个结点
free(temp_node_pre); //释放第一结点的空间
temp_node_pre = temp_node; //指向下一个空间
}
return TRUE;
}
//带头结点的清空链表,释放除头结点以外的空间
Status Clean_Head_SeqNode(LinkList Head)
{
LinkList temp_node = Head->next;
LinkList temp_node_pre = Head->next;
Head->next = NULL;
Head->data = 0;
while(NULL != temp_node->next)
{
temp_node = temp_node->next;
free(temp_node_pre);
temp_node_pre = temp_node;
}
return TRUE;
}
排序:对于排序,首先可以采用各种排序方法,然后就是排序过程中,我提一点就是只需要把值交换并不需要交换结点。这里采用冒泡排序。
//排序,由于只需要交换两个链表中的值就好了,不用修改指针指向所以带与不带头结点操作差不多,只是有细微的差别
Status Sort_No_Head_SeqNode(LinkList Head)
{
LinkList temp_node_i = Head;
LinkList temp_node_j = Head;
LinkList temp_node_pre = Head;
ElemType temp; //用与交换值
if(NULL == temp_node_i)
{
printf("链表为空,无法排序\n");
return FALSE;
}
for(temp_node_i = temp_node_i->next; NULL != temp_node_i; temp_node_i = temp_node_i->next)
{
for( temp_node_j = temp_node_j; NULL != temp_node_j; temp_node_j = temp_node_j->next)
{
if(temp_node_j->data > temp_node_pre->data)
{
temp = temp_node_j->data;
temp_node_j->data = temp_node_pre->data;
temp_node_pre->data = temp;
temp_node_pre = temp_node_pre->next;
}
temp_node_pre = temp_node_pre->next;
}
}
return TRUE;
}
//排序带头结点
Status Sort_Head_SeqNode(LinkList Head)
{
LinkList temp_node_i = Head->next;
LinkList temp_node_j = Head->next;
LinkList temp_node_pre = Head->next;
ElemType temp; //用与交换值
if(NULL == temp_node_i)
{
printf("链表为空,无法排序\n");
return FALSE;
}
for(temp_node_i = temp_node_i; NULL != temp_node_i->next; temp_node_i = temp_node_i->next)
{
for(temp_node_j = Head; NULL != temp_node_j->next; temp_node_j = temp_node_j->next)
{
if(temp_node_j->data > temp_node_j->next->data)
{
temp = temp_node_j->next->data;
temp_node_j->next->data = temp_node_j->data;
temp_node_j->data = temp;
}
}
}
return TRUE;
}
以上对单链表带头结点与不带头结点的头插、尾插、按照位置插、头删、尾删、按照位置删除、清空链表、排序、打印输出做了尽可能详尽的注释,都做了测试,但是没有给出主函数,数据结构中,这里不是重点,并且限于篇幅,因而没有给出主函数。当然以上代码只是我的理解,大家可以如果发现那块有错误,希望指正。
最后,细心的大家会发现这里边有好多重发的代码:比如生成新结点,定位要插入删除的位置,有好多重复的代码,那么就可以把它写成一个函数,简化代码,更有,这种结构的结构体,操作起来有些不方便,如果采用下边这种结构,更会简化,并且便于理解。
typedef struct node //节点类型
{
type value;
struct node *next;
}Node;
typedef struct list
{
Node *phead;
Node *ptail;
}List;
感谢各位的阅读,以上就是“c语言线性表的链式存储结构是什么”的内容了,经过本文的学习后,相信大家对c语言线性表的链式存储结构是什么这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是创新互联,小编将为大家推送更多相关知识点的文章,欢迎关注!
本文名称:c语言线性表的链式存储结构是什么
路径分享:http://myzitong.com/article/ijdidh.html