数据结构与算法分析实验.doc

数据结构与算法分析实验教材：电子信息技术专业实验指导书的第2章：数据结构实验本实验课学分：0.5上课周次：10周- 17周(各个班不同，13)成绩评定：随课实验，成绩不单独给，但会体现在数据结构与算法分析课程的成绩中，课程总3.5学分，理论课程3学分，实验0.5学分。实验成绩体现在：1.实验程序完成之后的检查。2.实验报告（格式，每人按时交，16周交完报告）。3.随堂测试（13周-15周，时间不定）。课程使用编程语言：Visual C+或TC,需要同学们自己再重温一下C语言课本，特别要注意函数调用、指针、结构体部分的内容。实验一 线性顺序表的插入删除（8课时）教材实验1实验目的：学习线性顺序表的建立与各个操作以及编程语言的熟练掌握。实验内容：一、 线性顺序表1：函数调用方式实现建立线性表及线性表的各项功能typedef struct ListET alistMaxSize;int size;/一旦定义一个struct List这样的数据结构名称与类型，那么在你的程序里，struct List就象int 一样的意义了typedef char ET;/定义一个宏，用ET代表数据类型char ，这样若要改变数据类型，只需改动这一个地方就可以了。实现七个函数： 1）置空表：void setnull(struct List *p)2) 求长度：int length(struct List *p)3)取表中第i个结点：ET get (struct List *p,int i)4)按值查找：int locate(struct List *p,ET x)5)插入结点：void insert(struct List *p,int i,ET x)6)删除结点：void delete(struct List *p,int i)7)显示链表：void display(struct List *p)这样可以直接调用这七个函数来实现顺序表的操作，如实现在屏幕上显示如下内容：（就是说，每个动作都应该在屏幕上有提示）我的顺序表为：d- e-a-c-a-b值为a在表中的位置为：3位置4的值为：c删除第二个结点后顺序表：d- a-c-a-b删除第二个结点后顺序表：d- c-a-b删除第1个结点后顺序表： c-a-b删除第1个结点后顺序表： a-b实验二 线性链表（8课时）教材实验2实验目的：学习线性链表的数据结构与算法实现，继续学习编程，重点掌握单链表、循环单链表的数据结构的建立与各种操作的实现，学习双链表的建立方法。实验内容：一、 链表的建立与操作1：和实验一中的线性顺序表的同样方法，用函数调用方式实现建立线性链表及线性链表的各项功能链表的数据格式：struct SNodeET data;struct SNode *next; ;定义链表的每一个结点：struct SNode *s;struct SNode *s,*q;s=(struct SNode *)malloc(sizeof(struct SNode);s-data=x;q-next=s;实现七个函数： 1）置空表：void setnull(struct SNode *p)2) 求长度：int length(struct SNode *p)3)取表中第i个结点：ET get (struct SNode *p,int i)4)按值查找：int locate(struct SNode *p,ET x)5)插入结点：void insert(struct SNode *p,int i,ET x)void insert(struct SNode *p,ET x,int i)int j=1;struct SNode *s,*q;s=(struct SNode *)malloc(sizeof(struct SNode);s-data=x;q=*p;if(i=1)s-next=q;*p=s;elsewhile(jnext!=NULL)q=q-next;j+;if(j=i-1)s-next=q-next;q-next=s;printf(not exist!);6)删除结点：void delete(struct SNode *p,int i)7)显示链表：void display(struct SNode *p)这样可以直接调用这七个函数来实现链表的操作，如同线性顺序表的d- e-a-c-a-b一样。实验三 求解迷宫问题（8课时）教材实验3一、实验目的：巩固队列、栈的数据结构形式，掌握其在程序设计中的具体应用；通过迷宫问题的分析，进一步了解程序设计的基本方法，提高解决实际问题的能力。二、实验内容：耗子走迷宫的古典问题，要求用队列的存储方式、堆栈的存储方式分别实现程序。首先，用二维数组来表示迷宫，其元素值只有两个入口000110001000010011101101010101101000出口几个问题：1、二维迷宫数组的初始化mgmn2、迷宫中的每个位置（i,j）有8个方向可走，我们要约定每次先走哪个方向，这样程序才有章可循。边缘位置只有3个方向，这样我们给迷宫周围增加一圈围墙，即迷宫数组扩充为mgm+1n+1，且边缘全部为1。11111111100011011001000110100111110110111010101111010001111111113、不同方向对应有不同的坐标变换值，如对（i,j）这个位置来说，有8个方向，定义一个变量v18，对应i=i+zxv,j=j+zyv,这样，事先将每个方向上的横坐标、纵坐标增量zx，zy分别用数组给出即可。4、问题的关键在：如何在走不通的情况下回过头来重新寻找其他方向？队列、栈的存储结构？需要存储哪些数据？5、输出迷宫路径的方式：入口-(x1,y1)-(x2,y2)-.-出口实验四 构建Huffman树(二叉树应用)一、 实验的目的和要求: 学习huffman树这种特殊的二叉树的建立方法，详细给出Huffman树的建立过程以及该二叉树建立的程序(要求建立一个二叉树，不要求进行哈弗曼的编解码，有兴趣的同学可以自己学习编码解码的程序，当然在提交报告中能够把哈弗曼编解码原理阐述清楚，程序也实现的话更好。) 二、实验内容给定有18个字符组成的文本： A A D A T A R A E F R T A A F T E R 求各字符的出现的频度，以此建立哈夫曼树。 哈夫曼编码/不定长码 能按字符的使用频度,使文本代码的总长度具有最小值。 构造哈夫曼树的过程：（1）将给定的n个权值w1,w2,.,wn作为n个根结点的权值构造一个具有n棵二叉树的森林T1,T2,.,Tn，其中每棵二叉树只有一个根结点；（2）在森林中选取两棵根结点权值最小的二叉树作为左右子树构造一棵新二叉树，新二叉树的根结点权值为这两棵树根的权值之和；（3）在森林中，将上面选择的这两棵根权值最小的二叉树从森林中删除，并将刚刚新构造的二叉树加入到森林中；（4）重复上面（2）和（3），直到森林中只有一棵二叉树为止。这棵二叉树就是哈夫曼树。 假设有一组权值5,29,7,8,14,23,3,11，下面我们将利用这组权值演示构造哈夫曼树的过程。第一步：首先将这8个权值排序。 第二步：从中选择两个根