【文档说明】数据结构课程设计(1)课件.ppt，共(58)页，393.000 KB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-6094.html

以下为本文档部分文字说明：

课程设计pp-1数据结构课程设计课程设计pp-2数据结构时间：二周。完成方式：一人一题。考核方式：考查。考核形式：检查：上机运行、检查结果；答辩：对程序提问、回答问题；提交：原程序清单、课程设计报告。成绩评定方式：按上机调试

情况、运行结果和答辩情况、课程设计报告三方面评定。成绩评定档次：优、良、中、及格、不及格。课程设计pp-3数据结构文档要求课程设计报告按教务处指定的格式填写打印。1封面2课程设计任务书3课程设计鉴定表4目录要求给出标题及页次。5课程设计的目的6课程设计任务与要求7设计思想及实现

要点课程设计pp-4数据结构8系统测试说明程序调试过程中出现的问题及解决的方法。9操作说明说明使用本软件的操作方法。10总结在总结中可谈本人的心得体会及软件进一步改进的方向等项内容。11参考文献12附录课程设计pp-5数据结构题目1一元多项式计算器问题描述

：设计一个稀疏多项式简单计算器基本要求：(1)输入并分别建立多项式A和B。(2)输入输出多项式，输出形式为整数序列：n,c1,e1,c2,e2……，其中n是多项式的项数，ci和ei是第i项的系数和指数，序列按指数降序排列。(3)完成两个多项式的相加、相减，并将结果输出。课程设计

pp-6数据结构测试数据：(1)A+BA=3x14-8x8+6x2+2；B=2x10+4x8+-6x2(2)A-BA=11x14+3x10+2x8+10x6+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=100x100+50x50+20x20+x；B=10x100+10x50+10x20+x选作内容：（1）多项式在x=1时的运算结果；（2）求多项式A和B的乘积。课程设计pp-7数据结构题目2迷宫问题问题描述：以一个m*n的长方阵表示

迷宫，0和1分别表示迷宫中的通路和障碍。迷宫问题要求求出从入口（1,1）到出口（m,n）的一条通路，或得出没有通路的结论。基本要求：首先实现一个以链表作存储结构的栈类型，然后编写一个求迷宫问题的非递归程序，求得

的通路以三元组（i,j,d）的形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。课程设计pp-8数据结构测试数据：左上角（1,1）为入口，右下角（m,n）为出口。选作内容：（1）编写递归形式的算法，求

得迷宫中的所有可能的通路；（2）以方阵的形式输出迷宫及其通路迷宫中的所有可能的通路；课程设计pp-9数据结构题目3二叉排序树的应用问题描述：利用二叉排序树对顺序表进行排序。基本要求：（1）生成一个顺序表L;（2）对所生成的顺序表L构造二叉排序树;（3）利用栈结构实现中

序遍历二叉排序树;（4）中序遍历所构造的二叉排序树将记录由小到大输出。测试数据：用伪随机数产生程序产生随机数，表长不小于20。选作内容：实现二叉排序树的插入和删除操作。课程设计pp-10数据结构问题描述：设计一个交通咨

询系统，为自驾游旅行者客咨询从任一个城市到另一个城市之间的最短路径问题。设计分三个部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现两个城市顶点之间的最短路径问题。基本要求：1对城市信息(城市名、城市间的里程)

进行编辑：具备添加、修改、删除功能；2咨询以用户和计算机对话方式进行，要注意人机交互的屏幕界面。由用户选择输入起点、终点，输出信息：旅行者从起点、终点经过的每一座城市。3.主程序可以有系统界面、菜单；也可用命令提示方式

；选择功能模块执行，要求在程序运行过程中可以反复操作。题目4交通咨询系统课程设计pp-11数据结构测试数据：参考《数据结构（C语言版）》（严蔚敏吴伟民编著）7.6节图7.33的交通图。答辩测试数据：北京到乌鲁木齐；北京到昆明；广州到哈尔滨；乌鲁木齐到南昌；沈阳到昆明。选作内容：考虑由于

路况不同，不同城市间自驾旅行每百公里油耗不同，为旅行选择最经济路线。课程设计pp-12数据结构题目5内部排序算法的比较问题描述：通过比较各内部排序算法的关键字比较次数和关键字移动的次数，以取得直观感受。基本要求：1、待排序表的表长

不小于100；2、至少要用5组不同的输入数据作比较；3、排序算法不少于5种；4、最后要对结果作简单的分析。测试数据：用伪随机数产生程序产生。选作内容：对不同的表长做试验分析两个指标相对于表长变化关系。实现要点课程设

