数据结构实训报告(线性表+栈和队列+二叉树+图+排序)_数据结构列队实验总结

来自草稿箱的最早一篇博客。

一、线性表的基本操作

1.实验内容：

（1）输入并建立多项式，用带表头结点的单链表存储多项式。
（2）输出多项式，输出形式为整数序列：n，c1，e1，c2，e2……cn，en， 其中n是多项式的项数，ci，ei分别为第i项的系数和指数。序列按指数降序排列。
（3）多项式a和b相加，建立多项式a 、b，输出相加的多项式。
（4）多项式a和b相减，建立多项式a 、b，输出相减的多项式。
（5）多项式a和b相加，建立多项式a 、b，输出相乘的多项式。

2.设计思路：

我们可以将实验内容分解为几个问题：如果存储多项式？如何完成多项式的运算？接下来细化这些问题。
1.多项式的存储：实验内容已经提示了用链表存储，链表的存储内容有两点，一是数据域，二是指针域；数据域有两部分，一是系数，二是指数；指针域表示指向的下一个节点，这样就完成了多项式的存储。
2.多项式的输出：本质上还是链表的遍历，从入口进入后依次访问每个元素。这里要注意多项式的特殊性，所以要分类讨论来访问。如果说一项的指数和系数都存在的话，直接都输出即可，要注意用$x的次方$连接（当然不用也可以）；如果说指数为0的话，说明这项为常数项，就不用输出后面的$x的次方$和系数了；如果系数为0的话，直接跳过该项即可，因为这项为无用项，在计算过程中就可以直接省略。另外还有个小的美化的地方就是如果不是最后一项的话，就输出“+”，表示连接两项。
3.多项式的加减：加法和减法的原理很简单，就是指数相同的项进行系数的合并（相加或相减），最后输出即可。 设计思路为分别设两个指针指向两个多项式，这里用链表存储多项式，由于内容已经要求按指数降序排 列了，我们无需比较大小，直接从前向后遍历即可，遍历的时候比较两个指针的指数是否相同，如果相 同旧合并，否则就每次都将大的添加到结果链表里，并将该指针后移，直到两个链表里有一个指针为 空。最后再将剩余的项接到结果链表就好了。
4.多项式的乘法：由于多项式的存储是按照指数降序排的，所以两个多项式里第一个元素的指数相乘一定是最大的， 我们可以先把这个计算出来。然后两层for循环枚举一下两项相乘的结果，考虑生成的新的项插入在哪：本位或者向前插入或者向后插入。

3.实验代码：

