数据结构实验报告

右边👉是实验报告文档→📖

实验一 顺序表的操作

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
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<cstdio>
using namespace std;
#define ElemType int
typedef int Status;
#define OK 1
#define ERROR 0
#define OVERFLOW 3
#define MAXSIZE 100
typedef struct{
ElemType* elem;
int length;
}SqList;
Status InitList(SqList &L);//初始化
Status ClearList(SqList &L);//清空
Status ListEmpty(SqList L);//判断是否为空
Status GetElem(SqList L,int i,ElemType& e);//获取表中第i位的元素
Status ListLength(SqList L);//求线性表的长度
Status ListInsert(SqList &L,int i,ElemType e);//在线性表指定位置插入元素
void ShowList(SqList L);//显示线性表所有元素
Status ListDelete(SqList& L,int i);//删除线性表指定位置元素
Status LocateElem(SqList L,int e);//定位第一个i出现的位置
Status NextElem(SqList L,int cur_e,int& next_e);//求后继
Status PriorElem(SqList L,int cur_e,int& pre_e);//求前驱
int main()
{
int order;
SqList L;
if(InitList(L)){
cout<<"初始化成功!\n";
}else cout<<"初始化失败!\n";
while(true){
cout << "Menu***********************************\n";
cout << "1---(清空) 清空线性表\n"; //ClearList(&L)
cout << "2---(判空) 判断线性表是否为空\n"; //ListEmpty(L)
cout << "3---(求长) 求线性表长度\n"; //ListLength(L)
cout << "4---(获取) 获取线性表指定位置元素\n"; //GetElem()
cout << "5---求前驱\n"; //PriorElem(L,cur_e,&pre_e)
cout << "6---求后继\n"; //NextElem(L,cur_e,&next_e)
cout << "7---(插入) 在线性表指定位置插入元素\n"; //ListInsert(&L,i,e)
cout << "8---(删除) 删除线性表指定位置元素\n"; //ListDelete(&L,i)
cout << "9---显示线性表\n"; //ShowList(L)
cout << "10--定位\n"; //LocateElem(L,e)
cout << "11--求两个集合的交集,并集和差集\n";//
cout << " 退出,输入一个负数!\n";
cout << "Menu***********************************\n";
cout << "请输入操作代码:";
cin >> order;
if (order < 0) return 0;
cout << "\n";
int i;
ElemType e,cur_e,pre_e,next_e;
switch (order) {
case 1:
cout << (ClearList(L) ? "清空成功!\n" : "清空失败!\n");
cout << "线性表长度为:" << ListLength(L) << "\n";
break;
case 2:
cout << (ListEmpty(L) ? "线性表为空\n" : "线性表不为空\n");
break;
case 3:
cout << "线性表长度为:" << ListLength(L) << "\n";
break;
case 4:
cout << "请输入要获取第几位元素:";
cin >> i;
if (GetElem(L, i, e))
cout << "第" << i << "位元素是:" << e << "\n";
else cout << "第" << i << "位元素不存在!\n";
break;
case 5:
cout<<"请输入你要求谁的前驱:";
cin>>cur_e;
if(PriorElem(L,cur_e,pre_e)) cout<<cur_e<<"的前驱是:"<<pre_e<<"\n";
else cout<<"该元素不存在或者没有前驱\n";
break;
case 6:
cout<<"请输入你要求谁的后继:";
cin>>cur_e;
if(NextElem(L,cur_e,next_e)) cout<<cur_e<<"的后继是:"<<next_e<<"\n";
else cout<<"该元素不存在或者没有后继\n";
break;
case 7:
cout << "请输入插入位置:";
cin >> i;
cout << "请输入插入数据:";
cin >> e;
cout << (ListInsert(L, i, e) ? "插入成功!\n" : "插入失败!\n");
break;
case 8:
cout << "请输入你要删除的位置:";
cin >> i;
cout << (ListDelete(L, i) ? "删除成功!\n" : "删除失败!\n");
break;
case 9:
ShowList(L);
break;
case 10:
cout<<"请输入你要定位的元素:";
cin>>e;
if(LocateElem(L,e)) cout<<e<<"的位置是"<<LocateElem(L,e)<<"\n";
else cout<<"不存在\n";
break;
case 11:
SqList A,B;
InitList(A);
for(int i=0;i<10;i++){
ListInsert(A,i+1,i+1);
}
cout<<"已经生成了A,";
ShowList(A);
InitList(B);
for(int i=0;i<10;i++){
ListInsert(B,i+1,i+6);
}
cout<<"已经生成了集合B,";
ShowList(B);
cout<<"A和B的交集是:";
for(int i=0;i<A.length;i++){
for(int j=0;j<B.length;j++){
if(A.elem[i]==B.elem[j]){
cout<<A.elem[i]<<" ";
break;
}
}
}
cout<<"\nA和B的并集是:";
for(int i=0;i<A.length;i++){
if(LocateElem(B,A.elem[i])) continue;
else cout<<A.elem[i]<<" ";
}
for(int i=0;i<B.length;i++){
cout<<B.elem[i]<<" ";
}
cout<<"\nA和B的差集如下:\n";
cout<<" A-B=";
for(int i=0;i<A.length;i++){
if(LocateElem(B,A.elem[i])) continue;
else cout<<A.elem[i]<<" ";
}
cout<<"\n B-A=";
for(int i=0;i<B.length;i++){
if(LocateElem(A,B.elem[i])) continue;
else cout<<B.elem[i]<<" ";
}
cout<<"\n";
break;
default:
cout << "输入命令错误!";
break;
}
cout<<"按回车键继续....";
getchar();getchar();
}
}
Status InitList(SqList &L){
L.elem=new ElemType[MAXSIZE];
if(!L.elem) exit(OVERFLOW);
L.length=0;
return OK;
}
Status ClearList(SqList &L){
L.length=0;
return OK;
}
Status ListEmpty(SqList L){
return (!L.length);
}
Status GetElem(SqList L,int i,ElemType& e){
if(i<=0||i>L.length) return ERROR;
e=L.elem[i-1];
return OK;
}
Status ListLength(SqList L){
return L.length;
}
Status ListInsert(SqList &L,int i,ElemType e){
if(i<=0||i>L.length+1) return ERROR;
if(L.length==MAXSIZE) return ERROR;
for(int j=L.length-1;j>=i-1;j--){
L.elem[j+1]=L.elem[j];
}
L.elem[i-1]=e;
L.length++;
return OK;
}
void ShowList(SqList L){
if(ListEmpty(L)) {
cout<<"线性表为空!\n";
return ;
}else cout<<"线性表元素为:";
for(int i=0;i<L.length;i++){
cout<<L.elem[i]<<" ";
}cout<<"\n";
}
Status ListDelete(SqList& L,int i){
if(i<=0||i>L.length) return ERROR;
for(int j=i;j<L.length;j++){
L.elem[i-1]=L.elem[i];
}
L.length--;
return OK;
}
Status LocateElem(SqList L,int e){
for(int i=0;i<L.length;i++){
if(L.elem[i]==e) return i+1;
}
return ERROR;
}
Status PriorElem(SqList L,int cur_e,int &pre_e){
int ret=LocateElem(L,cur_e);
if(ret&&ret!=1){
pre_e=L.elem[ret-2];
return OK;
}else return ERROR;
}
Status NextElem(SqList L,int cur_e,int &next_e){
int ret=LocateElem(L,cur_e);
if(ret&&ret!=L.length){
next_e=L.elem[ret];
return OK;
}else return ERROR;
}

