数据结构实验报告.doc

目 录 实验一 线性表的基本操作 1．实验目的……………………………………………………2 2．实验环境……………………………………………………2 3．实验内容，主要代码，调试与运行……………………2 4．总结……………………………………………………14 实验二 栈的基本操作 1．实验目的……………………………………………………15 2．实验环境……………………………………………………15 3．实验内容，主要代码，调试与运行……………………15 4．总结……………………………………………………18 实验三 赫夫曼树 1．实验目的……………………………………………………18 2．实验环境……………………………………………………18 3．实验内容，主要代码，调试与运行……………………19 4．总结……………………………………………………32 实验一 线性表的基本操作 一、 实验目的 １、 熟悉ｃ或vc++语言上机环境。 ２、 会定义线性表的顺序存储结构和链式存储结构。 ３、 熟悉顺序表和链表的一些基本操作和应用。 ４、 加深对线性表的理解，逐步培养解决实际问题的编程能力。 二、 实验环境 运行ｃ或vc++的微机。 三、 实验内容 已知线性表la的数据元素（n个，n为偶数），现要求将la拆开成两个新的线性表lb，lc。要求lb中的数据元素为la中的奇数位序的数据元素（a1, a3, …, an-1），lc中的数据元素为la中的偶数位序的数据元素（a2, a4, …, an）。 实验代码如下： #includelt;stdio.hgt; #includelt;malloc.hgt; #define max 100 //定义线性表的最大长度 typedef struct { char elem; char list[max]; //线性表 int length; //length指示当前线性表的长度 }sqlist; void initial(sqlist amp;); //初始化线性表 void insert(sqlist amp;,int,char); //在线性表中插入元素 void initlist(sqlist amp;); void print(sqlist); //显示线性表中所有元素 void main() {sqlist la,lb,lc;// la,lb,lc是线性表 initial(la); initlist(lb); initlist(lc); int i; for(i=0;ilt;la.length;i++) {if(i%2==0) insert(lb,i/2,la.list[i]); //奇数位插入lb else insert(lc,i/2,la.list[i]);} //偶数位插入lc printf(\n您输入的线性表元素为:\n\n); print(la); printf(线性表的奇数位次的元素为:\n\n); print(lb); printf(线性表的偶数位次的元素为:\n\n); print(lc); } void initial(sqlist amp;v) { int i,a; printf(请输入一个偶数作为线性表的长度:\n\n); scanf(%d,amp;a); while(a%2!=0) {printf(您输入的数是奇数，请重新输入一个偶数:\n\n); scanf(%d,amp;a);} v.length=a; printf(\n请输入线性表元素:\n\n); for(i=0;ilt;v.length;i++) scanf(%c,amp;v.list[i]); //对la进行赋值 } void initlist(sqlist amp;v) //构造一个空的线性表 { v.elem=(char)malloc(max*sizeof(char)); v.length=0; } void insert(sqlist amp;v,int j,char c) { v.list[j]=c; //插入c v.length++; } void print(sqlist v) { int i; for(i=0;ilt;v.length;i++) {printf(%c,v.list[i]);} //输出线性表元素 printf(\n\n); 调试通过后运行结果如下： 已知线性表la的数据元素（n个），现要求将la的数据元素复制到另一个线性表lb中。 实验代码如下： #includelt;stdio.hgt; #includelt;malloc.hgt; #define max 100 //定义线性表的最大长度 typedef struct {