{
ListNode *p=head->next; //从开始结点打印 while(p){ printf(\ \ p=p->next; }
printf(\}
//==========删除所有结点,释放空间=========== void DeleteAll(LinkList head) {
ListNode *p=head,*r; while(p->next){ r=p->next; free(p); p=r; } free(p); }
实验结果:
Input # to end Please input Node_data:bat Input # to end Please input Node_data:cat Input # to end Please input Node_data:eat Input # to end Please input Node_data:fat Input # to end Please input Node_data:hat Input # to end Please input Node_data:jat Input # to end Please input Node_data:lat Input # to end Please input Node_data:mat Input # to end Please input Node_data:#
mat, lat, jat, hat, fat, eat, cat, bat, Delete node (y/n):y
Please input Delete_data:hat
mat, lat, jat, fat, eat, cat, bat, Insert node (y/n):y
Please input Insert_data:put position :5
mat, lat, jat, fat, eat, put, cat, bat, 请按任意键继续. . .
示意图:
head mat lat jat hat fat eat cat bat NULL head mat lat jat fat eat hat cat bat NULL head mat lat jat fat eat cat put
bat NULL 心得体会:
本次实验使我们对链表的实质了解更加明确了,对链表的一些基本操作也更加熟练了。另外实验指导书上给出的代码是有一些问题的,这使我们认识到实验过程中不能想当然的直接编译执行,应当在阅读并完全理解代码的基础上再执行,这才是实验的意义所在。
实验2
实验题目:二叉树操作设计和实现
实验目的:
掌握二叉树的定义、性质及存储方式,各种遍历算法。
实验要求:
采用二叉树链表作为存储结构,完成二叉树的建立,先序、中序和后序以及按层次遍历的操作,求所有叶子及结点总数的操作。
实验主要步骤:
1、分析、理解程序。 2、调试程序,设计一棵二叉树,输入完全二叉树的先序序列,用#代表虚结点(空指针),如ABD###CE##F##,建立二叉树,求出先序、中序和后序以及按层次遍历序列,求所有叶子及结点总数。
实验代码
#include\#include\#include\
#define Max 20 //结点的最大个数 typedef struct node{ char data;
struct node *lchild,*rchild;
}BinTNode; //自定义二叉树的结点类型 typedef BinTNode *BinTree; //定义二叉树的指针
int NodeNum,leaf; //NodeNum为结点数,leaf为叶子数 //==========基于先序遍历算法创建二叉树==============
//=====要求输入先序序列,其中加入虚结点\以示空指针的位置========== BinTree CreatBinTree(void) {
BinTree T; char ch;
if((ch=getchar())=='#') return(NULL); //读入#,返回空指针 else{ T= (BinTNode *)malloc(sizeof(BinTNode)); //生成结点 T->data=ch; T->lchild=CreatBinTree(); //构造左子树 T->rchild=CreatBinTree(); //构造右子树 return(T); } }
//========NLR 先序遍历============= void Preorder(BinTree T) {
if(T) { printf(\ //访问结点 Preorder(T->lchild); //先序遍历左子树 Preorder(T->rchild); //先序遍历右子树 } }
//========LNR 中序遍历=============== void Inorder(BinTree T) {
if(T) { Inorder(T->lchild); //中序遍历左子树 printf(\ //访问结点 Inorder(T->rchild); //中序遍历右子树 } }
//==========LRN 后序遍历============ void Postorder(BinTree T) {
if(T) { Postorder(T->lchild); //后序遍历左子树 Postorder(T->rchild); //后序遍历右子树 printf(\ //访问结点 } }
//=====采用后序遍历求二叉树的深度、结点数及叶子数的递归算法======== int TreeDepth(BinTree T) {
int hl,hr,max; if(T){ hl=TreeDepth(T->lchild); //求左深度 hr=TreeDepth(T->rchild); //求右深度 max=hl>hr? hl:hr; //取左右深度的最大值 NodeNum=NodeNum+1; //求结点数 if(hl==0&&hr==0) leaf=leaf+1; //若左右深度为0,即为叶子。 return(max+1); }
else return(0); }
//====利用\先进先出\(FIFO)队列,按层次遍历二叉树========== void Levelorder(BinTree T) {
int front=0,rear=1;
BinTNode *cq[Max],*p; //定义结点的指针数组cq cq[1]=T; //根入队 while(front!=rear) { front=(front+1)%NodeNum; p=cq[front]; //出队 printf(\ //出队,输出结点的值 if(p->lchild!=NULL){ rear=(rear+1)%NodeNum; cq[rear]=p->lchild; //左子树入队 } if(p->rchild!=NULL){ rear=(rear+1)%NodeNum; cq[rear]=p->rchild; //右子树入队 } } }
//====数叶子节点个数========== int countleaf(BinTree T) { int hl,hr; if(T){ hl=countleaf(T->lchild); hr=countleaf(T->rchild); if(hl==0&&hr==0) //若左右深度为0,即为叶子。 return(1); else return hl+hr; } else return 0; }
//==========主函数================= void main() {
BinTree root; char i; int depth; printf(\
printf(\; Input preorder:\输入完全二叉树的先序序列, // 用#代表虚结点,如ABD###CE##F## root=CreatBinTree(); //创建二叉树,返回根结点
do { //从菜单中选择遍历方式,输入序号。