实验二 单链表的操作

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
#include<iostream>
#define ElemType int
typedef int Status;
#define OK 1
#define ERROR 0
typedef struct LNode{
ElemType data;
LNode* next;
}LNode,*LinkList;
Status InitList(LinkList &L);//单链表的初始化
void CreateList_H(LinkList &L,int n);//前插法创建单链表
void CreateList_R(LinkList &L,int n);//后插法创建单链表
LNode* LocateElem(LinkList L,ElemType e);//定位单链表中的元素位置
Status ListInsert(LinkList &L,int i,ElemType e);//插入元素
Status ListDelete(LinkList &L,int i);//删除元素
void ShowList(LinkList L);//显示链表内容
void Merge(LinkList A,LinkList B,LinkList &C);//合并两个单链表
using namespace std;
int main()
{
LinkList L;
while(true){
cout<<"1710121058李博\n";
cout<<"0----初始化创建空的单链表\n";
cout<<"1----前插法创建单链表插入n个元素\n";
cout<<"2----后插法创建单链表插入n个元素\n";
cout<<"3----查找单链表\n";
cout<<"4----插入单链表\n";
cout<<"5----删除单链表\n";
cout<<"6----两个有序单链表的归并运算\n";
cout<<"7----显示单链表所有元素\n";
cout<<"输入负数退出\n";
int order,i,e,n;
cout<<"请输入你要执行的操作:";
cin>>order;
if(order<0) break;
switch(order){
case 0:
if(InitList(L)) cout<<"初始化成功!\n";
else cout<<"初始化失败!\n";
break;
case 1:
cout<<"请输入你要建的链表长度n和n个内容:";
cin>>n;
CreateList_H(L,n);
break;
case 2:
cout<<"请输入你要建的链表长度n和n个内容:";
cin>>n;
CreateList_R(L,n);
break;
case 3:
cout<<"请输入你需要查找的元素:";
cin>>e;
if(LocateElem(L,e)) cout<<"元素"<<e<<"的位置在"<<LocateElem(L,e)<<"\n";
else cout<<"该元素不在链表中!\n";
break;
case 4:
cout<<"请输入你要插入的位置和插入的元素(空格隔开):";
cin>>i>>e;
ListInsert(L,i,e);
break;
case 5:
cout<<"请输入你要删除元素的位置:";
cin>>i;
cout<<(ListDelete(L,i)?"删除成功!\n":"删除失败!\n");
break;
case 6:
LinkList A,B,C;
cout<<"首先建立两个有序的单链表A和B\n";
cout<<"请输入A的长度n和n个内容:";
cin>>n;
CreateList_R(A,n);
cout<<"请输入B的长度n和n个内容:";
cin>>n;
CreateList_R(B,n);
cout<<"已经建立好单链表A和B\n";
cout<<"建立好的表分别如下:\n";
InitList(C);
cout<<"A"; ShowList(A);
cout<<"B"; ShowList(B);
Merge(A,B,C);
cout<<"合并以后的";
ShowList(C);
break;
case 7:
ShowList(L);
break;
default:
cout<<"输入指令错误!\n";
break;
}
cout<<"按回车键继续...\n";
getchar();
getchar();
}

return 0;
}
Status InitList(LinkList &L){
L=new LNode;
L->next=NULL;
return OK;
}
void CreateList_H(LinkList &L,int n){//逆序位输入n个元素的值,建立带表头结点的单链表
L=new LNode;
L->next=NULL;
for(int i=0;i<n;i++){
LNode* p=new LNode;
cin>>p->data;
p->next=L->next;
L->next=p;
}
}
void CreateList_R(LinkList &L,int n){//正位序输入n个元素的值,建立带表头节点的单链表
L=new LNode;
LNode* r=L;
for(int i=0;i<n;i++){
LNode* p=new LNode;
cin>>p->data;
p->next=NULL;
r->next=p;
r=p;
}
}
LNode *LocateElem(LinkList L,ElemType e){
LNode* p=L->next;
while(p&&p->data!=e){
p=p->next;
}
return p;
}
Status ListInsert(LinkList &L,int i,ElemType e){
LNode* p=L;
int j=0;
while(p&&j<i-1){
p=p->next;
j++;
}
if(!p||j>i-1) return ERROR;
LNode* s=new LNode;
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}
Status ListDelete(LinkList &L,int i){
LNode* p=L;
int j=0;
while(p&&j<i-1){
p=p->next;
j++;
}
if(!(p->next)||j>i-1) return ERROR;
LNode* q=p->next;
p->next=q->next;
delete(q);
return OK;
}
void ShowList(LinkList L){
LNode* p=L;
if(p->next==NULL){
cout<<"链表为空\n";
return ;
}
cout<<"链表内容为:";
while(p->next){
p=p->next;
cout<<p->data<<" ";
}
cout<<endl;
}
void Merge(LinkList A,LinkList B,LinkList &C){
LNode* pa=A->next;
LNode* pb=B->next;
C=A;
LNode* pc=C;
while(pa&&pb){
if(pa->data<=pb->data){
pc->next=pa;
pc=pa;
pa=pa->next;
}else{
pc->next=pb;
pc=pb;
pb=pb->next;
}
}
pc->next=pa?pa:pb;
}

