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

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

2、中、及格、不及格。课程设计课程设计pp-3数据结构数据结构文档要求文档要求课程设计报告按教务处指定的格式填写打印。课程设计报告按教务处指定的格式填写打印。1 1 封面封面2 2 课程设计任务书课程设计任务书3 3 课程设计鉴定表课程设计鉴定表4 4 目录目录 要求给出标题及页次。要求给出标题及页次。5 5 课程设计的目的课程设计的目的6 6 课程设计任务与要求课程设计任务与要求7 7 设计思想及实现要点设计思想及实现要点课程设计课程设计pp-4数据结构数据结构8 8 系统测试系统测试 说明程序调试过程中出现的问题及说明程序调试过程中出现的问题及解决的方法。解决的方法。9 9 操作说明操作说明

3、说明使用本软件的操作方法。说明使用本软件的操作方法。10 10 总结总结 在总结中可谈本人的心得体会及软件在总结中可谈本人的心得体会及软件进一步改进的方向等项内容。进一步改进的方向等项内容。11 11 参考文献参考文献12 12 附录附录课程设计课程设计pp-5数据结构数据结构题目1 1 一元多项式计算器一元多项式计算器问题描述：问题描述： 设计一个稀疏多项式简单计算器设计一个稀疏多项式简单计算器基本要求：基本要求： (1) (1) 输入并分别建立多项式输入并分别建立多项式A A和和B B。 (2) (2) 输入输出多项式，输出形式为整数序列：输入输出多项式，输出形式为整数序列： n,cn,c

