数据结构试验指导书.doc

《数据结构试验指导书.doc》由会员分享，可在线阅读，更多相关《数据结构试验指导书.doc（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构实验指导及报告书 / 学年 第 学期姓 名：_学 号：_班 级：_指导教师：_计算机科学与工程学院2009实验一 顺序表与链表一、实验目的1、掌握线性表中元素的前驱、后续的概念。2、掌握顺序表与链表的建立、插入元素、删除表中某元素的算法。3、对线性表相应算法的时间复杂度进行分析。4、理解顺序表、链表数据结构的特点（优缺点）。 二、实验内容和要求1、阅读下列两个函数，写出函数的基本功能。并运行程序，写出结果。#define m 100typedef struct int elemm; int len;sqlist;void creatsqlist(sqlist *l) 基本功能：_int

2、 i; scanf(%dn,&l-len); for(i=0;ilen;i+) scanf(%d,&l-elemi);void ins(sqlist *l,int k) 基本功能：_int j; for(j=l-len-1;j=k;j-) l-elemj+1=l-elemj; l-elemk=99; l-len+;int main() int i; sqlist *l,L; l=&L; creatsqlist(l); for(i=0;ilen;i+) printf(%dn,l-elemi); printf(n); ins(l,2); for(i=0;ilen;i+) printf(%3d,l-

3、elemi);return 0;l 算法分析与运行结果2、为第1题补充查找功能函数，根据给定的元素值，返回查找的结果：若找到则返回下标，未找到则返回1。l 算法代码3、阅读下列两个函数，写出函数的基本功能。并运行程序，写出结果。typedef struct lnodeint data; struct lnode *next; node,*nodeptr;nodeptr creat() 基本功能：_nodeptr l,p,q; int i ,n,e; l=(nodeptr)malloc (sizeof(node); q=l; q-next=0; scanf(%d,&n); for(i=1;ida

4、ta=e; q-next=p; q=p; q-next=0; return l;void out(nodeptr l) 基本功能：_nodeptr p; p=l-next; while(p) printf(%3d,p-data);p=p-next;int main() nodeptr l; l=creat(); out(l); l 算法分析与运行结果4、为第3题补充插入功能函数和删除功能函数。l 算法代码以下为选做实验：5、循环链表的应用（约瑟夫回环问题）n个数据元素构成一个环，从环中任意位置开始计数，计到m将该元素从表中取出，重复上述过程，直至表中只剩下一个元素。提示：用一个无头结点的循环单

5、链表来实现n个元素的存储。l 算法代码6、设一带头结点的单链表，设计算法将表中值相同的元素仅保留一个结点。提示：指针p从链表的第一个元素开始，利用指针q从指针p位置开始向后搜索整个链表，删除与之值相同的元素；指针p继续指向下一个元素，开始下一轮的删除，直至pnull为至，既完成了对整个链表元素的删除相同值。l 算法代码三、实验小结四、教师评语实验二 栈和队列一、实验目的1、掌握栈的结构特性及其入栈，出栈操作；2、掌握队列的结构特性及其入队、出队的操作，掌握循环队列的特点及其操作。二、实验内容和要求1、阅读下列函数，写出函数的基本功能。并运行程序，写出结果。#define Stack_Size

6、50typedef structint elemStack_Size;int top;SeqStack;int push(SeqStack *S, int x) 基本功能：_ if(S-top=Stack_Size-1) return(0); S-top+; S-elemS-top=x; return(1);int pop(SeqStack *S, int *x) 基本功能：_ if(S-top=-1) printf(stack empty); return(0); else *x=S-elemS-top; S-top-; return(1); void prin(SeqStack *x) 基

7、本功能：_int i;printf(n);for(i=0;itop;i+)printf( %d ,x-elemi);int main()SeqStack x;int i,a;x.top=-1;for(i=0;i=5;i+) push(&x,i*2);prin(&x);prin(&x);for(i=0;i=2;i+)pop(&x,&a);printf(pop: %d,a);prin(&x);return 0; l 算法分析与结果2、阅读并运行下面算法程序，并分析算法功能及运行结果。#include#define m 20#define elemtype chartypedef structele

8、mtype stackm;int top;stacknode;stacknode *sp;init(stacknode *st)st-top=0;return;void push(stacknode *st,elemtype x)if(st-top=m)printf(the stack is overflow!n);elsest-top=st-top+1;st-stackst-top=x;void pop(stacknode *st)st-top=st-top-1;int main()char sm;int i,k;printf(create a empty stack!n);sp=mallo

9、c(sizeof(stacknode);init(sp);printf(input a expression:n);gets(s);for(i=0;itop=0)printf(match)!n);elseprintf(not match)!n);return 0;l 算法分析及运行结果3、利用栈，编写算法函数将给定的十进制数转换为八进制。l 算法实现代码以下为选做实验：4、正读和反读都相同的字符序列为“回文”，例如，“abcddcba”、 “qwerewq”是回文，“ashgash”不是回文。试写一个算法判断读入的n个字符的字符序列是否为回文。要求利用栈或队列完成。l 算法实现代码三、实验小结

10、四、教师评语实验三 串的模式匹配一、实验目的1、了解串的基本概念2、了解串的模式匹配的基本算法的实现 二、实验内容和要求1、阅读并运行下面程序，分析算法的基本功能。#define m 100typedef structchar chm;int len;sqstr;void creat(sqstr *s)scanf(%s,s-ch);s-len=strlen(s);int index(sqstr s,sqstr t) int i=0,j=0; while(is.len&jt.len) if(s.chi=t.chj) i+;j+; else i=i-j+1;j=0; if(j=t.len) ret

11、urn (i-j+1); else return(-1);int main() int a; sqstr S,T,*s=&S,*t=&T; creat(s); creat(t); a=index(S,T); printf(%d,a);return 0;l 算法分析及运行结果2、实现串的模式匹配的KMP算法l 算法实现代码三、实验小结四、教师评语实验四 二叉树一、实验目的1、掌握二叉树的基本特性2、掌握二叉树的递归遍历算法 3、理解二叉树的非递归算法4、通过二叉树的深度和层次遍历算法，理解二叉树的基本特性 二、实验内容和要求1、阅读并运行下面二叉树的基本操作算法。/*二叉链表基本算法*/#inc

12、lude #include #include #define null NULLtypedef struct BTNode /*节点结构声明*/int data ; /*节点数据*/struct BTNode *lchild;struct BTNode *rchild ; /*指针*/*BiTree;void createBiTree(BiTree *t); /*先序建立二叉链表*/void preorder(BiTree t); /*二叉链表先序遍历递归算法*/void inorder(BiTree t); /*二叉链表中序遍历递归算法*/void postorder(BiTree t);

13、/*二叉链表后序遍历递归算法*/void release(BiTree t); /*释放二叉链表算法*/int main() BiTree root=null;createBiTree(&root);printf(nPreOrder Traverse:);preorder(root);printf(nInOrder Traverse:);inorder(root);printf(nPostOrder Traverse:);postorder(root); release(root);return 0;void createBiTree(BiTree *t)int s;BiTree q;prin

14、tf(nplease input data:(exit for 0);scanf(%d,&s);if(s=0)*t=null; return;q=(BiTree)malloc(sizeof(struct BTNode);if(q=null) printf(Memory alloc failure!); exit(0);q-data=s;*t=q;createBiTree(&q-lchild);createBiTree(&q-rchild);void preorder(BiTree t)if(t!=null) printf(%d ,t-data);preorder(t-lchild);preor

15、der(t-rchild);void inorder(BiTree t)if(t!=null)inorder(t-lchild);printf(%d ,t-data);inorder(t-rchild);void postorder(BiTree t)if(t!=null)postorder(t-lchild);postorder(t-rchild);printf(%d ,t-data);void release(BiTree t) if(t!=null) release(t-lchild); release(t-rchild); free(t); l 算法分析与运行结果2、参考第1题，写出并

16、实现求二叉树深度的算法。l 算法实现代码3、参考第1题，写出并实现层次遍历二叉树的算法。l 算法实现代码以下为选做实验：4、写出并实现统计二叉树叶子结点个数的算法。l 算法实现代码三、实验小结四、教师评语实验五 图的表示及遍历一、实验目的1、掌握图的表示方法2、掌握图的两种遍历算法 二、实验内容和要求1、阅读下面程序，分析算法并写出运行结果。#define MaxVertexNum 100 /*最大顶点数设为100*/typedef char VertexType; /*顶点类型设为字符型*/typedef int EdgeType; /*边的权值设为整型*/typedef struct Ve

17、rtexType vexsMaxVertexNum; /*顶点表*/EdgeType iedgesMaxVertexNumMaxVertexNum; /*邻接矩阵，即边表*/ int n,e; /*顶点数和边数*/Mgraph; /*Maragh是以邻接矩阵存储的图类型*/int visited100;void BFSM(Mgraph *G,int k);void CreateMGraph(Mgraph *G)/*建立无向图G的邻接矩阵存储*/ int i,j,k,w; char ch; printf(请输入顶点数和边数(输入格式为:顶点数,边数):n); scanf(%d,%d,&(G-n)

18、,&(G-e);/*输入顶点数和边数*/ printf(请输入顶点信息(输入格式为:顶点号):n); for(i=0;in;i+) scanf(n%c,&(G-vexsi); /*输入顶点信息，建立顶点表*/ for(i=0;in;i+) for(j=0;jn;j+) G-iedgesij=0; /*初始化邻接矩阵*/ printf(请输入边顶点的序号(输入格式为:i,j):n); for (k=0;ke;k+) scanf(n%d,%d,&i,&j); /*输入e条边，建立邻接矩阵*/ G-iedgesij=1; G-iedgesji=1; /*CreateMGraph*/void BFST

19、raverseAL(Mgraph *G)/*广度优先遍历以邻接矩阵存储的图G*/ int i; for (i=0;in;i+) visitedi=0; /*标志向量初始化*/ for (i=0;in;i+)if (!visitedi) BFSM(G,i); /* vi未访问过，从vi开始BFS搜索*/ /*BFSTraverseAL*/void BFSM(Mgraph *G,int k) /*以Vk为出发点，对邻接矩阵存储的图G进行BFS搜索*/int i,j;int Q100,front,rear;front=rear=0;printf(visit vertex:V%cn,G-vexsk);

20、 /*访问原点Vk*/visitedk=1;/*1代表true*/Qrear=k;rear=rear+1; /*原点Vk入队列*/while (rear!=front) i= Qfront;front+; /*Vi出队列*/for (j=0;jn;j+) /*依次搜索Vi的邻接点Vj*/ if (G-iedgesij=1 & !visitedj) /*若Vj未访问*/ printf(visit vertex:V%cn,G-vexsj); /*访问Vj */visitedj=1;Qrear=j;rear+; /*访问过的Vj入队列*/ /*BFSM*/int main()Mgraph tu;Cr

21、eateMGraph(&tu);BFSTraverseAL(&tu);return 0;l 算法分析与运行结果2、设计学校的校园平面图，所含场所不少于10个。以图中顶点表示校内各场所，存放场所名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息，并用邻接矩阵或邻接表存储。l 算法实现代码三、实验小结四、教师评语实验六 内部排序算法一、实验目的1、掌握内部排序的基本算法2、分析比较内部排序算法的效率 二、实验内容和要求实现下列各个排序算法，要求输出每趟排序的中间结果和最终排序结果。1、插入排序l 算法实现代码2、冒泡排序l 算法实现代码3、选择排序l 算法实现代码以下为选做实验：4、希尔

22、排序l 算法实现代码5、快速排序l 算法实现代码6、堆排序l 算法实现代码三、实验小结四、教师评语实验七 查找一、实验目的1掌握查找表、动态查找表、静态查找表和平均查找长度的概念。2掌握线性表中顺序查找和折半查找的方法。3学会哈希函数的构造方法，处理冲突的机制以及哈希表的查找。二、实验内容和要求1.、静态查找表技术依据顺序查找算法和折半查找算法的特点，对下面的两个整数数组选择一个合适的算法，设计出完整的C源程序。要求设计的程序能观察每一次查找的结果。数组1 ： 8 ，15 ，19 ，26 ，33 ，41 ，47 ，52 ，64 ，90 ，查找key = 41数组2 ： 12 ，76 ，29 ，15 ，62 ，35 ，33 ，89 ，48 ，20 ，查找key =35l 算法实现代码2、哈希表的查找在构造好的哈希表中实现对某一个元素的查找。【要求】如果查找成功，在返回的信息中指示查找元素的数值、地址和查找的次数，并返回1，查找失败返回0。l 算法实现代码三、实验小结四、教师评语