c数据结构实验报告

第一篇：c数据结构实验报告

c数据结构实验报告

数据结构(C语言版)实验报告;专业：计算机科学与技术、软件工程;学号:____XX40703061_____;班级:_________软件二班________;姓名:________朱海霞__________;指导教师:___刘遵仁_____________;青岛大学信息工程学院;XX年10月;实验1;实验题目：顺序存储结构线性表的插入和删除;实验目

数据结构(C语言版)实验报告

专业：计算机科学与技术、软件工程

学号:____XX40703061___________________

班级:_________软件二班______________

姓名:________朱海霞______________

指导教师:___刘遵仁________________

青岛大学信息工程学院

XX年10月

实验1

实验题目：顺序存储结构线性表的插入和删除

实验目的：

了解和掌握线性表的逻辑结构和顺序存储结构，掌握线性表的基本算法及相关的时间性能分析。

实验要求：

建立一个数据域定义为整数类型的线性表，在表中允许有重复的数据;根据输入的数据，先找到相应的存储单元，后删除之。

实验主要步骤：

1、分析、理解给出的示例程序。

2、调试程序，并设计输入一组数据(3，-5，6，8，2，-5，4，7，-9)，测试程序的如下功能：根据输入的数据，找到相应的存储单元并删除，显示表中所有的数据。

程序代码:

#include

#include

#define OK 1

#define ERROR 0

#define OVERFLOW-2

#define LIST_INIT_SIZE 100

#define LISTINCREMENT 10

typedef struct{

int* elem;

int length;

int listsize;

}Sqlist;

int InitList_Sq(Sqlist &L){

=(int*)malloc(LIST_INIT_SIZE*sizeof(int));

if(!)return-1;

=0;

=LIST_INIT_SIZE;

return OK;

}

int ListInsert_Sq(Sqlist&L,int i,int e){

if(i+1)return ERROR;

if(==){

int *newbase;

newbase=(int*)realloc(,(+LISTINCREMENT)*sizeof(int));

if(!newbase)return-1;

=newbase;

+=LISTINCREMENT;

}

int *p,*q;

q=&();

for(p=&();p>=q;--p)

*(p+1)=*p;

*q=e;

++;

return OK;

}

