算法与数据结构实验册

1、金陵科技学院实验报告学 生 实 验 报 告 册（理工类）课程名称：算法与数据结构 专业班级： 16计算机科学与技术（专转本） 学生学号： 1613203022 学生姓名： 张义丹 所属院部：计算机工程学院 指导教师： 沈奇 20162017学年 第 2 学期 金陵科技学院教务处制实验报告书写要求实验报告原则上要求学生手写，要求书写工整。若因课程特点需打印的，要遵照以下字体、字号、间距等的具体要求。纸张一律采用A4的纸张。实验报告书写说明实验报告中一至四项内容为必填项，包括实验目的和要求；实验仪器和设备；实验内容与过程；实验结果与分析。各院部可根据学科特点和实验具体要求增加项目。填写注意事项（1

2、）细致观察，及时、准确、如实记录。（2）准确说明，层次清晰。（3）尽量采用专用术语来说明事物。（4）外文、符号、公式要准确，应使用统一规定的名词和符号。（5）应独立完成实验报告的书写，严禁抄袭、复印，一经发现，以零分论处。实验报告批改说明实验报告的批改要及时、认真、仔细，一律用红色笔批改。实验报告的批改成绩采用百分制，具体评分标准由各院部自行制定。实验报告装订要求实验批改完毕后，任课老师将每门课程的每个实验项目的实验报告以自然班为单位、按学号升序排列，装订成册，并附上一份该门课程的实验大纲。实验项目名称： 顺序表 实验学时： 2 同组学生姓名： 实验地点： A107 实验日期： 6.2 实验成

3、绩： 批改教师： 沈奇 批改时间： 实验1 顺序表一、实验目的和要求掌握顺序表的定位、插入、删除等操作。二、实验仪器和设备Turbo C 2.0/ Visual C+三、实验内容与过程（含程序清单及流程图）1、必做题（1） 编写程序建立一个顺序表，并逐个输出顺序表中所有数据元素的值。编写主函数测试结果。（2） 编写顺序表定位操作子函数，在顺序表中查找是否存在数据元素x。如果存在，返回顺序表中和x值相等的第1个数据元素的序号（序号从0开始编号）；如果不存在，返回1。编写主函数测试结果。（3） 在递增有序的顺序表中插入一个新结点x，保持顺序表的有序性。解题思路：首先查找插入的位置，再移位，最后进行

4、插入操作；从第一个元素开始找到第一个大于该新结点值x的元素位置i即为插入位置；然后将从表尾开始依次将元素后移一个位置直至元素i；最后将新结点x插入到i位置。（4） 删除顺序表中所有等于X的数据元素。2、选做题（5） 已知两个顺序表A和B按元素值递增有序排列，要求写一算法实现将A和B归并成一个按元素值递减有序排列的顺序表（允许表中含有值相同的元素）。程序清单：#include<stdio.h>#define MAXSIZE 100typedef struct int data MAXSIZE;int last;sequenlist;sequenlist L;/*（1）编写程序建立一个

5、顺序表，并逐个输出顺序表中所有数据元素的值。编写主函数测试结果。*/sequenlist Scanflist(int n) /输入顺序表函数 int i;printf("请输入%d个数(按递增有序)：",n);for(i=0;i<n;i+) scanf("%d",&L.datai); L.last=n-1;return L;void Printlist(int n) /输出顺序表函数int i; printf("输出顺序表中所有数据元素的值:n");for(i=0;i<n;i+)printf("%3d&q

6、uot;,L.datai);printf("n");/*(2)在顺序表中查找是否存在数据元素x。如果存在，返回顺序表中和x值相等的第1个数据元素的序号（序号从0开始编号）；如果不存在，返回1。*/int Locate(int x)int i;for(i=0;i<=L.last;i+)if(x=L.datai)return i;return -1;/*（3）在递增有序的顺序表中插入一个新结点x，保持顺序表的有序性。解题思路：首先查找插入的位置，再移位，最后进行插入操作；从第一个元素开始找到第一个大于该新结点值x的元素位置i即为插入位置；然后将从表尾开始依次将元素后移一个

7、位置直至元素i；最后将新结点x插入到i位置。*/Insert(int x)int i,j,loc;for(i=0;i<=L.last;i+)if(x<=L.datai)loc=i;break;if(i>L.last)loc=i;L.dataloc=x;elsefor(j=L.last;j>=loc;j-)L.dataj+1=L.dataj;L.dataloc=x;L.last+;printf("输出插入%d后的顺序表:n",x);for(i=0;i<L.last;i+)printf("%3d",L.datai);printf

