山东科技大学泰山科技学院

1、目录一、 设计题目2二、 设计目的2三、 数据结构及算法设计2四、源代码 2五、运行结果分析14六、实训总结17七、参考资料18一、设计题目课程设计题一：链表操作 利用链表的插入运算建立线性链表，然后实现链表的查找、插入、删除、计数、输出、排序、逆置等运算（查找、插入、删除、查找、计数、输出、排序、逆置要单独写成函数），并能在屏幕上输出操作前后的结果。 课程设计题二：二叉树的基本操作 1.对任意给定的二叉树（顶点数自定）建立它的二叉链表存储结构，并实现二叉树的先序、中序、后序三种遍历，输出三种遍历的结果。 2 求二叉树高度、结点数、度为1的结点数和叶子结点数。二、设计目的通过课程实训掌握线性链

2、表的建立及线性链表的基本操作，进一步了解链表时如何进行创建，在创建时是运用什么思想，了解输出链表、查找、插入、删除、计数、排序等基本操作的算法的实质及运用。掌握二叉树的概念和性质，掌握任意二叉树存储结构及任意二叉树的基本操作，通过设计二叉树的遍历，进一步了解二叉树的遍历，并进一步了解递归的实质，并且计算了结点数，叶子数，更加了解其算法的实质。三、数据结构及算法设计链表的各种功能，例如创建，输出，查找，插入，删除，计数，排序；以上这些功能都是先建立子函数，然后再主函数main中进行调用，而不是直接在主函数中生成，调用过程中主要的就是实参，形参之间的传递，同时运用case语句构造主菜单，使可以对各

3、种方法进行选择。二叉树的各种功能，例如创建，先序，中序，后序三种遍历，高度，结点数，叶子结点数等.对于二叉树的遍历，是运用的递归的思想，求高度，结点数，叶子结点数等方法和链表一样，都是先建立子函数，再进行调用。四、源代码对于链表#include #include #define ERROR 0#define OK 1 typedef int ElemType;typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkList;struct LNode *L;int x;void Creat_L(LinkList &L) /建

