数据结构课程设计(1)课件

1、课 程 设 计时间： 二周。完成方式： 一人一题。考核方式： 考查。 考核形式： 检查：上机运行、检查结果； 答辩：对程序提问、回答问题； 提交：原程序清单、课程设计报告。 成绩评定方式： 按上机调试情况、运行结果和答辩情况、课程设计报告三方面评定。 成绩评定档次： 优、良、中、及格、不及格。文档要求课程设计报告按教务处指定的格式填写打印。1 封面2 课程设计任务书3 课程设计鉴定表4 目录 要求给出标题及页次。5 课程设计的目的6 课程设计任务与要求7 设计思想及实现要点8 系统测试 说明程序调试过程中出现的问题及解决的方法。9 操作说明 说明使用本软件的操作方法。10 总结 在总结中可谈本

2、人的心得体会及软件进一步改进的方向等项内容。11 参考文献12 附录题目1 一元多项式计算器问题描述： 设计一个稀疏多项式简单计算器基本要求： (1) 输入并分别建立多项式A和B。 (2) 输入输出多项式，输出形式为整数序列： n,c1,e1,c2,e2， 其中n是多项式的项数，ci和ei是第i项的系数和指数，序列按指数降序排列。 (3)完成两个多项式的相加、相减，并将结果输出。测试数据：(1)A+B A=3x14-8x8+6x2+2； B=2x10+4x8+-6x2(2) A-B A=11x14+3x10+2x8+10 x6+5 ； B=2x14+3x8+5x6+7(3) A+B A=x3+

3、x1 ； B=-x3-x1(4) A+B A=0 ； B=x7+x5+x3+x1(5)A-B A=100 x100+50 x50+20 x20+x ； B=10 x100+10 x50+10 x20+x选作内容：（1）多项式在x=1时的运算结果；（2）求多项式A和B的乘积。题目2 迷宫问题 问题描述： 以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。迷宫问题要求求出从入口（1,1）到出口（m,n）的一条通路，或得出没有通路的结论。 基本要求： 首先实现一个以链表作存储结构的栈类型，然后编写一个求迷宫问题的非递归程序，求得的通路以三元组（i,j,d）的形式输出，其中：（i，j）指

4、示迷宫中的一个坐标， d表示走到下一坐标的方向。测试数据： 左上角（1,1）为入口，右下角（m,n）为出口。选作内容： （1）编写递归形式的算法，求得迷宫中的所有可能的通路； （2）以方阵的形式输出迷宫及其通路迷宫中的所有可能的通路；题目3 二叉排序树的应用 问题描述： 利用二叉排序树对顺序表进行排序。基本要求： （1）生成一个顺序表L; （2）对所生成的顺序表L构造二叉排序树; （3）利用栈结构实现中序遍历二叉排序树; （4）中序遍历所构造的二叉排序树将记录由小到大输出。测试数据： 用伪随机数产生程序产生随机数，表长不小于20。选作内容： 实现二叉排序树的插入和删除操作。问题描述： 设计一个

5、交通咨询系统，为自驾游旅行者客咨询从任一个城市到另一个城市之间的最短路径问题。设计分三个部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现两个城市顶点之间的最短路径问题。基本要求： 1 对城市信息(城市名、城市间的里程)进行编辑：具备添加、修改、删除功能； 2 咨询以用户和计算机对话方式进行，要注意人机交互的屏幕界面。由用户选择输入起点、终点，输出信息：旅行者从起点、终点经过的每一座城市。 3. 主程序可以有系统界面、菜单；也可用命令提示方式；选择功能模块执行，要求在程序运行过程中可以反复操作。题目4 交通咨询系统测试数据： 参考数据结构（C语言版）（严蔚敏 吴伟民编著）

6、7.6节图7.33的交通图。 答辩测试数据：北京到乌鲁木齐；北京到昆明；广州到哈尔滨；乌鲁木齐到南昌；沈阳到昆明。选作内容： 考虑由于路况不同，不同城市间自驾旅行每百公里油耗不同，为旅行选择最经济路线。题目5 内部排序算法的比较 问题描述： 通过比较各内部排序算法的关键字比较次数和关键字移动的次数，以取得直观感受。 基本要求： 1、待排序表的表长不小于100； 2、至少要用5组不同的输入数据作比较； 3、排序算法不少于5种； 4、最后要对结果作简单的分析。 测试数据： 用伪随机数产生程序产生。 选作内容： 对不同的表长做试验分析两个指标相对于表长变化关系。实 现 要 点 多项式相加 p(x)=