计pp-14数据结构多项式相加p(x)=3x14−8x8+6x2+2q(x)=2x10+4x8−6x2p(x)p(x)+q(x)结果：p(x)=3x14+2x10−4x8+2题目1多项式的算术运算课程设计pp-15数据结构多项式的逻辑结构：视为线性表p(x)=3x14-8x8

+6x2+2数据元素(coef,exp)表示多项式项coef·xexp，coef是该项的系数，exp是变元x的指数。多项式的存储表示p(x)=3x14-8x8+6x2+2((3,14)，(-8,8)，(6,2)，

(2,0))顺序表示线性表长度事先难以确定；算术运算需插入和删除元素。课程设计pp-16数据结构多项式的链接表示多项式的项课程设计pp-17数据结构多项式相加课程设计pp-18数据结构带头结点的线性链表类型(pp37)typedefstructLNode/

/结点类型{ElemTypedata;LNode*next;}*Link,*Position;structLinkList//链表类型{Linkhead,tail;//分别指向线性链表中的头结点和最后一个结

点intlen;//指示线性链表中数据元素的个数};课程设计pp-19数据结构分配由p指向的值为e的结点StatusMakeNode(Link&p,ElemTypee){//分配由p指向的值为e的结点，并返回OK；//若分配失败,则返回ERRORp=(Link)

malloc(sizeof(LNode));if(!p)returnERROR;p->data=e;returnOK;}释放p所指结点voidFreeNode(Link&p)//释放p所指结点{free(p);p=NULL;}课程设计pp-20数据结构构造一个空的线性链表Stat

usInitList(LinkList&L){Linkp;p=(Link)malloc(sizeof(LNode));//生成头结点if(p){p->next=NULL;L.head=L.tail=p;L.len=0;returnOK;}

elsereturnERROR;}课程设计pp-21数据结构销毁线性链表LStatusDestroyList(LinkList&L)//销毁线性链表L，L不再存在{ClearList(L);//清空链表FreeNode(L.hea

d);L.tail=NULL;L.len=0;returnOK;}课程设计pp-22数据结构将线性链表L重置为空表StatusClearList(LinkList&L){Linkp,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;}r

eturnOK;}课程设计pp-23数据结构将s所指结点插入在第一个结点之前StatusInsFirst(LinkList&L,Linkh,Links){//形参增加L,因为需修改L//h指向L的一个结点，把h当做头结点，//将s所指结点插入在第一个结点之前s->next

=h->next;h->next=s;if(h==L.tail)//h指向尾结点L.tail=h->next;//修改尾指针L.len++;returnOK;}课程设计pp-24数据结构删除链表中的第一个结点StatusDelFirst(LinkList&L,Linkh,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--;returnOK;}elsereturnFALSE;//链表空}课程设计pp-25数据结构StatusAppend(LinkList&L,Links){//将指针s(s->data为第一个数据元素)

所指(彼此//以指针相链，以NULL结尾)的一串结点链接在//线性链表L的最后一个结点之后,并改变链表L//的尾指针指向新的尾结点inti=1;L.tail->next=s;while(s->next){s=s->next;i++;}L.tail=s

;L.len+=i;returnOK;}链接两个单链表课程设计pp-26数据结构返回p所指结点中数据元素的值ElemTypeGetCurElem(Linkp){//已知p指向线性链表中的一个结点，//返回p所指结点中数据元素的

值returnp->data;}判断线性链表L为空表StatusListEmpty(LinkListL){//若线性链表L为空表，则返回TRUE，否则返回FALSEif(L.len)returnFALSE;elsereturnTRUE;}课程设计pp-27数据结构返回线性

链表L中头结点的位置PositionGetHead(LinkListL){//返回线性链表L中头结点的位置returnL.head;}返回p所指结点的直接后继的位置PositionNextPos(Link

p){//已知p指向线性链表L中的一个结点，//返回p所指结点的直接后继的位置//若无后继，则返回NULLreturnp->next;}课程设计pp-28数据结构LocateElem:判定升序链表L中是否存在与e相等的元素Statu

sLocateElem(LinkListL,ElemTypee,Position&q,int(*compare)(ElemType,ElemType)){//若升序链表L中存在与e满足判定函数compare()取值为

0的元素，//则q指示L中第一个值为e的结点的位置；否则q指示第一个与e//满足判定函数compare()取值>0的元素的前驱的位置。Linkp=L.head,pp;do{pp=p;p=p->next;}while(p&&(compare(p->data

,e)<0));//没到表尾且p->data.expn<e.expnif(!p||compare(p->data,e)>0){q=pp;returnFALSE;}//到表尾或compare(p->data,e)>0else{q=p;returnTRUE;}//找到}课程设计pp-29数据结构

项结点项结点Termtypedefstruct{//项的表示,多项式的项作为LinkList的数据元素pp42floatcoef;//系数intexpn;//指数}term,ElemType;//两个类型

名:term用于本ADT,//ElemType为LinkList的数据对象名课程设计pp-30数据结构typedefLinkListpolynomial;#defineDestroyPolynDestroyList#definePolynLengt

hListLength课程设计pp-31数据结构多项式的基本操作的函数intcmp(terma,termb)//CreatPolyn()的实参{//依a的指数值<、=或>b的指数值，分别返回-1、0或+1if(a.expn==b.expn

)return0;elsereturn(a.expn-b.expn)/abs(a.expn-b.expn);}课程设计pp-32数据结构建立表示一元多项式voidCreatPolyn(polynomial&P,intm)//pp42,算法2.22{//输入m

