北科大_ 数据结构上机实验报告

1、北京科技大学 计算机与通信工程学院实 验 报 告实验名称： 数据结构上机实验 学生姓名： 专 业： 计算机科学与技术 班 级： 学 号： 指导教师： 实验成绩：_实验地点： 实验时间： 2015 年_ _6 _月一、实验目的与实验要求1 实验目的（1）加深对常用数据结构和算法设计基本思路、思考方法及其适用场合的理解，并能运用于解决实际问题；（2）能根据特定问题需求，分析建立计算模型（包括逻辑结构和物理结构）、设计算法和程序，并在设计中综合考虑多种因素，对结果的有效性进行分析；（3）训练分析问题、解决问题的能力以及自主学习与程序设计实践能力；（4）形成将非数值型问题抽象为计算模型到算法设计、程序

2、实现、结果有效性分析的能力。2 实验要求（1）由于在有限的实验课内学时难以较好完成所有实验内容，因此要求在实验课前自主完成部分实验或实验的部分内容；（2）对于每个实验都要针对问题进行分析，设计出有效的数据结构、算法和程序，对实现结果的正确性进行测试，给出测试用例和结果，分析算法的时间复杂度、空间复杂度、有效性和不足，在算法设计和实现过程中体现创新意识，并能综合考虑时空权衡、用户的友好性、程序的模块化和扩展性等；（3）完成的每个实验需要在实验课内经指导教师现场检查、查看程序代码，回答指导教师提出的问题，以确认实验实际完成的质量；（4）在实验报告中体现问题分析、算法思路、算法描述、程序实现和验证、

3、算法和结果的有效性分析。二、实验设备（环境）及要求Win7、C语言、Dev-C+三、实验内容、步骤与结果分析1 实验1：链表的应用1.1 实验内容输入数据（设为整型）建立单链表，并求相邻两节点data值之和为最大的第一节点。1.2 主要步骤1.2.1 问题分析与算法思路采用单链表结构。新建链表：每输入一个整数数据，建立一个新节点。循环操作直到输入结束符结束输入。利用一个调用函数求两节点data值之和为最大的第一节点：假设，设一个int类型的变量s=0，读取链表中第一个节点的数据以及它的第二个节点的数据，并计算它们之和a，再计算第二个节点数据和第三个节点数据之和b，如果a>b，则s=a；反

