数据结构实验报告

2024-06-22 来源：好土汽车网

导读数据结构实验报告

课程实验报告

课程名称：数据结构（C语言版）

专业班级：计算机1002班学号： U201014285 姓名：邹若兰指导教师：周时阳报告日期： 2012/5/4

计算机科学与技术学院

1 课程实验概述 ............................................................................................................... 3 2 实验一基于顺序结构的线性表实现 .............................................................................. 4

2.1 问题描述............................................................................................................ 4

2.2 系统设计............................................................................................................ 4 2.3 系统实现............................................................................................................ 7 2.4 效率分析............................................................................................................ 9 3 实验二基于链式结构的线性表实现 ..................................................................... 10 3.1 问题描述.......................................................................................................... 10 3.2 系统设计.......................................................................................................... 10 3.3 系统实现.......................................................................................................... 13 3.4 效率分析.......................................................................................................... 16 4 实验三基于二叉链表的二叉树实现 ............................................................................ 17

4.1 问题描述.......................................................................................................... 17 4.2 系统设计.......................................................................................................... 17 4.3 系统实现.......................................................................................................... 22 4.4 效率分析.......................................................................................................... 26 5 实验总结与评价.......................................................................................................... 26

1 课程实验概述

本课程实验为数据结构试验，包括三个实验内容，实验目的在于：

1．加深对数据结构和算法的理解，进一步提高学生编程能力；

2．培养和提高学生分析问题与解决问题的综合能力；

3．整理资料，撰写规范的实验报告。

2 实验一基于顺序结构的线性表实现

2.1 问题描述

基于顺序存储结构，实现线性表的基本的、常见的运算。实验要求：

⑴ 提供一个实现功能的演示系统

⑵ 具体物理结构和数据元素类型自行选定 ⑶ 线性表数据可以使用磁盘文件永久保存

2.2 系统设计

本系统提供两个基于顺序存储结构的线性表，模拟应用背景为：学生信息表和教师信息表，数据元素的数据项为：姓名、学号（或教师编号）、性别、年龄。

该演示系统提供的操作有：表的初始化、销毁、置空、判空，求表长、获取数据元素、查找数据元素、获得前驱、获得后继、插入数据元素、删除数据元素、表的遍历；此外还有表的创建、加载、保存操作选项，并提供已保存的数据表文件，便于演示操作。

应用程序构架：主要包含主程序、菜单函数、菜单选项处理函数。

在主程序中实现分支循环控制，主要部分是：调用菜单函数显示菜单；询问并接受用户的菜单选项进行消息的接受处理；对选择消息判断后通过分支转至相应处理部分，在处理部分实现功能调用前的准备工作（如继续对用户处理要求进行询问）、功能函数的调用、调用后的后续控制处理工作（询问用户要求）；调用结束返回菜单选项，进行下一轮的处理。在菜单选项中提供退出系统的退出函数。

演示系统具体实现流程图如下：

开始

输出与系统相关的说明文字

N 是否加载已保存的

信息表文件？ Y

加载学生及教师信息表

1 1

调用清屏函数清屏调用菜单函数显示菜单选项询问并接受用户选择op(0-15) op=1—15 根据选择转至相应功能调用处理部分，实现有关线性表的操作 op=0 调用退出函数退出系统

结束

说明：

其中“根据选择转至相应功能调用处理部分，实现线性表的基本操作”本应是包含十

五个分支的分支结构分别指向不同的基本操作处理部分，限于篇幅不一一赘举。现文字描述如下：

十五个分支对应1—15个选项，分别为：表的加载、保存、表的初始化、表的创建、销毁、置空、判空、求表长、获取数据元素、查找数据元素、获得前驱、获得后继、插入数据元素、删除数据元素、表的遍历。对于每一个“功能调用”处理部分大致结构为：预处理、调用处理函数、后继处理。其中预处理包括询问是对学生还是教师信息表进行操作、或是为调用处理函数还需用户输入的相关信息，如插入操作调用插入函数前需询问插入位置并要求输入插入信息，等；后继处理包括输出功能函数调用后的相关结果或询问用户是否遍历输出表的信息以便检查是否操作正确成功（方便老师检查）。

