级本数据结构实验教案

数据结构与算法实验教案授课教师：祁文青适用专业：计算机科学与技术使用班级：11计科2班、11计科（数媒）授课时间：2012年秋季授课学时：16学时使用教材：《数据结构》严蔚敏主编实验指导书：数据结构与算法实验指导书，计算机学院编，2012年版湖北理工学院计算机学院

实验安排表周次日期实验课题学时实验报告次数9实验一线性表的实验2学时10实验一线性表的实验2学时111实验二栈、队列的实现及应用2学时112实验三二叉树的操作及应用2学时13实验三二叉树的操作及应用2学时114实验四图的操作及应用2学时115实验五查找与排序2学时16实验五查找与排序2学时1

实验一线性表的实验一、实验目的及要求1、掌握在TC环境下调试顺序表的基本方法2、掌握顺序表的基本操作，插入、删除、查找、以及有序顺序表的合并等算法的实现。3、掌握用在TC环境下上机调试单链表的基本方法4、掌握单链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现5、进一步掌握循环单链表的插入、删除、查找算法的实现二、实验学时4学时三、实验任务生成一个顺序表并动态地删除任意元素和在任意位置插入元素。将两个有序表合并成一个有序表。3、在带头结点的单链表h中第i个数据元素之前插入一个数据元素。4、将两个有序单链表合并成一个有序单链表。四、实验重点、难点在顺序表中移动元素。在顺序表中找到正确的插入位置。在单链表中寻找到第i-1个结点并用指针p指示。比较两个单链表的节点数据大小。五、操作要点(一)顺序表基本操作的实现[问题描述]当我们要在顺序表的第i个位置上插入一个元素时，必须先将顺序表中第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。[基本要求]要求生成顺序表时，可以键盘上读取元素，用顺序存储结构实现存储。[实现提示]要实现基本操作，可用实现的基本操作，也可设计简单的算法实现。[程序实现]#include<stdio.h>#include<conio.h>typedefintDataType;#definemaxnum20typedefstruct{intdata[maxnum];intlength;}SeqList;/*插入函数*/intinsert(SeqList*L,inti,DataTypex)/*将新结点x插入到顺序表L第i个位置*/{intj;if(i<0||i>(*L).length+1){printf("\ni值不合法!");return0;}if((*L).length>=maxnum-1){printf("\n表满不能插入!");return0;}for(j=(*L).length;j>=i;j--)(*L).data[j+1]=(*L).data[j];(*L).data[i]=x;(*L).length++;return1;}/*删除函数*/intdelete(SeqList*L,inti)/*从顺序L中删除第i个结点*/{intj;if(i<0||i>(*L).length){printf("\n删除位置错误!");return0;}for(j=i+1;j<=(*L).length;j++)(*L).data[j-1]=(*L).data[j];(*L).length--;return1;}/*生成顺序表*/voidcreatlist(SeqList*L){intn,i,j;printf("请输入顺序表L的数据个数：\n");scanf("%d",&n);for(i=0;i<n;i++){printf("data[%d]=",i);scanf("%d",&((*L).data[i]));}(*L).length=n-1;printf("\n");}/*creatlist*//*输出顺序表L*/printout(SeqList*L){inti;for(i=0;i<=(*L).length;i++){printf("data[%d]=",i);printf("%d",(*L).data[i]);}/*printout*/printf("\n");}main(){SeqList*L;charcmd;inti,t,x;clrscr();creatlist(L);do{printf("\ni,I-----插入\n");printf("d,D-----删除\n");printf("q,Q-----退出\n");do{cmd=getchar();}while((cmd!='i')&&(cmd!='I')&&(cmd!='d')&&(cmd!='D')&&(cmd!='q')&&(cmd!='Q'));switch(cmd){case'i':case'I': printf("\nPleaseinputtheDATA:"); scanf("%d",&x); printf("\nWhere?"); scanf("%d",&i); insert(L,i,x); printout(L); break;case'd':case'D': printf("\nWheretoDelete?"); scanf("%d",&i); delete(L,i);printout(L);break;}}while((cmd!='q')&&(cmd!='Q'));}（二）有序顺序表的合并[问题描述]已知顺序表la和lb中的数据元素按非递减有序排列，将la和lb表中的数据元素，合并成为一个新的顺序表lc[基本要求]lc中的数据元素仍按非递减有序排列，并且不破坏la和lb表[程序实现]#include<stdio.h>#definemaxnum20typedefintDataType;typedefstruct{DataTypedata[maxnum];intlength;}SeqList;intMergeQL(SeqListla,SeqListlb,SeqList*lc){inti,j,k;if(la.length+1+lb.length+1>maxnum){printf("\narrayoverflow!");return0;}i=j=k=0;while(i<=la.length&&j<=lb.length){if(la.data[i]<=lb.data[j])lc->data[k++]=la.data[i++];elselc->data[k++]=lb.data[j++];}/*处理剩余部分*/while(i<=la.length)lc->data[k++]=la.data[i++];while(j<=lb.length)lc->data[k++]=lb.data[j++];lc->length=k-1;return1;}main(){SeqListla={{3,4,7,12,15},4};SeqListlb={{2,5,7,15,18,19},5};SeqListlc;inti;if(MergeQL(la,lb,&lc)){printf("\n");for(i=0;i<=lc.length;i++)printf("%4d",lc.data[i]);}}（一）单链表基本操作的实现[问题描述]要在带头结点的单链表h中第i个数据元素之前插入一个数据元素x，首先需要在单链表中寻找到第i-1个结点并用指针p指示，然后申请一个由指针s指示的结点空间，并置x为其数据域值，最后修改第i-1个结点，并使x结点的指针指向第i个结点，要在带头结点的单链表h中删除第i个结点，首先要计数寻找到第i个结点并使指针p指向其前驱第i-1个结点，然后删除第i个结点并释放被删除结点空间。[基本要求]用链式存储结构实现存储[实现提示]链式存储结构不是随机存储结构，即不能直接取到单链表中某个结点，而要从单链表的头结点开始一个一个地计数寻找。[程序实现]#include<stdio.h>#include<malloc.h>typedefcharDataType;typedefstructnode{DataTypedata;/*结点的数据域*/structnode*next;/*结点的指针域*/}ListNode;voidInit_List(ListNode**L){(*L)=(ListNode*)malloc(sizeof(ListNode));/*产生头结点*/(*L)->next=NULL;}intList_Length(ListNode*L){intn=0;ListNode*p=L->next;while(p!=NULL){n++;p=p->next;}returnn;}ListNode*GetNode(ListNode*L,inti){intj;ListNode*p;p=L;j=0;/*从头结点开始扫描*/while(p->next&&j!=i)/*顺指针向后扫描,直到p->next为NULL或i=j为止*/{p=p->next;j++;}if(i==j)returnp;/*找到了第i个结点*/elsereturnNULL;/*当i<0或i>0时,找不到第i个结点*/}voidInsertList(ListNode*L,DataTypex,inti){ListNode*p,*s;p=GetNode(L,i-1);/*寻找第i-1个结点*/if(p==NULL)/*i<1或i>n+1时插入位置i有错*/{printf("positionerror");return;}s=(ListNode*)malloc(sizeof(ListNode));s->data=x;s->next=p->next;p->next=s;}voidDeleteList(ListNode*L,inti){ListNode*p,*r;p=GetNode(L,i-1);/*找到第i-1个结点*/if(p==NULL||p->next==NULL)/*i<1或i>n时,删除位置错*/{printf("positionerror");return;}r=p->next;/*使r指向被删除的结点a*/p->next=r->next;/*将ai从链上删除*/free(r);}/*使用头插法建立带头结点链表算法*/ListNode*CreatListF(void){charch;ListNode*head=(ListNode*)malloc(sizeof(ListNode));/*生成头结点*/ListNode*s;/*工作指针*/head->next=NULL;ch=getchar();/*读入第1个字符*/while(ch!='\n'){s=(ListNode*)malloc(sizeof(ListNode));/*生成新结点*/s->data=ch;/*将读入的数据放入新结点的数据域中*/s->next=head->next;head->next=s;ch=getchar();/*读入下一字符*/}returnhead;}/*使用尾插法建立带头结点链表算法*/ListNode*CreatListR1(void){charch;ListNode*head=(ListNode*)malloc(sizeof(ListNode));/*生成头结点*/ListNode*s,*r;/*工作指针*/r=head;/*尾指针初值也指向头结点*/while((ch=getchar())!='\n'){s=(ListNode*)malloc(sizeof(ListNode));s->data=ch;r->next=s;r=s;}r->next=NULL;/*终端结点的指针域置空,或空表的头结点指针域置空*/returnhead;}/*复制链表A中的内容到表B中*/voidcopy(ListNode*a,ListNode*b){ListNode*pa=a->next;ListNode*u;ListNode*rb=b;while(pa!=NULL){u=(ListNode*)malloc(sizeof(ListNode));u->data=pa->data;rb->next=u;rb=u;pa=pa->next; }rb->next=NULL;}/*输出带头结点的单链表*/voidDisplaySL(ListNode*la,char*comment){ListNode*p;p=la->next;if(p)printf("\n%s\n",comment);while(p) { printf("%4c",p->data); p=p->next; }printf("\n");}/*主函数*/main(){ListNode*la,*lb,*lc,*p;intn,x,i;printf("\n用头插法建立链表la，请输入节点内容:");la=CreatListF();DisplaySL(la,"新生成链la节点内容:");printf("\n链表la的长度:%2d",List_Length(la));printf("\n请输入要插入的元素:");scanf("%c",&x);printf("\n请输入要插入的位置：");scanf("%d",&i);InsertList(la,x,i);DisplaySL(la,"插入后链la节点内容");printf("\n请输入要删除元素的位置：");scanf("%d",&i);DeleteList(la,i);DisplaySL(la,"删除后链la节点内容");printf("\n用尾插法建立链表lb，请输入节点内容:");fflush(stdin);lb=CreatListR1();DisplaySL(lb,"新生成链lb节点内容:");Init_List(&lc);copy(la,lc);DisplaySL(lc,"复制生成的链lc节点内容:");}（二）有序单链表的合并[问题描述]已知单链表la和lb中的数据元素按非递减有序排列，将la和lb中的数据元素,合并为一个新的单链表lc,lc中的数据元素仍按非递减有序排列。[基本要求]不破坏la表和lb表的结构。[程序实现]#include<stdio.h>#include<alloc.h>#defineNULL0typedefintDataType;typedefstructSLNode{DataTypedata;structSLNode*next;}slnodetype;intMergeSL(slnodetype*la,slnodetype*lb,slnodetype**lc);intCreateSL(slnodetype*la,intn);voidDisplaySL(slnodetype*la,char*comment);main(){slnodetype*la,*lb,*lc,*p;intn,m;la=(slnodetype*)malloc(sizeof(slnodetype));la->next=NULL;lb=(slnodetype*)malloc(sizeof(slnodetype));lb->next=NULL;lc=(slnodetype*)malloc(sizeof(slnodetype));lc->next=NULL;printf("\n输入链la节点数:");scanf("%d",&n);printf("\n输入链la节点内容:");CreateSL(la,n);DisplaySL(la,"链la节点内容:");printf("\n输入链lb节点数:");scanf("%d",&m);printf("\n输入链lb节点内容:");CreateSL(lb,m);DisplaySL(lb,"链lb节点内容:");if(MergeSL(la,lb,&lc))DisplaySL(lc,"合成后的链lc:");getchar();}intMergeSL(slnodetype*la,slnodetype*lb,slnodetype**lc){slnodetype*pa,*pb,*pc;lc=(slnodetype*)malloc(sizeof(slnodetype));pa=la->next;pb=lb->next;pc=*lc;while(pa&&pb){pc->next=(slnodetype*)malloc(sizeof(slnodetype));pc=pc->next;if(pa->data<=pb->data){pc->data=pa->data;pa=pa->next;}else{pc->data=pb->data;pb=pb->next;}}while(pa)/*插入la链的剩余段*/{ pc->next=(slnodetype*)malloc(sizeof(slnodetype));pc=pc->next;pc->data=pa->data;pa=pa->next;}/*插入lb链的剩余段*/while(pb){ pc->next=(slnodetype*)malloc(sizeof(slnodetype));pc=pc->next;pc->data=pb->data;pb=pb->next;}/*生成单链表*/intCreateSL(slnodetype*la,intn){inti;slnodetype*p,*q;q=la;for(i=1;i<=n;i++){p=(slnodetype*)malloc(sizeof(slnodetype));scanf("%d",&p->data);q->next=p;q=p;}q->next=NULL;return1;}/*输出单链表*/voidDisplaySL(slnodetype*la,char*comment){slnodetype*p;p=la->next;if(p)printf("\n%s\n",comment);while(p){printf("\n%3d",p->data);p=p->next;}printf("\n");}

