1 #include<iostream>
2 #include<string>
3 #include<iomanip>
4 #include<stdlib.h>
5 using namespace std;
6
7 typedef struct LNode {
8 int data; //结点的数据域
9 struct LNode *next; //结点的指针域
10 }LNode, *LinkList; //LinkList为指向结构体LNode的指针类型
11
12 bool InitList_L(LinkList &L)//构造一个空的单链表L
13 {
14 L=new LNode; //生成新结点作为头结点，用头指针L指向头结点
15 if(!L)
16 return false; //生成结点失败
17 L->next=NULL; //头结点的指针域置空
18 return true;
19 }
20
21 void CreateList_H(LinkList &L)//前插法创建单链表
22 {
23 //输入n个元素的值，建立到头结点的单链表L
24 int n;
25 LinkList s; //定义一个指针变量
26 L=new LNode;
27 L->next=NULL; //先建立一个带头结点的空链表
28 cout <<"请输入元素个数n：" <<endl;
29 cin>>n;
30 cout <<"请依次输入n个元素：" <<endl;
31 cout <<"前插法创建单链表..." <<endl;
32 while(n--)
33 {
34 s=new LNode; //生成新结点s
35 cin>>s->data; //输入元素值赋给新结点的数据域
36 s->next=L->next;
37 L->next=s; //将新结点s插入到头结点之后
38 }
39 }
40
41 void CreateList_R(LinkList &L)//尾插法创建单链表
42 {
43 //输入n个元素的值，建立带表头结点的单链表L
44 int n;
45 LinkList s, r;
46 L=new LNode;
47 L->next=NULL; //先建立一个带头结点的空链表
48 r=L; //尾指针r指向头结点
49 cout <<"请输入元素个数n：" <<endl;
50 cin>>n;
51 cout <<"请依次输入n个元素：" <<endl;
52 cout <<"尾插法创建单链表..." <<endl;
53 while(n--)
54 {
55 s=new LNode;//生成新结点
56 cin>>s->data; //输入元素值赋给新结点的数据域
57 s->next=NULL;//因为是尾插法，可能是最后一个节点，所以要置空
58 r->next=s;//将新结点s插入尾结点*r之后
59 r=s;//重新更新尾指针，r指向新的尾结点s
60 }
61 }
62
63 bool GetElem_L(LinkList L, int i, int &e)//单链表的取值
64 {
65 //在带头结点的单链表L中查找第i个元素
66 //用e记录L中第i个数据元素的值
67 int j;
68 LinkList p;
69 p=L->next;//p指向第一个结点，
70 j=1; //j为计数器
71 while (j<i && p) //顺链域向后扫描，直到p指向第i个元素或p为空
72 {
73 p=p->next; //p指向下一个结点
74 j++; //计数器j相应加1
75 }
76 if (!p || j>i)
77 return false; //i值不合法i＞n或i<=0
78 e=p->data; //取第i个结点的数据域
79 return true;
80 }
81
82 bool LocateElem_L(LinkList L, int e) //按值查找
83 {
84 //在带头结点的单链表L中查找值为e的元素
85 LinkList p;
86 p=L->next;
87 while (p && p->data!=e)//顺链域向后扫描，直到p为空或p所指结点的数据域等于e
88 p=p->next; //p指向下一个结点
89 if(!p)
90 return false; //查找失败p为NULL
91 return true;
92 }
93
94 bool ListInsert_L(LinkList &L, int i, int e)//单链表的插入
95 {
96 //在带头结点的单链表L中第i个位置插入值为e的新结点
97 int j;
98 LinkList p, s;
99 p=L;
100 j=0;
101 while (p&&j<i-1) //查找第i-1个结点，p指向该结点
102 {
103 p=p->next;
104 j++;
105 }
106 if (!p || j>i-1)//i＞n+1或者i＜1
107 return false;
108 s=new LNode; //生成新结点
109 s->data=e; //将新结点的数据域置为e
110 s->next=p->next; //将新结点的指针域指向结点ai
111 p->next=s; //将结点p的指针域指向结点s
112 return true;
113 }
114
115 bool ListDelete_L(LinkList &L, int i) //单链表的删除
116 {
117 //在带头结点的单链表L中，删除第i个位置
118 LinkList p, q;
119 int j;
120 p=L;
121 j=0;
122 while((p->next)&&(j<i-1)) //查找第i-1个结点，p指向该结点
123 {
124 p=p->next;
125 j++;
126 }
127 if (!(p->next)||(j>i-1))//当i>n或i<1时，删除位置不合理
128 return false;
129 q=p->next; //临时保存被删结点的地址以备释放空间
130 p->next=q->next; //改变删除结点前驱结点的指针域
131 delete q; //释放被删除结点的空间
132 return true;
133 }
134
135 void Listprint_L(LinkList L) //单链表的输出
136 {
137 LinkList p;
138 p=L->next;
139 while (p)
140 {
141 cout<<p->data<<" ";
142 p=p->next;
143 }
144 cout<<endl;
145 }
146
147 int main()
148 {
149 int i,x,e,choose;
150 LinkList L;
151 cout << "1. 初始化
";
152 cout << "2. 创建单链表（前插法）
";
153 cout << "3. 创建单链表（尾插法）
";
154 cout << "4. 取值
";
155 cout << "5. 查找
";
156 cout << "6. 插入
";
157 cout << "7. 删除
";
158 cout << "8. 输出
";
159 cout << "0. 退出
";
160 choose=-1;
161 while (choose!=0)
162 {
163 cout<<"请输入数字选择:";
164 cin>>choose;
165 switch (choose)
166 {
167 case 1: //初始化一个空的单链表
168 if (InitList_L(L))
169 cout << "初始化一个空的单链表!
";
170 break;
171 case 2: //创建单链表（前插法）
172 CreateList_H(L);
173 cout << "前插法创建单链表输出结果:
";
174 Listprint_L(L);
175 break;
176 case 3: //创建单链表（尾插法）
177 CreateList_R(L);
178 cout << "尾插法创建单链表输出结果:
";
179 Listprint_L(L);
180 break;
181 case 4: //单链表的按序号取值
182 cout << "请输入一个位置i用来取值:";
183 cin >> i;
184 if (GetElem_L(L,i,e))
185 {
186 cout << "查找成功
";
187 cout << "第" << i << "个元素是："<<e<< endl;
188 }
189 else
190 cout << "查找失败
";
191 break;
192 case 5: //单链表的按值查找
193 cout<<"请输入所要查找元素x:";
194 cin>>x;
195 if (LocateElem_L(L,x))
196 cout << "查找成功
";
197 else
198 cout << "查找失败! " <<endl;
199 break;
200 case 6: //单链表的插入
201 cout << "请输入插入的位置和元素（用空格隔开）:";
202 cin >> i;
203 cin >> x;
204 if (ListInsert_L(L, i, x))
205 cout << "插入成功.
";
206 else
207 cout << "插入失败!
";
208 break;
209 case 7: //单链表的删除
210 cout<<"请输入所要删除的元素位置i:";
211 cin>>i;
212 if (ListDelete_L(L, i))
213 cout<<"删除成功!
";
214 else
215 cout<<"删除失败!
";
216 break;
217 case 8: //单链表的输出
218 cout << "当前单链表的数据元素分别为:
";
219 Listprint_L(L);
220 cout << endl;
221 break;
222 }
223 }
224 return 0;
225 }
//合并链表
#include<iostream>
#include<string>
using namespace std;
typedef struct LNode {
int data; //结点的数据域
struct LNode *next; //结点的指针域
}LNode, *LinkList; //LinkList为指向结构体LNode的指针类型
void CreateList_R(LinkList &L)//尾插法创建单链表
{
//输入n个元素的值，建立带表头结点的单链表L
int n;
LinkList s, r;
L=new LNode;
L->next=NULL; //先建立一个带头结点的空链表
r=L; //尾指针r指向头结点
cout <<"请输入元素个数n：" <<endl;
cin>>n;
cout <<"请依次输入n个整型数(非递减)：" <<endl;
cout <<"尾插法创建单链表..." <<endl;
while(n--)
{
s=new LNode;//生成新结点
cin>>s->data; //输入元素值赋给新结点的数据域
s->next=NULL;
r->next=s;//将新结点s插入尾结点r之后
r=s;//r指向新的尾结点s
}
}
void mergelinklist(LinkList La, LinkList Lb, LinkList &Lc)
{
LinkList p,q,r;
p=La->next; //p指向La的第一个元素
q=Lb->next; //q指向Lb的第一个元素
Lc=La; //Lc指向La的头结点；LC为新生成的链表头结点指针
r=Lc; //r指向Lc的尾部
while(p&&q)//pq都为真的时候才可以比较
{
if(p->data<=q->data)//把p指向的结点串起来
{
r->next=p;
r=p;
p=p->next;//p后移一个结点
}
else //把q指向的结点串起来
{
r->next=q;
r=q;
q=q->next;
}
}
r->next=p?p:q;//相当于if(p) r->next=p; else r->next=q;
delete Lb;
}
void Listprint_L(LinkList L) //单链表的输出
{
LinkList p;
p=L->next;
while (p)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}
int main()
{
LinkList La,Lb,Lc;
cout << "创建有序（非递减）单链表La:"<<endl;
CreateList_R(La);
cout << "创建有序（非递减）单链表Lb:"<<endl;
CreateList_R(Lb);
cout << "将两个有序（非递减）单链表La和Lb合并为Lc："<<endl;
mergelinklist(La,Lb,Lc);
cout << "合并后的结果Lc："<<endl;
Listprint_L(Lc);
return 0;
}
//快慢指针找中间数
#include<iostream>
#include<string>
using namespace std;
typedef struct LNode {
int data; //结点的数据域
struct LNode *next; //结点的指针域
}LNode, *LinkList; //LinkList为指向结构体LNode的指针类型
void CreateList_R(LinkList &L)//尾插法创建单链表
{
//输入n个元素的值，建立带表头结点的单链表L
int n;
LinkList s, r;
L=new LNode;
L->next=NULL; //先建立一个带头结点的空链表
r=L; //尾指针r指向头结点
cout <<"请输入元素个数n：" <<endl;
cin>>n;
cout <<"尾插法（正序）创建单链表..." <<endl;
while(n--)
{
s=new LNode;//生成新结点
cin>>s->data; //输入元素值赋给新结点的数据域
s->next=NULL;
r->next=s;//将新结点s插入尾结点r之后
r=s;//r指向新的尾结点s
}
}
LinkList findmiddle(LinkList L)
{
LinkList p,q;
p=L; //p为快指针，初始时指向L
q=L; //q为慢指针，初始时指向L
while(p!=NULL&&p->next!=NULL)
{
p=p->next->next;//p为快指针一次走两步；
q=q->next; //q为慢指针一次走一步
}
return q;//返回中间结点指针
}
void Listprint_L(LinkList L) //单链表的输出
{
LinkList p;
p=L->next;
while (p)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}
int main()
{
LinkList L,mid;
cout<<"创建单链表L:"<<endl;
CreateList_R(L);
cout<<"单链表数据为:"<<endl;
Listprint_L(L);
mid=findmiddle(L);
cout<<"单链表中间结点数据为："<<mid->data<<endl;
return 0;
}