实验指导
第一章 C语言相关知识复习实验
1.1 C语言结构体与指针
一、实验目的
巩固复习前期所学C语言的函数参数传递、指针和结构体等知识点，加强学习数据结构语言基础。
二、实验内容
1.学生信息的显示，具体要求如下：
1)定义一个结构体描述学生信息(学号,姓名,性别,年龄,住址);
2)设计一个函数，用于显示单个学生信息，函数的参数为前面定义的结构体类型;
3)设计一个主函数，在主函数中输入学生的信息，并调用前面定义的函数进行显示(学生人数不少于5人)。
提示：可用结构体数组保存学生信息。
2. 输入若干个整数作为数组元素值，然后按输入时顺序的就地逆置排序，最后打印出逆置后的元素值。要求用指针和动态内存分配方法实现。例如输入：10 2 30 4 5，逆置后显示为：5 4 302 10。
提示：
1.逆置的方法：设有n个数据元素a(0),a(1),a(2)…….,a(n-1)，将第i个元素与第n-i-1个元素调换位置即可。
2.采用动态内存分配方法可参考如下代码
int *a;
int i;
a=(int *)malloc(N*sizeof(int));//动态分配起始地址
for(i=0;i
{ scanf("%d",&a[i]);}//给内存空间赋值
三、实验源代码
此处写程序源代码，请在程序中适当注释，便于老师更快地看懂你的程序。
四、实验结果
此处写出程序运行的结果，即输入数据是什么，输出数据是什么，分析结果是否正确，如果不正确是什么原因。
第二章 线性表实验
2.2顺序表的建立与查找
一、实验目的
1、掌握建立顺序表的基本方法。
2、理解和掌握顺序表元素查找算法。
3、掌握顺序表的插入、删除算法的思想和实现。
二、实验内容
1、 建立一个顺序表，要求从键盘输入10个整数，并将该顺序表的元素从屏幕显示出来
2、编写查找函数，在上面的顺序表中查找其中一个元素，如果找到，返回该元素在顺序表中的位置和该元素的值，否则提示无此元素。要求被查找元素从键盘输入。
3、编写插入和删除函数，由用户输入待插入元素及插入位置，将完成插入后的顺序表输出;由用户输入删除第几个元素，将完成删除后的顺序表输出。
以下是程序部分代码，请调试并补充使之正确运行：
#include
#include
#define MAXSIZE 10
typedef struct{
int *elem;
int length;
}SqList;
main()
{int i,x,y;
int LocateElem_Sq(SqList L,int e);
printf("请输入顺序表的长度");
scanf("%d",&ST.length);
ST.elem=(int*)malloc(sizeof(int)*ST.length);
for(i=0;i<=ST.length-1;i++)
{ST.elem[i]=rand()%100;
printf("%d ",ST.elem[i]);
}
printf("请输入你要查找的数");
scanf("%d",&x);
y=LocateElem_Sq(x);
printf("%d",y);
printf("请输入你要插入的位置及元素值");
scanf("%d,%d",&i,&x);
y=ListInsert_Sq(&ST,i,x);
for(i=0;i
printf("%d ",ST.elem[i]);
}
int LocateElem_Sq(SqList L,int e)
{int i,*p;
i=1;
p=L.elem;
while(i<=L.length && *p++!=e) ++i;
if(i<=L.length)return i;
else return 0;
}
int ListInsert_Sq(SqList *L,int i,int e)
{int j;
for(j=L->length;j>=i;j--)
L->elem[j+1]=L->elem[j];
L->elem[i]=e;
++L->length;
return 1;
}
上述代码仅供参考，其中有的地方有错误，需要修改。请读懂以上代码，体会顺序表操作的C语言实现，注意函数调用过程中参数的值传递和地址传递。在此基础上完成顺序表的删除操作。
删除操作函数定义为：int ListDelete_Sq(SqList *L,int i)。
注意：其中顺序表的数据是随机产生，请考虑如何设计从键盘输入。
三、实验源代码
四、实验结果
2.4单链表的基本操作
一、实验目的
1、理解和掌握单链表的类型定义方法和结点生成方法。
2、掌握建立单链表和显示单链表元素的算法。
3、掌握单链表的插入和删除算法。
二、实验内容
1、建立一个单链表，并从屏幕显示单链表元素列表。
2、删除链表某位置上的元素，并保持链表原有的顺序不变，请在给出的程序中加入一个删除函数，实现上述功能要求。ElemType delete_L(LNode *L,int i)为删除函数的原型，L表示链表，i表示插入位置。注意菜单中给出了菜单项，请在switch语句给出调用语句，在主函数中加入删除函数，并注意判断表为空的情况。
提示：线性表的链表存储表示(结构)及实现如下，阅读下列程序请注意几个问题：
(1)关于线性表的链表存储结构的本质是：在逻辑上相邻的两个数据元素a[i-1], a[i]，在存储地址中可以不相邻，既地址不连续(当然也可以相邻)。
typedef struct LNode
{ ElemType data; /* 数据子域 */
struct LNode *next; /* 指针子域 */
}LNode; /* 结点结构类型 */
(2)本程序是一个比较完整的(挖去了删除函数)、子函数较多的源程序。目的为同学们提供一个示范，提供关于链表操作的资料，供学生参考，在理解程序的整体后，加入挖去的删除函数。本程序中使用菜单设计方法，此方法也可为其他程序所用。
[源程序]
#include
#include
#include
typedef int ElemType;
typedef struct LNode
{ ElemType data; /* 数据子域 */
struct LNode *next; /* 指针子域 */
}LNode; /* 结点结构类型 */
LNode *L;
/* 函数声明 */
LNode *creat_L();
void out_L(LNode *L);
void insert_L(LNode *L,int i ,ElemType e);
ElemType delete_L(LNode *L,int i);
int locat_L(LNode *L,ElemType e);
/* 主函数 */
main()
{ int i,k,loc; ElemType e,x; char ch;
do { printf("\n\n\n");
printf("\n\n 1. 建立线性链表 ");
printf("\n\n 2. 在i位置插入元素e");
printf("\n\n 3. 删除第i个元素，返回其值");
printf("\n\n 4. 查找值为 e 的元素");
printf("\n\n 5. 结束程序运行");
printf("\n======================================");
printf("\n 请输入您的选择 (1,2,3,4,5)"); scanf("%d",&k);
switch(k)
{
case 1:{ L=creat_L( ); out_L(L);
} break;
case 2:{ printf("\n i,e=?"); scanf("%d,%d",&i,&e);
insert_L(L,i,e); out_L(L);
} break;
case 3:{ printf("\n i=?"); scanf("%d",&i);
x=delete_L(L,i); out_L(L);
if(x!=-1) printf("\n x=%d\n",x);
} break;
case 4:{ printf("\n e=?"); scanf("%d",&e);
loc=locat_L(L,e);
if (loc==-1) printf("\n 未找到 %d",loc);
else printf("\n 已找到，元素位置是 %d",loc);
} break;
} /* switch */
printf("\n ----------------");
}while(k>=1 && k<5);
printf("\n 再见!");
printf("\n 打回车键，返回。"); ch=getch();
} /* main */
/* 建立线性链表 ( 11，22 ，33 ) */
LNode *creat_L( )
{ LNode *h,*p,*s; ElemType x;
h=(LNode *)malloc(sizeof(LNode)); /* 分配头结点 */
h->next=NULL;
p=h;
printf("\n data=?"); scanf("%d",&x); /* 输入第一个数据元素 */
while( x!=-111) /* 输入-111，结束循环 */
{ s=(LNode *)malloc(sizeof(LNode)); /* 分配新结点 */
s->data=x; s->next=NULL;
p->next=s; p=s;
printf("data=?( -111 end) "); scanf("%d",&x); /* 输入下一个数据*/
}
return(h);
} /* creat_L */
/* 输出单链表中的数据元素*/
void out_L(LNode *L)
{ LNode *p; char ch;
p=L->next; printf("\n\n");
while(p!=NULL) { printf("%5d",p->data); p=p->next;
};
printf("\n\n 打回车键，继续。"); ch=getch();
} /* out_link */
/* 在i位置插入元素e */
void insert_L(LNode *L,int i, ElemType e)
{ LNode *s,*p,*q; int j;
p=L; /* 找第i-1个结点 */
j=0;
while(p!=NULL && jnext; j++; }
if(p==NULL || j>i-1) printf("\n i ERROR !");
else { s=(LNode *)malloc(sizeof(LNode));
s->data=e;
s->next=p->next;
p->next=s;
}
} /* insert_L */
/* 查找值为 e 的元素, 返回它的位置 */
int locat_L(LNode *L,ElemType e)
{ LNode *p; int j=1;
p=L->next;
while(p!=NULL && p->data!=e) {p=p->next; j++;}
if(p!=NULL)return(j); else return(-1);
} /* locat_L */
/* 删除第i个位置的元素, 返回它的值 */
ElemType delete_L(LNode *L,int i)
{
}
三、实验源代码
四、实验结果
第三章 栈和队列实验
3.1栈的应用—括号匹配
一、实验目的
1.掌握堆栈特殊线性表的存储方式的基本操作方法。
2.掌握堆栈后进先出运算原则在解决实际问题中的应用。
3.掌握使用栈的原理来解决表达式中的括号配对问题。
二、实验内容
假设一个算术表达式中包含圆括弧、方括弧三种类型的括弧，编写一个程序用于判别表达式中括弧是否正确配对。
说明：检验表达式中的括号匹配情况：假设在一个算术表达式中，可以包含三种括号：圆括号"("和")"，方括号"["和"]"，并且这两种括号可以按任意的次序嵌套使用。比如，...[......[...]...]...(...)..。现在需要设计一个算法，用来检验在输入的算术表达式中所使用括号的合法性。
提示：
算术表达式中各种括号的使用规则为：出现左括号，必有相应的右括号与之匹配，并且每对括号之间可以嵌套，但不能出现交叉情况。我们可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配情况。在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。
(1)当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号;
(2)从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况;
(3)算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。
算法步骤：扫描表达式，
1)凡出现左括弧，则进栈;
2)凡出现右括弧，首先检查栈是否空。
若栈空，则表明该“右括弧”多余
否则和栈顶元素比较，
若相匹配，则“左括弧出栈”
否则表明不匹配
3)表达式检验结束时，
若栈空，则表明表达式中匹配正确
否则表明“左括弧”有余
栈的类型定义及基本操作代码可参考教材相关定义和程序。
三、实验源代码
四、实验结果
3.2栈的应用--数制转换
一、实验目的
1.掌握堆栈的存储方式和基本操作。
2.掌握堆栈后进先出运算原则在解决实际问题中的应用。
3.掌握使用栈的原理来解决数制转换问题。
二、实验内容
利用栈结构，编写程序将十进制数转换成二进制数或八进制数。
提示：十进制数值转换成二进制使用辗转相除法将一个十进制数值转换成二进制数值。即用该十进制数值除以2，并保留其余数;重复此操作，直到该十进制数值为0为止。最后将所有的余数反向输出就是所对应的二进制数值。十进制数值转换成八进制算法类似。转换算法要求用一个函数完成。
顺序栈的基本操作的代码可参考如下：
typedef struct
{
DataType stack[MaxStackSize];
int top;
} SeqStack;
void StackInitiate(SeqStack *S) /*初始化顺序堆栈S*/
{ S->top = 0; /*定义初始栈顶下标值*/
}
int StackNotEmpty(SeqStack S)
/*判顺序堆栈S非空否，非空则返回1，否则返回0*/
{ if(S.top <= 0) return 0;
else return 1;
}
int StackPush(SeqStack *S, DataType x)
/*把数据元素值x压入顺序堆栈S，入栈成功则返回1，否则返回0 */
{ if(S->top >= MaxStackSize)
{ printf("堆栈已满无法插入! \n");
return 0;
}
else
{ S->stack[S->top] = x;
S->top ++;
return 1;
}
}
int StackPop(SeqStack *S, DataType *d)
/*弹出顺序堆栈S的栈顶数据元素值到参数d ，出栈成功则返回1，否则返回0*/
{ if(S->top <= 0)
{
printf("堆栈已空无数据元素出栈! \n");
return 0;
}
else
{
S->top --;
*d = S->stack[S->top];
return 1;
}
}
int StackTop(SeqStack S, DataType *d)
/*取顺序堆栈S的当前栈顶数据元素值到参数d ，成功则返回1，否则返回0*/
{
if(S.top <= 0)
{ printf("堆栈已空! \n");
return 0;
}
else
{ *d = S.stack[S.top - 1];
return 1;
}
}
三、实验源代码
四、实验结果
3.3 队列的基本操作
一、实验目的
1.掌握队列的顺序存储结构。
2.掌握队列先进先出运算原则在解决实际问题中的应用。
3. 掌握自定义数据类型的用法。
二、实验内容
仿照资料中顺序循环队列的例子，设计一个只使用队头指针和计数器的顺序循环队列抽象数据类型。其中操作包括：初始化、入队列、出队列、判断队列是否非空。编写主函数，验证所设计的顺序循环队列的正确性。
以下是队列操作函数的定义：
(1)QueueInitiate(Q) 初始化队列Q
(2)QueueNotEmpty(Q) 队列Q非空否
(3)QueueAppend(Q,x) 入队列，在队列Q的队尾插入数据元素x。
(4)QueueDelete(Q,d) 出队列，把队列Q的队头元素删除并由参数d带回。
提示：队尾的位置可由队头指针与计数器进行求解，请思考它们之间的关系，同时还要考虑如何实现循环队列(可借助求模运算)。
三、实验源代码
四、实验结果(测试数据)
3.5栈与队列的应用—回文
一、实验目的
1、掌握链式堆栈的类型定义方法。
2、掌握链式堆栈上实现的几种基本操作。
3、掌握链式队列的类型定义方法。
4、掌握链式队列上实现的几种基本操作。
二、实验内容
1、编程序判断一个字符序列是否是回文，要求采用链式队列和链式堆栈。
提示：设字符数组str中存放了要判断的字符串。把字符数组中的字符逐个分别存入队列和堆栈，然后逐个出队列和退栈并比较出队列的字符和退栈的字符是否相等，若全部相等则该字符序列是回文，否则就不是回文。
以下是程序部分代码，请调试并补充使之正确运行。
LinStack.h
typedef struct snode
{
DataType data;
struct snode *next;
} LSNode;
void StackInitiate(LSNode **head)
/*初始化带头结点链式堆栈*/
{
if((*head = (LSNode *)malloc(sizeof(LSNode))) == NULL)
{
Printf(“没有空间申请\n”);
Return;
}
(*head)->next = NULL;
}
int StackNotEmpty(LSNode *head)
/*判堆栈是否非空，非空返回1;空返回0*/
{
if(head->next == NULL) return 0;
else return 1;
}
int StackPush(LSNode *head, DataType x)
/*把数据元素x插入链式堆栈head的栈顶作为新的栈顶 */
{
LSNode *p;
if((p = (LSNode *)malloc(sizeof(LSNode))) == NULL)
{
printf("内存空间不足无法插入! \n");
return 0;
}
p->data = x;
p->next = head->next; /*新结点链入栈顶*/
head->next = p; /*新结点成为新的栈顶*/
return 1;
}
int StackPop(LSNode *head, DataType *d)
/*出栈并把栈顶元素由参数d带回*/
{
LSNode *p = head->next;
if(p == NULL)
{
printf("堆栈已空出错!");
return 0;
}
head->next = p->next; /*删除原栈顶结点*/
*d = p->data; /*原栈顶结点元素赋予d*/
free(p); /*释放原栈顶结点内存空间*/
return 1;
}
int StackTop(LSNode *head, DataType *d)
/*取栈顶元素并把栈顶元素由参数d带回*/
{
LSNode *p = head->next;
if(p == NULL)
{
printf("堆栈已空出错!");
return 0;
}
*d = p->data;
return 1;
}
void Destroy(LSNode *head)
{
LSNode *p, *p1;
p = head;
while(p != NULL)
{
p1 = p;
p = p->next;
free(p1);
}
}
LinQueue.h
typedef struct qnode
{
DataType data;
struct qnode *next;
} LQNode;
typedef struct
{
LQNode *front; /*队头指针*/
LQNode *rear; /*队尾指针*/
} LQueue;
void QueueInitiate(LQueue *Q) /*初始化链式队列Q*/
{
Q->rear = NULL; /*定义初始队尾指针下标值*/
Q->front = NULL; /*定义初始队头指针下标值*/
}
int QueueNotEmpty(LQueue Q)
/*判链式队列Q非空否，非空则返回1，否则返回0*/
{
if(Q.front == NULL) return 0;
else return 1;
}
int QueueAppend(LQueue *Q, DataType x)
/*把数据元素值x插入链式队列Q的队尾，入队列成功则返回1，否则返回0 */
{
LQNode *p;
if((p = (LQNode *)malloc(sizeof(LQNode))) == NULL)
{
printf("内存空间不足!");
return 0;
}
p->data = x;
p->next = NULL;
if(Q->rear != NULL) Q->rear->next = p;
Q->rear = p;
if(Q->front == NULL) Q->front = p;
return 1;
}
int QueueDelete(LQueue *Q, DataType *d)
/*删除链式队列Q的队头数据元素值到d ，出队列成功则返回1，否则返回0*/
{
LQNode *p;
if(Q->front == NULL)
{
printf("队列已空无数据元素出队列! \n");
return 0;
}
else
{
*d = Q->front->data;
p = Q->front;
Q->front = Q->front->next;
if(Q->front == NULL) Q->rear = NULL;
free(p);
return 1;
}
}
int QueueGet(LQueue Q, DataType *d)
/*取链式队列Q的当前队头数据元素值到d ，成功则返回1，否则返回0*/
{
if(Q.front == NULL)
{
printf("队列已空无数据元素出队列! \n");
return 0;
}
else
{
*d = Q.front->data;
return 1;
}
}
void Destroy(LQueue Q)
{
LQNode *p, *p1;
p = Q.front;
while(p != NULL)
{
p1 = p;
p = p->next;
free(p1);
}
}
HuiWen(char str[])
{
自己编写代码
}
主程序
Void main(void)
{
Char str1[]=”abcdedcba”;
Char str2[]=”ABCDEABCDE”
HuiWen(str1);
HuiWen(str2);
}
三、实验源代码
四、实验结果
第四章 数组实验
4.1 动态数组的实现
一、实验目的
1.理解动态数组与静态数组的区别
2.掌握动态数组的实现方法和基本应用
二、实验内容
设矩阵A,B,C都是3*3矩阵，矩阵元素为整数类型，要求：
1.3个矩阵都采用动态数组进行存储;
2.编写实现C=A+B的函数;
3.编写实现C=A*B的函数。
提示：整个程序流程可参考如下：
开始
动态内存分配函数申请空间，输入矩阵A和B
调用两个矩阵求和函数，输出和值
| 调用两个矩阵乘积函数，输出乘积值 |
结束
三、实验源代码
四、实验结果(测试数据)
第五章 串实验
5.1 串的匹配与替换
一、实验目的
1.掌握串存储结构
2.掌握串的匹配算法，并能进行相关应用
二、实验内容
设串采用静态数组存储结构，编写函数实现串的替换Replace(S,start,T,V),即要求在主串S中从位置start开始查找是否存在子串T。若存在，则用子串V去替换子串T，且函数返回1;若主串S中不存在子串T，则函数返回0。要求设计主函数进行测试 。
提示：算法的主要思想是在主串S中，利用Brute-Force函数从位置start开始定位子串T的位置，如果有T存在则删除T，插入子串V，直到S中不存在子串T。
三、实验源代码
四、实验结果(测试数据)
第六章 递归实验
6.1折半查找递归算法
一、实验目的
1.理解递归调用的实现过程
2.学会递归程序的设计方法
二、实验内容
1.编写折半查找的递归程序。
2.在VC++的调试环境下观察折半查找递归程序的调用与返回过程,并记录其过程和返回值。
3.设计一个折半查找的循环结构的算法,并与递归算法进行对比分析。
提示：将要查找的元素key与查找区间正中元素相比，若key小，则查找区间缩小至前半部份查找，若key大，则查找区间缩小至后半部份查找;再取其中值比较，每次缩小1/2的范围，直到查找成功或失败为止。如递归实现，考虑函数的参数应有哪些。在用循环结构实现时，函数的参数有什么变化?
三、实验源代码
四、实验结果(测试数据)
6.2递归算法的实现
一、实验目的
1、掌握递归原理
2、掌握一些常用问题的递归算法设计
二、实验内容
1、设计模拟汉诺塔问题求解过程的算法。汉诺塔问题的描述是：设有3
根标号为A，B，C的柱子，在A柱上放着n个盘子，每一个都比下面的略小一点，要求把A柱上的盘子全部移到C柱上，移动的规则是：(1)一次只能移动一个盘子;(2)移动过程中大盘子不能放在小盘子上面;(3)在移动过程中盘子可以放在A，B，C的任意一个柱子上。本实验要求实现5个盘子的移动。
提示：1个盘子的汉诺塔问题可直接移动。n个盘子的汉诺塔问题可递归表示为，首先把上边的n-1个盘子从A柱移到B柱，然后把最下边的一个盘子从A柱移到C柱，最后把移到B柱的n-1个盘子再移到C柱。
算法设计：首先，盘子的个数n是必须的一个输入参数，对n个盘子,我们可从上至下依次编号为1,2,…,n;其次，输入参数还需有3个柱子的代号,我们令3个柱子的参数名分别为fromPeg，auxPeg和toPeg;最后，汉诺塔问题的求解是一个处理过程，因此算法的输出是n个盘子从柱子fromPeg借助柱子auxPeg移动到柱子toPeg的移动步骤，每一步的移动为屏幕显示如下形式的信息：
Move Disk i from Peg X to Peg Y
2、设计递归算法实现5!。
提示：阶乘的定义为
第七章 二叉树实验
7.1二叉树的遍历应用
一、实验目的
1、掌握二叉树的建立方法
2、掌握二叉树遍历的基本方法(前序、中序、后序)
3、掌握递归二叉树遍历算法的应用
二、实验内容
1.构造一棵二叉树,树的形态如下图所示，打印出前序遍历、中序遍历、后序遍历的遍历序列。
A
B F
C E G
D
提示：1.前序遍历二叉树的递归算法为：
若二叉树为空，则算法结束;否则：
(1)访问根结点;
(2)前序遍历根结点的左子树;
(3)前序遍历根结点的右子树。
2.中序遍历二叉树的递归算法为：
若二叉树为空，则算法结束;否则：
(1)中序遍历根结点的左子树;
(2)访问根结点;
(3)中序遍历根结点的右子树。
3.后序遍历二叉树的递归算法为：
若二叉树为空，则算法结束;否则：
(1)后序遍历根结点的左子树;
(2)后序遍历根结点的右子树;
(3)访问根结点。
2.选择一种遍历方式计算该树中叶子结点的个数，并打印出叶子结点。
提示：前序遍历、中序遍历、后序遍历都可以用来求出叶子结点数。在遍历过程中，如果判断为叶子结点，则访问该结点，计数器加1。
二叉树的定义可参考以下代码
定义头文件为BiTree.h
typedef struct Node
{
ElemType data; /*数据域*/
struct Node *leftChild; /*左子树指针*/
struct Node *rightChild; /*右子树指针*/
}BiTreeNode; /*结点的结构体定义*/
/*初始化创建二叉树的头结点*/
void Initiate(BiTreeNode **root)
{
*root = (BiTreeNode *)malloc(sizeof(BiTreeNode));
(*root)->leftChild = NULL;
(*root)->rightChild = NULL;
}
void Destroy(BiTreeNode **root)
{
if((*root) != NULL && (*root)->leftChild != NULL)
Destroy(&(*root)->leftChild);
if((*root) != NULL && (*root)->rightChild != NULL)
Destroy(&(*root)->rightChild);
free(*root);
}
/*若当前结点curr非空，在curr的左子树插入元素值为x的新结点*/
/*原curr所指结点的左子树成为新插入结点的左子树*/
/*若插入成功返回新插入结点的指针，否则返回空指针*/
BiTreeNode *InsertLeftNode(BiTreeNode *curr, ElemType x)
{
BiTreeNode *s, *t;
if(curr == NULL) return NULL;
t = curr->leftChild; /*保存原curr所指结点的左子树指针*/
s = (BiTreeNode *)malloc(sizeof(BiTreeNode));
s->data = x;
s->leftChild = t; /*新插入结点的左子树为原curr的左子树*/
s->rightChild = NULL;
curr->leftChild = s; /*新结点成为curr的左子树*/
return curr->leftChild; /*返回新插入结点的指针*/
}
/*若当前结点curr非空，在curr的右子树插入元素值为x的新结点*/
/*原curr所指结点的右子树成为新插入结点的右子树*/
/*若插入成功返回新插入结点的指针，否则返回空指针*/
BiTreeNode *InsertRightNode(BiTreeNode *curr, ElemType x)
{
BiTreeNode *s, *t;
if(curr == NULL) return NULL;
t = curr->rightChild; /*保存原curr所指结点的右子树指针*/
s = (BiTreeNode *)malloc(sizeof(BiTreeNode));
s->data = x;
s->rightChild = t; /*新插入结点的右子树为原curr的右子树*/
s->leftChild = NULL;
curr->rightChild = s; /*新结点成为curr的右子树*/
return curr->rightChild; /*返回新插入结点的指针*/
}
/*若curr非空，删除curr所指结点的左子树*/
/*若删除成功返回删除结点的双亲结点指针，否则返回空指针*/
BiTreeNode *DeleteLeftTree(BiTreeNode *curr)
{
if(curr == NULL || curr->leftChild == NULL) return NULL;
Destroy(&curr->leftChild);
curr->leftChild = NULL;
return curr;
}
/*若curr非空，删除curr所指结点的右子树*/
/*若删除成功返回删除结点的双亲结点指针，否则返回空指针*/
BiTreeNode *DeleteRightTree(BiTreeNode *curr)
{
if(curr == NULL || curr->rightChild == NULL) return NULL;
Destroy(&curr->rightChild);
curr->rightChild = NULL;
return curr;
}
三、实验源代码
四、实验结果
7.2二叉树层序遍历的实现
一、实验目的
1、掌握二叉树层序遍历的过程
2、熟悉二叉树层序遍历的实现
二、实验内容
二叉树的层序遍历是按二叉树的层次顺序(即从根结点层至叶结点层)，同一层按先左子树再右子树的次序遍历。给定如下图所示的二叉树，请输出对应的层序遍历的序列。
设计参考：可以采用队列结构来实现。
A
B F
C E G
D
提示：可参考层序遍历算法如下
(1)初始化设置一个队列;
(2)把根结点指针入队列;
(3)当队列非空时，循环执行步骤(3.a)到步骤(3.c):
(3.a)出队列取得一个结点指针，访问该结点;
(3.b)若该结点的左子树非空，则将该结点的左子树指针入队列;
(3.c)若该结点的右子树非空，则将该结点的右子树指针入队列;
(4)结束。
三、实验源代码
四、实验结果(打印遍历的顺序)
7.3哈夫曼编码的程序设计
一、实验目的
1、掌握哈夫曼树的建立过程
2、熟悉哈夫曼编码的实现
二、实验内容
设有字符集{A,B,C,D},各字符在电文中出现的次数集为{1,3,4,7};要求编程实现哈夫曼树的构造,并在此基础上编程实现哈夫曼编码。
提示：哈夫曼树的结点结构和编码结构可参考如下：
typedef struct //哈夫曼树的结点结构
{ int weight; //权值
int flag; //标记
int parent; //双亲结点下标
int leftChild; //左孩子下标
int rightChild; //右孩子下标
} HaffNode;
typedef struct //存放哈夫曼编码的数据元素结构
{ int bit[MaxN]; //数组
int start; //编码的起始下标
int weight; //字符的权值
} Code;
算法思想如下：
(1) 由给定的 n 个权值{ w1, w2, …, wn }构成n棵二叉树的集合F = { T1, T2, …, Tn } (即森林) ，其中每棵二叉树 Ti 中只有一个带权为 wi 的根结点，其左右子树均空。
(2) 在F 中选取两棵根结点权值最小的树 做为左右子树构造一棵新的二叉树，且让新二叉树根结点的权值等于其左右子树的根结点权值之和。
(3) 在F 中删去这两棵树，同时将新得到的二叉树加入 F中。
(4) 重复(2) 和(3) , 直到 F 只含一棵树为止。这棵树便是Huffman树。
从哈夫曼树求叶结点的哈夫曼编码实际上是从叶结点到根结点路径分支的逐个遍历，每经过一个分支就得到一位哈夫曼编码值。
三、实验源代码
四、实验结果(树结构及编码表)
第八章 图实验
8.1图的广度优先遍历的实现
一、实验目的
1、 掌握图的遍历过程;
2、 理解图的存储结构与基本操作;
2、熟悉图的广度优先遍历的实现
二、实验内容
1 采用邻接矩阵的存储结构保存下图;
2 编程实现该图的创建与广度优先遍历。
提示：连通图的广度优先遍历算法为：
(1)访问初始顶点v并标记顶点v为已访问;
(2)顶点v入队列;
(3)当队列非空时则继续执行，否则算法结束;
(4)出队列取得队头顶点u;
(5)查找顶点u的第一个邻接顶点w;
(6)若顶点u的邻接顶点w不存在，则转到步骤(3)，否则循环执行，
(6.1)若顶点w尚未被访问则访问顶点w并标记顶点w为已访问;
(6.2)顶点w入队列;
(6.3)查找顶点u的w邻接顶点后的下一个邻接顶点w，转到步骤(6)。
三、实验源代码
四、实验结果(打印遍历的顺序)
第九章 排序实验
9.1插入排序算法的实现
一、实验目的
1、理解插入排序思想
2、掌握直接插入排序的实现方法
3、掌握希尔排序的实现方法
二、实验内容
编写直接插入排序和希尔排序的实现程序，并编写测试函数，测试数据为(43，5，47，1，19，43，11，59，15，48，41)，其中希尔排序增量d=5,3,1。
提示：
1.直接插入排序算法思想：顺序地把待排序的数据元素按其关键字值的大小插入到已排序数据元素子集合的适当位置。
2.希尔排序算法思想：将相隔某个增量d的记录组成一个小组, 对同一小组内的数据元素用直接插入法排序;让增量dk逐趟缩短(例如依次取5,3,1)，直到dk=1为止。
三、实验源代码
四、实验结果
9.2排序算法综合测试
一、实验目的
1、理解各类排序算法的实现过程;
2、理解不同排序算法的时间复杂度及适用环境;
3、了解算法性能测试的基本方法。
二、实验内容
1、以下是一个通过随机数来测试排序算法运行时间的程序，中间留出了加入排序算法的部分。其中可以通过修改RANDNUM的值来更改测试的数据量：
#include "stdio.h"
#include
#include
#include
#define RANDNUM 10000 //随机数的个数
void main()
{
int iRandNum[RANDNUM];//存放随机数
time_t first,second; //记录开始和结束时间(以毫秒为单位)
int i;
for(i=0;i
{//产生1万个随机数
iRandNum[i]=rand()%RANDNUM;
}
first=clock(); //开始时间
//此处加入排序程序
second=clock();//结束时间
}
(2) 从所学的排序算法中任选四种排序算法进行测试，记录运行时间;
(3)把需排序的数改为20000，进行同样测试，并比较测试结果。
三、实验源代码
四、实验结果(记录测试结果)
第十章 查找实验
10.1动态查找表实验
一、实验目的
1、理解动态查找表的动态生成过程;
2、任意给出一组数(不少于10个)，建立对应二叉排序树;
3、在二叉排序树基础上进行数据的查找实验;
4、对比观察同样数据不同排列顺序，建立的二叉排序树是否一样。
二、实验内容
1、定义二叉排序树的数据结构;
2、实现二叉排序树的插入算法与查找算法，并建立二叉排序树;
3、进行数据查找和建树过程的比较。
提示：考虑二叉排序树的存储结构是否能借用二叉树的存储结构?二叉排序树的查找算法可参考如下：
若二叉排序树为空，则查找不成功;
否则
1)若给定值等于根结点的关键字，则查找成功;
2)若给定值小于根结点的关键字，则继续在左子树上进行查找;
3)若给定值大于根结点的关键字，则继续在右子树上进行查找。
插入思想：
若二叉排序树为空树，则新插入的结点为新的根结点;否则，新
插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。
三、实验源代码
四、实验结果
