数据结构实验指导书

1、2010王中国 编南阳师范学院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+;

3、main() 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(nod

4、e); 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;seq

6、stack;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

7、 x;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(sqqueu

9、e *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=qdataqfr

10、ont; 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)

11、return (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程序设计编写。四、 实验学时：

12、2学时五、 实验步骤：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

15、vertextype; /*顶点类型设为字符型*/ 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-ie

17、dgesij=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; i

18、nt 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.len

21、gth; 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); f

22、or(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

23、,x.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);

24、printf( %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;i

25、nt 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

26、(p=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

28、 delete); 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%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-elem