数据结构复习·3 线性表：双链表
宏定义
建议重新复习一下C++对结构体的定义以及typedef声明新的类型名
1
2
3
4
5
6
7
8
9
10
11
12
|
using namespace std;
typedef char ElemType;
typedef struct DNode{
ElemType data;
struct DNode *prior,*next;//prior next指针指向struct DNode结构体变量
//prior为前驱指针 next为后继指针
}DNode,*DLinkList; //结构体类型为DNode 别名DLinkList
|
后插法创建双链表
后插法(尾插法)：新元素插入到链表表尾，结点的次序与插入的次序是一致的
后插法只比头插法多了一个指向表尾结点的指针r
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| int InitList(DLinkList &L,int n){
L=new DNode;//头结点
L->next=NULL;
DLinkList r;//创建表尾指针r
r=L;
for(int i=1;i<=n;i++){
cout<<"请输入一个元素"<<endl;
DNode *p=new DNode;
cin>>p->data;
p->next=NULL;
p->prior=r;
r->next=p;
r=p;
}
return 1;
}
|
插入结点(针对后插法创建的链表)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 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;
}
|
删除结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 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;
}
|
显示双链表内数据
1
2
3
4
5
6
7
8
9
| void ShowList(DLinkList L){//显示元素
DNode *p=L;
while(p->next!=NULL)
{
p=p->next;
cout<<p->data<<" ";
}
cout<<endl;
}
|
如果需要计算表长 在while循环里放置一个计数器i输出即可
所有代码
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
|
using namespace std;
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=NULL;
DLinkList r;
r=L;
for(int i=1;i<=n;i++){
cout<<"请输入一个元素"<<endl;
DNode *p=new DNode;
cin>>p->data;
p->next=NULL;
p->prior=r;
r->next=p;
r=p;
}
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!=NULL)
{
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;
}
|
