算法与数据结构实验

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

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

3、定位、插入、删除等操作。二、实验仪器和设备VC6.0三、实验内容与过程（含程序清单及流程图）1、必做题（1） 编写程序建立一个顺序表，并逐个输出顺序表中所有数据元素的值。编写主函数测试结果。（2） 编写顺序表定位操作子函数，在顺序表中查找是否存在数据元素x。如果存在，返回顺序表中和x值相等的第1个数据元素的序号（序号从0开始编号）；如果不存在，返回1。编写主函数测试结果。（3） 在递增有序的顺序表中插入一个新结点x，保持顺序表的有序性。解题思路：首先查找插入的位置，再移位，最后进行插入操作；从第一个元素开始找到第一个大于该新结点值x的元素位置i即为插入位置；然后将从表尾开始依次将元素后移一个位

4、置直至元素i；最后将新结点x插入到i位置。（4） 删除顺序表中所有等于X的数据元素。2、选做题（5） 已知两个顺序表A和B按元素值递增有序排列，要求写一算法实现将A和B归并成一个按元素值递减有序排列的顺序表（允许表中含有值相同的元素）。程序清单：(1)#include <stdio.h>#define maxsize 20typedef int datatype;typedef structdatatype datamaxsize;int last; sequenlist; void CreateList(sequenlist *L,int n)int i;printf("

5、;please input n numbersn");for(i=0;i<n;i+) scanf("%d",&L->datai); (*L).last=n; void PrintList(sequenlist *L,int n)int i; printf("the sequenlist isn"); for(i=0;i<n;i+) printf("%d ",L->datai);main() int i,x; int n=10; sequenlist L; CreateList(&L,n

6、); PrintList(&L,n); getchar(); (2)#include<stdio.h> typedef int datatype; #define maxsize 1024 typedef struct datatype datamaxsize; int last; sequenlist; int fun(sequenlist L,int x,int n) int i;for(i=0;i<n;i+)if(L.datai=x)return i;return -1;void main()sequenlist L;int i,n,y;int x;printf

7、("请输入元素的个数：");scanf("%d",&n);for(i=0;i<n;i+)scanf("%d",&L.datai);printf("n请输入要查找的数据元素：");scanf("%d",&x);y = fun(L,x,n);if (y=1)printf("n所要查找的数据元素不存在n");elseprintf("n数据元素%d所在的位置为%dn",x,y);(3)#include <stdio.h>#

8、define maxsize 100 typedef struct int datamaxsize; int last; sequenlist; main() int i,x,j; sequenlist l=1,2,4,5,6,7,8,6; printf("n插入元素前的数据为:");for(i=0;i<=l.last;i+) printf("%2d",l.datai); printf("n请输入要插入的元素:"); scanf("%d",&x); for(i=1;i<=l.last;i+) i

9、f(l.datai-1>x) break; if(i>l.last ) l.data l.last +1=x; else for(j=l.last;j>=i-1;j-) l.dataj+1=l.dataj; l.datai-1=x; l.last+; printf("插入元素后的数据为:n"); for(j=0;j<=l.last;j+) printf("%3d",l.dataj); printf("n");return 0; (4)#include <stdio.h>#define maxsize

10、 100 typedef struct int datamaxsize; int last; sequenlist; main() int i,j,x=0,k=0; sequenlist L=1,3,5,7,2,4,6,8,2,9,9;printf("n原数据为:"); for(i=0;i<=L.last;i+) printf("%3d",L.datai); printf("n请输入要删除的数据:"); scanf("%d",&x); for(i=1;i<=L.last+1;i+) if(L.d

11、atai-1=x)for(j=i;j<=L.last+1;j+) L.dataj-1=L.dataj; L.last-; i-; k=1; if(k=1) printf("删除后的数据为:n"); for(j=0;j<=L.last;j+) printf("%3d",L.dataj); else printf("Not found!n"); printf("n"); 四、实验结果与分析（程序运行结果及其分析）1.11.21.31.4五、实验体会（遇到问题及解决办法，编程后的心得体会）遇到问题：读取数据元