（一）约瑟夫环问题[问题描述]设有N个人围坐一圈，现从某个人开始报数，数到M的人出列，接着从出列的下一个人开始重新报数，数到M的人以出列，如此下去，直到所有人都出列为此。试设计确定他们的出列次序序列的程序。[基本要求]选择单向循环链表作为存储结构模拟整个过程，并依次输出列的各人的编号。[实现提示]程序运行之后，首先要求用户指定初始报数的下限值，可以n<=30,此题循环链表可不设头节点，而且必须注意空表和非空表的界限。如n=8,m=4时，若从第一个人，设每个人的编号依次为1，2，3，…开始报数，则得到的出列次序为4，8，5，2，1，3，7，6，如下图所示，内层数字表示人的编号，每个编号外层的数字代表人出列的序号。[程序实现]#include<stdio.h>#include<malloc.h>typedefstructnode{intnum;structnode*next;}linklist;linklist*creat(head,n)/*使n个人围成一圈，并给每个人标识号数*/linklist*head;intn;{linklist*s,*p;inti;s=(linklist*)malloc(sizeof(linklist));head=s;s->num=1;p=s;for(i=2;i<=n;i++){s=(linklist*)malloc(sizeof(linklist));s->num=i;p->next=s;p=s;}p->next=head; return(head);}/*creat*/linklist*select(linklist*head,intm){linklist*p,*q;inti,t;p=head;t=1;q=p;/*q为p的前趋指针*/p=p->next;do{t=t+1;/*报一次数*/if(t%m==0) {printf("%4d",p->num);q->next=p->next;free(p); p=q->next; }else{q=p; p=p->next; }}while(q!=p);head=p;printf("%4d",p->num);return(head);}/*select*/main(){intn,m;linklist*head;printf("\ninputthetotalnumber:n=");scanf("%d",&n);printf("\ninputthenumbertocall:m=");scanf("%d",&m);head=creat(head,n);head=select(head,m);printf("\nthelastoneis:%d",head->num);}/*main*/六、注意事项删除元素或插入元素表的长度要变化。在合并表中当某一个表到表尾了就不用比较了，直接将另一个表的元素复制到总表去即可。3、在第i个节点前删除或插入节点需要用指针来表示第i-1个节点。4、在合并链表时需要设置多个指针变量。5、如果不是要删除的节点则指针后移，否则删除该节点。七、思考题1、编程实现两个循环单链表的合并。

