太原理工大学数据结构实验报告.doc

线性构造一、实验目的和要求本次实习的主要目的是为了使学生熟练掌握线性表的根本操作在顺序存储构造和链式存储构造上的实现，提高分析和解决问题的能力。要求仔细阅读并理解以下例题，上机通过，并观察其结果，然后独立完成后面的实习题。二、实验容和原理习题问题描述 设顺序表A中的数据元素递增有序，试写一程序，将*插入到顺序表的适当位置上，使该表仍然有序。输入顺序表的长度，初始化顺序表数据，插入数据*。输出已建立顺序表，输出插入*后的顺序表。存储构造采用顺序存储构造算法的根本思想建立顺序表用数组的形式实现。在表中从后往前查找要插入元素的位置，直到查找到第一个比*小的数，并从表的最后一元素依次后移，把要插入元素插入搜查找位置。三、主要仪器设备使用的计算机惠普：硬件配置Win7、软件环境win-TC四、操作方法与实验步骤习题源程序*include"stdio.h"*define MA*SIZE 100*define RIGHT 1*define ERROR 0typedef int ElemType;typedef struct ElemType elemMA*SIZE; int last;SeqList; void Initlist(SeqList *L) L->last=-1;void putseqList(SeqList *L,int n) int i; for(i=0;i<n;i+) scanf("%d",&(L->elemi); L->last=L->last+n; int LenList(SeqList *L) int Len; Len=L->last+1; return Len;int PositionList(SeqList *L,int *) int j; for(j=0;j<=L->last;j+) if(*<L->elemj) return j+1; return (L->last+1);int InsList(SeqList *L,int i,int e) int k; if(i<1)|(i>L->last+2) printf("the position is wrong"); return(ERROR); if(L->last>=MA*SIZE-1) printf("the list is full"); return(ERROR); for(k=L->last;k>=i-1;k-) L->elemk+1=L->elemk; L->elemi-1=e; L->last+; return(RIGHT);int OutputSeqList(SeqList *L) int i; for(i=0;i<=L->last;i+) printf("%d,",L->elemi); return(L->elemi);void main() int s,c; SeqList L; Initlist(&L); printf("please input the length: "); scanf("%d",&s); printf("please input the list: "); putseqList(&L,s); LenList(&L); printf("Please input an element to insert : "); scanf("%d",&c); InsList(&L,PositionList(&L,c),c); OutputSeqList(&L); printf("n"); getch();五、实验数据记录和处理六、实验结果与分析 此程序的优点是算法简单，易于实现。但是由于采用的是顺序存储的形式，导致算法的时间性能和空间性能不是很好，而且本程序的的强健性不是很好，对空间不够的情况没有很人性化的提出解决方案。七、讨论、心得改良思想：*define LIST_INIT_SIZE 100typedef struct int *elem;int length;int listsize;sqlist;void creat_sqlist(sqlist *p)int i,l;p->elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int);if(!p->elem)printf("OVERFLOW");e*it(1);printf("Please input length:n");scanf("%d",&l);p->length=l;p->listsize=LIST_INIT_SIZE;printf("Input sqlist:n");for(i=0;i<p->length;i+)scanf("%d",&p->elemi);for(i=0;i<p->length;i+)printf("%d ",p->elemi);printf("n");这是对顺序表构造的局部改良，同时可以将数据的存储改成链表的形式。心得体会：通过本次试验让我对顺序表有了更深层次的了解，同时也对顺序表和链表的区别有了自己的见解。树形构造一、实验目的和要求熟悉树的各种表示方法和各种遍历方式，掌握有关算法的实现，了解树在计算机科学及其它工程技术中的应用。2、 实验容和原理习题问题描述编写递归算法，计算二叉树中叶子结点的数目。输入一棵二叉树的结点假设无子树，则可将其子树看作“.，输入时，按照前序序列的顺序输入该结点的容。对以以下图，其输入序列为ABD.EH.CF.I.G.。A B CD E F G H I输出二叉树中叶子结点的个数存储构造采用二叉链表存储。算法的根本思想求二叉树中叶子结点个数，即求二叉树的所有结点中左、右子树均为空的结点个数之和。可以将此问题转化为遍历问题，在遍历中“访问一个结点时判断该结点是不是叶子，假设是则将计数器累加。三、主要仪器设备使用的计算机惠普：硬件配置Win7、软件环境win-TC四、操作方法与实验步骤习题源程序*include<stdio.h>struct BiTreechar data; struct BiTree *lchild; struct BiTree *rchild;struct BiTree* CreatBiTree()char *; struct BiTree* p; scanf("%c",&*); if(*!='.') p=(struct BiTree*)malloc(sizeof(struct BiTree); p->data=*; p->lchild=CreatBiTree(); p->rchild=CreatBiTree(); else p=NULL; return p;int LeafNum(struct BiTree *T) if(!T) return 0; else if(!T->lchild&&!T->rchild) return 1; else return LeafNum(T->lchild)+LeafNum(T->rchild);int main() int num; struct BiTree* T; printf("Please input the tree(pre):n"); T=CreatBiTree(); while(T=NULL) printf("empoty,again:n"); T=CreatBiTree(); num=LeafNum(T); printf("nthe sum of leaf is:%dn",num); getch();五、实验数据记录和处理六、实验结果与分析 实验程序采用了二叉链表作为存储构造方便了递归函数的进展。此外由于数的定义采用了递归的形式，所以关于数的构造、遍历、以及其他运算采用递归形式，使得程序的可阅读性增强。7、 讨论、心得改良思想：void CountLeaf(Bitree T, int &cout)if(T) if(!T->lchild)&&(!T->rchild) count+;CountLeaf(T->lchild,count);CountLeaf(T->rchild,count); 采用C+的引用形式，可以对叶子结点的程序上进展修正，使其看起来更为简练。心得体会： 通过实验操作，了解到了数的递归定义的优点，以及对于程序算法上的思想指导。同时，也对数的不同存储形式有了了解。图构造一、实验目的和要求熟悉图的存储构造，掌握有关算法的实现，了解图在计算机科学及其他工程技术中的应用。二、实验容和原理习题【问题描述】 试基于图的深度优先搜索策略编写一程序，判别以邻接表方式存储的有向图中是否存在有顶点Vi到Vj顶点的路径ij。【输入】图的顶点个数N，以及以V1、V2、V3、V4为弧尾的所有的弧，并以-1完毕。还有你要判断是否连通的两个顶点。【输出】假设A到B无路径，则输出“不是连通的,否则输出A到B路径上各顶点。【存储构造】图采用邻接矩阵的方式存储。【算法的根本思想】 采用深度优先搜索的方法，从顶点A开场，依次访问与A邻接的顶点VA1,VA2,.,VAK, 访问遍之后,假设没有访问B，则继续访问与VA1邻接的顶点VA11,VA12,.,VA1M，再访问与VA2邻接顶点.，如此下去，直至找到B，最先到达B点的路径，一定是边数最少的路径。实现时采用队列记录被访问过的顶点。每次访问与队头顶点相邻接的顶点，然后将队头顶点从队列中删去。假设队空，则说明到不存在通路。在访问顶点过程中，每次把当前顶点的序号作为与其邻接的未访问的顶点的前驱顶点记录下来，以便输出时回溯。三、主要仪器设备使用的计算机惠普：硬件配置Win7、软件环境win-TC四、操作方法与实验步骤习题源程序*include"stdio.h"int n;struct VNode int position; struct VNode* ne*t;struct Arode int mark; struct VNode* first;void DFS(struct Arode* v,struct Arode* w) struct VNode* L; w->mark=1; L=w->first; while(L!=NULL) if(v+(L->position)->mark=0) DFS(v,(v+L->position); L=L->ne*t; int main() int i,j,k; int key1,key2; int num=0; struct Arode* p; struct VNode* temp; struct VNode* flag; printf("you *iang tu de ding dian:n"); scanf("%d",&n); while(n<1) printf("shu ru cuo wu,again:n"); scanf("%d",&n); p=(struct Arode*)malloc(n*sizeof(struct Arode); for(i=0;i<n;i+) printf("shu ru V%dn",i+1); scanf("%d",&k); if(k=-1) pi.mark=0; pi.first=NULL; else temp=(struct VNode*)malloc(sizeof(struct VNode); temp->position=k; temp->ne*t=NULL; pi.first=temp; pi.mark=0; flag=temp; scanf("%d",&k); while(k!=-1) temp=(struct VNode*)malloc(sizeof(struct VNode); temp->position=k; temp->ne*t=NULL; flag->ne*t=temp; flag=temp; scanf("%d",&k); printf("shu ru liang dian de wei zi:n"); printf("n"); scanf("%d%d",&key1,&key2); DFS(p,(p+key1); if(pkey2.mark=1) printf("V%dV%dn",key1+1,key2+1); else pkey1.mark=0; DFS(p,(p+key2); if(pkey1.mark=1) printf("V%dV%d lian tongn",key1+1,key2+1); else printf("V%dV%d bu lian tongn",key1+1,key2+1); system("pause"); return 0; getch();五、实验数据记录和处理六、实验结果与分析 图构造是一个复杂的构造，在建立图和对图进展深度优先遍历是程序执行的关键步骤其时间复杂度为0n²七、讨论、心得 这次试验的程序在输入上有很高的要求，比方例题的输入是要输入不带权值的图构造，也就是说有关系用1表示，没关系用0表示。查找一、实验目的和要求通过本次实验，掌握查找表上的有关查找方法，并分析时间复杂度。二、实验容和原理习题【问题描述】将折半查找算法改写成递归算法。【输入】输入有序表【输出】要查找元素的位置【存储构造】数组存储。【算法的根本思想】将n个元素分成个数大致一样的两半，取an/2与欲查找的*作比拟，如果*=an/2则找到*，算法终止。如果*<an/2，则我们只要在数组a的左半部继续搜索*这里假设数组元素呈升序排列。如果*>an/2，则我们只要在数组a的右半部继续搜索*。递归调用这个算法。三、主要仪器设备使用的计算机惠普：硬件配置Win7、软件环境win-TC四、操作方法与实验步骤习题源程序*include"stdio.h"typedef struct int a30; int length;sqtable;sqtable st;int b=0;void createst(int k) int i; printf("Please input data:"); st.a0=-100; for (i=1;(!b&&(i<=k);i+) scanf("%d",&(st.ai); if (st.ai<st.ai-1) printf("Input data error.n"); b=1; if (!b) st.length=k; printf("The table is builted.n"); int stfind(sqtable st,int l,int h,int y) int m; while (l<=h) m=(l+h)/2; if (y=st.am) return m; else if (y<st.am) return stfind(st,l,m-1,y); else return stfind(st,m+1,h,y); main() int n,*,l,h,s; l=1; h=st.length; printf("nPlease input n:"); scanf("%d",&n); createst(n); h=st.length; if (b=0) printf("Please input you want find value:"); scanf("%d",&*); s=stfind(st,l,h,*); printf("Find %d in position %d.n",*,s); getch();五、实验数据记录和处理六、实验结果与分析程序表达了折半算法优越性，它比顺序查找的时间性能更为优越。其平均查找长度为ASL=(n+1)/n*log(n+1)-1七、讨论、心得改良思想：*include "stdio.h"*include "conio.h"*include "alloc.h"*define n 14int count=0;int bin_search(int a,int low,int high,int *) int mid; count+; if(low>high) return -1; else mid=(low+high)/2; if(*=amid) return mid; else if(*<amid) return bin_search(a,low,mid-1,*); else return bin_search(a,mid+1,high,*); main() int s,i,*; int an; printf("Input 14 numbers:n"); for(i=0;i<n;i+) scanf("%d",&ai); printf("Input a number that you want to search:n"); scanf("%d",&*); s=bin_search(a,0,13,*); if(s=-1) printf("failn"); printf("cha *u %d cin",count); else printf("cha zhao %d cin",count); printf("cha zhao *ia biao shi: %d n",s); getch();心得体会： 通过本次试验对查找有了深刻的了解，认识到不同查找方法的区别和不同的优势。同时对折半查找算法的思想有了很深的认识。排序一、实验目的和要求通过本次实验，掌握线性表的排序方法，并分析时间复杂度。二、实验容和原理问题描述 对于N个关键字取整数的记录进展整序，以使所有关键字为非负数的记录排在关键字为负数的记录之前，要求使用最少的附加空间，且算法的时间复杂度为O(N)。输入一组数据。输出非负数排在负数之前。存储构造顺序存储。算法的根本思想由于问题仅要求非负数排在负数之前，所以提取非负数插在前面即可。三、主要仪器设备使用的计算机惠普：硬件配置Win7、软件环境win-TC4、 操作方法与实验步骤习题源程序*include"stdio.h"void Sort(int* a,int m) int i=0; int j=m-1; int t; while(i<=j) while(i<m&&ai>=0) i+; while(j>=0&&aj<0) j-; if(i<j) t=ai; ai=aj; aj=t; i+; j-; int main() int n,i; int* p; printf("you have how many data want to input:n"); scanf("%d",&n); while(n<2) printf("you input data is wrong,please input again:n"); scanf("%d",&n); p=(int*)malloc(n*sizeof(int); printf("input data:n"); for(i=0;i<n;i+) scanf("%d",&pi); Sort(p,n); printf("after order data is:n"); for(i=0;i<n;i+) printf("%-4d",pi); printf("n"); system("pause"); return 0; getch();5、 实验数据记录和处理六、实验结果与分析 此程序的优点是算法简单，便于操作和理解其缺点是空间复杂度不是很好。时空性能都为O(N)。七、讨论、心得 对于本次试验程序而言，采用链表形式更可以提高算法的性能，减少空间复杂度。同时，通过本次试验，对查找思想有了更深刻的了解。