7、3x148x8+6x2+2q(x)=2x10+4x86x2 p(x)p(x)+q(x)结果：p(x) =3x14+2x104x8+2 题目1 多项式的算术运算多项式的逻辑结构：视为线性表 p(x)=3x14-8x8+6x2+2 数据元素 (coef,exp) 表示多项式项 coefxexp ，coef是该项的系数，exp是变元x的指数。多项式的存储表示 p(x)=3x14-8x8+6x2+2 ( (3,14)，(-8,8)，(6,2)，(2,0) ) 顺序表示 线性表长度事先难以确定； 算术运算需插入和删除元素。 多项式的链接表示多项式的项 多项式相加带头结点的线性链表类型(pp37) typ

8、edef 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;

9、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不再存在 ClearL

10、ist(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(Link

11、List &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) /链表非

12、空 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; retur

13、n 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所指结点的直

14、接后继的位置 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 / 满足判定函数com

15、pare()取值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; / 找到 项结点项结点 Term typedef struct / 项的表示,多项式的项作为LinkList的数据元素pp42 float coef; / 系数 int expn; / 指数 term,ElemType; / 两个类型名:term用于本AD

16、T,/ElemType为LinkList的数据对象名 typedef LinkList polynomial; #define DestroyPolyn DestroyList #define PolynLength ListLength多项式的基本操作的函数int cmp(term a,term b) / CreatPolyn()的实参 / 依a的指数值b的指数值，分别返回-1、0或+1 if(a.expn=b.expn) return 0; else return (a.expn-b.expn)/abs(a.expn-b.expn); 建立表示一元多项式 void CreatPolyn(p

17、olynomial &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(q

18、b); qb=NextPos(hb); qa=NextPos(ha); break; case 1: DelFirst(Pb,hb,qb); /多项式Pb中当前结点的指数值小 InsFirst(Pa,ha,qb); ha=ha-next; qb=NextPos(hb); 系数处理一元多项式系数取反void Opposite(polynomial Pa) / 一元多项式系数取反 Position p; p=Pa.head; while(p-next) p=p-next; p-data.coef*=-1; 多项式减法 void SubtractPolyn(polynomial &Pa,polyno

19、mial &Pb) / 多项式减法:Pa=Pa-Pb,并销毁一元多项式Pb Opposite(Pb); AddPolyn(Pa,Pb); 打印输出一元多项式P void PrintPolyn(polynomial P) / 打印输出一元多项式P Link q; q=P.head-next; / q指向第一个结点 printf( 系数 指数n); while(q) printf(%f %dn,q-data.coef,q-data.expn); q=q-next; void CreatPolyn(polynomial &P,int m) / 算法2.22void AddPolyn(polynomi

20、al &Pa,polynomial &Pb) / 算法2.23void PrintPolyn(polynomial P) / 打印输出一元多项式 主函数题目2 迷宫问题 问题：以一个m*n的方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。迷宫问题要求求出从入口（1,1）到出口（m,n）的所有通路，或得出没有通路的结论。 思路：从入口（1,1）出发，按某一方向向前搜索，若能走通（未走过），即某处可以到达，则到达新点，否则，试探下一方向；若所有的方向都没有通路，则沿原路返回前一点，换下一个方向再试探，直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。 用一个栈保存所能到达的每一

21、点的下标及从该点前进的方向。需要解决的四个问题（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

22、：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; else d+; 题目3 利用二叉排序树对顺序表进行排序涉及知识面1 排序2 查找3 树4 顺序表5 栈设计内容、要求：生成一个顺序表L对所生成的顺序表L构造二叉排序树利用栈结构实现中序遍历二叉排序树中序遍历所构造的二叉排序树将记录由小到大输出步骤1 生成顺序表L定义顺序表：p22；利用算法2.3 InitList_Sq 初始化顺

23、序表；利用算法2.4 ListInsert_Sq 生成顺序表；数据元素个数和数据元素的值从键盘输入；2 对所生成顺序表L构造二叉排序树（1）定义二叉排序树 P127（2）初始化二叉排序树为空树 BiTree T=NULL；（3）按待排序的顺序表构造二叉排序树 利用算法9.5(b)和9.6 方法： for (int i=0;idata;方法：用output替代visit调用算法6.3 i=0; InorderTraverse(T,output(T,l,i);按顺序输出顺序表L L即为由小到大排序的顺序表。函数表InitList_Sq, ListInsert_Sq, InsertBST, Sear

24、chBST, InOrderTraverser,output, InitStack, StackEmpty, Push, Pop四 函数调用关系 mainInitList_Sq InOrderTraverser ListInsert_Sq InsertBST SearchBST output InitStack StackEmpty Push Pop问题描述： 设计一个交通咨询系统，为自驾游旅行者客咨询从任一个城市到另一个城市之间的最短路径问题。设计分三个部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现两个城市顶点之间的最短路径问题。题目4 交通咨询系统(1) 数据存储。 城市信息(城市名、代码)、城市间的里程存储于磁盘文件。建议把城市信息存于文件前面，交通信息存于文件的后面，用fread和fwrite函数