单链表的基本操作

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
#include <iostream>
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef int elemtype;
typedef struct LNode{
//单链表的存储结构
elemtype date;
//结点的数据域
struct LNode *next; //结点的指针域
}LNode,*Linklist;
//Linklist为指向结构体LNode的指针类型
Status Initlist_L(Linklist &L)//构造一个空的单链表L
{
L=new LNode;//生成新结点作为头结点，用头指针L指向头结点
L->next=NULL;//头结点的指针域为空
return OK;
}
Status Getelem_L(Linklist L,int i,elemtype &e)//按序号查找，在带头结点的单链表L中
//查找第i个元素
{
int j;
LNode *p;
p=L->next;j=1;//初始化，p指向第一个结点，j为计数器
while(p&&j<i) //顺链域向后扫描，直至p指向第i个元素或p为空
{
p=p->next;j++;
}
if(!p||j>i)
return ERROR;//第i个元素不存在
e=p->date;//取第i个元素
return OK;
}
//按值查找
LNode *Locatelem_L(Linklist L,elemtype e)
{
LNode *p;
p=L->next;
while(p&&p->date!=e)//寻找满足条件的结点
p=p->next;//返回L中值为e的数据元素的值，查找失败返回NULL
return p;
}
//单链表的插入
//在带头结点的单链表L中第i个位置之前插入元素e
Status Linkinsert_L(Linklist &L,int i,elemtype e)
{
LNode *p,*s;
int j;
p=L;j=0;
while(p&&j<i-1)//寻找第i-1个结点
{
p=p->next;
j++;
}
if(!p||j>i-1)	return ERROR;//i大于表长+1 或小于1
s=new LNode;
//生成新结点s
s->date=e;
//将结点s的数据域设为e
s->next=p->next;//将结点插入L中
p->next=s;
return OK;
}
//单链表的删除
Status Listdelete_L(Linklist &L,int i,elemtype &e)
{
LNode *p,*q;
int j;
p=L;j=0;
while(p->next&&j<i-1)
{
p=p->next;
j++;
}
if(!(p->next)||j>i-1) return ERROR;
q=p->next;//临时保存被删除结点的地址以备释放
p->next=q->next;//改变删除结点前驱结点的指针域
e=q->date;//保存删除结点的数据域
delete q;//释放删除结点的空间
return OK;
}
//前插法创建单链表
void Createlist_F(Linklist &L,int n)
{
int i;
LNode *p;
L=new LNode;//先建立一个带头结点的空链表
L->next=NULL;
for(i=n;i>0;i--)
{
p=new LNode;//生成新结点
cin>>p->date;//输入元素值
p->next=L->next;//插入到表头
L->next=p;
}
}
//后插法创建单链表
void Createlist_L(Linklist &L,int n)
{
LNode *p,*r;
L=new LNode;
L->next=NULL;
r=L;//尾指针指向头结点
cout<<"请输入元素：";
for(int i=0;i<n;i++)
{
p=new LNode;
cin>>p->date;
p->next=NULL;//插入到表尾
r->next=p;
r=p;//r指向新的尾结点
}
}
int main()
{
int choose,a,b,n1;
elemtype
rec;
LNode *p,*la;
cout<<"1.建立链表n";
cout<<"2.输入数据n";
cout<<"3.按位置查找元素n";
cout<<"4.按值查找元素n";
cout<<"5.链表的插入n";
cout<<"6.链表的删除n";
cout<<"7.输出数据n";
cout<<"0.退出nn";
choose=-1;
while(choose!=0)
{
cout<<"请选择:";
cin>>choose;
switch(choose)
{
case 1:
if(Initlist_L(la))
cout<<"成功建立链表！nn";
break;
case 2:
cout<<"请输入要输入的元素个数：";
cin>>n1;
Createlist_L(la,n1);
cout<<"成功创建链表！"<<endl<<endl;
break;
case 3:
cout<<"请输入要查找的元素的位置：";
cin>>a;
if(Getelem_L(la,a,rec))
cout<<"查找成功！第"<<a<<"个数是"<<rec<<endl<<endl;
else
cout<<"查找失败！nn";
break;
case 4:
cout<<"请输入一个数值来查找：";
cin>>b;
if(Locatelem_L(la,b)!=NULL)
cout<<"查找成功！nn";
else
cout<<"查找失败！元素"<<b<<"没有找到！nn";
break;
case 5:
cout<<"请分别输入两个数代表要插入的元素及其位置：";
cin>>a>>b;
if(Linkinsert_L(la,b,a))
cout<<"成功将"<<a<<"插入"<<"第"<<b<<"个位置nn";
else
cout<<"插入失败！nn";
break;
case 6:
cout<<"请输入要删除的元素的位置：";
cin>>a;
if(Listdelete_L(la,a,rec))
cout<<"删除成功！被删除的数是："<<rec<<"nn";
else
cout<<"删除失败！nn";
break;
case 7:
cout<<"当前链表里的元素是：";
p=la->next;
while(p)
{
cout<<p->date<<" ";
p=p->next;
}
cout<<endl<<endl;
break;
}
}
}