数据结构——链表（定义详解及建立单链表与实现其操作）

本文主要是介绍数据结构——链表（定义详解及建立单链表与实现其操作），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链表定义：链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

本文仅讲解单链表，其他链表构造基本类似单链表。
单链表有带头节点链表和不带头节点链表，头节点就是链表中第一个节点前的一般不存储数据元素的节点。因为带头节点可使删除和插入等操作不需要区分是否为空链表，更加便捷，所以本文讲解的是带有头节点的单链表。
单链表示意图如下（带头节点）：
在这里插入图片描述
相比顺序表，链表的优点：
1.存储数据基本无上限，且不用提前固定存储空间，节省大量空间。
2.插入删除等操作不用移动大量其他元素，更加快速。
缺点：
1.结构更为复杂，需较多指针操作，容易出错。
2.查找较为繁琐，需从头结点向后依次查找。

代码实现（C语言）

1.定义线性表的链式储存结构

typedef int cont;       //这里将cont定义为int类型，为什么要多此一步，因为如果将int类型改为floct类型，只需要将这里的int换为float即可，省去很多修改步骤
typedef struct node{cont data;struct node *next;
}LinkNode;             //定义一个LinkNode结构体，内含有cont，类型的数据data，和指向下一个数据的指针域，此时LinkNode就是定义一个链表接节点。

2.空链表的建立

LinkNode *SetList()
{// 创建头节点 LinkNode *H = (LinkNode *)malloc(sizeof(LinkNode));if(H == NULL)return NULL;H->data = NULL;H->next = NULL;return H; 
}

3.链表数据的查找

LinkNode *FindList(LinkNode *H,int i)     //H为头指针，i为数据的位置
{LinkNode *P=H;int j=0;if(i==0)return P;else{while(P->next!=NULL&&j<i){P=P->next;j++;}if(j==i){return P;}else return NULL;}
}

3.数据的插入（采用尾部插入，因为尾部插入后数据存储顺序与数据输入顺序一致）

int InsertList(LinkNode *H,int i,cont x)   //H为头指针，i为数据的位置，x为插入的数据
{LinkNode *P,*S;P=FindList(H,i-1);if(P==NULL){printf("插入位置错误\n");return 0;}else{S = (LinkNode *)malloc(sizeof(LinkNode));S->data=x;S->next=P->next;P->next=S;return 1;}
}

4.链表数据的遍历打印

void PrintList(LinkNode *H)     //遍历打印
{if (H->next==NULL)return;LinkNode *p = H->next;while (p){printf("%-3d",p->data);p = p->next;}printf("\n");
}

5.链表某数据的删除


int DelList(LinkNode *H,int i)  //H为头指针，i为数据的位置
{LinkNode *P;P=FindList(H,i-1);if(P==NULL){printf("删除位置错误\n");return 0;}else{P->next=P->next->next; }
}

6.链表某数据的修改

int AmendList(LinkNode *H,int i,cont x)   //H为头指针，i为数据的位置，x为修改后的数据
{LinkNode *P;P=FindList(H,i-1);if(P==NULL){printf("修改位置错误\n");return 0;}else{P->next->data=x;}}

7.判断链表是否为空

int EmptyList(LinkNode *H)
{if(H==NULL||H->next==NULL)return 0;elsereturn 1;
}

以上就是链表创建及实现其操作的c语言各模块函数代码，完整的代码及试验其功能操作如下：

完整代码

#include<stdio.h>
#include<stdlib.h>typedef int cont;
typedef struct node{cont data;struct node *next;
}LinkNode;LinkNode *SetList()
{// 创建头节点 LinkNode *H = (LinkNode *)malloc(sizeof(LinkNode));if(H == NULL)return NULL;H->data = NULL;H->next = NULL;return H; 
}LinkNode *FindList(LinkNode *H,int i)
{LinkNode *P=H;int j=0;if(i==0)return P;else{while(P->next!=NULL&&j<i){P=P->next;j++;}if(j==i){return P;}else return NULL;}
}int InsertList(LinkNode *H,int i,cont x)
{LinkNode *P,*S;P=FindList(H,i-1);if(P==NULL){printf("插入位置错误\n");return 0;}else{S = (LinkNode *)malloc(sizeof(LinkNode));S->data=x;S->next=P->next;P->next=S;return 1;}
}void PrintList(LinkNode *H)//遍历打印
{if (H->next==NULL)return;LinkNode *p = H->next;while (p){printf("%-3d",p->data);p = p->next;}printf("\n");
}int DelList(LinkNode *H,int i)
{LinkNode *P;P=FindList(H,i-1);if(P==NULL){printf("删除位置错误\n");return 0;}else{P->next=P->next->next; }
}int AmendList(LinkNode *H,int i,cont x)
{LinkNode *P;P=FindList(H,i-1);if(P==NULL){printf("修改位置错误\n");return 0;}else{P->next->data=x;}}int EmptyList(LinkNode *H)
{if(H==NULL||H->next==NULL)return 0;elsereturn 1;
}int main()
{LinkNode *H;H = SetList();InsertList(H,1,15);InsertList(H,2,9);InsertList(H,3,27);InsertList(H,1,7);PrintList(H);InsertList(H,8,4);DelList(H,2);DelList(H,7);PrintList(H);AmendList(H,2,81);AmendList(H,9,24);PrintList(H);
}

运行结果：
在这里插入图片描述
这里为了使各功能是否能正常实现清晰地呈现，最后的试验部分代码重复繁琐，各位看这部分只需要明白它们是如何实现即可。