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

目录一、设计题目 (2)二、设计目的 (2)三、数据结构及算法设计 (2)四、源代码 (2)五、运行结果分析 (14)六、实训总结 (17)七、参考资料 (18)一、设计题目课程设计题一：链表操作利用链表的插入运算建立线性链表，然后实现链表的查找、插入、删除、计数、输出、排序、逆置等运算（查找、插入、删除、查找、计数、输出、排序、逆置要单独写成函数），并能在屏幕上输出操作前后的结果。

课程设计题二：二叉树的基本操作1.对任意给定的二叉树（顶点数自定）建立它的二叉链表存储结构，并实现二叉树的先序、中序、后序三种遍历，输出三种遍历的结果。

2．求二叉树高度、结点数、度为1的结点数和叶子结点数。

二、设计目的通过课程实训掌握线性链表的建立及线性链表的基本操作，进一步了解链表时如何进行创建，在创建时是运用什么思想，了解输出链表、查找、插入、删除、计数、排序等基本操作的算法的实质及运用。

掌握二叉树的概念和性质，掌握任意二叉树存储结构及任意二叉树的基本操作，通过设计二叉树的遍历，进一步了解二叉树的遍历，并进一步了解递归的实质，并且计算了结点数，叶子数，更加了解其算法的实质。

三、数据结构及算法设计链表的各种功能，例如创建，输出，查找，插入，删除，计数，排序；以上这些功能都是先建立子函数，然后再主函数main中进行调用，而不是直接在主函数中生成，调用过程中主要的就是实参，形参之间的传递，同时运用case语句构造主菜单，使可以对各种方法进行选择。

二叉树的各种功能，例如创建，先序，中序，后序三种遍历，高度，结点数，叶子结点数等.对于二叉树的遍历，是运用的递归的思想，求高度，结点数，叶子结点数等方法和链表一样，都是先建立子函数，再进行调用。

四、源代码对于链表#include <stdio.h>#include <stdlib.h>#define ERROR 0#define OK 1typedef int ElemType;typedef struct LNode{ElemType data;struct LNode *next;}LNode,*LinkList;struct LNode *L;int x;void Creat_L(LinkList &L) //建立单链表{ 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("数据元素个数:%d",n);}void Print_L(LinkList &L) //输出{ LinkList p;p=L->next ;printf("创建的链表为：\n");if(L!=NULL)do{printf("%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;}else{p=p->next;i++;if(p==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 && j<i-1){p=p->next;++j;}if(!p || j>i-1){printf("输入位置有误\n");}else{q=(LinkList)malloc(sizeof(LNode));q->data=e;q->next=p->next;p->next=q;}p=L;while(p->next!=NULL){printf("%d ",p->next->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 && j<i-1){p=p->next;++j;}if(!(p->next) || j>i-1){printf("输入有误！\n");}else{q=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) //冒泡排序{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;while(s){ q->next=p;p=q;q=s;if(s->next!=NULL) //s后面还有结点，则逆置继续 s=s->next;elsebreak;}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");printf("5.删除\n");printf("6.计数\n");printf("7.排序\n");printf("8.逆置\n");printf("0.退出\n");printf("\n");printf("select [0—8]：");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: 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 <stdio.h>/* 头文件 */#include <stdlib.h>#include <malloc.h>typedef struct BiTNode/* 定义结点 */{char data;struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;BiTree CreateBiTree()/* 用先序递归建树 */{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);}}/*中序遍历*/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==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 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==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");PostOrderTraverse(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为数据结尾。