实验二栈、队列的实现及应用一、实验目的及要求1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。2、掌握栈和队列的特点，即先进后出与先进先出的原则。3、掌握栈和队列的基本操作实现方法。二、实验学时2学时三、实验任务实现栈的顺序存储利用栈实现数制转换四、实验重点、难点进栈、出栈栈顶指针都要改变。数制转换结束的判断条件。五、操作要点（一）实现栈的顺序存储#defineMAXSIZE100typedefintElemType;typedefstruct{ElemTypedata[MAXSIZE];inttop;}SeqStack;voidInitStack(SeqStack*s){s->top=0;return1;}intStackEmpty(SeqStack*s){if(s->top==0)return1;elsereturn0;}intStackFull(SeqStack*s){if(s->top==MAXSIZE-1)return1;elsereturn0;}voidPush(SeqStack*s,intx){if(StackFull(s)){printf("thestackisoverflow!\n"); return0; }else{s->data[s->top]=x;s->top++;}}voidDisplay(SeqStack*s){if(s->top==0)printf("thestackisempty!\n");else{while(s->top!=0){printf("%d->",s->data[s->top]); s->top=s->top-1;}}}ElemTypePop(SeqStack*s){if(StackEmpty(s))return0;elsereturns->data[--s->top];}ElemTypeStackTop(SeqStack*s){inti;if(StackEmpty(s))return0;else{i=s->top-1;returns->data[i];}/*返回栈顶元素的值，但不改变栈顶指针*/}main(SeqStack*p){intn,i,k,h,x1,x2,select;printf("createaemptystack!\n");InitStack(p);printf("inputastacklength:\n");scanf("%d",&n);for(i=0;i<n;i++){printf("inputastackvalue:\n");scanf("%d",&k);Push(p,k);}printf("select1:Display()\n");printf("select2:Push()\n");printf("select3:Pop()\n");printf("select4:StackTop()\n");printf("inputayourselect(1-4):\n");scanf("%d",&select);switch(select){case1:{ display(p); break;}case2:{ printf("inputapushavalue:\n"); scanf("%d",&h); Push(p,h); display(p); break;}case3:{ x1=Pop(p); printf("x1->%d\n",x1); display(p); break; }case4:{ x2=StackTop(p); printf("x2->%d",x2); break;}}}（二）利用栈实现数制转换#defineMAXSIZE100typedefintElemType；/*将顺序栈的元素定义为整型*/typedefstruct{ElemTypedata[MAXSIZE];inttop;}SeqStack;voidInitStack(SeqStack*s){s->top=0;return1;}intStackEmpty(SeqStack*s){if(s->top==0)return1;elsereturn0;}intStackFull(SeqStack*s){if(s->top==m-1)return1;elsereturn0;}voidPush(SeqStack*s,intx){if(StackFull(s)){printf("thestackisoverflow!\n"); return0; }else{s->data[s->top]=x;s->top++;}}ElemTypePop(SeqStack*s){ElemTypey;if(StackEmpty(s)){printf("thestackisempty!\n"); return0;}else{y=s->data[s->top]; s->top=s->top-1; returny;}}ElemTypeStackTop(SeqStack*s){if(StackEmpty(s))return0;elsereturns->data[s->top];}voidDec_to_Ocx(intN)/*n是非负的十进制整数，输出等值的八进制数*/{SeqStack*S；/*定义一个顺序栈*/ElemTypex；Init_SeqStack(S)；/*初始化栈*/if(N<0){printf("\nError,Thenumbermustbeover0。")；return；}if(!N)Push(S,0)；while(N)/*自右向左产生八进制的各位数字，并将其进栈*/