项的系数和指数，建立表示一元多项式的有序链表PPositionq,s;terme;inti;InitList(p);printf("请依次输入%d个系数，指数：\n",m);for(i=1;i<=m;++i){//依次输入m个非零项（可按任意

顺序）scanf("%f,%d",&e.coef,&e.expn);if(!LocateElem(p,e,q,cmp))//当前链表中不存在该指数项,cmp是实参if(MakeNode(s,e))InsFirst(p,q,s);//生成结点并插入链表}}课程设计pp-33数据结构AddPo

lyn:多项式加法（算法2.23）voidAddPolyn(polynomial&Pa,polynomial&Pb){//多项式加法:Pa=Pa+Pb,并销毁一元多项式PbPositionha,hb,qa,qb;terma,b;ha

=GetHead(Pa);hb=GetHead(Pb);//ha和hb分别指向Pa和Pb的头结点qa=NextPos(ha);qb=NextPos(hb);//qa和qb分别指向Pa和Pb中当前结点（现为第一个结点）while(!ListEmpty(Pa)&&!ListEmpty(Pb)

&&qa){//Pa和Pb均非空且ha没指向尾结点(qa!=0)a=GetCurElem(qa);b=GetCurElem(qb);//a和b为两表中当前比较元素switch(cmp(a,b)){系数处理}}if(!ListEmpty(Pb))//链接Pb中剩余结点,销毁Pb{Pb.t

ail=hb;Append(Pa,qb);DestroyPolyn(Pb);}}课程设计pp-34数据结构case-1:ha=qa;//多项式Pa中当前结点的指数值小qa=NextPos(ha);break;//ha和qa均向后移一个结点case0:qa-

>data.coef+=qb->data.coef;//两者的指数值相等,修改Pa当前结点的系数值if(qa->data.coef==0)//删除多项式Pa中当前结点{DelFirst(Pa,ha,qa);FreeNode(qa);}elseha=

qa;DelFirst(Pb,hb,qb);FreeNode(qb);qb=NextPos(hb);qa=NextPos(ha);break;case1:DelFirst(Pb,hb,qb);//多项式Pb中当前结点的指数值小

InsFirst(Pa,ha,qb);ha=ha->next;qb=NextPos(hb);系数处理课程设计pp-35数据结构一元多项式系数取反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);AddPol

yn(Pa,Pb);}课程设计pp-36数据结构打印输出一元多项式PvoidPrintPolyn(polynomialP){//打印输出一元多项式PLinkq;q=P.head->next;//q指向第一个结点pr

intf("系数指数\n");while(q){printf("%f%d\n",q->data.coef,q->data.expn);q=q->next;}}课程设计pp-37数据结构voidCreatPolyn(po

lynomial&P,intm)//算法2.22voidAddPolyn(polynomial&Pa,polynomial&Pb)//算法2.23voidPrintPolyn(polynomialP)//打印输出一元多项式主函数题目2迷宫问题课程设计pp-3

9数据结构问题：以一个m*n的方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。迷宫问题要求求出从入口（1,1）到出口（m,n）的所有通路，或得出没有通路的结论。思路：从入口（1,1）出发，按某一方向向前搜索，若能走通（

未走过），即某处可以到达，则到达新点，否则，试探下一方向；若所有的方向都没有通路，则沿原路返回前一点，换下一个方向再试探，直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。用一个栈保

存所能到达的每一点的下标及从该点前进的方向。课程设计pp-40数据结构需要解决的四个问题（1）表示迷宫的数据结构利用maze[m][n]表示一个迷宫，maze[m][n]=0，1。1表示通路，0表示不通。为简化问题用m

aze[m+2][n+2]来表示一个迷宫，这样每个点的试探方向都为8。课程设计pp-41数据结构000000000000111011100101011110001000001000111011100100110000001100110000000

00000课程设计pp-42数据结构（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<=7课程设计pp-43数据结构定义

