实验1 线性表的基本操作
实验编号 JX020101-01
所属院系 计算机科学与技术 所属年级 2012-03
所属课程 数据结构试验
实验目的
1．掌握线性表的特点及其存储结构 2．掌握线性表的基本操作
实验要求
1．线性表可以用顺序表也可以用单链表实现，鼓励大家用两种方式实现； 2．创建线性表时，数据从键盘输入整形数据；
3．线性表类型定义和或各种操作的实现，可以用教材给出的方法，也可以自己设计。
实验环境
硬件平台：计算机CPU 主频2.0G以上；内存128兆以上； 软件平台：Windows2003或以上版本，Visual C++6.0。
实验内容
1．用结构体描述一个线性表；
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 */ { /* 操作结果：构造一个空的顺序线性表 */
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已存在，1≤i≤ListLength(L)+1 */ /* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */ ElemType *newbase, *q, *p;
if(i<1||i>L.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+=LISTINCREMENT; // 增加存储容量 }
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=%d\\n\ for(j=1;j<=5;j++) i=ListInsert(L,1,j);
printf(\在L的表头依次插入1～5后：*L.elem=\ for(j=1;j<=5;j++) cout<<*(L.elem+j-1)<<' '; cout< printf(\} 思考题 1、编写一个算法实现两个有序（从小到大）表合并成为一个有序表。 2、设有一个线性表A，包含n个元素，要求写出一个将该表逆置的算法。 实验2 栈的应用 实验编号 JX020101-02 所属院系 计算机科学与技术 所属年级 2012-03 所属课程 数据结构试验 实验目的 （1）学会栈基础知识、结构特点、存贮结构； （2）练习使用栈的结构特点和基本操作； （3）学会使用栈处理应用问题的方法。 实验要求 1．栈结构可以用顺序栈实现。 2．测试数据从键盘输入。 3．栈类型定义和或各种操作的实现，可以用教材给出的方法，也可以自己设计。 实验环境 硬件平台：计算机CPU 主频2.0G以上；内存128兆以上； 软件平台：Windows2003或以上版本，Visual C++6.0。 实验内容 1．用结构体描述一个栈； 2．构造一个空栈，实现数据元素出栈、入栈等操作； 3．编写程序实现非负十进制整数到八进制整数的转换； 4．假设一个算术表达式中包含圆括弧、方括弧和花括弧三种类型的括弧，这三种括号可以按任意的次序嵌套使用，编写程序实现表达式中括弧是否正确配对的判别。 实验步骤 实验指导 数制转换 十进制数值转换成八进制使用辗转相除法将一个十进制数值转换成八进制数值。 即用该十进制数值除以8，并保留其余数；重复此操作，直到该十进制数值为0为止。最后将所有的余数反向输出就是所对应的八进制数值。 数制转换的实现 括号匹配的检验 在检验过程中，若遇到以下几种情况之一，括号不匹配： （1）当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号； （2）从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况； （3）算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。 算法步骤： （1）扫描表达式 （2）凡出现左括弧，则进栈 （3）凡出现右括弧，首先检查栈是否空 若栈空，则表明该“右括弧”多余 否则和栈顶元素比较， 若相匹配，则“左括弧出栈” 否则表明不匹配 （4）表达式检验结束时， 若栈空，则表明表达式中匹配正确 否则表明“左括弧”有余 void conversion() { SqStack s; unsigned n; /* 非负整数 */ SElemType e; InitStack(s); /* 初始化栈 */ printf(\ while(n) { Push(s,n%8); n=n/8; } while(!StackEmpty(s)) { Pop(s,e); printf(\ printf(\ } 思考题 1．如何利用链栈实现数制转换问题？ 2．如何利用链栈实现括号匹配的检验问题？ 实验3 Huffman编码的实现 实验编号 JX020101-03 所属院系 计算机科学与技术 所属年级 2012-03 所属课程 数据结构试验 实验目的 1．掌握二叉树的存储结构； 2．掌握二叉树的遍历操作的实现方法； 3．掌握建立Huffman树及求Huffman编码的操作，加深对二叉树应用的理解。 实验要求 1．二叉树采用二叉链表存储结构； 2．二叉树的遍历操作可以用递归算法实现。 实验环境 硬件平台：计算机CPU 主频2.0G以上；内存128兆以上； 软件平台：Windows2003或以上版本，Visual C++6.0。 实验内容 1．设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针），如ABD###CE##F##，建立二叉树 2．实现二叉树的前序、中序和后序遍历 3．设计一个哈夫曼编码系统, 根据字符频率构造哈夫曼树，并给出每个字符的哈夫曼编码 实验步骤 实验指导 动态分配数组存储赫夫曼树 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．在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；