线性表的顺序存储表示：

typedef struct {

ElemType *elem; 指针，指向顺序存放的一串数据元素 int length; 表长（实际数据元素个数）

int size; 表的大小（最多存贮数据元素个数） }SqList;

相关函数的算法思想描述：

注：为操作方便采用带头结点的链表表示。

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 系统实现

数据元素结点，存储数据信息姓名、学号（或教师编号）、性别、年龄： typedef struct ElemSet{ char name[10]; char num[9]; char sex[3]; int age; }ElemType;

线性表的链式表示： typedef struct LNode{ ElemType data;

struct LNode *next; }LNode,* LinkList; 有关函数申明：

void Load(LinkList * L1,LinkList * L2); 加载学生机教师信息数据文件 void SaveStu(LinkList L); 保存学生信息表至文件 void SaveTch(LinkList L); 保存教师信息表至文件 status InitList(LinkList * L);

status CreateList(LinkList * L); 根据用户输入信息创建链表 status DestroyList(LinkList * L);

status ClearList(LinkList L); status ListEmpty(LinkList L); status ListLength(LinkList L);

status GetElem(LinkList L,int i,ElemType * e);

status LocateElem(LinkList L,ElemType e,status (* compare)(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 ListTraverse(LinkList L,void (* visit)(ElemType e));

status Equal(ElemType x, ElemType y); 判断两元素是否相等，用作compare函数 void DisplayStu(ElemType e); 输出学生信息数据元素，用作visit函数 void DisplayTch(ElemType e);

void Menu(void); 显示菜单 void ClrScr(void); 清屏

部分函数C语言实现：插入：

status ListInsert(LinkList L,int i,ElemType e) {

LNode *p=L; LNode *s; int j=0;

while(p&&jp=p->next; ++j;

}

if(!p||j>i-1) return ERROR; s=(LinkList)malloc(sizeof(LNode)); strcpy(s->data.name,e.name); strcpy(s->data.num,e.num); strcpy(s->data.sex,e.sex); s->data.age=e.age; s->next=p->next; p->next=s; return OK; }

删除：

status ListDelete(LinkList L,int i,ElemType *e) {

LNode *p=L;

LNode *q; int j=0;

while(p->next&&j输出教师信息数据元素，用作visit函数 {

p=p->next; ++j; }

if(!p->next||j>i-1) return ERROR; q=p->next; p->next=q->next;

strcpy(e->name,q->data.name); strcpy(e->num,q->data.num); strcpy(e->sex,q->data.sex); e->age=q->data.age; free(q); return OK; }

加载：

void Load(LinkList * L1,LinkList * L2) {

FILE *in1,*in2; LNode *p,*cur_p;

if((in1=fopen(\"studentlink.dat\ {

printf(\"\\n学生信息数据文件打开失败！\\n\"); exit(-1); }

if((in2=fopen(\"teacherlink.dat\ {

printf(\"\\n教师信息数据文件打开失败！\\n\"); exit(-1); }

InitList(L1); InitList(L2); cur_p=*L1;

while(!feof(in1)){

p=(LNode *)malloc(sizeof(LNode)); fread(p,sizeof(LNode),1,in1); if(!(feof(in1))){ p->next=NULL; cur_p->next=p; cur_p=p; }

}

cur_p=*L2;

while(!feof(in2)){

p=(LNode *)malloc(sizeof(LNode)); fread(p,sizeof(LNode),1,in2); if(!feof(in2)){

p->next=NULL; cur_p->next=p; cur_p=p; } }

fclose(in1); fclose(in2); }

清屏：

void ClrScr(void)

{

HANDLE gh_std_out;

gh_std_out=GetStdHandle(STD_OUTPUT_HANDLE); CONSOLE_SCREEN_BUFFER_INFO bInfo; COORD home={0,0},new_pos={0,0}; DWORD rnum1,rnum2;

unsigned long size;

printf(\"\\n 请按任意键进行清屏操作！\\n\"); getchar();

GetConsoleScreenBufferInfo(gh_std_out,&bInfo); size=bInfo.dwSize.X*bInfo.dwSize.Y;

FillConsoleOutputAttribute(gh_std_out,bInfo.wAttributes,size,home,&rnum1); FillConsoleOutputCharacter(gh_std_out,' ',size,home,&rnum2); SetConsoleCursorPosition(gh_std_out,new_pos); return; }

3.4 效率分析

主要分析插入和删除的时间复杂度：插入：

假设线性表长度为n，在第i个之前插入的概率为pi ，则插入运算指针移动次数的数学期望为：

n1Eis =

(ii11)pi

在等概率下，pi=

1n1 Eis==

平均时间复杂度：O(n)

最好情况时间复杂度：O(1) 最坏情况时间复杂度：O(n)

删除：

假设线性表长度为n，删除第i个结点的概率为pi ，则删除运算指针移动次数的数学期望为：

nEis =

(ii11)pi

在等概率下，pi=

1n Eis==

n12

平均时间复杂度：O(n)

最好情况时间复杂度：O(1) 最坏情况时间复杂度：O(n)

表面上看，顺序存储和链式存储的插入删除操作时间复杂度均为O(n)，然而由于顺序存储时涉及的是数据元素的移动操作，而链式存储只涉及指针的移动与修改，在实际中数据元素比较复杂其移动修改的操作量大，用顺序结构处理插入删除操作多的线性表其效率不如链式。

4 实验三基于二叉链表的二叉树实现

4.1 问题描述

基于二叉链表，实现二叉树的下列运算：

① 二叉树生成；

② 前序、中序和后序遍历； ③ 计算叶子数目； ④ 按层次遍历； ⑤ 求二叉树高度；实验要求：

⑴ 提供一个实现功能的演示系统

⑵ 具体物理结构和数据元素类型自行选定

⑶ ②、③和⑤运算分别采用递归和非递归算法实现

4.2 系统设计

本系统提供一个基于链式存储结构的二叉树，模拟应用背景为：族谱，数据

元素的数据项为：姓名、性别、年龄。

该演示系统提供的操作有：二叉树的生成，基于递归实现的二叉树的前序、中序、后序遍历，基于非递归（使用栈）实现的前序、中序、后序遍历，树的层次遍历（使用队），基于递归实现的二叉树的叶子数目计算、二叉树的深度计算，非递归实现的二叉树的叶子数目计算、二叉树的深度计算；此外还有二叉树的加载、保存操作选项，并提供已保存的数据表文件，便于演示操作。为实现队和栈的使用，实际工程中还创建了栈和队，实现了了栈和队的部分函数操作，作为子函数被调用。

应用程序构架：主要包含主程序、菜单函数、菜单选项处理函数。

演示系统具体实现流程图如下：开始输出与系统相关的说明文字 N 是否加载已保存的信息表文件？ Y 加载族谱二叉树文件调用清屏函数清屏调用菜单函数显示菜单选项询问并接受用户选择op(0-14) op=1—14 op=0 根据选择转至相应功能调用处调用退出函数理部分，实现有关线性表的操作退出系统

结束说明：

其中“根据选择转至相应功能调用处理部分，实现线性表的基本操作”本应是包含十

四个分支的分支结构分别指向不同的基本操作处理部分，限于篇幅不一一赘举。现文字描述如下：

十四个分支对应1—14个选项，分别为：二叉树的保存、加载、二叉树的创建、基于递归实现的二叉树的前序遍历、非递归实现的前序遍历、递归实现的中序遍历、非递归实现的中序遍历、递归实现的后续遍历、非递归实现的后续遍历、层次遍历、递归实现的叶子数目统计、非递归实现的叶子数目统计、递归实现的树深计算、非递归实现的树深计算。对于每一个“功能调用”处理部分大致结构为：预处理、调用处理函数、后继处理。其中预处理主要为异常的判断与提示；后继处理主要为输出功能函数调用后的相关结果。

二叉树的链式结构实现：

typedef struct BiTNode{

TElemType data; 数据域

struct BiTNode *lchild,*rchild; 指针域 }BiTNode,* BiTree;

相关函数的算法思想描述：递归实现的操作定义：前序遍历：

若二叉树为空，则空操作，否则：（1）访问根结点

（2）前序遍历左子树（3）前序遍历右子树中序遍历：

若二叉树为空，则空操作，否则：（1）中序遍历左子树（2）访问根结点

（3）中序遍历右子树后序遍历：

若二叉树为空，则空操作，否则：（1）后序遍历左子树（2）后序遍历右子树（3）访问根结点求树深：

若二叉树未空，返回树深0，否则：

（1）返回1+MAX[对左子树求树深的返回值，对右子树求树深的返回值] （2）对左子树求树深（3）对右子树求树深求叶子数目：

（1）若二叉树为空返回0，否则转(2)

（2）若二叉树左右子树为空，返回1，否则转（3）

（3）返回对“左子树求叶子数目”的的返回值+“对左子树求叶子数目”的返回

值

（4）对左子树求叶子数目（5）对右子树求叶子数目

部分非递归函数的算法（类C语言描述）：

中序遍历

使用的栈： typedef struct{

SElemType *base; SElemType 为TElemType * SElemType *top; int stacksize;

}SqStack;

Status InOrderTraverse(BiTree T,Status (*Visit)(TElemType e)) //采用二叉链表存储结构，Visit是对数据元素操作的应用函数

//中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit {

BiTree p=T; InitStack(S);

while(p||!StackEmpty(S)){

if(p){ Push(S,p); p=p->lchild; } //根指针进栈，遍历左子树

else{ //根指针退栈，访问根结点，遍历右子树 Pop(S,p);

if(!Visit(p->data)) return ERROR; p=p->rchild; } } return OK; }

后序遍历：

使用的栈：

typedef enum {L,R} tagtype; // L，R可标志是否已遍历左子树或右子树 typedef struct{

BiTree ptr; tagtype tag;

}SElemType2; //栈的基本数据元素 typedef struct{ SElemType2 *base; SElemType2 *top;

int stacksize;

}SqStack2; // 栈的结构表示

Status PostOrderTraverse(BiTree T,Status (*Visit)(TElemType e))

{

InitStack2(S); do{

while(p)

{ //标志左子树已遍历，将根结点和访问标志入栈，遍历左子树 x.ptr=p; x.tag=L; Push2(S,x); p=p->lchild; }

while((GetTop2(S,x))&&(x.tag==R))

{ //当根结点右子树已遍历时，根结点出栈，访问根结点 Pop2(S,x); p=x.ptr;

if(!Visit(p->data)) return ERROR; }

if(!StackEmpty2(S))

{ //将根结点标志为右子树已遍历，遍历右子树 px=S.top-1;px->tag=R; p=px->ptr->rchild; }

}while(!StackEmpty2(S)); return OK; }

层次遍历：

使用的链式队： typedef struct QNode{ QElemType data; struct QNode *next; }QNode,*QueuePtr; typedef struct{ QueuePtr front; QueuePtr rear; }LinkQueue;

Status LeverOrderTraverse(BiTree T,Status (*Visit)(TElemType e)) {

InitQueue(Q);

if(T){

if(!Visit(T->data)) return ERROR; //访问根结点 EnQueue(Q,T); //根结点指针入队 while(!QueueEmpty(Q)){

DeQueue(Q,p); //根结点出栈

if(p->lchild){

if(!Visit(p->lchild->data)) return ERROR; EnQueue(Q,p->lchild);

} //若左孩子非空，访问左孩子并将左孩子指针入栈 if(p->rchild){

if(!Visit(p->rchild->data)) return ERROR;

EnQueue(Q,p->rchild);

} //若右孩子非空，访问右孩子并将右孩子指针入栈 } } return OK; }

前序遍历非递归算法与中序遍历类似，而求叶子数目、求树深非递归算法也可类比（前序、中序或后序非递归遍历算法）使用栈实现，这里不详述。

4.3 系统实现

由于二叉树是可以基于递归描述的一种数据结构，其相关操作也易于用递归实现，典型的即指二叉树的前序中序后序遍历，而二叉树的相关基本操作又可基于遍历来实现，如此演示系统实现求叶子数目、求树深，可用递归函数实现也可根据遍历的实质写出基于栈实现的函数。前序、中序、后序遍历的本质是相同，只是调用VISIT函数（访问根结点）的时机不同，其层次遍历可类比图的广度遍历（可将树视为特殊的图）。虽然递归函数可使源码更简洁，但反复递归调用会浪费大量时间，一个功能是否用递归实现应视其具体应用环境设计。

数据元素结构，存放单个的人员信息： typedef struct ElemSet{ char name[10]; char sex[3];

int age; }TElemType;

二叉树的链式结构实现，结构中有两个指向其孩子的指针（左孩子、右孩子）：

typedef struct BiTNode{

TElemType data; 数据域

struct BiTNode *lchild,*rchild; 指针域

}BiTNode,* BiTree,* SElemType,* QElemType; 该结构的指针类型可作为队和栈中存放

的基本元素的类型栈一的实现结构 typedef struct{

SElemType *base; SElemType *top; int stacksize;

}SqStack;

栈二的实现（该站用于后序遍历的非递归实现）：

typedef enum {L,R} tagtype; L，R可标志是否已遍历左子树或右子树 typedef struct{ BiTree ptr;

tagtype tag;

}SElemType2; 栈二的基本数据元素 typedef struct{ SElemType2 *base; SElemType2 *top;

int stacksize;

}SqStack2; 栈二的结构表示

链式队的实现，用于层次遍历： typedef struct QNode{ QElemType data; struct QNode *next; }QNode,*QueuePtr; typedef struct{ QueuePtr front; QueuePtr rear;

}LinkQueue;

Status CreateBiTree(BiTree *T); 二叉树的创建

Status RecurPreOrderTraverse(BiTree T,Status (*Visit)(TElemType e)); 递归实现的前序遍历 Status PreOrderTraverse(BiTree T,Status (*Visit)(TElemType e)); 非递归实现的前序遍历 Status RecurInOrderTraverse(BiTree T,Status (*Visit)(TElemType e)); 递归实现的中序遍历 Status InOrderTraverse(BiTree T,Status (*Visit)(TElemType e)); 非递归实现的中序遍历 Status RecurPostOrderTraverse(BiTree T,Status (*Visit)(TElemType e)); 递归实现的后序遍历 Status PostOrderTraverse(BiTree T,Status (*Visit)(TElemType e)); 非递归实现的后序遍历 Status LeverOrderTraverse(BiTree T,Status (*Visit)(TElemType e)); 层次遍历 Status RecurBiTreeDepth(BiTree T) 递归实现求树深; Status BiTreeDepth(BiTree T); 非递归实现求树深 Status RecurLeafNum(BiTree T); 递归实现求叶子数目 Status LeafNum(BiTree T); 非递归实现求叶子数目

void LoadBiTree(BiTree *T);

void Load(BiTree *T,FILE *in); 在LoadBiTree中使用，用于递归实现文件加载 void SaveBiTree(BiTree T);

void Save(BiTree T,FILE *out); 在SaveBiTree中使用，用于递归实现树的保存（至文件）

Status DisPlay(TElemType e); 输出显示个人信息（姓名、性别、年龄） void ClrScr(void); 清屏

void Menu(void); 显示操作菜单

与栈二相关的操作函数（初始化栈、入栈、出栈、判空、获取栈顶元素）： Status InitStack2(SqStack2 *S);

Status Push2(SqStack2 *S,SElemType2 e); Status Pop2(SqStack2 *S,SElemType2 *e); Status StackEmpty2(SqStack2 S);

Status GetTop2(SqStack2 S,SElemType2 *e);

与栈一相关的函数操作（栈的初始化、入栈、出栈、判空、获取栈顶元素）： Status InitStack(SqStack *S); Status Push(SqStack *S,SElemType e); Status Pop(SqStack *S,SElemType *e); Status StackEmpty(SqStack S);

Status GetTop(SqStack S,SElemType *e);

与队相关的函数操作（队的初始化、入队、出队、判空）： Status InitQueue(LinkQueue *Q);

Status EnQueue(LinkQueue *Q,QElemType e); Status DeQueue(LinkQueue *Q,QElemType *e); Status QueueEmpty(LinkQueue Q);

部分函数实现的C语言代码：

前序遍历的递归实现：

Status RecurPreOrderTraverse(BiTree T,Status (*Visit)(TElemType e)) {

if(T){

if(Visit(T->data))

if(RecurPreOrderTraverse(T->lchild,DisPlay))

if(RecurPreOrderTraverse(T->rchild,DisPlay)) return OK; return ERROR; }

else return OK; }

前序遍历的非递归实现：

Status PreOrderTraverse(BiTree T,Status (*Visit)(TElemType e)) {

SqStack S; BiTree p=T; InitStack(&S);

while(p||!StackEmpty(S)){

if(p){

if(!Visit(p->data)) return ERROR; Push(&S,p);

p=p->lchild; } else{

Pop(&S,&p); p=p->rchild; } } return OK; }

后序遍历的非递归实现：

Status PostOrderTraverse(BiTree T,Status (*Visit)(TElemType e)) {

SqStack2 S; BiTNode *p=T; SElemType2 x,*px; InitStack2(&S); do{

while(p) {

x.ptr=p; x.tag=L;

Push2(&S,x); p=p->lchild; }

while((GetTop2(S,&x))&&(x.tag==R)) {

Pop2(&S,&x); p=x.ptr;

if(!Visit(p->data)) return ERROR; }

if(!StackEmpty2(S)) {

px=S.top-1;px->tag=R; p=px->ptr->rchild; }

}while(!StackEmpty2(S)); return OK; }

层次遍历：

Status LeverOrderTraverse(BiTree T,Status (*Visit)(TElemType e)) {

LinkQueue Q;

QElemType p;

InitQueue(&Q); if(T){

if(!Visit(T->data)) return ERROR; EnQueue(&Q,T); while(!QueueEmpty(Q)){ DeQueue(&Q,&p);

if(p->lchild){

if(!Visit(p->lchild->data)) return ERROR; EnQueue(&Q,p->lchild); }

if(p->rchild){

if(!Visit(p->rchild->data)) return ERROR; EnQueue(&Q,p->rchild); } } }

return OK; }

遍历是二叉树各种操作的基础，可以在遍历过程中对结点进行各种操作，如：对于一棵已知树可求结点的双亲，求结点的孩子结点，判定结点所在层次等，反之，也可在遍历过程中生成结点，建立二叉树的存储结构。

4.4 效率分析

遍历二叉树的算法中的基本操作是访问结点，则不论按哪种次序进行遍历，对含n个结点的二叉树，其时间复杂度均为O(n)。所需辅助空间为遍历过程中栈的最大容量即树深，最坏情况为n则空间复杂度也为O(n)。

求树深和叶子数目是基于遍历实现的时间和空间复杂度也均为O(n)。

5 实验总结与评价

线性表的顺序存储结构是一种随机存取的存储结构，基于此存储结构的线性表易实现取数据元素，由于有表示表长（length）和表的大小（size）的变量，也易于实现判空、求表长、置空、销毁操作。插入和删除操作本身易于实现，但涉及元素的移动，其移动次数取决于元素位置，平均情况为O(n)。

表面上看，顺序存储和链式存储的插入删除操作时间复杂度均为O(n)，然而由于顺序存储时涉及的是数据元素的移动操作，而链式存储只涉及指针的移动与修改，在实际中数据元素比较复杂其移动修改的操作量大，用顺序结构处理插入删除操作多的线性表其效率不如链式。然而链式存储不具备随机存取的特点，

其取元素操作相比较麻烦，与存取有关操作比顺序存储结构麻烦。求表长、置空、销毁操作也比顺序存储麻烦，涉及表的遍历过程，时间复杂度为O(n)。

本系统除实现基本功能操作外，还实现了与演示相关的程序控制操作，如根据用户操作输出提示警告信息，每次实现功能调用后清屏，对一些异常也有相应处理。如在第一个演示系统中：对于每一个“功能调用”处理部分大致结构为：预处理、调用处理函数、后继处理。其中预处理包括询问是对学生还是教师信息表进行操作、或是为调用处理函数还需用户输入的相关信息，如插入操作调用插入函数前需询问插入位置并要求输入插入信息，等；后继处理包括输出功能函数调用后的相关结果或询问用户是否遍历输出表的信息以便检查是否操作正确成功（方便老师检查）。

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文

全部栏目

数据结构实验报告