1. 首页
  2. 文章中心
  3. 数据结构

数据结构——链表单链表定义单链表的实现双链表循环链表循环双链表静态链表

110 阅读 0 评论
我是靠谱客的博主 烂漫人生，这篇文章主要介绍数据结构——链表单链表定义单链表的实现双链表循环链表循环双链表静态链表，现在分享给大家，希望可以做个参考。

单链表定义

通过一组任意的存储单元来存储线性表中的数据元素，为了建立数据元素之间的线性关系，对于每个链表的结点，除了存放数据以外，还要存放一个指向后继元素的指针

结构体模型

复制代码
1
2
3
4
5
typedef struct LNode{
	ElemType data;
	struct LNode *next;
	}LNode,*LinkList;

单链表解决了顺序表需要大量连续存储单元的缺点，但是单链表附加指针域，也存在浪费空间的缺点。
为了操作方便通常会在第一个节点之前添加一个节点，称为头节点，头节点的数据域可以不设置任何信息，也可以记录表长等信息。
引入头节点的两个优点：
1.由于第一个数据节点的位置被存放在头结点的指针域中，所以第一个元素和表的其他元素操作一致。
2。无论链表是否为空，其头指针都指向头结点的非空指针，因此空表和非空表的处理就得到了统一。

单链表的实现

单链表的建立

头插法

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
LinkList List_HeadInsert(LinkList &L){
	LNode *s; int x;
	L=(LinkList)malloc(sizeof(LNode));
	L->next=NULL;
	scanf("%d",&x);
	while(x!=9999){
		s=(LNode*)malloc(sizeof(LNode));
		s->data=x
		s->next=L->next;
		L->next=s;
		scanf("%d",&x);
	}
	return L;
}

尾插法

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
LinkList List_TailInsert(LinkList &L){
	int x;
	L=(LinkList)malloc(sizeof(LNode));
	LNode *s,*r=L;
	scanf("%d",&x);
	while(x!=9999){
		s=(LNode*)malloc(sizeof(LNode));
		s->data=x
		r->next=s;
		r=s;
		scanf("%d",&x);
	}
	r->next=NULL;
	return L;
}

单链表的基本操作

按序号查找结点

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
LNode *GetElem(LinkList L,int i){
	int j=1;
	LNode *p=L->next;
	if(i==0)
		return L;
	if(i<1)
		return NULL;
	while(p&&j<i){
		p=p->next
		j++;
	}
	return p;
}

按值查找结点

复制代码
1
2
3
4
5
6
7
LNode *LocateElem(LinkList L,ElemType e){
	LNode *p=L->next
	while(p!=NULL&&p->data!=e)
		p=p->next;
	return p;
}

插入

复制代码
1
2
3
4
5
6
7
8
LNode *insert(LinkList &L,int i，ElemType e){
	LNode *p=GetElem(L,i-1);
	LNode *s;
	s->date=e;
	s->next =p->next;
	p->next=s;
}

对于已知结点进行前插法

复制代码
1
2
3
4
5
6
7
8
9
10
LNode *insert2(LinkList &L,LNode *p){
	LNode *s;
	ElmeType temp;
	s->next=p->next;
	p->next=s;
	temp=p->data;
	p->data=s->data;
	s->data=temp;
}

双链表

为了克服单链表不能访问前驱结点的缺点，引入了双链表，双链表中有prior next两个指针，分别指向前驱结点和后继结点
结构体描述

复制代码
1
2
3
4
5
typedef struct DNode{
	ElemType data;
	struct DNode *prior,*next;
	}DNode,*DinkList;

循环链表

循环链表和单链表的区别在于，表中的最后一个结点的指针不是NULL，而是改为了头结点，整个链表形成一个环

循环双链表

循环的双链表

静态链表

静态链表借助数组来描述线性表，通过数组下标记录链表位置，每个结点的next指针指向数组下标
结构体描述

复制代码
1
2
3
4
5
typedef struct{
	ElemType data;
	int next;
}SLinkList [MxaSize];

最后

以上就是烂漫人生最近收集整理的关于数据结构——链表单链表定义单链表的实现双链表循环链表循环双链表静态链表的全部内容，更多相关数据结构——链表单链表定义单链表内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(73)

相关文章

环形数组逆向遍历
环形数组逆向遍历
ui环形循环可拖拽
ui环形循环可拖拽
队列：环形数组队列一个基本的环形数组队列的实现
队列：环形数组队列一个基本的环形数组队列的实现
Day02数组队列和环形数组队列
Day02数组队列和环形数组队列
数据结构——链表单链表定义单链表的实现双链表循环链表循环双链表静态链表
数据结构——链表单链表定义单链表的实现双链表循环链表循环双链表静态链表
循环队列数组模拟环形队列代码实现
循环队列数组模拟环形队列代码实现
错题整理（422）
错题整理（422）
数组中元素与字节的关系
数组中元素与字节的关系

评论列表共有 0 条评论

立即
投稿
返回
顶部