4、1 1,e,e1 1,c,c2 2,e,e2 2， 其中其中n n是多项式的项数，是多项式的项数，c ci i和和e ei i是第是第i i项的系数项的系数和指数，序列按指数降序排列。和指数，序列按指数降序排列。 (3) (3)完成两个多项式的相加、相减，并将结果输出。完成两个多项式的相加、相减，并将结果输出。课程设计课程设计pp-6数据结构数据结构测试数据：测试数据：(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 ； B=-x3

5、-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 1）多项式在）多项式在x=1x=1时的运算结果；时的运算结果；（2 2）求多项式）求多项式A A和和B B的乘积。的乘积。课程设计课程设计pp-7数据结构数据结构题目2 2 迷宫问题迷宫问题 问题问题描述：描述： 以一个以一个m m* *n n的长方阵表示迷宫，的长方阵表示迷宫，0 0和和1 1分别表示迷宫分别表示迷宫中的通路和障碍。迷宫问题要求求出从入口（中的通路和障碍。迷宫问题要求求出

6、从入口（1 1, ,1 1）到）到出口（出口（m,nm,n）的一条通路，或得出没有通路的结论。的一条通路，或得出没有通路的结论。 基本要求：基本要求： 首先实现一个以链表作存储结构的栈类型，然后首先实现一个以链表作存储结构的栈类型，然后编写一个求迷宫问题的非递归程序，求得的通路以三编写一个求迷宫问题的非递归程序，求得的通路以三元组（元组（i, ,j, ,d）的形式输出，其中：（的形式输出，其中：（i，j）指示迷宫中指示迷宫中的一个坐标，的一个坐标， d表示走到下一坐标的方向。表示走到下一坐标的方向。课程设计课程设计pp-8数据结构数据结构测试数据：测试数据： 左上角（左上角（1 1, ,1 1

7、）为入口，右下角（）为入口，右下角（m,nm,n）为出口。为出口。选作内容：选作内容： （1 1）编写递归形式的算法，求得迷宫中的所有可）编写递归形式的算法，求得迷宫中的所有可能的通路；能的通路； （2 2）以方阵的形式输出迷宫及其通路迷宫中的所）以方阵的形式输出迷宫及其通路迷宫中的所有可能的通路；有可能的通路；课程设计课程设计pp-9数据结构数据结构题目3 3 二叉排序树的应用二叉排序树的应用 问题描述：问题描述： 利用二叉排序树对顺序表进行排序。利用二叉排序树对顺序表进行排序。基本要求：基本要求： （1 1）生成一个顺序表）生成一个顺序表L;L; （2 2）对所生成的顺序表对所生成的顺序表

8、L L构造二叉排序树构造二叉排序树; ; （3 3）利用栈结构实现中序遍历二叉排序树）利用栈结构实现中序遍历二叉排序树; ; （4 4）中序遍历所构造的二叉排序树将记录由小到）中序遍历所构造的二叉排序树将记录由小到大输出。大输出。测试数据：测试数据： 用伪随机数产生程序产生随机数，用伪随机数产生程序产生随机数，表长不小于表长不小于2020。选作内容：选作内容： 实现二叉排序树的插入和删除操作。实现二叉排序树的插入和删除操作。课程设计课程设计pp-10数据结构数据结构问题描述：问题描述： 设计一个交通咨询系统，为自驾游旅行者客咨询从任设计一个交通咨询系统，为自驾游旅行者客咨询从任一个城市到另一个

9、城市之间的最短路径问题。设计分三一个城市到另一个城市之间的最短路径问题。设计分三个部分，一是建立交通网络图的存储结构；二是解决单个部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现两个城市顶点之间的最短源最短路径问题；最后再实现两个城市顶点之间的最短路径问题。路径问题。基本要求：基本要求： 1 对城市信息对城市信息(城市名、城市间的里程城市名、城市间的里程)进行编辑：具进行编辑：具备添加、修改、删除功能；备添加、修改、删除功能； 2 咨询以用户和计算机对话方式进行，要注意人机交咨询以用户和计算机对话方式进行，要注意人机交互的屏幕界面。由用户选择输入起点、终点，输出信息：互

10、的屏幕界面。由用户选择输入起点、终点，输出信息：旅行者从起点、终点经过的每一座城市。旅行者从起点、终点经过的每一座城市。 3. 主程序可以有系统界面、菜单；也可用命令提示方主程序可以有系统界面、菜单；也可用命令提示方式；选择功能模块执行，要求在程序运行过程中可以反式；选择功能模块执行，要求在程序运行过程中可以反复操作。复操作。题目4 4 交通咨询系统交通咨询系统课程设计课程设计pp-11数据结构数据结构测试数据：测试数据： 参考参考数据结构（数据结构（C语言版）语言版）（严蔚敏（严蔚敏 吴伟民吴伟民编著）编著）7.6节图节图7.33的交通图。的交通图。 答辩测试数据：北京到乌鲁木齐；北京到昆明

11、；答辩测试数据：北京到乌鲁木齐；北京到昆明；广州到哈尔滨；乌鲁木齐到南昌；沈阳到昆明。广州到哈尔滨；乌鲁木齐到南昌；沈阳到昆明。选作内容：选作内容： 考虑由于路况不同，不同城市间自驾旅行每百公考虑由于路况不同，不同城市间自驾旅行每百公里油耗不同，为旅行选择最经济路线。里油耗不同，为旅行选择最经济路线。课程设计课程设计pp-12数据结构数据结构题目5 5 内部排序算法的比较内部排序算法的比较 问题问题描述：描述： 通过比较各通过比较各内部排序算法的关键字比较次数和关内部排序算法的关键字比较次数和关键字移动的次数，键字移动的次数，以取得直观感受。以取得直观感受。 基本要求：基本要求： 1、待待排序

12、表的表长不小于排序表的表长不小于100100； 2 2、至少要用、至少要用5 5组不同的输入数据作比较；组不同的输入数据作比较； 3 3、排序算法不少于、排序算法不少于5 5种；种； 4 4、最后要对结果作简单的分析。、最后要对结果作简单的分析。 测试数据：测试数据： 用伪随机数产生程序产生。用伪随机数产生程序产生。 选作内容：选作内容： 对不同的表长做试验分析两个指标相对于表长变对不同的表长做试验分析两个指标相对于表长变化关系。化关系。实实 现现 要要 点点 课程设计课程设计pp-14数据结构数据结构题目1 1 课程设计课程设计pp-15数据结构数据结构多项式的逻辑结构：视为线性表多项式的逻

13、辑结构：视为线性表 数据元素数据元素 (coef,exp) 表示多项式项表示多项式项 coefxexp ，coef是该项的系数，是该项的系数，exp是变是变元元x的指数。的指数。 ( ( 顺序表示顺序表示 线性表长度事先难以确定；线性表长度事先难以确定； 算术运算需插入和删除元素算术运算需插入和删除元素。课程设计课程设计pp-16数据结构数据结构课程设计课程设计pp-17数据结构数据结构 多项式相加多项式相加课程设计课程设计pp-18数据结构数据结构带头结点的线性链表类型(pp37) typedef struct LNode / 结点类型 ElemType data; LNode *next;

14、 *Link,*Position; struct LinkList / 链表类型 Link head,tail; / 分别指向线性链表中的头结点和最后一个结点 int len; / 指示线性链表中数据元素的个数 ; 课程设计课程设计pp-19数据结构数据结构分配由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所指结点voi

15、d FreeNode(Link &p) / 释放p所指结点 free(p); p=NULL; 课程设计课程设计pp-20数据结构数据结构构造一个空的线性链表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; 课程设计课程设计pp-21数据结构数据结构销毁线性链表LStatus DestroyList(LinkList &L) / 销毁线性链表L，L

16、不再存在 ClearList(L); / 清空链表 FreeNode(L.head); L.tail=NULL; L.len=0; return OK; 课程设计课程设计pp-22数据结构数据结构将线性链表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; 课程设计

17、课程设计pp-23数据结构数据结构将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; 课程设计课程设计pp-24数据结构数据结构删除链表中的第一个结点Status DelFirst(LinkList &L,Link h,Link &q) / 形参增

18、加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; / 链表空 课程设计课程设计pp-25数据结构数据结构Status Append(LinkList &L,Link s) / 将指针s (s-data为第一个数据元素)所指 (彼此/ 以指针相 链，以NULL结尾)的一串结点链接在/ 线性链表L的最后一个结点之后, 并改变

19、链表L / 的尾指针指向新的尾结点 int i=1; L.tail-next=s; while(s-next) s=s-next; i+; L.tail=s; L.len+=i; return OK; 链接两个单链表链接两个单链表课程设计课程设计pp-26数据结构数据结构返回p所指结点中数据元素的值ElemType GetCurElem(Link p) /已知p指向线性链表中的一个结点， /返回p所指结点中数据元素的值 return p-data; 判断线性链表判断线性链表L为空表为空表Status ListEmpty(LinkList L) / 若线性链表L为空表，则返回TRUE，否则返回F

20、ALSE if (L.len) return FALSE; else return TRUE; 课程设计课程设计pp-27数据结构数据结构返回线性链表L中头结点的位置Position GetHead(LinkList L) / 返回线性链表L中头结点的位置 return L.head; 返回p所指结点的直接后继的位置 Position NextPos(Link p) / 已知p指向线性链表L中的一个结点， / 返回p所指结点的直接后继的位置 / 若无后继，则返回NULL return p-next; 课程设计课程设计pp-28数据结构数据结构LocateElem:判定升序链表L中是否存在与e相

21、等的元素 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; /

22、到表尾或compare(p-data,e)0 else q=p; return TRUE; / 找到 课程设计课程设计pp-29数据结构数据结构项结点项结点 Term typedef struct / 项的表示项的表示,多项式的项作为多项式的项作为LinkList的数据元素的数据元素pp42 float coef; / 系数系数 int expn; / 指数指数 term,ElemType; / 两个类型名两个类型名:term用于本用于本ADT,/ElemType为为LinkList的数据对象名的数据对象名课程设计课程设计pp-30数据结构数据结构 typedef LinkList polyn

23、omial; #define DestroyPolyn DestroyList #define PolynLength ListLength课程设计课程设计pp-31数据结构数据结构多项式的基本操作的函数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); 课程设计课程设计pp-32数据结构数据结构建立表示一元多项式 void C

24、reatPolyn(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);

25、 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); 系数处理课程设计课程设计pp-35数据结构数据结构一元多项式系数取反void Opposite(polynomial Pa) / 一元多项式系数取反一元多项式系数取反 Position p; p=Pa.head; while(p-next) p=p-next; p-data.coef*=-1; 多项式减法

26、多项式减法 void SubtractPolyn(polynomial &Pa,polynomial &Pb) / 多项式减法多项式减法:Pa=Pa-Pb,并销毁一元多项式并销毁一元多项式Pb Opposite(Pb); AddPolyn(Pa,Pb); 课程设计课程设计pp-36数据结构数据结构打印输出一元多项式P void PrintPolyn(polynomial P) / 打印输出一元多项式打印输出一元多项式P Link q; q=P.head-next; / q指向第一个结点指向第一个结点 printf( 系数系数 指数指数n); while(q) printf(%f %dn,q-d

27、ata.coef,q-data.expn); q=q-next; 课程设计课程设计pp-37数据结构数据结构void CreatPolyn(polynomial &P,int m) / 算法算法2.22void AddPolyn(polynomial &Pa,polynomial &Pb) / 算法算法2.23void PrintPolyn(polynomial P) / 打印输出一元多项式打印输出一元多项式 主函数题目2 2 迷宫问题迷宫问题课程设计课程设计pp-39数据结构数据结构 问题：问题：以一个以一个m*n的方阵表示迷宫，的方阵表示迷宫，0和和1分别表示迷分别表示迷宫中的通路和障碍。

28、迷宫问题要求求出从入口（宫中的通路和障碍。迷宫问题要求求出从入口（1,1）到出口（到出口（m,n）的所有通路，或得出没有通路的结论。的所有通路，或得出没有通路的结论。 思路：思路：从入口（从入口（1,1）出发，按某一方向向前搜索，若）出发，按某一方向向前搜索，若能走通（未走过），即某处可以到达，则到达新点，能走通（未走过），即某处可以到达，则到达新点，否则，试探下一方向；若所有的方向都没有通路，则否则，试探下一方向；若所有的方向都没有通路，则沿原路返回前一点，换下一个方向再试探，直到所有沿原路返回前一点，换下一个方向再试探，直到所有可能的通路都探索到，或找到一条通路，或无路可走可能的通路都探索

29、到，或找到一条通路，或无路可走又返回到入口点。又返回到入口点。 用一个栈保存所能到达的每一点的下标及从该点前进用一个栈保存所能到达的每一点的下标及从该点前进的方向。的方向。课程设计课程设计pp-40数据结构数据结构需要解决的四个问题（1）表示）表示迷宫的数据结构迷宫的数据结构 利用利用mazemn表示一个迷宫，表示一个迷宫， mazemn=0，1。 1表示通路，表示通路， 0 表示不通。表示不通。 为简化问题用为简化问题用mazem+2n+2来表示一个迷宫，来表示一个迷宫，这样每个点的试探方向都为这样每个点的试探方向都为8。课程设计课程设计pp-41数据结构数据结构00000000000011

30、101110010101111000100000100011101110010011000000110011000000000000课程设计课程设计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(x,y,d) 出栈；出栈； 求出下一个要试探的方向求出下一个要试探的方向d+； while (还有剩余试探的方向）还有剩余试探的方向） if（d方向可走）方向可走） (x,y,d)入栈；入栈； 求新

31、点坐标（求新点坐标（i，j）；）； 将新点（将新点（i，j）切换为当前点（切换为当前点（x，y）；）； if (x,y)=(m,n) 结束；结束； else 重置重置d=0; else d+; 课程设计课程设计pp-46数据结构数据结构题目3 3 利用二叉排序树对顺序表进行排序利用二叉排序树对顺序表进行排序涉及知识面涉及知识面1 1 排序排序2 2 查找查找3 3 树树4 4 顺序表顺序表5 5 栈栈设计内容、要求：设计内容、要求： 生成一个顺序表生成一个顺序表L L 对所生成的顺序表对所生成的顺序表L L构造二叉排序树构造二叉排序树 利用栈结构实现中序遍历二叉排序树利用栈结构实现中序遍历二叉

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

33、树为空树）初始化二叉排序树为空树 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即为由小到大排序的顺序表。即为由小到大排序的顺序表。课程设计课程设计pp-50数据结构数据结构函数表InitList_Sq, ListInsert_Sq, InsertBST, SearchBS

34、T, InOrderTraverser,output, InitStack, StackEmpty, Push, Pop课程设计课程设计pp-51数据结构数据结构四四 函数调用关系函数调用关系 mainInitList_Sq InOrderTraverser ListInsert_Sq InsertBST SearchBST output InitStack StackEmpty Push Pop课程设计课程设计pp-52数据结构数据结构问题描述：问题描述： 设计一个交通咨询系统，为自驾游旅行者客咨询设计一个交通咨询系统，为自驾游旅行者客咨询从任一个城市到另一个城市之间的最短路径问题。设从任一

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

36、ite函数操作。函数操作。(2) 数据的逻辑结构。数据的逻辑结构。 根据设计任务的描述，其城市之间的旅游交通问根据设计任务的描述，其城市之间的旅游交通问题是典型的图结构，可看作为有向图，图的顶点是城题是典型的图结构，可看作为有向图，图的顶点是城市，边是城市之间的市，边是城市之间的里里程。程。算法思路课程设计课程设计pp-54数据结构数据结构(3) 数据的存储结构。数据的存储结构。 采用邻接表和邻接矩阵都可作为数据的存储结构，采用邻接表和邻接矩阵都可作为数据的存储结构，但当邻接边不多时，宜采用邻接表，以提高空间的存但当邻接边不多时，宜采用邻接表，以提高空间的存储效率。这里建议采用邻接表作为数据的

37、存储结构。储效率。这里建议采用邻接表作为数据的存储结构。(4) 用不同的功能模块对城市信息和交通信息进行编辑。用不同的功能模块对城市信息和交通信息进行编辑。添加、修改、删除功能可用菜单方式或命令提示方式。添加、修改、删除功能可用菜单方式或命令提示方式。只要能方便的对城市信息和交通信息进行管理即可，只要能方便的对城市信息和交通信息进行管理即可，但要注意人机界面，具体实现自行设计。这些工作有但要注意人机界面，具体实现自行设计。这些工作有不小的工作量。不小的工作量。课程设计课程设计pp-55数据结构数据结构(5) 最优决策功能模块最优决策功能模块 读入城市信息和交通信息，用邻接表生成含权网络，读入城

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

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

40、系的城市求得决策值得决策值(最短时间最短时间)，若该值是局部最优值且该城市，若该值是局部最优值且该城市不在栈不在栈(队队)中，则进栈中，则进栈(队队)，直至栈，直至栈(队队)为空。为空。课程设计课程设计pp-57数据结构数据结构 输出结果。输出结果。 从目的城市出发，搜索到出发城市，所经过的城市从目的城市出发，搜索到出发城市，所经过的城市均入栈，再逐一出栈栈中的城市，输出保存在表头数组均入栈，再逐一出栈栈中的城市，输出保存在表头数组中对应城市的信息中对应城市的信息(对方城市的出发信息，里程、时间、对方城市的出发信息，里程、时间、费用等费用等)及最终结果。即输出依次于何时何地乘坐几点及最终结果。即输出依次于何时何地乘坐几点的飞机或火车于何时到达何地；最终所需的最快需要多的飞机或火车于何时到达何地；最终所需的最快需要多长时间才能到达及旅费，或者最少需要多少旅费才能到长时间才能到达及旅费，或者最少需要多少旅费才能到达及时间。达及时间。课程设计课程设计pp-58数据结构数据结构题目5 5 内部排序算法的比较内部排序算法的比较略