算法与大数据结构实验册

算法与大数据结构实验册算法与大数据结构实验册算法与大数据结构实验册适用标准文案学生实验报告册〔理工类〕课程名称：算法与数据结构专业班级：___________学生学号：__________学生姓名：___所属院部：------------指导教师：2013——2014学年第2学期金陵科技学院教务处制出色文档适用标准文案实验报告书写要求实验报告原那么上要修业新手写，要求书写工整。假定因课程特色需打印的，要依照以下字体、字号、间距等的详细要求。纸张一律采纳A4的纸张。实验报告书写说明实验报告中一至四项内容为必填项，包含实验目的和要求；实验仪器和设施；实验内容与过程；实验结果与剖析。各院部可依据学科特色和实验详细要求增添工程。填写本卷须知1〕仔细察看，实时、正确、照实记录。2〕正确说明，层次清楚。3〕尽量采纳专用术语来说明事物。4〕外文、符号、公式要正确，应使用一致规定的名词和符号。5〕应独立达成实验报告的书写，禁止剽窃、复印，一经发现，以零分论处。实验报告批阅说明实验报告的批阅要实时、认真、认真，一律用红色笔批阅。实验报告的批阅成绩采纳百分制，详细评分标准由各院部自行拟订。实验报告装订要求实验批阅完成后，任课老师将每门课程的每个实验工程的实验报告以自然班为单位、按学号升序摆列，装订成册，并附上一份该门课程的实验纲领。出色文档适用标准文案实验工程名称：次序表实验学时：2同组学生姓名：实验地址：实验日期：实验成绩：批阅教师：批阅时间：出色文档适用标准文案实验1次序表一、实验目的和要求掌握次序表的定位、插入、删除等操作。二、实验仪器和设施三、实验内容与过程〔含程序清单及流程图〕1、必做题1〕编写程序成立一个次序表，并逐一输出次序表中全部数据元素的值。编写主函数测试结果。〔2〕编写次序表定位操作子函数，在次序表中查找能否存在数据元素x。假如存在，返回次序表中和x值相等的第1个数据元素的序号〔序号从0开始编号〕；假如不存在，返回－1。编写主函数测试结果。3〕在递加有序的次序表中插入一个新结点x，保持次序表的有序性。解题思路：第一查找插入的地点，再移位，最后进行插入操作；从第一个元素开始找到第一个大于该新结点值x的元素地点i即为插入位置；而后将从表尾开始挨次将元素后移一个地点直至元素i；最后将新结点x插入到i地点。〔4〕删除次序表中全部等于X的数据元素。2、选做题5〕两个次序表A和B按元素值递加有序摆列，要求写一算法实现将A和B合并成一个按元素值递减有序摆列的次序表〔同意表中含有值同样的元素〕。程序清单：1.(1)#include<stdio.h>#definemaxsize20typedefstruct{intdata[maxsize];intlast;出色文档适用标准文案}sequenlist;voidCreatlist(sequenlist*L,intn)//成立次序表{inti;for(i=0;i<n;i++)scanf("%d",&(*L).data[i]);(*L).last=n;}voidOutputlist(sequenlist*L,intn)//输出次序表{intj;for(j=0;j<n;j++)printf("%2d",(*L).data[j]);printf("\n");}intmain(){intn=5;sequenlistL;Creatlist(&L,n);printf("Thearrayis:");Outputlist(&L,n);出色文档适用标准文案return0;}(2)intSearch(sequenlist*L,intn,intx)//搜寻数据元素x{inti,flag=-1;for(i=0;i<n;i++){if(L->data[i]==x){flag=i;break;}}returnflag;}3〕#include<stdio.h>#definemaxsize20typedefstruct{intdata[maxsize];intlast;}sequenlist;出色文档适用标准文案voidCreatlist(sequenlist*L,intn)//创办次序表{inti;for(i=0;i<n;i++)scanf("%d",&(*L).data[i]);(*L).last=n;}voidOutputlist(sequenlist*L,intn)//输出次序表{intj;for(j=0;j<n;j++)printf("%2d",(*L).data[j]);printf("\n");}voidInsert(sequenlist*L,intn,intx)//插入元素X{inti,j;for(i=0;i<n;i++){if(L->data[i]<x)continue;else{出色文档适用标准文案for(j=L->last;j>=i;j--)L->data[j+1]=L->data[j];L->data[i]=x;break;}}L->last++;}intmain(){intn=5,x;sequenlistL;Creatlist(&L,n);printf("Thearrayis:");Outputlist(&L,n);printf("Theaddednumberis:");scanf("%d",&x);Insert(&L,n,x);Outputlist(&L,L->last);return0;}出色文档适用标准文案voidDelete(sequenlist*L,intn,intx){inti,j;for(i=0;i<n;i++){if((*L).data[i]!=x)continue;else{for(j=i;j<n-1;j++)(*L).data[j]=(*L).data[j+1];n--;i--;}}(*L).last=n;}四、实验结果与剖析〔程序运转结果及其剖析〕出色文档适用标准文案五、实验领会〔碰到问题及解决方法，编程后的心得领会〕出色文档适用标准文案实验工程名称：单链表实验学时：2同组学生姓名：实验地址：实验日期：实验成绩：批阅教师：批阅时间：出色文档适用标准文案3实验2单链表一、实验目的和要求1、实验目的掌握单链表的定位、插入、删除等操作。2、实验要求〔1〕注意链表的空间是动向分派的，某结点不用以后要实时进行物理删除，以便开释其内存空间。〔2〕链表不可以实现直接定位，必定注意指针的保留，防备丧失。二、实验仪器和设施三、实验内容与过程〔含程序清单及流程图〕1、必做题〔1〕编写程序成立一个单链表，并逐一输出单链表中全部数据元素。〔2〕在递加有序的单链表中插入一个新结点x，保持单链表的有序性。解题思路：第一查找插入的地点而后进行插入操作；从第一个结点开始找到第一个大于该新结点值的结点即为插入地点；而后在找到的此结点以前插入新结点；注意保留插入地点以前结点的指针才能达成插入操作。〔3〕编写实现带头结点单链表就地逆置的子函数，并编写主函数测试结果。2、选做题指针LA和LB分别指向两个无头结点单链表的首元结点。要求编一算法实现，从表LA中删除自第i个元素起共len个元素后，将它们插入到表LB中第j个元素以前。程序清单：1〔1〕#include<stdio.h>#include<stdlib.h>typedefstructnode{intdata;structnode*next;出色文档适用标准文案}linklist;linklist*Creatlist(linklist*head)//创办单链表{charch;linklist*p=NULL,*s=NULL;ch=getchar();while(ch!='$'){p=malloc(sizeof(linklist));p->data=ch;if(head==NULL)head=p;elses->next=p;s=p;ch=getchar();}if(s!=NULL)s->next=NULL;returnhead;}intmain(){linklist*head=NULL,*p=NULL;head=Creatlist(head);出色文档适用标准文案p=head;while(p!=NULL){printf("%c",p->data);p=p->next;}return0;}2〕#include<stdio.h>#include<stdlib.h>typedefintdatatype;typedefstructnode{datatypedata;structnode*next;}linklist;linklist*CREATLISTR(linklist*head){charch;linklist*s,*r;r=NULL;出色文档适用标准文案scanf("%c",&ch);while(ch!='$'){s=malloc(sizeof(linklist));s->data=ch;if(head==NULL)head=s;elser->next=s;r=s;scanf("%c",&ch);}if(r!=NULL)r->next=NULL;returnhead;}linklist*INSERT(linklist*head,intx)//插入元素X{linklist*s,*q,*r;s=malloc(sizeof(linklist));s->data=x;q=head;r=q->next;出色文档适用标准文案while(r->data<x){q=r;r=r->next;}s->next=r;q->next=s;returnhead;}intmain(){charx;linklist*head=NULL,*p=NULL;scanf("%c",&x);head=CREATLISTR(head);p=head;while(p!=NULL){printf("%c",p->data);p=p->next;}出色文档适用标准文案head=INSERT(head,x);p=head;while(p!=NULL){printf("%c",p->data);p=p->next;}printf("\n");return0;}〔3〕linklist*Invert(linklist*head)//将单链表逆置{linklist*p=NULL,*q=NULL,*r=NULL;if(head==NULL||head->next==NULL)returnhead;p=head;q=p->next;while(q!=NULL){r=q->next;q->next=p;p=q;出色文档适用标准文案q=r;}head->next=NULL;head=p;returnhead;}四、实验结果与剖析〔程序运转结果及其剖析〕五、实验领会〔碰到问题及解决方法，编程后的心得领会〕出色文档适用标准文案实验工程名称：货仓和行列实验学时：2同组学生姓名：实验地址：实验日期：实验成绩：批阅教师：批阅时间：出色文档适用标准文案实验3货仓和行列一、实验目的和要求1〕掌握应用栈解决问题的方法。2〕掌握利用栈进行表达式乞降的算法。3〕掌握行列的储存结构及根本操作实现，并能在相应的应用问题中正确采纳它们。二、实验仪器和设施三、实验内容与过程〔含程序清单及流程图〕1、必做题1〕判断一个算术表达式中开括号和闭括号能否配对。2〕假定称正读和反读都同样的字符序列为〞回文〞，试写一个算法鉴别读入的一个以’@’为结束符的字符序列是不是“回文〞。2、选做题1〕测试“汉诺塔〞问题。2〕在次序储存结构上实现输出受限的双端循环行列的入列和出列算法。设每个元素表示一个待办理的作业，元素值表示作业的估计时间。入行列采纳简化的短作业优先原那么，假定一个新提交的作业的估计履行时间小于队头和队尾作业的均匀时间，那么插入在队头，否那么插入在队尾。程序清单：1〔1〕#include<stdio.h>#include<stdlib.h>#definemaxsize64typedefstructnode{chardata[maxsize];inttop;出色文档适用标准文案}seqstack;intJudge(chara[],intn,seqstack*s)//判断括号能否配对{inti,flag=1;s->top=-1;for(i=0;i<n;i++){if(a[i]=='('){s->top++;s->data[s->top]=a[i];}if(a[i]==')'){if(s->top==-1||s->data[s->top]!='('){flag=0;break;}else{s->top--;出色文档适用标准文案}}}if(s->top>-1)flag=0;returnflag;}intmain(){seqstacks;chara[maxsize]={0},ch;intn=0,flag;ch=getchar();a[n]=ch;while(ch!='@'&&n<maxsize){ch=getchar();a[++n]=ch;}flag=Judge(a,n,&s);if(flag==0)printf("该算式括号不配对！");elseprintf("该算式括号配对。");return0;出色文档适用标准文案}2〔1〕#include<stdio.h>voidmove(charx,charz){printf("%c-->",x);printf("%c\n",z);}voidHanoi(intn,charx,chary,charz){if(n==1)move(x,z);else{Hanoi(n-1,x,z,y);move(x,z);Hanoi(n-1,y,x,z);}}intmain(){intm;出色文档适用标准文案printf("请你输入A上边的碟子总数");scanf("%d",&m);Hanoi(m,'A','B','C');return0;}出色文档适用标准文案四、实验结果与剖析〔程序运转结果及其剖析〕五、实验领会〔碰到问题及解决方法，编程后的心得领会〕出色文档适用标准文案实验工程名称：串实验学时：2同组学生姓名：实验地址：实验日期：实验成绩：批阅教师：批阅时间：出色文档适用标准文案实验4串一、实验目的和要求掌握串的储存及应用。二、实验仪器和设施三、实验内容与过程〔含程序清单及流程图〕1、必做题〔1〕编写输出字符串s中值等于字符ch的第一个字符的函数，并用主函数测试结果。〔2〕编写输出字符串s中值等于字符ch的全部字符的函数，并用主函数测试结果。解题思路：能够将第一题程序改进成一个子函数，在本题中循环调用。〔3〕设字符串采纳单字符的链式储存结构，编程删除串s从地点i开始长度为k的子串。2、选做题假定以链结构表示串，编写算法实现将串S插入到串T中某个字符以后，假定串T中不存在这个字符，那么将串S联接在串T的末端。提示：为提升程序的通用性，插入地点字符应设计为从键盘输入。程序清单：1〔1〕#include<stdio.h>#include<string.h>intSearch(chara[],charx){inti;for(i=0;i<strlen(a);i++)if(a[i]==x)returni;出色文档适用标准文案}intmain(){intlocation;charch;chars[50];gets(s);scanf("%c",&ch);location=Search(s,ch);printf("%d",location);}2〕#include<stdio.h>#include<string.h>voidSearch(chara[],charx){inti;for(i=0;i<strlen(a);i++)if(a[i]==x)printf("%d",i);}intmain()出色文档适用标准文案{charch;chars[50];gets(s);scanf("%c",&ch);Search(s,ch);}3〕#include<stdio.h>#include<stdlib.h>typedefstructlinknode{chardata;structlinknode*next;}linkstring;linkstring*Creatlink(linkstring*S){linkstring*p=NULL,*q=NULL;charch;ch=getchar();while(ch!='$'){出色文档适用标准文案p=malloc(sizeof(linkstring));p->data=ch;if(S==NULL)S=p,q=p;elseq->next=p,q=p;ch=getchar();}if(q->next!=NULL)q->next=NULL;returnS;}linkstring*Delete(linkstring*S,inti,intk)//假定字符串足够长{linkstring*p=S,*q;intm=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++;}returnS;}voidOutput(linkstring*S){linkstring*p=S;while(p!=NULL){出色文档适用标准文案printf("%2c",p->data);p=p->next;}}intmain(){linkstring*S=NULL;inti,k;S=Creatlink(S);Output(S);printf("\n");printf("Pleaseenterthelocationandthelength:");scanf("%d%d",&i,&k);S=Delete(S,i,k);getchar();Output(S);printf("\n");return0;}出色文档适用标准文案四、实验结果与剖析〔程序运转结果及其剖析〕五、实验领会〔碰到问题及解决方法，编程后的心得领会〕出色文档适用标准文案实验工程名称：二叉树实验学时：2同组学生姓名：实验地址：实验日期：实验成绩：批阅教师：批阅时间：出色文档适用标准文案实验5二叉树一、实验目的和要求1〕掌握二叉的生成，以及前、中、后序遍算法。2〕掌握用二叉遍思想解决的方法。二、实验仪器和设施三、实验内容与过程〔含程序清单及流程图〕1、必做〔1〕成立一棵二叉。此行前序遍、中序遍布后序遍，出遍序列。〔2〕在第一基上，求二叉中叶点的个数。〔3〕在第一基上，求二叉中点数。〔4〕在第一基上，求二叉的深度。2、做一棵完整二叉存于序表sa中，sa.elem[1⋯sa.last]存点的。写算法由此序存构成立二叉的二叉表。解思路：依据完整二叉序存的性来确立二叉的父子关系即“原〞了二叉，以后再依据二叉二叉表的结构方法行成立。完整二叉序存的一个重要性，第i个点的左孩子是号2i的点，第i个点的右孩子是号2i+1的点。程序清：1#include<stdio.h>#include<stdlib.h>#definemaxsize64typedefstructnode{chardata;structnode*lchild,*rchild;出色文档适用标准文案}bitree;bitree*Q[maxsize];bitree*Creattree(bitree*root,int*n){charch;intfront=1,rear=0;bitree*s;ch=getchar();while(ch!='$'){s=NULL;if(ch!='@'){s=malloc(sizeof(bitree));s->data=ch;s->lchild=NULL;s->rchild=NULL;(*n)++;}rear++;Q[rear]=s;if(rear==1)root=s;出色文档适用标准文案else{if(s&&Q[front]){if(rear%2==0)Q[front]->lchild=s;elseQ[front]->rchild=s;if(rear%2==1)front++;}}ch=getchar();}returnroot;}voidPreOrder(bitree*root){if(root){printf("%2c",root->data);PreOrder(root->lchild);PreOrder(root->rchild);}出色文档适用标准文案}voidInOrder(bitree*root){if(root){InOrder(root->lchild);printf("%2c",root->data);InOrder(root->rchild);}}voidPostOrder(bitree*root){if(root){PostOrder(root->lchild);PostOrder(root->rchild);printf("%2c",root->data);}}intleafnum(bitree*root){if(root==NULL)出色文档适用标准文案return0;elseif(root->lchild==NULL&&root->rchild==NULL)return1;elsereturnleafnum(root->lchild)+leafnum(root->rchild);}intmain(){intn0,n=0;bitree*root=NULL;root=Creattree(root,&n);PreOrder(root);//前序遍历printf("\n");InOrder(root);//中序遍历printf("\n");PostOrder(root);//后序遍历printf("\n");n0=leafnum(root);printf("叶子节点总数是：%d\n",n0);printf("节点总数是%d\n",n);return0;}出色文档适用标准文案四、实验结果与剖析〔程序运转结果及其剖析〕出色文档适用标准文案五、实验领会〔碰到问题及解决方法，编程后的心得领会〕出色文档适用标准文案实验工程名称：图实验学时：2同组学生姓名：实验地址：实验日期：实验成绩：批阅教师：批阅时间：出色文档适用标准文案实验6图一、实验目的和要求1〕娴熟掌握图的根本观点、结构及其储存结构。2〕娴熟掌握对图的深度优先搜寻遍历和广度优先搜寻遍历的算法。二、实验仪器和设施三、实验内容与过程〔含程序清单及流程图〕1、必做题1〕结构一个无向图〔用毗邻矩阵表示储存结构〕。2〕对上边所结构的无向图，进行深度优先遍历和广度优先遍历，输出遍历序列。2、选做题采纳毗邻表储存结构，编写一个鉴别无向图中随意给定的两个极点之间能否存在一条长度为k的简单路径的算法。简单路径是指其极点序列中不含有重复极点的路径。提示：两个极点及k值均作为参数给出。程序清单：1．#include<stdio.h>#defineN3#defineM5typedefstruct{chardata[N];intlocation[N][N];}graph;voidCreatgraph(graph*g)//成立无向图出色文档适用标准文案{inti,j,k;intw;for(i=0;i<N;i++)g->data[i]=getchar();for(i=0;i<N;i++)for(j=0;j<N;j++)g->location[i][j]=0;for(k=0;k<M;k++){scanf("%d%d%f",&i,&j,&w);g->location[i][j]=w;g->location[j][i]=w;}}intvisited[N]={0};voidDFS(graph*g,inti)//深度优先遍历无向图{intj;printf("node:%c\n",g->data[i]);visited[i]=1;for(j=0;j<N;j++)出色文档适用标准文案if((g->location[i][j]==1)&&(!visited[j]))DFS(g,j);}voidBFS(graph*g,inti)//广度优先遍历{intj;printf("%d",g->data[i]);visited[i]=1;for(j=0;j<N;j++){if(g->location[i][j]!=0&&visited[j]!=1)BFS(g,j);}}intmain(){graphg;Creatgraph(&g);DFS(&g,3);BFS(&g,3);printf("\n");return0;出色文档适用标准文案}出色文档适用标准文案四、实验结果与剖析〔程序运转结果及其剖析〕五、实验领会〔碰到问题及解决方法，编程后的心得领会〕出色文档适用标准文案实验工程名称：排序实验学时：2同组学生姓名：实验地址：实验日期：实验成绩：批阅教师：批阅时间：出色文档适用标准文案实验7排序一、实验目的和要求1〕熟掌握希排序、堆排序、直接插入排序、起泡排序、迅速排序、直接排序、并排序和基数排序的根本观点。2〕掌握以上各样排序的算法。划分以上不一样排序的、弊端。二、实验仪器和设施三、实验内容与过程〔含程序清单及流程图〕1、必做用随机数生10000个待排序数据元素的关字。以下各排序函数的机器行〔起码两个〕：直接插入排序、希排序〔增量4，2，1〕、冒泡排序、迅速排序、直接排序、二路并排序、堆排序。2、做假含n个的序列中，其所相关字介于v和w之的整数，且此中好多关字的是同样的。可按以下方法排序：另数number[v⋯w]，令number[i]关字整数i的个数，而后按number重排序列以抵达有序。写算法上述排序方法，并此种方法的弊端。程序清：①直接选择排序：#include<stdio.h>#include<stdlib.h>#include<time.h>#defineN1000voidCreatstring(inta[]){inti;intrand(void);出色文档适用标准文案srand(time(NULL));for(i=0;i<N;i++)a[i]=rand()%N;}voidOutputstring(inta[]){inti;for(i=0;i<N;i++){printf("%4d",a[i]);if((i+1)%20==0)printf("\n");}}voidSortstring(inta[])//排序{inti,j,temp;intk;for(i=0;i<N-1;i++){k=i;for(j=i+1;j<N;j++){出色文档适用标准文案if(a[j]<a[k])k=j;}if(i!=k){temp=a[i];a[i]=a[k];a[k]=temp;}}}intmain(){inta[N];Creatstring(a);Outputstring(a);printf("\n");Sortstring(a);Outputstring(a);return0;}②冒泡排序：voidSortstring(inta[])出色文档适用标准文案{inti,j,t,flag;for(i=0;i<N-1;i++){flag=1;for(j=N-1;j>i;j--)if(a[j-1]>a[j]){t=a[j-1];a[j-1]=a[j];a[j]=t;flag=0;}if(flag)break;}}四、实验结果与剖析〔程序运转结果及其剖析〕出色文档适用标准文案五、实验领会〔碰到问题及