结构数组move[8]typedefstruct{intx;//x坐标增量inty;//y坐标增量}item;itemmove[8];课程设计pp-44数据结构（3）栈的设计typedefstruct{intx,y,d;//坐标及方向}elemtp;(4)如何防止到达重复点，

以避免死循环设置标志数组mark[m][n]。课程设计pp-45数据结构算法思路①栈初始化。②将入口坐标及到达该点的方向(-1)入栈。③while(栈不空）{栈顶元素=>(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++;}}课程设计pp-46数据结构题目3利用二

叉排序树对顺序表进行排序涉及知识面1排序2查找3树4顺序表5栈设计内容、要求：1生成一个顺序表L2对所生成的顺序表L构造二叉排序树3利用栈结构实现中序遍历二叉排序树4中序遍历所构造的二叉排序树将记录由小到

大输出课程设计pp-47数据结构步骤1生成顺序表L定义顺序表：p22；利用算法2.3InitList_Sq初始化顺序表；利用算法2.4ListInsert_Sq生成顺序表；数据元素个数和数据元素的值从键盘输入；课程设计pp-48数据结构2对所生成顺序表L构造二叉排序树（1）定义二叉排序树P

127（2）初始化二叉排序树为空树BiTreeT=NULL；（3）按待排序的顺序表构造二叉排序树利用算法9.5(b)和9.6方法：for(inti=0;i<L.Length;i++)Insert_BST(T,

L.elem(i));课程设计pp-49数据结构3中序遍历二叉排序树利用函数output,将排序的记录由小到大输出至Lvoidoutput(BitreeT,SqList&L,int&i){L.elem[i++]=T->da

ta;}方法：用output替代visit调用算法6.3i=0;InorderTraverse(T,output(T,l,i));4按顺序输出顺序表LL即为由小到大排序的顺序表。课程设计pp-50数据结构函数表InitList_Sq,ListInsert_

Sq,InsertBST,SearchBST,InOrderTraverser,output,InitStack,StackEmpty,Push,Pop课程设计pp-51数据结构四函数调用关系mainInitList_SqInOrderTraverserListIns

ert_SqInsertBSTSearchBSToutputInitStackStackEmptyPushPop课程设计pp-52数据结构问题描述：设计一个交通咨询系统，为自驾游旅行者客咨询从任一个城市到另一个城市之间的最短路径问题。设计分三个部分

，一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现两个城市顶点之间的最短路径问题。题目4交通咨询系统课程设计pp-53数据结构(1)数据存储。城市信息(城市名、代码)、城市间的里程存储于磁盘文件。建议把城市信息存于文件前面

，交通信息存于文件的后面，用fread和fwrite函数操作。(2)数据的逻辑结构。根据设计任务的描述，其城市之间的旅游交通问题是典型的图结构，可看作为有向图，图的顶点是城市，边是城市之间的里程。算法思路课程设计pp-54数据结构(3)数据的存储结构

。采用邻接表和邻接矩阵都可作为数据的存储结构，但当邻接边不多时，宜采用邻接表，以提高空间的存储效率。这里建议采用邻接表作为数据的存储结构。(4)用不同的功能模块对城市信息和交通信息进行编辑。添加、修改、删除功能可用菜单方式或命令提示方式。只要能方便的对

城市信息和交通信息进行管理即可，但要注意人机界面，具体实现自行设计。这些工作有不小的工作量。课程设计pp-55数据结构(5)最优决策功能模块①读入城市信息和交通信息，用邻接表生成含权网络，表头数组中的元素存放城市名及对方城市到达该元素所代表城市的所

有信息；表头数组中的元素所对应的单链表存放与该元素所代表的城市有交通联系的城市(代码、里程)。课程设计pp-56数据结构②根据具体最优决策的要求，用Dijkstra算法求出出发城市到其它各城市的最优值(最短里程)，搜索过程中所经过城市的局部最优信息都保存在邻接表的表头数组中。其目

的城市所代表的元素中就保存了所需的最优决策结果。这过程中，要用队列或栈保存局部最优决策值(局部最短的时间或最省的费用)变小的城市，其相应的初始值可为∞，并在表头数组对应的城市元素中保存响应的信息。开始时，栈(队)中只有出发地城市，随着对栈(队)顶(首)城市有交通联系的城市求得决策值(最短时间

)，若该值是局部最优值且该城市不在栈(队)中，则进栈(队)，直至栈(队)为空。课程设计pp-57数据结构③输出结果。从目的城市出发，搜索到出发城市，所经过的城市均入栈，再逐一出栈栈中的城市，输出保存在表头数组中对应城市的信息(对方城市的出发信息，里程、时间、费用等)及最终结果

。即输出依次于何时何地乘坐几点的飞机或火车于何时到达何地；最终所需的最快需要多长时间才能到达及旅费，或者最少需要多少旅费才能到达及时间。课程设计pp-58数据结构题目5内部排序算法的比较略