数据结构试验参考指导书.doc

目 录试验一 线性表1试验二 数组基础操作3试验三 队列基础操作5试验四 栈基础操作7试验五 二叉树操作树10试验六 图基础操作11数据结构试验指导书试验一 线性表一、试验目标：1、 掌握使用Turbo C2.0上机调试线性表基础方法；2、 掌握线性表基础操作：插入、删除、查找和线性表合并等运算在次序存放结构和链接存放结构上。二、试验环境：PC机、Turbo C 或 Visual C+三、试验描述：一元多项式相加四、试验要求：（1）建立两个一元多项式A、B，按指数降序排列。（2）实现A+B，输出其运算结果。五、试验步骤：（1） 用带头结点单链表存放多项式A、B，多项式类型定义以下： typedef struct /项表示，多项式项作为LinkList数据元素float coef ；/系数int expn； /指数term,ElemType;typedef struct Lnode ElemType data; Struct Lnode *next; *LinkList;typedef LinkList polynomial ； /用带头结点有序（按指数递增）单链表表示多项式（2） 基础操作：int cmp(term a,term b) /比较a于b指数，分别返回-1，0，1void CreatPolyn(polynomial &p,int m)/输入m项系数和指数，建立表示一元多项式有序单链表pvoid PrintPolyn(polynomal p)/输出多项式各项void AddPolyn(polynomial &pa, polynomial &pb)/多项式相加：pa=pa+pb，利用两个多项式结点组成“和多项式” （3） 程序步骤polynomal A,B; /定义多项式A，Bint m,n; /定义多项式A，B项数CreatPolyn(A,m); /创建有m项多项式A，PrintPolyn(A); /输出多项式A；CreatPolyn(B,n); /创建有n项多项式BPrintPolyn(B); /输出多项式BAddPolyn(A,B); /两个多项式相加A=A+BPrintPolyn(A); /输出相加结果A(4) 测试数据：1）（2x+5x8-3.1x11）+(7-5x8+11x9)=(7+2x+11x9-3.1x11)2) (1+x+x2+x3+x4+x5)+(-x3-x4)=(1+x+x2+x5)3) (x+x3)+(-x-x3)=04) (x+x2+x3)+0=(x+x2+x3)试验二 数组基础操作一、试验目标：掌握多种内部排序算法及多种内部排序效率。二、试验环境： PC机、Turbo C 或 Visual C+三、试验描述：经过随机数据比较多种内部排序算法。四、试验要求： （1）随机产生5组100个数据。 （2）对冒泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序关键字比较和交换次数进行统计。五、试验步骤：（1） 用次序存放结构存放数据（2） 产生100个随机数（3） 用上述内部排序算法（算法见）对（2）随机数进行排序，并统计比较次数和交换次数。参考算法：#define M 5#define N 4#include stdio.hmain() int i,j; static float scoreM+1N+1=78,85,83,65, 88,91,89,93, 72,65,54,75,86,88,75,60, 69,60,50,72; for(i=0;iM;i+) for(j=0;jN;j+) scoreiN += scoreij; scoreMj += scoreij; scoreiN /= N; for(j=0;jN;j+) scoreMj /= M; clrscr();printf(学生编号 课程1 课程2 课程3 课程4 个人平均n);for(i=0;iM;i+) printf(学生%dt,i+1); for(j=0;jN+1;j+) printf(%6.1ft,scoreij); printf(n); for(j=0;j8*(N+2);j+) printf(-); printf(n课程平均); for(j=0;jN;j+) printf(%6.1ft,scoreMj); printf(n); getch(); （4） 反复（2）（3）共5次。（5） 给出结论。试验三 队列基础操作一、试验目标：掌握队列基础操作：初始化队列、判队列为空、出队列、入队列等运算。二、试验环境：PC机、Turbo C 或 Visual C+三、试验描述：经过队列操作掌握队列多种性质。四、试验要求： （1）随机产生5组100个数据，加入队列。（2）初始化队列、判队列为空、出队列、入队列等运算五、试验步骤：（1）产生杨辉三角数据（2）利用队列基础操作实现杨辉三角输出算法以下：void out_number(int n);init_queue(Q);printf(1);en_queue(Q,s1+s2);for(I=2;I=n;I+)s1=0;for(j=1;j=I-1;j+)s2=out_queue(Q);printf(s2);en_queue(q,s1+s2);s1=s2;printf(1);en_queue(Q,1+s2);参考程序以下typedef structint *data;int front;int rear;sqqueue;main()int i,j,m,s1=0,s2=1;sqqueue q;clrscr();q.data=(int *)malloc(100*sizeof(int);q.rear=q.front=0;q.dataq.rear=s2;q.rear+;printf(%40d,s2);for(i=2;i=8;i+)s1=0;for(m=1;m=40-i;m+)printf(%c, );for(j=1;j=i-1;j+)s2=q.dataq.front;q.front+;printf(%d ,s2);q.dataq.rear=s1+s2;q.rear+;s1=s2;printf(%dn,1);q.dataq.rear=1+s2;q.rear+; （3）查看结果，得出结论。试验四 栈基础操作一、试验目标：掌握栈基础操作：初始化栈、判栈为空、出栈、入栈等运算。二、试验环境： PC机、Turbo C 或 Visual C+三、试验描述：经过队列操作掌握栈多种性质。四、试验要求：1 认真阅读和掌握本试验算法。2 上机将本算法实现。 3 保留和打印出程序运行结果，并结合程序进行分析。五、试验步骤：1、定义栈次序存取结构2、分别定义栈基础操作（初始化栈、判栈为空、出栈、入栈等）3、定义一个函数用来实现上面问题： 1）十进制整数X和R作为形参 2）初始化栈 3）只要不为反复做下列动作 4）将入栈5）X=X/R 6）只要栈不为空反复做下列动作7）栈顶出栈8）输出栈顶元素 参考程序：#define MAXSIZE 100#includestruct stack int dataMAXSIZE; int top;void init(struct stack *s) s-top=-1;int empty(struct stack *s) if(s-top=-1) return 1; else return 0; void push(struct stack *s,int i) if(s-top=MAXSIZE-1) printf(Stack is fulln); return; s-top+; s-datas-top=i;int pop(struct stack *s) if(empty(s) printf(stack is empty); return -1; return(s-datas-top-);void trans(int num) struct stack s; int k; init(&s); while(num) k=num%16; push(&s,k); num=num/16; while(!empty(&s) k=pop(&s); if(kLchild=P或F-Rchild=P）试验六 图基础操作一、试验目标：掌握图存放结构及深度优先遍历和广度优先遍历操作。二、试验环境：PC机、Turbo C 或 Visual C+三、试验描述：在连通无向图上访问全部结点四、试验要求：（1）以邻接表为存放结构，建立一个无向图（2）以用户指定顶点为起点，实现图深度和广度优先遍历，分别输出结点访问序列五、试验步骤：（1） 定义邻接表存放类型 （2） 基础操作Status CreateGraph(ALGraph &G) /采取邻接表表示法，结构无向图Gvoid DFSTraverse(ALGraph G, Status (*Visit)(int v)/对图G作深度优先遍历void BFSTraverse(ALGraph G, Status (*Visit)(int v)/对图G作广度优先遍历void Visit(int v)/ 访问顶点v（3） 程序步骤CreateGraph(ALGraph &G)DFSTraverse(ALGraph G, Status (*Visit)(int v)BFSTraverse(ALGraph G, Status (*Visit)(int v)