typedef struct LIST///结构体 
{
    int exp;///指数
    double coef;///系数
    struct LIST* next;
} LIST,*LISTLINK;//链表 
LISTLINK A,B,C;///三个多项式 
LISTLINK taila,tailb,tailc;///尾指针 
int cnta,cntb;
int n,m;///两个多项式的项数 
void initlist(LISTLINK &L,LISTLINK &tail)//初始化链表 
{
    L=(LIST*)malloc(sizeof(LIST));
    L->next=NULL;
    tail=L;
}
void Insertlist(int exp,double coef,LISTLINK &L,LISTLINK &tail) 
{///插入元素  
    LIST* tmp=(LIST*)malloc(sizeof(LIST));///申请空间 
    tmp->coef=coef;//赋值 
    tmp->exp=exp;
    tmp->next=NULL;
    tail->next=tmp;
    tail=tmp;
}
void output(LISTLINK &L,LISTLINK &tail)
{///遍历链表 注意输出格式 
    LISTLINK p=L->next;
    bool flag=0;
    while(p)
    {
    	if(p->coef!=0&&p->exp!=0)///指数和系数都不为0时，输出指数和系数并规范x的输出 
        	printf("%.2fx^%d",p->coef,p->exp),flag=1;
        else if(p->exp==0) printf("%.2f",p->coef),flag=1;//指数为0时说明只需要输出系数即可，不用输出x 
        if(p->next!=NULL) cout<<"+";///如果不是最后一项就输出+ 
        p=p->next;
    }
    if(!flag) cout<<"0";///flag为0说明是空链表 输出0 
}
void add()
{//多项式相加 相同系数直接进行指数相加即可 
    LIST* pa=A->next;
    LIST* pb=B->next;
    while(pa&&pb)
    {///两个表内都有元素时，比较指数的大小，每次把大的插入链表 
        if(pa->exp>pb->exp)
        {
            Insertlist(pa->exp,pa->coef,C,tailc);
            pa=pa->next;
        }
        else if(pa->exp<pb->exp)
        {
            Insertlist(pb->exp,pb->coef,C,tailc);
            pb=pb->next;
        }
        else
        {//指数相同时，要合并系数 
            double x=pa->coef+pb->coef;
            if(x!=0) Insertlist(pa->exp,x,C,tailc);
            pa=pa->next;
            pb=pb->next;
        }
    }
    ///将剩余元素接到表当中 
    while(pa)
    {
        Insertlist(pa->exp,pa->coef,C,tailc);
        pa=pa->next;
    }
    while(pb)
    {
        Insertlist(pb->exp,pb->coef,C,tailc);
        pb=pb->next;
    }
    output(C,tailc);///输出结果
    puts("");
}
void sub()
{//多项式相减 相同系数直接进行指数相减即可 
    LIST* pa=A->next;
    LIST* pb=B->next;
    while(pa&&pb)
    {///两个表都有元素时，将大的插入表 
        if(pa->exp>pb->exp)
        {
            Insertlist(pa->exp,pa->coef,C,tailc);
            pa=pa->next;
        }
        else if(pa->exp<pb->exp)
        {
            Insertlist(pb->exp,pb->coef,C,tailc);
            pb=pb->next;
        }
        else
        {//指数相同时进行合并 
            double x=pa->coef-pb->coef;
            if(x!=0) Insertlist(pa->exp,x,C,tailc);
            pa=pa->next;
            pb=pb->next;
        }
    }
    ///将剩余元素接到表里 
    while(pa)
    {
        Insertlist(pa->exp,pa->coef,C,tailc);
        pa=pa->next;
    }
    while(pb)
    {
        Insertlist(pb->exp,pb->coef,C,tailc);
        pb=pb->next;
    }
    output(C,tailc);///输出结果
    puts("");
}
LISTLINK mul()///多项式相乘 
{
/**
基本原理：由于多项式的存储是按照指数降序排的，所以两个多项式里第一个元素的指数相乘一定是最大的， 
我们可以先把这个计算出来。
然后两层for循环枚举一下两项相乘的结果，考虑生成的新的项插入在哪：本位或者向前插入或者向后插入 
*/
	int n=1;//项数 
    LISTLINK p1;
    LISTLINK p2;
    LISTLINK p=(LIST*)malloc(sizeof(LIST));
    LISTLINK pre=(LIST*)malloc(sizeof(LIST));
    LISTLINK phead=(LIST*)malloc(sizeof(LIST));
	p1=A->next,p2=B->next;
	//LISTLINK p,pre,phead;///工作指针 工作指针的前一个 头结点
	p->coef=p1->coef*p2->coef;
	p->exp=p1->exp+p2->exp;///这个一定是指数最大的
	p->next=NULL;
	phead->next=p;
	pre->next=p;
	///两层for循环遍历
	while(p1){
		p2=B->next;///注意每次都要重新设置p2的值 
		while(p2){
			p=phead->next;//记录结果链表的头结点 
			LISTLINK pnew=(LIST*)malloc(sizeof(LIST));
			pnew->coef=p1->coef*p2->coef;///系数相乘 
			pnew->exp=p1->exp+p2->exp;//指数相加 
			pnew->next=NULL; 
			if(pnew->coef==0) continue;///系数为0直接跳过
			for(int i=0;i<n*m;i++){///最多有n*m项 
				if(p->exp==pnew->exp){///本位相加 
					if(n==1) break;///第一项已经计算过了 
					else{//合并 
						p->coef=p->coef+pnew->coef;
						n++;///项数+1 
						break;///跳出循环 
					}
				}
				else if(p->exp>pnew->exp){///向后插入 
					pre=p;//更新工作节点的上一个指针 
					if(p->next==NULL){
						p->next=pnew;
						n++;
						break;
					}
					else p=p->next;
				} 
				else{///向前插入 
					pre->next=pnew; 
					pnew->next=p;
					pre=pnew;
					n++;
					break;
				}
			} 
			p2=p2->next;///p2移动 
		}
		p1=p1->next;//p1移动 
	} 
	return phead;
	
}
int main()
{
	cout<<"请输入两个多项式的项数"<<endl; 
    n=read(),m=read();///多项式A的项数 多项式B的项数
///初始化三个链表 从大到小指数 
    initlist(A,taila);
    initlist(B,tailb);
    cout<<"请输入第一个多项式的项:系数，指数（按照指数从大到小排列输入）"<<endl;
    for(int i=1; i<=n; i++)
    {
        double coef;
        cin>>coef;
        int exp=read();
        Insertlist(exp,coef,A,taila);///插入元素 

    }
    cout<<"请输入第二个多项式的项:系数，指数（按照指数从大到小排列输入）"<<endl;
    for(int i=1; i<=m; i++)
    {
        double coef;
        cin>>coef;
        int exp=read();
        Insertlist(exp,coef,B,tailb);///插入元素 
    }
    cout<<"第一个多项式为:\n";
	output(A,taila);puts("");
	cout<<"第二个多项式为:\n";
	output(B,tailb);puts("");
    initlist(C,tailc);
    cout<<"两个多项式相加的结果为:\n";
    add();
    initlist(C,tailc);
    cout<<"两个多项式相减的结果为:\n";
    sub();
    initlist(C,tailc);
    cout<<"两个多项式相乘的结果为:\n";
    C=mul();
    output(C,tailc);
    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

二、栈和队列的基本操作

1.实验内容：

1.实验目的：
（1）掌握顺序栈的和链队列的实现；
（2）能利用栈和队列的基本运算解决实际问题；
2.实验要求： 车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供进出（栈结构）。 汽车在停车场内按车辆到达的先后顺序依次排列。 若停车场内的已停满汽车，则后来的车只能在门外的变道上等候，一旦停车场内有车开走， 则排在便道上的第一辆车即可进入（队列结构）。 每辆停放在停车场的车，在离开时按其在停车场停留时间长短交费（在这里假设车不能从门外等侯便道 上直接开走）。 试设计一个实现停车场管理的程序，按照从终端输入数据序列进行模拟管理 。
（1）采用顺序栈和链式队列实现；
（2） 每一组输入数据包括三个数据项：汽车牌照，到达或离去的标记和时刻。； （3） 对每一组输入数据进行操作后的输出信息为：车辆到达：输出车辆在停车场或便道上的停车位置车辆离去：输出停留时间和费用（在便道上等候不收费）

2.设计思路：

栈和队列与实际生活结合的题。
首先依照实验要求我们可以把停车场抽象为一个栈，将变道抽象为一个队列。 每次来一辆新的车，要判断是到达还是离开。如果是到达的话，当停车场满了时，就只能在变道上停 留，放进队列即可；否则，可以直接将车开到停车场里，放入栈即可。如果是离开的话，要注意该车必 须是栈里最晚进来的一辆车，同时我们还要考虑的是该车开走后的影响：如果车位原先是满的话，那么 该车离开后就会有变道上的车进入停车场直到停车场满。
关于费用的计算要注意在变道上的等候是不收费的，所以当车从变道进入停车场时要更新到达的时间以便于离开的时候计算费用 结合实际情况，还增加了修改停车场容量和停车单位小时费用，把停车的单位小时费用设成全局变量后 后者就是件很容易的事情了。关于前者，要考虑扩容或减容后停车场和变道车辆的变化情况。
对于查看停车场和变道的停车情况，由于stl的队列和栈没有遍历的函数，所以借助了另一个容器来进行遍历，根据各自的特点决定是否倒序存储。

3.实验代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=110;
struct node
{
    string id;///车牌号
    int flag;///表示是到达还是离开：到达是1，离开是0
    int time;///表示到达或离开的时间
};
map<string,bool>mp;///停车场是否有该车
int n,cost;//停车场的容量和单位小时的停车费用 
stack<node>stk;///栈模拟的停车场 
queue<node>q;///队列模拟的车道 

void showmain()//打印菜单 
{
    cout<<"**********菜单*************"<<endl;
    cout<<"1.修改停车场的容量"<<endl;
    cout<<"2.输入车辆信息"<<endl;
    cout<<"3.修改停车一小时的费用"<<endl;
    cout<<"4.查看停车场的车辆情况"<<endl;
    cout<<"5.查看变道的车辆情况"<<endl;
    cout<<"6.退出系统"<<endl;
}

void change_n()///修改停车场容量：注意修改后停车场和变道的车辆情况 
{
    int tmp;
    cin>>tmp;
    if(tmp>n)
    {///扩容了说明有更多的车可以进入停车场，依次取出变道的元素并且放入停车场直到满了为止 
        while(stk.size()<=n)
        {
            node t=q.front();
            t.time=t.time;
            q.pop();
            stk.push(t);
            mp[t.id]=1;
        }
    }
    else
    {///缩容后要将停车场的车移动到变道 
        while(stk.size()>n)
        {
            node t=stk.top();
            stk.pop();
            mp[t.id]=0;
            q.push(t);
        }
    }
    n=tmp;
}

void change_cost()
{
    cin>>cost;
}

void add_car()
{
    cout<<"请输入车辆的相关信息："<<endl;
    node t;
    cin>>t.id>>t.flag>>t.time;
    if(t.flag) //到达
    {
        if(stk.size()==n)
        {
            q.push(t);///停车场满了，只在路上停留
            cout<<"车牌号为"<<t.id<<"的车在路上的"<<q.size()<<"号位置"<<endl;
        }
        else
        {
            stk.push(t);///直接将车停到停车场里
            cout<<"车牌号为"<<t.id<<"的车在停车场的"<<stk.size()<<"号位置"<<endl;
            mp[t.id]=1;
        }
    }
    else ///离开
    {
        if(!mp[t.id])
        {
            puts("停车场没有该车");
            return ;
        }
        mp[t.id]=0;
        node tt=stk.top();
        stk.pop();
        while(stk.size()<n&&!q.empty())///空出的车位让变道的车进入 
        {
            node tmp=q.front();
            tmp.time=t.time;
            q.pop();
            stk.push(tmp);
            mp[tmp.id]=1;
        }
        cout<<"车牌号为"<<t.id<<"的车的花费为"<<(t.time-tt.time)*cost<<endl;
    }
  ///  cout<<stk.size()<<"*************"<<q.size()<<endl;//debug专用 
}

void show_park()///查看停车场的车辆情况 
{
    ///先进后出
    vector<node>v;
    int cnt=stk.size();
    while(!stk.empty()){//依次取出栈里元素 
        v.push_back(stk.top());
        cout<<"车牌号为"<<stk.top().id<<"的车在停车场的"<<cnt--<<"号位置"<<endl;
        stk.pop();
    }
    reverse(v.begin(),v.end());//由于栈是先进后出，所以要翻转一下 
    for(int i=0;i<v.size();i++){//重新放入栈里 
        stk.push(v[i]);
    }
}

void show_road()//查看变道的车辆情况 
{
    vector<node>v;
    int cnt=1;
    while(!q.empty()){//依次取出队列内元素 
        v.push_back(q.front());
        cout<<"车牌号为"<<q.front().id<<"的车在路上的"<<cnt++<<"号位置"<<endl;
        q.pop();
    }
    for(int i=0;i<v.size();i++){///放回队列 
        q.push(v[i]);
    }
}

int main()
{
    puts("请输入停车场的容量:");
    cin>>n;
    puts("请输入停车一小时的费用:");
    cin>>cost;
    while(1)
    {
        showmain();
        cout<<"请输入您想进行的操作:"<<endl;
        int op;
        cin>>op;
        if(op==1) change_n();
        else if(op==2) add_car();
        else if(op==3) change_cost();
        else if(op==4) show_park();
        else if(op==5) show_road();
        else if(op==6) return 0;
    }
    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

4.运行结果：

5.实验心得：

对费用的计算不准确，主要表现在以下几个方面：1.由于停留在变道上不收费，所以停车场容量改变后可能会对部分车的停留时间产生影响。2.单位时间停车的费用改变后，改变前和改变后是两个费用，应该分别计算。

三、二叉树的操作

1.实验内容：

1.实验目的：
（1）掌握二叉树的基本算法；
（2）理解树转化为二叉树后的结点关系变化并能解决实际问题。
2.实验内容： 家谱的设计主要是实现对家庭成员信息的建立、查找、插入、修改、删除等功能。要求和基本功能 如下
（1）采用两种存储结构实现家谱管理功能，其中一种是孩子兄弟链表存储结构。； （2）家庭成员的添加：即添加某一人的儿女，儿女的数目由控制台端给出，然后输入相应的儿女 姓名（此处儿女的姓名不能重名） 。
（2）家庭成员的修改：可以修改某一成员的姓名。
（3）成员的查询：查询某一成员在家族中的辈分（第几代） ，并能查询此成员的所有子女及这一 辈的所有成员。
（5）家庭成员的删除：删除此成员时，若其有后代，将删除其所有后代成员

2.设计思路:

首先要明确一下存储方式是孩子兄弟链表存储法，就是说在每个结点的指针域存储该节点的第一个孩子和该节点的下一个兄弟。然后依次说说设计思路：
1.建树：先输入根节点，再依次输入每个节点的子节点，借助队列完成建树。
2.查找父节点的函数：本质还是树的遍历，在换用存储方式后设计思路也稍微有些变化。首先如果待查 询节点是根节点的话，直接返回NULL；然后将根节点放入队列，依次取出队首元素，如果该节点有孩 子的话，如果第一个孩子就是待查节点，返回该节点；否则就遍历该节点的孩子，也就是遍历该节点第 一个孩子的兄弟节点，如果某个兄弟节点是待查节点的话，也是返回该节点。
3.添加函数：仅仅实现了添加一个孩子的功能，比如给fa添加son。就是先找到fa节点，如果该节点没 有孩子，那么son就是他的第一个孩子；否则的话，就是通过fa的第一个孩子的兄弟节点一直遍历到结 尾，然后将son接上。
4.删除函数：要判断的是待删除元素是否为第一个孩子；先找到待删除元素的双亲节点，如果说待删除 元素是第一个孩子的话，直接将指针往后移即可；否则就要先找到该节点，再将指针后移。
5.查询函数：这里有点投机取巧的方法，先层次遍历将每个节点深度存储下来，所以对于每个节点来 说，和他同一辈的就是深度相同的，他的所有子节点就是所有深度比他大的节点，因为层次遍历时我们 假设根节点的深度为1.
6.修改函数：找到该节点后修改就行。

3.实验代码：

#include<bits/stdc++.h>
using namespace std;
/**初始化的状态定义start**/
#define OK 1
#define ERROR 0
#define FALSE 0
#define TRUE 1
#define OVERFLOW -2
typedef int Status;
typedef char ElemType;
/**初始化的状态定义end**/
/**二叉树的结构定义start**/
typedef struct CSNode
{
    ElemType data;
    struct CSNode *firstChild;///第一个孩子
    struct CSNode *nextsbling;///该孩子的下一个兄弟
} CSNode,*CSTree;
/**二叉树的结构定义end**/
/**队列定义start**/
typedef CSTree QElemType;
typedef struct QNode
{
    QElemType data;//数据域 
    struct QNode *next;//指针域 
} QNode,*QueuePtr;//链表 
typedef struct
{
    QueuePtr Front;///队头指针
    QueuePtr Rear;///队尾指针
} LinkQueue;
Status InitQueue(LinkQueue &Q)
{
    ///初始化队列
    Q.Front=Q.Rear=(QueuePtr)malloc(sizeof(QNode));
    if(!Q.Front)
        exit(OVERFLOW);///申请内存失败
    Q.Front->next=NULL;
    return OK;
}
Status QueueEmpty(LinkQueue Q) ///判断队列是否为空
{
    if(Q.Front==Q.Rear)
        return TRUE;
    return FALSE;
}
Status EnQueue(LinkQueue &Q,QElemType e) ///插入元素
{
    QueuePtr t=(QueuePtr)malloc(sizeof(QNode));
    if(!t)
        exit(OVERFLOW);
    t->data=e;
    t->next=NULL;
    Q.Rear->next=t;
    Q.Rear=t;
    return OK;
}
Status DeQueue(LinkQueue &Q,QElemType &e)
{
    ///取队头元素赋给e
    if(QueueEmpty(Q))
        return ERROR;///队列为空
    QueuePtr t=Q.Front->next;
    e=t->data;
    Q.Front->next=t->next;
    if(Q.Rear==t)
        Q.Rear=Q.Front;
    free(t);///释放空间
    return OK;
}
/**队列定义end**/
/**二叉树的操作定义start**/
Status CreateTree(CSTree &T) ///创建家谱树
{
    LinkQueue Q;
    InitQueue(Q);///构造队列并且初始化
    char buffChild[20];///用于暂时存放孩子
    memset(buffChild,0,sizeof buffChild);///初始化
    getchar();
    cout<<"请输入根节点(以字符形式输入,#代表空节点):"<<endl;
    scanf("%c",&buffChild[0]);
    ///cout<<buffChild[0]<<"************"<<endl;//debug专用 
    if(buffChild[0]!='#')///如果有第一个孩子 
    {
        T=(CSNode*)malloc(sizeof(CSNode));
        if(!T)
            exit(OVERFLOW);///申请内存失败
        T->data=buffChild[0];
        T->nextsbling=NULL;///根节点没有兄弟节点
        EnQueue(Q,T);///根节点入队
        while(!QueueEmpty(Q))
        {
            QElemType e;
            DeQueue(Q,e);///获取队首元素
            printf("请输入结点%c的孩子(输入的字符串以#结束):",e->data);
            scanf("%s",buffChild);
            if(buffChild[0]!='#') ///有孩子
            {
                CSTree q=(CSTree)malloc(sizeof(CSNode));///开辟孩子节点空间
                if(!q)
                    exit(OVERFLOW);
                q->data=buffChild[0];
                e->firstChild=q;///指向第一个孩子
                EnQueue(Q,q);///将第一个孩子入队
                CSTree p=q;///指向刚入队的孩子
                for(int i=1; i<strlen(buffChild)-1; i++)///依次存入兄弟节点 
                {
                    q=(CSTree)malloc(sizeof(CSNode));
                    if(!q)
                        exit(OVERFLOW);
                    q->data=buffChild[i];
                    p->nextsbling=q;
                    EnQueue(Q,q);///入队
                    p=q;///指向刚入队的孩子
                }
                p->nextsbling=NULL;///最后一个没有后面的兄弟
            }
            else
                e->firstChild=NULL;///没有孩子
        }
    }
    else
        T=NULL;///空树
    return OK;
}
Status TreeEmpty(CSTree T) ///判断以T为根节点的树是否为空
{
    if(T)
        return TRUE;
    else
        return FALSE;
}
CSNode* FindNode(CSTree T,ElemType val)
{
    ///查询值为val的节点 
    LinkQueue Q;
    InitQueue(Q);///构造并初始化队列
    if(T)
    {
        EnQueue(Q,T);
        while(!QueueEmpty(Q))
        {
            QElemType e;
            DeQueue(Q,e);
            if(e->data==val)
                return e;
            if(e->firstChild)
                EnQueue(Q,e->firstChild);
            if(e->nextsbling)
                EnQueue(Q,e->nextsbling);
        }
    }
    return NULL;
}
Status Change(CSTree &T,ElemType val,ElemType upd) ///修改某成员的名字
{
    CSTree p=FindNode(T,val);//找到该成员直接修改 
    if(p==NULL)
        return FALSE;
    p->data=upd;
    return TRUE;
}
CSNode* Parent(CSTree T,ElemType val) ///找父节点
{
    LinkQueue(Q);
    InitQueue(Q);///构造并初始化队列
    if(T)
    {
        if(T->data==val)
            return NULL;///根节点没有父节点
        EnQueue(Q,T);
        while(!QueueEmpty(Q))
        {
            QElemType e;
            DeQueue(Q,e);
            QElemType p=e;///定义为队首元素
            if(e->firstChild) ///如果该节点有孩子
            {
                if(e->firstChild->data==val)
                    return p;///第一个孩子就是所求的
                EnQueue(Q,e->firstChild);
                QElemType bro=e->firstChild->nextsbling;///遍历该孩子的兄弟
                while(bro)
                {
                    if(bro->data==val)
                        return p;///兄弟节点是待求节点
                    EnQueue(Q,bro);
                    bro=bro->nextsbling;
                }
            }
        }
    }
    return NULL;
}
ElemType Insert(CSTree &T,ElemType val,ElemType s) ///插入节点
{
    CSTree q=(CSTree)malloc(sizeof(CSNode));
    if(!q)
        exit(OVERFLOW);
    q->data=s;
    q->firstChild=NULL;
    q->nextsbling=NULL;///孩子节点
    CSNode* node=FindNode(T,val);///找他的双亲节点
    if(node->firstChild) ///已经有第一个孩子了
    {
        node=node->firstChild;
        while(node->nextsbling)
            node=node->nextsbling;
        node->nextsbling=q;
    }
    else
        node->firstChild=q;
}
map<char,int>mp;
Status LevelOrderTraverse(CSTree T)  ///层次遍历
{
    cout<<"层次遍历结果为"<<endl;
    int cnt=1;
    LinkQueue Q;
    InitQueue(Q);
    if(T)
    {
        printf("%c ",T->data); ///访问结点
        mp[T->data]=cnt;
        EnQueue(Q,T);             ///根结点排队
        while(!QueueEmpty(Q))
        {
            QElemType e,p;
            DeQueue(Q,e);
            p = e->firstChild;
            cnt++;
            while(p)
            {
                printf("%c ",p->data);
                mp[p->data]=cnt;
                EnQueue(Q,p);
                p = p->nextsbling;
            }
        }
        puts("");
        return OK;
    }
    return ERROR;
}
ElemType Delete(CSTree &T,ElemType val)
{
    CSNode* node=Parent(T,val);///找到双亲节点
    if(node->firstChild->data==val)
    {
        ///第一个孩子就是待删除的元素
        node->firstChild=node->firstChild->nextsbling;
    }
    else
    {//遍历兄弟节点找待删除元素 
        node=node->firstChild;
        while(node->nextsbling->data!=val)
            node=node->nextsbling;
        node->nextsbling=node->nextsbling->nextsbling;
    }
}
void FindBro(CSTree T,ElemType val)
{
    cout<<"和该人同辈分的有:"<<endl;
    for(map<char,int>::iterator  t=mp.begin(); t!=mp.end(); t++)
        if(t->second==mp[val]&&t->first!=val)
            cout<<t->first<<" ";
    puts("");
}
void FindChirld(CSTree T,ElemType val)
{
    cout<<"该人的孩子有"<<endl;
    for(map<char,int>::iterator t=mp.begin(); t!=mp.end(); t++)
        if(t->second>mp[val])
            cout<<t->first<<" ";
    puts("");
}
/**二叉树的操作定义end**/
/**打印菜单start**/
void showmain()
{
    cout<<"欢迎来到家谱管理系统"<<endl;
    cout<<"请输入您想要进行的操作"<<endl;
    cout<<"1.建立家谱树"<<endl;
    cout<<"2.添加家庭成员"<<endl;
    cout<<"3.修改某家庭成员的姓名"<<endl;
    cout<<"4.删除某家庭成员"<<endl;
    cout<<"5.查询某家庭成员"<<endl;
    cout<<"6.退出系统"<<endl;
}
/**打印菜单end**/
/**菜单的函数主体start**/
void AddPeople(CSTree &T)
{
    cout<<"请输入要添加的人的父亲的姓名"<<endl;
    char fa;
    cin>>fa;
    cout<<"请输入要添加的人的孩子的姓名"<<endl;
    char son;
    cin>>son;
    Insert(T,fa,son);

}
void UpdatePeople(CSTree &T)
{
    cout<<"请输入要修改姓名的人的旧名字"<<endl;
    char old;
    cin>>old;
    cout<<"请输入要修改姓名的人的新名字"<<endl;
    char New;
    cin>>New;
    Change(T,old,New);
}
void DeletePeople(CSTree &T)
{
    cout<<"请输入想要删除的人的姓名"<<endl;
    char del;
    cin>>del;
    Delete(T,del);
}
void FindPeople(CSTree &T)
{
    cout<<"请输入想要查找的人的姓名"<<endl;
    char name;
    cin>>name;
    cout<<"该人处于第"<<mp[name]<<"辈"<<endl;
    LevelOrderTraverse(T);
    FindBro(T,name);
    FindChirld(T,name);
}
/**菜单的函数主体end**/
int main()
{
    CSTree T;
    while(1)
    {
        showmain();
        int op;
        cin>>op;
        if(op==1)
            CreateTree(T);
        else if(op==2)
            AddPeople(T);
        else if(op==3)
            UpdatePeople(T);
        else if(op==4)
            DeletePeople(T);
        else if(op==5)
            FindPeople(T);
        else if(op==6)
            return 0;
        LevelOrderTraverse(T);
    }
    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

4.运行结果：

5.实验心得：

修改后没有更新记录深度的节点的数组的值。在添加成员时只能够添加一个子女。

四、图的操作

1.实验内容：

1.实验目的：
（1）掌握回溯算法；
（2）掌握图的深度优先和广度优先搜索算法并用来解决实际问题；
2.实验内容： 迷宫求解：以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序， 对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。要求如下：
（1）首先实现一个栈类型，利用回溯法求解迷宫路径（非递归程序）。求得的通路以三元组(i,j,d) 的形式输出，其中(i,j)指示迷宫中的一个坐标，d表示走到下一坐标的方向。
（2）建立图的存储结构，利用深度优先搜索，求得迷宫路径。输出方式自行定义，简单清晰则 可。
（3）利用广度优先搜索，求得迷宫路径。输出方式自行定义，简单清晰则可。 （4）假如有多条路径，如何求最短的那一条路径？

2.设计思路：

分为几个方面：
1.迷宫的生成：可以手动输入，也可以借助prim算法生成。
2.非递归借助栈：大体思路还是跟dfs差不多，就是一直往四周走，如果路不通的话就退回上一步的状态，可以借助栈来实现。对于内容所要求的输入，d表示走到下一坐标的方向，在走到这一步时我们并 不能记录这一步在最终路径里的方向，我们只能记录从上一步走到这一步的方向，每次都记录一下方向 然后再入栈就好了。
3.dfs：可以找到迷宫的所有路径，一直走就好了，借助递归实现代码很短。输出路径的话还是借助栈吧。
4.bfs:输出迷宫的最短路径，思想类似于层次遍历，每次用队列维护一下。记录路径的话就记录一下这 个点是从哪个点走过来的，然后从终点递推回去。

3.实验代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;///迷宫的大小：行和列 
int mp[110][110];//地图 
struct node///某个节点：坐标和从哪个点走过来的 
{
    int x,y;
    string dir;
};
bool check(node t)///判断某个节点是否可以走
{
    int x=t.x,y=t.y;
    if(x>=1&&x<=n&&y>=1&&y<=m&&!mp[x][y]) return 1;
    return 0;
}
void init()
{
    ///输入迷宫
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            cin>>mp[i][j];
}
void findpath1()///非递归求解迷宫路径
{
    stack<node>stk;//借助栈 
    node now= {1,1,"0"};//定义工作指针 
    stk.push({1,1,"0"});
    while(!stk.empty())
    {
        node t=stk.top();//每次取出栈内元素 
        if(t.x==n&&t.y==m)//走到了终点 
        {
            break;
        }
        node ne=t;
        mp[t.x][t.y]=2;//走过的点标记为2 

        ne=t;
        ///分别遍历四个方向：如果该方向可走，就将该方向入栈，这时候要更新上一节点的走向，即上一节点如何到达的这节点 
        ne.x--;
        if(check(ne))
        {
            t.dir="up";
            stk.pop();
            stk.push(t);
            stk.push(ne);
            continue;
        }
        ne=t;
        ne.x++;
        if(check(ne))
        {
            t.dir="down";
            stk.pop();
            stk.push(t);
            stk.push(ne);
            continue;
        }
        ne=t;
        ne.y--;
        if(check(ne))
        {
            t.dir="left";
            stk.pop();
            stk.push(t);
            stk.push(ne);
            continue;
        }
        ne=t;
        ne.y++;
        if(check(ne))
        {
            t.dir="right";
            stk.pop();
            stk.push(t);
            stk.push(ne);
            continue;
        }
        t=stk.top();
        stk.pop();
        mp[t.x][t.y]=3;
    }
    ///要倒序输出 
    vector<node>v;
    while(!stk.empty())
    {
        v.push_back(stk.top());
        stk.pop();
    }
    reverse(v.begin(),v.end());
    for(int i=0; i<v.size(); i++) cout<<v[i].x<<" "<<v[i].y<<" "<<v[i].dir<<endl;
}

stack<node>path,tmp;//存储最终路径和暂时路径 
int nx[]= {0,0,1,-1};//方向函数 
int ny[]= {1,-1,0,0};
int vis[110][110];//标记数组 
int cnt=0;//记录有多少条路径 
void findpath2(int x,int y) ///dfs求解迷宫所有路径
{
    if(x==n&&y==m)//到达终点 
    {
        cout<<"***************路径"<<++cnt<<"*****************"<<endl;
        while(!path.empty())//输出路径 
        {
            tmp.push(path.top());
            path.pop();
        }
        while(!tmp.empty())
        {
            cout<<"("<<tmp.top().x<<","<<tmp.top().y<<")"<<endl;
            path.push(tmp.top());
            tmp.pop();
        }
        return ;
    }
    if(x<1||x>n||y<1||y>m) return ;
    for(int i=0; i<4; i++)//遍历四个方向 
    {
        int xx=x+nx[i],yy=y+ny[i];
        if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!mp[xx][yy]&&vis[xx][yy]==0)
        {//合法就走 
            vis[xx][yy]=1;
            path.push({xx,yy});
            findpath2(xx,yy);
            vis[xx][yy]=0;
            path.pop();
        }
    }
}
queue<node>q;
int dis[110][110],fx[110][110],fy[110][110];
void Prinpath3(int x,int y)///bfs打印路径 递归打印
{
    if(x!=-1&&y!=-1)
    {
        Prinpath3(fx[x][y],fy[x][y]);
        cout<<"("<<x<<","<<y<<")"<<endl;
    }
}
void findpath3()///bfs求解最短路径
{
    memset(dis,-1,sizeof dis);///初始化距离数组
    q.push({1,1});///将起始点放入队列
    dis[1][1]=0;///初始化距离
    fx[1][1]=fy[1][1]=-1;///表示这个点的上一个点的坐标
    while(!q.empty())//每次取出队列元素扩展 
    {
        node now=q.front();
        q.pop();
        for(int i=0; i<4; i++)
        {
            node nex;
            nex.x=now.x+nx[i],nex.y=now.y+ny[i];
            if(check(nex)&&dis[nex.x][nex.y]==-1)
            {
                q.push(nex);
                dis[nex.x][nex.y]=dis[now.x][now.y]+1;//相当于层次遍历的拓展 
                fx[nex.x][nex.y]=now.x;//记录这个节点是由哪个节点走过来的 
                fy[nex.x][nex.y]=now.y;
            }
        }
    }
    Prinpath3(n,m);//递归打印路径 
}
int main()
{
    init();
  // findpath1();
   //  findpath2(1,1);
     findpath3();
    return 0;
}
/*
3 3
0 1 1
0 1 1
0 0 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

4.运行结果：

5.实验心得：

五、排序算法的应用

1.实验内容：

1.实验目的：
（1）熟练掌握常用的内排序方法并加以比较。
2.实验内容： 利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。要求：
（1）至少采用三种方法实现上述问题求解（提示，可采用的方法有希尔排序、起泡排序、快速排 序、选择排序、堆排序）。并把排序后的结果保存在不同的文件中。
（2）统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种 较快的方法。

2.设计思路：

1.关于数据的生成和运行程序花费的时间的计算： 前者用随机数来生成，要记得在main函数里加上随机数种子；后者借助 clock_t 变量和 clock()函数来计 算；
2.冒泡排序：O（n^2）
两层for循环比较，每次将最小的或最大的移动到开头或结尾。
3.快速排序：O（nlgn）
每次选择一个基准，将比他小的放到前面，比他大的放到后面，在递归处理左右两部分即可。每次都将排序的范围变为原来的一半，提高效率。
4.希尔排序： O(n^(1.3—2))
插入排序的一种高效改进版本。每次都将下标间距相同的元素进行排序，使得部分有序，提高效率。

3.实验代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=20000+100;
int a[maxn],n,b[maxn];
void sortloop(int n,int *b)///冒泡排序 
{
    for(int i=1; i<n; i++)
    {
        for(int j=i+1; j<=n; j++)
            if(b[i]>b[j]) swap(b[i],b[j]);
    }
}
void sortquick(int l,int r,int *b)//快速排序 
{
	//每次选择一个基准元素，将比他小的移动到他的前面，比他大的移动到他的后面不
	//具体实现就是设置首尾指针，每次都分别移动两个指针，当需要修改元素位置时一定会有一个元素的位置空出来，赋值即可 
  	//然后基准元素的位置就一定确定了，在分别递归求解左右两部分即可 
    if(l<r)
    {
        int val=b[l];
        int low=l,high=r;
        while(low<high)
        {
            while(b[high]>=val&&low<high) high--;
            b[low]=b[high];
            while(b[low]<=val&&low<high) low++;
            b[high]=b[low];
        }
        a[low]=val;
        sortquick(l,low-1,b);///注意边界的处理 
        sortquick(low+1,r,b);
    }
}
void sortshell(int n,int *b){///希尔排序
//每次都将下标间距相同的元素进行排序，直到间距为1 
    /*for(int gap=2*n;gap;gap=gap/2){//枚举间距 
        for(int i=gap;i<=n;i++){//枚举元素 
            for(int j=i-gap;j>=1;j-=gap){//枚举该元素之前的元素 
                if(b[j]>b[j+gap]) swap(b[j],b[j+gap]);///暴力比较 不优化
            }
        }
    }*/
    for(int gap=2*n;gap;gap=gap/2){///枚举间距 
        for(int i=1;i<=gap;i++){///gap组
            for(int j=i+gap;j<=n;j+=gap){//枚举第一个元素 
                if(b[j]<b[j-gap]){///依次往后遍历的时候比较和之前的元素 借助单调栈的原理 
                    int tmp=b[j],q=j-gap;
                    while(q>=1&&b[q]>tmp){
                        b[q+gap]=b[q];q-=gap;
                    }
                    b[q+gap]=tmp;
                }
            }
        }
    }
}
int main()
{
    srand(time(0));//随机数种子
    clock_t s,e;
    n=10000;
    ///n=(rand()*rand()+rand())%20000+1;///随机生成数组的长度
    for(int i=1; i<=n; i++)
    {
        a[i]=(rand()*rand()+rand())%10000+1;///随机生成数组内的元素
        b[i]=a[i];///拷贝
    }
    s=clock();///计算代码运行时间
    sortloop(n,b);
    e=clock();
    cout<<"冒泡排序花费的时间为:"<<(double(e-s)/CLOCKS_PER_SEC)<<"s\n";

    s=clock();///计算代码运行时间
    for(int i=1; i<=n; i++) b[i]=a[i];
    sortquick(1,n,b);
    e=clock();
    cout<<"快速排序花费的时间为:"<<(double(e-s)/CLOCKS_PER_SEC)<<"s\n";

    s=clock();///计算代码运行时间
    for(int i=1; i<=n; i++) b[i]=a[i];
    sortshell(n,b);
    e=clock();
    cout<<"希尔排序花费的时间为:"<<(double(e-s)/CLOCKS_PER_SEC)<<"s\n";

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87