数据结构实验指导书.doc

数 据 结 构 实 验 指 导 书计算机学院专业基础教研室2004年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. 创建一个数组。2. 输入数据3. 给定矩阵任一元素的下标，4. 打印给定下标所对应的数据。5. 创建三元组顺序表。6. 输入矩阵中的数据。7. 输出对应的矩阵。四、实现提示1.对于如下对称矩阵：将它们存入到一个线性数组中B，不存非零元素，a11存入到第1个位置，a21存入到第二个位置，则aij能存到第几个位置，我们要以用梯形公式算面积。aij的位置是它上面的元素之和再加上左边的元素之和。它上面的元素之和为(1+(i-1)(i-1)/2，左边的元素为(j-1)所以这个元素存储的位置为k=i(i-1)/2+j-1。因为矩阵A为对称矩阵，(另一部分没有写出)，所以另一部分的元素为k=j(j-1)/2+i-1.所以存在关系k=i(i-1)/2+j-1(ij)和k=j(j-1)/2+i-1 (idata = 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. 掌握图的基本存储方法； 2. 掌握有关图的操作算法并用高级语言实现； 3. 熟练掌握图的两种搜索路径的遍历方法。二、实验内容假设以一个带权有向图表示某一区域的公交线路网，图中顶点代表一些区域中的重要场所，弧代表已有的公交线路，弧上的权表示该线路上的票价（或搭乘所需时间），试设计一个交通指南系统，指导前来咨询者以最低的票价或最少的时间从区域中的某一场所到达另一场所。三、实验步骤1. 定义结点结构，定义图结构。2.存储图信息；3. 定义求任意两点最短路径函数；4. 写出主函数。四、实现提示typedef struct node int no; float wgt; struct node *next; edgenode; typedef struct char vtx; edgenode *link; vexnode; typedef vexnode Graphn; void Floyd(Graph G, float Ann, int pnn) int i, j, k; for (i=0; in; i+) for(j=0;jn;j+) Aij=Gij; Pij=-1; for (k=0; kn; k+) for (i=0; in; i+) for (j=0; jn; j+) if(Aik +AkjAij) Pij=k; Aij=Aik+Akj; 五、思考与提高1. 判断两点是否可达。2. 如何对程序进行修改，找一条人最少的公交线路？3. 练习图的拓扑排序实验六 查找一、实验目的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. 比较各种算法的时间及空间复杂度。实验七 排序一、实验目的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.