数据结构和算法实验报告

数据结构实验报告

题目： 线性表 班级：网络工程1401班 学号： 1408020106 指导教师： 高峰 日期： 2016/7/6

专业整理 知识分享

完美WORD格式

实验一：线性表

一：实验要求

掌握数据结构中线性表的基本概念。

熟练掌握线性表的基本操作：创建、插入、删除、查找、输出、求长度及合并并运算在顺序存储结构撒谎能够的实验。 熟练掌握链表的各种操作和应用。

二．实验内容

1. 编程实现在顺序存储的有序表中插入一个元素（数据类型为整型）。

2. 编程实现把顺序表中从i个元素开始的k个元素删除（数据类型为整型）。

三：实验过程及步骤

源代码：

#include #include

#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct{ int * elem; int length; int listsize; }SqList; //SqList sq;

void InitList_Sq(SqList *sq) //初始化列表 {

sq->elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int)); sq->length=0;

sq->listsize=LIST_INIT_SIZE; printf(\"---申请空间成功---!\\n\"); }

void GetElem(SqList *sq,int i)//获取第i位置元素的值 {

int *p;

p=&(sq->elem[i-1]); printf(\"%d\

专业整理 知识分享

完美WORD格式

printf(\"\\n\"); }

int ListInsert_Sq(SqList *sq,int i,int a)//在i位置之前插入a {

int *p,*q;

if(i<=0||i>sq->length+1) {

printf(\"---位置不合法---!\\n\"); return 0; }

if(sq->length>=sq->listsize) {

int* newbase=(int *)realloc(sq->elem,(sq->listsize+LISTINCREMENT)*sizeof(int)); if(!newbase) {

printf(\"申请空间溢出\\n\"); return 0; }

sq->elem=newbase;

sq->listsize+=LISTINCREMENT; }

p=&(sq->elem[i-1]);//p指向第i位置的元素

q=&(sq->elem[sq->length-1]);//q指向最后一个元素 for(;q>=p;--q) *(q+1)=*q; *p=a;

++sq->length; return 1; }

int ListDelete_Sq(SqList *sq,int i) //删除i位置上的值 {

int *p,*q;

if(i<1||i>sq->length) return 0;

p=&(sq->elem[i-1]);//p指向第i位置的元素 q=sq->elem+sq->length-1;//q指向最后一个元素 for(++p;p<=q;++p) {

*(p-1)=*p; }

--sq->length; return 1; }

void visit(SqList *sq)//输出数据 {

int i=1;

专业整理 知识分享

完美WORD格式

for(;i<=sq->length;i++) {

int *p;

p=&sq->elem[i-1]; printf(\"%d\printf(\" \"); } }

void main() {

int i=1,a=0,boo=1,number=0; SqList s,*sq; sq=&s;

InitList_Sq(sq);

printf(\"初始化空表\\n\"); printf(\"输入数据个数：\\n\"); scanf(\"%d\

printf(\"输入%d个数据：\printf(\"\\n\");

for(;i<=number;i++) {

scanf(\"%d\

if(boo=ListInsert_Sq(sq,i,a)) {

printf(\"---插入成功！---\\n\"); } else {

printf(\"---插入不成功,重新插入---！\\n\"); i=i-1; } }

printf(\"输出所有元素\\n\"); visit(sq); printf(\"\\n\");

printf(\"输出删除的位置:\"); scanf(\"%d\

if(boo=ListDelete_Sq(sq,a)) {

printf(\"---数据删除成功！---\\n\"); }else {

printf(\"---没有删除成功---\\n\"); }

专业整理 知识分享

完美WORD格式

printf(\"输出所有元素:\\n\"); visit(sq); printf(\"\\n\");

printf(\"输出要显示数据的位置：\"); scanf(\"%d\

printf(\"输出%d位置数值\\n\if(a<0||a>sq->length) {

printf(\"---输出位置的数据不存在---\\n\"); } else {

GetElem(sq,a); } }

步骤：

1.初始化空表

2.顺序插入数据后输出所有元素

3.选择删除位置，删除数据后输出所有元素 4.选择查看的数据位置，输出选择查看的数据

四：实验结果及分析

分析：

本程序在实现顺序存储插入以及删除i个元素开始的k个元素删除（数据类型为

整型）。之外在删除、查看是实时输出结果，并且可以查看希望显示数据的位置。

专业整理 知识分享

完美WORD格式

数据结构实验报告

题目： 树

专业整理 知识分享

完美WORD格式

班级：网络工程1401班 学号： 1408020106 指导教师： 高峰 日期： 2016/7/6

实验二：树

一：实验要求

掌握二叉树，二叉树排序数的概念和存储方法。

掌握二叉树的遍历算法。

熟练掌握编写实现树的各种运算的算法。

二．实验内容

统计一棵二叉树中每种类型节点数（度为0/1/2的节点数）。

三：实验过程及步骤

#include #include #include

typedef struct BitNode{ int data;

struct BitNode *lchild,*rchild; }BitNode,*BitTree; BitTree BitTreeInit(){ BitTree BT;

BT=(BitNode*)malloc(sizeof(BitNode)); BT=NULL;

专业整理 知识分享

完美WORD格式

return BT; }

BitTree BitTreeCreat(BitTree &BT){ int ch;

printf(\"请输入节点的内容,输入0时结束建立！\\n\"); scanf(\"%d\ if(ch==0) BT=NULL; else{

BT=(BitTree)malloc(sizeof(BitNode)); BT->data=ch;

BitTreeCreat(BT->lchild); BitTreeCreat(BT->rchild); }

return BT; }

void BitTreeEmpty(BitTree BT){ if(BT==NULL)

printf(\"树为空！\\n\"); else

printf(\"树非空！\\n\"); }

void PreOrderTraverse(BitTree BT){ if(BT!=NULL){

printf(\"树结点的内容为:%d\\n\ PreOrderTraverse(BT->lchild); PreOrderTraverse(BT->rchild); } }

void InOrderTraverse(BitTree BT){ if(BT!=NULL){

InOrderTraverse(BT->lchild);

printf(\"树结点的内容为:%d\\n\ InOrderTraverse(BT->rchild); } }

void PostOrderTraverse(BitTree BT){ if(BT!=NULL){

PostOrderTraverse(BT->lchild); PostOrderTraverse(BT->lchild);

printf(\"树结点的内容为:%d\\n\ } }

int count(BitTree BT){

专业整理 知识分享

完美WORD格式

if(BT==NULL) return 0; else

return(count(BT->lchild)+count(BT->rchild)+1); }

int BinTreeDepth(BitTree BT){ int i=1,j=1; if(BT==NULL) return 0; else {

i=BinTreeDepth(BT->lchild); j=BinTreeDepth(BT->rchild); if(i>j)

return(i+1); else

return (j+1); } }

void BinTreeClear(BitTree &BT){ if(BT){

if(BT->lchild)

BinTreeClear(BT->lchild); if(BT->rchild)

BinTreeClear(BT->rchild); free(BT); BT=NULL; } } main(){

int i=1,j,l; BitTree BT; while(i!=0){

printf(\"-----------------欢迎使用-------------------\\n\"); printf(\"请选择要进行的操作\\n\");

printf(\"1.初始化一棵树 2.建立一棵树 3.判断树是否为空\\n\"); printf(\"4.按前序遍历树 5.按中序遍历树 6.按后序遍历树\\n\"); printf(\"7.求树的深度 8.求树的结点数 9.把树清空\\n\"); printf(\"0.退出操作界面\\n\");

printf(\"-----------------谢谢使用-------------------\\n\"); scanf(\"%d\ switch(j){

case 1:BT=BitTreeInit();printf(\"树已经初始化！\\n\");break; case 2:BitTreeCreat(BT);break;

专业整理 知识分享

完美WORD格式

case 3:BitTreeEmpty(BT);break; case 4:PreOrderTraverse(BT);break; case 5:InOrderTraverse(BT);break; case 6:PostOrderTraverse(BT);break;

case 7:l=BinTreeDepth(BT);printf(\"树的深度为：%d\\n\ case 8:l=count(BT);printf(\"树的结点数为：%d\\n\ case 9:BinTreeClear(BT);printf(\"树已经清空！\\n\");break; case 0:exit(0); } } }

步骤：

1.选择进行的操作

2.初始化、建立、判断树是否空、先/中/后序遍历、求深度/结点，清空树 3.显示结果

四：实验结果及分析

专业整理 知识分享

完美WORD格式

分析：

本程序不仅可以统计一棵二叉树中每种类型节点数（度为0/1/2的节点数）。

同时让他有以下功能：1.初始化一棵树。2.建立一棵树。3.判断树是否为空。4.分别按先/中/后序遍历树。5.求树的深度。6.求树的结点数。7.清空树。

专业整理 知识分享