8、("n");/(4)删除顺序表中所有等于X的数据元素int Delete(int x)int i,j,loc=-1;for(i=0;i<=L.last;i+)if(x=L.datai)loc=i;for(j=loc+1;j<=L.last;j+)L.dataj-1=L.dataj;L.last-;i-;if(loc=-1)printf("不存在与x相等的值");return -1;return 1;void main()/主函数int i,j,x,select,result;int n=6;Scanflist(n);Printlist(n);

9、for(j=0;j<3;j+) printf("select=2时,执行查找操作:n"); printf("select=3时,执行插入操作:n"); printf("select=4时,执行删除操作:n"); printf("n请输入select的值:"); scanf("%d",&select); switch(select) case 2: printf("请输入你要查找x的值："); scanf("%d",&x); resul

10、t = Locate(x); if(result = -1) printf("不存在与%d相等的数n",x); else printf("与%d相等的数在第%d个n",x,result+1); break; case 3: printf("请输入需要插入的x的值：");scanf("%d",&x);Insert (x); break; case 4: printf("请输入要删除的x的值："); scanf("%d",&x); result=Delete (x

11、); if(result=1) printf("输出删除所有%d后的顺序表:n",x);for(i=0;i<L.last;i+)printf("%3d",L.datai);printf("n"); else printf("所要删除的元素不存在n"); break; 四、实验结果与分析（程序运行结果及其分析）五、实验体会（遇到问题及解决办法，编程后的心得体会）本次实验学习了对顺序表的输出、查询、插入、删除等操作，输出顺序表的下标是从零开始，所以顺序表的长度要减1。在做插入时，我发现我插入的数值把后面的数值盖住

12、了，后来查了一下书发现顺序表的长度没有加1。对于删除操作，找到等于x的值通过后面赋值给它，然后需要把顺序表长度减1。实验项目名称： 单链表 实验学时： 2 同组学生姓名： 实验地点： A107 实验日期： 6.5 实验成绩： 批改教师： 沈奇 批改时间： 实验2 单链表一、实验目的和要求1、实验目的掌握单链表的定位、插入、删除等操作。2、实验要求（1）注意链表的空间是动态分配的，某结点不用之后要及时进行物理删除，以便释放其内存空间。（2）链表不能实现直接定位，一定注意指针的保存，防止丢失。二、实验仪器和设备Turbo C 2.0/ Visual C+三、实验内容与过程（含程序清单及流程图）1、

13、必做题（1） 编写程序建立一个单链表，并逐个输出单链表中所有数据元素。（2） 在递增有序的单链表中插入一个新结点x，保持单链表的有序性。解题思路：首先查找插入的位置然后进行插入操作；从第一个结点开始找到第一个大于该新结点值的结点即为插入位置；然后在找到的此结点之前插入新结点；注意保留插入位置之前结点的指针才能完成插入操作。（3） 编写实现带头结点单链表就地逆置的子函数，并编写主函数测试结果。2、选做题已知指针LA和LB分别指向两个无头结点单链表的首元结点。要求编一算法实现，从表LA中删除自第i个元素起共len个元素后，将它们插入到表LB中第j个元素之前。程序清单：1、必做题#include&l

14、t;stdio.h>#include<stdlib.h>typedef struct node int data;struct node *next;linklist;linklist *CREATLINKLIST()/用尾插法创建单链表 int x; linklist *head,*s,*r; head = (linklist *)malloc(sizeof(linklist); r=head; printf("请输入单链表的数据元素(以-1结束)：n"); scanf("%d",&x); while(x!=-1) s=(li