4、立单链表 LinkList p,q;L=(LinkList)malloc(sizeof(LNode); L-next=NULL;p=L; printf(建立单链表,输入0则退出.n); scanf(%d,&x);while(x!=0) q=(LinkList)malloc(sizeof(LNode); q-data=x; q-next=NULL; p-next=q; p=q; scanf (%d,&x);void Count_L(LinkList &L,int n) /计数 LinkList p;n=0;p=L-next;while(p) n+;p=p-next; printf(数据元素个数:

5、%d,n);void Print_L(LinkList &L) /输出 LinkList p;p=L-next ;printf(创建的链表为：n);if(L!=NULL)doprintf(%d ,p-data );p=p-next ;while(p);void Getelem_L(LinkList &L) /查找单链表中的元素 LinkList p;int i=1;printf(输入一个要查找的数据:n);scanf(%d,&x);p=L-next; while(p!=NULL)if(p-data=x)printf(该元素位置：%d,i);break;elsep=p-next;i+;if(p=

6、NULL) printf(未找到元素);void Insert_L(LinkList &L,int i,int e) /在单链表中插入新元素 LinkList p,q;int j;printf(输入要插入的数据位置和数据:n);scanf(%d %d,&i,&e); p=L;j=0;while(p & jnext;+j;if(!p | ji-1)printf(输入位置有误n);elseq=(LinkList)malloc(sizeof(LNode); q-data=e; q-next=p-next;p-next=q;p=L; while(p-next!=NULL)printf(%d ,p-ne

7、xt-data);p=p-next;void Delete_L(LinkList &L, int i,int e) /删除元素 LinkList p,q;int j=0;p=L;printf(输入要删除第几个数据:n);scanf(%d,&i);while(p-next & jnext;+j;if(!(p-next) | ji-1)printf(输入有误！n);elseq=p-next;p-next=q-next;e=q-data;p=L;while(p-next!=NULL)printf(%d ,p-next-data);p=p-next;void Sort_L(LinkList &L) /

8、冒泡排序LinkList p,q;int t;for(p=L-next;p!=NULL;p=p-next) /p指向第一个结点 / q为下一个结点（第二个结点）for(q=p;q;q=q-next) /比较第一和第二个元素大小if(p-data q-data) t=p-data; p-data=q-data; q-data=t; p=L-next;while(p)printf(%d ,p-data);p=p-next;void Reverse_L(LinkList &L) /逆置 LinkList s,p,q;p=L-next;q=p-next;s=q-next;p-next=NULL;whi

9、le(s) q-next=p;p=q;q=s;if(s-next!=NULL) /s后面还有结点，则逆置继续 s=s-next; else break;s-next=p; L-next=s; /头结点指向最后一个结点 p=L-next; while(p!=NULL)printf(%d ,p-data);p=p-next;void main() /主程序 LinkList s;int menu;menu=1;int i,e,n; while(menu!=0) printf(.n);printf(1.建立链表n);printf(2.输出n);printf(3.查找n);printf(4.插入n);

10、printf(5.删除n);printf(6.计数n);printf(7.排序n);printf(8.逆置n);printf(0.退出n);printf(n);printf(select 08：);scanf(%d,&menu); switch(menu) case 1: Creat_L(s); break; /建立链表 case 2: Print_L(s);break; /输出 case 3: Getelem_L(s);break; /查找 case 4: Insert_L(s,i,e);break; /插入 case 5: Delete_L(s,i,e);break; /删除 case 6

11、: Count_L(s,n);break; /计数 case 7: Sort_L(s);break; /排序 case 8: Reverse_L(s);break; /逆置 case 0: menu=0;break; default : printf(Error!n); 对于二叉树#include /* 头文件 */#include #include typedef struct BiTNode/* 定义结点 */ char data; struct BiTNode *lchild,*rchild;BiTNode,*BiTree;BiTree CreateBiTree()/* 用先序递归建树

12、*/ char p; BiTree T; scanf(%c,&p); if(p= ) T=NULL; else T=(BiTNode *)malloc(sizeof(BiTNode);/* 开辟存储空间 */ T-data=p; T-lchild=CreateBiTree(); T-rchild=CreateBiTree(); return (T);/*先序遍历*/void PreOrderTraverse(BiTree T) if (T) printf(%c ,T-data); PreOrderTraverse(T-lchild); PreOrderTraverse(T-rchild); /

13、*中序遍历*/void InOrderTraverse(BiTree T) if (T) InOrderTraverse(T-lchild); printf(%c ,T-data); InOrderTraverse(T-rchild); /*后序遍历*/void PostOrderTraverse(BiTree T) if (T) PostOrderTraverse(T-lchild); PostOrderTraverse(T-rchild); printf(%c ,T-data); /*二叉树的深度*/int TreeDepth(BiTree T) int hl,hr,h,max; if(T

14、=NULL) return(0); else hl=TreeDepth(T-lchild); hr=TreeDepth(T-rchild); h=max(hl,hr)+1; return(h); /*二叉树的结点数*/int NodeCount(BiTree T) int num1=0,num2=0; if(T=NULL) return(0); if(T-lchild!=NULL) num1=NodeCount(T-lchild); if(T-rchild!=NULL) num2=NodeCount(T-rchild); return(num1+num2+1); /*度为1的结点数*/int

15、Deg1NodCount(BiTree T) int dl,dr,count; if(T=NULL) return(count=0); if(T-lchild!=NULL|T-rchild!=NULL) return(count=1); dl=Deg1NodCount(T-lchild); dr=Deg1NodCount(T-rchild); return(count=dl+dr); count+; /* 叶子结点个数 */int LeafCount(BiTree T) int num1,num2; if(T=NULL) return(0); if(T-lchild=NULL&T-rchild

16、=NULL) return(1); num1=LeafCount(T-lchild); num2=LeafCount(T-rchild); return(num2+num1); void main() /* 主函数 */ BiTree T; int height,numN,numD,numL; printf(先序建立二叉链表:n); T=CreateBiTree(); printf(n先序遍历输出:n); PreOrderTraverse(T); printf(n中序遍历输出:n); InOrderTraverse(T); printf(n后序遍历输出:n); PostOrderTravers

17、e(T); height=TreeDepth(T); printf(n二叉树的深度:%d,height); numN=NodeCount(T); printf(n结点数 :%d,numN); numD=Deg1NodCount(T); printf(n度为1的结点数:%d,numD); numL=LeafCount(T); printf(n叶子结点数:%d,numL);四、 运行结果分析.链表 链表操作程序实现了链表的八个基本功能：当运行程序时，屏幕会出现一个选择菜单，如图：(1).链表的创建当选择1便会出现：输入数据，用空格分开，并以0为数据结尾。如图：然后随机输入一串数据，例如6 8 3

18、1 2 9 0，回车然后便会出现生成的链表6 8 3 1 2 9。如图：（2）链表的输出操作 （3）链表的查找 选择3，输入查找的数据为6，显示该元素位置为1，如图：（4）链表的插入插入的数据位置为5，数据为5，如图：（5）删除链表中数据选5，删除第二个数据，如图：（6）计数操作选6，数据元素个数为6个，如图：（7）排序选7,冒泡排序，如图：（8）逆置（9）退出按0则退出，至此整个链表的各种功能运算完成。.二叉树对于二叉树，共实现了先，中，后序三种遍历及结点数，叶子数，深度等。(1).创建二叉树 当运行程序时，会出现按照先序遍历创建二叉树，例如输入ABC 。如图：(2)先序、中序、后序遍历（3）二叉树的深度、结点数、度为1的结点数、叶子结点数二叉树的各项操作完成。六、实训总结通过两周的数据结构实训，进一步加深了对数据结构整体的理解，明白了链表的各种操作的实质，并且对老师课上讲的各种算法进行了实际的运用，更加掌握了各种算法的使用方法，例如链表的创建，查找，插入，二叉树的遍历等算法。而且，通过这一次的实训，不仅加深了对数据结构知