课程实验报告
课程名称： 数据结构
专业班级：
学 号：
姓 名：
指导教师：
报告日期：
计算机科学与技术学院
目 录
1 课程实验概述............................................................................................................... 1
2 实验一 基于顺序结构的线性表实现
2.1 问题描述............................................................................................................ 2
2.2 系统设计............................................................................................................ 2
2.3 系统实现............................................................................................................ 2
2.4 效率分析............................................................................................................ 2
3 实验二 基于链式结构的线性表实现
3.1 问题描述............................................................................................................ 3
3.2 系统设计............................................................................................................ 3
3.3 系统实现............................................................................................................ 3
3.4 效率分析............................................................................................................ 3
4 实验三 基于二叉链表的二叉树实现
4.1 问题描述............................................................................................................ 4
4.2 系统设计............................................................................................................ 4
4.3 系统实现............................................................................................................ 4
4.4 效率分析............................................................................................................ 4
5 实验总结与评价............................................................................................................ 5
1 课程实验概述
本课程实验为数据结构试验，包括三个实验内容，实验目的在于：
1．加深对数据结构和算法的理解，进一步提高学生编程能力；
2．培养和提高学生分析问题与解决问题的综合能力；
3．整理资料，撰写规范的实验报告。
2 实验一 基于顺序结构的线性表实现
2.1 问题描述
基于顺序存储结构，实现线性表的基本的、常见的运算。 实验要求：
⑴ 提供一个实现功能的演示系统
⑵ 具体物理结构和数据元素类型自行选定
⑶ 线性表数据可以使用磁盘文件永久保存
2.2 系统设计
线性表的顺序存储表示：
typedef struct {
ElemType *elem; 指针，指向顺序存放的一串数据元素
int length; 表长（实际数据元素个数）
int size; 表的大小（最多存贮数据元素个数）
}SqList；
相关函数的算法思想描述：
InitList(&L) (创建表，此处是指表的初始化)：
（1）申请存储数据元素空间
（2）置表长为0.
DestroyList(&L) (销毁表)：
（1）释放存储数据元素的空间置指针值为NULL。
ClearList(&L) (置表空)：
（1）置表长为空（length=0）
ListEmpty(L) (判空)：
（1）若表长=0，返回TRUE，否则返回FALSE。
ListLength(L) (求表长)：
（1）返回表长
GetElem (L, i, &e) (获取数据元素)：
（1）将第i单元值赋值给e
LocateElem( L,e,compare( ) ) （查找数据元素）
（1）按compare条件顺序查找e，若找到（第一次找到）返回对应位序，若未找到返回0
PrioreElem( L, cur_e, &pre_e ) （获得前驱）
（1）查找cur_e获取位序K
（2）若K>1，将K-1号单元的元素赋值给pre_e并返回，否则返回ERROR。
NextElem( L, cur_e, &next_e ) ( 获取后继）：
（1）查找cur_e, 获得位序K
（2）若K<表长，将K+1号元素值赋值给next_e并返回，否则返回ERROR。
ListInsert( &L, i, e ) (插入数据元素）：
（1）移动元素，将位序为L.length ~ i 的数据元素顺序向后移动一个存储单元
（2）插入新值，将e置入第i号存储单元 （3）修改表长，将表长加1
ListDelete(&L, i, &e) （删除数据元素）：
（1）获取返回值，将i号单元数据值赋给e返回
（2）移动元素，将序号i+1 ~ L.length的数据元素顺序前移一个存储单元 （3）修改表长，将表长减1
ListTraverse( L, visit( ) )
(1)调用visit函数顺序访问每一个数据元素，用L.length控制循环次数。
2.3 系统实现
相关结构及函数原型的说明（C语言描述）
/* Linear Table On Sequence Structure */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define LIST_INIT_SIZE 100 /*线性表存储空间的初始分配量*/
#define LISTINCREMENT 10 /*线性表存储空间的分配增量*/
#define OVERFLOW 0
#define OK 1
#define TURE 1
#define FLASE 0
#define ERROR 0
/*------------------------------------------------------*/
typedef int status;
typedef struct{
int item1;
}Elemtype;
typedef struct{
Elemtype * elem;
int length;
int listsize;
}SqList;
/*------------------------------------------------------*/
status IntiaList(SqList * L);
status DestroyList(SqList * L);
status ClearList(SqList L);
status ListEmpty(SqList L);
int ListLength(SqList L);
status GetElem(SqList L,int i,Elemtype * e);
status LocatElem(SqList L,Elemtype e,status (* equal)(Elemtype x,Elemtype y));
status PriorElem(SqList L,Elemtype cur_e,Elemtype * pre_e);
status NextElem(SqList L,Elemtype cur_e,Elemtype * next_e);
status ListInsert(SqList *L,int i, Elemtype e);
status ListDelete(SqList *L,int i, Elemtype e);
status ListTrabverse(SqList L,void (* disply)(Elemtype e));
/*------------------------------------------------------*/
status equal(Elemtype x, Elemtype y);
void display(Elemtype e);
/*------------------------------------------------------*/
void menu(void);
/*------------------------------------------------------*/
void main(void){
SqList L1,L2;
int op=0;
L1.elem=L2.elem=NULL;
do{
system("cls");
menu();
printf(" Please input your option[0-12]:");
scanf("%d",&op);
switch(op){
case 0:
if(L1.elem){
printf("\tPlease destory L1 first!");
op=-1;
getchar();getchar();
}
else
printf("\n\t\tThe program is exiting");
break;
case 1:
if(IntiaList(&L1))
printf("\n here is IntiaList(),which being realized\n");
else
printf("IntiaList()is failed!");
getchar();getchar();
break;
case 2:
if(DestroyList(&L1))
printf("\n here is DestroyList(),which being realized\n");
else
printf("DestroyList()is failed!");
getchar();getchar();
break;
case 3:
if(ClearList(L1))
printf("here is ClearList(),which being realized\n");
else
printf("ClearList()is failed!");
getchar();getchar();
break;
case 4:
if(ListEmpty(L1))
printf("\tThe list is empty\n");
else
printf("\tThe list is not empty\n");
getchar();getchar();
break;
case 5:
printf("\n here is ListLength() ,which being realized\n");
printf(" the listlength is %d",ListLength(L1));
getchar();getchar();
break;
case 6:
{
int i=0;
Elemtype e;
printf("Please input the location:");
scanf("%d",&i);
if(GetElem(L1,i,&e))
printf("\tThe %dth elem is %d.\n",i,e);
else
printf("\tInvaild location.");
printf("\n here is GetElem(),which being realized\n");
getchar();getchar();
break;
}
case 7:{
Elemtype e;
int n;
printf("\tPlease input the item you want to find:");
scanf("%d",&e);
n=LocatElem(L1,e,equal);
if(n)
printf("\t%d is the %dth item in L1",e,n);
else
printf("\t%d is not in L1",e);
printf("\n here is LocatElem(),which being realized\n");
getchar();getchar();
break;
}
case 8:{
Elemtype cur_e,pre_e;
printf("\tPlease input the cur_e :");
scanf("%d",&cur_e);
if(PriorElem(L1,cur_e,&pre_e))
printf("the pre_e is: %d",pre_e);
else
printf("Not Found!");
printf("\n here is PriorElem(),which being realized\n");
getchar();getchar();
break;
}
case 9: {
Elemtype cur_e,next_e;
printf("\tPlease input the cur_e :");
scanf("%d",&cur_e);
if(NextElem(L1,cur_e,&next_e))
printf("the next_e is: %d",next_e);
else
printf("Not Found!");
printf("\n here is NextElem(),which being realized\n");
getchar();getchar();
break;
}
case 10: {
Elemtype e;
int i;
printf("\tPlease input the item you want to insert:");
scanf("%d",&e);
printf("\tPlease input the position:");
scanf("%d",&i);
if(ListInsert(&L1,i,e))
printf("\tThe %d is insert at %d position.",e,i);
else
printf("\tInsert failed!");
printf("\n here is ListInsert(),which being realized\n");
getchar();getchar();
break;
}
case 11:{
Elemtype e;
int i;
printf("\tPlease input the position:");
scanf("%d",&i);
if(ListDelete(&L1,i,e))
printf("\tThe %dth item is deleted. ");
else
printf("\tDelete failed.");
printf("\n here is ListDelete(),which being realized\n");
getchar();getchar();
break;
}
case 12: {printf("\n here is ListTrabverse(),which being realized\n");
if(!L1.elem)
printf("\n linear table L1 does not exist!\n");
else if(!ListTrabverse(L1,display))
printf("\n this linear table is empty!\n");
getchar();getchar();
break;
}
default: ;
}
}while(op);
getchar();getchar();
}
status IntiaList(SqList *L){
/* 构造一个空的线性表*/
L->elem=(Elemtype * )malloc(LIST_INIT_SIZE * sizeof(Elemtype));
if(! L->elem) exit(OVERFLOW);
L->length=0;
L->listsize=LIST_INIT_SIZE;
return OK;
}
status DestroyList(SqList *L){
L->elem=NULL;
L->listsize=0;
return OK;
}
status ClearList(SqList L){
L.length=0;
return OK;
}
status ListEmpty(SqList L){
if(L.length==0)
return TURE;
else
return FLASE;
}
int ListLength(SqList L){
return L.length;
}
status GetElem(SqList L,int i,Elemtype * e){
if(i>L.length||i<1)
return ERROR;
*e=L.elem[i-1];
}
status LocatElem(SqList L,Elemtype e,status (* equal)(Elemtype ,Elemtype )){
int i;
i=1;
Elemtype *p;
p=L.elem;
while(i<=L.length&&!(* equal)(*p++,e)) ++i;
if(i<=L.length) return i;
else return 0;
}
status PriorElem(SqList L,Elemtype cur_e,Elemtype * pre_e){
int i;
for(i=1;i<L.length;i++)
if((L.elem[i]).item1==cur_e.item1){
*pre_e=L.elem[i-1];
return 1;
}
return 0;
}
status NextElem(SqList L,Elemtype cur_e,Elemtype * next_e){
int i;
for(i=0;i<L.length-1;i++)
if((L.elem[i]).item1==cur_e.item1){
*next_e=L.elem[i+1];
return 1;
}
return 0;
}
status ListInsert(SqList *L,int i, Elemtype e){
if(i<1||i>L->length+1) return ERROR;
Elemtype *newbase,*q,*p;
if(L->length>=L->listsize){
newbase=(Elemtype *)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(Elemtype));
if(!newbase)exit(OVERFLOW);
L->elem=newbase;
L->listsize+=LISTINCREMENT;
}
q=&(L->elem[i]);
for(p=&(L->elem[L->length]);p>=q;--p) *(p+1)=*p;
*p=e;
L->length++;
return OK;
}
status ListDelete(SqList *L,int i, Elemtype e){
if((i<1)||(i>L->length)) return ERROR;
Elemtype *p,*q;
p=&(L->elem[i-1]);
e=*p;
q=L->elem+L->length-1;
for(++p;p<=q;++p) *(p-1)=*p;
--L->length;
return OK;
}
status ListTrabverse(SqList L, void (* disply)(Elemtype e)){
int i;
if(!L.length) return(0);
printf("\n-------------all elements of linear table----------------\n");
for(i=0;i<L.length;i++) display(L.elem[i]);
return(1);
}
/*------------------------------------------------------*/
void menu(void){
printf("\n\n");
printf(" Menu for Linear Table On Sequence Structure \n");
printf("------------------------------------------------------\n");
printf(" 1. IntiaList 7. LocatElem\n");
printf(" 2. DestroyList 8. PriorElem\n");
printf(" 3. ClearList 9. NextElem \n");
printf(" 4. ListEmpty 10. ListInsert\n");
printf(" 5. ListLength 11. ListDelete\n");
printf(" 6. GetElem 12. ListTrabverse\n");
printf(" 0. Exit\n");
printf("------------------------------------------------------\n");
}
/*------------------------------------------------------*/
status equal(Elemtype x, Elemtype y){
return (x.item1==y.item1);
}
void display(Elemtype e){
printf("%d ",e.item1);
}
2.4 效率分析
分公司的
InitList(创建表，此处是指表的初始化)：
DestroyList(销毁表)： ClearList(置表空)： ListEmpty(判空)： ListLength(求表长)：
GetElem (L, i, &e) (获取数据元素)： 上述操作时间复杂度均为O(1)
LocateElem( L,e,compare( ) ) （查找数据元素） T(n)=O(n)
PrioreElem( L, cur_e, &pre_e ) （获得前驱） T(n)=O(n)
NextElem( L, cur_e, &next_e ) ( 获取后继）： T(n)=O(n)
ListInsert( &L, i, e ) (插入数据元素）： ListDelete(&L, i, &e) （删除数据元素）：
删除和插入操作的时间主要耗费在移动元素上，而移动元素的个数取决于插入或删除的元素位置。
假设pi是删除第i个元素的概率，则在长度为n的线性表中删除或插入一个元素所需移动元素的次数的期望值为
删除：
插入：
若在任何位置插入或删除是等概率的，则：
插入：
删除：
则插入与删除的时间复杂度为O(n)
3 实验二 基于链式结构的线性表实现
3.1 问题描述
基于链式存储结构，实现线性表的基本的、常见的运算。 实验要求：
⑴ 提供一个实现功能的演示系统
⑵ 具体物理结构和数据元素类型自行选定
⑶ 线性表数据可以使用磁盘文件永久保存
3.2 系统设计
线性表的链式表式（具体使用时带头结点）：
typedef struct LNode{
ElemType data; 数据域，存放数据元素
struct LNode *next; 指针域，指向下一个结点（或为NULL）
}LNode,* LinkList;
相关函数的算法思想描述：
注：为操作方便采用带头结点的链表表示。
InitList(&L)(创建表，此处是指表的初始化)：
（1）头指针指向申请的一个存储结点，存储结点指针域赋值NULL。
DestroyList(&L)(销毁表)：
（1）释放所有结点包括头结点，头指针置为NULL。 ClearList(L)(置表空)：
（1）释放所有数据存储结点（不包括头结点），头结点指针域置为NULL。
ListEmpty(L)(判空)：
（1）若头结点指针域为NULL则返回TRUE，否则返回FALSE。
ListLength(L)(求表长)：
（1）指针p指向头结点
（2）当p指向的结点的指针域非空时移动指针p，并统计移动次数n
（3）返回移动次数n
GetElem (L, i, &e) (获取数据元素)：
（1）指针p指向头结点
（2）将指针p移动i次，使指针p指向第i号单元
（3）将第i单元值赋值给e并返回
LocateElem( L,e,compare( ) ) （查找数据元素）
（1）指针p指向头结点，通过p=p->next,依次移动指针，访问数据域，用compare函数与e进行比较判断,并记录移动次数i
（2）若第一次找到与e对应的结点数据域,返回移动次数i，若直至p=NULL,仍未找到，返回0
PrioreElem( L, cur_e, &pre_e ) （获得前驱）
（1）指针p指向头结点
（2）通过p=p->next移动p,将指针pl指向其前驱，比较当前p所指结点数据域与cur_e
（3）若相等且pl不是指向头结点，将pl所指结点数据域赋值给pre_e并返回，若相等但pl指向头结点返回ERROR；若访问至p=NULL，返回ERROR
NextElem( L, cur_e, &next_e ) ( 获取后继）：
（1）依次移动指针p,比较p->data与cur_e
（2）若相等且p->next不等于null，将p->next->data赋值给next_e并返回，否则返回ERROR
ListInsert( L, i, e ) (插入数据元素）：
（1）指针定位，将指针p移至第i号数据存储结点的直接前驱
（2）指针准备，将指针q指向新申请结点，其数据域由e赋值，
（3）修改结点指针域，q->next=p->next, p->next=p
ListDelete(L, i, &e) （删除数据元素）：
（1）指针定位，将指针p移至第i号数据存储结点的直接前驱，q指向i号结点，将i号单元数据域值赋值给e
（2）修改结点指针域，p->next=q->next
（3）释放q所指结点空间
ListTraverse( L, visit( ) )
(1)调用visit函数依次访问每一个数据元素，p=p->next控制访问，p=null表示遍历结束。
3.3 系统实现
/* Linear Table On Link Structure */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define OVERFLOW 0
#define OK 1
#define TURE 1
#define FLASE 0
#define ERROR 0
/*------------------------------------------------------*/
typedef int status;
typedef int Elemtype;
typedef struct LNode{
Elemtype data;
struct LNode *next;
}LNode,*Link;
typedef struct{
Link head,tail;
int length;
} LinkList;
/*------------------------------------------------------*/
status IntiaList(LinkList * L);
status DestroyList(LinkList * L);
status ClearList(LinkList *L);
status ListEmpty(LinkList L);
int ListLength(LinkList L);
status GetElem(LinkList L,int i,Elemtype * e);
status LocatElem(LinkList L,Elemtype e,status (* equal)(Elemtype x,Elemtype y));
status PriorElem(LinkList *L,Elemtype cur_e,Elemtype * pre_e);
status NextElem(LinkList *L,Elemtype cur_e,Elemtype * next_e);
status ListInsert(LinkList *L,int i, Elemtype e);
status ListDelete(LinkList *L,int i, Elemtype e);
status ListTrabverse(LinkList L,void (* disply)(Elemtype e));
/*------------------------------------------------------*/
status equal(Elemtype x, Elemtype y);
void display(Elemtype e);
/*------------------------------------------------------*/
void menu(void);
/*------------------------------------------------------*/
void main(void){
LinkList L1;
L1.head=NULL;
int op=0;
do{
system("cls");
menu();
printf(" Please input your option[0-12]:");
scanf("%d",&op);
switch(op){
case 0:
if(L1.head){
printf("\tPlease destory L1 first!");
op=-1;
getchar();getchar();
}
else
printf("\n\t\tThe program is exiting");
break;
case 1:
if(IntiaList(&L1))
printf("\n here is IntiaList(),which being realized\n");
else
printf("IntiaList()is failed!");
getchar();getchar();
break;
case 2:
if(DestroyList(&L1))
printf("\n here is DestroyList(),which being realized\n");
else
printf("DestroyList()is failed!");
getchar();getchar();
break;
case 3:
if(ClearList(&L1))
printf("here is ClearList(),which being realized\n");
else
printf("ClearList()is failed!");
getchar();getchar();
break;
case 4:
if(ListEmpty(L1))
printf("\tThe list is empty\n");
else
printf("\tThe list is not empty\n");
getchar();getchar();
break;
case 5:
printf("\n here is ListLength() ,which being realized\n");
printf(" the listlength is %d",ListLength(L1));
getchar();getchar();
break;
case 6:
{
int i=0;
Elemtype e;
printf("Please input the location:");
scanf("%d",&i);
if(GetElem(L1,i,&e))
printf("\tThe %dth elem is %d.\n",i,e);
else
printf("\tInvaild location.");
printf("\n here is GetElem(),which being realized\n");
getchar();getchar();
break;
}
case 7:{
Elemtype e;
int n;
printf("\tPlease input the item you want to find:");
scanf("%d",&e);
n=LocatElem(L1,e,equal);
if(n)
printf("\t%d is the %dth item in L1",e,n);
else
printf("\t%d is not in L1",e);
printf("\n here is LocatElem(),which being realized\n");
getchar();getchar();
break;
}
case 8:{
Elemtype cur_e,pre_e;
printf("\tPlease input the cur_e :");
scanf("%d",&cur_e);
if(PriorElem(&L1,cur_e,&pre_e))
printf("the pre_e is: %d",pre_e);
else
printf("Not Found!");
printf("\n here is PriorElem(),which being realized\n");
getchar();getchar();
break;
}
case 9: {
Elemtype cur_e,next_e;
printf("\tPlease input the cur_e :");
scanf("%d",&cur_e);
if(NextElem(&L1,cur_e,&next_e))
printf("the next_e is: %d",next_e);
else
printf("Not Found!");
printf("\n here is NextElem(),which being realized\n");
getchar();getchar();
break;
}
case 10: {
Elemtype e;
int i;
printf("\tPlease input the item you want to insert:");
scanf("%d",&e);
printf("\tPlease input the position:");
scanf("%d",&i);
if(ListInsert(&L1,i,e))
printf("\tThe %d is insert at %d position.",e,i);
else
printf("\tInsert failed!");
printf("\n here is ListInsert(),which being realized\n");
getchar();getchar();
break;
}
case 11:{
Elemtype e;
int i;
printf("\tPlease input the position:");
scanf("%d",&i);
if(ListDelete(&L1,i,e))
printf("\tThe %dth item is deleted. ");
else
printf("\tDelete failed.");
printf("\n here is ListDelete(),which being realized\n");
getchar();getchar();
break;
}
case 12: {printf("\n here is ListTrabverse(),which being realized\n");
if(!L1.head)
printf("\n linear table L1 does not exist!\n");
else if(!ListTrabverse(L1,display))
printf("\n this linear table is empty!\n");
getchar();getchar();
break;
}
default: ;
}
}while(op);
getchar();getchar();
}
status IntiaList(LinkList *L){
/* 构造一个空的链表*/
Link p;
p=(Link)malloc(sizeof(LNode));
if(!p) exit(OVERFLOW);
p->next=NULL;
L->head=L->tail=p;
L->length=0;
return OK;
}
status DestroyList(LinkList *L){
Link p,q;
p=L->head;
q=L->head->next;
free(p);
p=q;
while(p){
q=q->next;
free(p);
p=q;
}
L->length=0;
L->head=L->tail=NULL;
return OK;
}
status ClearList(LinkList *L){
Link p,q;
p=q=L->head->next;
while(p){
q=q->next;
free(p);
p=q;
}
L->length=0;
L->head=L->tail;
return OK;
}
status ListEmpty(LinkList L){
if(L.length==0)
return TURE;
else
return FLASE;
}
int ListLength(LinkList L){
return L.length;
}
status GetElem(LinkList L,int i,Elemtype *e){
Link p=L.head;
int j=1;
if(i>L.length||i<1) return ERROR;
for(j=0;j<i;j++)
p=p->next;
*e=p->data;
return OK;
}
status LocatElem(LinkList L,Elemtype e,status (* equal)(Elemtype ,Elemtype )){
Link p=L.head;
int i=0;
do{
p=p->next;
i++;
}while(p&&!equal(p->data,e));
return i;
}
status PriorElem(LinkList *L,Elemtype cur_e,Elemtype * pre_e){
Link p,q;
p=L->head->next;
while(p->next)
{
q=p->next;
if(q->data==cur_e) {
*pre_e=p->data;
return OK;
}
p=q;
}
return 0;
}
status NextElem(LinkList *L,Elemtype cur_e,Elemtype * next_e){
Link p,q;
p=L->head->next;
while(p->next)
{
q=p->next;
if(p->data==cur_e) {
*next_e=q->data;
return OK;
}
p=q;
}
return 0;
}
status ListInsert(LinkList *L,int i, Elemtype e){
Link p,s;
p=L->head;
int j=0;
while(p&&j<i-1){p=p->next;++j;}
if(!p||j>i-1) return ERROR;
s=(Link)malloc(sizeof(LNode));
s->data=e;s->next=p->next;
p->next=s;
L->length++;
return OK;
}
status ListDelete(LinkList *L,int i, Elemtype e){
Link p,q;
p=L->head;
int j=0;
while(p->next&&j<i-1){p=p->next;++j;}
if(!p->next||j>i-1) return ERROR;
q=p->next;p->next=q->next;
e=q->data;free(q);
L->length--;
return OK;
}
status ListTrabverse(LinkList L, void (* disply)(Elemtype e)){
int i;
Link p=L.head->next;
if(!L.length) return(0);
printf("\n-------------all elements of linear table----------------\n");
for(i=0;i<L.length;i++){
disply(p->data);
p=p->next;
}
return OK;
}
/*------------------------------------------------------*/
void menu(void){
printf("\n\n");
printf(" Menu for Linear Table On Sequence Structure \n");
printf("------------------------------------------------------\n");
printf(" 1. IntiaList 7. LocatElem\n");
printf(" 2. DestroyList 8. PriorElem\n");
printf(" 3. ClearList 9. NextElem \n");
printf(" 4. ListEmpty 10. ListInsert\n");
printf(" 5. ListLength 11. ListDelete\n");
printf(" 6. GetElem 12. ListTrabverse\n");
printf(" 0. Exit\n");
printf("------------------------------------------------------\n");
}
/*------------------------------------------------------*/
status equal(Elemtype x, Elemtype y){
return (x==y);
}
void display(Elemtype e){
printf("%d ",e);
}
3.4 效率分析
主要分析插入和删除的时间复杂度：
插入：
假设线性表长度为n，在第i个之前插入的概率为pi ，则插入运算指针移动次数的数学期望为：
在等概率下，
平均时间复杂度：O(n)
最好情况时间复杂度：O(1)
最坏情况时间复杂度：O(n)
删除：
假设线性表长度为n，删除第i个结点的概率为pi ，则删除运算指针移动次数的数学期望为： 在等概率下，
平均时间复杂度：O(n)
最好情况时间复杂度：O(1)
最坏情况时间复杂度：O(n)
4 实验三 基于二叉链表的二叉树实现
4.1 问题描述
基于二叉链表，实现二叉树的下列运算：
① 二叉树生成；
② 前序、中序和后序遍历；
③ 计算叶子数目；
④ 按层次遍历；
⑤ 求二叉树高度； 实验要求：
⑴ 提供一个实现功能的演示系统
⑵ 具体物理结构和数据元素类型自行选定
⑶ ②、③和⑤运算分别采用递归和非递归算法实现
4.2 系统设计
相关函数的算法思想描述： 递归实现的操作定义：
前序遍历：
若二叉树为空，则空操作，否则：
（1）访问根结点
（2）前序遍历左子树
（3）前序遍历右子树 中序遍历：
若二叉树为空，则空操作，否则：
（1）中序遍历左子树
（2）访问根结点
（3）中序遍历右子树 后序遍历：
若二叉树为空，则空操作，否则：
（1）后序遍历左子树
（2）后序遍历右子树
（3）访问根结点 求树深：
若二叉树未空，返回树深0，否则：
（1）返回1+MAX[对左子树求树深的返回值，对右子树求树深的返回值
（2）对左子树求树深
（3）对右子树求树深
求叶子数目：
（1）若二叉树为空返回0，否则转(2)
（2）若二叉树左右子树为空，返回1，否则转（3）
（3）返回对“左子树求叶子数目”的的返回值+“对左子树求叶子数目”的返回值
（4）对左子树求叶子数目
（5）对右子树求叶子数目
4.3 系统实现
相关代码如下：
/*-------------------BiTree-------------------*/
#include <stdio.h>
#include <stdlib.h>
/*--------------------------------------------*/
#define TRUE 1
#define FALSE 0
#define ERROR -1
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define MAXQSIZE 100
#define BiTreeSp 7
#define BiTreeSpInput 3
#define MAX 100
/*--------------------------------------------*/
typedef int Status;
typedef struct ElemType{
char data;
}TElemType;
typedef struct BiTNode{
TElemType elem;
struct BiTNode *lchild,*rchild;
}BiTNode;
typedef BiTNode * SElemType;
typedef struct SqStack{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
typedef BiTNode * QElemType;
typedef struct SqQueue{
QElemType *base;
int front;
int rear;
}SqQueue;
enum definition {PreOrder,InOrder,PostOrder,LevelOrder};
/*--------------------------------------------*/
//BiTree
//NO.1
Status CreatBiTree(BiTNode ** T,char *s,int *num);
//NO.2
Status PreOrderTraverse(BiTNode * T,Status(*Visit)(TElemType e));
Status InOrderTraverse(BiTNode * T,Status(*Visit)(TElemType e));
Status PostOrderTraverse(BiTNode * T,Status(*Visit)(TElemType e));
//NO.3
Status BiTreeLeaf(BiTNode * T);
//NO.4
Status LevelOrderTraverse(BiTNode * T,Status(*Visit)(TElemType e));
//NO.5
Status BiTreeDepth(BiTNode * T);
//Others
Status menu(void);
Status Visit(TElemType e);
Status DisplayOutput(BiTNode *T);
Status DisplayInput(char *s,int num);
Status InitStack(SqStack *s);
Status Push(SqStack *s,SElemType e);
Status Pop(SqStack *s,SElemType *e);
Status InitQueue(SqQueue *q);
Status En(SqQueue *q,QElemType e);
Status De(SqQueue *q,QElemType *e);
Status Save(BiTNode *T);
Status Open(BiTNode **T);
Status WriteBiTree(BiTNode **T,char *s,int *i);
/*--------------------------------------------*/
int main(void){
BiTNode *T=NULL;
char s[MAX];int num=0;
int op;
do{
system("cls");
if(num)DisplayInput(s,num);
DisplayOutput(T);
menu();
printf("please input your option[0-9]: ");
scanf("%d",&op);
putchar('\n');
getchar(); //get the line break
switch(op){
case 0:break;
case 1:printf("\nThere is CreatBiTree(), which is been realized!\n");
CreatBiTree(&T,s,&num);getchar();
break;
case 2:printf("\nThere is PreOrderTraverse(), which is been realized!\n");
PreOrderTraverse(T,Visit);getchar();
break;
case 3:printf("\nThere is InOrderTraverse(), which is been realized!\n");
InOrderTraverse(T,Visit);getchar();
break;
case 4:printf("\nThere is PostOrderTraverse(), which is been realized!\n");
PostOrderTraverse(T,Visit);getchar();
break;
case 6:printf("\nThere is BiTreeLeaf(), which is been realized!\n");
BiTreeLeaf(T);getchar();
break;
case 5:printf("\nThere is LevelOrderTraverse(), which is been realized!\n");
LevelOrderTraverse(T,Visit);getchar();
break;
case 7:printf("\nThere is BiTreeDepth(), which is been realized!\n");
printf("\nThe depth of the BiTree is %d",BiTreeDepth(T));getchar();
break;
case 8:printf("\nThere is Save(), which is been realized!\n");
Save(T);getchar();
break;
case 9:printf("\nThere is Open(), which is been realized!\n");
Open(&T);getchar();
break;
default: ;
}//switch
}while(op);
printf("welcome to the system again!");
return 0;
}
Status menu(void){
printf("\t\t\tmenu for BiTree\n");
printf("--------------------------------------------------------\n");
printf("\t 1.CreatBiTree\n");
printf("\t 2.PreOrderTraverse \t 3.InOrderTraverse\n");
printf("\t 4.PostOrderTraverse\t 5.LevelOrderTraverse\n");
printf("\t 6.BiTreeLeaf \t 7.BiTreeDepth\n");
printf("\t 8.Save \t 9.Open\n");
printf("\t 0.Exit\n");
printf("--------------------------------------------------------\n");
return 0;
}//menu
Status DisplayInput(char *s,int num){
int i=0;
printf("--------------------------------------------------------\n");
printf("The Input: ");
while(i<num){
if(*(s+i)!=' ')
printf("%c",*(s+i));
else
printf("%c",BiTreeSpInput);
i++;
}
putchar('\n');
return 0;
}//DisplayInput
Status DisplayOutput(BiTNode *T){
//按顺序分别显示各操作的结果
if(T){
printf("--------------------------------------------------------");
PreOrderTraverse(T,Visit);
InOrderTraverse(T,Visit);
PostOrderTraverse(T,Visit);
LevelOrderTraverse(T,Visit);
BiTreeLeaf(T);
printf("\nThe depth of the BiTree is %d",BiTreeDepth(T));
printf("\n--------------------------------------------------------\n");
}
return 0;
}//DisplayOutput
Status CreatBiTree(BiTNode ** T,char *s,int *num){
//按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树，
//构造二叉链表表示的二叉树T。
char ch;
printf("\nPlease input the BiTree(PreOrder): ");
scanf("%c",&ch);
*(s+(*num)++)=ch;
if(ch=='\n') (*T)=NULL;
else{
if(ch==' ')(*T)=NULL;
else{
if(!((*T)=(BiTNode *)malloc(sizeof(BiTNode)))){
printf("节点空间分配失败！\n");
exit(ERROR);
}
(*T)->elem.data=ch;
CreatBiTree(&(*T)->lchild,s,num);
CreatBiTree(&(*T)->rchild,s,num);
}
}
return 0;
}//CreatBiTree
Status PreOrderTraverse(BiTNode * T,Status(*Visit)(TElemType e)){
//先输出，再入栈，
//访问左子树
//出栈，访问右子树
SqStack s;
InitStack(&s);
if(!T)
printf("This is an ampty BiTree!\n");
else{
printf("\nthe PreOrder:\t");
while(T!=NULL||s.top!=s.base){
if(T!=NULL){
printf("%c",T->elem.data);
putchar(' ');
Push(&s,T);
T=T->lchild;
}
else {
Pop(&s,&T);
T=T->rchild;
}
}//while
}
return 0;
}//PreOrderTraverse
Status InOrderTraverse(BiTNode * T,Status(*Visit)(TElemType e)){
//先入栈，访问左子树
//出栈，输出
//访问右子树
SqStack s;
InitStack(&s);
if(!T)
printf("This is an ampty BiTree!\n");
else{
printf("\nthe InOrder:\t");
while(T!=NULL||s.top!=s.base){
if(T!=NULL){
Push(&s,T);
T=T->lchild;
}
else{
Pop(&s,&T);
printf("%c",T->elem.data);
putchar(' ');
T=T->rchild;
}
}//while
}
return 0;
}//InOrderTraverse
Status PostOrderTraverse(BiTNode * T,Status(*Visit)(TElemType e)){
//用两个栈，访问左子树，入栈s1，访问右子树，入栈s2,当栈顶s1=s2时，表明
//栈顶元素的左右子树都被访问，此时 出栈，输出
SqStack s1,s2;
InitStack(&s1);
InitStack(&s2);
if(!T)
printf("This is an ampty BiTree!\n");
else{
printf("\nthe PostOrder:\t");
while(T!=NULL|| s1.top!=s1.base){
if(T!=NULL){
Push(&s1,T);
T=T->lchild;
}
else{
if(s2.top!=s2.base&&*(s1.top-1)==*(s2.top-1)){
Pop(&s1,&T);
s2.top--;
printf("%c",T->elem.data);
putchar(' ');
T=NULL;
}
else{
Pop(&s1,&T);
Push(&s1,T);
Push(&s2,T);
T=T->rchild;
}
}
}//while
}
return 0;
}//PostOrderTraverse
Status BiTreeLeaf(BiTNode * T){
//参照层次遍历，
//出队，判断左右孩子是否为空，是则输出，计数加1；否则将左右孩子入队
SqQueue q;
int leaf=0;
InitQueue(&q);
if(!T){
printf("This is an ampty BiTree!\n");
return 0;
}
printf("\nThe leaf(leaves) is(are): ");
if(T!=NULL) En(&q,T);
while(q.front!=q.rear){
De(&q,&T);
if(T->lchild==NULL&&T->rchild==NULL){
printf("%c",T->elem.data);
putchar(' ');
leaf++;
}
else{
if(T->lchild)En(&q,T->lchild);
if(T->rchild)En(&q,T->rchild);
}
}
printf("\nThe number(s) of leaf(leaves) is %d",leaf);
return leaf;
}//BiTreeLeaf
Status LevelOrderTraverse(BiTNode * T,Status(*Visit)(TElemType e)){
//将根结点指针入队
//出队，输出，将左右孩子指针入队
SqQueue q;
InitQueue(&q);
if(!T){
printf("This is an ampty BiTree!\n");
return 0;
}
else{
printf("\nThe LevelOrder:\t");
En(&q,T);
while(q.front!=q.rear){
De(&q,&T);
printf("%c",T->elem.data);
putchar(' ');
if(T->lchild)En(&q,T->lchild);
if(T->rchild)En(&q,T->rchild);
}
}
return 0;
}//LevelOrderTraverse
Status BiTreeDepth(BiTNode * T){
//递归，树的深度等于左右子树深度的较大值加1
int depth,depthleft,depthright;
if(!T)depth=0;
else {
depthleft=BiTreeDepth(T->lchild);
depthright=BiTreeDepth(T->rchild);
depth=1+(depthleft>depthright?depthleft:depthright);
}
return depth;
}//BiTreeDepth
Status Visit(TElemType e){
printf("%c",e.data);
putchar(' ');
return 0;
}//Visit
Status InitStack(SqStack *s){
s->base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
if(!s->base) exit(ERROR);
s->top=s->base;
s->stacksize=STACK_INIT_SIZE;
return 0;
}//InitStack
Status Push(SqStack *s,SElemType e){
if(s->top-s->base>=s->stacksize){
s->base=(SElemType *)realloc(s->base,(s->stacksize+STACKINCREMENT) * sizeof(SElemType));
if(!s->base) exit(ERROR);
s->top=s->base+s->stacksize;
s->stacksize+=STACKINCREMENT;
}
*s->top++=e;
return 0;
}//Push
Status Pop(SqStack *s,SElemType* e){
if(s->top==s->base) return ERROR;
(*e)=*--s->top; //s->top--;e=*s->top;
return 0;
}//Pop
Status InitQueue(SqQueue *q){
q->base=(QElemType *)malloc(MAXQSIZE *sizeof(QElemType));
if(!q->base) exit(ERROR);
q->front=q->rear=0;
return 0;
}//InitQueue
Status En(SqQueue *q,QElemType e){
if((q->rear+1)%MAXQSIZE==q->front) return ERROR;
q->base[q->rear]=e;
q->rear=(q->rear+1)%MAXQSIZE;
return 0;
}//En
Status De(SqQueue *q,QElemType *e){
if(q->front==q->rear) return ERROR;
(*e)=q->base[q->front];
q->front=(q->front+1)%MAXQSIZE;
return 0;
}//De
Status Save(BiTNode *T){
FILE *fin=fopen("c:\\BiTree.txt","w+");
SqStack s;
InitStack(&s);
while(T!=NULL||s.top!=s.base){
if(T!=NULL){
fprintf(fin,"%c",T->elem.data);
Push(&s,T);
T=T->lchild;
}
else {
fprintf(fin,"%c",BiTreeSp);
Pop(&s,&T);
T=T->rchild;
}
}//while
if(T==NULL&&s.top==s.base)
fprintf(fin,"%c",BiTreeSp);
fclose(fin);
printf("\nSaved!\n");
return 0;
}//Save
Status Open(BiTNode **T){
FILE *fout;
char s[MAX];
int i=0;
fout=fopen("c:\\BiTree.txt","r+");
if(!fout){
printf("The file is not exist!\n");
return 0;
}
fscanf(fout,"%s",s);
WriteBiTree(T,s,&i);
printf("\nOpened!\n");
return 0;
}//Open
Status WriteBiTree(BiTNode **T,char *s,int *i){
char ch;
ch=s[*i];(*i)++;
if(ch=='\0'){
// (*T)=NULL;
return 0;
}
if(ch==BiTreeSp)
(*T)=NULL;
else{
if(!((*T)=(BiTNode *)malloc(sizeof(BiTNode)))){
printf("节点空间分配失败！\n");
exit(ERROR);
}
(*T)->elem.data=ch;
WriteBiTree(&(*T)->lchild,s,i);
WriteBiTree(&(*T)->rchild,s,i);
}
return 0;
}
4.4 效率分析
遍历二叉树的算法中的基本操作是访问结点，则不论按哪种次序进行遍历，对含n个结点的二叉树，其时间复杂度均为O(n)。所需辅助空间为遍历过程中栈的最大容量即树深，最坏情况为n则空间复杂度也为O(n)。
求树深和叶子数目是基于遍历实现的时间和空间复杂度也均为O(n)。
5 实验总结与评价
通过此次上机实验，我对线性表，链表及二叉树有了更加深刻的认识。对于线性表和链表的几种基本操作有了更加熟练的掌握，对于二叉树的几种遍历过程也有了更为深刻的理解。在实验过程中，由于链式存储不具备随机存取的特点，导致在变成过程中遇到了一些困难，而对于二叉树，主要是通过遍历来对结点进行各种操作。总的来说，实验过程锻炼了自己的动手能力，也让我体会到了细致认真的重要性。