《算法语言与数据结构》实验指导指导书.doc

理学系实验指导书 算法语言与数据结构专业名称：信息与计算科学专业 课程名称：算法语言与数据结构授课对象：本科生 总学时数：24学时实验室名称：信息与计算科学实验室内容摘要：数据结构是计算机应用专业的一门专业基础课，通过本实验的训练，应培养学生的数据抽象能力和程序设计能力。数据结构的先修课主要是C语言程序设计，本实验以C语言作为算法描述和上机实践工具。根据教学内容和教学目标，实验课共开设12次实验。学生应按照实验指导书的要求，完成指定的实验任务。实验课分班进行，每个实验班50人左右，配备一名实验指导教师（另编写了一本实验指导与题解的教材，8月份出版）。考核方式：以平时完成实验情况和最后作业进行评定。实验类别：专业必修课实验一 结构体与共用体一、实验目的（1）掌握结构体类型数组的概念和使用；（2）掌握枚举类型的概念与使用；（3）设计并掌握算法，学会分析算法并培养用算法解决实际问题的能力。二、实验要求（1）设计相应原始表格（比赛的成绩），选择恰当的数据结构；（2）统计各院校的男、女总分和团体总分，并输出。三、实验内容假设有A、B、C、D、E五个高校进行田径比赛，各院校的单项成绩均已存入计算机，并构成一张表，表的每一行的形式为：项目名称 性别 校名 成绩 得分编程统计各院校的男、女总分和团体总分，并输出。四、主要仪器设备PC机及TC或VC五、实验步骤#define NULL 0typedef struct char *sport; enummale,female gender; char schoolname; char *result; int score; resulttype;typedef struct int malescore; int femalescore; int totalscore; scoretype;void summary(resulttype result ) scoretype score5=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0; int i=0; while(resulti.sport!=NULL) switch(resulti.schoolname) case A:score0.totalscore+=resulti.score;if(resulti.gender=0) score0.malescore+=resulti.score; else score0.femalescore+=resulti.score; break; case B: score1.totalscore+=resulti.score; if(resulti.gender=0) score1.malescore+=resulti.score; else score1.femalescore+=resulti.score; break; case C: score2.totalscore+=resulti.score; if(resulti.gender=0) score2.malescore+=resulti.score; else score2.femalescore+=resulti.score; break; case D: score3.totalscore+=resulti.score; if(resulti.gender=0) score3.malescore+=resulti.score; else score3.femalescore+=resulti.score; break; case E: score4.totalscore+=resulti.score; if(resulti.gender=0) score4.malescore+=resulti.score; else score4.femalescore+=resulti.score; break; i+; for(i=0;i5;i+) printf(School %d:n,i); printf(Total score of male:%dn,scorei.malescore); printf(Total score of female:%dn,scorei.femalescore); printf(Total score of all:%dnn,scorei.totalscore); main()resulttype result20=bm,male,A,verygood,9,ty,female,A,good,8,bm,male,B,good,8,ty,female,B,verygood,10,bm,male,C,good,7,ty,female,C,good,8,bm,male,D,verygood,10,ty,female,d,good,9,bm,male,E,good,9,ty,female,E,verygood,9;summary(result);六、注意事项（1）、将本实验上机调试、运行，注意调试过程中出现的问题；（2）、结合运行结果，对程序进行分析。实验二 文件一、实验目的（1）学会使用文件打开、关闭、读、写等文件操作函数；（2）学会用缓冲文件系统对文件进行简单的操作；（3）设计并掌握算法，学会分析算法并培养用算法解决实际问题的能力。二、实验要求 （1）将这10个学生信息存入到磁盘文件student中； （2）将磁盘文件中的所有学生记录读入内存中一块静态顺序空间中，求出所有学生的平均成绩； （3）将学生成绩按平均分进行排序处理，将已排序的学生数据存入一个新文件stu_sort中。三、实验内容（1）有10个学生，每个学生有3门课的成绩，从键盘输入数据（包括学生号、姓名、3门课成绩）计算平均成绩，将原有数据和计算出的平均分数存放在磁盘文件student中。（2）将上题student文件中的学生数据，按平均分进行排序处理，将已排序的学生数据存入一个新文件stu_sort中（并检查该文件中的内容是否正确）。四、主要仪器设备PC机及TC或VC五、实验步骤l 学生记录结构如下：Struct student_typeChar id5;Char name11;int age;int math;int eng;int data_struct;int os;六、注意事项（1）、将本实验上机调试、运行，注意调试过程中出现的问题；（2）、结合运行结果，对程序进行分析。实验三 顺序表基本操作一、实验目的（1）掌握线性表的顺序存储结构及其实现方法；（2）掌握顺序表上的插入、删除和查找操作。二、实验要求（1）设计相应的两级测试数据，一组为整形数据，一组为字符数据，个数不少于10个；（2）在第5个位置上插入一个数或字符；（3）将第7个元素删除；（4）查找值为？的元素，若存在将其输出，否则打印没有该元素。三、实验内容用C语言数组实现在顺序表上进行插入、删除和查找操作。四、主要仪器设备PC机及TC或VC五、实验步骤（1）算法提示：参照书本上的算法。（2）参考源代码#include #define init_size 20typedef int elemtype ;typedef struct elemtype *elem;int length;int listsize;sqlist;int Insert_sqList(sqlist *va,int x) int i; if(va-length+1va-listsize) return -1; va-length+; for(i=va-length;va-elemix&i=0;i-) va-elemi+1=va-elemi; va-elemi+1=x; return 1;main()sqlist va;int i,e;va.elem=(elemtype *)malloc(init_size*sizeof(elemtype);va.length=10;va.listsize=init_size;for(i=1;i=va.length;i+)scanf(%d,&va.elemi);scanf(%d,&e);if(Insert_sqList(&va,e);for(i=1;ilink=NULL;p=head_a-link;q=head_b-link;while(p!=NULL)&(q!=NULL)if(p-datadata)head_a-link=p-link;p-link=head-link;head-link=p;p=head_a-link;elsehead_b-link=q-link;q-link=head-link;head-link=q;q=head_b-link;while(p!=NULL) head_a-link=p-link; p-link=head-link; head-link=p; p=head_a-link; while(q!=NULL) head_b-link=q-link; q-link=head-link; head-link=q; q=head_b-link; free(head_a);free(head_b);return(head);六、注意事项（1）、将本实验上机调试、运行，注意调试过程中出现的问题；（2）、结合运行结果，对程序进行分析。实验五 一元稀疏多项式运算一、实验目的设计并掌握算法，学会分析算法并培养用算法解决实际问题的能力。二、实验要求（1）用带头结点的单链表做存储结构；（2）构造两个多项式，实现相加和相乘。三、实验内容用C语言编程实现一元稀疏多项式加、减、乘运算。四、主要仪器设备PC机及TC或VC五、实验步骤#define NULL 0#include #include typedef struct termfloat coef;int expn;struct term *next;term,*polynomial;term *creat(int n)term *head, *p,*q;int i;float s;head=(polynomial)malloc(sizeof(term);head-next=NULL;head-coef=0.0;head-expn=-1;q=head;for(i=n;i0;i-)p=(polynomial)malloc(sizeof(term);scanf(%f,%d,&s,&p-expn);p-coef=s;p-next=q-next;q-next=p;q=p;return(head);void print(polynomial head)term *p;p=head-next;printf(%f*x%d,p-coef,p-expn);p=p-next;while(p)if(p-coef0)printf(+%f*x%d,p-coef,p-expn);else if(p-coefcoef,p-expn);p=p-next;polynomial addpolyn(polynomial f,polynomial g)polynomial p,q,pre,u;float sum;p=f-next;q=g-next;pre=f;while(p&q)if(p-expnexpn)pre=p;p=p-next;else if(p-expn=q-expn) sum=p-coef+q-coef; if(sum!=0) p-coef=sum;pre=p; elsepre-next=p-next;free(p); p=pre-next;u=q;q=q-next;free(u); else u=q-next;q-next=p;pre-next=q;pre=q;q=u; if(q) pre-next=q; free(g); return(f);main()polynomial f,g,h;int n,m;printf(n=);scanf(%d,&n);f=creat(n);printf(m=);scanf(%d,&m);g=creat(m);h=addpolyn(f,g);print(h); #define NULL 0#include #include typedef struct termfloat coef;int expn;struct term *next;term,*polynomial;term *creat(int n)term *head, *p,*q;int i;float s;head=(polynomial)malloc(sizeof(term);head-next=NULL;head-coef=0.0;head-expn=-1;q=head;for(i=n;i0;i-)p=(polynomial)malloc(sizeof(term);scanf(%f,%d,&s,&p-expn);p-coef=s;p-next=q-next;q-next=p;q=p;return(head);void print(polynomial head)term *p;p=head-next;printf(%f*x%d,p-coef,p-expn);p=p-next;while(p)if(p-coef0)printf(+%f*x%d,p-coef,p-expn);else if(p-coefcoef,p-expn);p=p-next;polynomial reverse(polynomial l)polynomial p,q;p=l-next;l-next=NULL;while(p)q=p-next;p-next=l-next;l-next=p;p=q;return(l);polynomial *multiply(polynomial f,polynomial g)polynomial h,l,fp,gp,hp,q;int max,k,r;float c;max=f-next-expn+g-next-expn;h=(term *)malloc(sizeof(term);h-coef=0.0;h-expn=-1;h-next=NULL;hp=h;l=reverse(g);for(r=max;r=0;r-)c=0.0;fp=f-next;gp=l-next;while(fp&gp)k=fp-expn+gp-expn; if(kr) fp=fp-next; else if(knext; else c+=fp-coef*gp-coef; fp=fp-next;gp=gp-next;if(c!=0.0)q=(term*)malloc(sizeof(term);q-expn=r;q-coef=c;q-next=hp-next;hp-next=q;hp=q;return(h);main()polynomial f,g,h;int n,m;printf(n=);scanf(%d,&n);f=creat(n);printf(m=);scanf(%d,&m);g=creat(m);h=multiply(f,g);print(h);六、注意事项（1）、将本实验上机调试、运行，注意调试过程中出现的问题；（2）、结合运行结果，对程序进行分析。实验六 栈的应用一、实验目的1、使学生深入了解堆栈的特性，以便在遇到实际问题时灵活运用堆栈知识。2、巩固堆栈数据结构的构造方法。二、实验要求1、掌握堆栈的逻辑结构和存储结构。2、熟练掌握堆栈的出栈、入栈等操作。三、实验内容用C语言编程实现数制转换和算术表达式的求值。四、主要仪器设备PC机及TC或VC五、实验步骤1、算法分析将十进制数N和其它d进制数的转换是计算机实现计算的基本问题，其解决方案很多，其中最简单方法基于下列原理：即除d取余法。例如:(1348)10=(2504)8NN div 8N mod 81348 168 416821021 2 520 2从中我们可以看出，最先产生的余数4是转换结果的最低位，这正好符合栈的特性即后进先出的特性。所以可以用顺序栈来模拟这个过程。2、源程序如下struct nodeint data; struct node *link;typedef struct node NODE;NODE *top=NULL;void conversion(int x)while(x0)push(top,x%8); x=x/8;while(!stackempty(top) /* stackempty( )为判断堆栈是否为空函数*/x=pop(s);printf(“%d”,x);#define Maxsize 100#include void trans(char str,char exp)char stackMaxsize;char ch;int i=0,j,t,top=0;i=1,t=1;ch=stri;while(ch!=#)if(ch=0& ch=9) expt=ch;t+; else if(ch=() top+;stacktop=ch; else if(ch=) while(stacktop!=() expt=stacktop;top-;t+; top-; else if(ch=+|ch=-) while(top!=0 & stacktop!=() expt=stacktop;top-;t+; top+;stacktop=ch; else if(ch=*|ch=/) while(stacktop=/|stacktop=*) expt=stacktop; top-;t+; top+;stacktop=ch; i+; ch=stri; while(top!=0) expt=stacktop;t+;top-; expt=#; for(j=1;j=0&c=9)top+;stacktop=d;elseswitch(c)case +:stacktop-1=stacktop-1+stacktop; break;case -:stacktop-1=stacktop-1-stacktop; break;case *:stacktop-1=stacktop-1*stacktop; break;case /:if (stacktop!=0) stacktop-1=stacktop-1/stacktop;else printf(chu ling chuo wu !n); break;top-; c=expt; t+; printf(ji suan jie guo shi:%g,stacktop); main() char strMaxsize; char expMaxsize; int i=0,j,t=0; do i+; scanf(%c,&stri); while (stri!=#& iMaxsize); trans(str,exp); compvalue(exp);六、注意事项（1）、将本实验上机调试、运行，注意调试过程中出现的问题；（2）、结合运行结果，对程序进行分析。实验七 队列的应用一、实验目的（1）、使学生深入了解队列特性，以便遇到实际问题时灵活运用队列知识。（2）、巩固队列结构的构造方法。（3）设计并掌握算法，理解队列的广泛应用，从而培养用算法解决实际问题的能力。二、实验要求（1）、掌握队列的逻辑结构和存储结构。（2）、熟练掌握队列的出队、入队等操作。三、实验内容用C语言编程实现迷宫问题求解。四、主要仪器设备PC机及TC或VC五、实验步骤（1）、算法分析迷宫的定义如下：#define m 6 /* 迷宫的实际行 */#define n 8 /* 迷宫的实际列 */int maze m+2n+2 ;mazeij=0或1; 其中：0表示通路，1表示不通，当从某点向下试探时，中间点有8个方向可以试探，（见图3.4）而四个角点有3个方向，其它边缘点有5个方向，为使问题简单化我们用mazem+2n+2来表示迷宫，而迷宫的四周的值全部为1。Move数组定义如下：typedef struct int x，y item ; item move8 ;当到达了某点而无路可走时需返回前一点，再从前一点开始向下一个方向继续试探。因此，压入栈中的不仅是顺序到达的各点的坐标，而且还要有从前一点到达本点的方向。typedef structint x , y , d ;/* 横纵坐标及方向*/datatype ;迷宫求解算法思想如下：1 栈初始化;2 将入口点坐标及到达该点的方向（设为）入栈3 while (栈不空) 栈顶元素（x , y , d）出栈 ;求出下一个要试探的方向d+ ; while （还有剩余试探方向时） if （d方向可走）则 （x , y , d）入栈 ; 求新点坐标 (i, j ) ;将新点（i , j）切换为当前点（x , y） ; if ( (x ,)= =(,n) ) 结束 ; else 重置 d=0 ; else d+ ; 2、源程序如下#include #define M 6#define N 8typedef structint x,y,pre;sqtype;sqtype sq400;struct movedint x,y;move8;int mazeM+2N+2;void printpath(sqtype sq,int rear)int i; i=rear; do printf(%d,%d)-,sqi.x,sqi.y); i=sqi.pre; while(i!=0); int shortpath()int i,j,v,front,rear,x,y;sq1.x=1;sq1.y=1;sq1.pre=0;front=1;rear=1;maze11=-1;while(front=rear)x=sqfront.x;y=sqfront.y;for(v=0;v8;v+)i=x+movev.x; j=y+movev.y; if(mazeij=0) rear+;sqrear.x=i;sqrear.y=j;sqrear.pre=front; mazeij=-1; if(i=M)&(j=N) printpath(sq,rear); return(1); front+; return(0); main()int i,j;for(i=1;i=M;i+) for(j=1;j=N;j+) scanf(%1d,&mazeij); for(i=0;i=M+1;i+) mazei0=1;mazeiN+1=1; for(j=0;j=N+1;j+) maze0j=1;mazeM+1j=1; move0.x=0;move0.y=1; move1.x=1;move1.y=1; move2.x=1;move2.y=0; move3.x=1;move3.y=-1; move4.x=0;move4.y=-1; move5.x=-1;move5.y=-1; move6.x=-1;move6.y=0; move7.x=-1;move7.y=1; shortpath(); 六、注意事项（1）、将本实验上机调试、运行，注意调试过程中出现的问题；（2）、结合运行结果，对程序进行分析。实验八 串的基本运算一、实验目的（1）掌握串在顺序存储结构下的基本运算；（2）掌握串模式匹配的BF算法和KMP算法；（3）设计并掌握算法，理解串的具体应用，从而培养用算法解决实际问题的能力。二、实验要求（1）、掌握串的逻辑结构及顺序存储结构；（2）、熟练掌握串的一些基本运算。三、实验内容（1）求两个串的最长公共子串；（2）串模式匹配的BF算法和KMP算法实现。（3）、实现两个串的最长公共子串。四、主要仪器设备PC机及TC或VC五、实验步骤方法一：1、算法分析该算法的基本思想是在主串s中取从第i个字符起并且长度和串t相等的子串和t比较，若相等，则求得函数值为i，否则，i增1直至串中不存在从i开始和t相等的子串，匹配失败，返回0。2、算法如下#define NAX 100int index(char s ,char t ,int start)int i,eq,m,n;char subchMAX;m=strlen(s);n=strlen(t);if(startm)return(0);i=start;while(eq=sub(s,i,n,subch) /*sub为取子串函数*/if(strcmp(t,subch)break;else i+ +;if(eq)return(i+1);else return(0);方法二：1、算法分析本算法不依赖串的其他操作的匹配算法，在该算法中设置两个指针i和j分别指向主串s和模式串t中当前正待比较的字符位置。算法的基本思想是：从主串s的第一个字符(i=0)起和模式串的第一个字符(j=0)比较，若相等，则继续逐个比较后续字符(i+,j+)，否则从主串的第二个字符起再重新和模式串比较(i返回到原位置加1，j返回0)。依此类推，直至模式串t的第一个字符依次和主串s 的一个连续的字符序列相等，则称匹配成功，否则称匹配失败。该算法与方法一所讨论的相同，只是前者是以每一个位置为始点，取出子串与串t比较，而后者以每一个位置为出发点，与t比较，并且若匹配成功比较到t串结束，否则只需要比较到某一位置，即串s与串t的字符不相同。2、算法如下int index (char s,char t,int start)int i,j,m,n;m=strlen(s);n=strlen(t);if(startm)return(0);i=start;j=0;while(im&j=n)return(i-n+1);else return(0);int next9;int Index(char *S,char *T,int pos)int i=pos,j=1;while(i=S0&jT0) return i-T0;else return 0;int Index_KMP(char *S,char *T,int pos)int i=pos,j=1;while(i=S0&jT0) return i-T0;else return 0;void get_next(char *T,int next)int i=1,j=0;next1=0;while(iT0)if(j=0|Ti=Tj)+i;+j;nexti=j;else j=nextj;main()int i;char S=19,I, a,m,s,t,a,b,a,a,b,c,a,c,u,d,e,n,t,!;char T=8,a,b,a,a,b,c,a,c;/*for(i=0;i=11;i+)printf(%c ,Si);*/get_next(T,next);/*for(i=1;i=8;i+)printf(%d,nexti);*/i=Index_KMP(S,T,3);printf(%d,i);四、实验内容模式匹配若串t是串s的子串，则函数值为s中第一个这样的子串在主串中的位置，否则函数值为零。串t非空。五、实验报告要求1、认真阅读和掌握本实验内容所给的程序。2、将本实验上机运行。3、结合运行结果，对程序进行分析。4、试编写从s串中删除一个子串t的算法，子串由起始位置start和长度len决定。实验六 数组的应用一、实验目的1、使学生更进一步掌握数组的逻辑结构和存储结构。2、熟练特殊矩阵的存储结构。二、实验前的准备工作1、掌握数组的逻辑结构及存储结构。2、掌握稀疏矩阵的存储结构及一些运算的实现。三、实验指导1、算法分析设多项式的系数按幂次由高到低的顺序存于一数组中，多项式的幂次存于另一变量中。辗转相除法求两个多项式的最大公因式的算法是：用其中的一个多项式去除另一个多项式，然后将所得余式变成除式，原除式变成被除式。如此反复相除，直至余式为零时，最后的除式即为最大公因式。2、算法如下int remainder(double *pa,int an,double *pb,int bn,double *q)double x,y,*temp;int k,j;if(an0)bn-;pb+;if(*pb=0.0&bn=0)break;k=0;x=*pb;while(k=bn)pbk+/=x;for(k=0;k=an-bn;k+)x=pak;for(j=0;jbn;j+)y=pak+j+1-x*pbj+1;pak+j+1=y0.00005&-yrch=NULL）若*p结点为单分支结点，只需用它惟一子树的根去继承它的位置。即：将双亲结点原指向它原指针，设置为指向它的左孩子或右孩子(若只有左子树，则f-rch=p-lch;若只有右子树，则f-rch =p-rch)。 若*p结点为双亲分支结点，为保证删除该结点后，该树的中序序列仍然是按关键值递增有序。有如下解决方法：用左子树中序遍历的最后一个结点（左子树的最右结点）替换*p。首先，沿*p的左子树的右链，查找右指针域为空的结点*s；然后，用*s的数据替换*p的数据；最后，删除*s结点。因为，*s是其双亲结点的右孩子，并且s-rch为NULL。所以，若s-lch也为空，则置*s双亲的右指针为NULL，删除*s;若s-lch不为空，则置*s双亲的右指针为s-lch，删除*s。2、算法如下struct nodeint data;struct node *lch,*rch;typedef struct node NODE;NODE *del (NODE *root,int x)NODE *p,*f,*s_f,*s;/*p为要删除结点，f为p的双亲，s为p的左子树的最右边结点s_f为s的双亲*/if(root=NULL)return;f=NULL;p=root;while(p!=NULL & p-data!=x)if(p-datax)if(p-lch!=NULL)f=p;p=p-lch; else break;else if(p-rch!=NULL)f=p;p=p-rch;else break;if(p=NULL|p-data!=x)return(root);if(p=root)return; /*删除根结点*/if(p-lch=NULL & p-rch=NULL) /*删除叶子结点*/ if(f=NULL)free(p);return(NULL); if(f-lch=p)f-lch=NULL; else f-rch=NULL;free(p);return(root);if(p-lch=NULL) /*删除单分支结点,没有左子树*/if(f=NULL)root=p-rch;free(p);return(root);if(f-lch=p)f-lch=p-rch;else f-rch=p-rch;free(p);return(root);if(p-rch=NULL) /*删除单分支结点,没有右子树*/if(f=NULL)root=p-lch;free(p);return(root);if(f-lch=p)f-lch=p-lch;else f-rch=p-lch;free(p);return(root);s_f=p;s=p-lch; /*删除双分支结点*/while(s-rch!=NULL)s_f=s;s=s-rch;p-data=s-data;if(s-lch