数据结构实验报告_数据结构 主函数 功能菜单创建

实验报告一 顺序表和链表
（1）实验内容
1．随机产生或键盘输入一组元素，建立一个带头结点的单向链表（无序）。
2．遍历单向链表。
3．把单向链表中元素逆置（不允许申请新的结点空间）。
4．在单向链表中删除所有的偶数元素结点。
5．编写在非递减有序链表中插入一个元素使链表元素仍有序的函数，并利用该函数建立一个非递减有序单向链表。
6．利用算法5建立两个非递减有序单向链表，然后合并成一个非递增链表。
7．利用算法5建立两个非递减有序单向链表，然后合并成一个非递减链表。
8．利用算法1建立的链表，实现将其分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量利用已知的存储空间）。

• 9．采用单向链表实现一元多项式的存储并实现两个多项式相加并输出结果。
  10．在主函数中设计一个简单的菜单，分别调试上述算法。
  *11．综合训练：利用链表实现一个班级学生信息管理（数据录入、插入、删除、排序、查找等，并能够实现将数据存储到文件中）

1）顺序表实现基本操作
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 10
using namespace std;
typedef int Elemtype;
//抽象化元素类型，到时候可根据需要将int修改成其他的基本数据类型
typedef struct {
Elemtype data[MaxSize];
int length;
}Sqlist;
//1.构造新的顺序表L
//这种创建方法在逻辑上是不对的，因为数组的长度已经规定，不能无限制地输入数据元素
Sqlist createSqlist(){
Sqlist l;//length此时不为0，而是随机分配的一个数字
int x;
scanf ("%d",&x);
int i=0;
l.length=0;
while (x!=-999){
    l.data[i]=x;
    l.length++;
    i++;
    scanf("%d",&x);//勿忘重新读入数据
}
return l;
}
void displaySqlist(Sqlist &l){//加不加引用的区别？？
for (int i=0;i<l.length;i++){
    printf("%d ",l.data[i]);
}
printf("\n");
}
//初始化顺序表
void InitSqlist(Sqlist &l){
 l.length=0;
}
//插入：在第i个元素之前
void InsertSqlist(Sqlist &l,int i,Elemtype e){
//1.判断I的位置是否合理
if (i<1||i>l.length+1)//可以插在最后一个位置
    printf("positon error");
for (int j=l.length;j>i-1;j--){
    l.data[j]=l.data[j-1];
}
l.data[i-1]=e;
l.length++;
}

void readitemSqlist(Sqlist &l){
int x;
scanf ("%d",&x);
int i=0;
while (x!=-999&&l.length<=MaxSize){
    l.data[i]=x;
    i++;
    scanf ("%d",&x);
    l.length++;
}
}
//有返回值的插入方法
int InsertSqlist2(Sqlist &l,int i,Elemtype e){
//1.判断I的位置是否合理
if (i<1||i>l.length+1){
   printf("positon error");
   return 0;
}

for (int j=l.length;j>i-1;j--){
    l.data[j]=l.data[j-1];
}
l.data[i-1]=e;
l.length++;
return 1;
}
int deleteSqlist (Sqlist &l,int i,Elemtype &e){
//删除i之前的元素，回收到e中
if (i<1||i>l.length){
    printf("positon error");
    return 0;
}
e=l.data[i-1];
for (int j=i-1;j<l.length-1;j++){
    l.data[j]=l.data[j+1];
}
l.length--;
return 1;
}
int locateSqlist (Sqlist &l,Elemtype e){
for (int i=0;i<l.length;i++){
    if (l.data[i]==e)
        return i+1;//返回的是序号
}
printf("can not find it !");
return 0;
//另一种做法
//int i=l.length;
//while (i>=0&&l.data[i]!=x) i--;
//return i+1;
//if (i==-1)
//return 0;
}
int main()
{
   Sqlist l;
   InitSqlist(l);
   readitemSqlist(l);
   displaySqlist(l);
   Elemtype e=5;
   int i=locateSqlist(l,e);
   printf("%d",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
108
109
110
111
112
113
114
115

2）单链表实现基本操作
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;


    typedef int Elemtype;
    typedef struct node
    {
        Elemtype data;
        struct node *next;
    } node,*linklist;
    linklist creatlinklist()
    {
        //尾插法建立单链表
        linklist l,p,q;
        l=(linklist)malloc(sizeof(node));
        p=l;
        int x;
        scanf("%d",&x);
        while (x!=-999)
        {
            q=(linklist)malloc(sizeof(node));
            q->data=x;
            p->next=q;
            q->next=NULL;
            p=q;
            scanf("%d",&x);
        }
        return l;
    }
    void displaylinklist(linklist l)
    {
        linklist p=l->next;
        while (p!=NULL)
        {
            printf("%d ",p->data);
            p=p->next;
        }
        printf("\n");
    }
    void nizhilinklist(linklist &l)
    {
        linklist p,q;//p指向后面结点，q指向当前结点
        q=l;
        p=l->next;
        l->next=NULL;//解放头结点
        while(p!=NULL)
        {
            q=p;//q指向即将头插法的结点
            p=p->next;//保存后面的结点首地址；
            q->next=l->next;
            l-> next=q;
        }

    }
    void deletelinklist(linklist &l)
    {
        linklist p=l;
        //p指向待删除元素的前面的位置，必须要从L开始，不然第一个元素无法删除
        while (p!=NULL)
        {
            if(p->next==NULL)//如果最后一个元素是奇数要特别对待
                break;
            if (p->next->data%2==0)
            {
                p->next=p->next->next;
            }
            p=p->next;

        }
    }
    void insertlinklist(linklist &l)
    {
         Elemtype x;
        scanf("%d",&x);
        linklist p;
        linklist q;
        p=l;
        while (p->next!=NULL&&p->next->data < x)
        {
        p=p->next;
        }
        if (p->next!=NULL){
            q=(linklist )malloc(sizeof(node));
            q->data=x;
            q->next=p->next;
            p->next=q;
        }
        if (p->next==NULL)
        {
            p->next=q;
            q->next=NULL;
        }
    }
    void mergelinklist(linklist &la,linklist &lb,linklist &lc){
    //假设la与lb为非递减有序单向链表
    lc=la;
    linklist pa=la->next,pb=lb->next,pc=lc;
    lc->next=NULL;
    while (pa!=NULL&&pb!=NULL){
        if (pa->data > pb->data){
         pc->next=pb;
         pc=pb;
         pb=pb->next;
    }
     if (pa->data <= pb->data){
         pc->next=pa;
         pc=pa;
         pa=pa->next;
    }

    }
    if (pa!=NULL)
        pc->next=pa;
    if (pb!=NULL)
        pc->next=pb;
        free(lb);
        //free(la)??
        //这里判断条件如果用==，那么while循环出来的一定都满足该条件，所以要用不等于



    }
    void mergenizhilinklist(linklist &la,linklist &lb,linklist &lc){
    mergelinklist(la,lb,lc);
    nizhilinklist(lc);
    }
    linklist dividelinklist(linklist &l){
    linklist h=(linklist)malloc(sizeof(node));
    h->next=NULL;
    linklist p=l,q=h;
    while(p!=NULL){
            if(p->next==NULL)
            break;//最后为偶数
        if (p->next->data%2!=0){
            q->next=p->next;
            q=p->next;
            p->next=q->next;
            p=p->next;
        }
        p=p->next;
    }
    q->next=NULL;
    return h;
    //这里或许可以用头插法建立？？

    }
   //实现一元多项式
typedef struct {
float conf;
int expn;
}Elemtype;

typedef struct pnode{
Elemtype data;
struct pnode *next;
}pnode,*linklist;

linklist creatPolylist(){
linklist l=(linklist )malloc(sizeof(pnode));
linklist p=l,q;
float con;
int exp;
scanf ("%f %d",&con,&exp);

while (exp!=-1){
    q=(linklist )malloc(sizeof(pnode));
    (q->data).conf=con;
    (q->data).expn=exp;
    p->next=q;
    p=q;
    scanf ("%f %d",&con,&exp);
}
p->next=NULL;
return l ;
}
void displayPoly(linklist &l){
linklist p=l->next;
while (p!=NULL){
    printf("(%.2f %d)",((p->data).conf),((p->data).expn));
    p=p->next;
}
printf("\n");
}
void addPoly(linklist &la,linklist &lb){
linklist pa=la,pb=lb,qa,qb;
qa=pa->next;
qb=pb->next;
int sum;
while (qa!=NULL&&qb!=NULL){
if (qa->data.expn < qb->data.expn){
pa=qa;
qa=qa->next;
}else if(qa->data.expn = qb->data.expn){
sum=qa->data.conf + qb->data.conf;
if (sum!=0){
qa->data.conf=sum;
pa=qa;
qa=qa->next;
pb=qb->next;
free(qb);
qb=qb->next;//释放B链表中的重复系数结点，这样不占用任何多余空间。
}else {
    pa=qa->next;
    pb=qb->next;
    free(qa);
    free(qb);
    qa=pa->next;
    qb=pb->next;//两个结点都要释放

}
}else {
pa->next=qb;
qb->next=qa;
pa=qb;
qb=qb->next;//在la链表中插入B中的一个结点，仍旧保持Pa为Qa的前驱，qb后移
}
}
if(qb!=NULL)
qa->next=qb;
}


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

实验二 栈、队列

（1）实验内容
1．采用链式存储实现栈的初始化、入栈、出栈操作。
2．采用顺序存储实现栈的初始化、入栈、出栈操作。
3．采用链式存储实现队列的初始化、入队、出队操作。
4．采用顺序存储实现循环队列的初始化、入队、出队操作。
5．在主函数中设计一个简单的菜单，分别测试上述算法。
*6．综合训练:1)利用栈实现表达式求值算法。
2)利用栈实现迷宫求解。

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
#define OVERFLOW -2
using namespace std;
//顺序栈
typedef int Elemtype;
typedef struct {
Elemtype elem[MAXSIZE];
int top;
}SeqStack;
void initSeqStack(SeqStack &s){
s.top=-1;
}
int stackEmpty(SeqStack &s){
if (s.top==-1)
return 1;
return 0;//或者返回 表达式的真值return s.top==-1;
}
int push(SeqStack &s,Elemtype e){
if (s.top>=MAXSIZE-1)
return 0;
else {
s.top++;
s.elem[s.top]=e;
return 1;
}
}
int pop(SeqStack &s,Elemtype &e){
if (s.top==-1)
return 0;
else {
e=s.elem[s.top];
s.top--;
return 1;
}
}
int gettop(SeqStack &s,Elemtype &e){
if (s.top==-1)
return 0;
else {
e=s.elem[s.top];
return 1;
}
}
void display(SeqStack &s){
for (int i=0;i<=s.top;i++){
cout<<s.elem[i]<<" ";
}
cout<<endl;
}

//链栈
typedef struct node {
Elemtype data;
struct node *next;
}node,*linkstack;
void initLinkstack(linkstack &top){
top=NULL;//无头节点的链栈
}
int linkstackEmpty(linkstack &top){
return top==NULL;
}
int linkstackPush(linkstack &top,Elemtype e){
linkstack p=(linkstack )malloc (sizeof(node));
if (!p) exit(OVERFLOW);
p->data=e;
p->next=top;
top=p;
return 1;
}
int linkstackPop(linkstack &top,Elemtype &e){
e=top->data;
linkstack p=top;
top=top->next;
free(p);
return 1;
}
void getTop(linkstack &top,Elemtype &E){
E=top->data;
}
void displaylinkstack(linkstack &top){
linkstack p=top;
while (p){
printf ("%d ",p->data);
p=p->next;
}
printf ("\n");
}
//顺序循环队列
typedef int Elemtype;
typedef struct{
Elemtype data[MAXSIZE];
int rear,front;
}Seqqueue;
void initSeqqueue(Seqqueue &q){
q.rear=q.front=-1;
}
int emptySeqqueue(Seqqueue &q){
return q.rear==q.front;
}
int enSeqqueue(Seqqueue &q,Elemtype e){
    //先判断是否队满
    if ((q.rear+1)%MAXSIZE==q.front){
    printf ("full!\n");
    return 0;
    }
    q.rear=(q.rear+1)%MAXSIZE;
    q.data[q.rear]=e;
    return 1;
}
int deSeqqueue(Seqqueue &q,Elemtype &e){
if (emptySeqqueue(q)){
printf ("null!\n");
return 0;
}
q.front=(q.front+1)%MAXSIZE;
e=q.data[q.front];
return 1;
}
Elemtype getFront(Seqqueue &q){
if (emptySeqqueue(q)){
printf ("null!\n");
}
else {
Elemtype e;
q.front=(q.front+1)%MAXSIZE;
e=q.data[q.front];
return e;
}
}
int length(Seqqueue &q){
return (q.rear-q.front+MAXSIZE)%MAXSIZE;
}
void display(Seqqueue &q){
if (emptySeqqueue(q)){
printf ("null!\n");
}
else {
int i=(1+q.front)%MAXSIZE;
for (int j=0;j<length(q);j++){
printf ("%d ",q.data[i]);
i++;
}
printf ("\n");
}
}


