数据结构课程设计课件

课课 程程 设设 计计时间：时间：二周。二周。完成方式：完成方式：一人一题。一人一题。考核方式：考核方式：考查。考查。考核形式：考核形式：检查：上机运行、检查结果；检查：上机运行、检查结果；答辩：对程序提问、回答问题；答辩：对程序提问、回答问题；提交：原程序清单、课程设计报告。提交：原程序清单、课程设计报告。成绩评定方式：成绩评定方式：按上机调试情况、运行结果和答辩按上机调试情况、运行结果和答辩情况、课程设计报告三方面评定。情况、课程设计报告三方面评定。成绩评定档次：成绩评定档次：优、良、中、及格、不及格。优、良、中、及格、不及格。文档要求文档要求课程设计报告按教务处指定的格式填写打印。课程设计报告按教务处指定的格式填写打印。1 1 封面封面2 2 课程设计任务书课程设计任务书3 3 课程设计鉴定表课程设计鉴定表4 4 目录目录 要求给出标题及页次。要求给出标题及页次。5 5 课程设计的目的课程设计的目的6 6 课程设计任务与要求课程设计任务与要求7 7 设计思想及实现要点设计思想及实现要点8 8 系系统统测测试试 说说明明程程序序调调试试过过程程中中出出现现的的问问题题及及解决的方法。解决的方法。9 9 操作说明操作说明 说明使用本软件的操作方法。说明使用本软件的操作方法。10 10 总总结结 在在总总结结中中可可谈谈本本人人的的心心得得体体会会及及软软件件进一步改进的方向等项内容。进一步改进的方向等项内容。11 11 参考文献参考文献12 12 附录附录题目1 1 一元多一元多项式式计算器算器问题描述：问题描述：设计一个稀疏多项式简单计算器设计一个稀疏多项式简单计算器基本要求：基本要求：(1)(1)输入并分别建立多项式输入并分别建立多项式A A和和B B。(2)(2)输入输出多项式，输出形式为整数序列：输入输出多项式，输出形式为整数序列：n,cn,c1 1,e,e1 1,c,c2 2,e,e2 2，其其中中n n是是多多项项式式的的项项数数，c ci i和和e ei i是是第第i i项项的的系系数数和指数，序列按指数降序排列。和指数，序列按指数降序排列。(3)(3)完成两个多项式的相加、相减，并将结果输出。完成两个多项式的相加、相减，并将结果输出。测试数据：测试数据：(1)A+BA=3x14-8x8+6x2+2；B=2x10+4x8+-6x2(2)A-BA=11x14+3x10+2x8+10 x6+5；B=2x14+3x8+5x6+7(3)A+BA=x3+x1；B=-x3-x1(4)A+BA=0；B=x7+x5+x3+x1(5)A-BA=100 x100+50 x50+20 x20+x；B=10 x100+10 x50+10 x20+x选作内容：选作内容：（1 1）多项式在）多项式在x=1x=1时的运算结果；时的运算结果；（2 2）求多项式）求多项式A A和和B B的乘积。的乘积。题目2 2 迷迷宫问题 问题描述：描述：以一个以一个m*nm*n的长方阵表示迷宫，的长方阵表示迷宫，0 0和和1 1分别表示迷宫分别表示迷宫中的通路和障碍。迷宫问题要求求出从入口（中的通路和障碍。迷宫问题要求求出从入口（1 1,1 1）到）到出口（出口（m,nm,n）的一条通路，或得出没有通路的结论。的一条通路，或得出没有通路的结论。基本要求：基本要求：首先实现一个以链表作存储结构的栈类型，然后编首先实现一个以链表作存储结构的栈类型，然后编写一个求迷宫问题的非递归程序，求得的通路以三元组写一个求迷宫问题的非递归程序，求得的通路以三元组（i,j,d）的形式输出，其中：（的形式输出，其中：（i，j）指示迷宫中的一指示迷宫中的一个坐标，个坐标，d表示走到下一坐标的方向。表示走到下一坐标的方向。测试数据：测试数据：左上角（左上角（1 1,1 1）为入口，右下角（）为入口，右下角（m,nm,n）为出口。为出口。选作内容：选作内容：（1 1）编编写写递递归归形形式式的的算算法法，求求得得迷迷宫宫中中的的所所有有可可能能的通路；的通路；（2 2）以以方方阵阵的的形形式式输输出出迷迷宫宫及及其其通通路路迷迷宫宫中中的的所所有有可能的通路；可能的通路；题目3 3 二叉排序树的应用二叉排序树的应用 问题描述：问题描述：利用二叉排序树对顺序表进行排序。利用二叉排序树对顺序表进行排序。基本要求：基本要求：（1 1）生成一个顺序表）生成一个顺序表L;L;（2 2）对所生成的顺序表对所生成的顺序表L L构造二叉排序树构造二叉排序树;（3 3）利用栈结构实现中序遍历二叉排序树）利用栈结构实现中序遍历二叉排序树;（4 4）中中序序遍遍历历所所构构造造的的二二叉叉排排序序树树将将记记录录由由小小到到大输出。大输出。测试数据：测试数据：用伪随机数产生程序产生随机数，用伪随机数产生程序产生随机数，表长不小于表长不小于2020。选作内容：选作内容：实现二叉排序树的插入和删除操作。实现二叉排序树的插入和删除操作。问题描述：问题描述：设计一个交通咨询系统，为自驾游旅行者客咨询从任设计一个交通咨询系统，为自驾游旅行者客咨询从任一个城市到另一个城市之间的最短路径问题。设计分三一个城市到另一个城市之间的最短路径问题。设计分三个部分，一是建立交通网络图的存储结构；二是解决单个部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现两个城市顶点之间的最短源最短路径问题；最后再实现两个城市顶点之间的最短路径问题。路径问题。基本要求：基本要求：1对城市信息对城市信息(城市名、城市间的里程城市名、城市间的里程)进行编辑：具进行编辑：具备添加、修改、删除功能；备添加、修改、删除功能；2咨询以用户和计算机对话方式进行，要注意人机交咨询以用户和计算机对话方式进行，要注意人机交互的屏幕界面。由用户选择输入起点、终点，输出信息：互的屏幕界面。由用户选择输入起点、终点，输出信息：旅行者从起点、终点经过的每一座城市。旅行者从起点、终点经过的每一座城市。3.主程序可以有系统界面、菜单；也可用命令提示方主程序可以有系统界面、菜单；也可用命令提示方式；选择功能模块执行，要求在程序运行过程中可以反式；选择功能模块执行，要求在程序运行过程中可以反复操作。复操作。题目4 4 交通咨询系统交通咨询系统测试数据：测试数据：参考参考数据结构（数据结构（C语言版）语言版）（严蔚敏（严蔚敏 吴伟民吴伟民编著）编著）7.6节图节图7.33的交通图。的交通图。答辩测试数据：北京到乌鲁木齐；北京到昆明；答辩测试数据：北京到乌鲁木齐；北京到昆明；广州到哈尔滨；乌鲁木齐到南昌；沈阳到昆明。广州到哈尔滨；乌鲁木齐到南昌；沈阳到昆明。选作内容：选作内容：考虑由于路况不同，不同城市间自驾旅行每百公考虑由于路况不同，不同城市间自驾旅行每百公里油耗不同，为旅行选择最经济路线。里油耗不同，为旅行选择最经济路线。题目5 5 内部排序算法的比内部排序算法的比较 问题描述：描述：通过比较各通过比较各内部排序算法的关键字比较次数和关内部排序算法的关键字比较次数和关键字移动的次数，键字移动的次数，以取得直观感受。以取得直观感受。基本要求：基本要求：1、待待排序表的表长不小于排序表的表长不小于100100；2 2、至少要用、至少要用5 5组不同的输入数据作比较；组不同的输入数据作比较；3 3、排序算法不少于、排序算法不少于5 5种；种；4 4、最后要对结果作简单的分析。、最后要对结果作简单的分析。测试数据：测试数据：用伪随机数产生程序产生。用伪随机数产生程序产生。选作内容：选作内容：对不同的表长做试验分析两个指标相对于表长变对不同的表长做试验分析两个指标相对于表长变化关系。化关系。实实 现现 要要 点点 多项式相加多项式相加p(x)=3x148x8+6x2+2q(x)=2x10+4x86x2 p(x)p(x)+q(x)结果：结果：p(x)=3x14+2x104x8+2 题目1 1 多项式的算术运算多项式的逻辑结构：视为线性表多项式的逻辑结构：视为线性表p p(x x)=3)=3x x1414-8-8x x8 8+6+6x x2 2+2+2数据元素数据元素(coef,exp)表表示示多多项项式式项项coefxexp，coef是是该该项项的的系系数数，exp是是变变元元x的指数。的指数。多项式的存储表示多项式的存储表示多项式的存储表示多项式的存储表示p p(x x)=3)=3x x1414-8-8x x8 8+6+6x x2 2+2+2(3,14)3,14)，(-8,8)(-8,8)，(6,2)(6,2)，(2,0)(2,0)顺序表示顺序表示线性表长度事先难以确定；线性表长度事先难以确定；算术运算需插入和删除元素算术运算需插入和删除元素。多项式的链接表示多项式的链接表示多项式的项多项式的项 多项式相加多项式相加带头结点的线性链表类型(pp37)typedef struct LNode /结点类型 ElemType data;LNode*next;*Link,*Position;struct LinkList /链表类型 Link head,tail;/分别指向线性链表中的头结点和最后一个结点 int len;/指示线性链表中数据元素的个数;分配由p指向的值为e的结点Status MakeNode(Link&p,ElemType e)/分配由p指向的值为e的结点，并返回OK；/若分配失败,则返回ERROR p=(Link)malloc(sizeof(LNode);if(!p)return ERROR;p-data=e;return OK;释放p所指结点void FreeNode(Link&p)/释放p所指结点 free(p);p=NULL;构造一个空的线性链表Status InitList(LinkList&L)Link p;p=(Link)malloc(sizeof(LNode);/生成头结点 if(p)p-next=NULL;L.head=L.tail=p;L.len=0;return OK;else return ERROR;销毁线性链表LStatus DestroyList(LinkList&L)/销毁线性链表L，L不再存在 ClearList(L);/清空链表 FreeNode(L.head);L.tail=NULL;L.len=0;return OK;将线性链表L重置为空表Status ClearList(LinkList&L)Link p,q;if(L.head!=L.tail)/不是空表 p=q=L.head-next;L.head-next=NULL;while(p!=L.tail)p=q-next;free(q);q=p;free(q);L.tail=L.head;L.len=0;return OK;将s所指结点插入在第一个结点之前Status InsFirst(LinkList&L,Link h,Link s)/形参增加L,因为需修改L/h指向L的一个结点，把h当做头结点，/将s所指结点插入在第一个结点之前 s-next=h-next;h-next=s;if(h=L.tail)/h指向尾结点 L.tail=h-next;/修改尾指针 L.len+;return OK;删除链表中的第一个结点Status DelFirst(LinkList&L,Link h,Link&q)/形参增加L,因为需修改L。h指向L的一个结点，/把h当做头结点，删除链表中的第一个结点并 /以q返回。q=h-next;if(q)/链表非空 h-next=q-next;if(!h-next)L.tail=h;/删除尾结点，修改尾指针 L.len-;return OK;else return FALSE;/链表空 Status Append(LinkList&L,Link s)/将指针s(s-data为第一个数据元素)所指(彼此/以指针相 链，以NULL结尾)的一串结点链接在/线性链表L的最后一个结点之后,并改变链表L/的尾指针指向新的尾结点 int i=1;L.tail-next=s;while(s-next)s=s-next;i+;L.tail=s;L.len+=i;return OK;链接两个单链表链接两个单链表返回p所指结点中数据元素的值ElemType GetCurElem(Link p)/已知p指向线性链表中的一个结点，/返回p所指结点中数据元素的值 return p-data;判断线性链表判断线性链表L为空表为空表Status ListEmpty(LinkList L)/若线性链表L为空表，则返回TRUE，否则返回FALSE if(L.len)return FALSE;else return TRUE;返回线性链表L中头结点的位置Position GetHead(LinkList L)/返回线性链表L中头结点的位置 return L.head;返回p所指结点的直接后继的位置 Position NextPos(Link p)/已知p指向线性链表L中的一个结点，/返回p所指结点的直接后继的位置 /若无后继，则返回NULL return p-next;LocateElem:判定升序链表L中是否存在与e相等的元素 Status LocateElem(LinkList L,ElemType e,Position&q,int(*compare)(ElemType,ElemType)/若升序链表L中存在与e满足判定函数compare()取值为0的元素，/则q 指示 L 中第一个值为e的结点的位置；否则q指示第一个与e/满足判定函数compare()取值0的元素的前驱的位置。Link p=L.head,pp;do pp=p;p=p-next;while(p&(compare(p-data,e)data.expndata,e)0)q=pp;return FALSE;/到表尾或compare(p-data,e)0 else q=p;return TRUE;/找到 项结点项结点项结点项结点Termtypedefstruct/项的表示项的表示,多项式的项作为多项式的项作为LinkList的数据元素的数据元素pp42floatcoef;/系数系数intexpn;/指数指数term,ElemType;/两个类型名两个类型名:term用于本用于本ADT,/ElemType为为LinkList的数据对象名的数据对象名 typedefLinkListpolynomial;#defineDestroyPolynDestroyList#definePolynLengthListLength多项式的基本操作的函数intcmp(terma,termb)/CreatPolyn()的实参的实参/依依a的指数值的指数值b的指数值，分别返回的指数值，分别返回-1、0或或+1if(a.expn=b.expn)return0;elsereturn(a.expn-b.expn)/abs(a.expn-b.expn);建立表示一元多项式 void CreatPolyn(polynomial&P,int m)/pp42,算法2.22 /输入m项的系数和指数，建立表示一元多项式的有序链表P Position q,s;term e;int i;InitList(p);printf(请依次输入%d个系数，指数：n,m);for(i=1;idata.coef+=qb-data.coef;/两者的指数值相等,修改Pa当前结点的系数值 if(qa-data.coef=0)/删除多项式Pa中当前结点 DelFirst(Pa,ha,qa);FreeNode(qa);else ha=qa;DelFirst(Pb,hb,qb);FreeNode(qb);qb=NextPos(hb);qa=NextPos(ha);break;case 1:DelFirst(Pb,hb,qb);/多项式Pb中当前结点的指数值小 InsFirst(Pa,ha,qb);ha=ha-next;qb=NextPos(hb);系数处理一元多项式系数取反voidOpposite(polynomialPa)/一元多项式系数取反一元多项式系数取反Positionp;p=Pa.head;while(p-next)p=p-next;p-data.coef*=-1;多项式减法多项式减法voidSubtractPolyn(polynomial&Pa,polynomial&Pb)/多项式减法多项式减法:Pa=Pa-Pb,并销毁一元多项式并销毁一元多项式PbOpposite(Pb);AddPolyn(Pa,Pb);打印输出一元多项式P voidPrintPolyn(polynomialP)/打印输出一元多项式打印输出一元多项式PLinkq;q=P.head-next;/q指向第一个结点指向第一个结点printf(系数系数指数指数n);while(q)printf(%f%dn,q-data.coef,q-data.expn);q=q-next;voidCreatPolyn(polynomial&P,intm)/算法算法2.22voidAddPolyn(polynomial&Pa,polynomial&Pb)/算法算法2.23voidPrintPolyn(polynomialP)/打印输出一元多项式打印输出一元多项式主函数题目2 2 迷迷宫问题 问题：问题：以一个以一个m*n的方阵表示迷宫，的方阵表示迷宫，0和和1分别表示迷分别表示迷宫中的通路和障碍。迷宫问题要求求出从入口（宫中的通路和障碍。迷宫问题要求求出从入口（1,1）到出口（到出口（m,n）的所有通路，或得出没有通路的结论。的所有通路，或得出没有通路的结论。思路：思路：从入口（从入口（1,1）出发，按某一方向向前搜索，若）出发，按某一方向向前搜索，若能走通（未走过），即某处可以到达，则到达新点，能走通（未走过），即某处可以到达，则到达新点，否则，试探下一方向；若所有的方向都没有通路，则否则，试探下一方向；若所有的方向都没有通路，则沿原路返回前一点，换下一个方向再试探，直到所有沿原路返回前一点，换下一个方向再试探，直到所有可能的通路都探索到，或找到一条通路，或无路可走可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。又返回到入口点。用一个栈保存所能到达的每一点的下标及从该点前进用一个栈保存所能到达的每一点的下标及从该点前进的方向。的方向。需要解决的四个问题（1）表示）表示迷宫的数据结构迷宫的数据结构利用利用mazemn表示一个迷宫，表示一个迷宫，mazemn=0，1。1表示通路，表示通路，0表示不通。表示不通。为简化问题用为简化问题用mazem+2n+2来表示一个迷宫，来表示一个迷宫，这样每个点的试探方向都为这样每个点的试探方向都为8。00000000000011101110010101111000100000100011101110010011000000110011000000000000（2）试探方向 (北北)(x-1,y-1)(x-1,y)(x-1,y+1)(西西)(x,y-1)(x,y)(x,y+1)(东东)(x+1,y-1)(x+1,y)(x+1,y+1)(南南)方向方向V：0=v(x,y,d)出栈；出栈；求出下一个要试探的方向求出下一个要试探的方向d+；while(还有剩余试探的方向）还有剩余试探的方向）if（d方向可走）方向可走）(x,y,d)入栈；入栈；求新点坐标（求新点坐标（i，j）；）；将新点（将新点（i，j）切换为当前点（切换为当前点（x，y）；）；if(x,y)=(m,n)结束；结束；else重置重置d=0;elsed+;题目3 3 利用二叉排序利用二叉排序树对顺序表序表进行排序行排序涉及知识面涉及知识面1 1 排序排序2 2 查找查找3 3 树树4 4 顺序表顺序表5 5 栈栈设计内容、要求：设计内容、要求：1 1生成一个顺序表生成一个顺序表L L2 2对所生成的顺序表对所生成的顺序表L L构造二叉排序树构造二叉排序树3 3利用栈结构实现中序遍历二叉排序树利用栈结构实现中序遍历二叉排序树4 4中序遍历所构造的二叉排序树将记录由小到大输出中序遍历所构造的二叉排序树将记录由小到大输出步骤1生成顺序表生成顺序表L定义顺序表：定义顺序表：p22；利用算法利用算法2.3InitList_Sq初始化顺序表；初始化顺序表；利用算法利用算法2.4ListInsert_Sq生成顺序表；生成顺序表；数据元素个数和数据元素的值从键盘输入；数据元素个数和数据元素的值从键盘输入；2 对所生成生成顺序表序表L构造二叉排序构造二叉排序树（1）定义二叉排序树）定义二叉排序树P127（2）初始化二叉排序树为空树）初始化二叉排序树为空树BiTreeT=NULL；（3）按待排序的顺序表构造二叉排序树按待排序的顺序表构造二叉排序树利用算法利用算法9.5(b)和和9.6方法：方法：for(inti=0;idata;方法：用方法：用output替代替代visit调用算法调用算法6.3i=0;InorderTraverse(T,output(T,l,i);4按顺序输出顺序表按顺序输出顺序表LL即为由小到大排序的顺序表。即为由小到大排序的顺序表。函数表InitList_Sq,ListInsert_Sq,InsertBST,SearchBST,InOrderTraverser,output,InitStack,StackEmpty,Push,Pop四四 函数函数调用关系用关系 mainInitList_SqInOrderTraverserListInsert_SqInsertBSTSearchBST outputInitStackStackEmptyPushPop问题描述：问题描述：设计一个交通咨询系统，为自驾游旅行者客咨询设计一个交通咨询系统，为自驾游旅行者客咨询从任一个城市到另一个城市之间的最短路径问题。设从任一个城市到另一个城市之间的最短路径问题。设计分三个部分，一是建立交通网络图的存储结构；二计分三个部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现两个城市顶点是解决单源最短路径问题；最后再实现两个城市顶点之间的最短路径问题。之间的最短路径问题。题目4 交通咨交通咨询系系统(1)数据存储。数据存储。城市信息城市信息(城市名、代码城市名、代码)、城市间的里程存储于磁、城市间的里程存储于磁盘文件。建议把城市信息存于文件前面，交通信息存于盘文件。建议把城市信息存于文件前面，交通信息存于文件的后面，用文件的后面，用fread和和fwrite函数操作。函数操作。(2)数据的逻辑结构。数据的逻辑结构。根据设计任务的描述，其城市之间的旅游交通问题根据设计任务的描述，其城市之间的旅游交通问题是典型的图结构，可看作为有向图，图的顶点是城市，是典型的图结构，可看作为有向图，图的顶点是城市，边是城市之间的边是城市之间的里里程。程。算法思路(3)数据的存储结构。数据的存储结构。采用邻接表和邻接矩阵都可作为数据的存储结构，采用邻接表和邻接矩阵都可作为数据的存储结构，但当邻接边不多时，宜采用邻接表，以提高空间的存但当邻接边不多时，宜采用邻接表，以提高空间的存储效率。这里建议采用邻接表作为数据的存储结构。储效率。这里建议采用邻接表作为数据的存储结构。(4)用不同的功能模块对城市信息和交通信息进行编辑。用不同的功能模块对城市信息和交通信息进行编辑。添加、修改、删除功能可用菜单方式或命令提示方式。添加、修改、删除功能可用菜单方式或命令提示方式。只要能方便的对城市信息和交通信息进行管理即可，只要能方便的对城市信息和交通信息进行管理即可，但要注意人机界面，具体实现自行设计。这些工作有但要注意人机界面，具体实现自行设计。这些工作有不小的工作量。不小的工作量。(5)最优决策功能模块最优决策功能模块读入城市信息和交通信息，用邻接表生成含权网络，读入城市信息和交通信息，用邻接表生成含权网络，表头数组中的元素存放城市名及对方城市到达该元素所表头数组中的元素存放城市名及对方城市到达该元素所代表城市的所有信息；表头数组中的元素所对应的单链代表城市的所有信息；表头数组中的元素所对应的单链表存放与该元素所代表的城市有交通联系的城市表存放与该元素所代表的城市有交通联系的城市(代码、代码、里程里程)。根据具体最优决策的要求，用根据具体最优决策的要求，用Dijkstra算法求出出算法求出出发城市到其它各城市的最优值发城市到其它各城市的最优值(最短里程最短里程)，搜索过程，搜索过程中所经过城市的局部最优信息都保存在邻接表的表头中所经过城市的局部最优信息都保存在邻接表的表头数组中。其目的城市所代表的元素中就保存了所需的数组中。其目的城市所代表的元素中就保存了所需的最优决策结果。这过程中，要用队列或栈保存局部最最优决策结果。这过程中，要用队列或栈保存局部最优决策值优决策值(局部最短的时间或最省的费用局部最短的时间或最省的费用)变小的城市，变小的城市，其相应的初始值可为其相应的初始值可为，并在表头数组对应的城市元，并在表头数组对应的城市元素中保存响应的信息。开始时，栈素中保存响应的信息。开始时，栈(队队)中只有出发地中只有出发地城市，随着对栈城市，随着对栈(队队)顶顶(首首)城市有交通联系的城市求城市有交通联系的城市求得决策值得决策值(最短时间最短时间)，若该值是局部最优值且该城市，若该值是局部最优值且该城市不在栈不在栈(队队)中，则进栈中，则进栈(队队)，直至栈，直至栈(队队)为空。为空。输出结果。输出结果。从目的城市出发，搜索到出发城市，所经过的城市从目的城市出发，搜索到出发城市，所经过的城市均入栈，再逐一出栈栈中的城市，输出保存在表头数组均入栈，再逐一出栈栈中的城市，输出保存在表头数组中对应城市的信息中对应城市的信息(对方城市的出发信息，里程、时间、对方城市的出发信息，里程、时间、费用等费用等)及最终结果。即输出依次于何时何地乘坐几点及最终结果。即输出依次于何时何地乘坐几点的飞机或火车于何时到达何地；最终所需的最快需要多的飞机或火车于何时到达何地；最终所需的最快需要多长时间才能到达及旅费，或者最少需要多少旅费才能到长时间才能到达及旅费，或者最少需要多少旅费才能到达及时间。达及时间。题目5 5 内部排序算法的比内部排序算法的比较略