{Push(S，N%8)；/*余数入栈*/N=N/8；/*商作为被除数*/}printf("Number%dconvertedtoOCT:",N);while(StackEmpty(S))/*栈非空时退栈输出*/

{x=Pop(S)；printf(“%d”,x)；}printf("\n");}main(){intn;printf("InputanumbertoconverttoOCT:\n");scanf("%d",&n);Dec_to_Ocx(n);}六、注意事项1、进栈、出栈栈顶指针都要改变。2、数制转换余数入栈后商作为被除数。七、思考题1、实现循环队列的顺序存储

实验三二叉树的操作及应用一、实验目的及要求1、进一步掌握指针变量、动态变量的含义。2、掌握二叉树的结构特性，以及各种存储结构的特点和适用范围。3、掌握用指针类型描述、访问和处理二叉树的运算。二、实验学时4学时三、实验任务以二叉链表作存储结构，编写前序、中序、后序及层次顺序遍历二叉树的算法。2、以二叉链表作存储结构，编写计算二叉树深度、所有结点总数、叶子结点数、双孩子结点个数、单孩子结点个数的算法四、实验重点、难点1、前序、中序、后序及层次顺序遍历二叉树的算法。2、计算二叉树深度、所有结点总数、叶子结点数、双孩子结点个数、单孩子结点个数的算法。五、操作要点（一）以二叉链表作存储结构，试编写前序、中序、后序及层次顺序遍历二叉树的算法。#defineM10typedefintDataType;/*元素的数据类型*/typedefstructnode{DataTypedata;structnode*lchild,*rchild;}BitTNode,*BiTree;intfront=0,rear=0;BitTNode*que[10];BitTNode*creat(){BitTNode*t;DataTypex;scanf("%d",&x);if(x==0)t=NULL;else{t=(BitTNode*)malloc(sizeof(BitTNode));t->data=x;t->lchild=creat();t->rchild=creat();}return(t);}/*creat*//*前序遍历二叉树t*/voidpreorder(BiTreet){if(t!=NULL){printf("%4d",t->data);preorder(t->lchild);preorder(t->rchild);}}/*中序遍历二叉树t*/voidinorder(BiTreet){if(t!=NULL){inorder(t->lchild);printf("%4d",t->data);inorder(t->rchild);}}/*后序遍历二叉树t*/voidpostorder(BiTreet){if(t!=NULL){postorder(t->lchild);postorder(t->rchild);printf("%4d",t->data);}}voidenqueue(BitTNode*t){if(front!=(rear+1)%M){rear=(rear+1)%M;que[rear]=t;}}/*enqueue*/BitTNode*delqueue(){if(front==rear)returnNULL;{front=(front+1)%M;return(que[front]);}}/*delqueue*//*按层次遍历二叉树t*/voidlevorder(BiTreet){BitTNode*p;if(t!=NULL){enqueue(t);while(front!=rear){p=delqueue();printf("%4d",p->data);if(p->lchild!=NULL)enqueue(p->lchild);if(p->rchild!=NULL)enqueue(p->rchild);}}}/*levorder*/main(){BitTNode*root;root=creat();printf("\n按先序遍历次序生成的二叉树");printf("\n前序遍历二叉树");preorder(root);printf("\n中序遍历二叉树");inorder(root);printf("\n后序遍历二叉树");postorder(root);printf("\n层次顺序遍历二叉树");levorder(root);}（二）以二叉链表作存储结构，试编写计算二叉树深度、所有结点总数、叶子结点数、双孩子结点个数、单孩子结点个数的算法#include<stdio.h>#defineMaxSize100typedefcharElemType;typedefstructnode{ElemTypedata;structnode*left,*right;}BTree;BTree*createbt(){ BTree*q; structnode1*s[30]; intj,i,x; printf("建立二叉树，输入结点对应的编号和值,编号和值之间用逗号隔开\n\n"); printf("i,x="); scanf("%d,%c",&i,&x); while(i!=0&&x!='$') {q=(BTree*)malloc(sizeof(BTree));/*建立一个新结点q*/ q->data=x;q->left=NULL;q->right=NULL; s[i]=q;/*q新结点地址存入s指针数组中*/ if(i!=1)/*i=1，对应的结点是根结点*/ {j=i/2;/*求双亲结点的编号j*/ if(i%2==0)s[j]->left=q;/*q结点编号为偶数则挂在双亲结点j的左边*/ elses[j]->right=q;/*q结点编号为奇数则挂在双亲结点j的右边*/} printf("i,x="); scanf("%d,%c",&i,&x);} returns[1];/*返回根结点地址*/}voidpreorder(BTree*BT)/*前序遍历二叉树t*/{if(BT!=NULL){printf("%4c",BT->data);preorder(BT->left);preorder(BT->right);}}intBTreeDepth(BTree*BT){intleftdep,rightdep;if(BT==NULL) return(0);else{ leftdep=BTreeDepth(BT->left); rightdep=BTreeDepth(BT->right); if(leftdep>rightdep) return(leftdep+1); else return(rightdep+1);}}intnodecount(BTree*BT){if(BT==NULL) return(0);else return(nodecount(BT->left)+nodecount(BT->right)+1);}intleafcount(BTree*BT){if(BT==NULL) return(0);elseif(BT->left==NULL&&BT->right==NULL) return(1);else return(leafcount(BT->left)+leafcount(BT->right));}intnotleafcount(BTree*BT){if(BT==NULL) return(0);elseif(BT->left==NULL&&BT->right==NULL) return(0);else return(notleafcount(BT->left)+notleafcount(BT->right)+1);}intonesoncount(BTree*BT){if(BT==NULL) return(0);elseif((BT->left==NULL&&BT->right!=NULL)||(BT->left!=NULL&&BT->right==NULL)) return(onesoncount(BT->left)+onesoncount(BT->right)+1);else return(onesoncount(BT->left)+onesoncount(BT->right));}inttwosoncount(BTree*BT){if(BT==NULL) return(0);elseif(BT->left==NULL||BT->right==NULL) return(twosoncount(BT->left)+twosoncount(BT->right));elseif(BT->left!=NULL&&BT->right!=NULL) return(twosoncount(BT->left)+twosoncount(BT->right)+1);}main(){BTree*B;B=creatree();printf("\n按先序遍历次序生成的二叉树");preorder(B);printf("\n二叉树深度:%d\n",BTreeDepth(B));printf("总结点个数:%d\n",nodecount(B));printf("叶子结点个数:%d\n",leafcount(B));printf("非叶子结点个数:%d\n",notleafcount(B));printf("具有双孩子结点个数:%d\n",twosoncount(B));printf("具有单孩子结点个数:%d\n",onesoncount(B));}六、注意事项遍历的思想。七、思考题1、用非遍历算法如何实现？

