数据结构课程设计

数据结构课程设计(数据构造课程设计(

一、设计目的

1.1问题描述：

任意给定一个M进制的数x，请实现如下要求：

１、对给字一个M进制的数据x，求出此数x的10进制值(用MD表示)；２、实现对x向任意的一个非M进制的数的转换；

1.2问题分析：

１、用串实现该问题：

⑴m,n,x是定义的全局变量；

⑵Loop循环是实现M进制数转换为10进制；

⑶trans()是实现10进制数转换为n进制数的函数;(4)voidmain()是主函数，功能是给出测试的数据，并在特定条件下调用trans()

函数。

２、用栈实现该问题：

⑴SeqStack定义栈，top为栈顶指针；

⑵intInitStack(SqStackinti;for(i=0;n>0;i++)

{if(n%m0;n--){printf(“%c“,str[n-1]);}}

voidmain()

{intm,n,x;charch;

printf(“geidingjingzhiM---“);scanf(“%d“,loop:

printf(“geidingyige%djinzhideshuX---“,m);fflush(stdin);//一个M进制的数X转10进制for(x=0;;){ch=getchar();

if(ch>=“0“}x=x*m+n;}

printf(“zhuanhuacheng10jinzhideshuwei---%d\\n“,x);printf(“geidingyaozhuanhuachengdejinzhiN---“);scanf(“%d“,

printf(“zhuanhuacheng%djinzhihoudejieguo---“,m);trans(x,m);printf(“\\n“);}

栈转换：

#include#include#defineStack_Size20typedefintElemType;//挨次栈存储类型typedefstruct

{ElemTypeelem[Stack_Size];inttop;}SeqStack;

//初始化：为未初始化的挨次栈S设置栈顶指针voidInitStack(SeqStack*S)

{S->top=-1;printf(“kongzhanS=()\\n“);}//判空栈：推断栈S是否为空栈intIsEmpty(SeqStack*S)

{if(S->top==-1)return1;elsereturn0;}//判栈满：推断栈S是否为满栈intIsFull(SeqStack*S)

{if(S->top==Stack_Size-1)return1;elsereturn0;}//进栈：向S栈顶压入一个数据元素intPush(SeqStack*S,ElemTypex){if(IsFull(S))return0;S->top++;S->elem[S->top]=x;return1;}//出栈：弹出S的栈顶元素，并用x返回intPop(SeqStack*S,ElemType*x){

if(IsEmpty(S))return0;*x=S->elem[S->top];S->top--;return1;}

//销毁栈S

voidClearStack(SeqStack*S)

{free(S);printf(“zhanxiaohui\\n“);}

voidmain()

{charx[20];intMx;intM;

intm;intX=0;intt;inti,length;

SeqStack*S=(SeqStack*)malloc(sizeof(SeqStack));InitStack(S);

printf(“qingshurujinzhiheshu:“);scanf(“%d,%s“,t=1;

length=strlen(x);

for(i=0;i=“a“elseprintf(“%d“,m);}

printf(“\\n“);ClearStack(S);}

三、运行结果

1、2进制的111的10进制值，转换成3进制的测试状况如下（栈实现）：

2、7进制的236的10进制值，转换成9进制的测试状况如下（串实现）：

四、总结与展望

在这次课程设计中使我们明白在遇到一个大的程序，不知道该如何下手时，只有找多方面的资料，加强思索力量。做这次数制转换的课程设计是我知道了只有在细节方面需要娴熟运用栈、数组、串，这样才可以。

通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论学问是远远不够的，只有把所学的理论学问与实践相结合起来，从理论中得出结论，才是真正的学问，才能提高自己的实际动手力量和独立思索的力量。通过课程设计的训练，我进一步学习和把握了对程序的设计和编写，从中体会到了数据构造的便利和奇妙。

扩展阅读：数据构造课程设计报告

数据构造课程设计试验报告

名目

1.单位员工通讯录治理系统（线性表的应用）*********************22.停车场治理（栈和队列的应用）*******************************43.哈夫曼编码/译码系统（树应用）******************************64.教学规划编制问题（图的应用）*******************************85.药店的药品销售统计系统（排序应用**************************116.最小生成树问题（**）**************************************137．总结*******************************************************158．源代码*****************************************************1、单位员工通讯录治理系统（线性表的应用）

[需求分析]

为某个单位建立一个员工通讯录治理系统，可以便利查询每一个员工的办公室电话、手机号、及电子邮箱。其功能包括通讯录链表的建立、员工通讯信息的查询、修改、插入与删除、以及整个通讯录表的输出。[问题分析]

为建立单位员工通讯录系统，首先要实现员工信息的录入、保存等根本操作。对于员工通讯录我们要存入要求的员工的各种信息等，对于已经保存的信息，我们要可以对这些信息进展查询、修改、插入新信息、删除信息、还有可以直接输出整个全部员工信息等。而这些操作对于我们来说都是对建立的链表的根本操作，对于本次试验我采纳单向线性链表。[算法设计]

首先我们要进展最根本的操作，即建立链表。链表的节点信息保存的有员工编号、员工姓名、办公室电话号码、手机号码、员工邮箱这些信息。而链表的结点信息保存的有员工信息以及其指针域。然后我们可以添加员工信息，对于新的员工信息我们将其添加在链表的表尾，在添加之前我们要进展一项操作，即遍历链表找到其尾指针，然后开拓一个结点并将其加到链尾。我们还可以进展员工信息的查询操作，在进展查询时我们首先要遍历链表，然后在遍历的同时与关键字进展比拟从而找到员工信息并输出。员工信息删除操作，此操作首先要找到要删除的员工信息，然后将此节点的前一节点的后续指针直接指向要删除的结点的后续指针，并且释放要删除的结点空间即可。员工信息修改，首先找到要修改的员工，然后输入要修改的员工信息，将输入信息直接掩盖在原有信息上即可。员工信息输出，遍历整个链表并输出。

流程图如下：

.5.员工信息查询员工信息插入员工信息修改员工信息删除员工信息输出2

开头建立员工信息链表

中项

完毕全部操作或者返回重新选择操作.5

[调试分析及测试数据]

员工信息插入：

员工信息查询：

员工信息删除：

员工信息修改：

2、停车场治理（栈和队列的应用）

[需求分析]

设停车场是一个可以停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后挨次，依次有北向南排列（大门在最

南端，最先到达的第一车停放在车场的最北端），若车场内已停满n辆车，那么后来的车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必需先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必需按它停留的时间长短交纳费用。试为停车场编制按上述要求进展治理的模拟程序。[问题分析]

停车场停车系统，首先来的车辆要进入停车厂或者进入便道。当停车场车辆未满时直接将车停入停车场。当停车场车辆停满时，则此时进入的车辆应当进入便道。然后等待停车场中的车辆离去，离去一辆车则便道中的车辆进入停车场。[算法设计]

此算法用到了栈和队列，在栈中保存停车场车辆，在队列中保存便道中车辆，本试验要定义一个队列两个栈，其中一个栈可以帮助停车场中的车辆离开，即离开一辆车时，在此车前面的车依次进入帮助栈，离开后这些车辆再进入停车栈，然后推断队列中是否有车，假如有则将便道队列中的车辆移进停车厂。否则不进展操作。本试验主要运用的就是对栈和队列的根本操作。流程图如下：

[调试分析及测试数据]

完毕1.进车2.出车初始化栈和队列可以反复选择进展重复操作开头

3、哈夫曼编码/译码系统（树应用）

[需求分析]

利用哈夫曼编码进展通信，可以压缩通信的数据量，提高传输效率，缩短信息的传输时间，还有肯定的保密性。现在要求编写一程序模拟传输过程，实现在发送前将要发送的字符信息进展编码，然后进展发送，接收后将传来的数据进展译码，马上信息复原成发送前的字符信息。[问题分析]

在本例中设置发送者和承受者两个功能，发送者的功能包括：①输入待传送的字符信息；

②统计字符信息中消失的字符种类数和各字符消失的次数（频率）；②依据字符的种类数和各自消失的次数建立哈夫曼树；③利用以上哈夫曼树求出各字符的哈夫曼编码；④将字符信息转换成对应的编码信息进展传送。承受者的功能包括：

①接收发送者传送来的编码信息；

②利用上述哈夫曼树对编码信息进展翻译，马上编码信息复原成发送前的字符信

息。

从以上分析可发觉，在本例中的主要算法有三个：（1）哈夫曼树的建立；（2）哈夫曼编码的生成；（3）对编码信息的翻译。

本试验首先从文件中读取数据，然后分析数据，对不同的元素依次存入一字符数组并统计其消失的次数并当做其权值，然后依据这些信息建立哈弗曼树，并对各个字符进展哈弗曼编码，然后依据各个字符的编码对全部输入的一组字符进展哈弗曼编码。译码是依据哈弗曼树和接收到的一组编码进展译码操作。译码也就是对哈弗曼树的遍历。[算法设计]

首先读入一组字符，然后统计这些字符中不同字符消失的次数，并当做其权值，然后依据不同字符及其权值建立哈弗曼树。建立哈弗曼树后即可得到这些不同字符的哈弗曼编码，然后即可依据这些哈弗曼编码对那组输入的一串字符进展哈弗曼编码。译码是依据一组编码翻译成一组字符的操作，其算法就是依据这一串编码来对哈弗曼树进展遍历，每遍历到一个叶子结点即输出一个字符，直至将编码操作完即可完成多编码的翻译操作。[调试分析及测试数据]

4、教学规划编制问题（图的应用）

[需求分析]

大学的每个专业都要制定教学规划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必需满意先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这

样的前提下设计一个教学规划编制程序。

1、输入参数应包括：学期总数，一学期的学分上限，每门课的课程号（可以是固定占3位的字母数字串）、学分和直接先修课的课程号。2、应允许用户指定以下两种编排策略之一：一是使学生在各学期中的学习负担尽量匀称；二是使课程尽可能地集中在前几个学期中。

3、若依据给定的条件问题无解，则报告适当的信息；否则将教学规划输出到用户指定的文件中。规划的表格格式可以自己设计。

4、可设学期总数不超过12，课程总数不超过100。假如输入的先修课程号不在该专业开设的课程序列中，则作为错误处理。

[问题分析]

编制教学规划，固然涉及到的课程都要给学完。所以我们可以将所以的课程编制成一张图，然后遍历图。由于课程有前续后继的关系，所以用AOV网是最适宜。对AOV网进展拓扑排序即可以得出结果。对AOV网进展拓扑排序有两种状况：广度优先和深度优先。在进展深度优先周游时，我们要考虑到一种状况。例如：高等数学和C语言编程是并列的两门学科，他们之间没有前续后继的关系，可以同时进展学习。高等数学是数值分析和电子电路的根底课程，电子电路又是模拟电子电路的根底课程。C语言编程是数据构造的根底课程，数据构造是算法设计与分析的根底课程。假如根据深度优先周游的话就有可能将上面几门课程排成：C语言程序设计，数据构造，算法设计与分析，高等数学，电子电路，模拟电子电路。这样的教学规划很明显不符合实际教学的需要。因此我们应当进展广度优先周游，将高等数学和C语言程序设计先学，再学其他后继课程。[算法设计]

首先确定学期数和每学期的学分总数上限，不能一学期将许多课全部学完。然后依据输入的规划课程树和输入的拓扑排序所形成的课程先修关系建立拓扑图。有向图G采纳邻接表存储构造。若G无回路,则输出G的顶点的一个拓扑序列并返回OK，否则返回ERROR。[调试分析及测试数据]

5、药店的药品销售统计系统（排序应用）

[需求分析]

设计一系统，实现医药公司定期对销售各药品的记录进展统计，可按药品的编号、单价、销售量或销售额做出排名。[问题分析]

在本设计中，首先从数据文件中读出各药品的信息记录，存储在挨次表中。各药品的信息包括：药品编号、药名、药品单价、销出数量、销售额。药品编号共4位，采纳字母和数字混合编号，如：A125，前一位为大写字母，后三位为

数字，按药品编号进展排序时，可采纳基数排序法。对各药品的单价、销售量或销售额进展排序时，可采纳多种排序方法，如直接插入排序、冒泡排序、快速排序，直接选择排序等方法。在本设计中，对单价的排序采纳冒泡排序法，对销售量的排序采纳快速排序法，对销售额的排序采纳堆排序法。[算法设计]

首先从txt文件中读取数据信息并保存，本次试验采纳了5中排序方法。其中编号排序是根据基数排序，采纳多关键字进展排序。基数排序是借助“安排”和“收集”两种操作对单规律关键字进展排序的一种内部排序方法。对单价的排序采纳了直接插入排序和冒泡排序，直接插入排序就是首先将第一个元素看成是一个有序的，然后其次个元素和第一个比拟，若大于第一个则放在其后面否则放前面，依次直至最终一个。冒泡排序就是采纳两个循环，马上第一个元素和其次个比拟若第一个大于其次个则交换，否则不变，然后其次个和第三个比拟，同上。第一趟可将最大的一个放在最终，依次可得排序。销售量是快速排序，快速排序就是首先设置一个关键字，然后让最终一个和其比拟，直至找到一个比关键字小的，然后和其交换，接下来让第一个和其比拟，直至找到一个比其大的，然后交换，在找到的位置分别做标记，依次执行即可。销售额使用的是堆排序，堆排序首先要建立一个完全二叉树的堆，其标准符合为父节点始终比子节点大。然后依次输出顶结点，然后在建立一个符合标准的堆重复操作即可。[调试分析及测试数据]

6、最小生成树问题（**）

【需求分析】

若要在n个城市之间建立通信网络，只需要假设n-1条线路即可。如何以最低的经济代价建立这个通信网，是一个网的最小生成树问题。[问题分析]

利用克鲁斯卡尔算法求网的最小生成树。利用普里姆算法求网的最小生成树。要求输出各条边及它们的权值。通信线路一旦建成，必定是双向的。因此，构造最小生成树的网肯定是无向网。设图的顶点数不超过30个，并为简洁起见，网中边的权值设成小于100的整数，可利用C语言供应的随机函数产生。图的存储构造的选取应和所作操作相适应。为了便于选择权值最小的边，此题的存储构造既不选用邻接矩阵的数组表示法，也不选用邻接表，而是以存储边（带权）的数组表示图。

[算法设计]

Kruskal算法要选择n-1条边，所使用的贪欲准则是：从剩下的边中选择一条不会产生环路的具有最小消耗的边参加已选择的边的集合中。留意到所选取的边若产生环路则不行能形成一棵生成树。Kruskal算法分e步，其中e是网络中边的数目。按消耗递增的挨次来考虑这e条边，每次考虑一条边。当考虑某条边时，若将其参加到已选边的集合中会消失环路，则将其抛弃，否则，将它选入。Prim首先任意选取一个顶点放入到最小生成树中去，然后分别在最小生成树的内外各选取一个定点顶点，要求这两个顶点之间的权重是最小的。然后将最小生成树外的这个顶点参加到最小生成树中去，而这条边就做为最小生成树的一条边。重复以上操作，最终将顶点全部包含在最小生成树之中为止

[调试分析及测试数据]

[总结]

做了两个星期的程序设计最终做完了，在这次程序设计课中，真是让我获益匪浅，我突然发觉写程序还挺有意思的。

由于上学期的C++语言跟这学期的数据构造都算不上真正的懂，对于书上的略微难点的学问就是是而非的，所以我只是对教师的程序理解，我也试着去转变了一些变量，自己也尽量多的去理解教师做程序的思路。当我第一天坐在那里的时候，我就不知道该做些什么，后来我只有下来自己看了一遍书来熟识下以前学过的学问。

通过这次的程序设计，发觉一个程序设计就是算法与数据构造的结合体，自己也开头对程序产生了前所未有的兴趣，以前偷工减料的学习也不行能一下子写出一个程序出来，于是我就仔细看教师写的程序，发觉我们看懂了一个程序其实不难，难的是对于一个程序的思想的理解，我们要把握一个算法，不仅仅限于读懂，主要的是要理解教师的思路，学习教师的解决问题的方法。

这次试验中，我发觉书本上的学问是一个根底，但是我根底都没把握，更别说写出一个整整的程序了。自己在写程序的时候，也发觉自己的学问太少了，特殊是根底学问许多都是模模糊糊的一个概念，没有落实到真正的程序，所以自

己写的时候也感到万分苦痛，根本上涉及一个学问我就会去看看书，对于书本上的学问没把握好。在饭后闲暇时间我也总结了一下，自己以前上课也仔细的听了，但是还是写不出来，这主要归结于自己的练习太少了，而且也总是半懂就不管了。在改写教师的程序中也消失了许多的问题，不断的修改就是不断的学习过程，当我们全身心的投入其中时，实际上是一件很有乐趣的事情。对于以后的学习有了几点总结：第一、熟记各种数据构造类型，定义、特点、根本运算（分开点一点也没多少东西，难度不大，但是根本）；其次、各种常用的排序算法，如冒泡排序、堆排序……，这些是必考的内容，分数不会少于20%；第三，多做习题，看题型，针对题型来有选择复习；数据构造看上去很简单，但你静下心来把书扫上几遍，分解各个学问点，这一下来，学数据构造的思路就会很清楚了。

1.#include#includeusing

namespacestd;typedefstruct{/*员工通讯信息的构造类型定义*/char

num[20];/*员工编号*/charname[20];/*员工姓名*/charphone[20];/*办公室电话号码*/charcall[20];/*手机号码*/charemail[20];//员工邮

箱}DataType;/*通讯录单链表的结点类型*/typedefstructnode

{DataTypedata;/*结点的数据域*/

structnode*next;/*结点的指针域

*/}ListNode,*LinkList;LinkListlist=newListNode;voidchushihua(LinkListlist){ListNode*p=newListNode;strcpy(p->data.call,);

strcpy(p->data.email,“1@163.com“);

strcpy(p->,“lvdezhou“);

strcpy(p->data.num,“201*1“);

strcpy(p->data.phone,“1314111“);

list->next=p;p->next=NULL;vo

aa=list->next;coutbh;

do{if(!(strcmp(bh,aa->data.num))){

cout}while(aa->next!=NULL,aa=aa->next);}void

yuangongxinxicharu(LinkListlist){

ListNode*w;w=list->next;while(w->next!=N

ULL)

{w=w->next;}

ListNode*u=newListNode;

u->next=NULL;

coutu->data.call;coutu->data.email;coutu->;coutu->data.num;coutu->data.phone;w->next=u;w=w->

next;}

voidshanchu(LinkListlist){

ListNode*cz1;ListNode*cz2;ListNode*cz3;cz1=list;

cz2=list;

ints=0;

charchax[20];

coutchax;

while((strcmp(chax,cz1->data.num))){

s++;cz1=cz1->next;

}for(intj=0;jnext;

}cz3=cz2->next;cz2->next=cz3->next;}

voidxiugai(LinkListlist){

ListNode*xiug;

ListNode*zans;zans=list->next;

coutbh;

do{if(!(strcmp(bh,zans->data.num))){

xiug=newListNode;

coutvoidjiemian(LinkListlist){

intxuhao=0;

coutcout>chu;

S.top--;

while(strcmp(S.top->name,chu)){

*(q.top)=*(S.top);q.top++;

S.top--;}

coutSqStackq;//备用栈，用来帮助车的进出//便道用队列进展操作，假设停车每天不超过辆

}HTNode,*HuffmanTree;

HuffmanTreep;inti;

typedefchar**HuffmanCode;

voidtongji(char*d1,intfor(p=HT+1,i=1;irchild=0;

p->weight=*w;}

for(;ilchild=p->parent=p->rchild=0;

p->weight=0;

}for(i=n+1;iif(HT[t].parent==0break;}

for(t=t+1;tHT[t].weight

}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;}HC=newchar*[n+1];char*cd=newchar[n];

cd[n-1]=“\\0“;intstart,c,f;for(i=1;i

HuffmanCoding(HT,HC,w,n,d);

cout/*图的邻接表存储的根本操作*/int

LocateVex(ALGraphG,VertexTypeu)

{/*初始条件:图G存在,u和G中顶点有一样特征*/

/*操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1*/

inti;

for(i=0;i

{p=G.vertices[i].firstarc;

while(p){printf(“%s→%s“,G.vertices[i].data,G.vertices[p->adjvex].data);#define

STACK_INIT_SIZE10/*存储空间初始安排量*/#define

STACKINCREMENT2/*存储空间安排增量*/

typedefstructSqStackvoid

ClearStack(SqStack*S)//清空栈的操作

{S->top=S->base;}Status

StackEmpty(SqStackS)

p=p->nextarc;}printf(“\\n“);}}void

FindInDegree(ALGraphG,intindegree[])

{/*求顶点的入度，算法调用*/

inti;ArcNode*p;

for(i=0;inextarc;}}}typedefint

SElemType;/*栈类型*/

/*栈的挨次存储表示*/

{SElemType*base;/*在栈构造之前和销毁之后，base的值为NULL*/SElemType*top;/*栈顶指针*/

intstacksize;/*当前已安排的存储空间，以元素为单位*/

}SqStack;/*挨次栈*/

/*挨次栈的根本操作*/

Status

InitStack(SqStack*S)

{/*构造一个空栈S*/

(*S).base=(SElemType

*)malloc(STACK_INIT_SIZE*sizeof(SElemType));

if(!(*S).base)

exit(OVERFLOW);/*存储安排失败*/

(*S).top=(*S).base;

(*S).stacksize=STACK_INIT_SIZE;

returnOK;}

{/*若栈S为空栈，则返回TRUE，否则返回FALSE*/

if(S.top==S.base)returnTRUE;else

returnFALSE;}StatusPop(SqStack*S,SElemType*e)

{/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/

if((*S).top==(*S).base)

returnERROR;*e=*--(*S).top;returnOK;}StatusPush(SqStack*S,SElemTypee)

{/*插入元素e为新的栈顶元素*/

if((*S).top-(*S).base>=(*S).stacksize)/*栈满，追加存储空间*/

{(*S).base=(SElemType

*)realloc((*S).base,((*S).stac

ksize+STACKINCREMENT)*sizeof

(SElemType));pathtwob;ArcN