4、之，则s=b。利用if语句和while语句实现。每当输入一个数据，程序会判断输入的时候输入的数据是否是整数，如果不是整数，要求重新输入。1.2.2 算法描述typedef int datatype; /设当前数据元素为整型 typedef struct node /节点类型 datatype data; /节点的数据域 struct node *next; /节点的后继指针域 Linknode,*Link; Link Createlist() /创建单链表的算法 int a;Link H,P,r; /H,P,r分别为表头，新节点和表尾节点指针 H=(Link)malloc(sizeof(Lin

5、knode); /建立头节点 r=H;scanf(“%d”,&a); /输入一个数据while(a!=0) P=(Link)malloc(sizeof(Linknode);/申请新节点 P->data=a; /存入数据 r->next=P; /新节点链入表尾 r=P; scanf(“%d”,&a); /输入下一个数据r->next=NULL; /将尾节点的指针域置空 return(H); /返回已创建的头节点 Link Adjmax(Link H) /求链表中相邻两节点data值之和为最大的第一节点的指针的算法 Link p,p1,q;int i,j;p=p1

6、=H->next;if(p1=NULL) return(p1); /表空返回 q=p->next;if(q=NULL) return(p1); /表长=1时返回 i=p->data+q->data; /相邻两节点data值之和 while(q->next)p=q;q=q->next; /取下一对相邻节点的指针 j=p->data+q->data;if(j>i)p1=p;i=j; /取和为最大的第一节点指针 return (p1);1.2.3 程序实现#include<stdio.h>#include<stdlib.h>

7、;typedef int datatype; /设当前数据元素为整型 typedef struct node /节点类型 datatype data; /节点的数据域 struct node *next; /节点的后继指针域 Linknode,*Link; /linknode为节点说明符，link为节点指针说明符 Link Createlist() /创建单链表的算法 int a,c;float b;Link H,P,r; /H,P,r分别为表头，新节点和表尾节点指针 H=(Link)malloc(sizeof(Linknode); /建立头节点 r=H;doc=(fflush(stdin),

8、scanf("%f",&b);/printf("%d",c); /判断输入的是否是整数a=(int)b;if(c!=1|a!=b|a<-32768|a>32767) printf("非法输入!请重新输入!n");while(c!=1|a!=b|a<-32768|a>32767);while(a!=0) P=(Link)malloc(sizeof(Linknode);/申请新节点 P->data=a; /存入数据 r->next=P; /新节点链入表尾 r=P; do c=(fflush(st

9、din),scanf("%f",&b); /判断输入的是否是整数 a=(int)b; if(c!=1|a!=b|a<-32768|a>32767) printf("非法输入!请重新输入!n"); while(c!=1|a!=b|a<-32768|a>32767); r->next=NULL; /将尾节点的指针域置空 return(H); /返回已创建的头节点 Link Adjmax(Link H) /求链表中相邻两节点data值之和为最大的第一节点的指针的算法 Link p,p1,q;int i,j;p=p1=H-&

10、gt;next;if(p1=NULL) return(p1); /表空返回 q=p->next;if(q=NULL) return(p1); /表长=1时返回 i=p->data+q->data; /相邻两节点data值之和 while(q->next)p=q;q=q->next; /取下一对相邻节点的指针 j=p->data+q->data;if(j>i)p1=p;i=j; /取和为最大的第一节点指针 return (p1);void main() /主函数 Link A,B,p,q;int a,b;doprintf("请输入一组整数

11、(以0为结束符，数之间回车):n");p=A=Createlist(); /创建新链表 B=Adjmax(A); /求链表中相邻两节点data值之和为最大的第一节点的指针 a=(int)(B->data); /取第一节点的data值 printf("第一节点的data值为:%dn",a); while(p->next) /释放链表空间 q=p; p=p->next; free(q); free(p); printf("是否继续输入下一组整数:是:1,否:0n"); scanf("%d",&b); w

12、hile(b); 1.3 结果分析输入的数组为：2 6 4 7 3，输出结果：第一节点为4。结果是正确的。输入的数组为：45 21 456 4 214 54 230，输出结果：第一节点为21。结果是正确的。输入的数组为：45 7 23 564 70 1224 12 145 24，输出结果：第一节点为70。结果是正确的。1.3.1 测试如图所示，只要输入的数据不是整数（字符或小数），或者输入的整数不在32768,32767这个范围，程序会用"非法输入!请重新输入!"提示用户，直到用户输入正确的数据。1.3.2 算法和结果的有效性分析时间复杂度：O(n)空间复杂度：不复杂有效性

13、：算法正确，算法易读、易编码和易于调试不足：每个数据输入之间只能用回车区分。2 实验2：栈的应用2.1 实验内容设操作数：0，1，2，8，9（可扩充）；运算符：+，-，*，/，（，），#（#号为结束）。输入中缀表达式，将其转换成后缀表达式，然后计算，输出结果。例如：输入中缀表达式5+(4-2)*3 #，将其转换成后缀表达式：542-3*+#，然后计算，本例结果为11。2.2 主要步骤2.2.1 问题分析与算法思路利用栈来写程序。首先要获得中缀表达式，再利用一个调用函数是中缀表达式变为后缀表达式。再用一个函数求后缀表达式的值。利用一个调用函数取判断中缀表达式的合法性。2.2.2 算法描述type

14、def struct node char data;struct node *next;snode,*slink;typedef struct node1 int data;struct node1 *next;snode1,*slink1;void Clearstack(slink s) /置栈空 s=NULL;int Emptystack(slink s) /判断栈是否为空if(s=NULL) return(1); /栈空返回1else return(0); /栈非空返回0 char Getstop(slink s) /取栈顶元素if(s!=NULL) return (s->data

15、); return (0); void Push(slink*s,char x) /元素x进栈slink p;p=(slink)malloc(sizeof(snode); /生成进栈p节点 p->data=x; /存入新元素 p->next=*s; /p节点作为新的栈顶链入 *s=p;char Pop(slink*s) /出栈char x;slink p;if(Emptystack(*s) return (-1); /栈空，返回-1 elsex=(*s)->data;p=*s;*s=(*s)->next;free(p);return (x); /成功 int Prece

16、de(char x,char y) /比较x是否"大于"y int a,b;switch(x)case '#':case '(':a=0;break;case '+': case '-':a=1;break; case '*': case '/':a=2;break; switch(y)case '+':case '-':b=1;break;case '*':case '/':b=2;break;case '

17、(':b=3;break;if(a>=b) return (1);else return (0); void Mid_post(char E,char B) /中缀表达式B到后缀表达式E的转换 int i=0,j=0;char x; int a;slink s=NULL; /置空栈 Clearstack(s);Push(&s,'#'); /结束符入栈 dox=Bi+; /扫描当前表达式分量x switch(x) case ' ':break; case '#':while(!Emptystack(s) Ej+=' &

18、#39; /栈非空时 Ej+=Pop(&s);break; case ')':while(Getstop(s)!='(') Ej+=' ' Ej+=Pop(&s); /反复出栈直到遇到'(' Pop(&s); /退掉'(' break;case '+':case '-':case '*':case '/':case '(':while(Precede(Getstop(s),x) /栈顶运算符（Q1）与x比较 Ej

19、+=' ' Ej+=Pop(&s); /Q1>=x时，输出栈顶符兵退栈 /Ej+=' 'Push(&s,x); /Q1<x时，x进栈Ej+=' ' break; default:Ej+=x; /操作数直接输出 while(x!='#'); Ej='0'Clearstack(s);int Ecount(char E) /后缀表达式求值 int i=0,g=0,k=0,d=0,d1,g1;char x;int z,a,b;slink1 s=NULL; /置栈空 while(Ei!='

20、#') /扫描每一个字符是送x x=Ei;switch(x)case ' ':break;case '+':b=Pop1(&s);a=Pop1(&s);z=a+b;Push1(&s,z);break;case '-':b=Pop1(&s);a=Pop1(&s);z=a-b;Push1(&s,z);break;case '*':b=Pop1(&s);a=Pop1(&s);z=a*b;Push1(&s,z);break;case '/':b

21、=Pop1(&s);a=Pop1(&s);z=a/b;Push1(&s,z);break;/执行相应运算结果进栈 default: g=0;g1=0; /获取操作数 while(Ei!=' ') g1=Ei-'0' g=g*10+g1; i+; Push1(&s,g); /操作数进栈 i+;if(!Emptystack1(s) return(Getstop1(s); /返回结果 Clearstack1(s);2.2.3 程序实现#include<stdio.h>#include<stdlib.h>#incl

22、ude<string.h>typedef struct node char data;struct node *next;snode,*slink;typedef struct node1 int data;struct node1 *next;snode1,*slink1;void Clearstack(slink s) /置栈空 s=NULL;int Emptystack(slink s) /判断栈是否为空if(s=NULL) return(1); /栈空返回1else return(0); /栈非空返回0 char Getstop(slink s) /取栈顶元素if(s!=N

23、ULL) return (s->data); return (0); void Push(slink*s,char x) /元素x进栈slink p;p=(slink)malloc(sizeof(snode); /生成进栈p节点 p->data=x; /存入新元素 p->next=*s; /p节点作为新的栈顶链入 *s=p;char Pop(slink*s) /出栈char x;slink p;if(Emptystack(*s) return (-1); /栈空，返回-1 elsex=(*s)->data;p=*s;*s=(*s)->next;free(p);re

24、turn (x); /成功 void Push1(slink1*s,int x) /元素x进栈slink1 p;p=(slink1)malloc(sizeof(snode1); /生成进栈p节点 p->data=x; /存入新元素 p->next=*s; /p节点作为新的栈顶链入 *s=p;int Pop1(slink1*s) /出栈int x;slink1 p;if(Emptystack1(*s) return (-1); /栈空，返回-1 elsex=(*s)->data;p=*s;*s=(*s)->next;free(p);return (x); /成功 int

25、Emptystack1(slink1 s) /判断栈是否为空if(s=NULL) return(1); /栈空返回1else return(0); /栈非空返回0 void Clearstack1(slink1 s) /置栈空 s=NULL;int Getstop1(slink1 s) /取栈顶元素if(s!=NULL) return (s->data); return (0); int Precede(char x,char y) /比较x是否"大于"y int a,b;switch(x)case '#':case '(':a=0;b

26、reak;case '+': case '-':a=1;break; case '*': case '/':a=2;break; switch(y)case '+':case '-':b=1;break;case '*':case '/':b=2;break;case '(':b=3;break;if(a>=b) return (1);else return (0); void Mid_post(char E,char B) /中缀表达式B到后缀

27、表达式E的转换 int i=0,j=0;char x; int a;slink s=NULL; /置空栈 Clearstack(s);Push(&s,'#'); /结束符入栈 dox=Bi+; /扫描当前表达式分量x switch(x) case ' ':break; case '#':while(!Emptystack(s) Ej+=' ' /栈非空时 Ej+=Pop(&s);break; case ')':while(Getstop(s)!='(') Ej+=' '

28、; Ej+=Pop(&s); /反复出栈直到遇到'(' Pop(&s); /退掉'(' break;case '+':case '-':case '*':case '/':case '(':while(Precede(Getstop(s),x) /栈顶运算符（Q1）与x比较 Ej+=' ' Ej+=Pop(&s); /Q1>=x时，输出栈顶符兵退栈 Push(&s,x); /Q1<x时，x进栈Ej+=' '

29、break; default:Ej+=x; /操作数直接输出 while(x!='#'); Ej='0'Clearstack(s);int Ecount(char E) /后缀表达式求值 int i=0,g=0,k=0,d=0,d1,g1;char x;int z,a,b;slink1 s=NULL; /置栈空 while(Ei!='#') /扫描每一个字符是送x x=Ei;switch(x)case ' ':break;case '+':b=Pop1(&s);a=Pop1(&s);z=a+b;Pu

30、sh1(&s,z);break;case '-':b=Pop1(&s);a=Pop1(&s);z=a-b;Push1(&s,z);break;case '*':b=Pop1(&s);a=Pop1(&s);z=a*b;Push1(&s,z);break;case '/':b=Pop1(&s);a=Pop1(&s);z=a/b;Push1(&s,z);break;/执行相应运算结果进栈 default: g=0;g1=0; /获取操作数 while(Ei!=' &

31、#39;) g1=Ei-'0' g=g*10+g1; i+; Push1(&s,g); /操作数进栈 i+;if(!Emptystack1(s) return(Getstop1(s); /返回结果 Clearstack1(s);int pd(char B) /判断输入错误 int i=0,c,j,k; c=strlen(B); /获取B的长度 while(Bi!='#') switch(Bi) /检查有无非法字符 case ' ':break; case '0': case '1': case '2

32、': case '3': case '4': case '5': case '6': case '7': case '8': case '9': j=i+1; /一个操作数之间不能有空格 if(Bj=' ') while(Bj=' ') j+; switch(Bj) case '0': case '1': case '2': case '3': case '4':

33、case '5': case '6': case '7': case '8': case '9':printf("非法输入!请重新输入!n");return(0);break; break; case '+': case '-': case '*': case '/': j=i-1; while(Bj=' ') j-;switch(Bj) /'+'，'-'，'*'，&#

34、39;/'左边不能有 '+'，'-'，'*'，'/'，'(','#' case '+':case '-': case '*':case '/':case '(':case '#':printf("非法输入!请重新输入!n");return(0);break; k=i+1; while(Bk=' ') k+; switch(Bk) /'+',

35、9;-'，'*'，'/'左边不能有 '+'，'-'，'*'，'/'，')','#'case '+':case '-':case '*':case '/':case ')':case '#':printf("非法输入!请重新输入!n");return(0);break; break;case '(': /'('左边不

36、能有 '0''9','#',')' j=i-1; while(Bj=' ') j-;switch(Bj)case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9':case '#':case ')&

37、#39;:printf("非法输入!请重新输入!n");return(0);break; k=i+1; while(Bk=' ') k+; switch(Bk) /'('右边不能有 '+','-','*','/','#'case '+':case '-':case '*':case '/':case '#':printf("非法输入!请重新输入!n");return

38、(0);break; break;case ')': /')'左边不能有'(' j=i-1; while(Bj=' ') j-; switch(Bj) case '(':printf("非法输入!请重新输入!n");return(0);break; k=i+1; while(Bk=' ') k+; /')'右边不能有'0''9' switch(Bk)case '0': case '1': case &

39、#39;2': case '3': case '4': case '5': case '6': case '7': case '8': case '9':printf("非法输入!请重新输入!n");return(0);break; break; case '0':break; default:printf("8非法输入!请重新输入!n");return(0); i+; if(B0='#') printf

40、("表达式为空!请重新输入!n");return(0); else if (Bc-1!='#') printf("9非法输入!请重新输入!n");return(0); void main() int a,b,c,d;char B100,E100;dodo printf("请输入中缀表达式:n");B100=fflush(stdin); gets(B); /输入B while(B0='0') B100=fflush(stdin); gets(B); b=pd(B); /判断B是否合法 while(b=0)

41、; Mid_post(E,B); printf("后缀表达式为:n"); printf("%sn",E); a=Ecount(E); printf("结果=%dn",a); printf("是否继续?是:1否:0n"); scanf("%d",&c); while(c=1); 2.3 结果分析输入的中缀表达式为：5+(4-2)*3，输出的后缀表达式为：5 4 2 -3 * +，后缀表达式求值结果为：11。结果是正确的。输入的中缀表达式为：123+45*2-56，输出的后缀表达式为：123

42、 45 2 * + 56 -，后缀表达式求值结果为：157。结果是正确的。输入的中缀表达式为：7856-56*5+(78-55)，输出的后缀表达式为：7856 56 5 * - 78 55 - +，后缀表达式求值结果为：7599。结果是正确的。2.3.1 测试输入各种不合法表达式，例如45 56 - 56#、 56 + 55#等，这时会有提示语句：非法输入!请重新输入! 又如，如果直接输入#，那么中缀表达式为空，这时会有提示语句：表达式为空!请重新输入!2.3.2 算法和结果的有效性分析时间复杂度：O(n) 空间复杂度：不复杂有效性：算法正确、算法易读、易编码和易于调试不足：代码不够简洁3 实

43、验3：队列的应用3.1 实验内容从键盘输入字符x，若x='0'，则进行出队操作；若x=''，则输出当前队列的元素，结束；否则，将x入队。3.2 主要步骤3.2.1 问题分析与算法思路采用队列结果当队列为空时，输入0或要有相应的结果。3.2.2 算法描述typedef struct nodechar data;struct node *next;Qnode,*Qlink;typedef structQnode *front,*rear;linkqueue;void Clearqueue(linkqueue *q) /清空队列q->front->next

44、=NULL;q->rear=q->front;void Creatqueue(linkqueue *q) /创建队列 q->front=(Qlink)malloc(sizeof(Qnode);q->front->next=NULL;q->rear=q->front;int Emptyqueue(linkqueue *q) /判断队列是否为空if(q->front=q->rear) return (1);else return (0);void Enqueue(linkqueue *q,char e) /元素进队Qlink p;p=(Qlin

45、k)malloc(sizeof(Qnode);p->data=e;p->next=NULL;q->rear->next=p;q->rear=p;char Dequeue(linkqueue *q) /元素出队Qlink p;if(Emptyqueue(q) return;elsep=q->front;q->front=p->next;free(p);return(q->front->data);3.2.3 程序实现#include <stdio.h>#include <string.h>#include<

46、stdlib.h>typedef struct nodechar data;struct node *next;Qnode,*Qlink;typedef structQnode *front,*rear;linkqueue;void Clearqueue(linkqueue *q) /清空队列q->front->next=NULL;q->rear=q->front;void Creatqueue(linkqueue *q) /创建队列 q->front=(Qlink)malloc(sizeof(Qnode);q->front->next=NULL;q->rear=q->front;int Emptyqueue(linkqueue *q) /判断队列是否为空if(q->front=q->rear) return (1);else return (0);void Enqueue(linkqueue *q,char e) /元素进队Qlink p;p=(Qlink)malloc(sizeof(Qnode);p->data=e;p->next=NULL;q->rear->next=p;q->rear=p;char Dequeue(linkqueue *q