C语言线性表链式表示
世纪末的架构师 人气:0前言
线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，而线性表的链式存储特点则是用一组任意的存储单元存储线性表的数据元素。这组存储单元既可以是连续的，也可以是不连续的。
对于链式存储的每个数据元素而言，除了存储其本身的信息之外，还需要存储一个指示其直接后继的信息，即直接后继的存储位置。这两部分信息组成了数据元素的存储映像，称为结点。
链式存储的结构包含两个域：一个用于存储数据元素的信息，另一个用于存储直接后继的存储位置；存储数据元素信息的域称为数据域，存储直接后继存储位置的域称为指针域。
图示：
数据结构中，在单链表的开始结点之前一般要附设一个类型相同的结点，称之为头结点。头结点的数据域可以不存储任何信息，头结点的指针域存储指向开始结点的指针，即第一个元素结点的存储位置。
附设头结点的作用：
- 防止单链表是空的而设的。当链表为空的时候，带头结点的头指针就指向头结点，如果当链表为空的时候，单链表没有带头结点，那么它的头指针就为NULL
- 方便单链表的特殊操作，插入在表头或者删除第一个结点，加入头结点的话就可以保持单链表操作的统一性
- 当单链表加上头结点之后，无论单链表是否为空，头指针始终指向头结点，因此空表和非空表的处理也就统一了，方便了单链表的操作，也减少了程序的复杂性和出现bug的机会
链式表示要实现的功能：
实现工具：Dev C++
- 构造一个空的头结点
- 对线性表进行赋值
- 对线性表进行销毁
- 对线性表进行重置
- 判断线性表是否为空
- 获取线性表的长度
- 获取线性表某一位置对应的元素
- 在线性表某一位置插入元素
- 删除线性表某一位置的元素
- 求线性表某一元素的前驱
- 求线性表某一元素的后继
- 打印线性表
- 退出
准备工作：
打开Dev C++后新建一个Source File文件即可 File>new>Source File
代码实现
在实现线性表的链式存储时导入的头文件有
#include<stdio.h> #include<stdlib.h> #include<malloc.h> #include<windows.h>
在这里我调用windows头文件是为了在后面的代码中修改控制台的名称，在实现线性表的链式存储时真正用到的只有前三个头文件
在写各种函数之前先对一些表示结果状态的字符进行预定义
//函数结果状态代码 #define TRUE 1 //代码中出现TRUE相当于出现了1 #define FALSE 0 //出现FALSE相当于出现了0 #define OK 1 //出现OK相当于出现了1 #define ERROR 0 //出现ERROR相当于出现了0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; //定义函数的返回状态 typedef int ElemType;
在这里使用了typedef定义了Status和ElemType为int类型，也就是说之后的代码当中如果出现了Status和ElemType，它们与int作用相同
1. 单链表的结点构造
typedef struct LNode{
ElemType data; //数据域
struct LNode * next; //指针域,指向一整个结点(结构体,该结构体中包含数据域和指针域)
}LNode , * LinkList;
代码中的* LinkList指的是结点的类型，在之后的代码中出现了它就相当于出现了指向这个结点的指针
2. 构造一个空的头结点
//构造一个空的头结点
Status InitList_L(LinkList &L){
L = (LinkList)malloc(sizeof(LNode)); //产生头结点，并使L指向该头结点(L也称头指针)
if(!L) return ERROR; //如果存储空间分配失败，返回ERROR
L->next = NULL; //将指针域赋值为NULL
printf("空的头结点创建成功\n");
return OK;
}
在该函数传参时一定要在L之前加"&"符号，表示引用传递，保证形参和实参同时改变。之前在写代码时因为没有输入"&"符号，没有使用引用传递也就意味着没有开辟了新的内存空间，所以在之后赋值的时候会出现无法赋值的情况 在这里要强调一点："->"是一个指针类型的运算符，它是用于指向结构体子数据的指针
3. 对线性表进行赋值
//对线性表进行赋值
Status ValueList_L(LinkList &L,ElemType e){
LinkList s,p;
p = L;
while(p->next){
p = p->next;
}
s = (LinkList)malloc(sizeof(LNode)); //生成一个新结点
s->data = e; //将e赋值给新结点的数据域
s->next = p->next; //将新结点与后一个结点的地址连接
p->next = s;
return OK;
}
因为要实现构造一个单链表，所以在main函数中会循环调用ValueList_L方法，所以通过以下的循环是用来使p指向要赋值的位置
while(p->next){
p = p->next; }
之后利用malloc()函数开辟新的结点来存放数据和下一个结点的位置即可，因为malloc()函数开辟空间之后返回的不是LinkList结点类型，所以在利用malloc()函数开辟新的结点时要将其通过强制类型转换使其转换成LinkList类型
4.对线性表进行销毁
//对线性表进行销毁
Status DistoryList_L(LinkList &L) {
if(!L){ //如果线性表不存在，返回ERROR
printf("线性表不存在\n");
return ERROR;
}
LinkList q = L->next; //使q指向单链表的首元结点
while(q != NULL){ //当q结点不为空时一直进入循环
free(L); //释放L结点
L = q; //将q结点赋值给L结点
q = L->next; //将q结点赋值给L结点以后使q结点指向L的下一个结点
}
free(L); //此时q的值为NULL，L指向尾结点，将其释放
L = NULL;
printf("线性表已销毁\n");
}
在对单链表进行销毁操作时，从头结点开始逐一释放，释放前使q指向开始释放的结点，当开始结点不为空时，执行释放过程，先释放头结点，然后将L，q都向后移，依次释放，因为q始终是L的后继，所以最后一定是L留到最后，最后释放L结点
L = NULL;
为什么在feel(L);之后还要将L赋值为空？
因为free函数只是将之前动态分配给L的内存归还给系统，但是指针类型的结点L仍然存在，为了防止之后发生野指针访问，将L赋值为NULL
5.对线性表进行重置
//对线性表进行重置
Status ClearList_L(LinkList &L)
{
if(!L->next){
printf("线性表为空表，不需要重置\n");
return ERROR;
}
LinkList p,q;
p = L->next; //将单链表的头结点赋值给p
while(p){
q = p->next; //将单链表的首元结点赋值给q
free(p);
p = q;
}
L->next = NULL; //将头结点的指针域赋值为空
printf("线性表已重置\n");
return OK;
}
在对线性表进行重置前首先要判断线性表是为空表，当其不为空时构造两个LinkList类型的结点p和q，使p指向L的首元结点，当p不为空即单链表不为空时进入while循环，将p的下一个结点复制给q，将p释放后再将q赋值给p。p为空时说明此时单链表只剩下了头结点，将头结点的指针域设置为NULL，完成单链表的重置（因为LinkList为指针类型的数据，所以赋值的内容都是地址）
图示：
6.判断线性表是否为空
//判断线性表是否为空
Status ListEmpty_L(LinkList L)
{
if(L){
if(L->next == NULL) //如果首元结点不存在
printf("线性表是空表\n");
else
printf("线性表不是空表\n");
}
else{
printf("线性表不存在，无法判断\n");
}
return OK;
}
在判断线性表是否为空时，首先判断头结点是否存在，当头结点存在时看头结点的指针域是否为空，当指针域为空时说明首元结点不存在，单链表是空表；当指针域不为空时说明存在首元结点，单链表不是空表。如果头结点不存在的话说明单链表不存在，无法判断是否为空表。
7.获取线性表的长度
//获取线性表的长度
Status ListLength_L(LinkList L,int count)
{
//L为带头结点的单链表的头指针，count为计数器
LinkList p = L->next; //定义p为单链表L的指针域
while(p){
p = p->next;
count++;
}
return count;
}
获取线性表长度的核心思路是遍历单链表，定义LinkList类型的变量p，将单链表的首元结点赋值给p。在该函数中count为计数器，形参count传来的值始终为1，count的值为1代表从首元结点开始计数，所以才将L->next赋值给p，目的是为了让count与存储数据元素的结点位置对应一致。（在单链表中有头结点的存在，所以这种方法计算出的长度最后的值要比线性表的实际长度大1）进入循环后每当p不断向后移动，每当p后移一次，计数器count的值就加1，直到p为空，此时count的位置就对应着最后一个存储着数据元素的结点位置。
8.获取线性表某一位置对应的元素
//获取线性表某一位置对应的元素
Status GetElem_L(LinkList L,int index)
{
LinkList p;
p = L->next; //使p指向L的首元结点
int count = 1; //count为计数器 ，赋值等于1的原因是从首元结点开始计数
while(p && count < index){ //顺着指针向后查找，直到p指向第index个元素或p为空
p = p->next;
count++; //此时p一直指向第count个元素
}
if(!p || count > index){
printf("当前位置没有元素\n");
return ERROR;
}
printf("第%d个元素的值是：%d\n",index,p->data);
return OK;
}
与获取单链表的长度思路一样，获取单链表某一位置的元素也需要遍历单链表，只不过什么时候停止遍历由自己决定，可能不需要全部遍历。定义LinkList类型的变量p并且将首元结点的地址赋值给p。定义计数器count的初始值为1之后，进入while循环，循环判断有两个：
- p 因为p一直指向第count个结点，所以此循环判断条件的意思是当第count个结点存在时才能进入循环
- count < index 当count还不是我们想要获取的结点位置时继续循环
退出循环以后p指向的位置就是我们想要获取的结点位置，这个时候要先进行越界判断，!p的意思是如果在之前的循环中index的值大于单链表的长度，那么退出循环的原因就是p为NULL，那么!p就为true，满足if语句中的条件，返回ERROR，所以 !p的作用就是限制index不大于单链表的长度。 count > index的目的是为了限制index的值小于1
9.在线性表某一位置插入元素
//在线性表某一位置插入元素
Status ListInsert_L(LinkList &L,int index,ElemType e)
{
LinkList p,q;
p = L; //将线性表的头结点赋值给p
int count = 0; //count为计数器
while(p && count < index - 1){ //寻找第index-1个结点
p = p->next; //此时的p结点指向第index-1个结点
count++;
}
if(!p || count > index -1){ //越界判断,index小于1或是index大于表长加1
printf("当前结点无法插入元素\n");
return ERROR;
}
q = (LinkList)malloc(sizeof(LNode));
q->data = e; //将e赋值到q的数据域当中
q->next = p->next;
p->next = q;
printf("元素插入成功\n");
return OK;
}
与寻找某个位置结点的值思路一致，需要先找到要插入结点的位置。但是这里不同的地方在于要插入结点的话，可以在单链表的表尾插入元素，也可以在头结点和首元结点间插入元素，所以计数器count的初值为0（为了保证从头结点开始遍历，count的值与实际的结点位置相匹配），所以判断条件变为index - 1。在结束循环和越界判断结束后p之后的位置就是要插入结点的位置，先构造出一个空结点并赋值给q，将p的下一个结点位置赋值给q的指针域，再将p的下一个结点位置赋值给q完成插入操作。
图示：
10.删除线性表某一位置的元素
//删除线性表某一位置的元素
Status DeleteList_L(LinkList &L,int index)
{
LinkList p,q;
p = L; //将线性表的头结点赋值给p
int count = 0; //计数器
while(p->next && count < index - 1){
p = p->next;
count++; //此时p一直指向第count个结点
}
if(!(p->next) || count > index - 1){ //越界判断
printf("当前位置无法删除元素\n");
return ERROR;
}
q = p->next;
p->next = q->next;
free(q);
q = NULL;
printf("当前位置元素已删除\n");
return OK;
}
删除某一结点的思路仍然是从头结点开始遍历，找到要删除的结点的位置的前一个结点，此时p就是要删除结点位置的前一个结点。将p的后一个结点赋值给q，此时q就是要删除的结点，将q的下一个结点与p的下一个结点连接，释放q结点，完成删除操作。
11.求线性表某一元素的前驱
//求线性表某一元素的前驱
Status PriorElem_L(LinkList L,int index)
{
LinkList p;
int count = 0; //count为计数器
p = L;
while(p->next && count < index - 1){ //寻找第index-1个结点
p = p->next; //p一直指向第count个结点
count++;
}
if(!(p->next) || count > index - 1){ //越界判断
printf("当前位置无法求该元素的前驱\n");
return ERROR;
}
if(p != L) //如果要获取第一个元素的前驱，就是获取头结点数据域的值
printf("该元素的前驱为：%d\n",p->data);
else
printf("该位置的前驱是头结点\n头结点的数据域中存储的值为：%d\n",p->data);
return OK;
}
和删除结点的思路完全一致，只不过求前驱时不需要进行删除结点，在循环中控制循环条件使p在index - 1位置结束循环，此时p指向的就是第index的前驱，直接将p结点的数据域输出即可
12.求线性表某一元素的后继
//求线性表某一元素的后继
Status NextElem_L(LinkList L,int index)
{
LinkList p;
int count = 0;
p = L->next;
while(p && count < index){ //不断遍历寻找第index之后的结点
p = p->next; //p一直指向index-1的后一个结点
count++;
}
//!p的目的是为了确保i不大于表长-1，count>index的目的是为了确保index不小于0
if(!p || count > index){ //越界判断
printf("当前位置无法求该元素的后继\n");
return ERROR;
}
printf("该元素的后继为：%d\n",p->data);
}
在声明LinkList类型变量p时将L的首元结点赋值给p，在循环中p一直指向第index的下一个结点，所以直接将p结点的数据域输出即可
13.打印线性表
//打印线性表
Status PrintList_L(LinkList L)
{
if(!L){ //如果线性表不存在，返回ERROR
printf("线性表不存在，无法打印\n");
return ERROR;
}
LinkList p;
p = L->next; //将L的首元结点赋值给p ,为了不将头结点打印出来
while(p){
printf(" %d",p->data); //将p结点的数据域输出
p = p->next; //结点不断的向后移动
}
printf("\n");
return OK;
}
打印单链表的思路也是进行对单链表的遍历，在遍历的过程中将每个结点的数据域中存储的值输出
运行结果演示
为了方便演示，在这里为单链表一次赋值为1，2，3，4，5
构造一个空的头结点
赋值操作
判断此时线性表是否为空
获取单链表的长度
获取2号位置的元素
在3号位置插入520并打印单链表
获取此时单链表的长度
删除3号位置的元素并打印单链表
求3号位置元素的前驱和后继
重置单链表并获取长度以及判断是否为空表
销毁单链表并进行赋值和判断是否为空
以上便是线性表链式表示和实现，由于链表在空间的合理利用上和插入、删除是不需要移动等的优点，因此在很多场合下它
是线性表的首选存储结构。然而，它也存在着实现某些基本操作的缺点，比如：求线性表长度时不如顺序存储结构......
源码
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<windows.h>
//函数结果状态代码
#define TRUE 1 //代码中出现TRUE相当于出现了1
#define FALSE 0 //出现FALSE相当于出现了0
#define OK 1 //出现OK相当于出现了1
#define ERROR 0 //出现ERROR相当于出现了0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status; //定义函数的返回状态
typedef int ElemType;
typedef struct LNode{
ElemType data; //数据域
struct LNode * next; //指针域,指向一整个结点(结构体,该结构体中包含数据域和指针域)
}LNode , * LinkList; //* LinkList是结点的类型，在之后的代码中出现了它就相当于出现了指向这个结点的指针
//构造一个空的头结点
Status InitList_L(LinkList &L){ //之前因为没有输入"&"符号,没有使用引用传递也就意味着没有开辟了新的内存空间，所以在之后赋值的时候会出现无法赋值的情况
L = (LinkList)malloc(sizeof(LNode)); //产生头结点，并使L指向该头结点(L也称头指针)
if(!L) return ERROR; //如果存储空间分配失败，返回ERROR
L->next = NULL; //将指针域赋值为NULL,在这里要强调一点："->"是一个整体，它是用于指向结构体子数据的指针
printf("空的头结点创建成功\n");
return OK;
}
//对线性表进行赋值
Status ValueList_L(LinkList &L,ElemType e){
LinkList s,p;
p = L;
while(p->next){
p = p->next;
}
s = (LinkList)malloc(sizeof(LNode)); //生成一个新结点
s->data = e; //将e赋值给新结点的数据域
s->next = p->next; //将新结点与后一个结点的地址连接
p->next = s;
return OK;
}
//对线性表进行销毁
Status DistoryList_L(LinkList &L) {
/*从头结点开始逐一释放，释放前使p指向头结点，q指向开始释放的结点
当开始结点不为空时，执行释放过程
先释放头结点，然后将p，q都向后移，依次释放
因为q始终是p的后继，所以最后一定是p留到最后，最后释放p
*/
if(!L){ //如果线性表不存在，返回ERROR
printf("线性表不存在\n");
return ERROR;
}
LinkList q = L->next; //使q指向单链表的首元结点
while(q != NULL){ //当q结点不为空时一直进入循环
free(L); //释放L结点
L = q; //将q结点赋值给L结点
q = L->next; //将q结点赋值给L结点以后使q结点指向L的下一个结点
}
free(L); //此时q的值为NULL，L指向尾结点，将其释放
L = NULL; //free函数只是将之前动态分配给L的内存归还给系统，但是指针类型的结点L仍然存在
//为了防止之后发生野指针访问，将L赋值为NULL
printf("线性表已销毁\n");
}
//对线性表进行重置
Status ClearList_L(LinkList &L)
{
if(!L->next){
printf("线性表为空表，不需要重置\n");
return ERROR;
}
LinkList p,q;
p = L->next; //将单链表的头结点赋值给p
while(p){
q = p->next; //将单链表的首元结点赋值给q
free(p);
p = q;
}
L->next = NULL; //将头结点的指针域赋值为空
printf("线性表已重置\n");
return OK;
}
//判断线性表是否为空
Status ListEmpty_L(LinkList L)
{
if(L){
if(L->next == NULL) //如果首元结点不存在
printf("线性表是空表\n");
else
printf("线性表不是空表\n");
}
else{
printf("线性表不存在，无法判断\n");
}
return OK;
}
//获取线性表的长度
Status ListLength_L(LinkList L,int count)
{
//L为带头结点的单链表的头指针，count为计数器
LinkList p = L->next; //定义p为单链表L的指针域
while(p){
p = p->next;
count++;
}
return count;
}
//获取线性表某一位置对应的元素
Status GetElem_L(LinkList L,int index)
{
LinkList p;
p = L->next; //使p指向L的首元结点
int count = 1; //count为计数器 ，赋值等于1的原因是从首元结点开始计数
while(p && count < index){ //顺着指针向后查找，直到p指向第index个元素或p为空
p = p->next;
count++; //此时p一直指向第count个元素
}
if(!p || count > index){
printf("当前位置没有元素\n");
return ERROR;
}
printf("第%d个元素的值是：%d\n",index,p->data);
return OK;
}
//在线性表某一位置插入元素
Status ListInsert_L(LinkList &L,int index,ElemType e)
{
LinkList p,q;
p = L; //将线性表的头结点赋值给p
int count = 0; //count为计数器
while(p && count < index - 1){ //寻找第index-1个结点
p = p->next; //此时的p结点指向第index-1个结点
count++;
}
if(!p || count > index -1){ //越界判断,index小于1或是index大于表长加1
printf("当前结点无法插入元素\n");
return ERROR;
}
q = (LinkList)malloc(sizeof(LNode));
q->data = e; //将e赋值到q的数据域当中
q->next = p->next;
p->next = q;
printf("元素插入成功\n");
return OK;
}
//删除线性表某一位置的元素
Status DeleteList_L(LinkList &L,int index)
{
LinkList p,q;
p = L; //将线性表的头结点赋值给p
int count = 0; //计数器
while(p->next && count < index - 1){
p = p->next;
count++; //此时p一直指向第count个结点
}
if(!(p->next) || count > index - 1){ //越界判断
printf("当前位置无法删除元素\n");
return ERROR;
}
q = p->next;
p->next = q->next;
free(q);
q = NULL;
printf("当前位置元素已删除\n");
return OK;
}
//求线性表某一元素的前驱
Status PriorElem_L(LinkList L,int index)
{
LinkList p;
int count = 0; //count为计数器
p = L;
while(p->next && count < index - 1){ //寻找第index-1个结点
p = p->next; //p一直指向第count个结点
count++;
}
if(!(p->next) || count > index - 1){ //越界判断
printf("当前位置无法求该元素的前驱\n");
return ERROR;
}
if(p != L) //如果要获取第一个元素的前驱，就是获取头结点数据域的值
printf("该元素的前驱为：%d\n",p->data);
else
printf("该位置的前驱是头结点\n头结点的数据域中存储的值为：%d\n",p->data);
return OK;
}
//求线性表某一元素的后继
Status NextElem_L(LinkList L,int index)
{
LinkList p;
int count = 0;
p = L->next;
while(p && count < index){ //不断遍历寻找第index之后的结点
p = p->next; //p一直指向index-1的后一个结点
count++;
}
//!p的目的是为了确保i不大于表长-1，count>index的目的是为了确保index不小于0
if(!p || count > index){ //越界判断
printf("当前位置无法求该元素的后继\n");
return ERROR;
}
printf("该元素的后继为：%d\n",p->data);
}
//打印线性表
Status PrintList_L(LinkList L)
{
if(!L){ //如果线性表不存在，返回ERROR
printf("线性表不存在，无法打印\n");
return ERROR;
}
LinkList p;
p = L->next; //将L的首元结点赋值给p ,为了不将头结点打印出来
while(p){
printf(" %d",p->data); //将p结点的数据域输出
p = p->next; //结点不断的向后移动
}
printf("\n");
return OK;
}
int main(){
SetConsoleTitle("Dream_飞翔"); //控制windows终端控制台的名称
//system("mode con cols=60 lines=30"); 这条语句可以控制windows终端控制台的大小
LinkList L = NULL; //声明线性表的头结点，但是并未进行初始化
int choose,index,e,Num,Value,k;
while(1){
printf("*****************************************\n");
printf("* *\n");
printf("* 线性表的链式表示和实现： *\n");
printf("* *\n");
printf("* 1. 构造一个空的头结点 *\n");
printf("* 2. 对线性表进行赋值 *\n");
printf("* 3. 对线性表进行销毁 *\n");
printf("* 4. 对线性表进行重置 *\n");
printf("* 5. 判断线性表是否为空 *\n");
printf("* 6. 获取线性表的长度 *\n");
printf("* 7. 获取线性表某一位置对应的元素 *\n");
printf("* 8. 在线性表某一位置插入元素 *\n");
printf("* 9. 删除线性表某一位置的元素 *\n");
printf("* 10. 求线性表某一元素的前驱 *\n");
printf("* 11. 求线性表某一元素的后继 *\n");
printf("* 12. 打印线性表 *\n");
printf("* 13. 退出 *\n");
printf("* *\n");
printf("*****************************************\n");
printf("请做出您的选择：");
scanf("%d",&choose);
switch(choose){
case 1:InitList_L(L);break;
case 2:{
if(L){ //对线性表赋值的前提是线性表的头结点存在
printf("请输入线性表元素的个数：");
scanf("%d",&Num);
if(Num > 0){
for(int i = 1;i <= Num;i++){
printf("请输入第%d个元素的值：",i);
scanf("%d",&Value);
ValueList_L(L,Value);
}
printf("线性表赋值成功\n");
}
else
printf("请输入一个有效数字\n");
}
else
printf("线性表不存在，无法赋值\n");
}
break;
case 3:DistoryList_L(L);break;
case 4:ClearList_L(L);break;
case 5:ListEmpty_L(L);break;
case 6:{
int count = ListLength_L(L,1);
printf("线性表的长度为：%d\n",count-1);
};break;
case 7:{
printf("请输入要获取元素的位置：");
scanf("%d",&index);
GetElem_L(L,index);
}
break;
case 8:{
printf("请输入插入元素的位置：");
scanf("%d",&index);
printf("请输入插入元素的值：");
scanf("%d",&e);
ListInsert_L(L,index,e);
}
break;
case 9:{
printf("请输入要删除元素的位置：");
scanf("%d",&index);
DeleteList_L(L,index);
}
break;
case 10:{
if(L){
printf("请输入想要查找哪一个元素的前驱：");
scanf("%d",&index);
PriorElem_L(L,index);
}
else
printf("线性表不存在，无法获取其中元素的前驱\n");
}
break;
case 11:{
if(L){
printf("请输入想要查找哪一个元素的后继：");
scanf("%d",&index);
NextElem_L(L,index);
}
else
printf("线性表不存在，无法获取其中元素的后继\n");
}
break;
case 12:PrintList_L(L);break;
case 13:exit(0);
}
}
return 0;
}加载全部内容