《《数据结构实验》讲义》由会员分享，可在线阅读，更多相关《《数据结构实验》讲义（10页珍藏版）》请在金锄头文库上搜索。
1、实验1 线性表的基本操作实验编号 JX020101-01所属院系 计算机科学与技术所属年级 2012-03所属课程 数据结构试验实验目的1掌握线性表的特点及其存储结构2掌握线性表的基本操作实验要求1线性表可以用顺序表也可以用单链表实现，鼓励大家用两种方式实现；2创建线性表时，数据从键盘输入整形数据；3线性表类型定义和或各种操作的实现，可以用教材给出的方法，也可以自己设计。实验环境硬件平台：计算机CPU 主频2.0G以上；内存128兆以上；软件平台：Windows2003或以上版本，Visual C+6.0。实验内容1用结构体描述一个线性表；2创建线性表，在线性表中实现插入、删除、按位置查找、按
2、元素值查找和求表长等操作；3设计选择式菜单，以选择菜单方式进行操作。实验步骤实验指导定义顺序表#define LIST_INIT_SIZE 100 /* 线性表存储空间的初始分配量 */#define LISTINCREMENT 2 /* 线性表存储空间的分配增量 */struct SqList ElemType *elem; /* 存储空间基址 */ int length; /* 当前长度 */ int listsize; /* 当前分配的存储容量(以sizeof(ElemType)为单位) */ ;定义算法函数Status InitList(SqList &L) /* 算法2.3 */ /
3、* 操作结果：构造一个空的顺序线性表 */ L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType); if(!L.elem) exit(OVERFLOW); /* 存储分配失败 */ L.length=0; /* 空表长度为0 */ L.listsize=LIST_INIT_SIZE; /* 初始存储容量 */ return OK;Status ListInsert(SqList &L, int i, ElemType e) /* 算法2.4 */ /* 初始条件：顺序线性表L已存在，1iListLength(L)+1 */ /* 操作
4、结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */ ElemType *newbase, *q, *p; if(iL.length+1) /* i值不合法 */ return ERROR; if(L.length=L.listsize) /* 当前存储空间已满,增加分配 */ if(!(newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType) exit(OVERFLOW); /* 存储分配失败 */ L.elem=newbase; /* 新基址 */ L.listsize+=LIS
5、TINCREMENT; / 增加存储容量 q=L.elem+i-1; /* q为插入位置 */ for(p=L.elem+L.length-1; p=q; -p) /* 插入位置及之后的元素右移 */ *(p+1)=*p; *q=e; / 插入e +L.length; /* 表长增1 */ return OK; 主函数样例void main() SqList L; Status i; int j; i=InitList(&L); printf(初始化L后：L.elem=%u L.length=%d L.listsize=%dn,L.elem,L.length,L.listsize); for(
6、j=1;j=5;j+) i=ListInsert(L,1,j); printf(在L的表头依次插入15后：*L.elem=); for(j=1;j=5;j+) cout*(L.elem+j-1) ; cout=0)=); scanf(%u,&n); while(n) Push(s,n%8); n=n/8; while(!StackEmpty(s) Pop(s,e); printf(%d,e); printf(n); 思考题1如何利用链栈实现数制转换问题？2如何利用链栈实现括号匹配的检验问题？实验3 Huffman编码的实现实验编号 JX020101-03 所属院系 计算机科学与技术 所属年级
7、2012-03 所属课程 数据结构试验实验目的1掌握二叉树的存储结构；2掌握二叉树的遍历操作的实现方法；3掌握建立Huffman树及求Huffman编码的操作，加深对二叉树应用的理解。 实验要求1二叉树采用二叉链表存储结构；2二叉树的遍历操作可以用递归算法实现。 实验环境硬件平台：计算机CPU 主频2.0G以上；内存128兆以上；软件平台：Windows2003或以上版本，Visual C+6.0。实验内容1设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针），如ABD#CE#F#，建立二叉树 2实现二叉树的前序、中序和后序遍历3设计一个哈夫曼编码系统, 根据字符频率构造哈夫曼树
8、，并给出每个字符的哈夫曼编码 实验步骤实验指导动态分配数组存储赫夫曼树 typedef struct char ch;int weight; int parent,lchild,rchild; HTnode, * Huffmantree;动态分配数组存储赫夫曼编码表 typedef char * * Huffmancode;哈夫曼树的构造：假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n 个权值分别设为w1、w2、wn，则哈夫曼树的构造规则为：1将w1、w2、，wn看成是有n棵树的森林（每棵树仅有一个结点）； 2在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的
9、根结点权值为其左、右子树根结点权值之和；3从森林中删除选取的两棵树，并将新树加入森林；4重复（2）、（3）步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。由已形成的哈夫曼树求哈夫曼编码：对每个叶结点都进行如下的处理：扫描由叶结点到根结点的各条分支，若分支中的当前结点与双亲结点是左支关系，则生成编码0，若分支中的当前结点与双亲结点是右支关系，则生成编码1，由此生成的二进制码的序列即为该结点的哈夫曼编码。思考题1用非递归算法实现二叉树的前序、中序和后序遍历；2设计一个哈夫曼编码器的译码系统。实验4 图的遍历的实现实验编号 JX020101-04 所属院系 计算机科学与技术所属年级 2012
10、-03 所属课程 数据结构试验实验目的1掌握图的邻接矩阵、邻接表的表示方法。2掌握建立图的邻接矩阵的算法。3掌握建立图的邻接表的算法。4加深对图的理解，逐步培养解决实际问题的编程能力。实验要求实验环境硬件平台：计算机CPU 主频2.0G以上；内存128兆以上；软件平台：Windows2003或以上版本，Visual C+6.0实验内容1建立图的邻接矩阵、邻接表。2对建立好的邻接矩阵表示的图进行深度优先搜索遍历。实验步骤实验指导1图的结构定义#define VMAX 30 /*图中最多顶点数*/typedef struct node /*邻接表中链表的结点类型*/ int vno; /*邻接顶点的顶点序号*/ struct node *next; /*后继邻接顶点*/EdgeNode;
