【数据结构】链表

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
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
#include<iostream>
#include<stack>
#include<cstdlib>
#include<cstdio>
using namespace std;
int n,j,pos;
typedef struct LNode{
int data;
struct LNode *next;
}LNode,*LinkList;
bool Linklist_Init(LinkList &L){
//初始化
L=new LNode;
L->next=NULL;
return true;
}
void Linklist_creatR(LinkList &L,int n){
//后插法建表
LNode *r;
LNode *p;
r=L;
for(int i=0;i<n;i++){
p=new LNode;
cin>>p->data;
p->next=NULL;
r->next=p;
r=p;
}
}
bool Linklist_Insert(LinkList &L,int i,int e){ //插入
LNode *p;
p=L;
j=0;
while(p&&(j<i-1)){
p=p->next;
++j;
}
if(!p||j>i-1)
return false;
LNode *s;
s=new LNode;
s->data=e;
s->next=p->next;
p->next=s;
n++;
return true;
}
bool Linklist_Delete(LinkList &L,int i){ //删除
LNode *p;
LNode *q;
p=L;
j=0;
while((p->next)&&(j<i-1)){
p=p->next;
++j;
}
if(!(p->next)||(j>i-1))
return false;
q=p->next;
p->next=q->next;
delete q;
//p->next=p->next->next;
return true;
}
LNode *LocateElem(LinkList &L,int e){//按元素值查找
LNode *p;
p=L->next;
pos=1;
while(p&&p->data!=e){
p=p->next;
pos++;
}
return p;
}
void Linklist_Show(LinkList &L){
//显示
LNode *p;
p=L->next;
//
int y=n;
//
while(y){
//虽然n是全局变量，但主函数用了while循环，导致每次刷新后，n未初始化，y无法初始化，程序卡退
//
cout<<p->data<<" ";
//
p=p->next;
//
y--;
//
}
if(p){
cout<<p->data<<" ";
while(p->next){
p=p->next;
cout<<p->data<<" ";
}
}
else
cout<<"链表为空，请先创建"<<endl;
return;
}
void menu(){
getchar();
getchar();
system("cls");
cout<<"请选择"<<endl;
cout<<"0,
初始化链表"<<endl;
cout<<"1,
建表"<<endl;
cout<<"2,
输出所有元素"<<endl;
cout<<"3,
删除"<<endl;
cout<<"4,
插入"<<endl;
cout<<"5,
退出"<<endl;
}
int main(){
cout<<"请选择"<<endl;
cout<<"0,
初始化链表"<<endl;
cout<<"1,
建表"<<endl;
cout<<"2,
输出所有元素"<<endl;
cout<<"3,
删除"<<endl;
cout<<"4,
插入"<<endl;
cout<<"5,
退出"<<endl;
int choose;
LinkList L=NULL;
while(cin>>choose){
switch(choose){
case 0:{
if(Linklist_Init(L)){
cout<<"初始化成功"<<endl;
}
else{
cout<<"初始化失败"<<endl;
}
menu();
continue;
}
case 1 :{
if(L!=NULL){
cout<<"请输入链表元素个数n"<<endl;
cin>>n;
cout<<"请输入n个元素"<<endl;
Linklist_creatR(L,n);
cout<<"创建成功！"<<endl;
}
else {
cout<<"链表未初始化"<<endl;
}
menu();
continue;
}
case 2 :{
if(L==NULL)
cout<<"链表未创建"<<endl;
else
Linklist_Show(L);
menu();
continue;
}
case 3 :{
cout<<"请输入要删除的值e"<<endl;
int e;
cin>>e;
LNode *F=LocateElem(L,e);
if(F==NULL){
cout<<"没有找到该元素"<<endl<<"链表数据如下："<<endl;
Linklist_Show(L);
}
else {
if(Linklist_Delete(L,pos)){
cout<<"删除成功"<<endl<<"链表数据如下："<<endl;
Linklist_Show(L);
}
}
menu();
continue;
}
case 4 :{
cout<<"请输入插入位置t,以及元素值e"<<endl;
int t,e;
cin>>t>>e;
if(Linklist_Insert(L,t,e))
cout<<"插入成功"<<endl;
else
cout<<"插入失败"<<endl;
menu();
continue;
}
case 5:{
cout<<"退出成功！"<<endl;
break;
}
default :{
cout<<"没有此选项!"<<endl;
menu(); continue;
}
}
}
return 0;
}

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
#include<iostream>
using namespace std;
struct LNode{
int data;
LNode *next;
};
int main(){
int n,p,k;
cout<<"请输入数字个数N"<<endl;
cin>>n;
cout<<"请输入N个数字"<<endl;
LNode* L;
//表头
LNode* r;
//表尾 (后插法)
L=new LNode;
r=new LNode;
L->next=NULL;
r=L;
cin>>L->data;
//表头也输入数据，方便操作
LNode* pp;
for(int i=1;i<=n-2;i++){
//建表
pp=new LNode;
cin>>pp->data;
pp->next=NULL;
r->next=pp;
r=pp;
}
pp=new LNode;
cin>>pp->data;
pp->next=L;
//循环链表，表位指向表头
r->next=pp;
//保留最后一个元素的位置
cout<<"请输入开始位置p,以及循环数k"<<endl;
cin>>p>>k;
cout<<"开始报数"<<endl;
LNode *pos;
pos=new LNode;
//先找到开始位置的前驱，方便删除；
if(p==1){
pos=r->next;
//第一个元素的前驱是最后一个元素
}
else{
pos=L;
int i=1;
while(i<p-1){
pos=pos->next;
i++;
}
}
int t=1;
//计数器
while(n){
if(t%k==0){
cout<<pos->next->data<<" "; //输出
pos->next=pos->next->next;
//删除操作
n--;
}
else{
pos=pos->next;
//往下遍历
}
t++;
}
free(L);free(pos);
free(r);free(pp);
cout<<endl<<"报数完毕!"<<endl;
return 0;
}