《数据结构实验》讲义

实验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．在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；

3．从森林中删除选取的两棵树，并将新树加入森林； 4．重复（2）、（3）步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。 由已形成的哈夫曼树求哈夫曼编码： 对每个叶结点都进行如下的处理：

扫描由叶结点到根结点的各条分支，若分支中的当前结点与双亲结点是左支关系，则生成编码0，若分支中的当前结点与双亲结点是右支关系，则生成编码1，由此生成的二进制码的序列即为该结点的哈夫曼编码。

思考题

1．用非递归算法实现二叉树的前序、中序和后序遍历； 2．设计一个哈夫曼编码器的译码系统。

实验4 图的遍历的实现

实验编号 JX020101-04 所属院系 计算机科学与技术 所属年级 2012-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;

typedef EdgeNode *lgraph[VMAX]; /*邻接表类型*/

typedef int mgraph[VMAX][VMAX]; /*邻接矩阵类型*/

int visited[VMAX]; /*访问标志*/

int queue[VMAX]; /*广度优先搜索遍历存储队列*/

2．函数定义

int create_graph(lgraph lg,mgraph mg)

/*输入无向图的边，建立图的邻接表，邻接矩阵*/

void ldfs(lgraph g,int i) /*邻接表表示的图的深度优先搜索遍历*/ void lbfs(lgraph g,int s,int n) /*广度优先搜索遍历*/

3．主函数例 void main() {

lgraph lg; mgraph mg; int n,i;

n=create (lg,mg); /*调用create函数，建立图的邻接表、邻接矩阵*/ for(i=0;i

visited[i]=0; /*置全部顶点未访问标志*/

printf(\邻接表表示的图的递归深度优先搜索遍历\ ldfs(lg,0); /*调用ldfs函数*/

printf(\邻接表表示的图的递归广度优先搜索遍历\ lbfs(lg,0,n); /*调用lbfs函数*/ printf(\}

思考题 1．图的遍历 2．最小生成树

实验5 哈希表设计

实验编号 JX020101-05 所属院系 计算机科学与技术 所属年级 2012-03 所属课程 数据结构试验

实验目的

1．熟悉有关哈希表的基本概念； 2．熟悉构造哈希表的方法； 3．掌握哈希冲突的处理方法。

实验要求

实验环境

硬件平台：计算机CPU 主频2.0G以上；内存128兆以上； 软件平台：Windows2003或以上版本，Visual C++6.0

实验内容

对一批关键字集合采用开放定址哈希表的存储结构来建立相应的哈希表和完成查找过程。

实验步骤

实验指导

1．开放定址哈希表的存储结构

/* HashTableDef.h 开放定址哈希表的存储结构 */

int hashsize[]={11,19,29,37}; /* 哈希表容量递增表，一个合适的素数序列 */ int m=0; /* 哈希表表长，全局变量 */ struct HashTable {

ElemType *elem; /* 数据元素存储基址，动态分配数组 int count; /* 当前数据元素个数 */

int sizeindex; // hashsize[sizeindex]为当前容量 };

2．函数的定义

/* 哈希函数的基本操作 */

Status InitHashTable(HashTable &H) /* 操作结果: 构造一个空的哈希表 */

void DestroyHashTable(HashTable &H)

/* 初始条件: 哈希表H存在。操作结果: 销毁哈希表H */ unsigned Hash(KeyType K)

/* 一个简单的哈希函数(m为表长，全局变量) */ void collision(int &p,int d) // 线性探测再散列 /* 开放定址法处理冲突 */

Status SearchHash(HashTable H,KeyType K,int &p,int &c)

/* 在开放定址哈希表H中查找关键码为K的元素,若查找成功,以p指示待查数据 */ Status InsertHash(HashTable &,ElemType); /* 对函数的声明 */ void RecreateHashTable(HashTable &H) // 重建哈希表 /* 重建哈希表 */

Status InsertHash(HashTable &H,ElemType e)

/* 查找不成功时插入数据元素e到开放定址哈希表H中，并返回OK； */ /* 若冲突次数过大，则重建哈希表，算法9.18 */

void TraverseHash(HashTable H,void(*Vi)(int,ElemType)) /* 按哈希地址的顺序遍历哈希表 */

Status Find(HashTable H,KeyType K,int &p)

/* 在开放定址哈希表H中查找关键码为K的元素,若查找成功,以p指示待查数据

元素在表中位置,并返回SUCCESS;否则,返回UNSUCCESS */

思考题

采用除留余数法定义哈希表来建立相应的哈希表和完成查找过程

本文来源：https://www.bwwdw.com/article/cina.html