《数 据 结 构 实 验 指 导 书》由会员分享，可在线阅读，更多相关《数 据 结 构 实 验 指 导 书（18页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验指导书计算机学院专业基础教研室2004 年3 月实验一 线性表及其应用一、实验目的1. 熟悉C语言的上机环境，进一步掌握C语言的结构特点。2. 掌握线性表的顺序存储结构的定义及C语言实现。3. 掌握线性表的链式存储结构单链表的定义及C语言实现。4. 掌握线性表在顺序存储结构即顺序表中的各种基本操作。5. 掌握线性表在链式存储结构单链表中的各种基本操作。二、实验内容1. 顺序线性表的建立、插入及删除。2. 链式线性表的建立、插入及删除。三、实验步骤1. 建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。2. 利用前面的实验先建立一个顺序表L=21, 23, 14, 5,
2、 56, 17, 31，然 后在第 i 个位置插入元素 68。3. 建立一个带头结点的单链表,结点的值域为整型数据。要求将用户输入的 数据按尾插入法来建立相应单链表。四、实现提示1. 由于 C 语言的数组类型也有随机存取的特点,一维数组的机内表示就是顺 序结构。因此，可用C语言的一维数组实现线性表的顺序存储。在此，我们利用C语言的结构体类型定义顺序表：#define MAXSIZE 1024typedef int elemtype; /* 线性表中存放整型元素 */typedef struct elemtype vecMAXSIZE;int len;/* 顺序表的长度 */sequenlist
3、;将此结构定义放在一个头文件 sqlist.h 里,可避免在后面的参考程序中代码 重复书写,另外在该头文件里给出顺序表的建立及常量的定义。2. 注意如何取到第i个元素，在插入过程中注意溢出情况以及数组的下标与 位序(顺序表中元素的次序)的区别。3. 单链表的结点结构除数据域外，还含有一个指针域。用C语言描述结点结 构如下：typedef int elemtype;typedef struct node elemtype data; /数据域struct node *next; /指针域linklist;注意结点的建立方法及构造新结点时指针的变化。构造一个结点需用到 C 语 言的标准函数mall
4、oc(),如给指针变量p分配一个结点的地址：p=(linklist *)malloc(sizeof(linklist);该语句的功能是申请分配一个 类型为 linklist 的结点的地址空间，并将首地址存入指针变量 p 中。当结点不需要时可 以用标准函数free(p)释放结点存储空间，这时p为空值(NULL)。五、思考与提高1. 如果按由表尾至表头的次序输入数据元素，应如何建立顺序表。2. 在 main 函数里如果去掉 L=&a 语句，会出现什么结果？实验二 栈和队列一、实验目的1. 掌握栈的顺序表示和实现2. 掌握队列的链式表示和实现二、实验内容1. 编写一个程序实现顺序栈的各种基本运算。2
5、. 实现队列的链式表示和实现。三、实验步骤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
6、 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);/*置空顺序栈函数*/voi
7、d 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=l;iv=n;i
8、+)*利用循环快速输入数据*/scanf(%d,&x);Lappend(q,x); /*利用入链队列函数快速输入数据*/*入链队列函数*/void Lappend(Lqueue *q,int x) s-data=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 displa
9、y(Lqueue *q) while(p!=NULL) /*利用条件判断是否到队尾*/printf(%d-,p-data);p=p-next;五、思考与提高1. 读栈顶元素的算法与退栈顶元素的算法有何区别？2. 如果一个程序中要用到两个栈，为了不发生上溢错误，就必须给每个栈预 先分配一个足够大的存储空间。若每个栈都预分配过大的存储空间，势必会造成 系统空间紧张。如何解决这个问题？（1）链栈只有一个 top 指针，对于链队列，为什么要设计一个头指针和一个 尾指针？（2）一个程序中如果要用到两个栈时，可通过两个栈共享一维数组来实现 即双向栈共享邻接空间。如果一个程序中要用到两个队列，能否实现？如何
10、实 现？实验三 数组和广义表一、实验目的1. 掌握稀疏矩阵的压缩存储2. 掌握稀疏矩阵的转置算法二、实验内容1. 实现上三角阵的压缩存储。2. 用三元组顺序表存储稀疏矩阵，并实现矩阵的转置三、实验步骤1. 创建一个数组。2. 输入数据3. 给定矩阵任一元素的下标，4. 打印给定下标所对应的数据。5. 创建三元组顺序表。6. 输入矩阵中的数据。7. 输出对应的矩阵。四、实现提示1. 对于如下对称矩阵：a11aaA =2122aaa313233aaaa41424344将它们存入到一个线性数组中B,不存非零元素，all存入到第1个位置,a21存入到第二个位置，则aij能存到第几个位置，我们要以用梯形
11、公式算面积。a11aa2122aaa313233aaaa4142ij44aij 的位置是它上面的元素之和再加上左边的元素之和。它上面的元素之和为(l+(i-l)x(i-l)/2,左边的元素为(j-1) 所以这个元素存储的位置为 k=i(i-1)/2+j-1。因为矩阵A为对称矩阵，(另一部分没有写出)，所以另一部分的元素为 k=j(j-l)/2+i-l.所以存在关系 k=i(i-l)/2+j-l(ij)和 k=j(j-l)/2+i-l (idata = x; q-lchild = NULL; q-rchild = NULL;si = q;/*q 新结点地址存入 s 指针数组中*/if(i !=
12、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. 熟练掌握图的两种搜索路径的遍历方法。二、实验内容假设以一个带权有向图表示某一区域的公交线路网，图中顶点代表一些区域 中的重要场所，弧代表已有的公交线路，弧上
