《《数据结构（C语言描述）》-斯庆巴拉-电子教案 第10章实例分析》由会员分享，可在线阅读，更多相关《《数据结构（C语言描述）》-斯庆巴拉-电子教案 第10章实例分析（39页珍藏版）》请在金锄头文库上搜索。
1、第10章 案例分析,从实际问题中抽象出相应的数据类型 设计相应的数据结构及算法 实现抽象的数据类型，编制相应的程序代码并调试,第10章 案例分析,10.1 约瑟夫问题 10.2 迷宫求解 10.3 排队问题 10.4 教学计划中的课程编排 10.5 简单的学籍管理系统 本章总结,10.1 约瑟夫问题,10.1.1 问题描述 10.1.2 问题分析 10.1.3 函数设计 10.1.4 上机调试,10.1.1 问题描述,题目内容： 有n个人按1、2、3、n的顺序围成一圈，现从第s个人开始按1、2、3、m的顺序报数，数到m的人出圈，接着从出圈的下一个人开始重复此过程，直到所有人出圈为止。 基本要求
2、： 输入不同的n和m的值，按出圈顺序输出每个人的序号。,10.1.2 问题分析,输入信息： 要求输入n、s和m的值，并对输入值合法性进行判断。n和m的值不能太大，在本程序中限制在1000以下。 数据结构的确定： 将n个人看成是一个包含n个元素的线性表，表的长度就是人数n，线性表中每个元素的值就是他的序号。 存储结构的确定： 报数到m的人出圈，看成是从线性表中删除该元素。另外，数到最后一个人后接着返回到第一个人继续报数，所以采用循环单链表的形式存储线性表比较合适。,10.1.3 函数设计,程序源代码为： #include #include typedef struct Lnode int dat
3、a ; Lnode *next ; *Link;,void CreateList( Link &L , int n ) 建立一个n个结点的循环单链表 void DeleteList( Link &L , Lnode * p, Lnode *q) 从循环单链表中删除结点p void josephus(Link &L,int s , int m ) ,void main() Link L=NULL; int m,n,s; printf(“请输入围圈人数、报数的开始位置和报数的上限n“); scanf(“%d,%d,%d“,10.1.4 上机调试,第一组测试数据：n=20 s=5 m=12 输入输出
4、结果为： 请输入围圈人数、报数的开始位置和报数的上限 20,5 12 5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,1,2,3,4 Press any key to continue,10.2 迷宫求解,10.2.1 问题描述 10.2.2 问题分析 10.2.3 函数设计 10.2.4 上机调试,10.2.1 问题描述,题目内容： 求出从给定的迷宫的入口到出口的路径，路径中不能存在回路，可以不是所有路径中最短路径。,10.2.2 问题分析,迷宫求解中通常将迷宫用矩阵表示，转换成矩阵表示后，矩阵中用元素值0来代表通，以元素值1来代表不通。迷宫求解问题就变
5、成了在矩阵中搜索一条从入口元素到出口元素的元素值全为0的元素序列的搜索过程。 在整个搜索过程中，一方面需要将每一步探索到的当前位置都保存到当前路径中，直至到达出口为止；另一方面，如果当前位置是不可通的，则需要沿原路退回到上一个位置处，重新进行下一个位置的探索。所以，定义一个栈，每探索到一个新当前位置都将它入栈，可通继续探索下一个位置，若不可通，做出栈操作，朝另外的其他方向进行探索，直至到达出口处，栈中保存的就是所求路径。,10.2.3 函数设计,程序源代码为： # include # include # define m 6 # define n 6 struct postion /路径类型定
6、义 int row; int col; b4; /存放移动的四种可能性 struct stack /顺序栈类型定义 postion elem51; int top; ;,void creat(int Am+2n+2) 建立迷宫算法 void InitStack( stack &s) 顺序栈初始化算法 void push(stack &s,postion now) 顺序栈的进栈算法 postion pop(stack &S) 顺序栈的出栈算法 bool path(int Am+2n+2,postion ru, postion chu, stack &s, postion b) 求迷宫入口到出口的
7、路径算法，存在路径返回true，否则返回false,void main( ) /主函数 int Am+2n+2; postion ru,chu; creat(A); printf(“创建的迷宫为：n“); for(int i=0;im+2;i+) for(int j=0;jn+2;j+) printf(“%d “,Aij); printf(“n“); stack s; InitStack(s);,printf(“请输入迷宫入口位置：“); scanf(“%d,%d“, ,10.2.4 上机调试,第一组测试数据为： 输入和输出结果： 输入迷宫： （略） 创建的迷宫为：（略） 请输入迷宫入口位置：
8、2,1 请输入迷宫出口位置：3,6 所得路径为： （略） Press any key to continue,10.3 排队问题,10.3.1 问题描述 10.3.2 问题分析 10.3.3 函数设计 10.3.4 上机调试,10.3.1 问题描述,题目内容：使用队列模拟银行的排队存钱和取钱问题。 基本要求：设银行有n个办理业务的窗口，可同时为n位顾客办理各项业务。当顾客进门时，如果有空窗口，则可以立即办理手续，否则需要在旁边设置的可供等候的椅子上依次排队等候。一旦有顾客办理完业务离开时，排在队头的顾客便可以到窗口办理手续。,10.3.2 问题分析,银行内有n个办理业务的窗口，将n个窗口设成一
9、个线性表，线性表包含两个成员：一个是长度为n的一维数组，数组元素的下标就是窗口的编号。另一个成员用来记录元素个数（数组元素个数小于n时，就可以有顾客直接办理业务，同时元素个数加一；同样顾客离开时，元素个数减一。数组元素个数为n时，顾客需要在等候队列中依次排队等候）。 对于排队等候办理业务的顾客来讲，先排队的先办理业务。所以可以用一个队列来模拟排队过程。 顾客到达银行和离开银行事件由键盘输入来模拟，每位顾客都有唯一的编号。,10.3.3 函数设计,# include #include #include #define n 6 struct List int An+1; /顾客用来办理业务的n个窗
10、口 int len; /表示数组中的元素个数 L; struct Lnode ; /链表结点类型（略） struct Linkqueue /等候队列的类型定义 Lnode *front; Lnode *rear; Q;,void Initshuzu( ) 初始化线性表的算法 void Initqueue( ) 初始化队列的算法 void Enqueue(Linkqueue *Q,int elem) 进队算法 int Dlqueue(Linkqueue *Q) 出队算法 void print1( ) 输出数组算法 void print2( ) 输出队列算法 void daoda(int x )
11、解决顾客到达事件算法 void likai(int x) 解决顾客离开事件算法,void main( ) /主函数 int c,x; Initshuzu( ); Initqueue( ); while (1) printf(“按提示进行输入：n“); printf(“顾客到达请输入：1 n“); printf(“顾客离开请输入：2 n“); printf(“查看办理业务的顾客情况请输入：3 n“); printf(“查看等候办理业务的顾客情况请输入：4n“); printf(“退出请输入：5 n“); scanf(“%d“,switch (c) case 1: printf(“请输入到达顾客的
12、编号：n“); scanf(“%d“,10.3.4 上机调试,输入和输出结果为： 按提示进行输入： 顾客到达请输入：1 顾客离开请输入：2 查看办理业务的顾客情况请输入：3 查看等候办理业务的顾客情况请输入：4 退出请输入：5 （略）,10.4 教学计划中的课程编排,10.4.1 问题描述 10.4.2 问题分析 10.4.3 函数设计 10.4.4 上机调试,10.4.1 问题描述,题目内容： 高校中每个专业都有它固定的教学计划，学生所要必修的课程将比较均匀地分布在每个学期中。由于开设的课程之间存在着前导课和后续课的关系，所以每学期开设的课程都要满足它的前导和后续关系，也就是说学习一门课程时
13、，它的前导课必须在前面几个学期中已开设，它的后续课程不能在本学期开设。,10.4.2 问题分析,制定教学计划就是从AOV网求出一种满足条件的拓扑序列。 编排课程还需要所有课程比较均匀地分布在各个学期，设一学期最多能开设四门课，最少开设二门课。 具体实现方法： （1）将图10-2（a）中给定的图以邻接表的形式存储，并编写一个图的建立算法。 （2）编写一个对给定图求拓扑序列的算法。每次扫描后得到的序列将存储到一个队列中，另外在设一个后备队列，只有当前队列中的元素全部出队，才可以将后备队列中的元素全部移到当前队列中。,10.4.3 函数设计,#include #include #include #i
14、nclude #define n 14 #define e 14 struct edgenode /定义邻接表中的边结点类型 int adjvex; /邻接点域 edgenode *next; ;,struct adjlist char data20; int indegree; edgenode *firstnode; Gn+1; struct Lnode /队列链表结点类型 int data; Lnode *next; struct Linkqueue /等候队列的类型定义 Lnode *front; Lnode *rear;,void Initqueue(Linkqueue ,10.4.
15、4 上机调试,输入输出结果为：（图10-2中给定的课程编排结果） 输入邻接表的14个顶点 c1 c2 c3 c4 c5 c6 c7 c8 c9 c10 c11 c12 c13 c14（每个顶点后都有回车） 输入邻接表的14条边（略） 第1学期的课程为： c1 c2 c3 第2学期的课程为： （略） Press any key to continue,10.5 简单的学籍管理系统,10.5.1 问题描述 10.5.2 问题分析 10.5.3 函数设计 10.5.4 上机调试,10.5.1 问题描述,题目内容： 在学校中对在校生学籍信息的管理是一项庞大的工程,它要求能够完成信息的输入、修改、插入和
16、删除工作，还要求按照特定的信息进行查找、排序和打印学生信息。如果对学生信息管理进行分析，可将学生全部信息分成若干个相互有联系的不同表格来表示。 要求： 本例中主要解决对学生基本情况登记表进行输入、插入、删除、排序和查询等操作。,10.5.2 问题分析,学生情况登记表看成是一个线性表，采用顺序存储方式，则类型定义： struct student int num; / 表示学号 char name12; / 表示姓名 int age; ； # define size 1000 struct List student stu size ; int len ; ,10.5.3 函数设计,程序源代码为： #
