《数据结构课程设计.ppt》由会员分享，可在线阅读，更多相关《数据结构课程设计.ppt（49页珍藏版）》请在三一办公上搜索。
1、课 程 设 计,时间：二周。,完成方式：一人一题。,考核方式：考查。,考核形式：检查：上机运行、检查结果；答辩：对程序提问、回答问题；提交：原程序清单、课程设计报告。,成绩评定方式：按上机调试情况、运行结果和答辩情况、课程设计报告三方面评定。,成绩评定档次：优、良、中、及格、不及格。,文档要求,课程设计报告按教务处指定的格式填写打印。1 封面2 摘要 一般不超过400字。3 关键字 一般为4个左右。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+x1
3、；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）指示迷宫中的一个坐标，d
4、表示走到下一坐标的方向。,测试数据：左上角（1,1）为入口，右下角（m,n）为出口。选作内容：（1）编写递归形式的算法，求得迷宫中的所有可能的通路；（2）以方阵的形式输出迷宫及其通路迷宫中的所有可能的通路；,题目3 二叉排序树的应用,问题描述：利用二叉排序树对顺序表进行排序。基本要求：（1）生成一个顺序表L;（2）对所生成的顺序表L构造二叉排序树;（3）利用栈结构实现中序遍历二叉排序树;（4）中序遍历所构造的二叉排序树将记录由小到大输出。测试数据：用伪随机数产生程序产生，表长不小于20。选作内容：实现二叉排序树的插入和删除操作。,题目4 内部排序算法的比较,问题描述：通过比较各内部排序算法的关
5、键字比较次数和关键字移动的次数，以取得直观感受。基本要求：1、待排序表的表长不小于100；2、至少要用5组不同的输入数据作比较；3、排序算法不少于5种；4、最后要对结果作简单的分析。测试数据：用伪随机数产生程序产生。选作内容：对不同的表长做试验分析两个指标相对于表长变化关系。,实 现 要 点,多项式相加 p(x)=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)表示多项式项 coefxex
6、p，coef是该项的系数，exp是变元x的指数。,多项式的存储表示 p(x)=3x14-8x8+6x2+2(3,14)，(-8,8)，(6,2)，(2,0)顺序表示 线性表长度事先难以确定；算术运算需插入和删除元素。,多项式的链接表示多项式的项,多项式相加,带头结点的线性链表类型,typedef struct LNode/结点类型 ElemType data;LNode*next;*Link,*Position;struct LinkList/链表类型 Link head,tail;/分别指向线性链表中的头结点和最后一个结点 int len;/指示线性链表中数据元素的个数;,分配由p指向的值为
7、e的结点,Status MakeNode(Link,释放p所指结点void FreeNode(Link,构造一个空的线性链表,Status InitList(LinkList,销毁线性链表L,Status DestroyList(LinkList,将线性链表L重置为空表,Status ClearList(LinkList,将s所指结点插入在第一个结点之前,Status InsFirst(LinkList,删除链表中的第一个结点,Status DelFirst(LinkList/链表空,Status Append(LinkList,链接两个单链表,返回p所指结点中数据元素的值,ElemType
8、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中的
9、一个结点，/返回p所指结点的直接后继的位置/若无后继，则返回NULL return p-next;,LocateElem:判定升序链表L中是否存在与e相等的元素,Status LocateElem(LinkList L,ElemType e,Position/找到,项结点,项结点 Term,typedef struct/项的表示,多项式的项作为LinkList的数据元素 float coef;/系数 int expn;/指数 term,ElemType;/两个类型名:term用于本ADT(抽象数据类型),/ElemType为LinkList的数据对象名,typedef LinkList pol
10、ynomial;#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(polynomial/生成结点并插入链表,AddPolyn:多项式加法（算法2.23）,void AddPol
11、yn(polynomial,case-1:ha=qa;/多项式Pa中当前结点的指数值小 qa=NextPos(ha);break;/ha和qa均向后移一个结点 case 0:qa-data.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,h
12、b,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,打印输出一元多项式P,void PrintPolyn(polynomial P)/打印输出一元多项式P Link q;q=P.head-next;/q指向第一个结
13、点 printf(系数 指数n);while(q)printf(%f%dn,q-data.coef,q-data.expn);q=q-next;,void CreatPolyn(polynomial&P,int m)/建立多项式void AddPolyn(polynomial&Pa,polynomial&Pb)/多项式相加void PrintPolyn(polynomial P)/打印输出一元多项式,主函数,题目2 迷宫问题,问题：以一个m*n的方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。迷宫问题要求求出从入口（1,1）到出口（m,n）的一条通路，或得出没有通路的结论。思路：从入口（1,1
14、）出发，按某一方向向前搜索，若能走通（未走过），即某处可以到达，则到达新点，否则，试探下一方向；若所有的方向都没有通路，则沿原路返回前一点，换下一个方向再试探，直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。用一个栈保存所能到达的每一点的下标及从该点前进的方向。,需要解决的四个问题,（1）表示迷宫的数据结构 利用mazemn表示一个迷宫，mazemn=0，1。1表示通路，0 表示不通。,为简化问题用mazem+2n+2来表示一个迷宫，这样每个点的试探方向都为8。,（2）试探方向,(北)(x-1,y-1)(x-1,y)(x-1,y+1)(西)(x,y-1)(x,y)(x,y
15、+1)(东)(x+1,y-1)(x+1,y)(x+1,y+1)(南)方向V：0=v=7,定义结构数组move8typedef struct int x;/x坐标增量 int y;/y坐标增量item;item move8;/记8个方向的点,（3）栈的设计,typedef structint x,y,d;/坐标及方向elemtp;,(4)如何防止到达重复点，以避免死循环设置标志数组markmn。,算法思路,栈初始化。将入口坐标及到达该点的方向(-1)入栈。while(栈不空）栈顶元素=(x,y,d)出栈；求出下一个要试探的方向d+；while(还有剩余试探的方向）if（d方向可走）(x,y,d)
16、入栈；求新点坐标（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（参考教材）定义顺序表；InitList_Sq 初始化顺序表；ListInsert_Sq 生成顺序表；数据元素个数和数据元素的值从键盘输入；,2 对所生成顺序表L构造二叉排序树,（1）定义二叉排序树（2）初
17、始化二叉排序树为空树 BiTree T=NULL；（3）按待排序的顺序表构造二叉排序树方法：for(int i=0;iL.Length;i+)Insert_BST(T,L.elem(i);,3 中序遍历二叉排序树,利用函数output,将排序的记录由小到大输出至Lvoid output(Bitree T,SqList,按顺序输出顺序表L L即为由小到大排序的顺序表。,函数表,InitList_Sq,ListInsert_Sq,InsertBST,SearchBST,InOrderTraverser,output,InitStack,StackEmpty,Push,Pop,四 函数调用关系,mainInitList_Sq InOrderTraverser ListInsert_Sq InsertBST SearchBST output InitStack StackEmpty Push Pop,