int ListDelete_Sq(Sqlist &L,int i,int e){

int *p,*q;

if(i)return ERROR;

p=&();

e=*p;

q=+;

for(++p;p *(p-1)=*p;

--;

return OK;

}

int main(){

Sqlist L;

InitList_Sq(L);//初始化

int i,a={3,-5,6,8,2,-5,4,7,-9};

for(i=1;i ListInsert_Sq(L,i,a);

for(i=0;i printf(“ %d”,);

printf(“ ”);//插入9个数

ListInsert_Sq(L,3,24);

for(i=0;i printf(“ %d”,);

printf(“ ”);//插入一个数

int e;

ListDelete_Sq(L,2, e);

for(i=0;i printf(“ %d”,);//删除一个数

printf(“ ”);

return 0;

}

实验结果：

3，-5,6,8,2，-5,4,7，-9

3，-5,24,6,8,2，-5,4,7，-9

3,24,6,8,2，-5,4,7，-9

心得体会：

顺序存储结构是一种随机存取结构，存取任何元素的时间是一个常数，速度快;结构简单，逻辑上相邻的元素在物理上也相邻;不使用指针，节省存储空间;但是插入和删除元素需要移动大量元素，消耗大量时间;需要一个连续的存储空间;插入元素可能发生溢出;自由区中的存储空间不能被其他数据共享 实验2

实验题目：单链表的插入和删除

实验目的：

了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。

实验要求：

建立一个数据域定义为字符类型的单链表，在链表中不允许有重复的字符;根据输入的字符，先找到相应的结点，后删除之。

实验主要步骤：

3、分析、理解给出的示例程序。

4、调试程序，并设计输入数据(如：A，C，E，F，H，J，Q，M)，测试程序的如下功能：不允许重复字符的插入;根据输入的字符，找到相应的结点并删除。

5、修改程序：

(1)增加插入结点的功能。

(2)建立链表的方法有“前插”、“后插”法。

程序代码:

#include

#include

#define NULL 0

#define OK 1

#define ERROR 0

typedef struct LNode{

int data;

struct LNode *next;

}LNode,*LinkList;

int InitList_L(LinkList &L){

L=(LinkList)malloc(sizeof(LNode));L->next=NULL;

return OK;

} int ListInsert_L(LinkList &L,int i,int e){ LinkList p,s;

int j;

p=L;j=0;

while(p&&j

p=p->next;++j;

}

if(!p||j>i-1)

return ERROR;

s=(LinkList)malloc(sizeof(LNode));s->data=e;

s->next=p->next;

p->next=s;

return OK;

} int

ListDelete_L(LinkList&L,int

i,int &e){ LinkList p,q;

int j;

p=L;j=0;

while(p->next&&j

p=p->next;++j;

}

if(!(p->next)||j

return ERROR;

q=p->next;p->next=q->next;e=q->data;free(q);

return OK;

}

int main(){

LinkList L,p;

char a={'A','C','E','F','H','J','Q','U'};int i,j;

InitList_L(L);

for(i=1,j=0;i p=L->next;

while(p!=NULL){

printf(“%c ”,p->data);p=p->next;}//插入八个字符

printf(“;实验结果：;ACEFHJQU;ABCEFHJQU;ABEFHJQU;心得体会：;单链表是通过扫描指针P进行单链表的操作;头指针唯;实验3;实验题目：栈操作设计和实现;实验目的：;

1、掌握栈的顺序存储结构和链式存储结构，以便在实;

2、掌握栈的特点，即后进先出和先进先出的原则;

3、掌握栈的基本运算，如：入栈与出栈

}

}//插入八个字符 printf(” “);i=2;int e;ListInsert_L(L,i,'B');

p=L->next;while(p!=NULL){ printf(”%c “,p->data);p=p->next;}//插入一个字符 printf(” “);i=3;ListDelete_L(L,i,e);p=L->next;while(p!=NULL){ printf(”%c “,p->data);p=p->next;} printf(” “);return 0;

实验结果：

A C E F H J Q U

A B C E F H J Q U

A B E F H J Q U

心得体会：

单链表是通过扫描指针P进行单链表的操作;头指针唯一标识点链表的存在;插入和删除元素快捷，方便。

实验3

实验题目：栈操作设计和实现

实验目的：

1、掌握栈的顺序存储结构和链式存储结构，以便在实际中灵活应用。

2、掌握栈的特点，即后进先出和先进先出的原则。

3、掌握栈的基本运算，如：入栈与出栈等运算在顺序存储结构和链式存储结构上的实现。

实验要求：

回文判断：对于一个从键盘输入的字符串，判断其是否为回文。回文即正反序相同。如

“abba”是回文，而“abab”不是回文。

实验主要步骤

(1)数据从键盘读入;

(2)输出要判断的字符串;

(3)利用栈的基本操作对给定的字符串判断其是否是回文，若是则输出“Yes”，否则输出“No”。

程序代码:

#include

#include

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define OVERFLOW-2

#define N 100

#define STACK_INIT_SIZE 100

#define STACKINCREMENT 10

typedef struct{

int *base;// 在栈构造之前和销毁之后，base的值为NULL int *top;// 栈顶指针

int stacksize;// 当前已分配的存储空间，以元素为单位

} SqStack;

int InitStack(SqStack &S)

{ // 构造一个空栈S

if(!(=(int *)malloc(STACK_INIT_SIZE*sizeof(int))))

exit(OVERFLOW);// 存储分配失败

=;

=STACK_INIT_SIZE;

return OK;

}

int StackEmpty(SqStack S)

{ // 若栈S为空栈，则返回TRUE，否则返回FALSE

if(==)

return TRUE;

else

return FALSE;

}

int Push(SqStack &S, int e)

{ // 插入元素e为新的栈顶元素

if(>=)// 栈满，追加存储空间

{

=(int *)realloc(,(+STACKINCREMENT)*sizeof(int));if(!)

exit(OVERFLOW);// 存储分配失败

=+;

+=STACKINCREMENT;

}

*()++=e;

return OK;

}

int Pop(SqStack &S,int &e)

{ // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK;否则返回ERROR if(==)

return ERROR;

e=*--;

return OK;

}

int main(){

SqStack s;

int i,e,j,k=1;

char ch = {0},*p,b = {0};

if(InitStack(s))// 初始化栈成功

{

printf(”请输入表达式: “);

gets(ch);

p=ch;

while(*p)// 没到串尾

Push(s,*p++);

for(i=0;i

if(!StackEmpty(s)){// 栈不空

Pop(s,e);// 弹出栈顶元素

b=e;

}

}

for(i=0;i

if(ch!=b)

k=0;

}

if(k==0)

printf(”NO!“);

else

printf(”输出:“)

printf(”YES!“);

}

return 0;

}

实验结果：

请输入表达式：

abcba

输出：YES!

心得体会：栈是仅能在表尾惊醒插入和删除操作的线性表，具有先进后出的性质，这个固有性质使栈成为程序设计中的有用工具。

实验4

实验题目：二叉树操作设计和实现

实验目的：

掌握二叉树的定义、性质及存储方式，各种遍历算法。

实验要求：

采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。

实验主要步骤：

1、分析、理解程序。

2、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点(空指针)，如ABD###CE##F##，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求所有叶子及结点总数。

程序代码:

实验结果：

心得体会：

实验5

实验题目：图的遍历操作

实验目的：

掌握有向图和无向图的概念;掌握邻接矩阵和邻接链表建立图的存储结构;掌握DFS及BFS对图的遍历操作;了解图结构在人工智能、工程等领域的广泛应用。

实验要求：

采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的DFS和BFS操作。

实验主要步骤：

设计一个有向图和一个无向图，任选一种存储结构，完成有向图和无向图的DFS(深度优先遍历)和BFS(广度优先遍历)的操作。

1.邻接矩阵作为存储结构

#include”“

#include”“

#define MaxVertexNum 100 //定义最大顶点数

typedef struct{

char vexs;//顶点表

int edges;//邻接矩阵，可看作边表 int n,e;//图中的顶点数n和边数e

}MGraph;//用邻接矩阵表示的图的类型

//=========建立邻接矩阵=======

void CreatMGraph(MGraph *G)

{

int i,j,k;

char a;

printf(”Input VertexNum(n)and EdgesNum(e): “);

scanf(”%d,%d“,&G->n,&G->e);//输入顶点数和边数

scanf(”%c“,&a);

printf(”Input Vertex string:“);

for(i=0;in;i++)

{

scanf(”%c“,&a);

G->vexs=a;//读入顶点信息，建立顶点表

}

for(i=0;in;i++)

for(j=0;jn;j++)

G->edges=0;//初始化邻接矩阵

printf(”Input edges,Creat Adjacency Matrix “);

for(k=0;ke;k++){ //读入e条边，建立邻接矩阵

scanf(”%d%d“,&i,&j);//输入边(Vi，Vj)的顶点序号

G->edges=1;;G->edges=1;//若为;//=========定义标志向

量，为

全

局

变

量=;typedefenum{FALSE,TRUE}B;Booleanvisited=1;

G->edges=1;//若为无向图，矩阵为对称矩阵;若建立有向图，去掉该条语句 }

}

//=========定义标志向量，为全局变量=======

typedef enum{FALSE,TRUE} Boolean;

Boolean visited;

//========DFS：深度优先遍历的递归算法======

void DFSM(MGraph *G,int i)

{ //以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0，1矩阵

给出你的编码

//===========BFS：广度优先遍历=======

void BFS(MGraph *G,int k)

{ //以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索

给出你的编码

//==========主程序main =====

void main()

{

int i;

MGraph *G;

G=(MGraph *)malloc(sizeof(MGraph));//为图G请内存空间

CreatMGraph(G);//建立邻接矩阵

printf(”Print Graph DFS: “);

DFS(G);//深度优先遍历

printf(” “);

printf(”Print Graph BFS: “);

BFS(G,3);//以序号为3的顶点开始广度优先遍历

printf(” “);

}

2.邻接链表作为存储结构

#include”“

#include”“

#define MaxVertexNum 50 //定义最大顶点数

typedef struct node{ //边表结点

int adjvex;//邻接点域

struct node *next;//链域

申

}EdgeNode;

typedef struct vnode{ //顶点表结点

char vertex;//顶点域

EdgeNode *firstedge;//边表头指针

}VertexNode;

typedef VertexNode AdjList;//AdjList是邻接表类型 typedef struct {

AdjList adjlist;//邻接表

int n,e;//图中当前顶点数和边数

} ALGraph;//图类型

//=========建立图的邻接表=======

void CreatALGraph(ALGraph *G)

{

int i,j,k;

char a;

EdgeNode *s;//定义边表结点

printf(”Input VertexNum(n)and EdgesNum(e): “);

scanf(”%d,%d“,&G->n,&G->e);//读入顶点数和边数

scanf(”%c“,&a);

printf(”Input Vertex string:“);

for(i=0;in;i++)//建立边表

{

scanf(”%c“,&a);

G->adjlist.vertex=a;//读入顶点信息

G->adjlist.firstedge=NULL;//边表置为空表

}

printf(”Input edges,Creat Adjacency List “);

for(k=0;ke;k++){ //建立边表

scanf(”%d%d“,&i,&j);//读入边(Vi，Vj)的顶点对序号

s=(EdgeNode *)malloc(sizeof(EdgeNode));//生成边表结点

s->adjvex=j;//邻接点序号为j

s->next=G->adjlist.firstedge;

G->adjlist.firstedge=s;//将新结点*S插入顶点Vi的边表头部

s=(EdgeNode *)malloc(sizeof(EdgeNode));

s->adjvex=i;//邻接点序号为i

s->next=G->adjlist.firstedge;

G->adjlist.firstedge=s;//将新结点*S插入顶点Vj的边表头部

}

}

//=========定义标志向量，为全局变量=======

typedef enum{FALSE,TRUE} Boolean;

Boolean visited;

//========DFS：深度优先遍历的递归算法======

void DFSM(ALGraph *G,int i)

{ //以Vi为出发点对邻接链表表示的图G进行DFS搜索

给出你的编码

//==========BFS：广度优先遍历=========

void BFS(ALGraph *G,int k)

{ //以Vk为源点对用邻接链表表示的图G进行广度优先搜索

给出你的编码

//==========主函数===========

void main()

{

int i;

ALGraph *G;

G=(ALGraph *)malloc(sizeof(ALGraph));

CreatALGraph(G);

printf(”Print Graph DFS: “);

DFS(G);

printf(” “);

printf(”Print Graph BFS: “);

BFS(G,3);

printf(” ");

}

实验结果：

1.邻接矩阵作为存储结构

2.邻接链表作为存储结构

心得体会：

实验6

实验题目：二分查找算法的实现

实验目的：

掌握二分查找法的工作原理及应用过程，利用其工作原理完成实验题目中的内容。

实验要求：

编写程序构造一个有序表L，从键盘接收一个关键字key，用二分查找法在L中查找key，若找到则提示查找成功并输出key所在的位置，否则提示没有找到信息。

实验主要步骤：

1.建立的初始查找表可以是无序的，如测试的数据为{3，7，11，15，17，21，35，42，50｝或者{11，21，7，3，15，50，42，35，17｝。

2.给出算法的递归和非递归代码;

3.如何利用二分查找算法在一个有序表中插入一个元素x，并保持表的有序性?

程序代码

实验结果：

心得体会：

实验7

实验题目：排序

实验目的：

掌握各种排序方法的基本思想、排序过程、算法实现，能进行时间和空间性能的分析，根据实际问题的特点和要求选择合适的排序方法。

实验要求：

实现直接排序、冒泡、直接选择、快速、堆、归并排序算法。比较各种算法的运行速度。

实验主要步骤：

程序代码

实验结果：

心得体会：

第二篇：数据结构实验报告

注意：实验结束后提交一份实验报告电子文档

电子文档命名为“学号+姓名”，如：E01214058宋思怡

《数据结构》实验报告

（一）学号：姓名：专业年级：

实验名称：线性表

实验日期：2014年4月14日

实验目的：

1、熟悉线性表的定义及其顺序和链式存储结构；

2、熟练掌握线性表在顺序存储结构上实现基本操作的方法；

3、熟练掌握在各种链表结构中实现线性表基本操作的方法；

4、掌握用 C/C++语言调试程序的基本方法。

实验内容：

一、编写程序实现顺序表的各种基本运算，并在此基础上设计一个主程序完成如下功能：

（1）初始化顺序表L；

（2）依次在L尾部插入元素-1,21,13,24,8；

（3）输出顺序表L；

（4）输出顺序表L长度；

（5）判断顺序表L是否为空；

（6）输出顺序表L的第3个元素；

（7）输出元素24的位置；

（8）在L的第4个元素前插入元素0；

（9）输出顺序表L；

（10）删除L的第5个元素；

（11）输出顺序表L。

源代码

调试分析（给出运行结果界面）

二、编写程序实现单链表的各种基本运算，并在此基础上设计一个主程序完成如下功能：

„„„„

„„„„

小结或讨论:

（1）实验中遇到的问题和解决方法

（2）实验中没有解决的问题

（3）体会和提高

第三篇：数据结构实验报告

南京信息工程大学实验（实习）报告

实验（实习）名称数据结构实验（实习）日期 2011-11-2得分指导教师周素萍

系公共管理系专业信息管理与信息系统年级10级班次1姓名常玲学号2010230700

3实验一顺序表的基本操作及C语言实现

【实验目的】

1、顺序表的基本操作及 C 语言实现

【实验要求】

1、用 C 语言建立自己的线性表结构的程序库，实现顺序表的基本操作。

2、对线性表表示的集合，集合数据由用户从键盘输入（数据类型为整型），建立相应的顺序表，且使得数据按从小到大的顺序存放，将两个集合的并的结果存储在一个新的线性表集合中，并输出。

【实验内容】

1、根据教材定义的顺序表机构，用 C 语言实现顺序表结构的创建、插入、删除、查找等操作；

2、利用上述顺序表操作实现如下程序：建立两个顺序表表示的集合（集合中无重

复的元素），并求这样的两个集合的并。

【实验结果】

[实验数据、结果、遇到的问题及解决]

一． Status InsertOrderList(SqList &va,ElemType x)

{

}

二． Status DeleteK(SqList &a,int i,int k)

{//在非递减的顺序表va中插入元素x并使其仍成为顺序表的算法 int i;if(va.length==va.listsize)return(OVERFLOW);for(i=va.length;i>0,x

}

//注意i的编号从0开始 int j;if(i<0||i>a.length-1||k<0||k>a.length-i)return INFEASIBLE;for(j=0;j<=k;j++)a.elem[j+i]=a.elem[j+i+k];a.length=a.length-k;return OK;

三．// 将合并逆置后的结果放在C表中，并删除B表

Status ListMergeOppose_L(LinkList &A,LinkList &B,LinkList &C)

{

LinkList pa,pb,qa,qb;pa=A;pb=B;qa=pa;qb=pb;// 保存pa的前驱指针 // 保存pb的前驱指针 pa=pa->next;pb=pb->next;A->next=NULL;C=A;while(pa&&pb){} while(pa){} qa=pa;pa=pa->next;qa->next=A->next;A->next=qa;if(pa->data

data){} else{} qb=pb;pb=pb->next;qb->next=A->next;//将当前最小结点插入A表表头 A->next=qb;qa=pa;pa=pa->next;qa->next=A->next;//将当前最小结点插入A表表头 A->next=qa;

}

} pb=B;free(pb);return OK;qb=pb;pb=pb->next;qb->next=A->next;A->next=qb;

顺序表就是把线性表的元素存储在数组中，元素之间的关系直接通过相邻元素的位置来表达。

优点：简单，数据元素的提取速度快；

缺点：（1）静态存储，无法预知问题规模的大小，可能空间不足，或浪费存储空间；（2）插入元素和删除元素时间复杂度高——O（n）

求两个集合的并集

该算法是求两个集合s1和s2的并集，并将结果存入s引用参数所表示的集合中带回。首先把s1集合复制到s中，然后把s2中的每个元素依次插入到集合s中，当然重复的元素不应该被插入，最后在s中就得到了s1和s2的并集，也就是在s所对应的实际参数集合中得到并集。

第四篇：数据结构实验报告

数据结构实验报告

一． 题目要求

1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历；

3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二． 解决方案

对于前三个题目要求，我们用一个程序实现代码如下 #include #include #include #include “Stack.h”//栈的头文件，没有用上

typedefintElemType;

//数据类型 typedefint Status;

//返回值类型 //定义二叉树结构 typedefstructBiTNode{ ElemType

data;

structBiTNode *lChild, *rChild;//左右子树域 }BiTNode, *BiTree;intInsertBST(BiTree&T,int key){//插入二叉树函数

if(T==NULL){

T =(BiTree)malloc(sizeof(BiTNode));

T->data=key;

T->lChild=T->rChild=NULL;

return 1;} else if(keydata){ InsertBST(T->lChild,key);} else if(key>T->data){

InsertBST(T->rChild,key);} else

return 0;} BiTreeCreateBST(int a[],int n){//创建二叉树函数 BiTreebst=NULL;inti=0;while(i

//数据域

InsertBST(bst,a[i]);

i++;} returnbst;} int Delete(BiTree&T)

{

BiTreeq,s;

} if(!(T)->rChild){ //右子树为空重接它的左子树

q=T;T=(T)->lChild;free(q);}else{

if(!(T)->lChild){ //若左子树空则重新接它的右子树

q=T;T=(T)->rChild;}else{ q=T;s=(T)->lChild;while(s->rChild){

q=s;s=s->rChild;}

(T)->data=s->data;//s指向被删除结点的前驱

if(q!=T)

q->rChild=s->lChild;

else

q->lChild=s->lChild;

free(s);} } return 1;

//删除函数，在T中删除key元素 intDeleteBST(BiTree&T,int key){ if(!T)return 0;else{

if(key==(T)->data)return Delete(T);

else{

if(key<(T)->data)

returnDeleteBST(T->lChild,key);

else

returnDeleteBST(T->rChild,key);

} } } intPosttreeDepth(BiTree T){//求深度

inthr,hl,max;if(!T==NULL){ hl=PosttreeDepth(T->lChild);hr=PosttreeDepth(T->rChild);max=hl>hr?hl:hr;return max+1;} else

return 0;

} void printtree(BiTreeT,intnlayer){//打印二叉树 if(T==NULL)return;printtree(T->rChild,nlayer+1);for(inti=0;i

”);} printf(“%dn”,T->data);printtree(T->lChild,nlayer+1);} void PreOrderNoRec(BiTree root)//先序非递归遍历 { BiTree p=root;BiTreestack[50];intnum=0;while(NULL!=p||num>0){

while(NULL!=p)

{

printf(“%d ”,p->data);

stack[num++]=p;

p=p->lChild;

}

num--;

p=stack[num];

p=p->rChild;} printf(“n”);} void InOrderNoRec(BiTree root)//中序非递归遍历 { BiTree p=root;

} intnum=0;BiTreestack[50];while(NULL!=p||num>0){ while(NULL!=p){

stack[num++]=p;

p=p->lChild;} num--;p=stack[num];printf(“%d ”,p->data);p=p->rChild;} printf(“n”);void PostOrderNoRec(BiTree root)//后序非递归遍历 { BiTree p=root;BiTreestack[50];intnum=0;BiTreehave_visited=NULL;

while(NULL!=p||num>0){

while(NULL!=p)

{

stack[num++]=p;

p=p->lChild;

}

p=stack[num-1];

if(NULL==p->rChild||have_visited==p->rChild)

{

printf(“%d ”,p->data);

num--;

have_visited=p;

p=NULL;

}

else

{

p=p->rChild;

} } printf(“n”);}

int main(){//主函数

printf(“

---------------------二叉排序树的实现-------------------”);printf(“n”);int layer;inti;intnum;printf(“输入节点个数:”);scanf(“%d”,&num);printf(“依次输入这些整数（要不相等）”);int *arr=(int*)malloc(num*sizeof(int));for(i=0;i

scanf(“%d”,arr+i);} BiTreebst=CreateBST(arr,num);printf(“n”);printf(“二叉树创建成功!”);printf(“n”);layer=PosttreeDepth(bst);printf(“树状图为:n”);printtree(bst,layer);int j;int T;int K;for(;;){ loop: printf(“n”);printf(“

***********************按提示输入操作符************************:”);printf(“n”);printf(“

1:插入节点

2:删除节点

3:打印二叉树

4:非递归遍历二叉树

5:退出”);scanf(“%d”,&j);

switch(j){

case 1:

printf(“输入要插入的节点:”);

scanf(“%d”,&T);

InsertBST(bst,T);

printf(“插入成功!”);printf(“树状图为:n”);

printtree(bst,layer);

break;

case 2:

}

printf(“输入要删除的节点”);scanf(“%d”,&K);DeleteBST(bst,K);printf(“删除成功!”);printf(“树状图为:n”);printtree(bst,layer);break;case 3: layer=PosttreeDepth(bst);printtree(bst,layer);break;case 4:

printf(“非递归遍历二叉树”);printf(“先序遍历:n”);PreOrderNoRec(bst);printf(“中序遍历:n”);InOrderNoRec(bst);

printf(“后序遍历:n”);

PostOrderNoRec(bst);

printf(“树状图为:n”);

printtree(bst,layer);

break;case 5:

printf(“程序执行完毕!”);

return 0;} goto loop;} return 0;对于第四小问，要储存学生的三个信息，需要把上面程序修改一下，二叉树结构变为 typedefintElemType;

//数据类型 typedefstring SlemType;

typedefint Status;

//返回值类型 //定义二叉树结构 typedefstructBiTNode{ SlemType name;ElemType score;ElemType no;

//数据域 structBiTNode *lChild, *rChild;//左右子树域 }BiTNode, *BiTree;参数不是key,而是另外三个

intInsertBST(BiTree&T,intno,intscore,string name){//插入二叉树函数

if(T==NULL){

T =(BiTree)malloc(sizeof(BiTNode));

T->no=no;T->name=name;T->score=score;

T->lChild=T->rChild=NULL;

return 1;} else if(nono){ InsertBST(T->lChild,no,score,name);} else if(key>T->data){

InsertBST(T->rChild,no,score,name);} else

return 0;} 其他含参函数也类似 即可完成50个信息存储

用数组存储50个信息，查看以往代码

#include #include using namespace std;class student{ private: intnum;string name;int ob1;int ob2;intara;public: void set(inta,stringb,intc,int d);void show();int average();};void student ::set(inta,stringb,intc,int d){ num=a;name=b;ob1=c;ob2=d;ara=(c+d)/2;} void student::show(){ cout<<“学号：”<

int main(){ cout<<“ 欢迎来到学生管理系统”<>numlock;switch(numlock){ case 0: cout<<“输入想查询的学号”<>i;if(i==j){ cout<<“该学号信息已被删除”<>j;delete[j]ptr;cout<<“删除成功”<>k;if(k!=j){

cout<<“该学号信息已经存在，添加失败”<

break;} cout<<“重新输入添加的学号”<>q;cout<<“输入姓名”<>w;cout<<“输入科目一的成绩”<>e;cout<<“输入科目二的成绩”<>r;ptr[k].set(q,w,e,r);break;case 3: for(m=1;m<20;m++){

for(int n=m+1;n<20;n++){

if(ptr[m].average()

student a;

a=ptr[m];

ptr[m]=ptr[n];

ptr[n]=a;

}}

ptr[m].show();} break;case 4: cout<<“谢谢使用”<

二叉排序树储存数据界面（储存学生信息略）

创建二叉树：

插入节点：

删除节点：

非递归遍历：

退出：

数组储存学生信息界面

分析查找效率：

因为二叉树查找要创建二叉树，而数组查找只创建一个数组，二叉树的创建时间比较长，所以对于数据量较少的情况下数组的查找效率比较高。但当数据量增加时，二叉树的查找优势就显现出来。所以数据量越大的时候，二叉树的查找效率越高。

四． 总结与改进

这个实验工作量还是很大的，做了很久。树状图形输出还是不美观，还需要改进。

一开始打算用栈实现非递归，但是根据书里面的伪代码发现部分是在C++编译器里运行不了的（即使补充了头文件和数据的定义），所以之后参考了网上的数组非递归，发现其功能和栈相似。

递归遍历的实现比非递归的遍历真的简单很多。

开始时只看到前三问，所以没有写到储存学生数据的代码，里面还可以用clock（）函数加一个计算查找所要数据时间的代码，让二叉树查找与数组查找到效率比较更加直观。

第五篇：数据结构实验报告

实验报告4 排序

一、实验目的

1、掌握常用的排序方法，并掌握用高级语言实现排序算法的方法。

2、深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用。

3、了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂度的分析方法。

二、实验要求及内容

要求编写的程序所能实现的功能包括：

1、从键盘输入要排序的一组元素的总个数

2、从键盘依次输入要排序的元素值

3、对输入的元素进行快速排序

4、对输入的元素进行折半插入排序

三、实验代码及相关注释

#include using namespace std;#include “malloc.h”

typedef struct { int key;}RedType;

typedef struct { RedType r[100];int length;}SqList;

//1 快速排序的结构体

typedef struct {

int data[100];

int last;}Sequenlist;//2 折半插入排序的结构体

int Partition(SqList &L, int low, int high)

//1 寻找基准

{

L.r[0]=L.r[low];//子表的第一个记录作基准对象

int pivotkey = L.r[low].key;//基准对象关键字 while(low

while(low= pivotkey)--high;

L.r[low] = L.r[high];//小于基准对象的移到区间的左侧

while(low

L.r[high] = L.r[low];//大于基准对象的移到区间的右侧 }

L.r[low] = L.r[0];return low;}

void QuickSort(SqList &L, int low, int high)

//1 快速排序 { //在序列low-high中递归地进行快速排序

if(low < high)

{

int pivotloc= Partition(L, low, high);

//寻找基准

QuickSort(L, low, pivotloc-1);//对左序列同样递归处理

QuickSort(L, pivotloc+1, high);//对右序列同样递归处理

} }

Sequenlist *Sqlset()

//2 输入要折半插入排序的一组元素

{

Sequenlist *L;

int i;

L=(Sequenlist *)malloc(sizeof(Sequenlist));

L->last=0;

cout<<“请输入要排序的所有元素的总个数：”;

cin>>i;

cout<

cout<<“请依次输入所有元素的值：”;

if(i>0)

{

for(L->last=1;L->last<=i;L->last++)

cin>>L->data[L->last];

L->last--;

}

return(L);}

middlesort(Sequenlist *L)

//2 折半插入排序 { int i,j,low,high,mid;for(i=1;i<=L->last;i++){

L->data[0]=L->data[i];

low=1;

high=i-1;

while(low<=high)

{

mid=(low+high)/2;

if(L->data[0]data[mid])

high=mid-1;//插入点在前半区

else

low=mid+1;//插入点在后半区

}

for(j=i;j>high+1;j--){ L->data[j]=L->data[j-1];} //后移

L->data[high+1]=L->data[0];//插入 } return 0;}

int main(){ gg: cout<<“请选择功能（1.快速排序 2.折半插入排序 3.退出程序）：”;int m;cin>>m;cout<

if(m==1){ SqList L;int n;cout<<“请输入要排序的所有元素的总个数：”;cin>>n;cout<

cin>>L.r[i].key;

} cout<

QuickSort(L,1,L.length);

for(int j=1;j<=L.length;j++)

{

cout<

}

cout<

cout<

}

if(m==2){

Sequenlist *L;

int i;

L=Sqlset();

cout<

middlesort(L);

cout<<“折半插入排序后为：”;

for(i=1;i<=L->last;i++)

{

cout<data[i]<<“ ”;

}

cout<

cout<

goto gg;}

if(m==3){

exit(0);

cout<

四、重要函数功能说明

1、Sequenlist *Sqlset()

输入要折半插入排序的一组元素

2、int Partition(SqList &L, int low, int high)

寻找快速排序的基准

3、void QuickSort(SqList &L, int low, int high)

快速排序

4、middlesort(Sequenlist *L)

折半插入排序

五、程序运行结果

下图仅为分别排序一次，可多次排序，后面有相关截图：

六、实验中遇到的问题、解决及体会

1、起初编写快速排序的程序时，我是完全按照老师PPT上的算法敲上去的，然后建立了一个SqList的结构体，调试运行时出现错误，仔细查看才意识到Partition函数中L中应该包含元素key，而我建立结构体时没有注意，然后我将key这个元素补充进去，继续调试，又出现错误，提示我Partition没有定义，我就觉得很奇怪，我明明已经写了函数定义，为什么会这样，当我又回过头来阅读程序时，我发现QuickSort函数中调用了Partition函数，但是我的Partition函数的定义在QuickSort函数的后面，于是我将Partition函数放到了QuickSort函数的前面，再次调试运行，就可以正常运行，得出结果了。这让我懂得，编程一定要认真仔细，不可大意马虎，否则又会花很多时间回过头来检查修改程序，得不偿失。

运行程序错误截图：

2、本来我是编写了两个程序，分别实现快速排序和折半插入排序的功能，但我后来想我是否可以将其合二为一，于是我想到用if选择语句用来实现不同的功能，从键盘输入功能选项m，if（m==1），可以进行快速排序，if（m==2），可以进行折半插入排序，于是我继续思考，我是否可以在一次运行程序中，多次对含有不同元素的序列进行排序，于是我用了goto语句，每次排序一次后，自动循环到选择语句，当不需要在排序的时候，可以从键盘输入3，退出程序，这样一来，程序变得更加实用和清晰明朗。这让我懂得，想要编出好的程序，要善于思考，在实现所需功能的前提下，多想问题，看是否能使程序更加实用简便。

修改程序前两个运行结果截图

（两个程序，调试运行两次，每次只能进行一次排序）

1、快速排序程序运行结果截图：

2、折半插入排序程序结果截图：

程序重要模块修改截图：

修改程序后运行截图：

（一个程序，调试运行一次，可多次进行不同序列的不同排序）