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语言线性表的链式存储结构是什么这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是创新互联，小编将为大家推送更多相关知识点的文章，欢迎关注！