12、素时，误将=写成=，导致错误。实验过程中，顺序表的赋值没有弄懂，以致输出多个0或者少输出。格式运算符也要正确控制，否则系统会停止工作。实验体会：通过实验掌握了顺序表的基本操作，如初始化、插入、读取元素、删除等等。并了解到线性表顺序存储结构的特点，即逻辑关系上相邻的两个元素在物理位置上也相邻，然而从另一方面来看，在做插入和删除时需要移动大量元素。本次实验基本完成了实验要求的目的，顺序表的初始化，定义，插入，查找等，更好的了解了顺序表基本操作的算法，以及更直观的了解了数据结构在C语言环境下的体现。实验项目名称： 单链表 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师：

13、 批改时间： 实验2 单链表一、实验目的和要求1、实验目的掌握单链表的定位、插入、删除等操作。2、实验要求（1）注意链表的空间是动态分配的，某结点不用之后要及时进行物理删除，以便释放其内存空间。（2）链表不能实现直接定位，一定注意指针的保存，防止丢失。二、实验仪器和设备Visual C+6.0三、实验内容与过程（含程序清单及流程图）1、必做题（1） 编写程序建立一个单链表，并逐个输出单链表中所有数据元素。（2） 在递增有序的单链表中插入一个新结点x，保持单链表的有序性。解题思路：首先查找插入的位置然后进行插入操作；从第一个结点开始找到第一个大于该新结点值的结点即为插入位置；然后在找到的此结点之

14、前插入新结点；注意保留插入位置之前结点的指针才能完成插入操作。（3） 编写实现带头结点单链表就地逆置的子函数，并编写主函数测试结果。2、选做题已知指针LA和LB分别指向两个无头结点单链表的首元结点。要求编一算法实现，从表LA中删除自第i个元素起共len个元素后，将它们插入到表LB中第j个元素之前。程序清单：（1）#include<stdio.h> #include<stdlib.h> typedef struct node int data; struct node *next; *Linklist,Node; Linklist creat(int n) Linklis