实验四图的操作及应用一、实验目的及要求1、熟练掌握图的邻接矩阵和邻接表的存储方式；2、实现图的一些基本运算，特别是深度遍历和广度遍历；3、掌握以图为基础的一些常用算法，如最小生成树、拓扑排序、最短路径等。二、实验学时2学时三、实验任务1、定义邻接矩阵存储结构或邻接表存储结构。2、按照建立一个带权有向图的操作需要，编写在邻接矩阵或邻接表存储结构下，带权有向图基本操作的实现函数（如初始化图、在图中插入一个结点、在图中插入一条边、在图中寻找序号为v的结点的第一个邻接结点、在图中寻找序号为v1结点的邻接结点v2的下一个邻接结点、图的深度优先遍历、图的广度优先遍历等）。3、设计一个测试主函数，首先创建一个图（有n个结点和e条边），然后打印图的n个结点信息和e条边信息，最后分别打印出图的深度优先遍历和广度优先遍历的结点信息序列。四、实验重点、难点1、图的抽象数据结构的创建。2、图的遍历算法。五、操作要点1、抽象数据结构typedefintstatus;typedefstructArcNode{intadjvex;structArcNode*nextarc;ArctexTypeinfo;}ArcNode;typedefcharVertexType[10];statusVisited[MAC_VERTEX_NUM];typedefstructVNode{VertexTypedata;ArcNode*firstarc;}VNode,AdjList[MAC_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;intkind;}Graph;2、算法基本操作的说明及分析(1)以邻接表的形式建立图的算法voidCreateMGraph(Mgraph*G){inti,j,k;printf("Enterthenumberofverticesandedges：：n");scanf("%d%d",&G->n,&G->e);getchar();printf("Enter%dverticesn",G->n);for(i=0;i<G->n;i++)G->vexs[i]=getchar();for(i=0;i<G->n;i++)for(j=0;j<G->n;j++)G->edges[i][j]=0;printf("Enterthe%dinthematrixelements:n",2*(G->e));for(k=0;k<2*(G->e);k++){scanf("%d%d",&i,&j);G->edges[i][j]=1;}}(2)广度优先遍历算法：voidBFS(MgraphG,inti){intu,j;LinkQueueQ;InitQueue(&Q);printf("%c",G.vexs[i]);visited2[i]=1;EnQueue(&Q,i);while(!QueueEmpty(&Q)){i=DeQueue(&Q);for(j=0;j<G.n;j++)if(G.edges[i][j]==1&&!visited2[j]){printf("%c",G.vexs[j]);visited2[j]=1;EnQueue(&Q,j);}}}(3)深度优先遍历算法实现。voidDFSM(Mgraph*G,inti){intj;printf("%c",G->vexs[i]);visited1[i]=1;for(j=0;j<G->n;j++){if(G->edges[i][j]==1&&!visited1[j])DFSM(G,j);}}(4)总的算法描述的程序代码：#include<stdio.h>#include<stdlib.h>#include<malloc.h>intvisited1[20]={0},visited2[20]={0};typedefstruct{charvexs[20];intedges[20][20];intn,e;}Mgraph;typedefstructQNode{intdata;structQNode*next;intQueusize;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;voidInitQueue(LinkQueue*Q){Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));Q->front->next=NULL;}voidEnQueue(LinkQueue*Q,inte){QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode));p->data=e;p->next=NULL;Q->rear->next=p;Q->rear=p;}intDeQueue(LinkQueue*Q){inte;QueuePtrp;p=Q->front->next;e=p->data;Q->front->next=p->next;if(Q->rear==p)Q->rear=Q->front;free(p);return(e);}intQueueEmpty(LinkQueue*Q){if(Q->front==Q->rear)return1;elsereturn0;}voidCreateMGraph(Mgraph*G){inti,j,k;printf("Enterthenumberofverticesandedges：：n");scanf("%d%d",&G->n,&G->e);getchar();printf("Enter%dverticesn",G->n);for(i=0;i<G->n;i++)G->vexs[i]=getchar();for(i=0;i<G->n;i++)for(j=0;j<G->n;j++)G->edges[i][j]=0;printf("Enterthe%dinthematrixelements:n",2*(G->e));for(k=0;k<2*(G->e);k++){scanf("%d%d",&i,&j);G->edges[i][j]=1;}}voidBFS(MgraphG,inti){intu,j;LinkQueueQ;InitQueue(&Q);printf("%c",G.vexs[i]);visited2[i]=1;EnQueue(&Q,i);while(!QueueEmpty(&Q)){i=DeQueue(&Q);for(j=0;j<G.n;j++)if(G.edges[i][j]==1&&!visited2[j]){printf("%c",G.vexs[j]);visited2[j]=1;EnQueue(&Q,j);}}}voidDFSM(Mgraph*G,inti){intj;printf("%c",G->vexs[i]);visited1[i]=1;for(j=0;j<G->n;j++){if(G->edges[i][j]==1&&!visited1[j])DFSM(G,j);}}intmain(void){MgraphG;clrscr();CreateMGraph(&G);printf("BFS:n");BFS(G,0);printf("n");printf("DFS:n");DFSM(&G,0);}实验五查找与排序一、实验目的及要求1、掌握查找的不同方法，并能用高级语言实现查找算法。2、熟练掌握顺序表的查找方法和有序顺序表的折半查找算法以及静态查找树的构造方法和查找算法。3、掌握二叉排序树的生成、插入、删除、输出运算。4、掌握常用的排序方法，并能用高级语言实现排序算法。5、深刻理解排序的定义和各种排序方法的特点，并能加以灵活运用。6、了解各种方法的排序过程及依据的原则，并掌握各种排序方法的时间复杂度的分析方法。二、实验学时4学时三、实验任务1、顺序表的顺序查找有序顺序表的二分查找的递归算法3、直接插入排序、简单交换排序、快速排序、简单选择排序、堆排序、二路归并中的"一趟归并"算法。四、实验重点、难点1、设置一个监视哨。2、mid的变化。3、快速排序4、二路归并中的"一趟归并"算法五、操作要点（一）顺序表的顺序查找#include<stdio.h>#defineKEYTYPEint#defineMAXSIZE100typedefstruct{KEYTYPEkey;}SSELEMENT;typedefstruct{SSELEMENTr[MAXSIZE];intlen;}SSTABLE;intseq_search(KEYTYPEk,SSTABLE*st){/*顺序表上查找元素*/intj;j=st->len;/*顺序表元素个数*/st->r[0].key=k;/*st->r[0]单元作为监视哨*/while(st->r[j].key!=k)j--;/*顺序表从后向前查找*/returnj;/*j=0,找不到；j<>0找到*/}main(){SSTABLEa;inti,j,k;printf("请输入顺序表元素(整型量)，用空格分开，-99为结束标志：");j=0;k=1;i=0;scanf("%d",&i);while(i!=-99){j++;a.r[k].key=i;k++;scanf("%d",&i);}/*输入顺序表元素*/a.len=j;printf("\n顺序表元素列表显示：");for(i=1;i<=a.len;i++)printf("%d",a.r[i].key);printf("\n");printf("\n输入待查元素关键字:");scanf("%d",&i);k=seq_search(i,&a);if(k==0)printf("表中待查元素不存在\n\n");elseprintf("表中待查元素存在,为第%d个元素\n"，k);}（二）有序顺序表的二分查找的递归算法#include<stdio.h>#defineKEYTYPEint#defineMAXSIZE100typedefstruct{KEYTYPEkey;}SSELEMENT;typedefstruct{SSELEMENTr[MAXSIZE];intlen;}SSTABLE;intsearch_bin(KEYTYPEk,intlow,inthigh){/*有序表上二分法查找,递归算法*/intmid;mid=-1;if(low<=high)/*low表示当前表中第1个元素所在下标*//*high表示当前表中最后一个元素所在下标*/{mid=(low+high)/2;/*mid表示当前表中中间一个元素所在下标*/if(a.r[mid].key<k)mid=search_bin(k,mid+1,high);/*二分法递归查找*/elseif(a.r[mid].key>k)mid=search_bin(k,low,high-1);}returnmid;/*mid=-1查找不成功；mid!=-1查找成功*/}main(){SSTABLEa;inti,j,k;printf("请输入有序表元素，元素为整型量（从小到大输入），用空格分开，-99为结束标志：");j=0;k=1;i=0;scanf("%d",&i);while(i!=-99){j++;a.r[k].key=i;k++;scanf("%d",&i);}/*输入有序表元素*/a.len=j;printf("\n有序表元素列表显示：");for(i=1;i<=a.len;i++)printf("%d",a.r[i]);printf("\n");printf("\n输入待查元素关键字:");scanf("%d",&i);k=search_bin(i,1,a.len);if(k==-1)printf("表中待查元素不存在\n\n");elseprintf("表中待查元素存在,为第%d个元素\n"，k);}1、排序综合练习#include<stdio.h>#defineKEYTYPEint#defineMAXSIZE100intcreateList(RECNODE*r){intj,k;printf("\n\n输入待排序数据(整数，以空格隔开，0结束):");k=0;scanf("%d",&j);while(j!=0){k++;r[k].key=j;scanf("%d",&j);}returnk;}frontdisplayList(RECNODE*r,intn){inti;printf("\n排序前:");for(i=0;i<n;i++)printf("%d",r[i+1].key);printf("\n\n");}reardisplayList(RECNODE*r,intn){inti;printf("\n\n排序后:");for(i=0;i<n;i++)printf("%d",r[i+1].key);printf("\n\n");}voidinsertsort(RECNODE*r,intn){/*直接插入排序*/ inti,j; for(i=2;i<=n;i++) {r[0]=r[i];j=i-1;/*r[0]是监视哨，j表示当前已排好序列的长度*/ while(r[0].key<r[j].key)/*确定插入位置*/ {r[j+1]=r[j];j--;} r[j+1]=r[0];/*元素插入*/ }}voidbublesort(RECNODE*r,intn){/*简单交换排序:冒泡排序*/ inti,j; RECNODEtemp; for(i=1;i<n;i++) for(j=n-1;j>=i;j--) if(r[j+1].key<r[j].key) {temp=r[j+1];r[j+1]=r[j];r[j]=temp;}}intpartition(RECNODE*r,int*low,int*high){/*一趟快速排序,返回i,产生了两个独立的待排子序列*/ inti,j; RECNODE temp; i=*low;j=*high; temp=r[i];/*枢轴记录保存在temp变量中*/ do{while((r[j].key>=temp.key)&&(i<j))j--;/*j指针记录和枢轴记录比较*/ if(i<j){r[i]=r[j];i++;} while((r[i].key<=temp.key)&&(i<j))i++;/*i指针记录和枢轴记录比较*/ if(i<j){r[j]=r[i];j--;}}while(i!=j); r[i]=temp;/*枢轴记录的排序位置确定在i*/ returni;}voidquicksort(RECNODE*r,intstart,intend){/*快速排序*/ inti; if(start<end) {i=partition(r,&start,&end);/*一趟快速排序,返回i,产生了两个独立的待排子序列*/ quicksort(r,start,i-1);/*对两个独立的待排子序列分别递归调用快速排序算法*/ quicksort(r,i+1,end);}}voidselesort(RECNODE*r,intn){/*简单选择排序*/ inti,j,k; RECNODEtemp; for(i=1;i<n;i++) {k=i;/*k:最小关键字的初始位置*/ for(j=i+1;j<=n;j++) if(r[j].key<r[k].key) k=j;/*k:跟踪记录当前最小关键字的位置*/ if(k!=i)/*最小关键字元素和待排序列的第一个元素交换*/ {temp=r[i];r[i]=r[k];r[k]=temp;} }}voidsift(RECNODE*r,inti,intm){/*i是根结点编号,m是以i结点为根的子树中最后一个结点的编号*/ intj; RECNODEtemp; temp=r[i]; j=2*i;/*j为i根结点的左孩子*/ while(j<=m) {if(j<m&&(r[j].key<r[j+1].key)) j++;/*当i结点有左右孩子时,j取关键字大的孩子结点编号*/ if(temp.key<r[j].key)/*按堆定义调整,并向下一层筛选调整*/ {r[i]=r[j];i=j;j=2*i;} elsebreak;/*筛选调整完成,跳出循环*/ } r[i]=temp;}voidheapsort(RECNODE*r,intn){/*堆排序:n为r表中记录数,从r[1]开始放起*/ inti; RECNODEtemp; for(i=n/2;i>=1;i--) sift(r,i,n);/*将无序序列建