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

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，如果ab，则s=a；反之，则s

4、=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(Linknod

5、e); /建立头节点 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=H-next;if(p1=NULL) retu

6、rn(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(ji)p1=p;i=j; /取和为最大的第一节点指针 return (p1);1.2.3 程序实现#include#includetypedef int datatype; /设当前数据元素为整型 typedef struct node /节点类型 datatype data; /节点的数据域 struct

7、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),scanf(%f,&b);/printf(%d,c); /判断输入的是否是整数a=(int)b;if(c!=1|a!=b|a32767) printf(非法输入!请重新输入!n);w

8、hile(c!=1|a!=b|a32767);while(a!=0) P=(Link)malloc(sizeof(Linknode);/申请新节点 P-data=a; /存入数据 r-next=P; /新节点链入表尾 r=P; do c=(fflush(stdin),scanf(%f,&b); /判断输入的是否是整数 a=(int)b; if(c!=1|a!=b|a32767) printf(非法输入!请重新输入!n); while(c!=1|a!=b|a32767); r-next=NULL; /将尾节点的指针域置空 return(H); /返回已创建的头节点 Link Adjmax(Lin

9、k H) /求链表中相邻两节点data值之和为最大的第一节点的指针的算法 Link p,p1,q;int i,j;p=p1=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(ji)p1=p;i=j; /取和为最大的第一节点指针 return (p1);void main() /主函数 Link A,B,p,q;i

10、nt a,b;doprintf(请输入一组整数(以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); while(b); 1.3 结果分析输入的数组为：2 6 4 7 3，输

11、出结果：第一节点为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)空间复杂度：不复杂有效性：算法正确，算法易读、易编码和易于调试不足：每个数据输入之间只能用回车区分。2 实验2：栈的应

12、用2.1 实验内容设操作数：0，1，2，8，9（可扩充）；运算符：+，-，*，/，（，），#（#号为结束）。输入中缀表达式，将其转换成后缀表达式，然后计算，输出结果。例如：输入中缀表达式5+(4-2)*3 #，将其转换成后缀表达式：542-3*+#，然后计算，本例结果为11。2.2 主要步骤2.2.1 问题分析与算法思路利用栈来写程序。首先要获得中缀表达式，再利用一个调用函数是中缀表达式变为后缀表达式。再用一个函数求后缀表达式的值。利用一个调用函数取判断中缀表达式的合法性。2.2.2 算法描述typedef struct node char data;struct node *next;sno

13、de,*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); return (0); void Push(slink*s,char x) /元素x进栈slin

14、k 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 Precede(char x,char y) /比较x是否大于y int a,b;switch(x)case #:case (:a=0;brea

15、k;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到后缀表达式E的转换 int i=0,j=0;char x; int a;slink s=NULL; /置空栈 Clearstack(s);Push(&s,#); /结束符入栈 dox=Bi+; /扫

16、描当前表达式分量x switch(x) case :break; case #:while(!Emptystack(s) Ej+= ; /栈非空时 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+= ; Ej+=Pop(&s); /Q1=x时，输出栈顶符兵退栈 /Ej+= ;Push(&s

17、,x); /Q1x时，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!=#) /扫描每一个字符是送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=P

18、op1(&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!= ) g1=Ei-0; g=g*10+g1; i+; Push1(&s,g); /操作数进栈 i+;if(!Emptystack1(s) return(Getstop1(s); /返回结果 Clearstack1(s);2.2.

19、3 程序实现#include#include#includetypedef 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) /取

20、栈顶元素if(s!=NULL) 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);return (x);

21、 /成功 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 Emptystack1(slink1 s) /判断

22、栈是否为空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;break;case +: case -:a=1;break; case *: case /:a=2;break; swit

23、ch(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到后缀表达式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(

24、s) Ej+= ; /栈非空时 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+= ; Ej+=Pop(&s); /Q1=x时，输出栈顶符兵退栈 Push(&s,x); /Q1front-next=NULL;q-rear=q-front;void Creatqueue(linkqueue

25、*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(lin

26、kqueue *q) /元素出队Qlink p;if(Emptyqueue(q) return;elsep=q-front;q-front=p-next;free(p);return(q-front-data);3.2.3 程序实现#include #include #includetypedef struct nodechar data;struct node *next;Qnode,*Qlink;typedef structQnode *front,*rear;linkqueue;void Clearqueue(linkqueue *q) /清空队列q-front-next=NULL;q-

27、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;

28、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);void main()char a,b;int c;linkqueue q;Creatqueue(&q);printf(请输入队列元素!n); doa=getchar();switch (a)case :break;case 0: if(Emptyqueue(&q) printf(队列为空!n); printf(请继续输入!n);c=1; else b=Dequeue(&q); printf(%c出队n,b); printf(请继续输入!n);break; case : if(Emptyqueue(&q) printf(队列为空!n);return; elseprintf(全部元素出队:n);