《2022年2022年链表和二叉树的基本操作 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年链表和二叉树的基本操作 .pdf（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、山东科技大学泰山科技学院课 程 实 训 说 明 书课程：数据结构题目：链表和二叉树的基本操作院系：信息工程系专业班级：信管 09-2 学号：0943030206 学生姓名：丁辉指导教师：亓静2011年 5 月 20 日名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 17 页 - - - - - - - - - 2 成绩评语：指导教师名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - -
2、 - - - 第 2 页，共 17 页 - - - - - - - - - 3 目录一、 设计题目 4 二、 设计目的 4 三、数据结构及算法设计 5 四、 源代码 9 五、 运行结果分析 15 六、 实习总结（收获及体会） 17 七、参考资料；附录（核心代码） 17 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 17 页 - - - - - - - - - 4 一、设计题目：（一）链表操作（二）二叉树基本操作二、设计目的：（一）链表操作实训基本目的1掌握线性链表的建立
3、。2掌握线性链表的基本操作。（二）二叉树基本操作实训基本目的1掌握二叉树的概念和性质2. 掌握任意二叉树存储结构。3掌握任意二叉树的基本操作。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 17 页 - - - - - - - - - 5 三、数据结构及算法设计：（一）链表1.创建列表Lnode *CreatList(void) LinkList p,head,q; int x,n; head=q=(LinkList)malloc(sizeof(Lnode); print
4、f( 输入数据 ,个数为： n); scanf(%d,&n); for(int i=0;idata=x; q-next=p; q=p; p-next=NULL; return head; 2.输出列表void PrintList(LinkList L) LinkList p; p=L-next; printf( 输出数据 n); while(p) printf(%d ,p-data); p=p-next; printf(n); 3.插入元素bool ListInsert(LinkList L,int i,ElemType e) LinkList p,s; 名师资料总结 - - -精品资料欢迎下
5、载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 17 页 - - - - - - - - - 6 int j=0; p=L; while(jnext; j+; if(!p|ji-1) return ERROR; s=(LinkList)malloc(sizeof(Lnode); s-data=e; s-next=p-next; p-next=s; PrintList( L); return OK; 4.删除元素bool ListDelete(LinkList L,int i,ElemType e) LinkL
6、ist p,s; int j=0; p=L; while(jnext; j+; if(!p|ji-1) return ERROR; s=p-next; p-next=s-next; e=s-data; printf( 删除元素为： %dn,e); free(s); PrintList( L); return OK; 5.查找元素位置bool GetElem(LinkList L,int i,ElemType e) LinkList p; int j=1,flag=1; p=L-next; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - -
7、- - 名师精心整理 - - - - - - - 第 6 页，共 17 页 - - - - - - - - - 7 if(!p)return ERROR; while(p) if(p-data=e) flag=0; i=j;j+; printf( 查找位置 %d：,i); break; else j+; p=p-next; if(flag=1)printf( 无此元素 n); return OK; （二）二叉树1、初始化二叉树，即把树根指针置空void BinTreeInit(BitTree *BT) BT=(BitTree)malloc(sizeof(BitNode); BT-data=NU
8、LL; cout二叉树初始化成功 !ch; if(ch=#) BT=NULL; else if(!(BT=(BitTree)malloc(sizeof(BitNode) exit(0); BT-data=ch; BinTreeCreat(BT-lchild); BinTreeCreat(BT-rchild); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 17 页 - - - - - - - - - 8 return 0; 3、/* 检查二叉树是否为空 */ void
9、BinTreeEmpty(BitTree &BT) if(BT-data=NULL) cout 是空二叉树 !endl; else cout 不是空二叉树 !endl; 4、按任一种遍历次序（包括按先序、中序、后序）void BinTraverse(BitTree &BT) if(BT!=NULL) coutdata; BinTraverse(BT-lchild); BinTraverse(BT-rchild); 5、求二叉树的深度int BinTreeDepth(BitTree BT) int depthval; if(BT) int depthLeft=BinTreeDepth(BT-lc
10、hild); int depthRight=BinTreeDepth(BT-rchild); depthval=1+(depthLeftdepthRight?depthLeft:depthRight); else depthval=0; return depthval; 6、求二叉树中所有结点数 */ int BinTreeCount(BitTree BT) int node; if(BT) int lchild=BinTreeCount(BT-lchild); int rchild=BinTreeCount(BT-rchild); node=lchild+rchild+1; 名师资料总结 -
11、 - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 17 页 - - - - - - - - - 9 else node=0; return node; 四、源代码：（一）链表#include #include #define ERROR 0 #define OK 1 typedef int ElemType ; typedef struct Lnode ElemType data; struct Lnode *next; Lnode,*LinkList; / 创建链表 Lnode *Cre
12、atList(void) LinkList p,head,q; int x,n; head=q=(LinkList)malloc(sizeof(Lnode); printf(输入数据 , 个数为： n); scanf(%d,&n); printf(请输入数据： ); for(int i=0;idata=x; q-next=p; q=p; p-next=NULL; return head; / 输出链表 void PrintList(LinkList L) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - -
13、- - - - 第 9 页，共 17 页 - - - - - - - - - 10 LinkList p; p=L-next; printf(输出数据 n); while(p) printf(%d ,p-data); p=p-next; printf(n); / 插入元素bool ListInsert(LinkList L,int i,ElemType e) LinkList p,s; int j=0; p=L; while(jnext; j+; if(!p|ji-1) return ERROR; s=(LinkList)malloc(sizeof(Lnode); s-data=e; s-ne
14、xt=p-next; p-next=s; PrintList( L); return OK; / 删除 bool ListDelete(LinkList L,int i,ElemType e) LinkList p,s; int j=0; p=L; while(jnext; j+; if(!p|ji-1) return ERROR; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 17 页 - - - - - - - - - 11 s=p-next; p-next=s-
15、next; e=s-data; printf(删除元素为： %dn,e); free(s); PrintList( L); return OK; / 查找 bool GetElem(LinkList L,int i,ElemType e) LinkList p; int j=1,flag=1; p=L-next; if(!p)return ERROR; while(p) if(p-data=e) flag=0; i=j;j+; printf(查找位置： %dn：,i); break; else j+;p=p-next; if(flag=1)printf(无此元素 n); return OK;
16、void main() LinkList L;int i,e,x; printf(请先建立一个列表 n); L=CreatList(); printf(您可以选择以下操作 n); printf(1.建立一个新的列表 n); printf(2.在表中插入一个新元素 n); printf(3.删除表中元素 n); printf(4.查找元素位置 n); printf(5.输出列表： n); for(;) printf(请选择将要进行的操作：); fflush(stdin); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整
17、理 - - - - - - - 第 11 页，共 17 页 - - - - - - - - - 12 scanf(%d,&x); switch(x) case 1: L=CreatList(); break; case 2: printf(插入位置： ); scanf(%d,&i); printf(插入元素： ); scanf(%d,&e); ListInsert( L,i,e); break; case 3: printf(删除位置： ); scanf(%d,&i); ListDelete(L,i,e); break; case 4: printf(查找元素： ); scanf(%d,&e)
18、; GetElem(L,i,e); break; case 5: PrintList( L); break; default: printf(请输入 15！ ！ ！); （二）二叉树#include #include typedef char DataType; typedef struct BitNode DataType data; struct BitNode *lchild,*rchild; *BitTree; void BinTreeInit(BitTree &BT)/初始化二叉树，即把树根指针置空 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - -
19、 - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 17 页 - - - - - - - - - 13 BT=(BitTree)malloc(sizeof(BitNode); BT-data=NULL; cout 二叉树初始化成功 !ch; if(ch=#) BT=NULL; else if(!(BT=(BitTree)malloc(sizeof(BitNode) exit(0); BT-data=ch; BinTreeCreat(BT-lchild); BinTreeCreat(BT-rchild); return 0; /cout按先序序列建立一个二叉
20、树已经完成!data=NULL) cout 是空二叉树 !endl; else cout 不是空二叉树 !endl; void BinpreTraverse(BitTree &BT)/先序序列遍历二叉树 if(BT!=NULL) coutdata; BinpreTraverse(BT-lchild); BinpreTraverse(BT-rchild); void BininTraverse(BitTree &BT)/中序序列遍历二叉树 if(BT!=NULL) BininTraverse(BT-lchild); coutdata; BininTraverse(BT-rchild); 名师资料
21、总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 17 页 - - - - - - - - - 14 void BinpostTraverse(BitTree &BT)/后序序列遍历二叉树 if(BT!=NULL) BinpostTraverse(BT-lchild); BinpostTraverse(BT-rchild); coutdata; int BinTreeDepth(BitTree BT)/求二叉树的深度 int depthval; if(BT) int depthL
22、eft=BinTreeDepth(BT-lchild); int depthRight=BinTreeDepth(BT-rchild); depthval=1+ (depthLeftdepthRight?depthLeft:depthRight); else depthval=0; return depthval; int BinTreeCount(BitTree BT)/求二叉树中所有结点数 int node; if(BT) int lchild=BinTreeCount(BT-lchild); int rchild=BinTreeCount(BT-rchild); node=lchild+
23、rchild+1; else node=0; return node; void main() int i; BitTree BT; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 17 页 - - - - - - - - - 15 cout1 、初始化二叉树 :n2 、按先序序列建立二叉树 n3 、判断二叉树是否为空 :; coutn4 、先序序列遍历二叉树 n5 、中序序列遍历二叉树n6 、后序序列遍历二叉树 n7 、求二叉树的深度 n8 、求二叉树节点的个数 en
24、dl; for(;) couti; if(i=1) BinTreeInit(BT); else if(i=2) cout 输入你要建立的二叉树 :endl; BinTreeCreat(BT); else if(i=3) BinTreeEmpty(BT); else if(i=4) BinpreTraverse(BT);coutendl; else if(i=5) BininTraverse(BT);coutendl; else if(i=6) BinpostTraverse(BT);coutendl; else if(i=7) cout 二叉树的深度 :BinTreeDepth(BT)endl
25、; else if(i=8) cout 二叉树的节点数 BinTreeCount(BT)endl; else return ; 五、运算结果分析：（一）链表请先建立一个列表输入数据 ,个数为：5 请输入数据：12 34 56 78 90 您可以选择以下操作1.建立一个新的列表2.在表中插入一个新元素3.删除表中元素名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 17 页 - - - - - - - - - 16 4.查找元素位置5.输出列表：请选择将要进行的操作：2 插
26、入位置： 2 插入元素： 10 输出数据12 10 34 56 78 90 请选择将要进行的操作：3 删除位置： 5 删除元素为：78 输出数据12 10 34 56 90 请选择将要进行的操作：4 查找元素： 32 无此元素请选择将要进行的操作：4 查找元素： 34 查找位置： 3 ：请选择将要进行的操作：5 输出数据12 10 34 56 90 请选择将要进行的操作：0 Press any key to continue （二） 二叉树1、初始化二叉树: 2、按先序序列建立二叉树3、判断二叉树是否为空: 4、先序序列遍历二叉树5、中序序列遍历二叉树6、后序序列遍历二叉树7、求二叉树的深度8
27、、求二叉树节点的个数输出你所需的操作:1 二叉树初始化成功! 输出你所需的操作:2 输入你要建立的二叉树: abc#de#f#g# 输出你所需的操作:3 不是空二叉树! 输出你所需的操作:4 abcdefg 输出你所需的操作:5 cbefdga 输出你所需的操作:6 cfegdba 输出你所需的操作:7 二叉树的深度:5 输出你所需的操作:8 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 17 页 - - - - - - - - - 17 二叉树的节点数7 输出你所需的操作:0 Press any key to continue六、实习总结：经过此次实训，更熟悉了链表及二叉树的应用，加强了自己对编程的兴趣，对以后的学习做了很好的铺垫；同时也发现了自己的一些问题，比如基本知识不是太扎实，很多只是还不是太熟悉等问题，需要在今后的学习中更加努力，学好接下来的课程。七、参考资料：数据结构（ c 语言版）作者：严蔚敏，吴伟民名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 17 页 - - - - - - - - -