数据结构
实验教案
授课教师：许四平
适用专业：信息与计算科学
使用班级：13信计1、2
授课时间：20##年秋季
授课学时：14学时
使用教材：《数据结构》 严蔚敏 主编
实验指导书：数据结构实验指导书，
数理学院编，20##年版
湖北理工学院数理学院
实 验 安 排 表
数据结构设计性实验项目
1. 线性表的合并：已知线性表La和Lb的元素按值非递减排列。归并La和Lb得到新的线性表Lc，Lc的元素也按值非递减排列。分别采用顺序存储结构和链式结构来实现。
2. 线性表的逆置：设有一个线性表（e0, e1, …, en-2, en-1），请编写一个函数将这个线性表原地逆置，即将线性表内容置换为（en-1, en-2, …, e1, e0）。线性表中的数据可以为整数、字符或字符串，试分别采用顺序存储结构和链式结构来实现。
3. 约瑟夫环的实现：设有n个人围坐一圈，用整数序列1, 2, 3, ……, n表示顺序围坐在圆桌周围的人， 现从某个位置 s上的人开始报数，数到m的人出列，接着从出列的下一个人又从1开始重新报数，数到m的人出列，如此下去，直到所有人都出列为此。试设计确定他们的出列次序序列的程序。如 n=8, m=4 ,s=1时， 设每个人的编号依次为 1，2，3，…开始报数，则得到的出列次序为4，8，5，2，1，3，7，6。检查程序的正确性和健壮性。
(1)采用数组表示作为求解过程中使用的数据结构。
(2) 采用单向循环链表作为存储结构模拟整个过程，循环链表可不设头节点,必须注意空表和非空表的界限。
4. 数制转换： 利用顺序栈和链栈实现数制转换
5. 二叉树的遍历：分别以顺序存储结构和二叉链表作存储结构，试编写前序、中序、后序及层次顺序遍历二叉树的算法。
6. 赫夫曼树与赫夫曼编码：已知某系统在通信联络中只可能出现8种字符a,b,c,d,e,f,g,h，其概率分别为{0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11}，试设计Huffman编码，并计算其平均码长。
(1) 初始化：从键盘读入8个字符，以及它们的权值，建立Huffman树。
(2)编码：根据建立的Huffman树，求每个字符的Huffman编码。对给定的待编码字符序列进行编码。
(3) 译码：利用已经建立好的Huffman树，对上面的编码结果译码。译码的过程是分解电文中的字符串，从根结点出发，按字符’0’和’1’确定找左孩子或右孩子，直至叶结点，便求得该子串相应的字符。
(4) 打印 Huffman树。
7. 学生成绩管理查询系统：每个学生的数据信息有准考证号（主关键字）、姓名、语文、英语、数学、和总分等数据项，所有学生的信息构成一个学生成绩表。假设准考证号的头两位表示地区编号。请设计一个管理系统达到如下基本要求：
（1） 初始化：建立一个学生成绩表，输入准考证号、姓名、语文、英语、数学，然后计算每个学生的总分，存入相应的数据项；注意：分析数据对象和它们之间的关系，并以合适的方式进行组织（可选择无序的顺序表、有序的顺序表或索引顺序表来进行存储表示）；
（2） 查找：综合应用基本查找算法完成数据的基本查询工作，并输出查询的结果；
（3） 输出：有选择性地输出满足一定条件的数据记录，如输出地区编号为"01"，并且总分在550分以上的学生的信息；
（4） 计算：计算在等概率情况下该查找表的平均查找长度。
8. 排序：编制程序让机器随机产生2000个整数，放入一个数组中；对此2000个随机数序列分别用冒泡排序、快速排序、希尔排序和堆排序方法进行排序，并比较它们的运行时间。
注意：每三、四个同学组成一个小组。每个实验中的题目，可分别由不同的同学完成。其它题目可以相互交流，以利于互相提高。
数据结构验证性实验项目
实验一 线性表的顺序存储
一、实验目的及要求
1、掌握在TC环境下调试顺序表的基本方法
2、掌握顺序表的基本操作，插入、删除、查找、以及有序顺序表的合并等算法的实现。
二、实验学时
2学时
三、实验任务
1、 生成一个顺序表并动态地删除任意元素和在任意位置插入元素。
2、 将两个有序表合并成一个有序表。
四、实验重点、难点
1、 在顺序表中移动元素。
2、 在顺序表中找到正确的插入位置。
五、操作要点
(一)顺序表基本操作的实现
[问题描述] 当我们要在顺序表的第i个位置上插入一个元素时，必须先将顺序表中第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。
[基本要求] 要求生成顺序表时，可以键盘上读取元素，用顺序存储结构实现存储。
[实现提示] 要实现基本操作，可用实现的基本操作，也可设计简单的算法实现。
[程序实现]
#include <stdio.h>
#include <conio.h>
typedef int DataType ;
# define maxnum 20
typedef struct
{int data[maxnum];
int length;
}SeqList;
/*插入函数*/
int insert(SeqList *L , int i , DataType x)
/* 将新结点x插入到顺序表L第i个位置 */
{ int j ;
if( i<0 || i>(*L).length +1)
{ printf(" \n i 值不合法 ! ");
return 0;
}
if((* L).length >=maxnum-1)
{ printf(" \n 表满不能插入!");
return 0;
}
for(j=(*L).length;j>=i;j--) (*L).data[j+1]=(*L).data[j];
(*L).data[i] = x;
(*L).length++;
return 1;
}
/*删除函数*/
int delete( SeqList *L ,int i)
/*从顺序L中删除第i个结点*/
{ int j ;
if( i<0|| i>(*L).length )
{ printf(" \n 删除位置错误 ! ") ;
return 0;
}
for(j=i+1;j<=(*L).length;j++)
(*L).data[j-1] =(*L).data[j];
(*L).length--;
return 1;
}
/*生成顺序表*/
void creatlist(SeqList * L)
{ int n , i , j ;
printf("请输入顺序表 L 的数据个数：\n") ;
scanf("%d" , &n) ;
for(i=0 ; i<n ; i++)
{ printf("data[%d] =" , i) ;
scanf("%d",&((*L).data[i]));
}
(*L).length=n-1;
printf("\n") ;
}/*creatlist */
/*输出顺序表 L*/
printout(SeqList * L)
{ int i ;
for (i=0 ; i<=(* L).length ; i++)
{ printf(" data[%d]=", i) ;
printf("%d", (*L).data[i]);
}/*printout */
printf("\n");
}
main()
{ SeqList *L ;
char cmd ;
int i , t , x;
clrscr() ;
creatlist(L);
do
{
printf("\ni , I ----- 插入\n") ;
printf("d , D ----- 删除\n") ;
printf("q , Q ----- 退出\n") ;
do
{cmd=getchar() ;
}while((cmd!='i')&&(cmd!='I')&&(cmd!='d')&&(cmd!='D')&&(cmd!='q')&&(cmd!='Q'));
switch(cmd)
{ case 'i':
case 'I':
printf("\nPlease input the DATA: ");
scanf("%d",&x) ;
printf("\nWhere? ");
scanf("%d",&i) ;
insert(L,i,x) ;
printout(L);
break ;
case 'd':
case 'D' :
printf("\nWhere to Delete? ");
scanf("%d",&i);
delete(L,i);
printout(L);
break ;
}
}while((cmd!='q')&&(cmd!='Q'));
}
（二）有序顺序表的合并
[问题描述] 已知顺序表la和lb中的数据元素按非递减有序排列，将la和lb表中的数据元素，合并成为一个新的顺序表lc
[基本要求] lc中的数据元素仍按非递减有序排列，并且不破坏la和lb表
[程序实现]
#include<stdio.h>
#include<stdlib.h>
# define OK 1
# define ERROR 0
/* 定义ElemType为int或别的自定义类型 */
typedef int ElemType;
/* 链式存储类型 */
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
/* 单链表的建立(头插法)*/
void CreateList_L(LinkList &L,int n) //CreateList_L() function
{ //To Creatre a LinkList L with HeadNode
int i;
LNode *p;
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;
printf("Please input the data for LinkList Nodes: \n");
for(i=n;i>0;--i)
{
p=(LinkList)malloc(sizeof(LNode));
scanf("%d",&p->data); //Reverse order inputing for Creating a LinkList
p->next=L->next;
L->next=p;
}//end of for
if(n) printf("Success to Create a LinkList !\n");
else printf("A NULL LinkList have been created !\n");
}//end of CreateList() function
void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc)
{
LinkList pa,pb,pc;
pa=La->next;pb=Lb->next;
Lc=pc=La;
while(pa&&pb)
{
if(pa->data<=pb->data)
{
pc->next=pa;pc=pa;pa=pa->next;
}
else
{
pc->next=pb;pc=pb;pb=pb->next;
}
}
pc->next=pa?pa:pb;
free(Lb);
}
void main()
{
LinkList La,Lb,Lc,p;
int n;
printf("请输入La的长度n:");
scanf("%d",&n);
CreateList_L(La,n);
printf("输出La的内容：");
p=La->next;
while(p)
{
printf("%d->",p->data);
p=p->next;
}
printf("\n");
printf("请输入Lb的长度n:");
scanf("%d",&n);
CreateList_L(Lb,n);
printf("输出Lb的内容：");
p=Lb->next;
while(p)
{
printf("%d->",p->data);
p=p->next;
}
printf("\n");
MergeList_L(La,Lb,Lc);
printf("输出Lc的内容：");
p=Lc->next;
while(p)
{
printf("%d->",p->data);
p=p->next;
}
printf("\n");
}
六、注意事项
1、 删除元素或插入元素表的长度要变化。
2、 在合并表中当某一个表到表尾了就不用比较了，直接将另一个表的元素复制到总表去即可。
实验二 单链表
一、实验目的及要求
1、掌握用在TC环境下上机调试单链表的基本方法
2、掌握单链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现
3、进一步掌握循环单链表的插入、删除、查找算法的实现
二、实验学时
2学时
三、实验任务
1、在带头结点的单链表h中第i个数据元素之前插入一个数据元素。
2、将两个有序单链表合并成一个有序单链表。
3、生成一个循环单链表。
4、在循环单链表中删除一个节点。
四、实验重点、难点
1、 在单链表中寻找到第i-1个结点并用指针p指示。
2、 比较两个单链表的节点数据大小。
3、循环单链表中只有一个节点的判断条件。
4、在循环单链表中删除一个节点。
五、操作要点
（一）单链表基本操作的实现
1、实现栈的顺序存储和链式存储。
#include<stdio.h>
#include<stdlib.h>
# define STACK_INIT_SIZE 100
# define STACKINCREMENT 10
# define MAXQSIZE 100
# define OK 1
# define ERROR 0
/* 定义SElemType为int或别的自定义类型 */
typedef int SElemType;
/*链式栈的存储类型*/
typedef struct SNode
{
SElemType data;
struct SNode *next;
}SNode,*LinkStack;
/*取链式栈顶元素*/
int GeTop_L(LinkStack top,SElemType &e)
{
if(!top->next)
{
printf("Error!It's an empty LinkStack!\n");
return (ERROR);
}
else
{
e=top->next->data;
return (OK);
}
}
/*将元素压入链式栈*/
int Push_(LinkStack top,SElemType &e)
{
SNode *q;
q=(LinkStack)malloc(sizeof(SNode));
q->data=e;
q->next=top->next;
top->next=q;
return(OK);
}
/*将元素弹出链式栈*/
int Pop_L(LinkStack top,SElemType &e)
{
SNode *q;
e=top->next->data;
q=top->next;
top->next=q->next;
free(q);
return(OK);
}
/* 定义SElemType为int或别的自定义类型 */
typedef int SElemType;
/* 顺序栈的存储类型 */
typedef struct //define structure SqStack()
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
/*构造空顺序栈*/
int InitStack(SqStack &S) //InitStack() sub-function
{
S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S.base)
{
printf("Allocate space failure !\n");
return (ERROR);
}
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return (OK);
} //InitStack() end
/*取顺序栈顶元素*/
int GetTop(SqStack S,SElemType &e) //GetTop() sub-function
{
if(S.top==S.base)
{
printf("It's a empty SqStack !\n"); //if empty SqStack
return (ERROR);
}
e=*(S.top-1);
return (OK);
} //GetTop() end
/*将元素压入顺序栈*/
int Push(SqStack &S,SElemType e) //Push() sub-function
{
*S.top++=e;
return (OK);
} //Push() end
/* 将元素弹出顺序栈*/
int Pop(SqStack &S,SElemType &e) //Pop() sub-function
{
e=*--S.top;
return (OK);
} //Pop() end
void main()
{
int i,j;
SqStack s;
LinkStack s1;
SElemType e;
InitStack(s);
s1=(LinkStack)malloc(sizeof(SNode));
s1 -> next = NULL;
printf("顺序栈的元素：\n");
for(i=1;i<=8;i++)
{
scanf("%d",&e);
Push(s,e);
}
printf("顺序栈出栈：\n");
for(i=1;i<=8;i++)
{
Pop(s,e);
printf("%d ",e);
}
printf("\n");
printf("链式栈的元素：\n");
for(j = 1;j<=8;j++)
{
scanf("%d",&e);
Push_(s1,e);
}
printf("链式栈出栈：\n");
while(NULL != s1 -> next)
{
Pop_L(s1,e);
printf("%d ",e);
}
printf("\n");
}
2、利用顺序栈或链栈实现数制转换。
#include<stdio.h>
#include<stdlib.h>
# define STACK_INIT_SIZE 100
# define STACKINCREMENT 10
# define MAXQSIZE 100
# define OK 1
# define ERROR 0
/* 定义SElemType为int或别的自定义类型 */
typedef int SElemType;
/* 顺序栈的存储类型 */
typedef struct //define structure SqStack()
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
/*构造空顺序栈*/
int InitStack(SqStack &S) //InitStack() sub-function
{
S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S.base)
{
printf("Allocate space failure !\n");
return (ERROR);
}
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return (OK);
} //InitStack() end
int StackEmpty(SqStack S)
{
if(S.top==S.base)
return OK;
else
return ERROR;
}
/*取顺序栈顶元素*/
int GetTop(SqStack S,SElemType &e) //GetTop() sub-function
{
if(S.top==S.base)
{
printf("It's a empty SqStack !\n"); //if empty SqStack
return (ERROR);
}
e=*(S.top-1);
return (OK);
} //GetTop() end
/*将元素压入顺序栈*/
int Push(SqStack &S,SElemType e) //Push() sub-function
{
*S.top++=e;
return (OK);
} //Push() end
/* 将元素弹出顺序栈*/
int Pop(SqStack &S,SElemType &e) //Pop() sub-function
{
e=*--S.top;
return (OK);
} //Pop() end
/*利用顺序栈实现对于输入的任意一个非负十进制整数，输出与其等值的八进制数。*/
void Conversion()
{
SqStack S;
SElemType N,e;
InitStack(S);
scanf("%u",&N);
while(N)
{
Push(S,N%8);
N=N/8;
}
printf("Conversed to Oct.number=");
while(!StackEmpty(S))
{
Pop(S,e);
printf("%d",e);
}
printf("\n");
}
void main()
{
Conversion();
}
3、实现循环队列的存储和链队列的基本操作。
#include<stdio.h>
#include<stdlib.h>
# define OK 1
# define ERROR 0
typedef int QElemType;
/* 链队列的存储类型 */
typedef struct QNode //define structure QNode
{ QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct LinkQueue //define structure LinkQueue
{ QueuePtr front;
QueuePtr rear;
}LinkQueue;
/*构造空链式队列*/
int InitQueue(LinkQueue &Q) //InitQueue() sub-function
{ Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front)
{ printf("Overflow !\n");
return (ERROR);
}
Q.front->next=NULL;
return (OK);
} //InitQueue() end
/* 销毁链式队列*/
int DestroyQueue(LinkQueue &Q) //DestroyQueue() sub-function
{ while(Q.front)
{ Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
}
return (OK);
} //DestroyQueue() end
/* 在链式队列尾插入新元素*/
int EnQueue(LinkQueue &Q,QElemType e) //EnQueue() sub-function
{ QNode *p;
p=(QueuePtr)malloc(sizeof(QNode));
if(!p)
{ printf("Overflow !\n");
return (ERROR);
}
p->data=e;
p->next=NULL;
if(Q.front==NULL)
{ Q.front=Q.rear=p;
return (OK);
}
Q.rear->next=p;
Q.rear=p;
return (OK);
} //EnQueue() end
/*在链式队列头删除旧元素*/
int DeQueue(LinkQueue &Q,QElemType &e) //DeQueue() sub-function
{ if(Q.front==Q.rear)
{ printf("If it was deleted, it's empty !\n");
return (ERROR);
}
QNode *p;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
free(p);
return (OK);
} //DeQueue() end
void main()
{
LinkQueue L;
int i, n, e;
if(!InitQueue(L))
exit(0);
printf("请输入要写入队列的元素的个数：");
scanf("%d",&n);
printf("请输入要写入队列的元素：");
for(i = 0; i< n;i++)
{
scanf("%d",&e);
if(EnQueue(L, e))
break;
}
DeQueue(L,e);
printf("删除的元素为%d\n", e);
if(DestroyQueue(L))
printf("销毁队列成功。\n");
}
六、注意事项
1、在第i个节点前删除或插入节点需要用指针来表示第i-1个节点。
2、在合并链表时需要设置多个指针变量。
3、如果不是要删除的节点则指针后移，否则删除该节点。
七、思考题
1、编程实现两个循环单链表的合并。
实验三 栈、队列
一、实验目的及要求
1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。
2、掌握栈和队列的特点，即先进后出与先进先出的原则。
3、掌握栈和队列的基本操作实现方法。
二、实验学时
3学时
三、实验任务
1. 实现栈的顺序存储
2. 利用栈实现数制转换
四、实验重点、难点
1. 进栈、出栈栈顶指针都要改变。
2. 数制转换结束的判断条件。
五、操作要点
（一）实现栈的顺序存储
# define MAXSIZE 100
typedef int ElemType;
typedef struct
{ ElemType data[MAXSIZE];
int top;
}SeqStack;
void InitStack(SeqStack *s)
{s->top=0;
return 1;
}
int StackEmpty(SeqStack *s)
{ if(s->top==0) return 1;
else return 0;
}
int StackFull(SeqStack *s)
{ if(s->top==MAXSIZE-1) return 1;
else return 0;
}
void Push(SeqStack *s,int x)
{ if (StackFull(s)){ printf("the stack is overflow!\n");
return 0;
}
else { s->data[s->top]=x;
s->top++;
}
}
void Display(SeqStack *s)
{if(s->top==0)
printf("the stack is empty!\n");
else{ while(s->top!=0)
{ printf("%d->",s->data[s->top]);
s->top=s->top-1;
}
}
}
ElemType Pop(SeqStack *s)
{ if(StackEmpty(s)) return 0;
else return s->data[--s->top];
}
ElemType StackTop(SeqStack *s)
{ int i;
if(StackEmpty(s)) return 0;
else { i=s->top-1;
return s->data[i];} /*返回栈顶元素的值，但不改变栈顶指针*/
}
main(SeqStack *p)
{int n,i,k,h,x1,x2,select;
printf("create a empty stack!\n");
InitStack(p);
printf("input a stack length:\n");
scanf("%d",&n);
for(i=0;i<n;i++)
{ printf("input a stack value:\n");
scanf("%d",&k);
Push(p,k);
}
printf("select 1:Display()\n");
printf("select 2:Push()\n");
printf("select 3:Pop()\n");
printf("select 4:StackTop()\n");
printf("input a your select(1-4):\n");
scanf("%d",&select);
switch(select)
{case 1:{ Display(p);
break;}
case 2:{ printf("input a push a value:\n");
scanf("%d",&h);
Push(p,h);
Display(p);
break;}
case 3:{ x1=Pop(p);
printf("x1->%d\n",x1);
Display(p);
break;
}
case 4:{ x2=StackTop(p);
printf("x2->%d",x2);
break;
}
}
}
（二）利用栈实现数制转换
# define MAXSIZE 100
typedef int ElemType； /*将顺序栈的元素定义为整型*/
typedef struct
{ ElemType data[MAXSIZE];
int top;
}SeqStack;
void InitStack(SeqStack *s)
{s->top=0;
return 1;
}
int StackEmpty(SeqStack *s)
{ if(s->top==0) return 1;
else return 0;
}
int StackFull(SeqStack *s)
{ if(s->top==m-1) return 1;
else return 0;
}
void Push(SeqStack *s,int x)
{ if (StackFull(s)){ printf("the stack is overflow!\n");
return 0;
}
else { s->data[s->top]=x;
s->top++;
}
}
ElemType Pop(SeqStack *s)
{ ElemType y;
if(StackEmpty(s)){ printf("the stack is empty!\n");
return 0;
}
else { y=s->data[s->top];
s->top=s->top-1;
return y;
}
}
ElemType StackTop(SeqStack *s)
{ if(StackEmpty(s)) return 0;
else return s->data[s->top];
}
void Dec_to_Ocx (int N) /* n是非负的十进制整数，输出等值的八进制数*/
{
SeqStack *S； /*定义一个顺序栈*/
ElemType x；
Init_SeqStack(S)； /*初始化栈*/
if(N<0)
{
printf("\nError,The number must be over 0。")；
return；
}
if(!N) Push(S,0)；
while(N) /*自右向左产生八进制的各位数字，并将其进栈*/
{ Push(S，N%8)； /*余数入栈 */
N=N/8； /*商作为被除数*/
}
printf("Number %d converted to OCT:",N);
while(StackEmpty(S)) /*栈非空时退栈输出*/
{ x=Pop(S)；
printf(“%d”,x)；
}
printf("\n");
}
main( )
{ int n;
printf("Input a number to convert to OCT:\n");
scanf("%d",&n);
Dec_to_Ocx (n);
}
六、注意事项
1、进栈、出栈栈顶指针都要改变。
2、数制转换余数入栈后商作为被除数。
七、思考题
1、实现循环队列的顺序存储
实验四 树与二叉树
一、实验目的及要求
1、进一步掌握指针变量、动态变量的含义。
2、掌握二叉树的结构特性，以及各种存储结构的特点和适用范围。
3、掌握用指针类型描述、访问和处理二叉树的运算。
二、实验学时
4学时
三、实验任务
1、 以二叉链表作存储结构，编写前序、中序、后序及层次顺序遍历二叉树的算法。
2、 以二叉链表作存储结构，编写计算二叉树深度、所有结点总数、叶子结点数、双孩子结点个数、单孩子结点个数的算法
四、实验重点、难点
1、前序、中序、后序及层次顺序遍历二叉树的算法。
2、计算二叉树深度、所有结点总数、叶子结点数、双孩子结点个数、单孩子结点个数的算法。
五、操作要点
1、分别以顺序存储结构和二叉链表作存储结构，试编程实现前序、中序、后序及层次顺序遍历二叉树的算法。
顺序存储结构：
程序代码：
#include<stdio.h>
#include<iostream.h>
#define OK 1
#define ERROR 0
#define MAX_TREE_SIZE 100
typedef char TElemType ;
typedef TElemType SqBiTree[MAX_TREE_SIZE];
int Create(SqBiTree & bt,int &n)//层序创建二叉树的各个节点元素
{
cout<<"'*'表示结束创建，'/'表示空节点"<<endl;
TElemType c;
int i=0;
cout<<"请按层依次创建各个节点:";
cin>>c;
while(c!='*')
{
bt[++i]=c;
cin>>c;
}
n=i;
cout<<"二叉树创建完毕!"<<endl;
return OK;
}
int LevelOrderTraverse(SqBiTree bt,int n)//层序遍历
{
int i;
for( i=1;i<=n;i++)
{
if(bt[i]=='/')
continue;
else
if(i==n)
cout<<bt[i];
else
cout<<bt[i]<<"->";
}
cout<<endl;
return OK;
}
int PreOrederTraverse(SqBiTree bt,int i,int n)//先序遍历
{
if(i<=n)
if(bt[i]!='/')
cout<<bt[i]<<"->";
if(2*i<=n)
PreOrederTraverse(bt,2*i,n);
if((2*i+1)<=n)
PreOrederTraverse(bt,2*i+1,n);
return OK;
}
int InOrederTraverse(SqBiTree bt,int i,int n)//中序遍历
{
if(2*i<=n)
InOrederTraverse(bt,2*i,n);
if(i<=n)
if(bt[i]!='/'&& i!=n )
cout<<bt[i]<<"->";
else
if(bt[i]!='/'&& i==n )
cout<<bt[i];
if((2*i+1)<=n)
InOrederTraverse(bt,2*i+1,n);
return OK;
}
int PosOrederTraverse(SqBiTree bt,int i,int n)//后序遍历
{
if(2*i<=n)
PosOrederTraverse(bt,2*i,n);
if((2*i+1)<=n)
PosOrederTraverse(bt,2*i+1,n);
if(i<=n)
{
if(bt[i]!='/'&&i!=1)
cout<<bt[i]<<"->";
if(i==1)
cout<<bt[i];
}
return OK;
}
void main()
{
cout<<"顺序存储结构二叉树"<<endl;
SqBiTree Bt;
int i=1;
int Length;
Create(Bt,Length);
cout<<"该二叉树按层序遍历的遍历结果为:";
LevelOrderTraverse(Bt,Length);
cout<<endl<<"按先序遍历的结果为:";
PreOrederTraverse(Bt,i,Length);cout<<endl;
cout<<endl<<"按中序遍历的结果为:";
InOrederTraverse(Bt,i,Length);cout<<endl;
cout<<endl<<"按后序遍历的结果为:";
PosOrederTraverse(Bt,i,Length);cout<<endl;
cout<<"201240410111 周逊"<<endl;
}
运行结果：
二叉链表存储结构：
程序代码：
#include<iostream>
using namespace std;
#define ERROR 1
#define OK -1
typedef char TElemType;
/* 二叉树节点的存储类型 */
typedef struct BiTNode
{ TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode, *BiTree;
/*建立二叉树*/
int CreateBiTree(BiTree &T)
{
TElemType ch;
cin>>ch;
if(ch=='#') T=NULL;
else
{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
{ cout<<"Overflow!"; //no alloction
return (ERROR);
}
T->data=ch;
CreateBiTree(T->lchild); //create lchild
CreateBiTree(T->rchild); //create rchild
}
return (OK);
}
int PreOrderTraverse(BiTree T) //PreOrderTravers sub-function
{ if(T)
{ cout<<T->data<<"->"; //visite T
if (PreOrderTraverse(T->lchild)) //traverse lchild
if (PreOrderTraverse(T->rchild)) //traverse rchild
return (OK);
return (ERROR);
} //if end
else
return (OK);
} //PreOrderTraverse() end
int InOrderTraverse(BiTree T) //InOrderTraverse sub-function
{ if(T)
{ if (InOrderTraverse(T->lchild)) //traverse lchild
{ cout<<T->data<<"->"; //visite T
if(InOrderTraverse(T->rchild)) //traverse rchild
return (OK);
}
return (ERROR);
} //if end
else
return (OK);
} //InOrderTraverse() end
int PostOrderTraverse(BiTree T) //PostOrderTraverse() sub-function
{ if(T)
{ if (PostOrderTraverse(T->lchild)) //traverse lchild
if(PostOrderTraverse(T->rchild)) //traverse rchild
{ cout<<T->data<<"->"; //visite T
return (OK);
}
return (ERROR);
}
else
return (OK);
} //PostOrderTraverse() end
int main(int argc, char* argv[])
{
BiTree T;
cout<<"Please input data (/ for NULL node!) : ";
CreateBiTree( T);
cout<<"先序遍历二叉树 :";
PreOrderTraverse( T);
cout<<endl;
cout<<"中序遍历二叉树 :";
InOrderTraverse( T);
cout<<endl;
cout<<"后序遍历二叉树 :";
PostOrderTraverse(T);
cout<<endl;
return 0;
}
运行结果：
2、以二叉链表作存储结构，试编写计算二叉树深度、所有结点总数、叶子结点数、双孩子结点个数、单孩子结点个数的算法
程序代码：
#include<iostream>
using namespace std;
#define ERROR 1
#define OK -1
typedef char TElemType;
/* 二叉树节点的存储类型 */
typedef struct BiTNode
{ TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode, *BiTree;
/*建立二叉树*/
int CreateBiTree(BiTree &T)
{
TElemType ch;
cin>>ch;
if(ch=='#') T=NULL;
else
{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
{ cout<<"Overflow!"; //no alloction
return (ERROR);
}
T->data=ch;
CreateBiTree(T->lchild); //create lchild
CreateBiTree(T->rchild); //create rchild
}
return (OK);
}
int PreOrderTraverse(BiTree T) //PreOrderTravers sub-function
{
if(T)
{
cout<<T->data<<"->"; //visite T
if (PreOrderTraverse(T->lchild))
//traverse lchild
if (PreOrderTraverse(T->rchild)) //traverse rchild
return (OK);
return (ERROR);
} //if end
else
return (OK);
} //PreOrderTraverse() end
int InOrderTraverse(BiTree T) //InOrderTraverse sub-function
{ if(T)
{ if (InOrderTraverse(T->lchild)) //traverse lchild
{ cout<<T->data<<"->"; //visite T
if(InOrderTraverse(T->rchild)) //traverse rchild
return (OK);
}
return (ERROR);
} //if end
else
return (OK);
} //InOrderTraverse() end
int PostOrderTraverse(BiTree T) //PostOrderTraverse() sub-function
{ if(T)
{ if (PostOrderTraverse(T->lchild)) //traverse lchild
if(PostOrderTraverse(T->rchild)) //traverse rchild
{ cout<<T->data<<"->"; //visite T
return (OK);
}
return (ERROR);
}
else
return (OK);
} //PostOrderTraverse() end
int LeafCount (BiTree T)
{
int m,n;
if ( !T ) return 0;
if (!T->lchild&& !T->rchild)
return 1;
else{
m=LeafCount( T->lchild);
n=LeafCount( T->rchild);
return (m+n);
} // if
return OK;
}
int NodeCount(BiTree T)
{
if(!T)
return 0;
else
return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}
int onesoncount(BiTree T)
{
if (T==NULL)
return(0);
else if ((T->lchild==NULL && T->rchild!=NULL) || (T->lchild!=NULL && T->rchild==NULL))
return(onesoncount(T->lchild)+onesoncount(T->rchild)+1);
else
return(onesoncount(T->lchild)+onesoncount(T->rchild));
}
int twosoncount(BiTree T)
{
if (T==NULL)
return 0;
else if (T->lchild==NULL || T->rchild==NULL)
return(twosoncount(T->lchild)+twosoncount(T->rchild));
else if (T->lchild!=NULL && T->rchild!=NULL)
return(twosoncount(T->lchild)+twosoncount(T->rchild)+1);
return 1;
}
int BTDepth(BiTree T)
{
if(!T)
return 0;
else
{
int h1=BTDepth(T->lchild);
int h2=BTDepth(T->rchild);
if(h1>h2)
return h1+1;
else
return h2+1;
}
}
int main(int argc, char* argv[])
{
BiTree T;
cout<<"Please input data (/ for NULL node!) : ";
CreateBiTree( T);
cout<<"先序遍历二叉树 :";
PreOrderTraverse( T);
cout<<endl;
cout<<"中序遍历二叉树 :";
InOrderTraverse( T);
cout<<endl;
cout<<"后序遍历二叉树 :";
PostOrderTraverse(T);
cout<<endl;
cout<<"二叉树中叶子结点的个数 :"<<LeafCount(T)<<endl;
cout<<"二叉树中结点的个数 ："<<NodeCount(T)<<endl;
cout<<"二叉树的深度 :"<<BTDepth( T) <<endl;
cout<<"双孩子结点个数 :"<<twosoncount( T)<<endl;
cout<<"单孩子结点个数"<<onesoncount(T) <<endl;
return 0;
}
运行结果：
3、已知二叉树的前序遍历和中序遍历序列，构造对应的二叉树。
程序代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#define MaxSize 100
typedef struct Node
{
char data;
struct Node * lchild,*rchild;
}BitNode,*BiTree;
void CreateBiTree(BiTree *T,char *pre,char *in,int len);
void Visit(BiTree T,BiTree pre,char e,int i);
void PrintLevel(BiTree T);
void PrintLRT(BiTree T);
void PrintLevel(BiTree T)
{
BiTree Queue[MaxSize];
int front,rear;
if(T==NULL)
return;
front=-1;
rear=0;
Queue[rear]=T;
while(front!=rear)
{
front++;
printf("%2c",Queue[front]->data);
if(Queue[front]->lchild!=NULL)
{
rear++;
Queue[rear]=Queue[front]->lchild;
}
if(Queue[front]->rchild!=NULL)
{
rear++;
Queue[rear]=Queue[front]->rchild;
}
}
}
void PrintLRT(BiTree T)
{
if (T!=NULL)
{
PrintLRT(T->lchild);
PrintLRT(T->rchild);
printf("%2c",T->data);
}
}
void CreateBiTree(BiTree *T,char *pre,char *in,int len)
{
int k;
char *temp;
if(len<=0)
{
*T=NULL;
return;
}
*T=(BitNode*)malloc(sizeof(BitNode));
(*T)->data=*pre;
for(temp=in;temp<in+len;temp++)
if(*pre==*temp)
break;
k=temp-in;
CreateBiTree(&((*T)->lchild),pre+1,in,k);
CreateBiTree(&((*T)->rchild),pre+1+k,temp+1,len-1-k);
}
void main()
{
BiTree T,ptr=NULL;
int len;
char pre[MaxSize],in[MaxSize];
T=NULL;
printf("由先序序列和中序序列构造二叉树：\n");
printf("请你输入先序的字符串序列：");
gets(pre);
printf("请你输入中序的字符串序列：");
gets(in);
len=strlen(pre);
CreateBiTree(&T,pre,in,len);
printf("你建立的二叉树后序遍历结果是：\n");
PrintLRT(T);
printf("\n你建立的二叉树层次遍历结果是：\n");
PrintLevel(T);
printf("\n");
}
六、注意事项
1、 遍历的思想。
七、思考题
1、用非遍历算法如何实现？
实验五 查找
一、实验目的及要求
1、掌握查找的不同方法，并能用高级语言实现查找算法。
2、熟练掌握顺序表的查找方法和有序顺序表的折半查找算法以及静态查找树的构造方法和查找算法。
3、掌握二叉排序树的生成、插入、删除、输出运算。
二、实验学时
3学时
三、实验任务
1、顺序表的顺序查找
2、 有序顺序表的二分查找的递归算法
四、实验重点、难点
1、设置一个监视哨。
2、mid的变化。
3、快速排序
4、二路归并中的"一趟归并"算法
五、操作要点
任务1、顺序表的顺序查找
#include<stdio.h>
#include<malloc.h>
#include<conio.h>
#define MAX_LENGTH 11
typedef int KeyType;
typedef struct
{ KeyType *elem;
int length;
}SSTable;
int Search_Seq(SSTable ST,KeyType key)
{ int i;
ST.elem[0]=key;
for(i=ST.length;!(ST.elem[i]==key);--i);
return i;
}
int main()
{int i,m,n;
SSTable table1;
table1.elem=(int *)malloc(MAX_LENGTH*sizeof(int));
table1.length=MAX_LENGTH;
printf("数组元素:");
for(i=1;i<MAX_LENGTH;i++)
scanf("%d",&table1.elem[i]);
for(i=1;i<MAX_LENGTH;i++)
printf("%d ",table1.elem[i]);
printf("\n请输入查找元素:");
scanf("%d",&m);
n=Search_Seq(table1,m);
if(0==n)
printf("未找到元素");
else
printf("查找的元素的位置为elem.[%d]\n",n);
getch();
return 0;
}
任务2、有序顺序表的二分查找的算法
#include<stdio.h>
#include<malloc.h>
#include<conio.h>
#define MAX_LENGTH 11
typedef int KeyType;
typedef struct
{ KeyType *elem;
int length;
}SSTable;
/* 在有序查找表中折半查找其关键字等于 key 的数据元素*/
int Search_Seq(SSTable ST,KeyType key) //Search_Seq function
{ int mid,low=1,high=ST.length;
while(low<=high)
{ mid=(low+high)/2;
if(key==ST.elem[mid])
return (mid);
else if(key<ST.elem[mid])
high=mid-1;
else
low=mid+1;
}
return (0);
}
int main()
{int i,m,n;
SSTable table1;
table1.elem=(int *)malloc(MAX_LENGTH*sizeof(int));
table1.length=MAX_LENGTH;
printf("数组元素:");
for(i=1;i<MAX_LENGTH;i++)
scanf("%d",&table1.elem[i]);
for(i=1;i<MAX_LENGTH;i++)
printf("%d ",table1.elem[i]);
printf("\n请输入查找元素:");
scanf("%d",&m);
n=Search_Seq(table1,m);
if(0==n)
printf("未找到元素");
else
printf("查找的元素的位置为elem.[%d]\n",n);
getch();
return 0;
}
任务3、二叉排序树的查找、插入、删除等基本操作的实现
#include<iostream.>
using namespace std;
typedef int KeyType;
typedef struct tree//声明树的结构
{
struct tree *left; //存放左子树的指针
struct tree *right; //存放又子树的指针
KeyType key; //存放节点的内容
} BSTNode, * BSTree; //声明二叉树的链表
BSTree insertBST(BSTree tptr,KeyType key)// 在二叉排序树中插入结点
{ //若二叉排序树tptr中没有关键字为key的结点，则插入，否则直接返回
BSTree f,p=tptr; //p的初值指向根结点
while(p) //查找插入位置，循环结束时，p是空指针，f指向待插入结点的双亲
{
if(p->key==key) //树中已有key，无须插入
return tptr;
f=p; //f保存当前查找的结点，即f是p的双亲
p=(key<p->key)?p->left:p->right;
}
p=(BSTree )malloc(sizeof(BSTNode)); //生成新结点
p->key=key; p->left=p->right=NULL;
if(tptr==NULL) //原树为空，新插入的结点为新的根
tptr=p;
else
if(key<f->key)
f->left=p;
else
f->right=p;
return tptr;
}
BSTree createBST()//建立二叉树
{
BSTree t=NULL; //根结点
KeyType key;
cin>>key;
while(key!=-1)
{
t=insertBST(t,key);
cin>>key;
}
return t;
}
void inorder_btree(BSTree root)// 中序遍历打印二叉排序树
{
BSTree p=root;
if(p!=NULL){
inorder_btree(p->left );
cout<<p->key<<" ";
inorder_btree(p->right );
}
}
int searchBST(BSTree t,KeyType key)//查找
{
if(key==t->key)
return 1;
if(t==NULL)
return 0;
if(key<t->key)
return searchBST(t->left,key);
else
return searchBST(t->right,key);
}
BSTree deleteBST(BSTree tptr,KeyType key)//删除
{
BSTree p,tmp,parent=NULL;
p=tptr;
while(p)
{
if(p->key==key)
break;
parent=p;
p=(key<p->key)?p->left:p->right;
}
if(!p) return NULL;
tmp=p;
if(!p->right&&!p->left) /*p的左右子树都为空*/
{
if(!parent) //要删根，须修改根指针
tptr=NULL;
else if(p==parent->right)
parent->right=NULL;
else
parent->left=NULL;
free(p);
}
else if(!p->right) //p的右子树为空，则重接p的左子树
{
p=p->left;
if(!parent) //要删根，须修改根指针
tptr=p;
else if(tmp==parent->left)
parent->left=p;
else
parent->right=p;
free(tmp);
}
else if(!p->left) //的左子树为空，则重接p的左子树
{
p=p->right;
if(!parent) //要删根，须修改根指针
tptr=p;
else if(tmp==parent->left)
parent->left=p;
else
parent->right=p;
free(tmp);
}
else if(p->right&&p->left) //p有左子树和右子树，用p的后继覆盖p然后删去后继
{ //另有方法：用p的前驱覆盖p然后删去前驱||合并p的左右子树
parent=p; //由于用覆盖法删根，则不必特殊考虑删根
p=p->right;
while(p->left)
{
parent=p;
p=p->left;
}
tmp->key=p->key;
if(p==parent->left)
parent->left=NULL;
else
parent->right=NULL;
free(p);
}
return tptr;
}
int main()
{
KeyType key;
int flag,test;
char cmd;
BSTree root;
do
{
cout<<"请选择你要执行的操作:"<<endl;
cout<<"创建一棵二叉排序树:C.退出:E\n";
flag=0;
do
{
if(flag!=0)
cout<<"选择操作错误！请重新选择！\n";
fflush(stdin);
cin>>cmd;
flag++;
}while(cmd!='c'&&cmd!='C'&&cmd!='e'&&cmd!='E');
if(cmd=='c'||cmd=='C')
{
cout<<"请输入你所要创建的二叉树的结点的值，以-1结束：\n";
root=createBST();
do
{
flag=0;
cout<<"中序遍历二叉树："<<endl;
inorder_btree(root);
cout<<"\n请选择你要对这棵二叉树所做的操作:查找:S.插入:I.删除:D.退出:Q"<<endl;
do{
if(flag!=0)
cout<<"选择操作错误！请重新选择！\n";
fflush(stdin);
scanf("%c",&cmd);
flag++;
}while(cmd!='s'&&cmd!='S'&&cmd!='i'&&cmd!='I'&&cmd!='d'&&cmd!='D'&&cmd!='q'&&cmd!='Q');
switch(cmd)
{
case 's':
case 'S':
cout<<"请输入你要查找结点的关键字：\n";
cin>>key;
test=searchBST(root,key);
if(test==0)
cout<<"\n对不起，你所查找的结点 "<<key<<"不存在!";
else
cout<<"\n成功找到结点\n"<<key<<" ";
break;
case 'i':
case 'I':
cout<<"请输入你要插入结点的关键字：\n";
cin>>key;
root=insertBST(root,key); //注意必须将值传回根
break;
case 'd':
case 'D':
cout<<"请输入你要删除结点的关键字：\n";
cin>>key;
root=deleteBST(root,key); //注意必须将值传回根
if(root==NULL)
cout<<"\n对不起，你所删除的结点 "<<key<<" 不存在!\n";
else
cout<<"\n成功删除结点 "<<key<<" ";
break;
}
}while(cmd!='q'&&cmd!='Q');
}
}while(cmd!='e'&& cmd!='E');
return 0;
}
六、注意事项
1、mid的变化。
七、思考题
1、在用拉链法解决冲突的散列表上如何插入元素？