shaoyuanhangyes

shaoyuanhangyes@outlook.com

线性表·4

发表于 更新于 分类于

数据结构复习·4 线性表：循环单链表/循环双链表

循环单链表

单链表的最后一个结点的指针指向NULL r->next=NULL
循环单链表的最后一个结点的指针指向头结点 r->next=L
从而整个链表形成一个环
单链表为空条件为头结点的指针指向NULL L->next=NULL
循环单链表为空的条件为头结点的指否等于头指针 L->next=L

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int InitList_L(LinkList &L,int n)//后插法创建空表 
{
	L=new LNode;//头结点 
	L->next=L;
	LinkList r;//尾指针
	r=L;
	for(int i=1;i<=n;i++)
	{
		cout<<"请输入一个元素"<<endl;
		LNode *p=new LNode;
		cin>>p->data;
		p->next=L;//最后一个结点的next指针指向头结点L
		r->next=p;
		r=p;//r与L的关系为r->next=L
	}
	return 1;
}

插入和删除操作

循环单链表的插入删除算法与单链表的操作完全一样

遍历循环单链表

注意遍历时循环的条件要改为p->next!=L时继续遍历

循环单链表全部代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include<iostream>
using namespace std;
#define Maxsize 100
typedef char ElemType;
typedef struct LNode
{
	ElemType data;
	struct LNode *next;//next指向struct Lnode结构体变量 
}LNode,*LinkList;//结构体类型LNode 别名为*LinkList 
int InitList_L(LinkList &L,int n)//后插法创建空表 
{
	L=new LNode;//头结点 
	L->next=L;
	LinkList r;
	r=L;
	for(int i=1;i<=n;i++)
	{
		cout<<"请输入一个元素"<<endl;
		LNode *p=new LNode;
		cin>>p->data;
		p->next=L;
		r->next=p;
		r=p;
	}
	return 1;
}
int ListInsert_L(LinkList &L,int i,ElemType e)//插入数据 
{
	LNode *p=L;
	int j=1;
	while(p&&(j<i))
	{
		p=p->next;
		++j;
	}
	LNode *s=new LNode;
	s->data=e;
	s->next=p->next;
	p->next=s;
	return 1;
}
int ListDelete_L(LinkList &L,int i)//删除数据 
{
	LNode *p=L;
	int j=1;
	while(p&&(j<i))
	{
		p=p->next;
		++j;
	}
	LNode *q=new LNode;
	q=p->next;
	p->next=q->next;
	delete q;
	return 1;	
}
void Disp_L(LinkList L)//显示数据 
{
	LNode *p=L;
	while(p->next!=L)
	{
		p=p->next;
		cout<<p->data<<" ";
	}
	cout<<endl;
}
int main()
{
	LinkList L;
	cout<<"请输入要插入的元素数量";
	int i,j,m,n;
	ElemType e;
	cin>>n;
	if(InitList_L(L,n)) cout<<"单链表创建完毕"<<endl;
	else cout<<"单链表创建失败"<<endl; 
	do
	{
		cout<<"请输入对应功能的数字： 1.插入 2.删除 3.显示表 "<<endl;
		cin>>m;
		switch(m)
		{
			case 1:
				{
					cout<<"请输入要插入的位置"<<endl;
					cin>>i;
					cout<<"请输入要输入的元素"<<endl;
					cin>>e;
					if(!ListInsert_L(L,i,e)) cout<<"插入数据失败"<<endl;
					else cout<<"插入数据成功"<<endl;
					break; 
				}
			case 2:
				{
					cout<<"请输入要删除的位置"<<endl;
					cin>>i;
					if(!ListDelete_L(L,i)) cout<<"删除失败"<<endl;
					else cout<<"删除成功"<<endl;
					break; 
				}
			case 3:
				{
					cout<<"输出表数据"<<endl;
					Disp_L(L);
					break;
				}
		}
		cout<<"是否继续执行操作 1.继续 2.退出"<<endl;
		cin>>j;
	}while(j==1);
	return 0;
}

循环双链表