15、t head,r,p; int x,i; head=(Node*)malloc(sizeof(Node); r=head; printf("输入数字:n"); for(i=n;i>0;i-) scanf("%d",&x); p=(Node*)malloc(sizeof(Node); p->data=x; r->next=p; r=p; r->next=NULL; return head; void output(Linklist head) Linklist p; p=head->next; do printf(&q

16、uot;%3d",p->data); p=p->next; while(p); printf("n"); void main() Linklist head;int x,n; printf("输入数字的个数(n):n"); scanf("%d",&n); head=creat(n); printf("输出数字:n"); output(head); （2）#include <stdio.h>#include <stdlib.h>typedef struct nod

17、e int data; struct node *next;linklist;main() int x,y; linklist *h,*s,*r,*p,*q,*m,*n; h=malloc(sizeof(linklist); r=h; printf("请输入一个数组 :"); scanf("%d",&x); while(x!=0) s=malloc(sizeof(linklist); s->data=x; r->next=s; r=s; scanf("%d",&x); r->next=NULL; pr

18、intf("请输入插入值:"); scanf("%d",&y); p=h->next; while(p!=NULL) if (p->data)<y) p=p->next; else break; q=malloc(sizeof(linklist); q->data=y; m=h; while(m->next!=p) m=m->next; q->next=p; m->next=q; n=h->next; printf("这个链表是:"); while(n!=NULL)

19、printf("%2d",n->data); n=n->next; （3）#include <stdio.h>#include <stdlib.h>typedef struct node int data; struct node *next;linklist;main() int x; linklist *h,*s,*r,*p,*q,*t; h=malloc(sizeof(linklist); r=h; printf("请输入一个数组:"); scanf("%d",&x); while(x

20、!=-1) s=malloc(sizeof(linklist); s->data=x; r->next=s; r=s; scanf("%d",&x); r->next=NULL; printf("n这个链表是:n"); p=h->next; while(p!=NULL) printf("%2d",p->data); p=p->next; p=h->next; q=p->next; while(q!=NULL) t=q->next; q->next=p; p=q; q=

21、t; h->next->next=NULL; h->next=p; printf("n翻转转后的链表是:n"); p=h->next; while(p!=NULL) printf("%2d",p->data); p=p->next; 四、实验结果与分析（程序运行结果及其分析）(1)(2)(3)五、实验体会（遇到问题及解决办法，编程后的心得体会）遇到问题：编写成功后运行时，没有加入$导致程序运行不成功，不能够退出。后注意到这个问题才继续运行下去。实验体会：在编写程序时，设置了结束字符一定要牢牢记住，并且在输入时观察仔细类

22、型是什么，以及是否是输入一串有顺序的数字，编写成功不难，但是要规范格式，不能仅仅以完成程序为目的。而完成这一章的实验也让我了解了，顺序表便于查找不便于插入删除，而链表恰恰相反，链表的插入删除只需要移动指针，而顺序表要从后往前依次移动，二者各有优劣.实验项目名称： 堆栈和队列 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 实验3 堆栈和队列一、实验目的和要求（1）掌握应用栈解决问题的方法。（2）掌握利用栈进行表达式求和的算法。（3）掌握队列的存储结构及基本操作实现，并能在相应的应用问题中正确选用它们。二、实验仪器和设备Visual C+6.0三、实验

23、内容与过程（含程序清单及流程图）1、必做题（1） 判断一个算术表达式中开括号和闭括号是否配对。（2） 测试“汉诺塔”问题。（3） 假设称正读和反读都相同的字符序列为”回文”，试写一个算法判别读入的一个以为结束符的字符序列是否是“回文”。2、选做题在顺序存储结构上实现输出受限的双端循环队列的入列和出列算法。设每个元素表示一个待处理的作业，元素值表示作业的预计时间。入队列采取简化的短作业优先原则，若一个新提交的作业的预计执行时间小于队头和队尾作业的平均时间，则插入在队头，否则插入在队尾。程序清单：（1）#include <stdio.h>#include <stdlib.h>

24、;typedef char datatype;#define maxsize 64typedef struct datatype datamaxsize; int top; seqstack;int match(char exp,int n)char stmaxsize; /设置一个栈，用来存放扫描表达式中的括号 int top=-1,i=0,tag=1; while(i<n&&tag=1) if(expi='('|expi=''|expi='') /遇到'(''''',则将其

25、入栈 top+; sttop=expi; if(expi=')') /遇到')',若栈顶是'(',则继续处理，否则以不配对返回 if(sttop='(') top-; else tag=0; if(expi='') if(sttop='') top-; else tag=0; if(expi='') if(sttop='') top-; else tag=0; i+; if(top>=0) tag=0; /若栈不空，则不配对return tag;main()in

26、t tag,i; char exp7='+','(','2','-','4',')' printf("请输入一个算式表达式：n"); for(i=0;i<7;i+) expi=getchar(); tag=match(exp,7); if(tag) printf("算式表达式中的开括号和闭括号配对。"); else printf("算式表达式中的开括号和闭括号不配对！");(2)#include <stdio.h>void

27、 move(char x,char z)printf("%c->",x); printf("%cn",z);void Hanoi(int n,char x, char y,char z) if(n=1) move(x,z); else Hanoi(n-1,x,z,y); move(x,z); Hanoi(n-1,y,x,z); main() int m; printf("请你输入A上面的碟子总数"); scanf("%d",&m); Hanoi(m,'A','B',&#

28、39;C'); getchar(); getchar();(3)#include<stdio.h>#define N 100typedef struct char dataN; int top;seqstack;main() char strN; int i=0,n; seqstack a; a.top=0; gets(str); while(stri!='') i+; n=i; for(i=0;i<n/2;i+) a.top+; a.dataa.top=stri; i=i-1; if(n%2=0) i+; else i=i+2; while(i<

29、;n && a.dataa.top=stri) i+; a.top-; if(i=n) printf("是回文数组n"); else printf("不是回文数组n");四、实验结果与分析（程序运行结果及其分析）123五、实验体会（遇到问题及解决办法，编程后的心得体会）遇到问题：在本章栈和队列中编程，有许多的if语句，编写时一不小心就会少加一个花括号，以致编写不成功。在本章汉诺塔问题中，使用了栈以及函数的递归，这其中的过程一直不是很了解，在经过老师的讲解后，理解了大致过程。实验体会：递归函数是编程中经常会用到的一种函数，它可以实现许多我们

30、在平时言语和解释上解决不了的问题，我们需要理解并且可以熟练的使用它，这对我们之后的编程会有很大的帮助。而汉诺塔利用栈是一种很经典的递归的算法，这让我们理解栈和递归。实验项目名称： 串 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 实验4 串一、实验目的和要求掌握串的存储及应用。二、实验仪器和设备Visual C+6.0三、实验内容与过程（含程序清单及流程图）1、必做题（1） 编写输出字符串s中值等于字符ch的第一个字符的函数，并用主函数测试结果。（2） 编写输出字符串s中值等于字符ch的所有字符的函数，并用主函数测试结果。解题思路：可以将第一题程序

31、改进成一个子函数，在本题中循环调用。（3） 设字符串采用单字符的链式存储结构，编程删除串s从位置i开始长度为k的子串。2、选做题假设以链结构表示串，编写算法实现将串S插入到串T中某个字符之后，若串T中不存在这个字符，则将串S联接在串T的末尾。提示：为提高程序的通用性，插入位置字符应设计为从键盘输入。程序清单：(1)#include <stdio.h>void search(char *s,char ch)int i=0,n=0;while (*(s+i)if(*(s+i)=ch)printf("第一个字符：s%d=%cn",i,ch);n+;break;i+;i

32、f(!n) printf("No Found!n");void main()char s20,ch;printf("请输入一个串:");gets(s);printf("请输入要找的元素:");scanf("%c",&ch);search(s,ch);(2)#include <stdio.h>void search(char *s,char ch)int i=0,n=0;while (*(s+i)if(*(s+i)=ch)n+;printf("第%d个%c在串中的下标为：%dn"

33、;,n,ch,i);i+;if(!n) printf("No Found!n");void main()char s20,ch;printf("请输入串元素：");gets(s);printf("请输入要找的元素：");scanf("%c",&ch);search(s,ch);(3)#include<stdio.h>#include<stdlib.h>typedef struct linknodechar data;struct linknode *next;linkstring;l

34、inkstring *CREAT()linkstring *head = NULL,*p = NULL,*s = NULL;int a;printf("请输入顺序表的值，'-1'表示输入结束：n");scanf ("%d",&a);while (a!=-1)s= (linkstring *)malloc(sizeof(linkstring);if (s = NULL)exit(0);s->data = a;if(head = NULL)head = s;else p->next = s;p=s;scanf ("

35、;%d",&a);p->next = NULL;printf("建立完毕！n");return head;int SEARCH(linkstring *s,int i, int k)linkstring *p =s;int j= 0;for(;j<i+k-2&&p->next!=NULL;j+)p = p->next;if(j=i+k-2)return 1;return 0;void DELETE(linkstring *s,int i,int k)linkstring *p = s,*q = NULL;int j=

36、1;for(;j<i-1;j+)p=p->next;for(j=0;j<k;j+)q= p->next;p->next = q->next;free(q);printf("成功删除！");void PRINT(linkstring *head)linkstring *s = NULL;s = head;while (s)printf("%d ",s->data);s= s->next;printf("打印完毕！nn");int main()linkstring *ls;int i,k,m

37、;ls = CREAT();PRINT(ls);printf("输入你想删除第几个字符起的连续的多少个字符：");scanf ("%d%d",&i,&k);m = SEARCH(ls,i,k);if(m=0)printf("不存在这样的子串，删除失败！");elseDELETE(ls,i,k);PRINT(ls);return 0;四、实验结果与分析（程序运行结果及其分析）(1) (2)(3)五、实验体会（遇到问题及解决办法，编程后的心得体会）实验体会：本章第一题可以作为第二题的子函数，使用调用；也可以从开头查找对应的

38、字符到结尾，最后全部输出。前两题使用顺序串，后面一题是链串。串的存储结构包含有顺序存储结构和链式存储结构。在串的顺序存储结构中，表示串的长度通常有两种方法：一种方法是设置一个串的长度参数，其优点在于便于在算法中用长度参数控制循环过程；另一种方法是在串值得末尾添加结束标记，此种方法的优点在于便于系统自动实现。在串的存储过程中，串值用双引号引起来，系统将自动在串值得末尾添加结束标记0字符。实验项目名称： 二叉树 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 实验5 二叉树一、实验目的和要求（1）掌握二叉树的生成，以及前、中、后序遍历算法。（2）掌握应用

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

40、完全二叉树顺序存储的一个重要性质为，第i个结点的左孩子是编号为2i的结点，第i个结点的右孩子是编号为2i+1的结点。程序清单：（1）#include <stdio.h>#include <stdlib.h>#define maxsize 20typedef struct node char data; struct node *lchild,*rchild;bitree;bitree *Qmaxsize;bitree *Creatree() char ch; int front,rear; bitree *root,*s; root=NULL;front=1;rear=

41、0; printf("Now Creat the bitree,input baseing the order top to bottom,left to right:n"); ch=getchar(); while(ch!='#') s=NULL; if(ch!='') s=malloc(sizeof(bitree); s->data=ch; s->lchild=NULL; s->rchild=NULL; rear+; Qrear=s; if(rear=1) root=s; else if(s && Qfr

42、ont)if(rear%2=0) Qfront->lchild=s;else Qfront->rchild=s; if(rear%2=1) front+; ch=getchar(); return root;void preorder(t)bitree *t; if(t) printf("%c",t->data); preorder(t->lchild); preorder(t->rchild); void inorder(t)bitree *t; if(t) inorder(t->lchild); printf("%c&quo

43、t;,t->data); inorder(t->rchild); void postorder(t)bitree *t; if(t) postorder(t->lchild); postorder(t->rchild); printf("%c",t->data); main() bitree *root; root=Creatree(); printf("preorder is:");preorder(root); printf("n"); printf("inorder is:");

44、inorder(root); printf("n"); printf("postorder is:");postorder(root); printf("n");(2)#include<stdio.h>#include<stdlib.h>#define maxsize 100typedef struct node char data; struct node *lchild,*rchild;bitree;bitree *Qmaxsize;bitree *Creatree() char ch; int front

45、,rear; bitree *root,*s; root=NULL;front=1;rear=0; printf("Now Creat the bitree,input baseing the order top to bottom,left to right:n"); ch=getchar(); while(ch!='#') s=NULL; if(ch!='') s=malloc(sizeof(bitree); s->data=ch; s->lchild=NULL; s->rchild=NULL; rear+; Qrear

46、=s; if(rear=1) root=s; else if(s && Qfront)if(rear%2=0) Qfront->lchild=s;else Qfront->rchild=s; if(rear%2=1) front+; ch=getchar(); return root;int left(bitree *t) int num1,num2; if(t=NULL) return 0; else if(t->lchild=NULL && t->rchild=NULL) return 1; else num1=left(t->

47、lchild); num2=left(t->rchild); return(num1+num2); main() bitree *root; root=Creatree(); printf("lefts is %dn",left(root);(3)#include<stdio.h>#include<stdlib.h>#define maxsize 100typedef struct node char data; struct node *lchild,*rchild;bitree;bitree *Qmaxsize;bitree *Creatr

48、ee() char ch; int front,rear; bitree *root,*s; root=NULL;front=1;rear=0; printf("Now Creat the bitree,input baseing the order top to bottom,left to right:n"); ch=getchar(); while(ch!='#') s=NULL; if(ch!='') s=malloc(sizeof(bitree); s->data=ch; s->lchild=NULL; s->rc

49、hild=NULL; rear+; Qrear=s; if(rear=1) root=s; else if(s && Qfront)if(rear%2=0) Qfront->lchild=s;else Qfront->rchild=s; if(rear%2=1) front+; ch=getchar(); return root;int nodes(bitree *t) int num1,num2; if(t=NULL) return 0; else if(t->lchild=NULL &&t->rchild=NULL) return 1

50、; else num1=nodes(t->lchild); num2=nodes(t->rchild); return (num1+num2+1); main() bitree *root; root=Creatree(); printf("nodes is %dn",nodes(root);(4)#include<stdio.h>#include<stdlib.h>#define maxsize 100typedef struct node char data; struct node *lchild,*rchild;bitree;bi

51、tree *Qmaxsize;bitree *Creatree() char ch; int front,rear; bitree *root,*s; root=NULL;front=1;rear=0; printf("Now Creat the bitree,input baseing the order top to bottom,left to right:n"); ch=getchar(); while(ch!='#') s=NULL; if(ch!='') s=malloc(sizeof(bitree); s->data=ch; s->lchild=NULL; s->rchild=NULL; rear+; Qrear=s; if(rear=1) root=s; else if(s && Qfront)if(rear%2=0) Qfront->lchild=s;else Qfront->rchild=s; if(rear%2=1) front+; ch