《数据结构实验指导书.doc》由会员分享，可在线阅读，更多相关《数据结构实验指导书.doc（22页珍藏版）》请在三一办公上搜索。
1、10王中国 编南阳师范学院2010-2-20数据结构实验指导书数据结构实验指导书数据结构实验指导书2实验一 时间复杂度计算3实验二 线性表的基本操作4实验三 栈与队列的基本操作6实验四 数组的基本操作9实验五 树的基本操作11实验六 图的基本操作13实验七 查找的基本操作15实验八 排序的基本操作20实验一 时间复杂度计算一、 实验目的：1. 掌握使用Turbo C2.0上机调试线性表的基本方法；2. 熟练掌握C语言的指针和结构体相关知识点；3. 理解数据结构的基本概念；4. 掌握时间复杂度的计算方法。二、 实验内容：1. 熟悉实验用的C语言上机环境；2. 计算程序中指定的语句的执行频率，计算
2、时间复杂度。三、 实验要求：1. 编程实现对第一章绪论中的编程项目1、2、3、4个题目的时间复杂度运算；2. 记录程序的运行结果，并结合程序进行分析；3. 编写程序计算下列语句中“x+”的执行频率并将结果输出。x+;for(int i=1;i=n;i+) x+;for(int i=1;i=n;i+)for(int j=1;jlen); 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+;ma
3、in() int i; sqlist *l,L; l=&L; clrscr(); creatsqlist(l); for(i=0;ilen;i+) printf(%dn,l-elemi); printf(n); ins(l,2); for(i=0;ilen;i+) printf(%3d,l-elemi);(2)程序如下：typedef struct lnode int data; struct lnode *next; node,*nodeptr;nodeptr creat() nodeptr l,p,q; int i ,n,e; l=(nodeptr)malloc (sizeof(node)
4、; q=l; q-next=0; scanf(%d,&n); for(i=1;idata=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;main() nodeptr l; l=creat(); out(l); 实验三 栈与队列的基本操作一、 实验目的：1. 握栈与队列的基本概念；2. 掌握顺序栈的建立、入栈和出栈等方法；3. 掌握循环队列的概念和建立、入队出队方法；4. 了解链栈、链队的概念及有关操作。二、 实验
5、内容：1. 完成栈的基本操作；2. 完成队列的建立、入队和出队操作。三、 实验要求：1. 认真阅读、掌握和上机运行本实验的程序；2. 记录程序的运行结果，并结合程序进行分析；3. 参照示例程序，完成相应功能的C程序设计编写。四、 实验学时：2学时五、 实验步骤：1 实验准备：(1) 针对第二章课后编程项目的第1-4题，完成编程；(2)阅读实验步骤中的函数，写出函数功能；2 拓展练习：阅读下列程序，写出各子函数功能和程序运行结果，再上机调试运行。(1)栈的基本运算#define Stack_Size 50typedef structint elemStack_Size;int top;SeqSt
6、ack;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); prin(SeqStack *x)int I;printf(n);for(I=0;Itop;I+)printf( %d ,x-elemI);main()SeqStack x
7、;int I,a;clrscr();x.top=-1;for(I=0;I=5;I+) push(&x,I*2);prin(&x);prin(&x);for(I=0;I0) x=N%2; push(&S,x); N=N/2; while(S.top!=-1) pop(&S,&x); printf(%d,x); main() int x; clrscr();scanf(%d,&x);Conversion(x); (3)队列的基本运算3队列的基本运算#define qsize 50typedef structint data50; int front,rear; int len; sqqueue;
8、int inqueue(sqqueue *q,int x) if(q-len)=50) printf(queue overflow);return 0; q-len+; q-dataq-rear=x; q-rear=(q-rear+1)%qsize; return(1); int dequeue(sqqueue *q) int temp; if(q-len=0) printf(queue underflow);return(0); temp=q-dataq-front; q-len-; q-front=(q-front+1)%qsize; return(temp); prin(sqqueue
9、*q) int i; printf(n); for(i=q-front;i!=q-rear;i=(i+1)%qsize) printf( %d,q-datai); main()sqqueue sq;int I;clrscr();sq.len=0;sq.front=0;sq.rear=0;for (I=0;Ilen+; qdataqrear=x; qrear=(qrear+1)%queuesize;int dequeue(sqqueue *q) int temp; if(queueempty(q) printf(“queue underflow”);return; temp=qdataqfron
10、t; qlen-; qfront=(qfront+1)%queuesize; return temp; prin(sqqueue *q)int I;for(I=q-front;I!=q-rear;I+)printf(“ %d”,q-datai);main()squeue sq;int I;sq.len=0;for (I=0;Ich);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) re
11、turn (i-j+1); else return(-1);main() int a; sqstr S,T,*s=&S,*t=&T; creat(s); creat(t); a=index(S,T); printf(%d,a); 要求写出源程序。写出运行结果。实验五 数组的基本操作一、 实验目的：1. 清楚一维数组、多维数组的定义格式及下标范围；2. 学习利用数组解决简单应用问题；二、 实验内容：1. 数组的建立和操作；三、 实验要求：1. 认真阅读、掌握和上机运行本实验的程序；2. 记录程序的运行结果，并结合程序进行分析；3. 参照示例程序，完成相应功能的C程序设计编写。四、 实验学时：2学
12、时五、 实验步骤：1 实验准备：(1)完成教材第五章课后编程项目的第1-3题；(2)阅读实验步骤中的函数，写出函数功能；2 阅读下列程序，写出各子函数功能和程序运行结果，再上机调试运行。(1) 下面的程序重新安排数组a中的元素，请读懂这个程序；void main() int a=2,3,-3,-5,6,-1,9,8,7,-7,-6,11; int SIZE=sizeof(a)/sizeof(a0); int I=-1,j=SIZE; while(+i -j) while (i0)i+; while (ij &aj0)j-; if(ij) int d=ai; ai=aj; aj=d; for (
13、int k=0;kdata=ch; T-lchild= CreatBiTree(); T-rchild= CreatBiTree(); return (T) ;void InOrderOut(BinTree T) /*中序输出二叉树的结点值*/ if (T) InOrderOut(T-lchild); printf(%3c,T-data); InOrderOut(T-rchild); main() BinTree bt; clrscr(); bt=CreatBiTree(); InOrderOut(bt);实验七 图的基本操作一、 实验目的：1. 掌握图的概念；2. 掌握图的邻接矩阵存储和邻接
14、表存储；3. 掌握图的遍历方法能运用。二、 实验内容：1. 验证图的基本操作；2. 画出步骤3的平面图，写出该图的邻接矩阵和邻接表，写出源程序。三、 实验要求：1. 完成教材第七章课后编程项目的1-2题；2. 记录程序的运行结果，并结合程序进行分析；3. 参照示例程序，完成相应功能的C程序设计编写。四、 实验学时：2学时五、 实验步骤：1 实验准备：(1)复习书上有关内容；(2)阅读源程序；(3)编写有关程序。2 拓展练习：阅读下列程序，写出各子函数功能和程序运行结果，再上机调试运行。#define MaxVertexNum 100 /*最大顶点数设为100*/ typedef char Ve
15、rtexType; /*顶点类型设为字符型*/ typedef int EdgeType; /*边的权值设为整型*/ typedef struct VertexType vexsMaxVertexNum; /*顶点表*/EdgeType iedgesMaxVertexNumMaxVertexNum; /*邻接矩阵，即边表*/ int n,e; /*顶点数和边数*/ Mgraph; /*Maragh是以邻接矩阵存储的图类型*/ void CreateMGraph(Mgraph *G) /*建立无向图G的邻接矩阵存储*/ int i,j,k,w; char ch; printf(请输入顶点数和边数
16、(输入格式为:顶点数,边数):n); scanf(%d,%d,&(G-n),&(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-iedg
17、esij=1; G-iedgesji=1; /*CreateMGraph*/ int visited100; void BFSTraverseAL(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*/ BFSM(Mgraph *G,int k) /*以Vk为出发点，对邻接矩阵存储的图G进行BFS搜索*/ int i,j; int
18、 Q100,front,rear; front=rear=0; printf(visit vertex:V%cn,G-vexsk); /*访问原点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 */
19、visitedj=1; Qrear=j;rear+; /*访问过的Vj入队列*/ /*BFSM*/main() Mgraph tu;CreateMGraph(&tu);BFSTraverseAL(&tu); 实验八 查找的基本操作一、 实验目的：1. 掌握顺序查找的算法；2. 掌握二分查找法；3. 掌握二叉排序树的基本操作。二、 实验内容：1. 验证二分查找法；2. 验证二叉排序树的基本操作。三、 实验要求：1. 认真阅读、掌握和上机运行本实验的程序；2. 记录程序的运行结果，并结合程序进行分析；3. 参照示例程序，完成相应功能的C程序设计编写。四、 实验学时：2学时五、 实验步骤：1 实验准
20、备：(1)完成教材第八章课后编程项目1-3题；(2)阅读源程序；(3)编写有关程序。2 拓展练习：阅读下列程序，写出各子函数功能和程序运行结果，再上机调试运行。typedef struct int elem100; int length; SSTable; int Searchs(SSTable s,int key) int i; s.elem0=key; for(i=s.length;s.elemi!=key;i-); return(i); int Search_Bin( SSTable ST, int key) int low, high,mid; low=1; high=ST.lengt
21、h; while(low=high) mid=(low+high)/2; if(ST.elemmid=key) return (mid); else if( keyST.elemmid) high=mid-1; else low=mid+1; return (0); main()SSTable x; int I,y,k;clrscr(); printf(请输入线性表的长度); scanf(%d,&x.length); printf(n请输入线性表的各个元素n); for(I=1;I=x.length;I+) scanf(%d,&x.elemI); printf(所建立的线性表为:n); for
22、(I=1;I=x.length;I+) printf( %d,x.elemI); printf(n请输入待查找的元素); scanf(%d,&k); y=Searchs(x,k); if (y)printf(有值为%d的元素，下标为%d,k,y); else printf(没有值为%d的元素,k); printf(nn以下验证折半查找，请建立一个有序表，输入线性表的长度); scanf(%d,&x.length); for(I=1;I=x.length;I+) x.elemI=I*4; printf(所建立的线性表为?n);for(I=1;I=x.length;I+) printf( %d,x
23、.elemI);printf(n请输入待查找的元素); scanf(%d,&k); y=Search_Bin(x,k); if (y)printf(n有值为%d的元素,下标为%d,k,y); else printf(n 没有值为%d的元素!,k);3 拓展练习：阅读下列二叉排序树的程序，写出各函数的功能及程序运行结果，再上机调试运行。#include typedef struct bnode int data; struct bnode *left,*right; bitree; void output(t) bitree *t; if (t!=NULL) output(t-left); pr
24、intf( %d,t-data); output(t-right); return; bitree *insert(bitree *t,bitree *s) bitree *p=t,*q; if (t=NULL) return s; while(p!=NULL) q=p; if (s-data=p-data) return t; else if (s-datap-data) p=p-right; else p=p-left; if(s-dataq-data) q-right=s; else q-left=s; return t; bitree *creat() bitree *t,*s;int
25、 k,i,n,dat;t=NULL;/*scanf(%d,&n);*/n=5;for(i=1;ileft=NULL;s-right=NULL; s-data=dat; t=insert(t,s); return t; int delete(bitree *t,int x) bitree *p=t,*q=NULL; while(p!=NULL) if(p-data=x) break; else if(p-datax) q=p;p=p-left; else q=p;p=p-right; if(p=NULL) return 0; if(p-left=NULL)&(p-right=NULL) if(p
26、=t) t=NULL; else if(p=q-left) q-left=NULL; else q-right=NULL; free(p); else if(p-left=NULL)|(p-right=NULL) if(p=t)if(p-left=NULL) t=p-right; else t=p-left; else if(p=q-left)&(p-left!=NULL) q-left=p-left; else if(p=q-left&p-right!=NULL) q-left=p-right; else if(p=q-right&p-left!=NULL) q-right=p-left;
27、else if(p=q-right&p-right!=NULL) q-left=p-right; free(p); else if(p-left!=NULL)|(p-right!=NULL) bitree *m=p,*n=p-left; while(n-right!=NULL) m=n;n=n-right; p-data=n-data; if(m=p) p-left=n-left; else m-right=n-left; free(n); return 1; main() bitree *t; t=creat(); output(t); delete(t,8); printf(after d
28、elete); output(t); 实验九 排序的基本操作一、 实验目的：1. 掌握简单排序的算法；2. 掌握希尔排序的算法3. 掌握快速排序的算法二、 实验内容：1. 验证简单排序算法；2. 验证冒泡排序算法；3. 写出快速排序算法的源程序。三、 实验要求：1. 认真阅读、掌握和上机运行本实验的程序；2. 记录程序的运行结果，并结合程序进行分析；3. 参照示例程序，完成相应功能的C程序设计编写。四、 实验学时：2学时五、 实验步骤：1 实验准备：(1)完成教材第九章课后编程项目的1、3、5、6题；(2)阅读源程序；(3)编写有关程序。2 拓展练习：阅读下列程序，写出各子函数功能和程序运行结
29、果，再上机调试运行。#define MAX 50 typedef struct int elemMAX+1; int length; relist; relist *crea() /*线性表的建立*/ relist *a;int i; a=(relist *)malloc(sizeof(relist); printf(请输入长度n); scanf(%d,&a-length); printf(请输入各元素n); for(i=1;ilength;i+) /*scanf(%d,&a-elemi);*/ a-elemi=10-i; printf(所建立的线性表为n); printf(a-length%
30、dn,a-length); for(i=1;ilength;i+) printf( %d,a-elemi); return(a); void insertSort(relist *L)/*直接插入排序*/ int i ,j; for(i=2; ilength; i+) if(L-elemielemi-1) L-elem0=L-elemi; /* 作为监视哨*/ for( j=i-1; L-elem0elemj;-j )L-elemj+1=L-elemj; /* 记录后移*/L-elemj+1=L-elem0; /* 插入 */ main() int i; relist *r; r=crea(); insertSort(r); printf(排序后的结果为n); for(i=1;ilength;i+) printf( %d,r-elemi); 3 拓展练习：下列算法是简单选择排序和起泡排序函数，请仔细阅读，改变成C语言函数再编制好主函数，然后上机调试。1）void SelectSort( relist *L)/*简单选择排序*/ int i,j,k,t;