15、nklist *)malloc(sizeof(linklist);/申请空间 s->data=x; r->next=s;/连接 r=s;/移动尾指针 scanf("%d",&x); r->next=NULL; return head;void printLINKLIST(linklist *head)/输出单链表linklist *q;q=head->next;if(q=NULL)printf("空表n");while(q)printf("%3d",q->data);q=q->next;pr

16、intf("n");/*（2）在递增有序的单链表中插入一个新结点x，保持单链表的有序性。*/linklist* Serachinsert(linklist *head,int x) linklist *p,*s; p=(linklist*)malloc(sizeof(linklist);p->data=x;if(head->next =NULL|head->next->data>=x)/判断x插入链表最前端 p->next =head->next ;head->next =p;return head;s=(linklist*)

17、malloc(sizeof(linklist);s=head->next ;while(s&&s->next )/判断插入链表中间if(x>s->data && x<=s->next ->data ) p->next=s->next ;s->next =p;return head;s=s->next ;s->next =p;/判断插入链表尾部p->next =NULL; return head; /(3)编写实现带头结点单链表就地逆置的子函数，并编写主函数测试结果linklist* I

18、nverselink(linklist *head) linklist *p,*s; p=head->next; if(p=NULL) return head; s=p->next; while(p->next) p->next=s->next ; s->next =head->next; head->next =s; do s=s->next; while(s!=p->next); return head;main() int x; linklist *H,*H1,*H2; H=CREATLINKLIST(); printf(&qu

19、ot;n"); printf("你所创建的单链表为：n"); printLINKLIST(H); printf("n插入Xn"); printf("输入要插入的值X：n"); scanf("%d",&x); H1=Serachinsert(H,x); printf("插入后的单链表为：n"); printLINKLIST(H1); printf("n逆置单链表n"); H2=Inverselink(H); printf("n单链表被逆置后为n&qu

20、ot;); printLINKLIST(H2); 2、选做题#include<stdio.h>#include<stdlib.h>typedef struct node int data;struct node *next;linklist;/用尾插法建立不带头结点的链表linklist *CREATLINKLIST() int x,num=1; linklist *head=NULL,*s=NULL,*r=NULL; printf("请输入单链表的数据元素(-1为结束符)：n"); scanf("%d",&x); whi

21、le(x!=-1) s=(linklist *)malloc(sizeof(linklist); s->data=x; if(head=NULL) head=s; else r->next=s; r=s; scanf("%d",&x); if(r!=NULL) r->next=NULL; return head; /输出函数void printLINKLIST(linklist *head)linklist *q=head;/q=head->next;if(q=NULL)printf("空表n");while(q)prin

22、tf("%2d",q->data);q=q->next;printf("n");/获得链表第i-1个位置linklist * GET(linklist * head,int i)int j = 1;linklist * p;p=head;while(p->next !=NULL&&(j<i)p=p->next ;j+;if(i=j)return p;elsereturn NULL;/*已知指针LA和LB分别指向两个无头结点单链表的首元结点。要求编一算法实现，从表LA中删除自第i个元素起共len个元素后，将它们

23、插入到表LB中第j个元素之前。*/linklist *CONNECT(linklist *la,int i,linklist *lb,int j,int len)linklist *p=la,*q=lb,*w=NULL,*s=NULL,*r=NULL,*t=NULL;if(i<=0|j<=0|len<=0) printf("连接失败！");return NULL;/获得la第i-1个位置w=GET(p,i-1);/删la中第i个元素后len个元素if(w!=NULL) while(len>0)s=w->next ;w->next =s-&

24、gt;next ;free(s);len-;elseprintf("没找到la第i个位置");return NULL; while(w->next!=NULL)w=w->next; /获得lb第i-1个位置 t=GET(q,j-1); /将la查到第j个元素之前if(t!=NULL)w->next=t->next ;t->next=la ;else printf("没找到lb第j个位置");return NULL;return lb;main()int i,j,len;linklist *h1,*h2;printf(&quo

25、t;创建链表h1n");h1=CREATLINKLIST(); printLINKLIST(h1);printf("创建链表h2n");h2=CREATLINKLIST();printLINKLIST(h2);printf("输入i,j,len 的值"); scanf("%d,%d,%d",&i,&j,&len);printf("删除链表la后第%d个元素后%d个元素，n",i,len);printf("插入链表lb中第%d个元素后.n",j);h2=CONNE

26、CT(h1,i,h2,j,len); printf("连接后的链表为：n");printLINKLIST(h2);四、实验结果与分析（程序运行结果及其分析）1、必做题（1）（2）（3）2、选做题五、实验体会（遇到问题及解决办法，编程后的心得体会）本次实验是对单链表的操作，对于插入要充分考虑插入的各种可能性，不能随便试一下成功就可以了。开始没理解老师在课堂上讲的逆置链表的算法，虽然当时同学用扑克牌的思想演示了一遍，但是代码的实现还是不会，后来在网上找到了课件，弄清楚算法后，程序就编出来了。实验项目名称： 堆栈和队列 实验学时： 2 同组学生姓名： 实验地点： A107 实验日

27、期： 6.5 实验成绩： 批改教师： 沈奇 批改时间： 实验3 堆栈和队列一、实验目的和要求（1）掌握应用栈解决问题的方法。（2）掌握利用栈进行表达式求和的算法。（3）掌握队列的存储结构及基本操作实现，并能在相应的应用问题中正确选用它们。二、实验仪器和设备Turbo C 2.0/ Visual C+三、实验内容与过程（含程序清单及流程图）1、必做题（1） 判断一个算术表达式中开括号和闭括号是否配对。（2） 测试“汉诺塔”问题。（3） 假设称正读和反读都相同的字符序列为”回文”，试写一个算法判别读入的一个以为结束符的字符序列是否是“回文”。2、选做题在顺序存储结构上实现输出受限的双端循环队列的入

28、列和出列算法。设每个元素表示一个待处理的作业，元素值表示作业的预计时间。入队列采取简化的短作业优先原则，若一个新提交的作业的预计执行时间小于队头和队尾作业的平均时间，则插入在队头，否则插入在队尾。程序清单：#include <stdio.h>#include <stdlib.h>#define MAX 100typedef struct char dataMAX;int top;seqstack;typedef struct nodechar data; struct node *next;linklist;linklist *CLINKLIST()char ch;in

29、t num=0;linklist * head,*s,*r;head=(linklist *)malloc(sizeof(linklist *);r=head;ch=getchar();while(ch!='')s=(linklist *)malloc(sizeof(linklist *);s->data=ch;num+;r->next=s;r=s;ch=getchar();head->data=num;r->next=NULL;return head;/输出链表元素void printLINKLIST(linklist *head)linklist *

30、q;q=head->next;if(q=NULL)printf("空表n");while(q)printf("%2c",q->data);q=q->next;printf("n");/1、判断输入字符串中'（'与'）'是否配对int match(char str)seqstack S;char ch;int i=0;S.top=-1;while(ch=stri)!='0')switch(ch)case '(':/左括号入栈S.data+S.top=

31、9;(' break;case ')':/右括号出栈if(S.top=-1) return -1;S.top-;break; i+;if(S.top<0) return 1;else return 0;/（2）测试"汉诺塔"问题。void move(char x,char y)printf("%c->%cn",x,y);void hanoi(int n,char one,char two,char three)if(n=1)move(one,three);elsehanoi(n-1,one,three,two);mov

32、e(one,three);hanoi(n-1,two,one,three);/*3.设单链表中存放n个字符，试设计一个算法，使用栈判断该字符串是否中心对称，如xyzzyx即为中心对称字符串*/int fun(linklist *head)int i ,n=head->data;linklist *p=head->next;seqstack S;S.top=-1;/栈初始化/判溢出if(n/2>MAX)printf("overflown");return -1;/一半元素入栈 for(i=0;i<n/2;i+)S.data+S.top=p->da

33、ta;p=p->next;/奇偶长度特殊处理if(n%2=1) p=p->next;/一一出栈，判是否相等while(p)S.top-;if(p->data!=S.dataS.top+1)return 0; p=p->next; return 1; void main() /主函数int m;int flag=0,j,select;char str20;linklist *head;while(1)printf("select=1进行括号是否配对操作n");printf("select=2进行汉诺塔测试n");printf(&qu

34、ot;select=3进行回文判断n");printf("select=0退出操作n");scanf("%d",&select);getchar();switch (select)case 1: printf("请输入一个算术表达式:n");scanf("%s",str);flag=match(str);if(flag=1) printf("左右括号配对!n");else if(flag=-1)printf("栈为空!n");else printf(&quo

35、t;左右括号不配对!n");break;case 2: printf("请输入柱子的数目n");scanf("%d",&m);printf("3个盘子挪动的步骤是：n");hanoi(m,'A','B','C');break;case 3:printf("请输入一个字符串存入链表(以为结束符)：n");head=CLINKLIST();printf("输出链表元素：n");printLINKLIST(head);flag=fun(

36、head);if(flag=1) printf("是一个回文!n");else printf("不是一个回文!n");break;case 0:printf("退出已程序！n");return;四、实验结果与分析（程序运行结果及其分析）1、必做题1）2）3）五、实验体会（遇到问题及解决办法，编程后的心得体会）本次的实验难度明显比前面两章要大，而且都应用到了实际的问题，其实栈和队列就是一种运算方式，一道问题有时候不仅可以用栈来完成，队列也同样可以完成，教科书上的链队列是单链表组成的链队列，同样只要熟悉了这些基本的构造方式，在判断回文中我

37、也构造出了双向链表组成的链队列，大大增加的程序的灵活性，其实简单的栈和队列就能解决实际问题，但是作为练习，还是应该尝试用其他方法做试试的。同时，由于题目相对还是比较有难度的，所以我觉得自己的代码尚且还有不完美的地方，有待改进。实验项目名称： 串 实验学时： 2 同组学生姓名： 实验地点： A107 实验日期： 6.9 实验成绩： 批改教师： 沈奇 批改时间： 实验4 串一、实验目的和要求掌握串的存储及应用。二、实验仪器和设备Turbo C 2.0/ Visual C+三、实验内容与过程（含程序清单及流程图）1、必做题（1） 编写输出字符串s中值等于字符ch的第一个字符的函数，并用主函数测试结果

38、。（2） 编写输出字符串s中值等于字符ch的所有字符的函数，并用主函数测试结果。解题思路：可以将第一题程序改进成一个子函数，在本题中循环调用。（3） 设字符串采用单字符的链式存储结构，编程删除串s从位置i开始长度为k的子串。2、选做题假设以链结构表示串，编写算法实现将串S插入到串T中某个字符之后，若串T中不存在这个字符，则将串S联接在串T的末尾。提示：为提高程序的通用性，插入位置字符应设计为从键盘输入。程序清单：1、必做题（1）#include<stdio.h>#define maxsize 100typedef struct /定义顺序串char chmaxsize;int cu

39、rlen;seqstring;main()int i;char ch;seqstring s="asdfgh",6;for(i=0;i<s.curlen;i+)printf("%c",s.chi);printf("nPlease input aa character ch:");scanf("%c",&ch);for(i=0;i<s.curlen;i+)if(s.chi=ch)printf("ch=s.ch%d=%cn",i,s.chi);break;if(i>=s.c

40、urlen)printf("Not find!n");（2）#include<stdio.h>#define maxsize 100typedef struct /定义顺序串char chmaxsize;int curlen;seqstring;main()int i,flag=0;char ch;seqstring s="abadea",6;for(i=0;i<s.curlen;i+)printf("%c",s.chi);printf("nPlease input aa character ch:&quo

41、t;);scanf("%c",&ch);for(i=0;i<s.curlen;i+)if(s.chi=ch)printf("ch=s.ch%d=%cn",i,s.chi);flag+;if(flag=0)printf("Not find!n");3）#include<stdio.h>#include<stdlib.h>typedef struct linknode/定义链串 char data; struct linknode *next;linkstring;linkstring *Creatl

42、ink(linkstring *S) linkstring *p=NULL,*q=NULL; char ch; ch=getchar(); while(ch!='#') p=malloc(sizeof(linkstring);p->data=ch;if(S=NULL) S=p,q=p;else q->next=p,q=p; ch=getchar(); if(q->next!=NULL) q->next=NULL; return S;linkstring *Delete(linkstring *S,int i,int k)/假定字符串足够长 linkstr

43、ing *p=S,*q; int m=2; while(m<i) p=p->next; m+; m=0; if(i=1)while(m<k)S=p->next;free(p);p=S;m+; elsewhile(m<k) q=p->next;p->next=q->next; free(q);m+; return S;void Output(linkstring *S) linkstring *p=S; while(p!=NULL) printf("%2c",p->data); p=p->next; int main

44、() linkstring *S=NULL; int i,k; S=Creatlink(S); Output(S); printf("n"); printf("Please enter the location and the length:"); scanf("%d,%d",&i,&k); S=Delete(S,i,k); getchar(); Output(S); printf("n"); return 0;四、实验结果与分析（程序运行结果及其分析）1、必做题1）2）3）五、实验体会（遇到问题及

45、解决办法，编程后的心得体会）在这次实验中的一些问题借助之前C语言中的一些经验很快就解决了，但要注意一些该注意的细节。在做选做题时，刚开始链串插入时没有画图异想天开的插入链后，但错了，后来借助画图，终于将它改正过来。第三题刚开始做的时候忽略了删除第一个字符的情况，在检查时发现，思考后把算法补充完整。实验项目名称： 二叉树 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 6.12 实验成绩： A107 批改教师： 沈奇 批改时间： 实验5 二叉树一、实验目的和要求（1）掌握二叉树的生成，以及前、中、后序遍历算法。（2）掌握应用二叉树递归遍历思想解决问题的方法。二、实验仪器和设备Turbo

46、C 2.0/ Visual C+三、实验内容与过程（含程序清单及流程图）1、必做题（1） 建立一棵二叉树。对此树进行前序遍历、中序遍历及后序遍历，输出遍历序列。（2） 在第一题基础上，求二叉树中叶结点的个数。（3） 在第一题基础上，求二叉树中结点总数。（4） 在第一题基础上，求二叉树的深度。2、选做题已知一棵完全二叉树存于顺序表sa中，sa.elem1sa.last存储结点的值。试编写算法由此顺序存储结构建立该二叉树的二叉链表。解题思路：根据完全二叉树顺序存储的性质来确定二叉树的父子关系即“还原”了二叉树，之后再按照二叉树二叉链表的构造方法进行建立。完全二叉树顺序存储的一个重要性质为，第i个结

47、点的左孩子是编号为2i的结点，第i个结点的右孩子是编号为2i+1的结点。程序清单：#include <stdio.h>#include <stdlib.h>#define maxsize 100typedef struct node char data;struct node *lchild,*rchild;bitree;/(1)二叉树的创建bitree *CREATREE(bitree *Qmaxsize)char ch;int front,rear;bitree *root,*s;root=NULL;front=1; rear=0;ch=getchar();whil

48、e(ch!='#')s=NULL;if(ch!='')s=(bitree*)malloc(sizeof(bitree);s->data=ch;s->lchild=NULL;s->rchild=NULL;rear+;Qrear=s;if(rear=1) root=s;elseif(s&&Qfront)if(rear%2=0) Qfront->lchild=s;elseQfront->rchild=s;if(rear%2=1) front+;ch=getchar();return root;/二叉树的前序遍历void P

49、REORDER(bitree *t)if(t)printf("%c ",t->data);PREORDER(t->lchild);PREORDER(t->rchild);/二叉树的中序遍历void INORDER(bitree *t)if(t)INORDER(t->lchild);printf("%c ",t->data);INORDER(t->rchild);/二叉树的后序遍历void POSTORDER(bitree *t)if(t)POSTORDER(t->lchild);POSTORDER(t->r

50、child);printf("%c ",t->data);/求二叉树中叶子结点总数void COUNTLEFT(bitree *t,int *count)if(t) if(t->lchild=NULL && t->rchild=NULL) (*count)+; COUNTLEFT(t->lchild,count); COUNTLEFT(t->rchild,count);/求二叉树中结点总数void COUNT(bitree *t,int *count)if(t)(*count)+;COUNT(t->lchild,count

51、); COUNT(t->rchild,count);/(4)求二叉树的深度int BITREEDEPTH(bitree *t)int left,right;if(t=NULL)return 0;left=BITREEDEPTH(t->lchild);right=BITREEDEPTH(t->rchild);return left>right?(left+1):(right+1);main() bitree *r=NULL;bitree *Qmaxsize;int s=0;printf("创建二叉树,请输入你要创建的二叉树(''表示空结点,以'#'号