当前位置 : 主页 > 编程语言 > c语言 >

【数据结构】单链表

来源:互联网 收集:自由互联 发布时间:2023-09-07
链式存储结构 结点在存储器中的位置是任意的,即逻辑上相邻的数据元素在物理上不一定相邻。线性表的链式表示又称为非顺序影像或链式映像。用一组物理位置任意的存储单元来存放

链式存储结构

结点在存储器中的位置是任意的,即逻辑上相邻的数据元素在物理上不一定相邻。线性表的链式表示又称为非顺序影像或链式映像。 用一组物理位置任意的存储单元来存放线性表的数据元素。 这组存储单元既可以是连续的,也可以是不连续的,甚至是零散分布在内存中的任意位置上的。 链表中元素的逻辑次序和物理次序不一定相同。 image.png 在顺序表中,用存储位置的先后就能描述这些数据元素的先后,想取哪个元素,可以直接计算地址就能找到; 在链表中,是随意存储,在存储数据元素时,需要描述出这些元素的逻辑关系,在存储每一个元素的同时,我们还存储了它下一个元素在哪。 单链表是由头指针唯一确定,因此单链表可以用头指针的名字来命名。 image.png

与链式存储有关的术语

1.结点:数据元素的存储映像。由数据域和指针域两部分组成 2.链表:n个结点由指针链组成一个链表,它是线性表的链式存储映像,称为线性表的链式存储结构。 3.单链表、双链表、循环链表: 结点只有一个指针域的链表,称为单链表或线性链表。 结点有两个指针域的链表,称为双链表 首尾相接的链表称为循环链表 image.png 4.头指针、头结点和首元结点: 头指针:是指向链表中的第一个结点的指针 首元结点:是指链表中存储第一个数据元素a1的结点 头结点:是在链表的首元结点之前附设的一个结点; image.png image.png

如何表示空表

image.png

在链表中设置头结点有什么好处?

image.png

头结点的数据域内装的是什么?

image.png

链表(链式存储结构)的特点

image.png

单链表的定义和表示

带头结点的单链表 image.png 单链表的存储结构 image.png image.png 例如,存储学生学号、姓名、成绩的单链表结点类型定义如下: image.png

单链表基本操作的实现

单链表的初始化

即构造一个空表。 算法步骤: (1)生成新结点作头结点,用指针L指向头结点。 (2)将头结点的指针域置空。 算法描述

Status InitList L(LinkList &L)
{
	L=(LinkList)malloc(sizeof(LNode));
	L->next=NULL;
	return OK;
}

补充算法1————判断链表是否为空

空表:链表中无元素,称为空链表(头指针和头结点仍然在) 算法思路:判断头结点指针域是否为空

int ListEmpty(LinkList L)//若L为空表,则返回1,否则返回0
{
	if(L->next)//非空
		return 0;
	else
		return 1;
}

补充算法2————单链表的销毁

链表销毁后不存在 算法思路:从头指针开始,依次释放所有结点 一个变量想要指向某一个空间,则将空间的地址赋给它就可以了 image.png 将delete换为free就是C的语法

Status DestroyList_L(LinkList &L)
{
	LinkList p;
	while(L)
	{
		p=L;
		L=L->next;
		free p;
	}
	return OK;
}

补充算法3————清空链表

链表仍存在,但链表中无元素,成为空链表(头指针和头结点仍然在) 算法思路:依次释放所有结点,并将头结点指针域设置为空 如何获得第一个结点地址?头结点的next域,p=L->next; 怎么指向头结点?p=L; image.png 最后L->next=NULL;就可以啦!

Status ClearList(LinkList &L)
{
	LinkList p,q;//指针p用来存放当前我们要来删除的结点,指针q用来存放指针p的下一个结点
	p=L->next;//从首元结点开始
	while(p)//没到表尾
	{
		q=p->next;
		free p;
		p=q;
	}
L->next=NULL;//头结点指针域为空
return OK;
}

补充算法4————求单链表的表长

算法思路:从首元结点开始,依次计数所有结点

int ListLength_L(LinkList L)
{//返回L中数据元素个数
LinkList p;
p=L->next;//p指向第一个结点
i=0;
while(p)//遍历单链表,统计结点数
{
i++;
p=p->next;
}
return i;
}

image.png image.png

⭐重要算法————取单链表中第i个元素的内容

顺序表里是如何找到第i个元素?L->elem[i-1] image.png 算法步骤: 1.从第1个结点(L->next)顺链扫描,用指针p指向当前扫描到的结点,p初值p=L->next。 2.j做计数器,累计当前扫描过的结点数,j初值为1。 3.当p指向扫描到的下一结点时,计数器j加1。 4.当j==i时,p所指的结点就是要找的第i个结点。 算法描述:

Status GetElem_L(LinkList L,int i,ElemType &e)
{//获取线性表L中的某个数据元素的内容,通过变量e返回
	p=L->next;j=1;//初始化
	while(p&&j<i)
{//向后扫描,直到p指向第i个元素或p为空
p=p->next;
++j;
}
if(!p||j>i)//第i个元素不存在
	return ERROR;
e=p->data;//取第i个元素
return OK;
}

⭐重要算法————单链表的按值查找

分为两种情况: 按值查找1:根据指定数据获取该数据所在的位置(该数据的地址),返回变量p的值 按值查找2:根据指定数据获取该数据所在的位置序号(是第几个数据元素),返回计数器的值 image.png 算法步骤: 1.从第一个结点起,依次和e相比较。 2.如果找到一个其值与e相等的数据元素,则返回其在链表中的位置或地址。 3.如果查遍整个链表都没有找到其值和e相等的元素,则返回0或“NULL”。 算法描述:

Lnode *LocatElem_L(LinkList L,ElemType e)
{
p=L->next;
while(p&&p->data!=e)
	p=p->next;
return p;
}

算法描述:根据指定数据获取该数据位置序号

int LocateElem_L(LinkList L,ElemType e)
{
p=L->next;j=1;
while(p&&p->data!=e)
{
p=p->next;
j++;
}
if(p) return j;
else return 0;
}

⭐重要算法————插入操作

算法步骤: image.png ①和②不能换,会丢失ai的地址。 算法描述

Status ListInsert_L(LinkList &L,int i,ElemType e)
{
	p=L;j=0;
	while(p&&j<i-1)//寻找第i-1个结点,p指向i-1结点
{
	p=p->next;
	++j;
}
if(!p||j>i-1)
return ERROR;//大于表长+1或者小于1,插入位置非法
s=newLNode;
s->data=e;//生成新结点s,将结点s的数据域置为e
s->next=p->next;//将结点s插入L中
p->next=s;
return OK;
}

⭐重要算法————删除第i个结点

算法步骤: image.png 算法描述:

Status ListDelete_L(LinkList &L,int i,ElemType &e)
{
p=L;j=0;q;
while(p->next&&j<i-1)
{//寻找第i个结点,并令p指向其前驱
p=p->next;
++j;
}
if(!(p->next)||j>i-1)//删除位置不合适
return ERROR;
q=p->next;//临时保存被删结点的地址以备释放
p->next=q->next;//改变删除结点前驱结点的指针域
e=p->data;//保存删除结点的数据域
free q;//释放删除结点的空间点开始,依次将各结点插入到链表的前端
![image.png](https://s2.51cto.com/images/202304/060a22537e653fe3c1520855b3173d42896608.png?x-oss-process=image/watermark,size_14,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_30,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=)
![image.png](https://s2.51cto.com/images/202304/232ab8c7921dbcfae29608b26ede0e2de433e0.png?x-oss-process=image/watermark,size_14,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_30,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=)
算法描述:
```c
void CreateList_L(LinkList &L,int n)
{
L=newLNode;
L->next=NULL;
for(i=n;i>0;-i)
{
p=(LNode*)malloc(sizeof(LNode));
scanf(&p->data);
p->next=L->next;//插入表头
L->next=p;
}
}

单链表的建立————尾插法

尾插法————元素插入在链表的尾部,也叫后插法 image.png

//正位序输入n各元素的值,建立带表头结点的单链表L
void CreateList_L(LinkList &L,int n)
{
L->next=NULL;
r=L;//尾指针r指向头结点
for(i=0;i<n;++i)
{
p=newLNode;//生成新结点,输入元素值
p->next=NULL;
r->next=p;//插入到表尾
r=p;//r指向新的尾结点
}
}

单链表代码实现

//单链表操作 
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int ElemType;
typedef int Status;
typedef struct
{
	ElemType data;
	struct LNode* next;
}LNode,*LinkList;

Status InitList_L(LinkList L)
{//单链表的初始化 
	L = (LinkList)malloc(sizeof(LNode));
	L->next = NULL;
	return OK;
}
/*int GreateList_L(LinkList &L,int n)
{//头插法 
	LinkList newLNode;
	LinkList p;
	L=newLNode;
	L->next=NULL;
	for(i=n;i>0;i--)
	{
		p=(LNode*)malloc(sizeof(LNode));
		scanf(&p->data);
		p->next=L->next;
		L->next=p;
	}
}*/
Status CreatList(LinkList * L)
{
LinkList p,s;
*L=(LinkList)malloc(sizeof(LNode)); //创建头结点
p=*L; //创建一直指向表尾的指针
p->next=NULL; //将头节点的指针指向NULL
int x;
printf("请输入元素,输入0即停止输入\n");
scanf("%d",&x);
while(x){
    s=(LinkList)malloc(sizeof(LNode));//创建新的结点
    s->data=x; //将数据赋值给新结点的数据域
    p->next=s;
    p=s;
    scanf("%d",&x);
}
p->next=NULL;
}

Status GetElem_L(LinkList L, int i, ElemType* e)
{//取单链表中第i个元素的内容 
	LinkList p;
	p=L->next;
	int j=1;
	while (p && j < i)
	{
		p = p->next;
		++j;
	}
	if (!p || j > i)
		return ERROR;
	e = p->data;
	return p->data;
}
/*int LocateElem_L(LinkList L, ElemType e)
{//按值查找,返回p 
	LinkList p;
	p = L->next;
	while (p && p->data != e)
	{
		p = p->next;
	}
	return p;
}*/
int LocateElem_L(LinkList L,ElemType e)
{//按值查找,返回位置 
	LinkList p;
	p=L->next; 
	int j=1;
	while(p&&p->data!=e)
	{
		p=p->next;
		j++;
	}
	if(p)
	return j;
	else
	{
	printf("No Found!");
	exit(OVERFLOW);
	}
}
Status ListInsert_L(LinkList L, int i, ElemType e)
{//插入 
	LinkList p = L;
	LinkList s;
	s=(LinkList)malloc(sizeof(LNode));
	int j = 0;
	while (p && j < i - 1)//寻找i-1个结点,p指向i-1个结点 
	{
		p = p->next;
		++j;
	}
	if (!p || j > i - 1)
		return ERROR;
	s->data = e;//生成新结点s,将结点s的数据域置为e 
	s->next = p->next;//将结点s插入L中 
	p->next = s;
	return OK;
}
Status ListDelete_L(LinkList *L, int i,ElemType *e)
{//删除 
	LinkList p, q;
	p = *L;
	int j=0;
	while(p->next&&j<i-1)//寻找第i个结点,并令p指向其前驱 
	{
		p=p->next;
		++j;
	}
	if(!(p->next)||j>i-1)
	
		return ERROR;
	
	q=p->next;//临时保存被删结点前驱结点以备释放 
	p->next=q->next;//改变删除结点前驱的指针域 
	*e=q->data;//保存删除结点的数据域 
	free(q);//释放删除结点 
	return OK;
}
int ListEmpty(LinkList L)
{
	if(L->next)
		return 0;
	else
		return 1;
}
Status DestroyList_L(LinkList L)
{
	LinkList p;
	while(L)
	{
		p=L;
		L=L->next;
		free(p);
	}
	return OK;
}
Status ClearList(LinkList L)
{
	LinkList p,q;//指针p用来存放当前我们要来删除的结点,指针q用来存放p的下一个结点
	p=L->next;
	while(p)
	{
		q=p->next;
		free(p);
		p=q;
	}
	L->next=NULL;
	return OK;
}
int ListLength_L(LinkList L)
{
	LinkList p;
	p=L->next;
	int i=0;
	while(p)
	{
		i++;
		p=p->next;
	}
	return i;
}
void PrintList(LinkList  L)
{
LinkList p=L->next;
printf("链表如下:\n");
while(p!=NULL)
{
    printf("%d ",p->data);
    p=p->next;
}
printf("\n");
}

int main()
{//测试代码 
	LinkList L;
	int i;
	int j;
	int n;
	ElemType e;
	InitList_L(L);
	CreatList(&L);
	PrintList(L);
	printf("请输入要取出元素的位序:");
	scanf("%d",&i);
	e=GetElem_L(L,i,&e);
	printf("第%d个元素是%d\n",i,e);
	printf("请输入要查找的元素:");
	scanf("%d",&e);
	j=LocateElem_L(L,e); 
	printf("%d的位序为%d\n",e,j);
	printf("请输入要插入的元素及插入位置:");
	scanf("%d %d",&e,&i);
	ListInsert_L(L,i,e);
	PrintList(L);
	printf("请输入要删除元素的位置:");
	scanf("%d",&i);
	ListDelete_L(&L,i,&e);
	printf("删除后的链表为:\n");
	PrintList(L);
	return 0;
}

单链表的优缺点

image.png

【本文来自:美国大带宽服务器 http://www.558idc.com/mg.html提供,感恩】
网友评论