//链队列
typedef int Elemtype;
typedef struct qnode {
Elemtype data;
struct qnode *next;
}qnode,*Queueptr;
typedef struct {
Queueptr front ;
Queueptr rear;
}linkQueue;
int  initQueue(linkQueue &q){
Queueptr lq=(Queueptr)malloc(sizeof(qnode));
if (!lq) exit(OVERFLOW);
lq->next=NULL;
q.front=q.rear=lq;
}
int isempty(linkQueue q){
return q.front==q.rear;
}
int enterQueue(linkQueue &q,Elemtype e){
Queueptr p=(Queueptr)malloc(sizeof(qnode));
if (!p) exit(OVERFLOW);
p->data=e;
p->next=q.rear->next;
q.rear->next=p;
q.rear=p;
return 1;
}
int deQueue(linkQueue &q,Elemtype &e){
    //出队依旧要判空，入队不需要判满了
    if (q.rear==q.front){
    printf("null\n");
    return 0;
    }
Queueptr p=q.front->next;
e=p->data;
q.front->next=p->next;
//这里要特别注意如果链表中唯一的元素要出队，尾指针必须要重新指向头结点，不然丢失该指针了
if (q.front->next==NULL){//或者q.rear==p;
q.rear=q.front;
}
free(p);
return 1;
}
void display(linkQueue &q){
Queueptr p=q.front->next;
while (p){
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}
int main()
{
    SeqStack s;
    Elemtype e;
    linkstack top;
    Seqqueue q;
    linkQueue Q;

    cout<<"---------------------------------------------------"<<endl;
    cout<<"1.采用顺序存储实现栈的初始化、入栈、出栈操作"<<endl;
    cout<<"2.采用链式存储实现栈的初始化、入栈、出栈操作"<<endl;
    cout<<"3.采用顺序存储实现队列的初始化、入队、出队操作"<<endl;
    cout<<"4.采用链式存储实现循环队列的初始化、入队、出队操作"<<endl;
    cout<<"---------------------------------------------------"<<endl;
    int x,i;
    cout<<"请输入您的选择！"<<endl;
    while (cin>>x){
    switch(x){
    case 1:{
    initSeqStack(s);
    cout<<"初始化顺序栈成功！"<<endl;
    cout<<"请输入压栈的内容！"<<endl;
    cin>>i;
    while (i!=-999){
    push(s,i);
    cin>>i;
    }
    cout<<"压栈成功！显示栈内数字！"<<endl;
    display(s);
    cout<<"获取栈顶元素！"<<endl;
    gettop(s,e);
    printf ("%d\n",e);
    cout<<"弹栈！"<<endl;
    while (s.top>0){
    pop(s,e);
    cout<<"弹出元素："<<e<<" ";
    }
    cout<<endl;
    cout<<"显示栈内数字！"<<endl;
    display(s);
    break;
    }
    case 2:
    initLinkstack(top);
    cout<<"初始化链栈成功！"<<endl;
    cout<<"请输入压栈的内容！"<<endl;
    cin>>i;
    while (i!=-999){
    linkstackPush(top,i);
    cin>>i;
    }

    cout<<"压栈成功！显示栈内数字！"<<endl;
    displaylinkstack(top);
    cout<<"获取栈顶元素！"<<endl;
    getTop(top,e);
    printf ("%d\n",e);
    while (top){
    linkstackPop(top,e);
    cout<<"弹出元素："<<e<<" ";
    }
    cout<<endl;
    cout<<"显示栈内数字！"<<endl;
    displaylinkstack(top);
    break;
    case 3:
    initSeqqueue(q);
    cout<<"初始化顺序队列成功！"<<endl;
    cout<<"请输入进队的内容！"<<endl;
    cin>>i;
    while (i!=-999){
    enSeqqueue(q,i);
    cin>>i;
    }
    cout<<"进队成功！显示队内数字！"<<endl;
    display(q);
    cout<<"返回队头元素！"<<endl;
    e=getFront(q);
    cout<<e<<endl;
    while (!emptySeqqueue(q)){
    deSeqqueue(q,e);
    cout<<"出队元素"<<e<<" ";
    }
    cout<<endl;
    cout<<"显示队内数字"<<endl;
    display(q);
    break;
    case 4:
    initQueue(Q);
    cout<<"初始化链队列成功！"<<endl;
    cout<<"请输入进队的内容！"<<endl;
    cin>>i;
    while (i!=-999){
    enterQueue(Q,i);
    cin>>i;
    }
    cout<<"进队成功！显示队内数字！"<<endl;
    display(Q);

    while (!isempty(Q)){
    deQueue(Q,e);
    cout<<"出队元素"<<e<<" ";
    }
    cout<<endl;
    cout<<"显示队内数字"<<endl;
    display(Q);
    break;
    }
    cout<<"请输入您的选择！"<<endl;
    }

    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
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
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316

实验报告3 树
1）顺序二叉树

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string>
#include <string.h>
#include <math.h>
#define MAXSIZE 20
//顺序二叉树
using namespace std;
typedef int Elemtype;
typedef struct SqBinode
{
    Elemtype data[MAXSIZE];
} SqBinode,SqBiTree;
typedef struct
{
    int level;//第几层
    int order;//本层序号，(level,order)类似于（i，j）
} position;
void initBiTree(SqBiTree &bt)
{
    for (int i=0; i<MAXSIZE; i++)
    {
        bt.data[i]=NULL;
    }
}
int createBiTree(SqBiTree &bt)
{
    cout<<"无节点处请输入0,输入完毕请输入-999"<<endl;
    int i=0,n;
    cin>>n;
    while (n!=-999&&i<=MAXSIZE)
    {
        bt.data[i]=n;
        i++;
        if (i!=0&&bt.data[(i+1)/2-1]==NULL&&bt.data[i]!=NULL)
        {
            cout<<"存在双亲为空且自身为空且不为根节点的点！"<<endl;
            return 0;
        }
        cin>>n;

    }

    if (i>MAXSIZE)
        return 0;
    return 1;
}
int BiTreeEmpty(SqBiTree bt)
{
    if (bt.data[0]==NULL)
        return 1;
    else
        return 0;
}
int BiTreeDepth(SqBiTree bt)
{
    int n=0,i=0;//N为节点个数
   for (i=0;i<MAXSIZE-1;i++)
    {
        if (bt.data[i]!=NULL)
            n++;

    }
    int k=0;
    do
    {
        k++;
    }
    while (pow(2,k-1)<=n);
    return k-1;
}

Elemtype Root(SqBiTree bt)
{
    if (bt.data[0])
        return bt.data[0];
    else
        return 0;
}
void initPosition(position &p,int a,int b)
{
    p.level=a;
    p.order=b;
}
void Value(SqBiTree bt,Elemtype &e,position p)
{
    //根据E的位置P找到它
    int n=pow(2,p.level-1)+p.order-2;
    e=bt.data[n];
}

void Assign(SqBiTree &bt,position &p,Elemtype e)
{
    int x=pow(2,p.level-1)+p.order-2;
    bt.data[x]=e;
}

void print(SqBiTree bt)
{
    int i,j,k=0;
    for (i=1;i<=BiTreeDepth(bt); i++)
    {
        cout<<"第"<<i<<"层";
        for (j=1; j<=pow(2,i-1); j++)
        {
            if (bt.data[k]!=NULL)
                cout<<"("<<j<<","<<bt.data[k]<<") ";
            k++;
        }
        cout<<endl;
    }
}
void valueP(int i,int j,position &p)
{
    p.level=i;
    p.order=j;
}

int Parent(SqBiTree &bt,Elemtype e)
{
    if (bt.data[0]==e)
        return NULL;
    int i=1;
    while (bt.data[i]!=e && i<=MAXSIZE-1) i++;
    return bt.data[(i+1)/2-1];
}
int LeftChild(SqBiTree &bt,Elemtype e)
{
//1.叶子结点无左孩子 2.非叶子结点的左孩子是2*i
    int i=0;
    while (bt.data[i]!=e && i<=MAXSIZE-1) i++;
//循环停止时应当是找到了值为E的结点，但不知道是叶子节点还是非叶子
    if (bt.data[2*i+1]!=NULL)
        return bt.data[2*i+1];
    else
        return NULL;
}
int RightChild(SqBiTree &bt,Elemtype e)
{
//1.叶子结点无左孩子 2.非叶子结点的左孩子是2*i
    int i=0;
    while (bt.data[i]!=e && i<=MAXSIZE-1) i++;
//循环停止时应当是找到了值为E的结点，但不知道是叶子节点还是非叶子
    if (bt.data[2*i+2]!=NULL)
        return bt.data[2*i+2];
    else
        return NULL;
}

int LeftSibling(SqBiTree &bt,Elemtype e)
{
    int i=0;
    if (!bt.data[0]) return NULL;//空树不用查找
    if (bt.data[0]==e) return NULL;//根节点没有左兄弟
    while (bt.data[i]!=e && i<=MAXSIZE-1) i++;
//1.左兄弟为-1 2. 为最左侧的一列，没有左兄弟
    if (i%2==0) return bt.data[i-1];//序号为偶节点才有左兄弟
    else return NULL;
}
int RightSibling(SqBiTree &bt,Elemtype e)
{
    int i=0;
    if (!bt.data[0]) return NULL;//空树不用查找
    if (bt.data[0]==e) return NULL;//根节点没有左兄弟
    while (bt.data[i]!=e && i<=MAXSIZE-1) i++;
//1.左兄弟为-1 2. 为最左侧的一列，没有左兄弟
    if (i%2!=0) return bt.data[i+1];//序号为偶节点才有左兄弟
    else return NULL;
}

void Move(SqBiTree &bt,int k,SqBiTree &q,int g)
{
    if (bt.data[2*k+1]!=NULL) //左孩子不空
        Move(bt,2*k+1,q,2*g+1);
    if (bt.data[2*k+2]!=NULL)//右孩子不空
        Move(bt,2*k+2,q,2*g+2);
    q.data[g]=bt.data[k];
    bt.data[k]=NULL;
}

int InsertChild(SqBiTree &bt,Elemtype e,int LR,SqBiTree &c)
{
//1.找到E所在结点的序号
    int i =0;
    while (bt.data[i]!=e &&i<=MAXSIZE-1 ) i++;
    int k=2*i+LR+1;//得到E结点的LR孩子的序号
    if (bt.data[k])//如果LR结点存在，需要转移到C的右子树,也就是K结点的右子树
        Move(bt,k,bt,2*k+2);
    Move(c,0,bt,k);
    return 1;
}
void del(SqBiTree &bt ,int k)
{
    //删除bt的k结点作为根结点的非空树
    if (!bt.data[2*k+1])//左子树非空
        del(bt,2*k+1);
    if (!bt.data[2*k+2])
        del(bt,2*k+2);
    bt.data[k]=NULL;

}
int DeleteChild(SqBiTree &bt,Elemtype e,int lr)
{
    //删除e元素对应的左或右子树
    //1 find the number of e
    int i=0;
    while (bt.data[i]!=e &&i<=MAXSIZE-1) i++;
    //2 找到要删除的左或右子树
    int k =2*i+1+lr;
    if (bt.data[k]!=NULL) //非空则删除
    del(bt,k);
    else
    {
        cout<<"不存在左或右子树，无法删除"<<endl;
        return 0;
    }
}
void PreOrder(SqBiTree &bt ,int i)
{
    cout<<bt.data[i]<<" ";
    if (bt.data[2*i+1])//左子树非空
    PreOrder(bt,2*i+1);
    if (bt.data[2*i+2])//右子树非空
    PreOrder(bt,2*i+2);

}
int PreOrderTraverse(SqBiTree &bt)
{
    int i=0;
    if (bt.data[i])
    PreOrder(bt,i);//遍历左子树
    else
    {
        cout<<"此树为空，不能遍历"<<endl;
        return 0;
    }
    return 1;
}
void InOrder(SqBiTree &bt ,int i)
{

    if (bt.data[2*i+1])//左子树非空
    PreOrder(bt,2*i+1);
    cout<<bt.data[i]<<" ";
    if (bt.data[2*i+2])//右子树非空
    PreOrder(bt,2*i+2);

}
int InOrderTraverse(SqBiTree &bt)
{
    int i=0;
    if (bt.data[i])
    InOrder(bt,i);//遍历左子树
    else
    {
        cout<<"此树为空，不能遍历"<<endl;
        return 0;
    }
    return 1;
}
void PostOrder(SqBiTree &bt ,int i)
{

    if (bt.data[2*i+1])//左子树非空
    PostOrder(bt,2*i+1);
    if (bt.data[2*i+2])//右子树非空
    PostOrder(bt,2*i+2);
     cout<<bt.data[i]<<" ";

}
int PostOrderTraverse(SqBiTree &bt)
{
    int i=0;
    if (bt.data[i])
    PostOrder(bt,i);//遍历左子树
    else
    {
        cout<<"此树为空，不能遍历"<<endl;
        return 0;
    }
    return 1;
}
int main()
{
    cout<<"---顺序二叉树的基本操作实现 twomeng---"<<endl;
    cout<<"--------------------------------------"<<endl;
    cout<<"1 InsertChild()"<<endl;
    cout<<"2 DeleteChild()"<<endl;
    cout<<"3 PreOrderTraverse()"<<endl;
    cout<<"4 InOrderTraverse()"<<endl;
    cout<<"5 PostOrderTraverse()"<<endl;
    cout<<"6 Parent()"<<endl;
    cout<<"7 LeftChild()"<<endl;
    cout<<"8 RightChild()"<<endl;
    cout<<"9 leftSibling()"<<endl;
    cout<<"10 RightSibling()"<<endl;
    cout<<"11 Root()"<<endl;
    cout<<"12 Value()"<<endl;
    cout<<"13 Assign()"<<endl;
    cout<<"--------------------------------------"<<endl;
ll1:cout<<"请输入您选择的函数序号:)"<<endl;
    int number;
    cin>>number;
    SqBiTree bt;
    initBiTree(bt);
    createBiTree(bt);//创建一个可以公用的二叉树bt
    Elemtype e;position p;
    switch(number){
case 1:
    SqBiTree c;
    initBiTree(c);
    createBiTree(c);
    InsertChild(bt,3,1,c);
    print(bt);
    break;
case 2:
    DeleteChild(bt,3,1);
    print(bt);
    break;
case 3:
    PreOrderTraverse(bt);
    break;
case 4:
    InOrderTraverse(bt);
    break;
case 5:
    PostOrderTraverse(bt);
    break;
case 6:
    cout<<"输入E的值"<<endl;
    cin>>e;
    cout<<Parent(bt,e);
    break;
case 7:
    cout<<"输入E的值"<<endl;
    cin>>e;
    cout<<LeftChild(bt,e);
    break;
case 8:
    cout<<"输入E的值"<<endl;
    cin>>e;
    cout<<RightChild(bt,e);
    break;
case 9:
    cout<<"输入E的值"<<endl;
    cin>>e;
    cout<<LeftSibling(bt,e);
    break;
case 10:
    cout<<"输入E的值"<<endl;
    cin>>e;
    cout<<RightSibling(bt,e);
    break;
case 11:
    cout<<Root(bt);
    break;
case 12:
    cout<<"请输入P的位置(level,order)"<<endl;
    int a,b;
    cin>>a>>b;
    initPosition(p,a,b);
    Value(bt,e,p);
    cout<<e<<endl;
    break;
case 13:
    cout<<"请输入P的位置(level,order)和E的值"<<endl;
    cin>>a>>b>>e;
    initPosition(p,a,b);
    Assign(bt,p,e);
    print(bt);
    break;
    }

    cout<<"您是否想要继续调用函数？yes/no"<<endl;
    string s;cin>>s;
    if (!s.compare("yes"))
    goto ll1;
    else
    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
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
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382

链式二叉树
1.实验内容
1．输入字符序列，建立二叉链表。 1
2．中序遍历二叉树:递归算法。3
3．中序遍历二叉树:非递归算法。（最好也能实现先序，后序非递归算法）4
4．求二叉树的高度 。1
5．求二叉树的叶子个数。1
*6．将二叉链表视为森林的孩子兄弟链表，计算森林中叶子个数。1
*7．建立中序线索二叉树，并实现中序遍历。1
8．借助队列实现二叉树的层次遍历。1
9．在主函数中设计一个简单的菜单，分别调试上述算法。1
*10．综合训练：为N个权值设计哈夫曼编码。

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string>
#include <string.h>
#include <math.h>
#define MAXSIZE 10
//链式二叉树
using namespace std;
typedef char Elemtype;
typedef struct BiTNode{
Elemtype data;
struct BiTNode *left,*right;
}BiTNode,*BiTree;

void InitBiTree(BiTree &bt)
{
    bt=NULL;//构造空的二叉树
}
void CreateBiTree(BiTree &bt)
{
    Elemtype e;
    scanf("%c",&e);
    if (e==' ')
    {
        bt=NULL;//如果输入空格则将该结点置空
    }
    else
    {
        bt=(BiTree)malloc(sizeof(BiTNode));
        bt->data=e;
        CreateBiTree(bt->left);
        CreateBiTree(bt->right);
    }
}
void PreOrderTraverse(BiTree &bt)
{
    if (bt!=NULL)
    {
    printf("%c",bt->data);
    PreOrderTraverse(bt->left);
    PreOrderTraverse(bt->right);
    }

}

void InOrderTraverse(BiTree &bt)
{
    if (bt)//如果是空则不用遍历左右子树，如果不空则遍历
    {
        InOrderTraverse(bt->left);
        printf("%c",bt->data);
        InOrderTraverse(bt->right);
    }
}
void PostOrderTraverse(BiTree &bt )
{
    if (bt)
    {
        PostOrderTraverse(bt->left);
        PostOrderTraverse(bt->right);
        printf("%c",bt->data);
    }
}
void LevelOrderTraverse(BiTree &bt)
{
    BiTree q[MAXSIZE];//指针数组
    int front,rear;
    //初始化队列
    front=rear=-1;
    if (bt)
    {
        rear=(rear+1)%MAXSIZE;
        q[rear]=bt;//安置根节点
        //不断循环，直到队空为止
        while (front!=rear)
        {
            //如果队不空，队头出队
            front=(front+1)%MAXSIZE;
            printf("%c",q[front]->data);
            //左右孩子不空则入队
            if (q[front]->left)
            {
                rear=(rear+1)%MAXSIZE;
                q[rear]=q[front]->left;//安置根节点
            }
             if (q[front]->right)
            {
                rear=(rear+1)%MAXSIZE;
                q[rear]=q[front]->right;//安置根节点
            }
        }


    }
}
int BiTreeEmpty(BiTree &bt)
{
    if (!bt)
    return 1;
}

int BiTreeDepth(BiTree &bt)
{
    int depth=0;
    int depthL,depthR;
    if (!bt)
    depth=0;
    else
    {
        depthL=BiTreeDepth(bt->left);
        depthR=BiTreeDepth(bt->right);
        depth=1+(depthL>depthR?depthL:depthR);

    }
    return depth;
}
Elemtype Root (BiTree &bt)
{
    if (bt)
    {
        return bt->data;
    }
    else
    return 0;
}
Elemtype Value(BiTree &p)
{
    //P是二叉树中某个节点
    return p->data;
}
void Assign(BiTree &bt,Elemtype e)
{
    bt->data=e;
}
Elemtype Parent(BiTree &bt,Elemtype e)
{
    //e为二叉树bt中的某个节点，输出他的双亲
    BiTree q[MAXSIZE],p;
    int rear,front;
    rear=front =-1 ;

    if (bt)
    {
        rear=(rear+1)%MAXSIZE;
        q[rear]=bt;//根节点入队

        while (rear!=front)
        {
            //如果队不空则队头出队
            front=(front+1)%MAXSIZE;
            p=q[front];
            if (p && p->left->data ==e || p && p->right->data == e )
            {
                //如果P本身不空并且有一个孩子等于E,则返回该双亲节点的值
                return p->data;
            }
            //说明这次没有找到和E相等的节点，则把左孩子和右孩子送入队列
            if (p->left)
            {
              rear=(rear+1)%MAXSIZE;
              q[rear]=p->left;
            }
            if (p->right)
            {
              rear=(rear+1)%MAXSIZE;
              q[rear]=p->right;
            }
        }
    }
}
BiTree findE(BiTree &bt,Elemtype e)
{
    BiTree q[MAXSIZE],p;
    int rear,front;
    rear=front=-1;
    if (bt)
    {
        rear=(rear+1)%MAXSIZE;
        q[rear]=bt;//根入队

        while (front!=rear)
        {
            front=(front+1)%MAXSIZE;
            p=q[front];//取出队头元素
            if (p->data == e)
            {
                return p;
            }
            if (p->left)
            {
               rear=(rear+1)%MAXSIZE;
               q[rear]=p->left;//left child enqueue
            }
            if (p->right)
            {
               rear=(rear+1)%MAXSIZE;
               q[rear]=p->right;//left child enqueue
            }
        }
    }
}
Elemtype LeftChild( BiTree &bt,Elemtype e)
{
    //找到指向E的指针
    BiTree p=findE(bt,e);
    if (p &&p->left )
    {//P不为空并且左孩子不为空
        return p->left->data;
    }
    else
    return 0;

}
Elemtype RightChild( BiTree &bt,Elemtype e)
{
    //找到指向E的指针
    BiTree p=findE(bt,e);
    if (p &&p->right )
    {//P不为空并且左孩子不为空
        return p->right->data;
    }
    else
    return 0;

}
BiTree findP(BiTree &bt,Elemtype e)
{
    //e为二叉树bt中的某个节点，输出他的双亲
    BiTree q[MAXSIZE],p;
    int rear,front;
    rear=front =-1 ;

    if (bt)
    {
        rear=(rear+1)%MAXSIZE;
        q[rear]=bt;//根节点入队

        while (rear!=front)
        {
            //如果队不空则队头出队
            front=(front+1)%MAXSIZE;
            p=q[front];
            if (p && p->left->data ==e || p && p->right->data == e )
            {
                //如果P本身不空并且有一个孩子等于E,则返回该双亲节点的值
                return p;
            }
            //说明这次没有找到和E相等的节点，则把左孩子和右孩子送入队列
            if (p->left)
            {
              rear=(rear+1)%MAXSIZE;
              q[rear]=p->left;
            }
            if (p->right)
            {
              rear=(rear+1)%MAXSIZE;
              q[rear]=p->right;
            }
        }
    }
}
Elemtype LeftSibling(BiTree &bt,Elemtype e)
{
    BiTree parent = findP(bt,e);//找到E元素的双亲指针

    if (parent->left)
    {
        return parent->left->data;
    }
}

Elemtype RightSibling(BiTree &bt,Elemtype e)
{
    BiTree parent = findP(bt,e);//找到E元素的双亲指针
    if (parent->right)
    {
        return parent->right->data;
    }
}
int  InsertChild(BiTree &p ,int lr,BiTree &c)
{//插入更简单了！！
    if (p)
    {
        if (lr==0)//把C移到P的左子树上
        {
            c->right=p->left;
            p->left=c;
        }else
        {
          c->right=p->right;
          p->right=c;
        }
        return 1;
    }
    else
    return 0;//P为空
}
void clearBiTree(BiTree &bt)
{
    //同样用递归！
    if (bt)
    {
        if (bt->left)
            clearBiTree(bt->left);
        if (bt->right)
            clearBiTree(bt->right);
        free(bt);
        bt=NULL;
    }
}
void  DeleteChild(BiTree &p,int LR)
{
    // 初始条件: 二叉树T存在,p指向T中某个结点,LR为0或1
   // 操作结果: 根据LR为0或1,删除T中p所指结点的左或右子树
   if (p)
   {
     if (LR == 1)
   {
       clearBiTree(p->left);
   }else
   {
       clearBiTree(p->right);
   }
   }

}

//非递归实现pre/in/post 遍历二叉树
//使用栈实现中序遍历


typedef BiTree Elemtype1;
typedef struct {
Elemtype1 elem[MAXSIZE];
int top;
}SeqStack;
void initSeqStack(SeqStack &s){
s.top=-1;
}
int stackEmpty(SeqStack &s){
if (s.top==-1)
return 1;
return 0;//或者返回 表达式的真值return s.top==-1;
}
int push(SeqStack &s,Elemtype1 e){
if (s.top>=MAXSIZE-1)
return 0;
else {
s.top++;
s.elem[s.top]=e;
return 1;
}
}
int pop(SeqStack &s,Elemtype1 &e){
if (s.top==-1)
return 0;
else {
e=s.elem[s.top];
s.top--;
return 1;
}
}
int gettop(SeqStack &s,Elemtype1 &e){
if (s.top==-1)
return 0;
else {
e=s.elem[s.top];
return 1;
}
}
//中序遍历非递归算法
void InOrderTraverse2(BiTree &bt)
{
    //精髓是把每个结点的地址存入栈中，通过push & pop实现过程
    SeqStack s;
    initSeqStack(s);
    BiTree p=bt;
    while (p!=NULL || !stackEmpty(s))
    {
        //当且仅当两者都空时结束循环
        if (p)
        {
            push(s,p);
            p=p->left;
        }
        else
        {
            pop(s,p);//弹回根节点
            printf("%c ",p->data);//第二次回到根节点时才打印输出
            p=p->right;

        }
    }

}

//先序遍历非递归算法
void PreOrderTraverse2(BiTree p)
{
    //这里不加&即为形参，便不用定义新的变量作为移动的指针了
    SeqStack s;
    initSeqStack(s);
    do
    {
        if (p)
        {
          printf("%c ",p->data);
          push(s,p);
          p=p->left;
        }
        else
        {
        pop(s,p);
        p=p->right;
        }

    }while (p || !stackEmpty(s));

}

//后序遍历非递归算法
void PostOrderTraverse2(BiTree p)
{
    struct
    {
        BiTree pp;//pointer
        int tag;//标记位
    }s[MAXSIZE];//定义一个结构体数组,即为一个栈s
//这里struct之前不能加typedef ,因为s[]是结构体数组而不是别名

    int top=0;//栈顶指针

    while ( p || top>0)
    {
        while (p)//一直走到最左边
        {
            top++;
            s[top].pp=p;
            s[top].tag=0;
            p=p->left;
        }
        if (top>0)
        {
            if (s[top].tag == 0)
            {
                //如果栈顶元素标志位为0，即为第二次遇到该结点元素
                s[top].tag=1;
                p=s[top].pp;
                p=p->right;//继续向右孩子深入
            }
            else
            {
                p=s[top].pp;
                printf("%c ",p->data);//如果是第二次遇到该节点则输出
                top--;
                p=NULL;//不用往深处走了，直接退栈继续循环
            }
        }
    }
}
//找到叶子结点个数，左右孩子都空
int findleaf(BiTree p,int &count1)
{

    if (p)
    {
        if ( !p->left &&!p->right)
            count1++;
        findleaf(p->left,count1);
        findleaf(p->right,count1);
    }
}
int findrightleaf(BiTree p,int &count1)
{

    if (p)
    {
        if (!p->right)
            count1++;
        findleaf(p->left,count1);
        findleaf(p->right,count1);
    }
}
void PreOrderfindall(BiTree &bt,int &count2)
{
    if (bt!=NULL)
    {
    count2++;
    PreOrderfindall(bt->left,count2);
    PreOrderfindall(bt->right,count2);
    }

}

int findleafinforest(BiTree &bt)
{
    //假设bt代表一个森林，求森林中叶子的个数
    //利用理论：假设森林中有N个非终端结点，则二叉树中右指针域为空的结点个数为N+1
    if (bt)
    {
        int count1 = 0;
        findrightleaf(bt,count1);
        //count即为二叉树中右指针域为空的结点的个数
        int count2=0;
        PreOrderfindall(bt,count2);
        //count2即为二叉树中所有节点的个数，也就是森林总结点个数
        return (count2-count1+1);
    }
    else
        return 0;
}
//建立中序线索二叉树并遍历
typedef enum PointerTag {link=0,thread=1};//link=0 指针，thread=1 线索
typedef struct BithrNode{
Elemtype data;
struct BithrNode *left,*right;
PointerTag ltag,rtag;
}BithrNode,*BithrTree;

int InOrderThreading(BithrTree &thrt,BithrTree bt)
{
    void Inthreading(BithrTree &p,BithrTree &pre);
    //将普通二叉树线索化成thrt
    //1.建立头结点
    thrt = (BithrTree)malloc(sizeof(BithrNode));
    BithrTree pre;
    thrt->right=thrt;
    thrt->ltag=link;
    thrt->rtag=thread;
    if (!bt)
        thrt->left=thrt;
    else
    {
        thrt->left = bt;
        pre=thrt;//前驱指针指向头结点
        Inthreading(bt,pre);
        //线索化二叉树
        pre->right=thrt;
        pre->rtag=thread;
        thrt->right=pre;
        //线索化最后pre指向树中最后一个结点，进行最后的处理：连接树中最后一个结点与头结点，形成循环的线索树

    }
}
void Inthreading(BithrTree &p,BithrTree &pre)
{
    if (p)
    {
        Inthreading(p->left,pre);
        if (!p->left)//P的左孩子为空
        {
            p->ltag=thread;
            p->left=pre;
        }
        if (!pre->right)//Pre的右孩子为空
        {
           pre->rtag=thread;
           pre->right=p;
        }
        pre=p;
        Inthreading(p->right,pre);
    }
}
//遍历线索二叉树
int InOrderTraverseThrtree(BithrTree &thrt)
{
    BithrTree p=thrt->left;
    while (p != thrt)
    {
        //线索树不为空时
        while(p && p->ltag !=thread)
        {
            p=p->left;
        }
        printf("%c",p->data);
        while(p->rtag == thread && p->right != thrt)
        {
            //如果p->right==T,则不用继续往右走
            p=p->right;
            printf("%c",p->data);
        }
        p=p->right;//没有右线索，只有右孩子

    }
}
void CreateBithrTree(BithrTree &bt)
{
    Elemtype e;
    scanf("%c",&e);
    if (e==' ')
    {
        bt=NULL;//如果输入空格则将该结点置空
    }
    else
    {
        bt=(BithrTree)malloc(sizeof(BithrNode));
        bt->data=e;
        CreateBithrTree(bt->left);
        CreateBithrTree(bt->right);
    }
}
int main()
{

    cout<<"---二叉树的基本操作实现 twomeng---"<<endl;
    cout<<"--------------------------------------"<<endl;
    cout<<"1 InsertChild()"<<endl;
    cout<<"2 DeleteChild()"<<endl;
    cout<<"3 PreOrderTraverse()"<<endl;
    cout<<"4 InOrderTraverse()"<<endl;
    cout<<"5 PostOrderTraverse()"<<endl;
    cout<<"6 Parent()"<<endl;
    cout<<"7 LeftChild()"<<endl;
    cout<<"8 RightChild()"<<endl;
    cout<<"9 leftSibling()"<<endl;
    cout<<"10 RightSibling()"<<endl;
    cout<<"11 Root()"<<endl;
    cout<<"12 Value()"<<endl;
    cout<<"13 Assign()"<<endl;
    cout<<"14 LevelOrderTraverse()"<<endl;
    cout<<"15 BiTreeDepth()"<<endl;
    cout<<"16 findleaf()"<<endl;
    cout<<"17 PreOrderTraverse2()"<<endl;
    cout<<"18 InOrderTraverse2()"<<endl;
    cout<<"19 PostOrderTraverse2()"<<endl;
    cout<<"20 findleafinforest()"<<endl;
    cout<<"21 线索化二叉树并中序遍历输出"<<endl;
    cout<<"--------------------------------------"<<endl;

ll1:cout<<"请输入您选择的函数序号:)"<<endl;
    int number;
    cin>>number;


    BiTree bt,p;
    InitBiTree(bt);
    Elemtype e;int count3 = 0;
    cout<<"请按照先序顺序输入一棵树！没有结点的地方请输入空格"<<endl;
    fflush(stdin);
    CreateBiTree(bt);//创建一个可以公用的二叉树bt;
    switch(number)
{
case 1:
    PreOrderTraverse(bt);
    BiTree c;
    InitBiTree(c);
    cout<<"请按照先序顺序输入一棵Insert树！没有结点的地方请输入空格"<<endl;
    fflush(stdin);
    CreateBiTree(c);
    LevelOrderTraverse(c);
    cout<<"输入完毕！"<<endl;
    cout<<"如果您想插入到左子树，输入0；如果您想插入到右子树，输入1 "<<endl;
    int x;cin>>x;
    InsertChild(bt,x,c);
    PreOrderTraverse(bt);
    break;
case 2:
    PreOrderTraverse(bt);
    cout<<endl;
    cout<<"删除左子树，请输入1；删除右子树，请输入0"<<endl;
    cin>>x;
    DeleteChild(bt,x);
    PreOrderTraverse(bt);
    break;
case 3:
    PreOrderTraverse(bt);
    break;
case 4:
    InOrderTraverse(bt);
    break;
case 5:
    PostOrderTraverse(bt);
    break;
case 6:
    char ch;
    cout<<"请输入您要寻找的节点数值"<<endl;
    cin>>ch;
    cout<<Parent(bt,ch);
    break;
case 7:
    cout<<"输入E的值"<<endl;
    cin>>e;
    cout<<LeftChild(bt,e);
    break;
case 8:
    cout<<"输入E的值"<<endl;
    cin>>e;
    cout<<RightChild(bt,e);
    break;
case 9:
    cout<<"输入E的值"<<endl;
    cin>>e;
    cout<<LeftSibling(bt,e);
    break;
case 10:
    cout<<"输入E的值"<<endl;
    cin>>e;
    cout<<RightSibling(bt,e);
    break;
case 11:
    cout<<Root(bt);
    break;
case 12:
    p=bt->left;
    cout<<Value(p)<<endl;
    break;
case 13:
    p=bt->left;
    cout<<"请输入您要赋的值"<<endl;
    cin>>e;
    Assign(p,e);
    cout<<"assign函数调用成功！其中的值现在为："<<endl;
    cout<<p->data<<endl;
    break;

case 14:
    LevelOrderTraverse(bt);
    break;
case 15:
    cout<<BiTreeDepth(bt)<<endl;
    break;
case 16:

    findleaf(bt,count3);
    cout<<count3<<endl;
    break;
case 17:
    PreOrderTraverse2(bt);
    break;
case 18:
    InOrderTraverse2(bt);
    break;
case 19:
    PostOrderTraverse2(bt);
    break;
case 20:
    cout<<findleafinforest(bt)<<endl;
    break;
case 21:
    BithrTree bt;
    CreateBithrTree(bt);
    BithrTree thrt;
    cout<<"线索化二叉树成功！"<<endl;
    InOrderThreading(thrt,bt);
    InOrderTraverseThrtree(thrt);
    cout<<"遍历线索二叉树成功！"<<endl;
   break;
}


   cout<<"您是否想要继续调用函数？yes/no"<<endl;
    string s;cin>>s;
    if (!s.compare("yes"))
    goto ll1;
    else



    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
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
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762

我这个哈夫曼树貌似有点问题，结果不太对啊。。有空再调一调

哈夫曼测试数据：
8
5 29 7 8 14 23 3 11

未调试出来的哈夫曼：
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string>
#include <string.h>
#include <math.h>
#define MAXSIZE 20

using namespace std;
//哈夫曼编码
typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;

typedef char* *Huffmancode;//定义一个指针数组存放编码

int min(HuffmanTree t,int i)
 { // 函数void select()调用
   int j,flag;
   unsigned int k=UINT_MAX; // 取k为不小于可能的值
   for(j=1;j<=i;j++)
     if(t[j].weight<k&&t[j].parent==0)
       k=t[j].weight,flag=j;
   t[flag].parent=1;
   return flag;
 }

 void select(HuffmanTree t,int i,int &s1,int &s2)
 { // s1为最小的两个值中序号小的那个
   int j;
   s1=min(t,i);
   s2=min(t,i);
   if(s1>s2)
   {
     j=s1;
     s1=s2;
     s2=j;
   }
 }

void HuffmanCoding(HuffmanTree &ht,Huffmancode &hc,int *w,int n)
{
    int i;
    if (n<=1)
        return;//判断N(字符个数)的输入是否合法
    int m;//哈夫曼树结点个数
    m = 2*n-1;
    //哈夫曼树是一个数组，我们要先定义出来， 再初始化数组
    ht = (HuffmanTree )malloc((m+1)*sizeof(HTNode));//0 单元未用
    //给初始字符赋权值
    HuffmanTree p;
    p=ht;
    p++;
    int *t;t=w;

    for (i=1,t++;i<=n;i++,p++,t++)
    {
        (*p).weight=*t;
        (*p).lchild=0;
        (*p).rchild=0;
        (*p).parent=0;
    }
    //给还没计算的结点赋值0
    for (p=&ht[n+1],i=n+1;i<=m;i++,p++)
    {
        (*p).weight=0;
        (*p).lchild=0;
        (*p).rchild=0;
        (*p).parent=0;
    }

    //建立哈夫曼树
    for(int i=n+1;i<=m;i++)
    {
        int s1,s2;
        select(ht,i-1,s1,s2);//最小的两个结点序号为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;
    }
    //show()
//    for (i=1 ; i<=m ; i++)
//    {
//        cout<< ht[i].weight <<" " <<ht[i].parent <<" "<<ht[i].lchild <<" "<<ht[i].rchild<<endl;
//    }
    //进行哈夫曼编码
    int c,f;
    hc=(Huffmancode)malloc(sizeof(char *)*(n+1));//头指针向量
    char *cd = (char *)malloc(sizeof(char)*n);//一个字符编码的数组指针
    cd[n-1]='\0';
    for (int i=1;i<=n;i++)//循环N个字符
    {
        int start = n-1;//从叶节点开始往上编
        for (c=i,f=ht[i].parent;f!=0;c=f,f=ht[f].parent)
        {
            //定义C是为了不动I，顺次往上找双亲，判断自己是双亲的左子树还是右子树
            if (ht[f].lchild == c)
                cd[--start]='0';
            else
                cd[--start]='1';

        }

        for (int x = n-start;x<n;x++)
            cout<<cd[x];
        hc[i]=(char *)malloc((n-start)*sizeof(char));
        strcpy(hc[i],cd);
        //cout<<hc[i]<<endl;
    }

}

int main()
{
  int *w,*ww;

  int n;
  cout<<"请输入字符数N"<<endl;
  cin>>n;
  w=(int *)malloc(sizeof(int)*(n+1));//0号单元未用
  ww=w;
  int i;
  cout<<"请依次输入字符的权值"<<endl;
  for (ww++,i=1;i<=n;i++,ww++)
  {
     cin>> *ww;
  }

    HuffmanTree ht;
    Huffmancode hc;
    HuffmanCoding(ht,hc,w,n);
    Huffmancode q=hc;

    for (int k=1;k<=n;k++)
    puts(hc[k]);





    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

实验报告4 图的有关操作

无向网的创建、求度、深度遍历、广度遍历

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string>
#define MAX_VERTEX_NUM 20

using namespace std;
//1.建立无向网的邻接表

typedef int  InfoType;//权值
typedef  char VertexType ;

typedef struct ArcNode
{
    int adjvex;//该弧的弧尾
    struct ArcNode *nextarc;//指向的下一个弧
    InfoType *info;
}ArcNode;
typedef struct VNode
{
    VertexType data;//顶点类型和数据
    ArcNode *firstarc;//指向的第一条邻接弧
}VNode,AdjList[MAX_VERTEX_NUM];//表头
typedef struct
{
    AdjList vertices;//
    int vexnum,arcnum;
    int kind; //DG 0 DN 1 UDG 2 UDN 3
}ALGraph;//adjacency list graph 邻接表

int locate(ALGraph &g,char v)
{
    int i=0;
    for (i;i<g.vexnum;i++)
    {
        if (g.vertices[i].data == v)
            return i;
    }

}
void createUDN(ALGraph &g)
{
    cout<<"构造无向网：请输入网的顶点个数和弧的个数"<<endl;
    cin>>g.vexnum>>g.arcnum;
    g.kind = 3;

    //构造顶点向量
    int i,j,k;
    //请输入每个顶点的值
    for (i=0;i<g.vexnum;i++)//初始化
    {
       cin>> g.vertices[i].data;
       g.vertices[i].firstarc  = NULL;//头结点置空
    }

    //构造链表们
    char v1,v2;
    int w;
    cout<<"请输入每条弧的弧头 、弧尾、权值"<<endl;
    for(k=0;k<g.arcnum;k++)
    {
        cin>>v1>>v2>>w;
        i = locate(g,v1);//弧尾
        j = locate(g,v2);//弧头
        ArcNode *p ;
        p = (ArcNode *)malloc(sizeof(ArcNode));//新建一块表结点空间
        p->adjvex = j;
        p->info = (int *)malloc(sizeof(int));//对于网，用来存放权值
        p->info = &w;
        p->nextarc = g.vertices[i].firstarc;//置空
        g.vertices[i].firstarc = p;//头插法建表
        if (g.kind >= 2) //如果是无向图或者无向网，需要做对称
    {
        p = (ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex = i;
        p->info = (int *)malloc(sizeof(int));
        p->info = &w;
        p->nextarc = g.vertices[j].firstarc ;
        g.vertices[j].firstarc = p;
    }

    }

}

//求邻接表的入度和出度
int* out(ALGraph &g)
{
    int *p,*q;
    p = (int *) malloc((g.vexnum)*sizeof(int));//申请一个动态数组，存放的是每一个顶点对应的出度
    q=p;
    int i =0;
    int cou =1;//计数器
    for (i;i<g.vexnum ; i++)
    {
        //对每一个结点进行计算出度，循环一遍
        ArcNode *q=g.vertices[i].firstarc;//q指向第一个结点
        while (q->nextarc)
        {
         cou++;
         q=q->nextarc;
        }
        *p = cou;
        p++;
        cou=0;//清空计数器
    }
    return q;
}
int * in(ALGraph &g)
{
    int *p;
    p = (int *)malloc((g.vexnum)*sizeof(int));
    int i=0;
    int j=0;
    int cou=0;
    ArcNode *q;
    for (i;i<g.vexnum;i++)
    {//外层循环遍历每个结点，计算入度
        for (j;j<g.vexnum;j++)
        {
            //内层循环遍历全部表元素
            q = g.vertices[j].firstarc;
            while (q->nextarc)
            {
                if (q->adjvex == i)
                    cou++;
            }

        }
        *p=cou;
        p++;
        cou=0;

    }
    return p;
}
//深度优先搜索
bool visited[MAX_VERTEX_NUM];

void DFSTraverse(ALGraph g)
{
    void DFS(ALGraph g,int v);
    int v;
    //visited数组初始化
    for (v=0;v<g.vexnum;v++)
    visited[v]=false;

    for(v=0;v<g.vexnum;v++)
    if (!visited[v])//如果结点未被访问过 ,则深度遍历该结点
    DFS(g,v);
}
int FirstAdjVex(ALGraph &g,int v)
{
    //对于无向网来说，每个顶点必定有一个邻接点
    return g.vertices[v].firstarc->adjvex;//返回V结点的第一个邻接结点的序号
}
int NextAdjVex(ALGraph &g,int v,int w)
{//必须要讨论有没有除了第一个邻接点之外的第二个邻接点
    //注意要找
    ArcNode *p=g.vertices[v].firstarc;
    while (p->adjvex!=w)
        p=p->nextarc;
    p = p->nextarc;
    if (!p)
        return -1;
    else
        return p->adjvex;//所以我们的条件为w>=0
}
void DFS(ALGraph g,int v)
{
    visited[v]=true;//置标志
    cout<<g.vertices[v].data<<" ";
    int w;
    for (w = FirstAdjVex(g,v);w>=0;w=NextAdjVex(g,v,w))
        if (!visited[w])
        DFS(g,w);
}
//广度优先搜索
typedef int Elemtype;
//进队出队为序号，输出时打印char数据，这样比较方便
typedef struct
{
    Elemtype data[MAX_VERTEX_NUM];
    int rear,front;
}SeqQueue;
void InitQueue(SeqQueue &q)
{
    q.rear = q.front = -1;
}
void EnQueue(SeqQueue &q,Elemtype e )
{
    q.rear = (q.rear+1)%MAX_VERTEX_NUM;
    q.data[q.rear] = e;
}
void deQueue(SeqQueue &q,Elemtype &e)
{
    if (q.rear == q.front)
    {
        printf("empty queue");
    }
    q.front = (q.front + 1)% MAX_VERTEX_NUM;
    e = q.data[q.front];

}
int QueueEmpty(SeqQueue &q)
{
    return q.rear == q.front;
}
void BFSTraverse(ALGraph &g)
{
    int v,u,w;
    for (v=0;v<g.vexnum;v++)
        visited[v]=false;
    SeqQueue q;
    InitQueue(q);
    for (v=0;v<g.vexnum;v++)
    {
        if (!visited[v])
        {
            visited[v]=true;
            printf("%c ",g.vertices[v].data);
            EnQueue(q,v);
            while (!QueueEmpty(q))
            {
                deQueue(q,u);
                for ( w = FirstAdjVex(g,u);w>=0;w=NextAdjVex(g,u,w))
                {
                    if (!visited[w])
                    {
                        visited[w]=true;
                        printf("%c ",g.vertices[w].data);
                        EnQueue(q,w);

                    }
                }



            }
        }
    }


}
int main()
{
    ALGraph g;
    createUDN(g);
    //1.求无向网的度
    cout<<"无向图的度为"<<endl;
    int *p;p=out(g);int i=0;
    for (p,i;i<g.vexnum;i++,p++)
        cout<<*p<<" ";
    cout<<endl;
    //2.深度优先遍历
    cout<<"深度优先遍历无向图"<<endl;
    DFSTraverse(g);
    //3.广度优先遍历
    cout<<"广度优先遍历无向图"<<endl;
    BFSTraverse(g);

    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
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264

实验报告内容：
１．键盘输入数据，建立一个有向图的邻接表。
２．输出该邻接表。
*３．建立一个无向图的十字链表。
４．在有向图的邻接表的基础上计算各顶点的度，并输出。
５．以有向图的邻接表为基础实现输出它的拓扑排序序列。
*６．采用邻接矩阵存储一个有向图，输出单源点到其它顶点的最短路径。
７．采用邻接表存储实现无向图的深度优先非递归遍历。
８．采用邻接表存储实现无向图的广度优先遍历。
*９．采用邻接矩阵存储实现无向图的最小生成树的PRIM算法。
*10．判断无向图任意两个顶点间是否有路径，若有输出路径上的顶点序列。
11．在主函数中设计一个简单的菜单，分别调试上述算法。
*12．综合训练：为计算机专业设计教学计划：4个学年，每学年2个学期，开设50门课程，每学期所开课程门数尽量均衡，课程的安排必须满足先修关系。

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string>
#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20

using namespace std;
//1.定义有向网的邻接表结构

typedef int  InfoType;//权值
typedef  char VertexType ;

typedef struct ArcNode
{
    int adjvex;//该弧的弧尾
    struct ArcNode *nextarc;//指向的下一个弧
    InfoType info;
}ArcNode;
typedef struct VNode
{
    VertexType data;//顶点类型和数据
    ArcNode *firstarc;//指向的第一条邻接弧
}VNode,AdjList[MAX_VERTEX_NUM];//表头
typedef struct
{
    AdjList vertices;
    int vexnum,arcnum;
    int kind; //DG 0 DN 1 UDG 2 UDN 3 kind =1
}ALGraph;//adjacency list graph 邻接表

//一个桟
typedef int Elemtype;
typedef struct
{
    VertexType data[MAX_VERTEX_NUM];
    int top;
}SeqStack;
void InitStack(SeqStack &s)
{
    s.top=-1;
}
int isEmpty(SeqStack &s)
{
    return s.top==-1;
}
void push(SeqStack &s,Elemtype e)
{
    if (s.top == MAX_VERTEX_NUM)
        printf("full stack!");
    s.top++;
    s.data[s.top]=e;
}
void pop(SeqStack &s,Elemtype &e)
{
    if (isEmpty(s))
        printf("empty stack !");
    e = s.data[s.top--];
}
int getTop(SeqStack &s)
{
    return s.data[s.top];
}


//2.创建有向网
//定位函数
int locate(ALGraph &g,char v)
{
    int i=0;
    for (i;i<g.vexnum;i++)
    {
        if (g.vertices[i].data == v)
            return i;
    }

}
void createDN(ALGraph &g)
{
    cout<<"构造有向网：请输入网的顶点个数和弧的个数"<<endl;
    cin>>g.vexnum>>g.arcnum;
    g.kind = 1;

    //构造顶点向量
    int i,j,k;
    cout<<"请输入每个顶点的值"<<endl;
    for (i=0;i<g.vexnum;i++)//初始化
    {
       cin>> g.vertices[i].data;
       g.vertices[i].firstarc  = NULL;//头结点置空
    }

    //构造链表们
    char v1,v2;
    int w;
    cout<<"请输入每条弧的弧头 、弧尾、权值"<<endl;
    for(k=0;k<g.arcnum;k++)
    {
        cin>>v1>>v2>>w;
        i = locate(g,v1);//弧尾
        j = locate(g,v2);//弧头
        ArcNode *p ;
        p = (ArcNode *)malloc(sizeof(ArcNode));//新建一块表结点空间
        p->adjvex = j;
//        InfoType *info;
//        p->info = (int *)malloc(sizeof(int));//对于网，用来存放权值
//        p->info = &w;
        p->info = w;
        p->nextarc = g.vertices[i].firstarc;//置空
        g.vertices[i].firstarc = p;//头插法建表

    }

}
// 创建无向网
void createUDN(ALGraph &g)
{
    cout<<"构造无向网：请输入网的顶点个数和弧的个数"<<endl;
    cin>>g.vexnum>>g.arcnum;
    g.kind = 3;

    //构造顶点向量
    int i,j,k;
    //请输入每个顶点的值
    for (i=0;i<g.vexnum;i++)//初始化
    {
       cin>> g.vertices[i].data;
       g.vertices[i].firstarc  = NULL;//头结点置空
    }

    //构造链表们
    char v1,v2;
    int w;
    cout<<"请输入每条弧的弧头 、弧尾、权值"<<endl;
    for(k=0;k<g.arcnum;k++)
    {
        cin>>v1>>v2>>w;
        i = locate(g,v1);//弧尾
        j = locate(g,v2);//弧头
        ArcNode *p ;
        p = (ArcNode *)malloc(sizeof(ArcNode));//新建一块表结点空间
        p->adjvex = j;
        p->info = w;
        p->nextarc = g.vertices[i].firstarc;//置空
        g.vertices[i].firstarc = p;//头插法建表
        if (g.kind >= 2) //如果是无向图或者无向网，需要做对称
    {
        p = (ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex = i;
        p->info = w;
        p->nextarc = g.vertices[j].firstarc ;
        g.vertices[j].firstarc = p;
    }

    }

}

//3.输出邻接表
void printALGraph(ALGraph &g)
{
  int i=0;
  ArcNode *p;

  for (i;i< g.vexnum ;i++)
  {
      printf("弧头：%c ",g.vertices[i].data);
      p=g.vertices[i].firstarc;//P指向链表的第一个结点
      while (p)
      {
          printf("(弧尾：%d,权值：%d) ",p->adjvex,p->info);
          p=p->nextarc;
      }
      cout<<endl;
  }
}
// 4.有向网的十字链表
typedef struct ArcBox
{
    int tailvex,headvex;
    struct ArcBox *hlink,*tlink;
    InfoType info;
}ArcBox;

typedef struct VexNode
{
    VertexType data;
    ArcBox *firstin,*firstout;
}VexNode;

typedef struct
{
    VexNode xlist[MAX_VERTEX_NUM];//表头向量
    int vexnum,arcnum;
}OLGraph;

int locate(OLGraph &g,char v)
{
    int i=0;
    for (i;i<g.vexnum;i++)
    {
        if (g.xlist[i].data == v)
        {
            return i;
        }
    }
}

void createOLDN(OLGraph &g)
{
    cout <<"请输入有向网的顶点个数、弧的个数"<<endl;
    cin>>g.vexnum>>g.arcnum;

    int i,j,k;
    cout<<"请输入顶点值"<<endl;
    for (i=0;i<g.vexnum;i++)
    {
        cin>>g.xlist[i].data;
        g.xlist[i].firstin=g.xlist[i].firstout=NULL;
    }
    cout<<"请输入每条弧的弧头和弧尾和权值"<<endl;
    char v1,v2;int w;
    ArcBox *p;
    fflush(stdin);
    for (k=0;k<g.arcnum;k++)
    {
        cin>>v1>>v2>>w;
        i=locate(g,v1);
        j=locate(g,v2);
        p=(ArcBox *)malloc(sizeof(ArcBox));
        //对弧结点赋值
        p->headvex = j;//弧的弧头
        p->tailvex = i;//弧的弧尾 逆邻接表
        p->hlink = g.xlist[j].firstin;//弧头相同的结点 逆邻接表
        p->tlink = g.xlist[i].firstout;//弧尾相同的结点
        p->info = w;
        g.xlist[j].firstin = g.xlist[i].firstout = p;


    }
}
//输出有向网的十字链表，分为邻接表和逆邻接表
void printOLGraph(OLGraph &g)
{
  cout<<"输出邻接表"<<endl;
  int i=0;
  ArcBox *p;

  for (i;i< g.vexnum ;i++)
  {
      printf("弧头：%c ",g.xlist[i].data);
      p=g.xlist[i].firstout;//P指向链表的第一个结点
      while (p)
      {
          printf("(弧尾：%d,权值：%d) ",p->headvex,p->info);
          p=p->tlink;
      }
      cout<<endl;
  }
  cout<<"输出逆邻接表"<<endl;
  for (i=0;i< g.vexnum ;i++)
  {
      printf("弧头：%c ",g.xlist[i].data);
      p=g.xlist[i].firstin;//P指向链表的第一个结点
      while (p)
      {
          printf("(弧尾：%d,权值：%d) ",p->tailvex,p->info);
          p=p->hlink;
      }
      cout<<endl;
  }
}
//5.无向图的十字链表
void createOLUDG(OLGraph &g)
{
    cout <<"请输入有向网的顶点个数、弧的个数"<<endl;
    cin>>g.vexnum>>g.arcnum;

    int i,j,k;
    cout<<"请输入顶点值"<<endl;
    for (i=0;i<g.vexnum;i++)
    {
        cin>>g.xlist[i].data;
        g.xlist[i].firstin=g.xlist[i].firstout=NULL;
    }
    cout<<"请输入每条弧的弧头和弧尾"<<endl;
    char v1,v2;
    ArcBox *p;
    fflush(stdin);
    for (k=0;k<g.arcnum;k++)
    {
        cin>>v1>>v2;
        i=locate(g,v1);
        j=locate(g,v2);
        p=(ArcBox *)malloc(sizeof(ArcBox));
        //对弧结点赋值
        p->headvex = j;//弧的弧头
        p->tailvex = i;//弧的弧尾 逆邻接表
        p->hlink = g.xlist[j].firstin;//弧头相同的结点 逆邻接表
        p->tlink = g.xlist[i].firstout;//弧尾相同的结点
        g.xlist[j].firstin = g.xlist[i].firstout = p;
        //无向图做对称
        p=(ArcBox *)malloc(sizeof(ArcBox));
        //对弧结点赋值
        p->headvex = i;//弧的弧头
        p->tailvex = j;//弧的弧尾 逆邻接表
        p->hlink = g.xlist[i].firstin;//弧头相同的结点 逆邻接表
        p->tlink = g.xlist[j].firstout;//弧尾相同的结点
        g.xlist[i].firstin = g.xlist[j].firstout = p;



    }
}
//输出无向图
void printOLGraph2(OLGraph &g)
{

  cout<<"输出邻接表"<<endl;
  int i=0;
  ArcBox *p;

  for (i=0;i< g.vexnum ;i++)
  {
      printf("弧头：%c->",g.xlist[i].data);
      p=g.xlist[i].firstout;//P指向链表的第一个结点
      while (p)
      {
          printf("%d->",p->headvex);
          p=p->tlink;
      }
      cout<<"NULL"<<endl;
  }
  cout<<"输出逆邻接表"<<endl;
  for (i=0;i< g.vexnum ;i++)
  {
      printf("弧头：%c->",g.xlist[i].data);
      p=g.xlist[i].firstin;//P指向链表的第一个结点
      while (p)
      {
          printf("%d->",p->tailvex);
          p=p->hlink;
      }
      cout<<"NULL"<<endl;
  }
}

//6.求邻接表的入度和出度
int* out(ALGraph &g)
{
    int *p,*q;
    p = (int *) malloc((g.vexnum)*sizeof(int));//申请一个动态数组，存放的是每一个顶点对应的出度
    q=p;
    int i =0;
    int cou =0;//计数器
    for (i=0;i<g.vexnum ; i++)
    {
        //对每一个结点进行计算出度，循环一遍
        ArcNode *q=g.vertices[i].firstarc;//q指向第一个结点
        while (q)
        {
         cou++;
         q=q->nextarc;
        }
        *p = cou;
        p++;
        cou=0;//清空计数器
    }
    return q;
}
int * in(ALGraph &g)
{
    int *p;
    p = (int *)malloc((g.vexnum)*sizeof(int));
    int i=0;
    int j=0;
    int cou=0;
    ArcNode *q;
    for (i=0;i<g.vexnum;i++)
    {//外层循环遍历每个结点，计算入度
        for (j=0;j<g.vexnum;j++)
        {
            //内层循环遍历全部表元素
            q = g.vertices[j].firstarc;
            while (q)
            {
                if (q->adjvex == i)
                    cou++;
                q=q->nextarc;
            }

        }
        p[i]=cou;
        cou=0;

    }
    return p;
}
int *InAndOut(ALGraph &g)
{
    int *p=in(g);
    int *q=out(g);
    int *k;
    k=(int *)malloc((g.vexnum)*sizeof(int));
    for (int i=0;i<g.vexnum;i++)
    {
        k[i]=p[i]+q[i];
    }
    return k;
}

//7.深度优先搜索
bool visited[MAX_VERTEX_NUM];

void DFSTraverse(ALGraph g)
{
    void DFS(ALGraph g,int v);
    int v;
    //visited数组初始化
    for (v=0;v<g.vexnum;v++)
    visited[v]=false;

    for(v=0;v<g.vexnum;v++)
    if (!visited[v])//如果结点未被访问过 ,则深度遍历该结点
    DFS(g,v);
}
int FirstAdjVex(ALGraph &g,int v)
{
    //对于无向网来说，每个顶点必定有一个邻接点
    return g.vertices[v].firstarc->adjvex;//返回V结点的第一个邻接结点的序号
}
int NextAdjVex(ALGraph &g,int v,int w)
{//必须要讨论有没有除了第一个邻接点之外的第二个邻接点
    //注意要找
    ArcNode *p=g.vertices[v].firstarc;
    while (p->adjvex!=w)
        p=p->nextarc;
    p = p->nextarc;
    if (!p)
        return -1;
    else
        return p->adjvex;//所以我们的条件为w>=0
}
void DFS(ALGraph g,int v)
{
    visited[v]=true;//置标志
    cout<<g.vertices[v].data<<" ";
    int w;
    for (w = FirstAdjVex(g,v);w>=0;w=NextAdjVex(g,v,w))
        if (!visited[w])
        DFS(g,w);
}
// 非递归
/*
1.栈初始化
2.输出起始顶点；起始顶点改为“已访问”标记；将起始顶点进桟
3.重复直到桟空
  3.1 取栈顶元素（不出桟）
  3.2 栈顶元素顶点存在未被访问过的邻接点W，则
  	3.2.1 输出顶点W
  	3.2.2 将顶点W改为已访问标志
  	3.2.3 将顶点W进桟
  3.3 否则，当前顶点退桟
*/


int hasNextAdjVex(ALGraph &g,int h)
{
    //找到H的未被访问过的邻接点
    ArcNode *p=g.vertices[h].firstarc;
    if (!p)
        return -1;
    while (visited[p->adjvex])
    {
        p=p->nextarc;
    }
    return p->adjvex;

}
void DFS_2(ALGraph &g,int v)
{
    SeqStack s;
    InitStack(s);
    printf("%c",g.vertices[v].data);
    visited[v]=true;
    push(s,v);
    int h,w,e;
    while (!isEmpty(s))
    {
        h=getTop(s);
        w=hasNextAdjVex(g,h);
        if (w>=0)
        {
          printf("%c",g.vertices[w].data);
          visited[w]=true;
          push(s,w);
        }
        else
            pop(s,e);

    }

}
void DFSTraverse_2(ALGraph g)
{
    int v;
    //visited数组初始化
    for (v=0;v<g.vexnum;v++)
    visited[v]=false;

    for(v=0;v<g.vexnum;v++)
    if (!visited[v])//如果结点未被访问过 ,则深度遍历该结点
    DFS_2(g,v);
}
//8.广度优先搜索
typedef int Elemtype;
//进队出队为序号，输出时打印char数据，这样比较方便
typedef struct
{
    Elemtype data[MAX_VERTEX_NUM];
    int rear,front;
}SeqQueue;
void InitQueue(SeqQueue &q)
{
    q.rear = q.front = -1;
}
void EnQueue(SeqQueue &q,Elemtype e )
{
    q.rear = (q.rear+1)%MAX_VERTEX_NUM;
    q.data[q.rear] = e;
}
void deQueue(SeqQueue &q,Elemtype &e)
{
    if (q.rear == q.front)
    {
        printf("empty queue");
    }
    q.front = (q.front + 1)% MAX_VERTEX_NUM;
    e = q.data[q.front];

}
int QueueEmpty(SeqQueue &q)
{
    return q.rear == q.front;
}
void BFSTraverse(ALGraph &g)
{
    int v,u,w;
    for (v=0;v<g.vexnum;v++)
        visited[v]=false;
    SeqQueue q;
    InitQueue(q);
    for (v=0;v<g.vexnum;v++)
    {
        if (!visited[v])
        {
            visited[v]=true;
            printf("%c ",g.vertices[v].data);
            EnQueue(q,v);
            while (!QueueEmpty(q))
            {
                deQueue(q,u);
                for ( w = FirstAdjVex(g,u);w>=0;w=NextAdjVex(g,u,w))
                {
                    if (!visited[w])
                    {
                        visited[w]=true;
                        printf("%c ",g.vertices[w].data);
                        EnQueue(q,w);

                    }
                }



            }
        }
    }


}
//9.拓扑排序
// 建立辅助数组indegree 存放每个顶点的入度
void FindInDegree(ALGraph &g,int in[])
{
    int i=0,j=0;
    ArcNode *p;
    int count=0;
    for (i;i<g.vexnum;i++)
    {
        for (j=0;j<g.vexnum;j++)
        {
           p=g.vertices[j].firstarc;
           while (p)
           {
               if (p->adjvex == i)
                count++;
               p=p->nextarc;
           }
        }
        in[i] = count;
        cout<<count<<' ' ;
        count = 0;
    }
}
//这里需要一个栈

//拓扑排序算法
void TopologicalSort(ALGraph g)
{
    int indegree[g.vexnum];//定义一个入度的辅助数组
    int i,k;
    for (i=0;i<g.vexnum;i++)
    indegree[i]=0;
    FindInDegree(g,indegree);
    SeqStack s;
    InitStack(s);
    //如果入度为零则进栈
   for (i=0;i<g.vexnum;i++)
   {
       if (!indegree[i])
        push(s,i);//序号进栈
   }
   int count = 0;//对输出顶点个数进行计数
   ArcNode *p;
   while (!isEmpty(s))
   {
       pop(s,i);
       printf("%d:%c ",i,g.vertices[i].data);
       count++;
       for (p=g.vertices[i].firstarc;p;p=p->nextarc)
       {
           k=p->adjvex;
           if (!(--indegree[k]))
            push(s,k);
       }
   }
   if (count < g.vexnum)
    printf("该有向图有回路\n");
   else
    printf("该有向图无回路\n");


}

//10. PRIM 算法
//prim algorithm
//邻接矩阵
typedef int VRType;
typedef int VertexType2;
typedef int InfoType;
typedef struct ArcCell
{
    VRType adj;
    InfoType info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct
{
    VertexType2 vex[MAX_VERTEX_NUM];//顶点向量
    AdjMatrix arcs;//邻接矩阵
    int vexnum,arcnum;
    int kind;
}MGraph;
int locate(MGraph &g,int v)
{
    int i;
    for (i=0;i<g.vexnum;i++)
    {
       if (g.vex[i] == v)
            return i;
    }
}
//邻接数组创建无向图
void createUDG(MGraph &g)
{
    cout<<"请输入无向图的顶点个数和边的个数"<<endl;
    cin>>g.vexnum>>g.arcnum;
    int i,j,k;
    //初始化顶点向量
    for (i=0;i<g.vexnum;i++)
        cin>>g.vex[i];
        //初始化邻接矩阵
    for (i=0;i<g.vexnum;i++)
        for (j=0;j<g.vexnum;j++)
        g.arcs[i][j].adj = INFINITY;
        cout<<"请输入每条边的顶点和权值"<<endl;
    for (k=0;k<g.arcnum;k++)
    {
        int v1,v2;
        int w;
        cin>>v1>>v2>>w;
        i=locate(g,v1);
        j=locate(g,v2);
        g.arcs[i][j].adj=w;
        g.arcs[j][i].adj=g.arcs[i][j].adj;//无向图为对称的！
    }

}
typedef struct node {
    VertexType2 adjvex;//权最小的顶点
    VRType lowcost;//最小的权
    }closedge[MAX_VERTEX_NUM];

int mininum(closedge close,int n)
{
    int i=0;
    int min = 999;
    int k;
    for (i=1;i<n;i++)
    {
      if (close[i].lowcost < min && close[i].lowcost !=0)
      {
          min = close[i].lowcost;
          k = i;
      }
    }
    return k;
    //k记录最小权值顶点的序号

}
//最小生成树——PRIM算法
void MinispanTree_PRIM(MGraph g,VertexType2 u)
{

    closedge close;
    int k=locate(g,u);
    int i,j;
    //辅助数组初始化
    for (j=0;j<g.vexnum;j++)
        if (j!=k)
    {
      close[j].adjvex=u;
      close[j].lowcost = g.arcs[k][j].adj;
    }
    close[k].lowcost = 0;
    for (i=1;i<g.vexnum;i++)
    {
        k = mininum(close,g.vexnum);
        cout<<"("<<close[k].adjvex<<","<<g.vex[k]<<")";//输出这条边的两个顶点
        close[k].lowcost = 0;
        for (j=0;j<g.vexnum;j++)
        {
            if (g.arcs[k][j].adj < close[j].lowcost)
            {
                close[j].adjvex = g.vex[k];
                close[j].lowcost = g.arcs[k][j].adj;
            }

        }


    }

}
int main()
{
    cout << "------------------------------------"<<endl;
    cout << "1.createDN():建立一个有向网的邻接表 "<<endl;
    cout << "2.printALGraph():输出邻接表"<<endl;
    cout << "3.createOLDN():创建有向网十字链表并输出其邻接表和逆邻接表"<<endl;
    cout << "4.createOLUDG():创建无向图十字链表并输出其邻接表和逆邻接表"<<endl;
    cout << "5.in():求有向图/网的出度"<<endl;
    cout << "6.out():求有向图/网的入度"<<endl;
    cout << "7.InAndOut():求有向图的度"<<endl;
    cout << "8.DFSTraverse():无向图的深度优先遍历"<<endl;
    cout << "9.BFSTraverse():无向图的广度优先遍历"<<endl;
    cout << "10.TopologicalSort():以有向图的邻接表为基础实现输出它的拓扑排序序列。"<<endl;
    cout << "11.MinispanTree_PRIM():采用邻接矩阵存储实现无向图的最小生成树的PRIM算法"<<endl;
    cout << "12.DFS_2():非递归实现深度优先搜索"<<endl;
    cout << "------------------------------------"<<endl;

LL1:

    cout<< "请输入您要选择的函数序号:)"<<endl;
    int num,i;cin>>num;int *p;
    switch(num)
    {
    case 1:
    ALGraph g;
    createDN(g);
    cout<<"创建一个有向网的邻接表成功！"<<endl;
        break;
    case 2:
        createDN(g);
        printALGraph(g);
        break;
    case 3:
        OLGraph g1;
        createOLDN(g1);
        printOLGraph(g1);
        break;
    case 4:
        createOLUDG(g1);
        printOLGraph2(g1);
        break;
    case 5:
        createDN(g);
        p=in(g);
        for (i=0;i<g.vexnum;i++,p++)
            cout<<g.vertices[i].data<<":"<<*p<<" ";
        cout<<endl;
        break;
    case 6:
        createDN(g);
        p=out(g);
        for (i=0;i<g.vexnum;i++,p++)
            cout<<g.vertices[i].data<<":"<<*p<<" ";
        cout<<endl;
        break;
    case 7:
        createDN(g);
        p=InAndOut(g);
        for (i=0;i<g.vexnum;i++)
            cout<<g.vertices[i].data<<":"<<(p[i])<<" ";
        cout<<endl;

        break;
    case 8:
        createUDN(g);
        DFSTraverse(g);
        break;
    case 9:
        createUDN(g);
        BFSTraverse(g);
        break;
    case 10:
        createDN(g);
        TopologicalSort(g);
        break;
    case 11:
        MGraph gg;
        createUDG(gg);
        MinispanTree_PRIM(gg,0);
        break;
    case 12:
        createUDN(g);
        DFSTraverse_2(g);
    }
    fflush(stdin);
    char c;
cout <<"您是否要继续测试函数？y/n"<<endl;
cin >> c;
if (c == 'y')
    goto LL1;
else
    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
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
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849

第6，10题在此单独测试：

#include <iostream>
#define MAX_VERTEX_NUM 20
#define INFINITY INT_MAX
using namespace std;
//判断无向图任意两个顶点间是否有路径，若有输出路径上的顶点序列。
//floid 算法
//邻接矩阵

typedef char VertexType;
typedef int VRType;
typedef int InfoType;
typedef struct ArcCell
{
    VRType adj;
    InfoType *info;
}ArcCell,ArcMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct
{
    int kind ;
    int vexnum,arcnum;
    VertexType vexs[MAX_VERTEX_NUM];
    ArcMatrix arcs;
}MGraph;

int locate(MGraph &g,VertexType v)
{
    int i;
    for (i=0;i<g.vexnum;i++)
    {
        if (g.vexs[i] == v)
        return i;
    }
}
void createUDN(MGraph &g)
{
    cout <<"请输入顶点个数和弧的条数"<<endl;
    cin >> g.vexnum>>g.arcnum;
    int i,j,k;
    cout <<"请输入顶点集合"<<endl;
    for (i=0;i<g.vexnum;i++)
    {
      cin >>g.vexs[i];
      for (j=0;j<g.vexnum;j++)
      {
          if (i!=j)
             g.arcs[i][j].adj=INFINITY;
          else
             g.arcs[i][j].adj=0;
      }

    }


    cout <<"请输入各条弧的弧头、弧尾以及权值"<<endl;
    char v1,v2;
    int w;
    for (k=0;k<g.arcnum;k++)
    {
        cin >>v1>>v2>>w;
        i=locate(g,v1);
        j=locate(g,v2);
        g.arcs[i][j].adj=w;
        //无向网做对称
        g.arcs[j][i].adj=w;

    }
}
void printAdjMatrix(MGraph &g)
{
    int i,j;
    for (i=0;i<g.vexnum;i++)
    {
    for (j=0;j<g.vexnum;j++)
    cout <<g.arcs[i][j].adj<<" ";
    cout <<endl;
    }

}
typedef bool PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef int distanceMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

void ShortestPath_FLOYD(MGraph &g,PathMatrix &p,distanceMatrix &d)
{
    void printD(MGraph g,distanceMatrix &d);
    int v,w,u,i;
    for (v=0;v<g.vexnum;v++)
        for (w=0;w<g.vexnum;w++)
    {
        d[v][w]=g.arcs[v][w].adj;
    for (u=0;u<g.vexnum;u++)
    {
        p[v][w][u]=false;
    }
    if (d[v][w] < INFINITY )
    {
        p[v][w][v]=true;
        p[v][w][w]=true;
    }
    }

    for (u=0;u<g.vexnum;u++)
        for (v=0;v<g.vexnum;v++)
        for (w=0;w<g.vexnum;w++)
        {
            if (d[v][u]!=INFINITY && d[u][w]!=INFINITY )
        if (d[v][u] + d[u][w] < d[v][w])
    {
        d[v][w] = d[v][u]+d[u][w];
        for (i=0;i<g.vexnum ;i++)
        p[v][w][i]=p[v][u][i] || p[u][w][i];

    }

        }

}
void printD(MGraph g,distanceMatrix &d)
{
    int i,j;
    for(i=0;i<g.vexnum;i++)
    {
         for (j=0;j<g.vexnum;j++)
         {
             cout << d[i][j]<<" ";
         }
         cout <<endl;
    }

}

void printShortestPath_FLOIY(MGraph g,PathMatrix &p,distanceMatrix &d)
{
    int i,j,k;
    for (i=0;i<g.vexnum;i++)
    {
        for (j=0;j<=i;j++) // 输出一半即可
        {
            cout <<"顶点对：  <"<<g.vexs[i]<<","<<g.vexs[j]<<">   (";
            for (k=0;k<g.vexnum;k++)
            {
                if (p[i][j][k])
                    cout <<g.vexs[k]<<" ";
            }
            cout <<" )"<<"   路径长度："<<d[i][j]<<endl;
        }
    }
}
int main()
{
    MGraph g;
    createUDN(g);
    PathMatrix p;
    distanceMatrix d;
    ShortestPath_FLOYD(g,p,d);
    cout << " 输出每对顶点的最短路径"<<endl;
    printShortestPath_FLOIY(g,p,d);



    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

#include <iostream>
#define MAX_VERTEX_NUM 20
#define INFINITY INT_MAX
using namespace std;
//采用邻接矩阵存储一个有向图，输出单源点到其它顶点的最短路径。
//迪杰特斯拉

typedef char VertexType;
typedef int VRType;
typedef int InfoType;
typedef struct ArcCell
{
    VRType adj;
    InfoType *info;
}ArcCell,ArcMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct
{
    int kind ;
    int vexnum,arcnum;
    VertexType vexs[MAX_VERTEX_NUM];
    ArcMatrix arcs;
}MGraph;

int locate(MGraph &g,VertexType v)
{
    int i;
    for (i=0;i<g.vexnum;i++)
    {
        if (g.vexs[i] == v)
        return i;
    }
}
void createDN(MGraph &g)
{
    cout <<"请输入顶点个数和弧的条数"<<endl;
    cin >> g.vexnum>>g.arcnum;
    int i,j,k;
    cout <<"请输入顶点集合"<<endl;
    for (i=0;i<g.vexnum;i++)
    {
      cin >>g.vexs[i];
      for (j=0;j<g.vexnum;j++)
      g.arcs[i][j].adj=INFINITY;
    }


    cout <<"请输入各条弧的弧头、弧尾以及权值"<<endl;
    char v1,v2;
    int w;
    for (k=0;k<g.arcnum;k++)
    {
        cin >>v1>>v2>>w;
        i=locate(g,v1);
        j=locate(g,v2);
        g.arcs[i][j].adj=w;

    }
}

void printAdjMatrix(MGraph &g)
{
    int i,j;
    for (i=0;i<g.vexnum;i++)
    {
    for (j=0;j<g.vexnum;j++)
    cout <<g.arcs[i][j].adj<<" ";
    cout <<endl;
    }

}

typedef int ShortPathTable[MAX_VERTEX_NUM];
typedef bool PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

void shortestPath_DIJ(MGraph &g,int v0,PathMatrix &p,ShortPathTable &d)
{
// final d p
    bool final[g.vexnum];
    int v,w,i,j;
    for (v=0;v<g.vexnum;v++)
    {
        final[v]=false;
        d[v]=g.arcs[v0][v].adj;
        for (w=0;w<g.vexnum;w++)
        p[v][w]=false;

        if (d[v] < INFINITY)
        {
            p[v][v0]=true;
            p[v][v]=true;
        }
    }

    d[v0]=0;//自己到自己
    final[v0]=true;//并到S集合中
    int min;
    for (i=0;i<g.vexnum;i++)
    {
        min = INFINITY;
        for (w=0;w<g.vexnum;w++)
        {
            if (!final[w])
            if (d[w]<min)
            {
                v=w;
                min=d[w];
            }
        }
        final[v]=true;
        for (w=0;w<g.vexnum;w++)
        {
            //对于每个顶点，在介入离V0最近的点之后是否会离v0更近呢？
            if (!final[w]&&(min+g.arcs[v][w].adj<d[w]))
            {
                d[w]=min+g.arcs[v][w].adj;
                //p[w]=p[v];
                for (j=0;j<g.vexnum;j++)
                p[w][j]=p[v][j];
                p[w][w]=true;
            }
        }
    }
}
void printP(PathMatrix &p)
{
    int i,j;
    for (i=0;i<6;i++)
    {
      for (j=0;j<6;j++)
    cout << p[i][j]<<" ";
    cout <<endl;
    }

}
void printD(ShortPathTable &d)
{
    int i;
    for (i=0;i<6;i++)
    cout<<d[i]<<" ";
    cout<<endl;
}
void printShortestPath(MGraph &g,PathMatrix &p,ShortPathTable &d)
{
    int i,j;
    for (i=1;i<g.vexnum;i++)
    {
        cout <<g.vexs[i]<<":";
        cout <<"    最短路径：(";
        for (j=0;j<g.vexnum;j++)
        if (p[i][j])
        cout <<g.vexs[j]<<" ";
        cout <<")    路径长度："<<d[i]<<endl;
    }
}
int main()
{
    MGraph g;
    createDN(g);
    printAdjMatrix(g);
    PathMatrix p;
    ShortPathTable d;
    shortestPath_DIJ(g,0,p,d);
    // v0 = 0 为单源点
    printP(p);
    printD(d);
    printShortestPath(g,p,d);
    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

实验报告五 查找的相关操作

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define INFINITY INT_MAX
#define MAXSIZE 20

using namespace std;
//1.折半查找
typedef int KeyType;
typedef struct
{
    KeyType key;
    char data1;
}ElemType;
typedef struct
{
    ElemType data[MAXSIZE];
    int length;

}SeqList;

void createSeqList(SeqList &l)
{
    cout<<"请输入关键字个数"<<endl;
    cin>>l.length;
    cout<<"请顺序输入一组有序的数据及其关键字（key,data1）"<<endl;
    for (int i=1;i<=l.length;i++)
    {
        scanf("%d%c",&l.data[i].key,&l.data[i].data1);
    }
}

int Search_Bin(SeqList &l,KeyType key)
{
   int low=1,high=l.length;
   int mid;
   while (low<=high)
   {
       mid=(low+high)/2;
       if (key == l.data[mid].key)
        return mid;
       else if (key < l.data[mid].key )
        high=mid-1;
       else
        low=mid+1;
   }
   return 0;
}
//2.二叉排序树
typedef struct BiTNode
{
    ElemType data;
    struct BiTNode *left,*right;
}BiTNode,*BiTree;

// 查找二叉排序树
int SearchBST(BiTree t,KeyType key,BiTree f,BiTree &p)
{
    if (!t) {p=f;return 0;}
    else if (key==t->data.key){p=t;return 1;}
    else if (key <t->data.key)
        return SearchBST(t->left,key,t,p);
    else return SearchBST(t->right,key,t,p);
}
// 插入一个数据到二叉排序树
int InsertBST(BiTree &t,ElemType e)
{
    BiTree p,s;
    if (!SearchBST(t,e.key,NULL,p))
    {
        s=(BiTree)malloc(sizeof(BiTNode));
        s->data.key=e.key;
        s->data.data1=e.data1;
        s->left=s->right=NULL;
        if (!p)
            t=s;
        else if (e.key < p->data.key )
            p->left=s;
        else
            p->right=s;
        return 1;
    }
    else
        return 0;
}
// 循环插入一组数据，建立二叉排序树
void InsertBST_for()
{
    void InOrderTraverse(BiTree &t);
    void DeleteBST(BiTree &t,KeyType key);
    BiTree t;
    t=NULL;
    ElemType e;
    int n;
    cout<<"请输入您要输入的数据个数"<<endl;
    cin>>n;
    cout<<"请依次输入您要插入的数据及其关键字（key,data1）"<<endl;
    for (int i=0;i<n;i++)
    {
      cin>>e.key>>e.data1;
      InsertBST(t,e);
    }
     cout<<"中序遍历输出的结果为："<<endl;
     InOrderTraverse(t);
     cout<<"请输入您要删除的某一元素的关键字"<<endl;
     KeyType key;
     cin>>key;
     DeleteBST(t,key);
     cout<<"删除指定元素后的中序遍历结果为："<<endl;
     InOrderTraverse(t);




}
// 中序遍历二叉排序树
void InOrderTraverse(BiTree &t)
{
    if (t)
    {
        InOrderTraverse(t->left);
        cout<<t->data.key<<" ";
        InOrderTraverse(t->right);
    }
}
// 二叉排序树删除:删除某一指定结点
int Delete(BiTree &p)
{
    BiTree q,s;
    if (!p->right)
    {
        q=p;
        p=p->left;
        free(q);
    }
    else if (!p->right)
    {
        q=p;
        p=p->right;
        free(q);
    }
    else
    {
        q=p;
        s=p->left;
        while (s->right)
        {
            q=s;
            s=s->right;
        }
        p->data.key=s->data.key;
        p->data.data1=s->data.data1;

        if (q!=p)
            q->right=s->left;
        else
            q->left=s->left;
        delete(s);

    }
    return 1;
}
// 删除某关键字
int DeleteBST(BiTree &t,KeyType key)
{
    if (!t)
        return 0;
    else
    {
        if (key == t->data.key )
            return Delete(t);
        else if (key < t->data.key)
        return DeleteBST(t->left,key);
        else
            return DeleteBST(t->right,key);
    }
    return 1;
}
// AVL
typedef struct BSTNode
{
    ElemType data;
    int bf;
    struct BSTNode *left,*right;
}BSTNode,*BSTree;

// 右旋
void R_Rotate(BSTree &p)
{
    BSTree lc;
    lc=p->left;
    p->left=lc->right;
    lc->right=p;
    p=lc;

}
//左旋
void L_Rotate(BSTree &p)
{
    BSTree lc;
    lc=p->right;
    p->right=lc->left;
    lc->left=p;
    p=lc;
}
//左平衡
void LeftBalance(BSTree &t)
{
    BSTree lc,rd;
    lc=t->left;
    switch(lc->bf)
    {
    case 1:
        t->bf=lc->bf=0;
        R_Rotate(t);
        break;
    case -1:
        rd=lc->right;
        switch(rd->bf)
        {
        case 1:
            t->bf=-1;
            lc->bf=0;
            break;
        case 0:
            t->bf=lc->bf=0;
            break;
        case -1:
            t->bf=0;
            lc->bf=1;
            break;
        }
        rd->bf=0;
        L_Rotate(t->left);
        R_Rotate(t);
    }

}
//右平衡
void RightBalance(BSTree &t)
{
    BSTree lc,rd;
    lc=t->right;
    switch(lc->bf)
    {
    case 1:
        rd=lc->left;
        switch(rd->bf)
        {
        case 1:
            t->bf=0;
            lc->bf=-1;
            break;
        case 0:
            t->bf=lc->bf=0;
            break;
        case -1:
            t->bf=1;
            lc->bf=0;
            break;
        }
        rd->bf=0;
        R_Rotate(t->right);
        L_Rotate(t);
        break;
    case -1:
        t->bf=lc->bf=0;
        L_Rotate(t);
    }

}
//插入建立平衡二叉排序树
int InsertAVL(BSTree &t,ElemType e,bool taller)
{
    if (!t)
    {
        t=(BSTree )malloc(sizeof(BSTNode));
        t->bf=0;
        t->left=t->right=NULL;
        t->data.data1=e.data1;
        t->data.key=e.key;
        taller=true;//树长高则为正
    }
    else
    {
        if (e.key==t->data.key)
        {
            taller=false;
            return 0;
        }
        if (e.key < t->data.key)
        {
            if (!InsertAVL(t->left,e,taller))
                return 0;
                if (taller)
                {
                    switch(t->bf)
                    {
                        case 1:
                            LeftBalance(t);
                            taller=false;
                            break;
                        case 0:
                            t->bf=1;
                            taller=true;
                            break;
                        case -1:
                            t->bf=0;
                            taller=false;
                            break;
                    }
                }
        }
        else
        {
            if (!InsertAVL(t->right,e,taller))
                return 0;
                if (taller)
                {
                    switch(t->bf)
                    {
                        case 1:
                            t->bf=0;
                            taller=false;
                            break;
                        case 0:
                            t->bf=-1;
                            taller=true;
                            break;
                        case -1:
                            RightBalance(t);
                            taller=false;
                            break;
                    }
                }
        }
    }
    return 1;
}
// 中序遍历平衡二叉排序树
void InOrderTraverse_BST(BSTree &t)
{
    if (t)
    {
        InOrderTraverse_BST(t->left);
        cout<<t->data.key<<" ";
        InOrderTraverse_BST(t->right);
    }
}
// 线性探测法建立散列表
typedef struct
{
    ElemType data[MAXSIZE];
    int count;
}HashTable;
// 哈希函数
int Hash(KeyType k)
{
    int p=13;
    return k%13;
}
//发生冲突之后求出下一探查地址
void collision(HashTable h,int &p)
{
    p=(p+1+MAXSIZE)%MAXSIZE;
}
// 在哈希表中查找某关键字
int SearchHash(HashTable h,KeyType key,int &p)
{
    p=Hash(key);// 哈西地址
    while (h.data[p].key!=NULL && key!=h.data[p].key )
    collision(h,p);

    if (key==h.data[p].key)
        return 1;
    else
        return 0;

}
// 插入机建立线性探测哈希表
int InsertHash(HashTable &h,ElemType e)
{
    int p;
    h.count=0;
    if (SearchHash(h,e.key,p))
        return 0;
    else
        h.data[p].key=e.key;
        h.data[p].data1=e.data1;
        h.count++;
        return 1;
}
// 遍历输出线线性探测哈希表
void TraverseHash(HashTable h)
{
    int i;
    for (i=0;i<MAXSIZE;i++)
        cout<<"("<<h.data[i].key<<","<<h.data[i].data1<<")";
    cout<<endl;
}

// 外拉链法建立哈希表
typedef struct Node
{
    ElemType e;
    struct Node *next;
}Node,HashTable2[MAXSIZE];
// 查找外拉链表
int searchHash2(HashTable2 h,ElemType e,int &p)
{
    p=Hash(e.key);// 哈西地址
    Node *q;
    q=h[p].next;
    while (q)
    {
       if (q->e.key==e.key)
            return 1;
        q=q->next;
    }
    return 0;
}
// 插入建立外拉链表
int InsertHash2(HashTable2 h,ElemType e)
{
    int p;
    Node *q;
    if (searchHash2(h,e,p))
        return 0;
    else
    {
       q=(Node*)malloc(sizeof(Node));
       q->e.key=e.key;
       q->e.data1=e.data1;
       q->next=h[p].next;//头插法插入元素
       h[p].next=q;
    }
    return 1;
}
// 遍历外拉链表
void TraverseHash2(HashTable2 h)
{
    int i;
    Node *p;
    for (i=0;i<MAXSIZE;i++)
    {
       p=h[i].next;
       while (p)
       {
           cout<<"("<<p->e.key<<","<<p->e.data1<<")";
           p=p->next;
       }
    }
}


int main()
{   cout<<"--------------------------------------------------------"<<endl;
    cout<<"1.Search_Bin():采用折半查找实现某一已知的关键字的查找"<<endl;
    cout<<"2.InsertBST()&&DeleteBST():插入算法建立二叉排序树并删除某指定元素"<<endl;
    cout<<"3.InsertAVL():建立AVL树并实现删除某一指定关键字元素"<<endl;
    cout<<"4.InsertHash():线性探测法建立哈希表"<<endl;
    cout<<"5.InsertHash2():外拉链法建立哈希表"<<endl;
    cout<<"--------------------------------------------------------"<<endl;
ll1:cout<<"请输入您选择的函数序号"<<endl;
    int x;cin>>x;
    ElemType e;int n;
    switch(x)
    {
    case 1:
    {
    SeqList l;
    createSeqList(l);
    cout<<"请输入任一关键字"<<endl;
    KeyType key;
    cin>>key;
    int location=Search_Bin(l,key);
    printf("查找位置为：%d\n",location);
    break;
    }

    case 2:
    {
       InsertBST_for();
       break;
    }

    case 3:
        {
            BSTree t1;
            t1=NULL;
            cout<<"请输入数据个数"<<endl;
            cin>>n;
            cout<<"请输入一组数据（key,data1）以建立平衡二叉树"<<endl;
            for (int i=0;i<n;i++)
            {
                cin>>e.key>>e.data1;
                InsertAVL(t1,e,false);
            }
            cout<<"建立结束，现在中序遍历"<<endl;
            InOrderTraverse_BST(t1);
            break;
        }
    case 4:
        HashTable h;
        for (int i=0;i<MAXSIZE;i++)
    {
      h.data[i].key=0;
      h.data[i].data1='z';
    }
        cout<<"请输入元素个数"<<endl;
        cin>>n;
        cout<<"请输入一组关键字（key,data1）"<<endl;
        for (int i=0;i<n;i++)
        {
            cin>>e.key>>e.data1;
            InsertHash(h,e);
        }
        cout<<"建立结束，遍历哈希表,(0,z)表示NULL"<<endl;
        TraverseHash(h);

        break;

    case 5:
        HashTable2 h1;
        for (int i=0;i<MAXSIZE;i++)
    {
     h1[i].next=NULL;
    }
        cout<<"请输入元素个数"<<endl;
        cin>>n;
        cout<<"请输入一组关键字（key,data1）"<<endl;
        for (int i=0;i<n;i++)
        {
            cin>>e.key>>e.data1;
            InsertHash2(h1,e);
        }
        cout<<"建立结束，遍历哈希表"<<endl;
        TraverseHash2(h1);
        break;
    }
    cout<<"您是否还要继续测试其他函数？y/n"<<endl;
    fflush(stdin);
    char z;
    cin>>z;
    if (z=='y')
        goto ll1;
    else
    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
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
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550

实验6 排序

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define INFINITY INT_MAX
#define MAXSIZE 100

using namespace std;
typedef struct list
{int key;
}ElemType;
typedef struct {
ElemType data[MAXSIZE+1];
int length; /*参加排序元素的实际个数*/
}SeqList;
//创建顺序表
void creatList(SeqList &l)
{
    cout<<"请输入数据个数"<<endl;
    cin>>l.length;
    cout<<"请顺次输入一组无序数据"<<endl;
    for (int i=1;i<=l.length;i++)
    {
        cin>>l.data[i].key;
    }
}
// 直接插入排序
void InsertSort(SeqList &l)
{
    int i,j;
    for (i=2;i<=l.length;i++)
    {
        if (l.data[i].key < l.data[i-1].key )
        {
            l.data[0].key=l.data[i].key;
            l.data[i].key=l.data[i-1].key;
            for (j=i-2;l.data[0].key < l.data[j].key ;j--)
                l.data[j+1].key=l.data[j].key;
            l.data[j+1].key=l.data[0].key;
        }
    }
}
//输出顺序表元素
void print(SeqList l)
{
    int i;
    for (i=1;i<=l.length;i++)
        cout<<l.data[i].key<<" ";
    cout<<endl;
}
//冒泡排序
void BubbleSort(SeqList &l)
{
    int i,j;
    for (i=1;i<=l.length-1;i++)
        for (j=1;j<=l.length-i;j++)
    {
        if (l.data[j].key > l.data[j+1].key)
        {
           l.data[0]=l.data[j];
           l.data[j]=l.data[j+1];
           l.data[j+1]=l.data[0];
        }
    }
}
// 直接选择排序
void SelectSort(SeqList &l)
{
    int i,j,k;
    for (i=1;i<=l.length-1;i++)
    {
        k=i;
        for (j=i;j<=l.length;j++)
        {
          if (l.data[j].key<l.data[k].key)
          {
              k=j;
          }
        }
        if (k!=i)
        {
            l.data[0]=l.data[k];
            l.data[k]=l.data[i];
            l.data[i]=l.data[0];
        }
    }
}
//希尔插入
void ShellInsert(SeqList &l,int dk)
{
    //dk是位置增量
    int i,j;
    for (i=dk+1;i<=l.length;i++)
    {
        if (l.data[i].key < l.data[i-dk].key)
        {
            l.data[0]=l.data[i];
            for (j=i-dk;j>0&&l.data[0].key<l.data[j].key;j=j-dk)
            {
                l.data[j+dk]=l.data[j];
            }
            l.data[j+dk]=l.data[0];
        }
    }
}
//希尔排序
void ShellSort(SeqList &l,int dlta[],int t)
{
    //dlta[]是增量数组，每一次循环以dlta[k]为增量，dlta[0---t-1]
    int k;
    for (k=0;k<t;k++)
        ShellInsert(l,dlta[k]);
}
//快排
int Partition(SeqList &l,int low,int high)
{
    l.data[0]=l.data[low];
    int p;
    p=l.data[low].key;
    while (low<high)
    {
        while (low<high&&l.data[high].key>=p) high--;
        l.data[low]=l.data[high];
        while (low<high&&l.data[low].key<=p) low++;
        l.data[high]=l.data[low];
    }
    l.data[low]=l.data[0];
    return low;
}
void QSort(SeqList &l,int low,int high)
{
    int p;
    if (low<high)
    {
       p=Partition(l,low,high);
       QSort(l,low,p-1);
       QSort(l,p+1,high);
    }
}

//堆调整
void HeapAdjust(SeqList &l,int s,int m)
{
    ElemType rc=l.data[s];
    int j;
    for (j=2*s;j<=m;j*=2)
    {
        if (j<m && l.data[j].key < l.data[j+1].key)
            j++;
        if (!(rc.key < l.data[j].key))
            break;
        l.data[s]=l.data[j];s=j;
    }
    l.data[s]=rc;
}
//堆排序
void HeapSort(SeqList &l)
{
    int i;
    for (i=l.length/2;i>0;i--)
        HeapAdjust(l,i,l.length);
    for (i=l.length;i>1;i--)
    {
        l.data[0]=l.data[1];
        l.data[1]=l.data[i];//data[1]即为最大的数
        l.data[i]=l.data[0];
        HeapAdjust(l,1,i-1);
    }


}

//折半插入排序
void BinInsertSort(SeqList &l)
{
    int i,j,low,high,mid;
    for (i=2;i<=l.length;i++)
    {
        l.data[0]=l.data[i];
        low=1;high=i-1;
        while (low<=high)
        {
            mid=(low+high)/2;
            if (l.data[0].key < l.data[mid].key ) high=mid-1;
            else low=mid+1;
        }
        for (j=i-1;j>=high+1;j--)
            l.data[j+1]=l.data[j];
        l.data[high+1]=l.data[0];
    }
}
// 链式存储实现简单选择排序
typedef struct LNode
{
    ElemType data;
    struct LNode *next;
}LNode,*linklist;
//创建单链表l
void createLinkList(linklist &l)
{
    linklist p,q;
    l=(linklist)malloc(sizeof(LNode));
    p=l;
    cout<<"请输入数据个数"<<endl;
    int n;cin>>n;
    cout<<"请输入一组数据"<<endl;
    ElemType e;

    for (int i=0;i<n;i++)
    {
        cin>>e.key;
        q=(linklist)malloc(sizeof(LNode));
        q->data.key=e.key;
        q->next=NULL;
        p->next=q;
        p=q;
    }

}
// 简单选择排序
void SelectSort_linklist(linklist &l)
{
    ElemType tmp;
    linklist p,q,k;//P为工作指针，Q为指向最小元素的指针,k为前面指向第一个为排序元素的指针
    p=l->next;q=p;k=p;
    while (k)
    {

    while (p)
    {
        if (p->data.key < q->data.key )
        {
            q=p;
        }
        p=p->next;
    }
    if (k!=q)
    {
        tmp=k->data;
        k->data=q->data;
        q->data=tmp;
    }
    k=k->next;
    p=k;
    q=k;
    }
}
//打印链表
void print_linklist(linklist l)
{
    linklist p=l->next;
    while (p)
    {
        cout<<p->data.key<<" ";
        p=p->next;
    }
    cout<<endl;
}
// 链式直接插入排序
void InsertSort_linklist(linklist &l)
{
    linklist p,q,t;
    p=l->next->next;//把P插入到链表L中
    l->next->next=NULL;
    q=l;
    while (p)
    {
        while (q->next && p->data.key >q->next->data.key)
            q=q->next;
        if (!q)
        {
            q->next = p;
            p=p->next;
            p->next=NULL;
        }
        else
        {
            t=p;p=p->next;
            t->next=q->next;
            q->next=t;
        }
        q=l;
    }
}
// 链式冒泡排序
void BubbleSort_linklist(linklist &l)
{
    linklist p=l->next,q,c;
    q=p->next;
    ElemType e;
    c=p;
    while (c)
    {
       while (q)
    {

        if (p->data.key > q->data.key )
        {
            e=p->data;
            p->data=q->data;
            q->data=e;
        }
        p=p->next;q=q->next;
    }
    p=l->next,q=p->next;
    c=c->next;
    }


}
int main()
{   cout<<"--------------------------------------------------------"<<endl;
    cout<<"1.InsertSort():直接插入排序"<<endl;
    cout<<"2.Bl.data[1]ubbleSort():冒泡排序"<<endl;
    cout<<"3.SelectSort():直接选择排序"<<endl;
    cout<<"4.ShellSort():希尔排序"<<endl;
    cout<<"5.QSort():快速排序"<<endl;
    cout<<"6.HeapSort():堆排序"<<endl;
    cout<<"7.BinInsertSort():折半插入排序"<<endl;
    cout<<"9.SelectSort_linklist():链式简单选择排序"<<endl;
    cout<<"10.InsertSort_linklist():链式直接插入排序"<<endl;
    cout<<"11.BubbleSort_linklist():链式冒泡排序"<<endl;
    cout<<"--------------------------------------------------------"<<endl;
ll1:cout<<"请输入您选择的函数序号"<<endl;
    int x;cin>>x;
    SeqList l;
    linklist l1;
    switch(x)
    {
    case 1:
    {
    creatList(l);
    cout<<"直接插入排序前的结果"<<endl;
    print(l);
    InsertSort(l);
    cout<<"直接插入排序后的结果"<<endl;
    print(l);
    break;
    }

    case 2:
    {
    creatList(l);
    cout<<"冒泡排序前的结果"<<endl;
    print(l);
    BubbleSort(l);
    cout<<"冒泡排序后的结果"<<endl;
    print(l);
       break;
    }

    case 3:
        {
    creatList(l);
    cout<<"直接选择排序前的结果"<<endl;
    print(l);
    SelectSort(l);
    cout<<"直接选择排序后的结果"<<endl;
    print(l);
            break;
        }
    case 4:
    creatList(l);
    cout<<"希尔排序前的结果"<<endl;
    print(l);
    int dlta[3];dlta[0]=5;dlta[1]=3;dlta[2]=1;
    ShellSort(l,dlta,3);
    cout<<"希尔排序后的结果"<<endl;
    print(l);
        break;

    case 5:
    creatList(l);
    cout<<"快速排序前的结果"<<endl;
    print(l);
    QSort(l,1,8);
    cout<<"快速排序后的结果"<<endl;
    print(l);
        break;

    case 6:
        {
    creatList(l);
    cout<<"堆排序前的结果"<<endl;
    print(l);
    HeapSort(l);
    cout<<"堆排序后的结果"<<endl;
    print(l);
      break;
        }

    case 7:
        {
    creatList(l);
    cout<<"折半插入排序前的结果"<<endl;
    print(l);
    BinInsertSort(l);
    cout<<"折半插入排序后的结果"<<endl;
    print(l);
      break;
        }
    case 9:
        {
            createLinkList(l1);
            cout<<"链式简单选择排序之前："<<endl;
            print_linklist(l1);
            SelectSort_linklist(l1);
            cout<<"链式简单选择排序之后："<<endl;
            print_linklist(l1);
            break;
        }
    case 10:
        {
            createLinkList(l1);
            cout<<"链式直接插入排序之前："<<endl;
            print_linklist(l1);
            InsertSort_linklist(l1);
            cout<<"链式直接插入排序之后："<<endl;
            InsertSort_linklist(l1);
            break;
        }

    case 11:
        {
            createLinkList(l1);
            cout<<"链式冒泡排序之前："<<endl;
            print_linklist(l1);
            BubbleSort_linklist(l1);
            cout<<"链式冒泡排序之后："<<endl;
            print_linklist(l1);
            break;
        }




    }
    cout<<"您是否还要继续测试其他函数？y/n"<<endl;
    fflush(stdin);
    char z;
    cin>>z;
    if (z=='y')
        goto ll1;
    else
    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
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
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446