实验三 栈和队列的操作

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
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
#include<iostream>
#define MAXSIZE 100
#define SElemType int
#define QElemType int
typedef int Status;
#define OK 1
#define OVERFLOW -2
#define ERROR 0
using namespace std;
///--------------栈操作部分--------------///
typedef struct{
SElemType *base;
SElemType *top;
int stackSize;
}SqStack;
typedef struct StackNode{
SElemType data;
struct StackNode *next;
}StackNode,*LinkStack;

Status InitStack(SqStack &S){
S.base=new SElemType[MAXSIZE];
if(!S.base) exit(OVERFLOW);
S.top=S.base;
S.stackSize=MAXSIZE;
return OK;
}
Status InitStack(LinkStack &S){
S=NULL;
return OK;
}
SElemType GetTop(SqStack S){
if(S.base!=S.top){
cout<<"栈顶元素为:"<<*(S.top-1)<<"\n";
}else{
cout<<"栈为空\n";
}
return OK;
}
SElemType GetTop(LinkStack S,SElemType &e){
if(S!=NULL){
e=S->data;
return OK;
}else{
return ERROR;
}
}
Status Push(SqStack &S,SElemType e){
if(S.top-S.base==S.stackSize) {
cout<<"栈已满,入栈失败!\n";
return ERROR;
}
*S.top++=e;
cout<<"入栈成功!\n";
return OK;
}
Status Push(LinkStack S,SElemType e){
StackNode* p=new StackNode;
p->data=e;
p->next=S;
S=p;
return OK;
}
Status Pop(SqStack &S,SElemType &e){
if(S.top==S.base){
cout<<"栈为空,出栈失败!\n";
return ERROR;
}
e=*--S.top;
cout<<"出栈元素为:"<<e<<".\n";
return OK;
}
Status Pop(LinkStack S,SElemType &e){
if(S==NULL){
cout<<"栈为空,出栈失败!\n";
return ERROR;
}
e=S->data;
StackNode* p=new StackNode;
p=S;
S=S->next;
delete p;
cout<<"出栈元素为:"<<e<<"\n";
return OK;
}
///-----------队列部分--------------///
typedef struct{
QElemType *base;
int front;
int rear;
}SqQueue;

