计算机系
第一部分 算法与数据结构课程实验概述
一．实验目的
《算法与数据结构》是计算机专业的主干课程和必修课程之一，其目的是让大家学习、分析和研究数据对象特征，掌握数据组织方法和计算机的表示方法，以便选择合适的数据逻辑结构和存储结构，设计相应的运算操作，把现实世界中的问题转化为计算机内部的表示与处理的方法，要求掌握算法的时间、空间复杂度分析基本技术，培养良好的程序设计风格，掌握进行复杂程序设计的技能。在计算机科学领域，尤其是在系统软件和应用软件的设计和应用中要用到各种数据结构，因此，掌握数据结构对提高软件设计和程序编制水平有很大的帮助。
二．实验要求
2.1实验步骤
设计步骤的规范不但可以培养学生科学的工作方法和作风，而且还能有效地减少错误，提高工作效率。因此必须严格执行良好的实验步骤规范（包括上机操作规范）。本课程实验的基本步骤是：
2.1.1问题分析
充分地分析和理解问题本身，明确问题要求做什么。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如；输入、输出数据的类型、值的范围以及形式等。同时为调试程序准备好测试数据，包含合法的输入数据和非法形式输入的数据。
2.1.2设计和编码
设计即是对问题描述中涉及的操作对象定义相应的数据类型，定义主程序模块和各抽象数据类型；定义相应的存储结构并写出各过程和函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试。
编码即把详细设计的结果进一步求精为程序设计语言程序，写出源程序。对程序中的疑问应作出记号，以便上机时注意解决。每个明确的功能模块程序一般不超过60行，程序的每一行不得超过60个字符，否则要进一步划分。
2.1.3上机前程序静态检查
上机前程序静态检查可有效提高调试效率，减少上机调试程序时的无谓错误。
静态检查主要有两种途径：用一组测试数据手工执行程序；通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑。把程序中的明显错误事先排除。
2.1.4上机调试程序
上机实验时要带上《C语言》教材、《数据结构》教材、《数据结构上机实验指导书》，调试最好分模块进行，自底向下，即先调试低层过程或函数。调试过程中应多动手确定疑点，通过修改程序来证明。
调试正确后，认真整理源程序及其注释，写出或打印出带有完整注释的且格式良好的源程序清单和结果。
2.1.5完成上机实验报告
2.2实验报告格式
《算法与数据结构》
实验报告
题目：
班级： 组号：
姓名： 学号：
姓名： 学号：
姓名： 学号：
姓名： 学号：
姓名： 学号：
姓名： 学号：
姓名： 学号：
姓名： 学号：
姓名： 学号：
姓名： 学号：
华东理工大学
信息学院计算机系
20##年5月
1． 需求分析
以无歧义的陈述说明程序设计的任务，强调程序要做什么。明确规定：
（1）．输入的形式和输入值的范围；
（2） 输出的形式
（3） 程序所能达到的功能
（4） 测试数据：包括正确的输入及其输出结果，含有错误的输入及其输出结果。
2． 系统设计
1． 说明本程序中用到的所有抽象数据类型的定义；
2． 主程序的流程以及各程序模块之间的层次调用关系，画出函数的调用关系图。
3． 列出各个功能模块的主要功能及输入输出参数。
3．调试分析
内容包括：
（1）．调试过程中遇到的问题是如何解决的及对设计与实现的回顾讨论与分析。
（2） 算法的时间复杂度分析（包括基本操作和其他算法）和改进设想；
（3） 经验与体会等。
4．测试结果
列出你的测试结果，包括输入与输出，这里的测试数据应完整和严格，可用需求分析中的测试数据。
5、用户手册
说明如何使用你编写的程序，详细列出每一步操作步骤。
6、附录
即带注释的源程序清单和结果。除原有注释外再加一些必要的注释和断言(关键语句或函数功能的注释)。 对填空和改错题还要写出正确答案，如果题目规定了测试数据，则结果要包含这些测试数据和运行输出，当然还可以含其它测试数据及其运行输出。
2.4考核及评分办法
上机实验成绩根据上机考勤、调试情况、实验报告评分，分为五级制：优、良、中、及格、不及格。
第二部分 上机实验内容
实验一 线 性 表，栈和队列
一、 实验目的
1． 了解线性表，栈和队列等线性结构的特性，以便灵活应用。
2． 熟练掌握线性表，栈和队列的各种操作和应用
二、实验内容
1．分别用线性链表和队列设计实现一个一元稀疏多项式计算器
[问题描述]
设计一个一元稀疏多项式简单计算器。
[基本要求]
1. 用带表头结点的单链表存储多项式，多项式的项数存放在头结点中。
2. 用链式队列存储多项式。多项式的项数存放在队列头结点中。
一元稀疏多项式简单计算器的基本功能是：
（1） 输入并建立多项式；
（2） 输出多项式，输出形式为整数序列：n,c1,e1, c2,e2,,,,,,, cn,en,其中n是多项式的项数，ci,ei,分别是第i项的系数和指数，序列按指数降序排序；
（3） 多项式a和b相加，建立多项式a+b；如果用单链表存储多项式，则用a存储多项式（a+b）。如果用队列存储多项式，则需为多项式（a+b）另外创建一个队列。
（4） 多项式a和b相减，建立多项式a-b；如果用单链表存储多项式，则用a存储多项式（a+b）。如果用队列存储多项式，则需为多项式（a+b）另外创建一个队列。
（5） 计算多项式在x处的值。
[测试数据]
（1）（2x+5x8-3.1x11）+(7-5x8+11x9)=(-3.1x11+11x9+2x+7)
(2) (6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2-x2+7.8x15)=(-7.8x15-1.2x9-x+12x-3)
(3) (1+x+x2+x3+x4+x5)+(-x3-x4)=(x5+x2+x+1)
(4) (x+x3)+(-x-x3)=0
(5) (x+x2+x3)+0=( x3+ x2+ x)
2．算术表达式求值：设计一个程序，演示用算符优先法对算术表达式求值的过程。
【问题描述：】
设计一个算术表达式计算器。
[基本要求]
以字符序列的形式从终端输入语法正确的、不含变量，带括号的中缀整数表达式。利用下表给出的算符优先关系，应用运算符栈、运算数栈实现对算术四则混合运算表达式的求值。
算符优先关系表（θ1、θ2是相邻算符，θ1在左，θ2在右）
表达式中任何相邻运算符 q1、q2 的优先关系有：
q1 < q2：q1的优先级 低于 q2
q1 = q2：q1的优先级 等于 q2
q1 > q2：q1的优先级 高于 q2
[测试数据]
3×（7-2）/（32-17）× （23+45）
实验二 树和二叉树
一、 实验目的
1. 掌握二叉树，二叉树排序数的概念及存储方法。
2. 掌握二叉树的遍历算法。
3. 熟练掌握编写实现树的各种运算的算法。
二、实验内容
1. 用二叉树表示代数表达式并输出代数表达式的前缀式和后缀式
[要求及提示]：
编写一个程序，用二叉树来表示代数表达式，树的每个结点包括一个运算符，代数表达式由输入得到（其中只包含+，-，*，/和用一个字母表示的数且没有错误，并且按照先乘除后加减的原则），试编写程序输出表达式的前缀式和后缀式。
[实验数据]：
自己给出一个并附在实验报告中
2. 求二叉树中从根结点到叶子节点的路径
[要求及提示]
对于1中的代数表达式二叉树，分别用递归和非递归的方法编写程序完成如下功能：
1． 输出所有的叶子结点的数据项值。
2． 输出所有从叶子节点到根结点的路径
实验三 图
一、 实验目的
1.熟悉图的各种存储方法。
2.掌握遍历图的递归和非递归的算法。
3.理解图的有关算法。
二、实验内容
1．实现图的邻接矩阵和邻接表存储
[要求及提示]
对于下图所示的有向图G，编写一个程序完成如下功能：
1． 建立G的邻接表存储结构
2． 输出下图的拓扑排序序列
3． 编写一个程序输出从顶点0开始的深度优先遍历序列（递归算法）和广度优先遍历序列（非递归算法）。
实验数据
自己选择一个无圈图。
实验三 查找和排序
一、 实验目的
1. 掌握顺序查找，二分法查找，分块查找的算法。
2．掌握各种排序算法及其性能的比较
二、实验内容
1．编写一个程序输出在顺序表{13，22，35，43，54，68，71，82，98，1005}中采用顺序方法和折半方法查找某个关键字的过程。
2．编写一个程序实现直接插入排序过程，并输出{94，28，57，66，35，84，63，42，71，10}的排序过程
3．编写一个程序实现快速排序算法，并输出{94，28，57，66，35，84，63，42，71，10}的排序过程。
第二篇：《数据结构》实验指导书(新)
数据结构实验指导书
实验一 线性表
[实验目的]
1．了解顺序表的结构特点及有关概念，掌握顺序表建立、插入、删除的基本操作算法。
2．了解单链表的结构特点及有关概念，掌握单链表建立、插入、删除的基本操作算法。
[实验内容]
1．顺序表的实践。
1) 建立4个元素的顺序表list[]={2，3，4，5}，实现顺序表建立的基本操作。
2) 在list[]={2，3，4，5}的元素4和5之间插入一个元素9，实现顺序表插入的基本操作。
3) 在list[]={2，3，4，9，5}中删除指定位置（i=3）上的元素9，实现顺序表的删除的基本操作。
2．单链表的实践。
1) 建立一个包括头结点和3个结点的（4，2，1）的单链表，实现单链表建立的基本操作。
2) 在已建好的单链表中的指定位置（x=2）插入一个结点3，实现单链表插入的基本操作。
3) 在一个包括头结点和4个结点的（4，2，3，1）的单链表的指定位置删除一个结点，实现单链表删除的基本操作。
[实验要点及说明]
线性表（linear list）是n（n≥0）个数据元素a1，a2，…an组成的有限序列。
其中n 称为数据元素的个数或线性表的长度，当n=0时称为空表，n>0时称为非空表。
通常将非空的线性表记为（a1，a2，…,an），其中的数据元素ai（1≤i≤n）是一个抽象的符号， ai是第i个数据元素,称i为数据元素ai在线性表中的位置。其具体含义在不同情况下是不同的，即它的数据类型可以根据具体情况而定，本书中，我们将它的类型设定为elemtype，表示某一种具体的已知数据类型。
顺序表也称为线性表的顺序存储结构。其存储方式为：在内存中用一组地址连续的存储单元依次存储线性表的数据元素，但该连续存储空间的大小要大于或等于顺序表的长度。一般让线性表中第一个元素存放在连续存储空间第一个位置，第二个元素紧跟着第一个之后，其余依此类推。
可定义顺序表如下：
#define maxnum
elemtype list[maxnum];
int num=-1;
线性表的链式存贮结构，也称为链表。其存贮方式是：在内存中利用存贮单元(可以不连续)来存放元素值及它在内存的地址，各个元素的存放顺序及位置都可以以任意顺序进行，原来相邻的元素存放到计算机内存后不一定相邻，从一个元素找下一个元素必须通过地址(指针)才能实现。故不能像顺序表一样可随机访问。常用的链表有单链表、循环链表和双向链表、多重链表等。
单链表是线性表的链式存贮结构中每个结点只有一个指针域的链表。
可定义单链表的结点结构如下：
typedef struct node
{elemtype data;
struct node *next;
}slnode;
必做顺序表、单链表的建立，选作顺序表、单链表的插入或删除。
[参考程序]
1．建立顺序表
#include<stdio.h>
#define max 10
main()
{
int i=0,x,*num,ch;
int list[max];
printf("input list:");
while((ch= getchar())!='\n')
{
list[i];
i++;
}
*num=i-1;
for(i=0;i<=*num;i++)
printf("list[%d]=%c",i,list[i]);
}
2．顺序表插入
#include<stdio.h>
#define max 5
#define true 1
#define false 0
int insertq(int list[],int *num,int i,int x)
{
int j;
if((i<0)||(i>*num+1))
{ printf("mistake.");
return(false);}
if(*num>=max-1)
{printf("list is full.");
return(false);
}
for(j=*num+1;j>i;j--)
list[j]=list[j-1];
list[i]=x;
(*num)++;
return(true);
}
main()
{
int i=0,x,*num,ch;
int list[max];
printf("input list:");
while((ch=getchar())!='\n')
{
list[i]=ch;
i++;
}
*num=i-1;
printf("insert No.i:");
scanf("%d",&i);
getchar();
printf("insert data:");
x=getchar();
getchar();
insertq(list,num,i,x);
for(i=0;i<=*num;i++)
printf("list[%d]=%c",i,list[i]);
printf("\n");
}
3．单链表插入
#include <stdio.h>
#define null 0
typedef struct node
{int data;
struct node *next;
}slnode;
void *initiate(slnode **h)
{*h=(slnode*)malloc(sizeof(slnode));
(*h)->next=null;
}
slnode append(slnode *p,int x)
{slnode *s;
s=(slnode*)malloc(sizeof(slnode));
s->data=x;
s->next=p->next;
p->next=s;
}
slnode *search(slnode *p,int x)
{slnode *s;
s=p->next;
while(s!=null)
{if(s->data==x)
return(s);
s=s->next;
}
return(null);
}
int insert(slnode *p,int x,int y)
{ slnode *m,*n;
n=(slnode*)malloc(sizeof(slnode));
n->data=y;
m=search(p,x);
if(m!=null)
{n->next=m->next;
m->next=n;
return(0);
}
else
{printf(" %c not found.\n",x);
return(-1);
}
}
void travel(slnode *p)
{slnode *s;
s=p->next;
while(s!=null)
{
putchar(s->data);
s=s->next;
}
putchar('\n');}
main()
{int i,ch1,ch2,n;
slnode *q,*p;
initiate(&p);
for(i=1;i<4;i++)
{printf("ch%d=",i);
ch1=getchar();
getchar();
append(p,ch1);
printf("point ch%d=%c\n",i,ch1);
}
travel(p);
printf("ch1=");
ch1=getchar();
getchar();
printf("ch2=");
ch2=getchar();
getchar();
insert(p,ch1,ch2);
travel(p);
}
实验二 栈和队列
[实验目的]
1．了解顺序栈的结构特点及有关概念，掌握顺序栈建立及入栈的基本操作。
2．了解顺序栈共用的含义及优点，掌握顺序战的基本操作。
[实验内容]
进行顺序栈初始化及入栈、出栈、共用，实现顺序栈建立及入栈、出栈、共用的基本操作。
[实验要点及说明]
栈(stack)：是限定仅在表尾进行插入或删除操作的线性表。
栈顶(Top)：允许插入和删除的一端，为变化的一端。
栈底(Bottom):栈中固定的一端。
空栈：栈中无任何元素。
特点：根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。也就是说，栈是一种后进先出(Last In First Out)的线性表，简称为LIFO表。
栈的运算：
1.初始化栈：Void initstack(＆s)
将栈S置为一个空栈(不含任何元素)。
2.进栈：Void Push(&s,x)
将元素X插入到栈S中，也称为 “入栈”、 “插入”、 “压入”。
3.出栈：elemtype Pop(&s)
删除栈S中的栈顶元素，也称为”退栈”、 “删除”、 “弹出”。
4.取栈顶元素： Elemtype gettop(s)
取栈S中栈顶元素。
5.判栈空：Int empty(s)
判断栈S是否为空，若为空，返回值为1，否则返回值为0。
6. 置空栈：void clearstack(&s)
顺序栈的数据类型：
#define stacksize 100 //定义栈的最大容量为maxlen
Typedef int elemtype;
typedef Struct{
elemtype data[stacksize+1]; //将栈中元素定义为elemtype类型
int top; //:指向栈顶位置的指针
}sqstack;
[参考程序]
1．顺序栈初始化及入栈
#include <stdio.h>
#define max 10
typedef struct
{char stack[max];
int top;
}qstype;
void initiateqs(qstype *s)
{s->top=- 1;
}
int push(qstype *s,int x)
{if(s->top>=max- 1)
return(0);
else
{s->top++;
s->stack[s->top]=x;
return(1);
}
}
main()
{
int ch,sign;
qstype *s;
initiateqs(s);
printf(">");
scanf("%d",&ch);
while(ch!=-1)
if((sign=push(s,ch))==0)
{
printf(" overflow\n" );
break; }
else
scanf(" %d",&ch);
while(s->top!= 1)
{
s->top--;
printf("stack=%d\n",s->stack[s->top+ 1]);
}
printf("\n");
}
2．顺序栈初始化及出栈
#include <stdio.h>
#define max 10
typedef struct
{char stack[max];
int top;
}qstype;
void initiateqs(qstype *s)
{s->top= 1; }
int push(qstype *s,int x)
{if(s->top>=max- 1)
return(0);
else
{s->top++;
s->stack[s->top]=x;
return(1);}
}
int pop(qstype *s)
{if(s->top<0)
return('\0');
else
{s->top--;
return(s->stack[s->top+1]);
}
}
main()
{
int ch,sign;
qstype *s;
initiateqs(s);
printf(">");
scanf("%d",&ch);
while(ch!= -1 )
{if((sign=push(s,ch))!=1)
break;
scanf(" %d",&ch);
}
while((ch=pop(s))!='\0')
printf("%d",ch);
printf("\n");
}
3．顺序栈的共用
#include<stdio.h>
#define m 40
typedef struct
{int top[2];
int stack[m];
}dqstype;
void initiatedqs(dqstype *s)
{s->top[0]= 1;
s->top[1]=m;}
int pushdqs(dqstype *s,int i,int x)
{if(s->top[0]==s->top[1]-1)
{printf("full");
return(-1);
}
if(i!=0&&i!=1)
{printf("mistake");
return(-1);
}
if(i==0)
{s->top[i]++;
s->stack[s->top[i]]=x;
}
else
{s->top[i]--;
s->stack[s->top[i]] =x;
}
return(1);
}
int popdqs(dqstype *s,int i)
{if(i!=0&&i!=1)
{printf("mistake");
return('\0');
}
if(i==0){
if(s->top[i]<=- 1)
{printf("\nstrack0 empty");
return('\0');
}
s->top[i]--;
return(s->stack[s->top[i]+ 1]);
}
else
{if(s->top[i]==m)
{printf("\nstrack1 empty.");
return('\0');
}
s->top[i]++;
return(s->stack[s->top[i]-1]);
}
}
main()
{
int sign,i,ch;
dqstype *s;
initiatedqs(s);
printf("please enter stack i=");
scanf(" %d",&i);
getchar();
printf("%");
while((ch=getchar()) !='\n')
if((sign==pushdqs(s,i,ch)) != 1 )
break;
printf("please enter other stack i=");
scanf("%d",&i);
getchar();
printf(">");
while((ch=getchar()) !='\n')
if((sign=pushdqs(s,i,ch))!= 1 )
break;
printf("\nstack0 data out:\n");
while((ch=popdqs(s,0))!='\0')
printf(" %c",ch);
printf("\n");
printf("\nstack1 data out:\n");
while((ch=popdqs(s,1))!='\0')
printf("%c",ch);
printf( "\n");
}
实验三 稀疏矩阵的转置
[实验目的]
熟悉数组的有关概念，学习掌握稀疏矩阵的三元组存储结构的转置方法。
[实验内容]
已知一稀疏矩阵，用三元组a[10][3]存储此矩阵，然后将其转置并存储到b[10][3]。
[实验要点及说明]
1． 矩阵的压缩存储：所谓压缩存储是指为多个值相同的元只分配一个存储空间；对零元不分配空间。
2． 如何进行稀疏矩阵的压缩存储？
按照压缩存储的概念，只存储稀疏矩阵的非零元。因此，除了存储非零元的值之外，还必须同时记下它所在行和列的位置（i, j）。反之，一个三元组（i, j, aij）唯一确定了矩阵A的一个非零元。由此，稀疏矩阵可由表示非零元的三元组及其列数唯一确定。
[实验要求与步骤]
1． 基本要求：将矩阵的行列值相互交换，将每个三元组中的i和j相互调换，重排三元组之间的次序，这样便可实现矩阵的转置；
2． 测试数据：
0 3 1 0
M= 1 0 0 0
0 2 0 1
矩阵M与其对应的三元组a
3． 实现提示：三元组a中，a[0][0]、a[0][1]和a[0][2]分别代表稀疏矩阵的行数、列数和非零元素个数，a[i][0]、a[i][1]和a[i][2]（1≤i≤a[0][2]）分别代表非零元素的行数、列数和非零元素值。三元组b代表转置矩阵，其含义与三元组a相同；
4． 按要求编写程序；
5． 上机录入程序，并进行编辑、编译、调试，直到运行成功。
[参考程序]
1．带回溯的转置程序
#include "stdio.h"
main()
{
int a[10][3]={{3,4,5},{1,2,3},{1,3,1},{2,1,1},{3,2,2},{3,4,1}};
int b[10][3];
int i,j,q,l,p;
b[0][0]=a[0][1];
b[0][1]=a[0][0];
b[0][2]=a[0][2];
if(b[0][2]!=0)
{q=1;
for (l=1;l<=a[0][1];l++)
for (p=1;p<=a[0][2];p++)
if(a[p][1]==l)
{
b[q][1]=a[p][0];
b[q][0]=a[p][1];
b[q][2]=a[p][2];
q++;
}
}
printf("\n\n output data:\n");
for(i=0;i<=b[0][2];i++)
{for(j=0;j<=2;j++)
printf(" %d",b[i][j]);
printf("\n");
}}
2．不带回溯的转置程序
#include "stdio.h"
int a[10][3]={{3,4,5},{1,2,3},{1,3,1},{2,1,1},{3,2,2},{3,4,1}};
int b[10][3],pot[10];
int i,j,q,col;
main()
{b[0][0]=a[0][1];
b[0][1]=a[0][0];
b[0][2]=a[0][2];
if(b[0][2]!=0)
{for (col=2;col<=a[0][1]+1;col++)
pot[col]=0;
for(i=1;i<=a[0][2];i++)
{col=a[i][1];
pot[col+1]=pot[col+1]+1;
}
pot[1]=1;
for(i=2;i<=a[0][1];i++)
pot[i]=pot[i-1]+pot[i];
for(i=1;i<=a[0][2];i++)
{col=a[i][1];
q=pot[col];
b[q][0]=a[i][1];
b[q][1]=a[i][0];
b[q][2]=a[i][2];
pot[col]=pot[col]+1;
}
printf("\n\noutput data:\n");
for(i=0;i<=b[0][2];i++)
{for(j=0;j<=2;j++)
printf(" %d",b[i][j]);
printf("\n");
}}}
实验四 用递归算法遍历二叉树
[实验目的]
学习掌握二叉树各种遍历方法的基本操作算法。
[实验内容]
建立一棵二叉树，并用递归算法分别用前序、中序和后序遍历之。
[实验要点及说明]
由于二叉树的定义是递归的，因而一棵非空二叉树可以看作是由根结点、左子树和右子树这三个基本部分组成的。如果能依次遍历这三个部分的信息，也就遍历了整个二叉树。由此得到的二叉树的遍历是按某种策略访问二叉树中的每一个结点且仅访问一次的过程。二叉树的遍历按访问根结点的先后次序不同分为前序、中序和后序三种。
前序遍历二叉树的操作定义为：
若二叉树为空，则空操作；否则
（1）访问根结点；
（2）前序遍历左子树；
（3）前序遍历右子树。
中序遍历二叉树的操作定义为：
若二叉树为空，则空操作；否则
（1）中序遍历左子树；
（2）访问根结点；
（3）中序遍历右子树。
后序遍历二叉树的操作定义为：
若二叉树为空，则空操作；否则
（1）后序遍历左子树；
（2）后序遍历右子树；
（3）访问根结点。
[实验要求与步骤]
1． 基本要求：采用递归算法实现前序、中序和后序遍历；
2． 测试数据：
3． 实现提示：二叉树的遍历是指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且只被访问一次；
4． 按要求编写程序；
5． 上机录入程序，并进行编辑、编译、调试，直到运行成功。
[参考程序]
#include<stdio.h>
#define null 0
int counter=0;
typedef struct btreenode
{int data;
struct btreenode *lchild;
struct btreenode *rchild;
}bnode;
bnode *p;
bnode *creat(int x,bnode *lbt, bnode *rbt)
{bnode *p;
p=(bnode*)malloc(sizeof(bnode));
p->data=x;
p->lchild=lbt;
p->rchild=rbt;
return(p);
}
bnode *ins_lchild(bnode *p,int x)
{bnode *q;
if(p==null)
printf("Illegal insert.");
else
{q=(bnode*)malloc(sizeof(bnode));
q->data=x;
q->lchild=null;
q->rchild=null;
if(p->lchild!=null)
q->rchild=p->lchild;
p->lchild=q;
}
}
bnode *ins_rchild(bnode *p,int x)
{bnode *q;
if(p==null)
printf("Illegal insert.");
else
{q=(bnode*)malloc(sizeof(bnode));
q->data=x;
q->lchild=null;
q->rchild=null;
if(p->rchild!=null)
q->lchild=p->rchild;
p->rchild=q;
}}
void prorder(bnode*p)
{if(p==null)
return;
printf("%d\t%u\t%d\t%u\t%u\n",++counter,p,p->data,p->lchild,p->rchild);
if(p->lchild!=null)
proder(p->lchild);
if(p->rchild!=null)
proder(p->rchild);
}
void preorder(bnode *p)
{if(p==null)
return;
printf("%d",p->data);
if(p->lchild!=null)
preoder(p->lchild);
if(p->rchild!=null)
preoder(p->rchild);
}
void inorder(bnode *p)
{if(p==null)
return;
if(p->lchild!=null)
inoder(p->lchild);
printf("%d",p->data);
if(p->rchild!=null)
inoder(p->rchild);
}
void postorder(bnode *p)
{if(p==null)
return;
if(p->lchild!=null)
postoder(p->lchild);
if(p->rchild!=null)
postoder(p->rchild);
printf("%d",p->data);
}
main()
{bnode *bt,*p,*q;
int x;
printf("Input root:");
scanf("%d",&x);
p=creat(x,null,null);
bt=p;
scanf("%d",&x);
while(x!=-1)
{p=bt;
q=p;
wihle(x!=p->data&&q!=null)
{
p=q;
if(x<p->data)
q=p->lchild;
else
q=p->rchild;
}
if(x==p->data)
{printf("The data is exit.");
return;
}
else
{if(x<p->data)
ins_lchild(p,x);
else
ins_rchild(p,x);}
scanf("%d",&x);
}
p=bt;
printf("structure of the binary tree:\n");
printf("number\taddress\tdata\tlchild\trchild\n");
prorder(p);
printf("preorder:");
preorder(p);
printf("\n");
printf("inorder:");
inorder(p);
printf("\n");
printf("postorder:");
postorder(p);
printf("\n");
}
实验五 求哈夫曼编码
[实验目的]
学习掌握构造哈夫曼树的方法及哈夫曼编码的生成。
[实验内容]
输入一串叶结点的权值，建立一棵哈夫曼树，并求出每个叶结点的哈夫曼编码。
[实验要点及说明]
1．结点路径长度：由根结点到某个结点所经过的树的分支个数。
2．二叉树路径长度：由根结点到所有叶结点的路径长度之和。
3．二叉树的带权路径长度：设二叉树具有n个带权值的叶结点，那么从根结点到各叶结点的路径长度与相应结点权值的乘积的和即为二叉树的带权路径长度。
4．哈夫曼树：对于一组带有确定权值的叶结点，其构造出的不同的二叉树其带权路径长度并不相同，我们把其中具有最小带权路径长度的二叉树称作哈夫曼树。
[实验要求与步骤]
1．基本要求：哈夫曼编码规则：在所构造的哈夫曼树中，所有向左路径的分支规定为0，所有向右路径的分支规定为1；
2．测试数据：叶结点个数： n=4 ； 叶结点权值： 7 5 3 1 ；
3． 实现提示：写程序时每次都选取未构造过的权值最小的叶子结点来构造哈夫曼树，最后根据哈夫曼编码规则求出哈夫曼编码；
4． 按要求编写程序；
5． 上机录入程序，并进行编辑、编译、调试，直到运行成功。
[参考程序]
#include <stdio.h>
#define max 1000
#define maxsymbs 30
#define maxbits 10
#define maxnode 59
typedef struct
{int weight;
int flag;
int parent;
int lchild;
int rchild;
}huffnode;
typedef struct
{int bits[maxbits];
int start;
}huffcode;
main()
{huffnode huff_node[maxnode];
huffcode huff_code[maxsymbs],cd;
int i,j,m1,m2,x1,x2,n,c,p;
char symbs[maxsymbs],symb;
printf("n=");
scanf("%d",&n);
for(i=0;i<2*n-1;i++)
{huff_node[i].weight=0;
huff_node[i].parent=-1;
huff_node[i].flag=0;
huff_node[i].lchild=-1;
huff_node[i].rchild=-1;
}
printf(">");
for(i=0;i<n;i++)
scanf("%d",&huff_node[i].weight);
for(i=0;i<n-1;i++)
{m1=m2=max;
x1=x2=0;
for(j=0;j<n+i;j++)
{if(huff_node[j].weight<m1&&huff_node[j].flag==0)
{m2=m1;
x2=x1;
m1=huff_node[j].weight;
x1=j;
}
else
if(huff_node[j].weight<m2&&huff_node[j].flag==0)
{m2=huff_node[j].weight;
x2=j;
}
}
huff_node[x1].parent=n+i;
huff_node[x2].parent=n+i;
huff_node[x1].flag=1;
huff_node[x2].flag=1;
huff_node[n+i].weight=huff_node[x1].weight+huff_node[x2].weight;
huff_node[n+i].lchild=x1;
huff_node[n+i].rchild=x2;
}
for(i=0;i<n;i++)
{cd.start=n;
c=i;
p=huff_node[c].parent;
while(p!=-1)
{if(huff_node[p].lchild==c)
cd.bits[cd.start]=0;
else
cd.bits[cd.start]=1;
cd.start=cd.start-1;
c=p;
p=huff_node[p].parent;
}
for(j=cd.start+1;j<=n;j++)
huff_code[i].bits[j]=cd.bits[j];
huff_code[i].start=cd.start;
}
for(i=0;i<n;i++)
{printf("%d",huff_node[i].weight);
for(j=huff_code[i].start+1;j<=n;j++)
printf("%d",huff_code[i].bits[j]);
printf("\n");
}
}
实验六 图遍历的演示
[实验目的]
学习掌握图的两种搜索路径的遍历。
[实验内容]
试写一个程序，演示在连通的无向图上遍历全部结点的操作
[实验要点及说明]
1． 深度优先搜索遍历图的算法：首先访问指定的起始顶点 v0，从v0出发，访问v0的一个未被访问过的邻接顶点w1，再从w1出发，访问w1的一个未被访问过的顶点w2，然后从w2出发，访问w2的一个未被访问过的邻接顶点w3，依次类推，直到一个所有邻接点都被访问过为止。
2． 广度优先搜索遍历图的算法：首先访问指定的起始顶点 v0，从v0出发，访问v0的所有未被访问过的邻接顶点w1，w2，…，wk，然后再依次从w1，w2，…，wk出发，访问它们的所有未被访问过的邻接顶点，依次类推，直到图中所有未被访问过的邻接顶点都被访问过为止。
[实验要求与步骤]
1． 基本要求：采用邻接表作存储结构，实现连通无向图的深度优先搜索遍历和广度优先搜索遍历。
2． 测试数据：如下图：
3． 实现提示：根据广度优先搜索的规则，在其算法实现中，借助一个队列g-queque来存放已被访问过的顶点。从指定顶点开始，每访问一个顶点，就将它入队并排在队尾，然后从队头取出一个顶点，访问该顶点的所有未被访问的邻接点，依次类推，直至队列为空且图中结点均被访问过为止；
4． 按要求编写程序；
5． 上机录入程序，并进行编辑、编译、调试，直到运行成功。
[参考程序]
1、深度优先搜索遍历图
#include<stdio.h>
#include<stdlib.h>
#define maxnode 40
#define null 0
typedef struct st_arc
{int adjvex;
int weight;
struct st_arc *nextarc;
}arcnode;
typedef struct
{int vertex;
struct st_arc *firstarc;
}vernode;
typedef vernode adjlist[maxnode];
void trave(adjlist g,int n)
{int i,visited[maxnode];
void dfs();
for(i=0;i<n;i++)
visited[i]=0;
for(i=0;i<n;i++)
if(visited[i]==0)
dfs(g,i,visited);
}
void dfs(adjlist g, int k,int visited[])
{arcnode *p;
int w;
visited[k]=1;
printf("%d",g[k].vertex);
p=g[k].firstarc;
while(p!=null)
{w=p->adjvex;
if(visited[w]==0)
dfs(g,w,visited);
p=p->nextarc;
}}
main()
{int i,j,n,k,v;
arcnode *p,*q;
adjlist g;
printf("Input node: ");
scanf("%d",&n);
for(k=0;k<n;k++)
{printf("node%d=",k);
scanf("%d",&g[k].vertex);
g[k].firstarc=null;
}
for(;;)
{printf("Insert edge i-j:");
scanf("%d",&i);
scanf("%d",&j);
if(i==-1&&j==-1)
break;
q=(arcnode*)malloc(sizeof(arcnode));
q->adjvex=j;
q->nextarc=g[i].firstarc;
g[i].firstarc=q;
p=(arcnode*)malloc(sizeof(arcnode));
p->adjvex=i;
p->nextarc=g[j].firstarc;
g[j].firstarc=p;
}
printf("dfs:");
trave(g,n);
printf("\n");
}
2、广度优先搜索遍历图
#include<stdio.h>
#include<stdlib.h>
#define null 0
#define maxnode 40
typedef struct st_arc
{int adjvex;
int weight;
struct st_arc *nextarc;
}arcnode;
typedef struct
{int vertex;
struct st_arc *firstarc;
}vernode;
typedef vernode adjlist[maxnode];
typedef struct
{int queue[maxnode];
int front,rear;
}qqtype;
void initiate(qqtype *q)
{q->front=-1;
q->rear=-1;
}
int enter(qqtype *q, int x)
{if(q->rear==maxnode-1)
return(-1);
else
{q->rear++;
q->queue[q->rear]=x;
return(0);
}}
int delete(qqtype *q )
{if(q->front==q->rear)
return(null);
else
{q->front++;
return(q->queue[q->front]);
}}
int emtype(qqtype *q)
{if(q->front==q->rear)
return(-1);
return(0);
}
void bfs(adjlist g,int k,int visited[])
{arcnode *p;
int w;
initiate(g);
visited[k]=1;
printf("%d",g[p->adjvex].vertex);
enter(g,k);
while(emtype(g)==0)
{w=delete(g);
p=g[w].firstarc;
while(p!=null)
{if(visited[p->adjvex]==0)
{printf("%d",g[p->adjvex].vertex);
visited[p->adjvex]=1;
enter(g,p->adjvex);
}
p=p->nextarc;
}}}
void trave(adjlist g,int n)
{int i, visited[maxnode];
for(i=0;i<n;i++)
visited[i]=0;
for(i=0;i<n;i++)
if(visited[i]==0)
bfs(g,i,visited);
}
main()
{int i,j,n,k,v;
arcnode *p,*q;
adjlist g;
printf("Input node:");
scanf("%d",&n);
for(k=0;k<n;k++)
{printf("node%d=",k);
scanf("%d",&g[k].vertex);
g[k].firstarc=null;
}
for(;;)
{printf("Insert edge i-j:");
scanf("%d",&i);
scanf("%d",&j);
if(i==-1&&j==-1)
break;
q=(arcnode*)malloc(sizeof(arcnode));
q->adjvex=j;
q->nextarc=g[i].firstarc;
g[i].firstarc=q;
p=(arcnode*)malloc(sizeof(arcnode));
p->adjvex=i;
p->nextarc=g[j].firstarc;
g[j].firstarc=p;
}
printf("bfs:");
trave(g,n);
printf("\n");
}
实验七 查找
[实验目的]
学习掌握查找的过程及方法。
[实验内容]
1． 实现顺序查找，在输入的数组纪录中顺序查找所需的纪录。
2． 用二分查找，也称折半查找方法，对已知的有序序列进行查找。
3．将一个记录用一棵二叉树表示，并查找其中某一个记录。
[实验要点及说明]
1．顺序查找是一种简单的查找方法。从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和待找的值Ｋ相比较，若相等，则查找成功，若整个表扫描完毕，仍末找到关键字等于Ｋ的元素，则查找失败。顺序查找既适用于顺序表，也适用于链表。若用顺序表，查找可从前往后扫描，也可从后往前扫描，但若采用单链表，则只能从前往后扫描。另外，顺序查找的表中元素可以是无序的。
2．二分查找是一种高效率的查找方法。但二分查找有条件限制：要求表必须用向量作存贮结构，且表中元素必须按关键字有序(升序或降序均可)。基本思想是：首先将待查值K与有序表R[1]到R[n]的中点mid上的关键字R[mid].key进行比较，若相等，则查找成功；否则，若R[mid].key>k ， 则在R[1]到R[mid-1]中继续查找，若有R[mid].key<k ， 则在R[mid+1]到R[n]中继续查找。每通过一次关键字的比较，区间的长度就缩小一半，区间的个数就增加一倍，如此不断进行下去，直到找到关键字为K的元素；若当前的查找区间为空(表示查找失败)。
3．用整个二叉排序树表示一个集合，树中的一个结点对应预集合中的一个记录。二叉排序树种的每个结点所存储的纪录的关键字都大于它的左子树上所有结点记录的关键字，而小于或等于它的右子树上所有结点记录的关键字。查找是使用递归算法：若二叉排序树为空，则查找 失败，否则，先拿根结点值与待查值进行比较，若相等，则查找成功，若根结点值大于待查值，则进入左子树重复此步骤，否则，进入右子树重复此步骤，若在查找过程中遇到二叉排序树的叶子结点时，还没有找到待找结点，则查找不成功。
[实验要求与步骤]
1． 基本要求：至少做出一个。
2． 测试数据：由学生自由设定。
3． 按要求编写程序；
4． 上机录入程序，并进行编辑、编译、调试，直到运行成功。
[参考程序]
1．顺序查找
#include <stdio.h>
#define max 20
int seqsearch(int s[],int k,int n)
{
int i;
s[n]=k;
i=0;
while(s[i]!=k)
i++;
if(i<n)
{printf("Find it.");
return(i);
}
else
{printf("Not find it.");
return(-1);
} }
int getdata(int list[])
{int num,i;
printf("total=");
scanf(" %d",&num);
for(i=0;i<num;i++)
{printf("data[%d]=",i);
scanf(" %d",&list[i]);
}
return(num);}
main()
{int list[max],n,index,x;
n=getdata(list);
printf("search key=");
scanf(" %d",&x);
index=seqsearch(list,x,n);
if(index>=0)
printf(" data [ %d] =%d\n ",index,x);
else
printf(" %d:not found.\n",x);
}
2．二分查找
#include <stdio.h>
#define max 20
int binary(int x,int list[],int n)
{int low,high,mid;
low=0;
high=n-1;
while(low<=high)
{mid=(low+high)/2;
if(x<list[mid])
high=mid-1;
else
if(x>list[mid])
low=mid+1;
else
return(mid);
}
return(-1);
}
int getdata(int list[])
{int num,i;
printf("total=");
scanf("%d",&num);
for(i=0;i<num;i++)
{printf("data[%d]=",i);
scanf(" %d",&list[i]);
}
return(num);
}
main()
{int list[max],n,index,x;
n=getdata(list);
printf("search key=");
scanf(" %d",&x);
index=binary(x,list,n);
if(index>=0)
printf("data[%d]=%d\n",index,x);
else
printf("%d:not fonnd\n",x);
}
3．二叉数查找
#include <stdio.h>
#define null 0
typedef struct btreenode
{int data;
struct btreenode *lchild;
struct btreenode *rchild;
}bnode;
bnode *p;
bnode *creat(int x,bnode *lbt,bnode *rbt)
{bnode *p;
p=(bnode* )malloc(sizeof(bnode));
p->data=x;
p->lchild=lbt;
p->rchild=rbt;
return(p);
}
bnode *ins_lchild(bnode *p,int x)
{bnode *q;
if(p==null)
printf("Illegal insert.");
else
{ q=(bnode* )malloc(sizeof(bnode));
q->data=x;
q->lchild=null;
q->rchild=null;
if(p->lchild!=null)
q->rchild=p->lchild;
p->lchild=q;
}
}
bnode *ins_rchild(bnode *p,int x)
{bnode *q;
if(p==null)
printf("lllegal insert");
else
{q=(bnode*)malloc(sizeof(bnode));
q->data=x;
q->lchild=null;
q->rchild=null;
if(p->rchild!=null)
q->lchild=p->rchild;
p->rchild=q;
}
}
void prorder(bnode *p,int counter)
{if(p==null)
return;
counter++;
printf("%d\t%u\t%d\t%u\t%u\n",counter,p,p->data,p->lchild,p->rchild);
if(p->lchild!=null)
prorder(p->lchild,counter);
if(p->rchild!=null)
prorder(p->rchild,counter);
}
bnode *bs_search(bnode *t,int k)
{
bnode *s;
if(t==null)
{printf("empty tree.");
return(t);
}
s=t;
if(s->data==k)
{printf("Find it.");
return(s);
}
else
if(s->data>k)
return(bs_search(s->lchild,k) );
else
return(bs_search(s->rchild,k));
}
main()
{int k;
bnode *bt,*p,*q;
int x,counter=0;
printf("lnput root:");
scanf("%d",&x);
p=creat(x,null,null);
bt=p;
scanf("%d",&x);
while(x!=-1)
{p=bt;
q=p;
while(x!=p->data&&q!=null)
{p=q;
if(x<p->data)
q=p->lchild;
else
q=p->rchild;
}
if(x==p->data)
{printf("The data is exit.");
return;
}
else
if(x<p->data)
ins_lchild(p,x);
else
ins_rchild(p,x);
scanf("%d",&x);
}
p=bt;
prorder(p,counter);
printf("Search key=");
scanf(" %d",&k);
q=bs_search(p,k);
printf("q=%u",q);
printf("%n");
}
实验八 内部排序算法
[实验目的]
学习掌握各种排序方法的排序过程及其实现算法。
[实验内容]
实现常用的内部排序算法并进行比较：起泡排序、直接插入排序、简单选择排序、快速排序。试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。
[实验要点及说明]
1． 起泡排序的基本思想是：将待排序列中第一个记录的关键字R1.Key与第二个记录的关键字R2.Key作比较，如果R1.Key大于R2.Key，则交换记录R1和R2在序列中的位置，否则不交换；然后继续对当前序列中的第二个记录和第三个记录作同样的处理，依次类推，直到序列中倒数第二个记录和最后一个记录比较完为止，则第一趟排序结束，这时找出的最大记录排在序列的倒数第一个位置（n位置）上。随后，再对其前面的n-1个记录做第二趟排序，找出次大记录排在序列的倒数第二个位置（n-1位置）上……如此排序过程进行n-1趟就像冒泡一样，最终将初始序列按升序排列完成。
2． 直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。
3． 简单选择排序：一趟简单选择排序的操作为：通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1≤i≤n）个记录交换之。
4． 快速排序方法的基本思想是：从待排序列的n个记录中任意选取一个记录Ri（通常选取序列中的第一个记录）作标准，调整序列中各个记录的位置，使排在Ri前面的记录的关键字都小于Ri. Key，排在Ri后面的记录的关键字都大于Ri. Key。
[实验要求与步骤]
1． 基本要求：待排序表的表长不小于100；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。至少选作一个。
2． 测试数据：例如：初始序列 64 5 7 89 6 24。由学生自己给出。
3． 实现提示：主要工作是设法在已知算法中的适当位置插入对关键字的比较次数和移动次数的计数操作。程序还可以考虑几组数据的典型性，如正序、逆序和不同程度的乱序。注意采用分块调试的方法；
4． 按要求编写程序；
5． 上机录入程序，并进行编辑、编译、调试，直到运行成功。
[参考程序]
1．直接插入排序
#include<stdio.h>
#define max 40
typedef struct
{int key;
char name;
}elemtype;
elemtype x[max];
void getsort(elemtype x[],int n)
{int i;
printf("Recorder:" );
for(i=0;i<n;i++)
scanf("%d",&x[i].key);}
void hubblesort(elemtype x[],int n)
{int i,j,k,flag;
elemtype swap;
flag=1;
for(i=1 ;i<n&&flag==1;i++)
{flag=0;
for(j=0;j<n-i;j++)
if(x[j].key>x[j+1].key)
{flag=1;
swap=x[3];
x[j]=x[j+1];
x[j+1]=swap;
}
if(flag==0)
return;}
}
main()
{elemtype x[max];
int n,i;
printf("n=");
scanf(" %d",&n);
getsort(x,n);
hubblesort(x,n);
printf("Output the number:");
for(i=0;i<n;i++)
printf("%d\t",x[i]);
printf("\n");
}
2．直接选择排序
#include <stdio.h>
#define max 40
typedef struct
{int key;
char name;
}elemtype;
elemtype x[max];
void getsort(elemtype x[],int n)
{int i;
printf("Recorder:");
for(i=0;i<n;i++)
scanf(" %d",&x[i].key);}
void selectsort(elemtype x[],int n)
{int i,j,small,k,m;
elemtype swap;
for(i=0;i<n-1;i++)
{small=i;
for(j=i;j<n;j++)
if(x[j].key<x[small].key)
small=j;
if(small!=i)
{swap=x[i];
x[i]=x[small];
x[small]=swap;
}
m=i+1;
printf("No.%d selectsort:\t",m);
for(k=0;k<n;k++)
printf(" %d\t ",x[k].key);
printf("\n");
}}
main()
{elemtype x[max];
int n;
printf("n=");
scanf("%d",&n);
getsort(x,n);
selectsort(x,n);
}
3．冒泡排序
#include<stdio.h>
#define max 40
typedef struct
{int key;
char name;
}elemtype;
elemtype x[max];
void getsort(elemtype x[],int n)
{int i;
printf("Recorder:" );
for(i=0;i<n;i++)
scanf("%d",&x[i].key);}
void hubblesort(elemtype x[],int n)
{int i,j,k,flag;
elemtype swap;
flag=1;
for(i=1 ;i<n&&flag==1;i++)
{flag=0;
for(j=0;j<n-i;j++)
if(x[j].key>x[j+1].key)
{flag=1;
swap=x[3];
x[j]=x[j+1];
x[j+1]=swap;
}
if(flag==0)
return;}
}
main()
{elemtype x[max];
int n,i;
printf("n=");
scanf(" %d",&n);
getsort(x,n);
hubblesort(x,n);
printf("Output the number:");
for(i=0;i<n;i++)
printf("%d\t",x[i]);
printf("\n");
}