《数据结构》实验指导书2011.doc

数 据 结 构 实 验 指 导 书南京工程学院信息管理与信息系统教研室2011年3月实验一 线性表操作一、实验目的1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。2.掌握线性表的顺序存储结构的定义及C语言实现。3.掌握线性表的链式存储结构单链表的定义及C语言实现。4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。5.掌握线性表在链式存储结构单链表中的各种基本操作。二、实验内容 1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。三、实验步骤1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。2.利用前面的实验先建立一个顺序表L=21，23，14，5，56，17，31，然后在第i个位置插入元素68。3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。四、实现提示1.由于C语言的数组类型也有随机存取的特点，一维数组的机内表示就是顺序结构。因此，可用C语言的一维数组实现线性表的顺序存储。在此，我们利用C语言的结构体类型定义顺序表：#define MAXSIZE 1024typedef int elemtype; /* 线性表中存放整型元素 */typedef struct elemtype vecMAXSIZE; int len; /* 顺序表的长度 */sequenlist;将此结构定义放在一个头文件sqlist.h里，可避免在后面的参考程序中代码重复书写，另外在该头文件里给出顺序表的建立及常量的定义。2. 注意如何取到第i个元素，在插入过程中注意溢出情况以及数组的下标与位序（顺序表中元素的次序）的区别。3.单链表的结点结构除数据域外，还含有一个指针域。用C语言描述结点结构如下： typedef int elemtype;typedef struct node elemtype data; /数据域 struct node *next; /指针域 linklist; 注意结点的建立方法及构造新结点时指针的变化。构造一个结点需用到C语言的标准函数malloc()，如给指针变量p分配一个结点的地址：p=(linklist *)malloc(sizeof(linklist);该语句的功能是申请分配一个类型为linklist的结点的地址空间，并将首地址存入指针变量p 中。当结点不需要时可以用标准函数free(p)释放结点存储空间，这时p为空值（NULL）。五、思考与提高1. 如果按由表尾至表头的次序输入数据元素，应如何建立顺序表。2. 在main函数里如果去掉L=&a语句，会出现什么结果？实验二 栈和队列的应用一、实验目的1. 掌握栈的顺序表示和实现2. 掌握队列的链式表示和实现二、实验内容1. 编写一个程序实现顺序栈的各种基本运算。2. 实现队列的链式表示和实现。三、实验步骤1. 初始化顺序栈2. 插入元素3. 删除栈顶元素4. 取栈顶元素5. 遍历顺序栈6. 置空顺序栈7. 初始化并建立链队列8. 入链队列9. 出链队列10. 遍历链队列四、实现提示1. /*定义顺序栈的存储结构*/typedef struct ElemType stackMAXNUM; int top;SqStack; /*初始化顺序栈函数*/void InitStack(SqStack *p) q=(SqStack*)malloc(sizeof(SqStack) /*申请空间*/)/*入栈函数*/void Push(SqStack *p,ElemType x) if(p-toptop=p-top+1; /*栈顶+1*/ p-stackp-top=x; /*数据入栈*/*出栈函数*/ElemType Pop(SqStack *p)x=p-stackp-top; /*将栈顶元素赋给x*/p-top=p-top-1; /*栈顶-1*/*获取栈顶元素函数*/ElemType GetTop(SqStack *p) x=p-stackp-top;/*遍历顺序栈函数*/void OutStack(SqStack *p) for(i=p-top;i=0;i-)printf(第%d个数据元素是：%6dn,i,p-stacki);/*置空顺序栈函数*/void setEmpty(SqStack *p) p-top= -1;2. /*定义链队列*/typedef struct Qnode ElemType data; struct Qnode *next;Qnodetype;typedef struct Qnodetype *front; Qnodetype *rear;Lqueue; /*初始化并建立链队列函数*/void creat(Lqueue *q) h=(Qnodetype*)malloc(sizeof(Qnodetype); /*初始化申请空间*/ h-next=NULL; q-front=h; q-rear=h;for(i=1;idata=x; s-next=NULL; q-rear-next=s; q-rear=s;/*出链队列函数*/ElemType Ldelete(Lqueue *q) p=q-front-next; q-front-next=p-next; if(p-next=NULL) q-rear=q-front; x=p-data; free(p); /*释放空间*/*遍历链队列函数*/void display(Lqueue *q) while(p!=NULL) /*利用条件判断是否到队尾*/ printf(%d-,p-data); p=p-next; 五、思考与提高1. 读栈顶元素的算法与退栈顶元素的算法有何区别？2. 如果一个程序中要用到两个栈，为了不发生上溢错误，就必须给每个栈预先分配一个足够大的存储空间。若每个栈都预分配过大的存储空间，势必会造成系统空间紧张。如何解决这个问题？（1）链栈只有一个top指针，对于链队列，为什么要设计一个头指针和一个尾指针？（2）一个程序中如果要用到两个栈时，可通过两个栈共享一维数组来实现。即双向栈共享邻接空间。如果一个程序中要用到两个队列，能否实现？如何实现？实验三 树操作一、实验目的1. 通过实验，掌握二叉树的建立与存储2. 通过实验，掌握二叉树的遍历方法二、实验内容1. 练习二叉树的建立与存储2. 练习二叉树的遍历三、实验步骤1. 建立自己的头文件BT.H，内容包括二叉链表的结构描述、二叉树的建立、二叉树的先序、中序与后序遍历算法。2. 建立二叉树,并通过调用函数, 输出先序遍历、中序遍历与后序遍历的结果。四、实现提示建立二叉树的代码如下：BTCHINALR * createbt( ) BTCHINALR *q; struct node1 *s30; int j,i,x; printf(建立二叉树，输入结点对应的编号和值,编号和值之间用逗号隔开nn); printf(i,x = ); scanf(%d,%c,&i,&x); while(i != 0 & x != $) q = (BTCHINALR*)malloc(sizeof(BTCHINALR); /*建立一个新结点q*/ q-data = x; q-lchild = NULL; q-rchild = NULL; si = q;/*q新结点地址存入s指针数组中*/ if(i != 1)/*i = 1，对应的结点是根结点*/ j = i / 2; /*求双亲结点的编号j*/ if(i % 2 = 0) sj-lchild = q; /*q结点编号为偶数则挂在双亲结点j的左边*/ else sj-rchild = q; /*q结点编号为奇数则挂在双亲结点j的右边*/ printf(i,x = ); scanf(%d,%c,&i,&x); return s1; /*返回根结点地址*/五、思考与提高1. 如何用孩子兄弟表示法存储树？2. 熟悉并掌握赫夫曼树。实验四 查找和排序操作（1）一、实验目的1. 掌握查找的不同方法，并能用高级语言实现查找算法； 2. 熟练掌握二叉排序树的构造和查找方法。3. 了解静态查找表及哈希表查找方法。二、实验内容设计一个算法读入一串整数，然后构造二叉排序树，进行查找。三、实验步骤1. 从空的二叉树开始，每输入一个结点数据，就建立一个新结点插入到当前已生成的二叉排序树中。2. 在二叉排序树中查找某一结点。3.用其它查找算法进行排序（课后自己做）。四、实现提示1. 定义结构typedef struct node int key; int other; struct node *lchild, *rchild; bstnode; void inorder ( t ) if (t!=Null) inorder(tlchild); printf(“%4d”, tkey); inorder(trchild); bstnode *insertbst(t, s) bstnode *s, *t; bstnode *f, *p; p=t; while(p!=Null) f=p; if (skey= =pkey) return t; if (skeypkey) p=plchild; else p=prchild; if(t= =Null) return s; if (skeyfkey) flchild=s; else frchild=s; return t; bstnode *creatord( ) bstnode *t, * s; int key; t=Null; scanf(“%d”,&key); while (key!=0) s=malloc(sizeof (bitree); skey=key; slchild=Null; srchild=Null; scanf(“%d”, &data); sother=data; t=insertbst(t, s); scanf(“%d”,&key); return t; 五、思考与提高1. 用其它的查找方法完成该算法。2. 比较各种算法的时间及空间复杂度。实验四 查找和排序操作（2）一、实验目的1. 掌握常用的排序方法，并掌握用高级语言实现排序算法的方法； 2. 深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用；3. 了解各种方法的排序过程及其时间复杂度的分析方法。二、实验内容统计成绩 给出n个学生的考试成绩表，每条信息由姓名和分数组成，试设计一个算法： （1） 按分数高低次序，打印出每个学生在考试中获得的名次，分数相同的为同一名次； （2） 按名次列出每个学生的姓名与分数。三、实验步骤1. 定义结构体。2. 定义结构体数组。3. 定出主程序，对数据进行排序。四、实现提示#define n 30 typedef struct student char name8; int score; student Rn; main ( ) int num, i, j, max, temp; printf(“n请输入学生成绩: n”); for (i=0; in; i+) printf (“姓名:”); scanf (“%s”, &); scanf (“%4d”, &stui.score); num=1; for (i=0; in; i+)