typedef struct QNode{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;

typedef struct{
QueuePtr front;
QueuePtr rear;
}LinkQueue;

Status InitQueue(SqQueue &Q){
Q.base=new QElemType[MAXSIZE];
if(!Q.base) return OVERFLOW;
Q.front=Q.rear=0;
return OK;
}

Status InitQueue(LinkQueue &Q){
Q.front=Q.rear=new QNode;
Q.front->next=NULL;
return OK;
}

Status GetHead(SqQueue Q){
if(Q.front==Q.rear){
cout<<"队列为空\n";
return ERROR;
}else{
cout<<"队头元素为:"<<Q.base[Q.front]<<"\n";
return OK;
}

}
QElemType GetHead(LinkQueue Q){
if(Q.front==Q.rear){
cout<<"队列为空\n";
return ERROR;
}else{
cout<<"队头元素为:"<<Q.front->next->data<<"\n";
return OK;
}
}

Status EnQueue(SqQueue &Q,QElemType e){
if((Q.rear+1)%MAXSIZE==Q.front){
cout<<"队列已满\n";
return ERROR;
}
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MAXSIZE;
cout<<"入队成功\n";
return OK;
}
Status EnQueue(LinkQueue &Q,QElemType e){
QueuePtr p=new QNode;
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
cout<<"入队成功\n";
return OK;
}

Status DeQueue(SqQueue &Q){
if(Q.front==Q.rear){
cout<<"队列为空\n";
return ERROR;
}
Q.front=(Q.front+1)%MAXSIZE;
cout<<"出队成功\n";
return OK;
}
Status DeQueue(LinkQueue &Q){
if(Q.front==Q.rear){
cout<<"队列为空\n";
return ERROR;
}
QueuePtr p=Q.front->next;
Q.front->next=p->next;
if(Q.rear==p) Q.rear=Q.front;
delete p;
cout<<"出队成功\n";
return OK;
}
int main(){
SqStack S1;
LinkStack S2;
SElemType Se;

SqQueue Q1;
LinkQueue Q2;
QElemType Qe;

while(true){
int order;
cout<<"1:建栈(顺序表)\n";
cout<<"2:取栈顶元素(顺序表)\n";
cout<<"3:入栈(顺序表)\n";
cout<<"4:出栈(顺序表)\n";
cout<<"5:建栈(链表)\n";
cout<<"6:取栈顶元素(链表)\n";
cout<<"7:入栈(链表)\n";
cout<<"8:出栈(链表)\n";

cout<<"9:建队列(顺序表)\n";
cout<<"10:取队头元素(顺序表)\n";
cout<<"11:入队(顺序表)\n";
cout<<"12:出队(顺序表)\n";
cout<<"13:建队列(链表)\n";
cout<<"14:取队头元素(链表)\n";
cout<<"15:入队(链表)\n";
cout<<"16:出队(链表)\n";
cout<<"输入负数---退出\n";
cin>>order;
if(order<0) break;
switch (order)
{
case 1:
InitStack(S1);
break;
case 2:
GetTop(S1);
break;
case 3:
cout<<"输入你想入栈的元素:";
cin>>Se;
Push(S1,Se);
break;
case 4:
Pop(S1,Se);
break;
case 5:
InitStack(S2);
break;
case 6:
if(GetTop(S2,Se)){
cout<<"栈顶元素为:"<<Se<<"\n";
}else{
cout<<"栈为空!\n";
}
break;
case 7:
cout<<"输入你想入栈的元素:";
cin>>Se;
Push(S2,Se);
break;
case 8:
Pop(S2,Se);
break;
case 9:
InitQueue(Q1);
break;
case 10:
GetHead(Q1);
break;
case 11:
cout<<"输入你想入队的元素:";
cin>>Qe;
EnQueue(Q1,Qe);
break;
case 12:
DeQueue(Q1);
break;
case 13:
InitQueue(Q2);
break;
case 14:
GetHead(Q2);
break;
case 15:
cout<<"输入你想入队的元素:";
cin>>Qe;
EnQueue(Q2,Qe);
break;
case 16:
DeQueue(Q2);
break;
default:
cout<<"输入指令有误,请重新输入\n";
break;
}
}
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
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
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
#include<iostream>
#include<queue>
#include<stack>
#include<cstring>
#include<climits>
using namespace std;
#define TElemType char
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void CreatBiTree(BiTree &T){//先序递归建树
char ch;cin>>ch;
if(ch=='#') T=NULL;
else{
T=new BiTNode;
T->data=ch;
CreatBiTree(T->lchild);
CreatBiTree(T->rchild);
}
}
void PreOrderTraverse(BiTree T){//先序递归遍历
if(T){
cout<<T->data<<" ";
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
void InOrderTraverse(BiTree T){//中序递归遍历
if(T){
InOrderTraverse(T->lchild);
cout<<T->data<<" ";
InOrderTraverse(T->rchild);
}
}
void PostOrderTraverse(BiTree T){//后序递归遍历
if(T){
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout<<T->data<<" ";
}
}
void LevelOrderTraverse(BiTree T){
queue<BiTNode*>qu;
if(T) qu.push(T);
while(!qu.empty()){
BiTNode *cur=qu.front();
qu.pop();
cout<<cur->data<<" ";
if(cur->lchild) qu.push(cur->lchild);
if(cur->rchild) qu.push(cur->rchild);
}
}
int Depth(BiTree T){
if(T==NULL) return 0;
return max(Depth(T->lchild)+1,Depth(T->rchild)+1);
}
int LeafNodeCount(BiTree T,int cnt){
queue<BiTNode*>qu;//这个最好自己实现一个队列,很简单,我下一个的队列是自己直接在函数里面实现了一个。
if(T) qu.push(T);
else cnt++;
while(!qu.empty()){
BiTNode* cur=qu.front();
qu.pop();
if(cur->lchild) qu.push(cur->lchild);
if(cur->rchild) qu.push(cur->rchild);
if(!(cur->lchild||cur->rchild)) cnt++;
}
return cnt;
}
int Leaf(BiTree T){
if(T==NULL) return 0;
if(T->lchild==NULL&&T->rchild==NULL) return 1;
return Leaf(T->lchild)+Leaf(T->rchild);
}
void InOrderTraverse2(BiTree T){
stack<BiTNode*>st;//最好自己实现。
BiTNode* p=T,q;
while(p||!st.empty()){
if(p){
st.push(p);
p=p->lchild;
}else{
p=(st.top())->rchild;
cout<<(st.top())->data<<" ";
st.pop();
}
}
}
//-----------------下面是哈夫曼树部分-------------------
typedef struct{
int weight; //结点的权值
int parent,lchild,rchild; //结点的双亲,左孩子,右孩子的下标
}HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树
typedef char **HuffmanCode; //动态分配数组存储哈夫曼编码表
void Select(HuffmanTree HT,int r,int &s1,int &s2){
int min_weight=INT_MAX;
for(int i=1;i<=r;i++){
if(HT[i].weight<=min_weight&&HT[i].parent==0){
s1=i;
min_weight=HT[i].weight;
}
}
min_weight=INT_MAX;
for(int i=1;i<=r;i++){
if(i==s1) continue;
if(HT[i].weight<=min_weight&&HT[i].parent==0){
s2=i;
min_weight=HT[i].weight;
}
}
}
void CreateHuffmanTree(HuffmanTree &HT,int n){
if(n<=1) return;
int m=2*n-1;
HT=new HTNode[m+1];//0号不用
for(int i=1;i<=m;++i){
HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;
}
for(int i=1;i<=n;i++){
cin>>HT[i].weight;
}
for(int i=n+1;i<=m;i++){
int s1,s2;
Select(HT,i-1,s1,s2);
HT[s1].parent=i;HT[s2].parent=i;
HT[i].lchild=s1;HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
}
void CreatHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n){
HC=new char*[n+1];
char *cd=new char[n];
cd[n-1]='\0';
for(int i=1;i<=n;i++){
int start=n-1;
int c=i,f=HT[i].parent;//c is cur
while(f!=0){
--start;
if(HT[f].lchild==c) cd[start]='0';
else cd[start]='1';
c=f;
f=HT[f].parent;
}
HC[i]=new char[n-start];
strcpy(HC[i],&cd[start]);
}
delete[] cd;
}
int main(){
cout<<"李博-1710121058\n";
BiTree T;
cout<<"前序遍历建树,请输入节点信息:";
CreatBiTree(T);
cout<<endl<<"前序遍历:";
PreOrderTraverse(T);
cout<<endl<<"中序递归遍历:";
InOrderTraverse(T);
cout<<endl<<"中序非递归遍历:";
InOrderTraverse2(T);
cout<<endl<<"后序遍历:";
PostOrderTraverse(T);
cout<<endl<<"层序遍历:";
LevelOrderTraverse(T);
cout<<endl<<"深度:";
cout<<Depth(T);
cout<<endl<<"非递归求叶子个数:";
cout<<Leaf(T);
cout<<endl<<"递归求叶子个数:";
cout<<LeafNodeCount(T,0)<<endl;
cout<<"下面是哈夫曼树部分--------------------------\n";
HuffmanTree HT;
HuffmanCode HC;
char Hfstring[30];
cout<<"*****************************************************\n";
cout<<"*** 1,输入HuffmanTree的参数 ***\n";
cout<<"*** 2,初始化HuffmanTree参数.(含有26字母及空格) ***\n";
cout<<"*** 3,创建HuffmanTree和编码表. ***\n";
cout<<"*** 4,输出编码表 ***\n";
cout<<"*** 5,输入编码,并翻译为字符. ***\n";
cout<<"*** 6,输入字符,并实现转码. ***\n";
cout<<"*** 7,退出. ***\n";
cout<<"*****************************************************\n";
int order,cur;
string str;
while(cin>>order&&order!=7){
switch (order){
case 1:
cout<<"请输入参数:";
//64 13 22 32 103 21 15 47 57 1 5 32 20 57 63 15 1 48 51 80 23 8 18 1 16 1 168
CreateHuffmanTree(HT,27);
break;
case 2:
CreateHuffmanTree(HT,27);
break;
case 3:
CreatHuffmanCode(HT,HC,27);
break;
case 4:
cout<<"编码表如下:\n";
for(int i=1;i<=26;i++){
cout<<(char)('a'+i-1)<<" : "<<HC[i]<<endl;
}
cout<<" "<<" : "<<HC[27]<<endl;
break;
case 5:
cout<<"请输入一段编码:";
getchar();
getline(cin,str);
cur=2*27-1;
for(int i=0;i<str.length();i++){
if(str[i]=='0') cur=HT[cur].lchild;
else cur=HT[cur].rchild;
if(HT[cur].lchild==0&&HT[cur].rchild==0){
if(cur==27) cout<<" ";
else cout<<(char)('a'+cur-1);
cur=2*27-1;
}
}
cout<<endl;
break;
case 6:
//i love you
//01111111010010011100000010111100011100100001
cout<<"请输入一段字符:";
getchar();
getline(cin,str);
cout<<str.length()<<"len\n";
for(int i=0;i<str.length();i++){
if(isalpha(str[i])) cout<<HC[(str[i]-'a'+1)];
else cout<<HC[27];
}
cout<<endl;
break;
default:
cout<<"您输入的命令有误.\n";
break;
}
}
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
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
212
213
#include<iostream>
using namespace std;
#define OK 1
#define ERROR 0
/********************下面是邻接矩阵********************/
#define MaxInt 32767
#define MVNum 100
typedef char VerTexType;
typedef int ArcType;
typedef int Status;

typedef struct{
VerTexType vexs[MVNum]; //顶点表
ArcType arcs[MVNum][MVNum]; //邻接矩阵
int vexnum,arcnum; //图的当前点数和边数
}AMGraph;

int LocateVex(AMGraph G,VerTexType v){
int idx=-1;//返回-1就是没找到
for(int i=0;i<G.vexnum;++i){
if(G.vexs[i]==v) idx=i;
}
return idx;
}
Status CreatUDN(AMGraph &G){
cin>>G.vexnum>>G.arcnum;
for(int i=0;i<G.vexnum;++i){
cin>>G.vexs[i];
}
for(int i=0;i<G.vexnum;++i){
for(int j=0;j<G.vexnum;++j){
G.arcs[i][j]=MaxInt;
}
}
VerTexType v1,v2;
ArcType w;
for(int i=0;i<G.arcnum;++i){
cin>>v1>>v2>>w;
int idx1=LocateVex(G,v1),idx2=LocateVex(G,v2);
if(idx1==-1||idx2==-1){
cout<<"error!\n";
return ERROR;
}
G.arcs[idx1][idx2]=G.arcs[idx2][idx1]=w;
}
return OK;
}
bool visited[MVNum];
void initVis(){
for(int i=0;i<MVNum;++i){
visited[i]=false;
}
}
void DFS(AMGraph G,int v){
cout<<G.vexs[v]<<" ";
visited[v]=true;
for(int i=0;i<G.vexnum;++i){
if(G.arcs[v][i]!=MaxInt&&!visited[i]) DFS(G,i);
}
}
#define QElemType int
void BFS(AMGraph G,int v){
typedef struct{
QElemType *base;
int front,rear;
}SqQueue;
//初始化SqQueue
SqQueue Q;
Q.base=new QElemType[MVNum];
if(!Q.base) return;
Q.front=Q.rear=0;//头指针等于尾指针,队列为空

if((Q.rear+1)%MVNum==Q.front){
cout<<"队列满了!";
return ;
}else{
Q.base[Q.rear]=v;
cout<<G.vexs[Q.base[Q.rear]]<<" ";
visited[Q.base[Q.rear]]=true;
Q.rear=(Q.rear+1)%MVNum;
}
while(Q.rear!=Q.front){
int e=Q.base[Q.front];
Q.front=(Q.front+1)%MVNum;//出队
for(int i=0;i<G.vexnum;++i){
if(!visited[i]&&G.arcs[e][i]!=MaxInt){//入队
visited[i]=true;
if((Q.rear+1)%MVNum==Q.front){
cout<<"队列满了!";
return ;
}else{
Q.base[Q.rear]=i;
cout<<G.vexs[Q.base[Q.rear]]<<" ";
Q.rear=(Q.rear+1)%MVNum;
}
}
}
}
}
bool S[MVNum];//已求出最短路径的顶点集
int D[MVNum];
int Path[MVNum];
void ShortestPath_DIJ(AMGraph G,int v0){
//用Dijkstra算法求有向网
int n=G.vexnum;
int v;
for(v=0;v<n;++v){
S[v]=false;
D[v]=G.arcs[v0][v];
if(D[v]<MaxInt) Path[v]=v0;
else Path[v]=-1;
}
S[v0]=true;
D[v0]=0;

for(int i=1;i<n;++i){
int min=MaxInt;
for(int w=0;w<n;++w){
if(!S[w]&&D[w]<min){
v=w;
min=D[w];
}
}
S[v]=true;
for(int w=0;w<n;++w){
if(!S[w]&&(D[v]+G.arcs[v][w]<D[w])){
D[w]=D[v]+G.arcs[v][w];
Path[w]=v;
}
}
}
}
//****************下面是邻接表建图**********
typedef struct ArcNode{//边结点
int adjvex;
struct ArcNode *nextarc;
}ArcNode;

typedef struct VNode{//顶点信息
VerTexType data;
ArcNode *firstarc;
}VNode,AdjList[MVNum];

typedef struct{
AdjList vertices;
int vexnum,arcnum;
}ALGraph;

Status CreatUDG(ALGraph &G){
cin>>G.vexnum>>G.arcnum;
for(int i=0;i<G.vexnum;++i){
cin>>G.vertices[i].data;
G.vertices[i].firstarc=NULL;
}
for(int k=0;k<G.arcnum;++k){
int v1,v2;
cin>>v1>>v2;
int idx1,idx2;
for(int i=0;i<G.vexnum;++i){
if(G.vertices[i].data==v1){
idx1=i;
break;
}
}
for(int i=0;i<G.vexnum;++i){
if(G.vertices[i].data==v2){
idx2=i;
break;
}
}
ArcNode* p1=new ArcNode;
p1->adjvex=idx2;
p1->nextarc=G.vertices[idx1].firstarc;
G.vertices[idx1].firstarc=p1;
ArcNode* p2=new ArcNode;
p2->adjvex=idx1;
p2->nextarc=G.vertices[idx2].firstarc;
G.vertices[idx2].firstarc=p2;
}
return OK;
}
int main(){
/*测试样例
5 5
a b c d e
a b 1
a c 2
b d 3
c d 4
d e 5
*/
AMGraph G;//假设可能不联通
ALGraph GL;
CreatUDN(G);//生成无向图
initVis();//初始化visited数组
cout<<"DFS: ";
for(int i=0;i<G.vexnum;++i){
if(!visited[i]) DFS(G,i);//dfs
}
cout<<endl;
initVis();
cout<<"BFS: ";
for(int i=0;i<G.vexnum;++i){
if(!visited[i]) BFS(G,i);//dfs
}
cout<<endl;
ShortestPath_DIJ(G,0);
cout<<"源点为0的最短路径如下\n";
for(int i=1;i<G.vexnum;i++){
cout<<G.vexs[0]<<" -> "<<G.vexs[i]<<" ,length = "<<D[i]<<"\n";
}
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
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
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
#include<iostream>
using namespace std;
#define OK 1
#define OVERFLOW -1
#define ERROR 0
#define MAXSIZE 100
typedef int KeyType;
typedef struct{
KeyType key;
}ElemType;
typedef struct{
ElemType *R;
int length;
}SSTable;
void initSSTable(SSTable &ST){
ST.R=(ElemType *)malloc(sizeof(ElemType)*MAXSIZE);
ST.length=0;
for(int i=1;i<=100;i++){
ST.R[i].key=i;
ST.length++;
}
}
int Search_Bin(SSTable ST,KeyType key,int &cnt,int &idx){//Sequential Search Table
int low=1,high=ST.length;
while(low<=high){
cnt++;
int mid=(low+high)/2;
if(ST.R[mid].key==key){
idx=mid;
return OK;
}
if(ST.R[mid].key<key) low=mid+1;
else high=mid-1;
}
return ERROR;
}
/////// 二叉排序树部分
typedef struct{
KeyType key;
}treeElemType;
typedef struct BSTNode{
treeElemType data;
BSTNode *lchild,*rchild;
}BSTNode,*BSTree;
int InsertBST(BSTree &T,int num){
if(T){
if(T->data.key>=num) InsertBST(T->lchild,num);
else InsertBST(T->rchild,num);
}else{
BSTNode* S=new BSTNode;
S->data.key=num;
S->lchild=S->rchild=NULL;
T=S;
}
return OK;
}
BSTree SearchBST(BSTree T,KeyType key,int &cnt){
cnt++;
if(!T||T->data.key==key) {
return T;
}
else{
if(T->data.key<key) return SearchBST(T->rchild,key,cnt);
else return SearchBST(T->lchild,key,cnt);
}
}
void InOrderTraverse(BSTree T){
if(T){
InOrderTraverse(T->lchild);
cout<<T->data.key<<" ";
InOrderTraverse(T->rchild);
}
}
// int flag=true,last=0;//last设为比最小值还小的值
// bool InOrderTraverse1(BSTree T){//中序递归遍历
// if(T&&flag){
// InOrderTraverse1(T->lchild);
// if(T->data.key<=last){
// flag=false;//不是BST
// }
// last=T->data.key;//更新last
// InOrderTraverse1(T->rchild);
// }
// return flag;
// }

//////////////排序算法部分
typedef struct{
int *elem;
int length;
}SqList;
int InitList(SqList &L){
L.elem=new int[MAXSIZE];
if(!L.elem) exit(OVERFLOW);
L.length=0;
cout<<"输入待排序数据个数:";
int n,num;
cin>>n;
cout<<"输入每一个数:";
for(int i=0;i<n;i++){
cin>>num;
L.elem[i+1]=num;
L.length++;
}
return OK;
}
void TraverseList(SqList L){
cout<<"线性表数据为:";
for(int i=1;i<=L.length;i++){
cout<<L.elem[i]<<" ";
}
cout<<endl;
}
int Partition(SqList &L,int low,int high){
L.elem[0]=L.elem[low]; //将子表的第一个记录当作枢轴记录
while(low<high){
while(low<high&&L.elem[high]>=L.elem[0]) --high;
L.elem[low]=L.elem[high];
while(low<high&&L.elem[low]<=L.elem[0]) ++low;
L.elem[high]=L.elem[low];
}
L.elem[low]=L.elem[0];
return low;
}
void QSort(SqList &L,int low,int high){
if(low<high){
int pivotloc=Partition(L,low,high);
QSort(L,low,pivotloc-1);
QSort(L,pivotloc+1,high);
}
}
void QuickSort(SqList &L){
QSort(L,1,L.length);
}


void Merge(int R[],int T[],int low,int mid,int high){
int i=low,j=mid+1,k=low;
while(i<=mid&&j<=high){
if(R[i]<=R[j]) T[k++]=R[i++];
else T[k++]=R[j++];
}
while(i<=mid) T[k++]=R[i++];
while(j<=high) T[k++]=R[j++];
}
void MSort(int R[],int T[],int low,int high){
int *S=new int[MAXSIZE];
if(low==high) T[low]=R[low];
else{
int mid=(low+high)/2;
MSort(R,S,low,mid);
MSort(R,S,mid+1,high);
Merge(S,T,low,mid,high);
}
delete []S;
}
void MergeSort(SqList &L){
MSort(L.elem,L.elem,1,L.length);
}
int main(){

while(true){
SSTable ST;
BSTree T;
SqList L;
int key,cnt=0,idx=0,order=0,n,num;
cout<<"** 1710121058-李博 ********************\n";
cout<<"** 1.初始化顺序表,自动添加[1:100]一百个数据 **\n";
cout<<"** 2.显示数据表内容 **\n";
cout<<"** 3.输入你要查找的数并返回在线性表中的查找结果 **\n";
cout<<"** 4.初始化二叉排序树,并添加数据 **\n";
cout<<"** 5.显示二叉排序树的数据 **\n";
cout<<"** 6.输入你要查找的数并返回在二叉排序树中结点的指针 **\n";
cout<<"** 7.输入待排序数的个数和分别都是几 **\n";
cout<<"** 8.输出你输入的线性表 **\n";
cout<<"** 9,快速排序刚才的线性表 **\n";
cout<<"** 10,归并排序刚才的线性表 **\n";
cout<<"** -1,退出 **\n";

cout<<"****\n";
cout<<"输入命令:";
cin>>order;
if(order==-1) break;
switch(order){
case 1:
initSSTable(ST);//已经初始化进去100个数据[1,2,3,...,100],下标从1开始
break;
case 2:
for(int i=1;i<=ST.length;i++){
cout<<ST.R[i].key<<" ";
}
cout<<endl;
break;
case 3:
cout<<"请输入你要查找哪个数:";
cin>>key;
if(Search_Bin(ST,key,cnt,idx)){//如果没找到则返回ERROR并且idx=0
cout<<"查找成功,查找次数:"<<cnt<<",下标:"<<idx<<"\n";
}else cout<<"查找失败\n";
break;
case 4:
cout<<"你要在二叉排序树插入几个数:";
cin>>n;
cout<<"输入你要插入的所有数据";
for(int i=0;i<n;i++){
cin>>num;
InsertBST(T,num);
}
break;
case 5:
//中序遍历输出元素值
InOrderTraverse(T);
cout<<endl;
break;
case 6:
cout<<"请输入你要查找哪个数:";
cin>>key;
if(SearchBST(T,key,cnt)!=NULL){
cout<<"查找成功,查找次数:"<<cnt<<",指针为:"<<T<<"\n";
}else cout<<"查找失败\n";
break;
case 7:
InitList(L);
break;
case 8:
TraverseList(L);
break;
case 9:
QuickSort(L);
break;
case 10:
MergeSort(L);
break;
}
}
return 0;
}