数据结构上机实训指导结构设计.doc

数据结构上机实训指导结构设计上机实习规范上机实习是数据结构课程教学不可缺少的重要环节。通过上机实习编写解决简单应用问题的程序，达到如下训练目的： l 进一步理解和掌握课堂上所学各种基本数据结构的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。 l 掌握软件设计的基本内容和设计方法，并培养学生规范化软件设计的能力。 l 进一步熟练掌握一门高级程序设计语言。 常用的软件开发方法，是将软件开发过程分为分析、设计、实现和维护四个阶段，为了培养一个软件工作者所应具备的科学工作的方法和作风，制订了数据结构课程中上机实习步骤主要包含的内容： 1) 问题分析与系统结构设计充分地分析和理解问题本身，明确问题要求做什么，限制条件是什么。按照以数据结构为中心原则分模块，即先定义所需的数据结构，然后定义能在它上面进行的操作，使得对数据结构的存取仅通过这些操作实现。注意：本步骤强调的是做什么，而不是怎么做。 2) 数据类型和系统设计 设计这一步骤中需分逻辑设计和详细设计两步实现。逻辑设计是指对问题描述中涉及的操作对象及定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。详细设计则为定义相应的存储结构，并写出各过程和函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。作为逻辑设计的结果，应写出每个抽象数据类型的定义（包括数据结构的描述和每个基本操作的规格说明），各个主要模块的算法，并画出模块之间的调用关系图。详细设汁的结果是对数据结构和基本操作的规格说明作出进一步的求精，此步骤要对函数规格说明的进一步求精：用顺序语句、循环语句和赋值语句加上自然语言写出算法框架，在C语言中分别由赋值、for/while和if/switch等语句实现，这时不必确定很多局部数据结构和变量。算法的目的就是表达任务在求精的过程中，应尽量避免陷入语言细节，不必过早表述辅助数据结构和局部变量。 3) 编码 编码，即程序设计，是用某种高级语言表达出来，是对详细设计的结果进一步求精。程序的每行不要超过60个字符；每个函数体，即不计头和规格说明的部分，一般不要超过40行，最长不得超过60行。否则还应划分，要控制IF语句连续嵌套的深度。 4) 静态检查 在上机之前，应该用笔在纸上写出详细的程序编码，并做认真地静态检查。多数初学者在编好程序后处于以下两种状态之一：一种是对自己的“精心作品”的正确性确信不疑；另一种是认为上机前的任务已经完成，纠查错误是上机的工作。这两种态度是极为有害的。对一般的程序设计者而言，当编写的程序长度超过50行时，通常会含有语法错误或逻辑错误。上机动态调试决不能代替静态检查，否则调试效率将是极低的。静态检查主要有两种方法，一是用一组测试数据手工执行程序；二是通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑，在这个过程中再加入一些注解。 5) 上机准备 上机准备包括以下几方面： l 熟悉C语言用户手册或程序设计指导书。 l 熟悉机器的操作系统和语言集成环境的用户手册，尤其是最常用的命令操作，以便顺利进行上机的基本活动。 l 掌握调试工具，考虑调试方案，设计测试数据并手工得出正确结果。6) 上机调试程序一般要在静态检查无误后，才上机调试，调试最好分模块进行，自底向上，即先调试低层过程或函数。必要时可以另写一个调用驱动程序。这种表面上麻烦的工作实际上可以大大降低调试所面临的复杂性，提高调试工作效率。 在调试过程中可以不断借助借助系统提供的调试工具确定错误。调试正确后，认真整理源程序及其注释，印出带有完整注释的且格式良好的源程序清单和结果。7) 整理上机实习报告 上机实习报告的内容： 问题描述： 描述问题，简述题目要解决的问题是什么。规定软件做什么。原题条件不足时应补全。 分析：以无歧义的陈述说明程序设计的任务，强调的是程序要做什么 设计：说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。每个函数声明和规格说明；列出每个函数所调用和被调用的函数，也可以通过调用关系图表达。 实现注释：各项功能的实现程度、在完成基本要求的基础上还实现了什么功能。 程序实现：写出每个操作的算法（操作过程） 程序运行情况：写出输入数据及运行结果 实习心得：调试过程中遇到的主要问题是如何解决的；对设计和编码的回顾讨论和分析；改进设想；经验和体会等。 附录：源程序清单源程序要加注释，除原有注释外再用钢笔加一些必要的注释和断言。上机实习报告范例上机实训1： 约瑟夫（joseph）问题姓名： 班级： 日期：年月日1. 实例描述 约瑟夫（joseph）问题是由编号为1，n的n 个人按顺时针方向围坐一圈，从第1号的人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。2. 实例分析 设计的程序是模拟约瑟夫问题，按照出列的顺序印出各人的编号。要求： （1）输入总人数，建立一个顺序表或单向循环链表存储n个人的编号信息（2）输出在（1）中建立的顺序表或单向循环链表上实现约瑟夫问题的求解3. 设计思路为完成本程序的功能。（1）设置变量num标记出列人数，控制循环执行次数，当num取值0到n-1时，执行循环，否则退出循环。（2）设置变量count累计报数人数，决定某一个人是否出列，count从1开始累计，当count=m时，做如下处理：刚刚报数的人需要出列，即将其所在结点从表中删除。若采用循环链表结构，为了实现该操作，需要两个工作指针pre和p，分别指向链表中的两个相邻结点；出列人数num加1；count重新置1，准备开始下一轮报数。需要的数据结构定义为： typedef struct point int data;int No;struct point *next;LNode,*LinkList;本程序包含3个函数： 主函数main()生成单向循环链表create()实现报数问题search()4. 程序实现 #include stdlib.h#include stdio.h#define NULL 0typedef struct point int data;int No;struct point *next;LNode,*LinkList;int n,m;LinkList create() /*生成单向循环链表并返回*/int i;LinkList head, tail, new;head=NULL;printf(ninput n (总人数): );scanf(%d,&n);printf(ninput m : );scanf(%d, &m);for (i=1;iNo=i;if (head=NULL) /*链表的第一个结点插入*/ head=new; tail=head; else /*链表的其余结点插入*/ tail-next=new; tail=new; tail-next=head; /*循环单链表的生成*/return head;void search(LinkList head ) /* 用循环链表实现报数问题*/int count,num;LinkList pre, p;num=0; count=1;p=head;printf(noutput data : );while (numnext; while (countnext=p-next; /*报m的人出列*/printf(%3d,p-No);free(p);p=pre-next;count=1;num+;main() LinkList head;clrscr();head=create();search (head);getchar();getchar();5. 测试结果 input n (总人数) : 8input m : 3output data : 3 6 1 5 2 8 4 76. 实习心得（略）1 上机实训1：线性表基本操作一、 实训目的通过本实训，掌握线性表的逻辑结构、存储结构及线性表的两种存储结构的建立插入、删除等操作。通过对相关算法的C语言实现，掌握线性表算法的时间效率分析。重点是掌握线性表相关算法的基本思路、时间复杂度的计算。二、 实验理论知识逻辑结构线性表的逻辑结构是n（n 0）个结点的有穷序列。为了便于讨论，有时将含n（n0）个结点的线性结构表示为（a1，a2，a3，a4，an），其中ai代表一个结点。a1称为起始结点，an称为终端结点，i称为ai在线性结构中的序号或位置。对于任意一对相邻结点ai，ai+1（1icoef=m; p-exp=-1; tail=p;for(i=1;icoef=coef;new-exp=exp;new-next=NULL;tail-next=new; tail=new;void derivative(polynode p) /*对一元多项式的有序链表p求导*/polynode pa,qa;pa=p-next;qa=p;while(pa)if(pa-exp=0) /* 从多项式中删除*pa结点并释放存储空间*/qa-next=pa-next;free(pa); p-coef-;pa=qa-next;else /*修改*pa结点的系数和指数*/ pa-coef*=pa-exp;pa-exp-=1;qa=pa;pa=pa-next;void printpolyn(polynode p) /* 打印输出一元多项式 p */int n; polynode q;q =p-next; n =0; while (q)n+;if (n=1) if (q-exp=0) printf(%.2f, q-coef);else if (q-exp=1) if (q-coef=1) printf(x);else if (q-coef=-1) printf(-x);else printf(%.2f, q-coef); printf(x); else if (q-coef=1) printf(x%d, q-exp);else if( q-coef=-1) printf(-x%d, q-exp);else printf(%.2fx%d, q-coef, q-exp);/*if(n=1)*/else if (q-exp=0) printf(+%.2f, q-coef);else if (q-exp=1) if (q-coef=1) printf(+x);else if (q-coef=-1) printf(-x);else if (q-coef0) printf(+%.2fx, q-coef);else printf(%.2fx, q-coef);else if (q-coef=1) printf(+x%d, q-exp);else if( q-coef=-1) printf(-x%d, q-exp);else if (q-coef0) printf(+%.2fx%d, q-coef, q-exp);else printf(%.2fx%d, q-coef, q-exp);q =q-next;/*while*/*printpolyn*/main() polynode p;int m; printf(ninput m (多项式的项数) : );scanf(%d,&m);p=(polynode)malloc(sizeof(pnode);creatpolyn(p,m);printf(np(x)=);printpolyn(p);derivative(p);printf(np(x)=);printpolyn(p);getchar();getchar();【测试数据与结果】input m (多项式的项数) : 5input coef(系数) and exp(指数) : 1 5input coef(系数) and exp(指数) : 2 4input coef(系数) and exp(指数) : 3 3input coef(系数) and exp(指数) : 4 2input coef(系数) and exp(指数) : 5 1p(x)=x5+2.00x4+3.00x3+4.00x2+5.00xp(x)=5.00x4+8.00x3+9.00x2+8.00x+5.00【实例2】顺序存储的线性表插入与删除操作【实例要求】1) 建立线性表2) 从线性表插入一个元素3) 从线性表中删除一个元素【参考程序】#include#define MAXSIZE 100int listMAXSIZE;int n;/*在线性表中插入元素*/int sq_insert(int list, int *p_n, int i, int x)int j;if (i*p_n) return(1);if (*p_n=MAXSIZE) return(2);for (j=*p_n+1; ji; j-)listj=listj-1;listi=x;(*p_n)+;return(0);/*删除线性表中的元素*/int sq_delete(int list, int *p_n, int i)int j;if (i=*p_n) return(1);for (j = i+1; j=*p_n; j+)listj-1 = listj;(*p_n)-;return(0);/*主程序*/void main()int i,x,temp;printf(please input the number for nn);printf(n=);scanf(%d,&n);for (i=0; i=n; i+)printf(list%d=,i);scanf(%d,&listi);printf(The list before insertion isn);for (i=0; i=n; i+) printf(%d ,listi);printf(n);printf(please input the position where you want to insert a valuenposition=);scanf(%d,&i);printf(please input the value you want to insert.nx=);scanf(%d,&x);temp=sq_insert(list,&n,i,x);switch(temp)case 0:printf(The insertion is successful!n);printf(The list is after insertion isn);for(i=0; i=n; i+) printf(%d ,listi);printf(n);printf(%dn,n);break;case 1:case 2:printf(The insertion is not successful!n);break;/*deleting*/printf(The list before deleting isn);for (i=0; i=n; i+) printf(%d ,listi);printf(n);printf(please input the position where you want to delete a valuenposition=);scanf(%d,&i);temp=sq_delete(list,&n,i);switch(temp)case 0:printf(The deleting is successful!n);printf(The list is after deleting isn);for(i=0; ifront=Sq-rear,则称为队空，当(Sq-rear+1) mod MaxSize=Sq-front, 则称为队满。用链表表示的队列称为链队列，一个链队列显然需要两个分别指示队头和队尾的指针（分别称为头指针和尾指针）才能唯一确定。为了操作方便，给链队列添加一个头结点，并令头指针指向头结点。由此，空的链队列的判决条件为头指针和尾指针均指向头结点。链队列的操作即为单链表的插入和删除操作的特殊情况，只是尚需修改尾指针或头指针。三、 实训案例与分析【实例1】通用数制转换程序：将一个十进制数转换成其他进制的数。【实例分析】常用的数制有：二进制、八进制、十进制、十六进制。数制转换就是利用“待转换数与相应的进制数反复相除，所得余数的逆置即为转换结果”的方法，本实例的功能就是将一个十进制数转换成其他进制的数。假设待转换的十进制数为m，要转换成一个n进制的数，转换的具体方法如下：1) 用m除以n，得到相应的余数，将余数进栈stack（栈stack初始为空）。2) 用上一步所得的商再除以n，得到的余数继续进栈stack。3) 反复作（2）直到商为0，将最后一次所得的余数也进栈。4) 对栈stack依次进行出栈操作，直至栈stack为空，所得结果即为转换结果。【参考程序】#include stdio.h#define MAX 50char stackMAX; /*栈的类型定义为字符型*/int top=0; /*初始化栈*/void push(char x) /*进栈子函数*/ if(top=MAX) printf(overflow);else stacktop=x; /*进栈操作*/top+;char pop() /*出栈子函数,返回值类型为字符型*/ if(top=0) printf(underflow);return(NULL);top-; return(stacktop);int empty() /*判栈空子函数,空返回0,不空返回1*/ if(top=0)return(0);elsereturn(1);char fun(int x) /*整数转换成字符子函数*/ char t;switch(x) case 0:t=0;break;case 1:t=1;break;case 2:t=2;break;case 3:t=3;break;case 4:t=4;break;case 5:t=5;break;case 6:t=6;break;case 7:t=7;break;case 8:t=8;break;case 9:t=10;break;case 10:t=A;break; case 11:t=B;break;case 12:t=C;break;case 13:t=D;break;case 14:t=E;break;case 15:t=F;break;return(t); /*将转换后的字符返回,以备进栈*/void main() int m,n,x,t,r;char y;while(1) /*可循环输入待转换数*/printf(please input the operation:n); /*1为继续,0为退出*/printf(1 is continuet0 is exitn);scanf(%d,&t);if(t!=1&t!=0) /*如果输入的数非0,1,则提示重新输入*/continue;elseif(t=0) break;else printf(please input m:);scanf(%d,&m); /*输入待转换的十进制数*/printf(please input n,n);printf(n is 2,8 or 16:);scanf(%d,&n); /*输入要转换成的进制*/x=m%n; /*取第一次相除所得的余数*/r=m/n; while(r) /*如果商不为0,则继续取余求商*/y=fun(x); push(y); /*将字符型的余数进栈*/x=r%n; r=r/n; y=fun(x); push(y); /*将最后一次字符型余数进栈*/printf(the result is:n);while(empty() /*若栈不空,顺序输出出栈的结果*/printf(%c,pop();【测试数据与结果】please input the operation1 is continue 0 is exit1please input m:100please input n,n is 2,8 or 16:2 /*将100转换成2进制数*/the result is:1100100 /*100转换2进制的结果*/please input the operation1 is continue 0 is exit1please input m:100please input n,n is 2,8 or 16:8 /*将100转换成8进制数*/the result is:144 /*100转换8进制的结果*/ please input the operation1 is continue 0 is exit1please input m:100please input n,n is 2,8 or 16:16 /*将100转换成16进制数*/the result is:64 /*100转换成16进制的结果*/please input the operation1 is continue 0 is exit0【实例2】括号匹配问题【实例描述】假设一个算术表达式中可以包含3种括号：圆括号“（”和“）”，方括号“”和“”和花括号“”和“”，且这3种括号可按任意的次序嵌套使用（如：（）。设计一个程序，判别给定表达式中所含括号是否配对。该程序包括以下各项功能：1) 将算术表达式保存在带头结点的单链表或数组中2) 在1）中建立的单链表或数组上实现括号匹配问题的求解【实例分析】判断表达式中括号是否匹配，可通过栈来实现，简单说是当读入的字符为左括号时进栈，为右括号时退栈。退栈时，若栈顶元素是其对应的左括号，则新读入的右括号与栈顶左括号就可消去，栈顶元素出栈；若不是其对应的左括号，则说明括号不匹配，算法结束。如此下去，当输入表达式结束时，若栈为空，则说明表达式括号匹配，否则说明表达式括号不匹配。另外，由于本题是对表达式的括号匹配问题进行检查，所以对于表达式中输入的不是括号的字符一律不进行处理。【参考程序】#include stdio.htypedef struct nodechar ch;struct node *next;Lnode,*LinkList; /*类型描述*/LinkList create(void) /*生成单链表并返回*/char ch1;LinkList head, tail, new;head=(LinkList)malloc(sizeof(Lnode);head-next=NULL;tail=head;printf(n请输入表达式并且以#作为结束符：n);scanf(%c,&ch1);while(ch1!=#)new=(LinkList)malloc(sizeof(Lnode);new-ch=ch1;tail-next=new;tail=new;scanf(%c,&ch1);tail-next=NULL;return head;int Match(LinkList la)/*表达式存储在以la为头结点的单循环链表中，本算法判断括号是否配对*/char s30; /*s为字符栈，容量足够大*/int top=0;LinkList p;p=la-next; /*p为工作指针，指向待处理结点*/while (p!=NULL) switch (p-ch)case (:s+top=p-ch; break;case ):if(top=0|stop!= ()printf(n(no)括号不配对n); return(0);else top-;break;case : s+top=p-ch; break;case : if(top=0|stop!=)printf(n(no)括号不配对n); return(0);else top-;break;case : s+top=p-ch; break;case : if(top=0|stop!=)printf(n(no)括号不配对n); return(0);else top-;break;p=p-next; /* 后移指针*/*while*/if(top=0) printf(n(yes)括号配对n); return(1);elseprintf(n(no)括号不配对n); return(0);/*算法match结束*/main()LinkList head;clrscr();head=create();Match(head);getchar();【测试数据与结果】请输入表达式并且以#作为结束符：3*2+8*5-(2-1)*7+9-12#(yes)括号配对请输入表达式并且以#作为结束符：3+2)*6+7)-6*6-(9+6)-9+5# (no)括号不配对四、 思考项目1) 利用栈求解算术表达式的值。2) 模拟停车场管理的问题设停车场只有一个可停放几辆汽车的狭长通道，且只有一个大门可供汽车进出，汽车在停车场内按车辆到达的先后顺序依次排列，若车场内已经停满几辆汽车，则后来的汽车只能在门外的便道上等候，一旦停车场内有车开走，则排在便道上的第一辆车即可进入；当停车场内某辆车要离开时，由于停车场是狭长的通道，在它之后开入的车辆必须先退出停车场为它让路，待该辆车开出大门后，为它让路的车辆再按原次序进入车场。在这里假设汽车不能从便道上开走。试设计一个停车场管理程序。3 上机实训3：串的基本操作一、 实训目的 通过实训，掌握串的运算（赋值，比较，联结，插入子串，模式匹配等） 二、 实验理论知识 1) 串的基本概念及其含义 串( string)是由零个或多个字符组成的有限序列，一般记作:s=a1a2an(n0)，其中s为串的名字，用单引号括起来的字符序列为串的值；ai(1in)可以是字母、数字或其它字符（取决于程序设计语言所使用的字符集）；n为串中字符的个数，称为串的长度。2) 串的存储表示及其实现 l 顺序存储可以用一组地址连续的存储单元依次存放串的各个字符，这是串的顺序存储结构，也称为顺序串l 链式存储和线性表的链式存储结构相类似，也可采用链表方式存储串值。串的这种链式存储结构简称为链串。用链表存储字符串，每个结点需要有两个域：一个数据域（data）和一个指针域(Next)，其中数据域存放串中的字符，指针域存放后继结点的地址。3) 模式匹配问题三、 实训案例与分析 【实例1】串的存储与基本运算 【实例分析】在本实例中练习计算字符串的长度、字符串的复制、字符串的比较、字符串的连接、字符串的插入等基本操作。在设计时1) 编写一个菜单函数，根据不同情况做（1-5）不同选择。2) 如果选择1，即要求计算输入字符串的长度。3) 如果选择2，完成字符串的复制。4) 如果选择3，完成字符串的比较。5) 如果选择4，完成两个字符串的连接。6) 如果选择5，字符串的插入。【参考程序】#include #define MAX 128typedef enum fail,success status;typedef enum false,true boolean;main() int strlen();void strass();boolean strcmp();status strcat( );status strins();int t,n,i;boolean b;status st;char sMAX,s1MAX,s2MAX;printf(n1. The length of stringn);printf( 2. The assignment of stringn);printf( 3. A string compare with another string:n);printf( 4. A string connect with another string:n);printf( 5. A string to be inserted into another stringn);printf( Please input a operation:);/*输入操作选项*/scanf(%d,&t);switch(t) case 1:printf(please input a string:n);getchar();gets(s);n=strlen(s);printf(the length is: %d,n);break;case 2:printf(please input the first string:n);getchar();gets(s1);printf(please input the second string:n);getchar();gets(s2);strass(s1,s2);break;case 3:printf(please input the first string:n);getchar();gets(s1);printf(please input the second string: n);gets(s2);b=strcmp(s1,s2);if (b=true)printf(equaln);elseprintf(not equaln);break;case 4:printf(please input the first string:n);getchar();gets(s1);printf(please input the second string:n);gets(s2);st=strcat(s1,s2);if(st=success)printf(answer is %sn,s1);elseprintf(error!n);break;case 5:printf(please input the first string:n);getchar();gets(s1);printf(please input the second string:n);gets(s2);printf(please input i:);scanf(%d,&i);st=strins(s1,i,s2);if(st=success)printf(answer is: %sn,s1);else printf(error!n);break;case 0:break;default: printf(There isnt this operation!);int strlen(s) /*求字符串的长度子函数*/char s; int i;for(i=0;si!=0;i+);return (i);void strass(s1,s2)char s1,s2; int i=0;while(s1i!=0) s2i=s1i;i+;s2i=0;printf(s2 is %s,s2);boolean strcmp(s1,s2) /*字符串比较子函数*/char s1,s2; int i=0;while (s1i=s2i & s1i!=0 & s2i!=0)i+;if (s1i=0 & s2i=0)return (true);elsereturn (false);status strcat (s1,s2) /*字符串连接子函数*/char s1,s2; int i,j,k;i=strlen(s1);j=strlen(s2);if(i+j)=MAXN)return(fail);for(k=0;k=j;k+)s1i+k=s2k;return (success);status strins (s1,i,s2)char s1,s2;int i; int m,n,k;m=strlen(s1);n=strlen(s2);if (im|(m+n)MAXN )return (fail) ;for(k=m;k=i;k-)s1k+n=s1k;for(k=0;kn;k+)s1i+k=s2k;return (success);【测试数据与结果：】计算字符串的长度1. The length of string2. The assignment of string3. A string compare with another string:4. A string connect with another string:5. A string to be inserted into another stringPlease input a opertation:1please input a string:you are a boy!the length is: 14字符串的复制 1. The length of string2. The assignment of string3. A string compare with another string:4. A string connect with another string:5. A string to be inserted into another stringPlease input a opertation:2please input the first string:you are a boy!please input the second string:i am a girl!s2 is you are a boy!字符串的比较 1. The length of string2. The assignment of string3. A stri