双链表的最后一个结点指向NULL r->next=NULL
循环双链表的最后一个结点的后继指针指向头结点r->next=L
头结点的前驱指针指向最后一个结点L->prior=r
从而整个链表形成一个环
双链表为空条件为头结点的指针指向NULL L->next=NULL
循环单链表为空的条件为头结点的后继指针与前驱指针等于头指针
L->next=L;L->prior=L

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int InitList(DLinkList &L,int n){
	L=new DNode;//头结点 
	L->next=L;	L->prior=L;//空表 
	DLinkList r;//尾指针 
	r=L;
	for(int i=1;i<=n;i++){
		cout<<"请输入一个元素"<<endl;
		DNode *p=new DNode;
		cin>>p->data;
		p->next=L;//最后一个结点的后继指向头结点
		L->prior=p; //头结点的前驱指向最后一个结点
		p->prior=r;
		r->next=p;
		r=p;//r->next=L L->prior=r;
	}
	return 1;
}

插入和删除操作

循环双链表的插入删除算法与双链表的操作完全一样

遍历循环双链表

注意遍历时循环的条件要改为p->next!=L时继续遍历

循环双链表全部代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<iostream>
using namespace std;
#define Maxsize 100
typedef char ElemType;
typedef struct DNode{
	ElemType data;
	struct DNode *prior,*next;//prior next指针指向struct DNode结构体变量 
}DNode,*DLinkList; //结构体类型为DNode 别名DLinkList
int InitList(DLinkList &L,int n){
	L=new DNode;//头结点 
	L->next=L;	L->prior=L;//空表 
	DLinkList r;//尾指针 
	r=L;
	for(int i=1;i<=n;i++){
		cout<<"请输入一个元素"<<endl;
		DNode *p=new DNode;
		cin>>p->data;
		p->next=L;//最后一个结点的后继指向头结点
		L->prior=p; //头结点的前驱指向最后一个结点
		p->prior=r;
		r->next=p;
		r=p;//r->next=L L->prior=r;
	}
	return 1;
}
int ListInsert(DLinkList &L,int i,ElemType e){//插入数据 
	DNode *p=L;
	int j=1;
	while(p&&(j<i))
	{
		p=p->next;
		++j;
	}
	DNode *s=new DNode;
	s->data=e;
	s->next=p->next;
	p->next->prior=s;
	s->prior=p;
	p->next=s;
	return 1; 
} 
int ListDelete(DLinkList &L,int i){
	DNode *p=L;
	int j=1;
	while(p&&(j<i)){
		p=p->next;
		++j;
	}
	DNode *q=new DNode;
	q=p->next;
	p->next=q->next;
	q->next->prior=p;
	delete q;
	return 1;
}
void ShowList(DLinkList L){//显示元素 
	DNode *p=L;
	while(p->next!=L)
	{
		p=p->next;
		cout<<p->data<<" ";
	}
	cout<<endl;
}
int main(){
	DLinkList L;
	cout<<"请输入要插入的元素数量";
	int i,j,m,n;
	ElemType e;
	cin>>n;
	if(InitList(L,n)) cout<<"双链表创建完毕"<<endl;
	else cout<<"双链表创建失败"<<endl; 
	do
	{
		cout<<"请输入对应功能的数字： 1.插入 2.删除 3.显示表 "<<endl;
		cin>>m;
		switch(m)
		{
			case 1:
				{
					cout<<"请输入要插入的位置"<<endl;
					cin>>i;
					cout<<"请输入要输入的元素"<<endl;
					cin>>e;
					if(!ListInsert(L,i,e)) cout<<"插入数据失败"<<endl;
					else cout<<"插入数据成功"<<endl;
					break; 
				}
			case 2:
				{
					cout<<"请输入要删除的位置"<<endl;
					cin>>i;
					if(!ListDelete(L,i)) cout<<"删除失败"<<endl;
					else cout<<"删除成功"<<endl;
					break; 
				}
			case 3:
				{
					cout<<"输出表数据"<<endl;
					ShowList(L);
					break;
				}
		}
		cout<<"是否继续执行操作 1.继续 2.退出"<<endl;
		cin>>j;
	}while(j==1);
	return 0;
}
End of reading! -- Thanks for your supporting