还剩34页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
数据结构实验教案授课教师许四平适用专业信息与计算科学使用班级13信计
1、2授课时间2015年秋季授课学时14学时使用教材《数据结构》严蔚敏主编实验指导书数据结构实验指导书,数理学院编,2012年版湖北理工学院数理学院实验安排表周次日期实验课题学时实验报告次数
43.24实验一 线性表的顺序存储实验(验证性)2学时
143.25实验一 线性表的顺序存储实验(验证性)2学时
153.31实验二 单链表实验(验证性)2学时
154.1实验二 单链表实验(验证性)2学时
164.7实验三栈、队列(验证性)3学时
164.8实验三栈、队列(验证性)3学时
1105.5实验四树与二叉树(验证性)4学时
1105.6实验四树与二叉树(验证性)4学时
1135.26实验五查找(验证性)3学时
1135.27实验五查找(验证性)3学时1数据结构设计性实验项目
1.线性表的合并已知线性表La和Lb的元素按值非递减排列归并La和Lb得到新的线性表Lc,Lc的元素也按值非递减排列分别采用顺序存储结构和链式结构来实现
2.线性表的逆置设有一个线性表(e0e1…en-2en-1),请编写一个函数将这个线性表原地逆置,即将线性表内容置换为(en-1en-2…e1e0)线性表中的数据可以为整数、字符或字符串,试分别采用顺序存储结构和链式结构来实现
3.约瑟夫环的实现设有n个人围坐一圈,用整数序列123……n表示顺序围坐在圆桌周围的人,现从某个位置s上的人开始报数,数到m的人出列,接着从出列的下一个人又从1开始重新报数,数到m的人出列,如此下去,直到所有人都出列为此试设计确定他们的出列次序序列的程序如n=8m=4s=1时,设每个人的编号依次为1,2,3,…开始报数,则得到的出列次序为4,8,5,2,1,3,7,6检查程序的正确性和健壮性1采用数组表示作为求解过程中使用的数据结构2采用单向循环链表作为存储结构模拟整个过程,循环链表可不设头节点必须注意空表和非空表的界限
4.数制转换利用顺序栈和链栈实现数制转换
5.二叉树的遍历分别以顺序存储结构和二叉链表作存储结构,试编写前序、中序、后序及层次顺序遍历二叉树的算法
6.赫夫曼树与赫夫曼编码已知某系统在通信联络中只可能出现8种字符abcdefgh,其概率分别为{
0.05,
0.29,
0.07,
0.08,
0.14,
0.23,
0.03,
0.11},试设计Huffman编码,并计算其平均码长1初始化从键盘读入8个字符,以及它们的权值,建立Huffman树2编码根据建立的Huffman树,求每个字符的Huffman编码对给定的待编码字符序列进行编码3译码利用已经建立好的Huffman树,对上面的编码结果译码译码的过程是分解电文中的字符串,从根结点出发,按字符’0’和’1’确定找左孩子或右孩子,直至叶结点,便求得该子串相应的字符4打印 Huffman树
7.学生成绩管理查询系统每个学生的数据信息有准考证号(主关键字)、姓名、语文、英语、数学、和总分等数据项,所有学生的信息构成一个学生成绩表假设准考证号的头两位表示地区编号请设计一个管理系统达到如下基本要求
(1)初始化建立一个学生成绩表,输入准考证号、姓名、语文、英语、数学,然后计算每个学生的总分,存入相应的数据项;注意分析数据对象和它们之间的关系,并以合适的方式进行组织(可选择无序的顺序表、有序的顺序表或索引顺序表来进行存储表示);
(2)查找综合应用基本查找算法完成数据的基本查询工作,并输出查询的结果;
(3)输出有选择性地输出满足一定条件的数据记录,如输出地区编号为01,并且总分在550分以上的学生的信息;
(4)计算计算在等概率情况下该查找表的平均查找长度
8.排序编制程序让机器随机产生2000个整数,放入一个数组中;对此2000个随机数序列分别用冒泡排序、快速排序、希尔排序和堆排序方法进行排序,并比较它们的运行时间注意每
三、四个同学组成一个小组每个实验中的题目,可分别由不同的同学完成其它题目可以相互交流,以利于互相提高数据结构验证性实验项目实验一线性表的顺序存储
一、实验目的及要求
1、掌握在TC环境下调试顺序表的基本方法
2、掌握顺序表的基本操作,插入、删除、查找、以及有序顺序表的合并等算法的实现
二、实验学时2学时
三、实验任务
1、生成一个顺序表并动态地删除任意元素和在任意位置插入元素
2、将两个有序表合并成一个有序表
四、实验重点、难点
1、在顺序表中移动元素
2、在顺序表中找到正确的插入位置
五、操作要点一顺序表基本操作的实现[问题描述]当我们要在顺序表的第i个位置上插入一个元素时,必须先将顺序表中第i个元素之后的所有元素依次后移一个位置,以便腾空一个位置,再把新元素插入到该位置若是欲删除第i个元素时,也必须把第i个元素之后的所有元素前移一个位置[基本要求]要求生成顺序表时,可以键盘上读取元素,用顺序存储结构实现存储[实现提示]要实现基本操作,可用实现的基本操作,也可设计简单的算法实现[程序实现]#includestdio.h#includeconio.htypedefintDataType;#definemaxnum20typedefstruct{intdata[maxnum];intlength;}SeqList;/*插入函数*/intinsertSeqList*LintiDataTypex/*将新结点x插入到顺序表L第i个位置*/{intj;ifi0||i*L.length+1{printf\ni值不合法!;return0;}if*L.length=maxnum-1{printf\n表满不能插入!;return0;}forj=*L.length;j=i;j--*L.data[j+1]=*L.data[j];*L.data[i]=x;*L.length++;return1;}/*删除函数*/intdeleteSeqList*Linti/*从顺序L中删除第i个结点*/{intj;ifi0||i*L.length{printf\n删除位置错误!;return0;}forj=i+1;j=*L.length;j++*L.data[j-1]=*L.data[j];*L.length--;return1;}/*生成顺序表*/voidcreatlistSeqList*L{intnij;printf请输入顺序表L的数据个数\n;scanf%dn;fori=0;in;i++{printfdata[%d]=i;scanf%d*L.data[i];}*L.length=n-1;printf\n;}/*creatlist*//*输出顺序表L*/printoutSeqList*L{inti;fori=0;i=*L.length;i++{printfdata[%d]=i;printf%d*L.data[i];}/*printout*/printf\n;}main{SeqList*L;charcmd;intitx;clrscr;creatlistL;do{printf\niI-----插入\n;printfdD-----删除\n;printfqQ-----退出\n;do{cmd=getchar;}whilecmd!=icmd!=Icmd!=dcmd!=Dcmd!=qcmd!=Q;switchcmd{casei:caseI:printf\nPleaseinputtheDATA:;scanf%dx;printf\nWhere;scanf%di;insertLix;printoutL;break;cased:caseD:printf\nWheretoDelete;scanf%di;deleteLi;printoutL;break;}}whilecmd!=qcmd!=Q;}
(二)有序顺序表的合并[问题描述]已知顺序表la和lb中的数据元素按非递减有序排列,将la和lb表中的数据元素,合并成为一个新的顺序表lc[基本要求]lc中的数据元素仍按非递减有序排列,并且不破坏la和lb表[程序实现]#includestdio.h#includestdlib.h#defineOK1#defineERROR0/*定义ElemType为int或别的自定义类型*/typedefintElemType;/*链式存储类型*/typedefstructLNode{ElemTypedata;structLNode*next;}LNode*LinkList;/*单链表的建立头插法*/voidCreateList_LLinkListLintn//CreateList_Lfunction{//ToCreatreaLinkListLwithHeadNodeinti;LNode*p;L=LinkListmallocsizeofLNode;L-next=NULL;printfPleaseinputthedataforLinkListNodes:\n;fori=n;i0;--i{p=LinkListmallocsizeofLNode;scanf%dp-data;//ReverseorderinputingforCreatingaLinkListp-next=L-next;L-next=p;}//endofforifnprintfSuccesstoCreateaLinkList!\n;elseprintfANULLLinkListhavebeencreated!\n;}//endofCreateListfunctionvoidMergeList_LLinkListLaLinkListLbLinkListLc{LinkListpapbpc;pa=La-next;pb=Lb-next;Lc=pc=La;whilepapb{ifpa-data=pb-data{pc-next=pa;pc=pa;pa=pa-next;}else{pc-next=pb;pc=pb;pb=pb-next;}}pc-next=papa:pb;freeLb;}voidmain{LinkListLaLbLcp;intn;printf请输入La的长度n:;scanf%dn;CreateList_LLan;printf输出La的内容;p=La-next;whilep{printf%d-p-data;p=p-next;}printf\n;printf请输入Lb的长度n:;scanf%dn;CreateList_LLbn;printf输出Lb的内容;p=Lb-next;whilep{printf%d-p-data;p=p-next;}printf\n;MergeList_LLaLbLc;printf输出Lc的内容;p=Lc-next;whilep{printf%d-p-data;p=p-next;}printf\n;}
六、注意事项
1、删除元素或插入元素表的长度要变化
2、在合并表中当某一个表到表尾了就不用比较了,直接将另一个表的元素复制到总表去即可实验二单链表
一、实验目的及要求
1、掌握用在TC环境下上机调试单链表的基本方法
2、掌握单链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现
3、进一步掌握循环单链表的插入、删除、查找算法的实现
二、实验学时2学时
三、实验任务
1、在带头结点的单链表h中第i个数据元素之前插入一个数据元素
2、将两个有序单链表合并成一个有序单链表
3、生成一个循环单链表
4、在循环单链表中删除一个节点
四、实验重点、难点
1、在单链表中寻找到第i-1个结点并用指针p指示
2、比较两个单链表的节点数据大小
3、循环单链表中只有一个节点的判断条件
4、在循环单链表中删除一个节点
五、操作要点
(一)单链表基本操作的实现
1、实现栈的顺序存储和链式存储#includestdio.h#includestdlib.h#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineMAXQSIZE100#defineOK1#defineERROR0/*定义SElemType为int或别的自定义类型*/typedefintSElemType;/*链式栈的存储类型*/typedefstructSNode{SElemTypedata;structSNode*next;}SNode*LinkStack;/*取链式栈顶元素*/intGeTop_LLinkStacktopSElemTypee{if!top-next{printfError!ItsanemptyLinkStack!\n;returnERROR;}else{e=top-next-data;returnOK;}}/*将元素压入链式栈*/intPush_LinkStacktopSElemTypee{SNode*q;q=LinkStackmallocsizeofSNode;q-data=e;q-next=top-next;top-next=q;returnOK;}/*将元素弹出链式栈*/intPop_LLinkStacktopSElemTypee{SNode*q;e=top-next-data;q=top-next;top-next=q-next;freeq;returnOK;}/*定义SElemType为int或别的自定义类型*/typedefintSElemType;/*顺序栈的存储类型*/typedefstruct//definestructureSqStack{SElemType*base;SElemType*top;intstacksize;}SqStack;/*构造空顺序栈*/intInitStackSqStackS//InitStacksub-function{S.base=SElemType*mallocSTACK_INIT_SIZE*sizeofSElemType;if!S.base{printfAllocatespacefailure!\n;returnERROR;}S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}//InitStackend/*取顺序栈顶元素*/intGetTopSqStackSSElemTypee//GetTopsub-function{ifS.top==S.base{printfItsaemptySqStack!\n;//ifemptySqStackreturnERROR;}e=*S.top-1;returnOK;}//GetTopend/*将元素压入顺序栈*/intPushSqStackSSElemTypee//Pushsub-function{*S.top++=e;returnOK;}//Pushend/*将元素弹出顺序栈*/intPopSqStackSSElemTypee//Popsub-function{e=*--S.top;returnOK;}//Popendvoidmain{intij;SqStacks;LinkStacks1;SElemTypee;InitStacks;s1=LinkStackmallocsizeofSNode;s1-next=NULL;printf顺序栈的元素\n;fori=1;i=8;i++{scanf%de;Pushse;}printf顺序栈出栈\n;fori=1;i=8;i++{Popse;printf%de;}printf\n;printf链式栈的元素\n;forj=1;j=8;j++{scanf%de;Push_s1e;}printf链式栈出栈\n;whileNULL!=s1-next{Pop_Ls1e;printf%de;}printf\n;}
2、利用顺序栈或链栈实现数制转换#includestdio.h#includestdlib.h#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineMAXQSIZE100#defineOK1#defineERROR0/*定义SElemType为int或别的自定义类型*/typedefintSElemType;/*顺序栈的存储类型*/typedefstruct//definestructureSqStack{SElemType*base;SElemType*top;intstacksize;}SqStack;/*构造空顺序栈*/intInitStackSqStackS//InitStacksub-function{S.base=SElemType*mallocSTACK_INIT_SIZE*sizeofSElemType;if!S.base{printfAllocatespacefailure!\n;returnERROR;}S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}//InitStackendintStackEmptySqStackS{ifS.top==S.basereturnOK;elsereturnERROR;}/*取顺序栈顶元素*/intGetTopSqStackSSElemTypee//GetTopsub-function{ifS.top==S.base{printfItsaemptySqStack!\n;//ifemptySqStackreturnERROR;}e=*S.top-1;returnOK;}//GetTopend/*将元素压入顺序栈*/intPushSqStackSSElemTypee//Pushsub-function{*S.top++=e;returnOK;}//Pushend/*将元素弹出顺序栈*/intPopSqStackSSElemTypee//Popsub-function{e=*--S.top;returnOK;}//Popend/*利用顺序栈实现对于输入的任意一个非负十进制整数,输出与其等值的八进制数*/voidConversion{SqStackS;SElemTypeNe;InitStackS;scanf%uN;whileN{PushSN%8;N=N/8;}printfConversedtoOct.number=;while!StackEmptyS{PopSe;printf%de;}printf\n;}voidmain{Conversion;}
3、实现循环队列的存储和链队列的基本操作#includestdio.h#includestdlib.h#defineOK1#defineERROR0typedefintQElemType;/*链队列的存储类型*/typedefstructQNode//definestructureQNode{QElemTypedata;structQNode*next;}QNode*QueuePtr;typedefstructLinkQueue//definestructureLinkQueue{QueuePtrfront;QueuePtrrear;}LinkQueue;/*构造空链式队列*/intInitQueueLinkQueueQ//InitQueuesub-function{Q.front=Q.rear=QueuePtrmallocsizeofQNode;if!Q.front{printfOverflow!\n;returnERROR;}Q.front-next=NULL;returnOK;}//InitQueueend/*销毁链式队列*/intDestroyQueueLinkQueueQ//DestroyQueuesub-function{whileQ.front{Q.rear=Q.front-next;freeQ.front;Q.front=Q.rear;}returnOK;}//DestroyQueueend/*在链式队列尾插入新元素*/intEnQueueLinkQueueQQElemTypee//EnQueuesub-function{QNode*p;p=QueuePtrmallocsizeofQNode;if!p{printfOverflow!\n;returnERROR;}p-data=e;p-next=NULL;ifQ.front==NULL{Q.front=Q.rear=p;returnOK;}Q.rear-next=p;Q.rear=p;returnOK;}//EnQueueend/*在链式队列头删除旧元素*/intDeQueueLinkQueueQQElemTypee//DeQueuesub-function{ifQ.front==Q.rear{printfIfitwasdeleteditsempty!\n;returnERROR;}QNode*p;p=Q.front-next;e=p-data;Q.front-next=p-next;freep;returnOK;}//DeQueueendvoidmain{LinkQueueL;intine;if!InitQueueLexit0;printf请输入要写入队列的元素的个数;scanf%dn;printf请输入要写入队列的元素;fori=0;in;i++{scanf%de;ifEnQueueLebreak;}DeQueueLe;printf删除的元素为%d\ne;ifDestroyQueueLprintf销毁队列成功\n;}
六、注意事项
1、在第i个节点前删除或插入节点需要用指针来表示第i-1个节点
2、在合并链表时需要设置多个指针变量
3、如果不是要删除的节点则指针后移,否则删除该节点
七、思考题
1、编程实现两个循环单链表的合并实验三栈、队列
一、实验目的及要求
1、掌握栈和队列的顺序存储结构和链式存储结构,以便在实际背景下灵活运用
2、掌握栈和队列的特点,即先进后出与先进先出的原则
3、掌握栈和队列的基本操作实现方法
二、实验学时3学时
三、实验任务
1.实现栈的顺序存储
2.利用栈实现数制转换
四、实验重点、难点
1.进栈、出栈栈顶指针都要改变
2.数制转换结束的判断条件
五、操作要点
(一)实现栈的顺序存储#defineMAXSIZE100typedefintElemType;typedefstruct{ElemTypedata[MAXSIZE];inttop;}SeqStack;voidInitStackSeqStack*s{s-top=0;return1;}intStackEmptySeqStack*s{ifs-top==0return1;elsereturn0;}intStackFullSeqStack*s{ifs-top==MAXSIZE-1return1;elsereturn0;}voidPushSeqStack*sintx{ifStackFulls{printfthestackisoverflow!\n;return0;}else{s-data[s-top]=x;s-top++;}}voidDisplaySeqStack*s{ifs-top==0printfthestackisempty!\n;else{whiles-top!=0{printf%d-s-data[s-top];s-top=s-top-1;}}}ElemTypePopSeqStack*s{ifStackEmptysreturn0;elsereturns-data[--s-top];}ElemTypeStackTopSeqStack*s{inti;ifStackEmptysreturn0;else{i=s-top-1;returns-data[i];}/*返回栈顶元素的值,但不改变栈顶指针*/}mainSeqStack*p{intnikhx1x2select;printfcreateaemptystack!\n;InitStackp;printfinputastacklength:\n;scanf%dn;fori=0;in;i++{printfinputastackvalue:\n;scanf%dk;Pushpk;}printfselect1:Display\n;printfselect2:Push\n;printfselect3:Pop\n;printfselect4:StackTop\n;printfinputayourselect1-4:\n;scanf%dselect;switchselect{case1:{Displayp;break;}case2:{printfinputapushavalue:\n;scanf%dh;Pushph;Displayp;break;}case3:{x1=Popp;printfx1-%d\nx1;Displayp;break;}case4:{x2=StackTopp;printfx2-%dx2;break;}}}
(二)利用栈实现数制转换#defineMAXSIZE100typedefintElemType;/*将顺序栈的元素定义为整型*/typedefstruct{ElemTypedata[MAXSIZE];inttop;}SeqStack;voidInitStackSeqStack*s{s-top=0;return1;}intStackEmptySeqStack*s{ifs-top==0return1;elsereturn0;}intStackFullSeqStack*s{ifs-top==m-1return1;elsereturn0;}voidPushSeqStack*sintx{ifStackFulls{printfthestackisoverflow!\n;return0;}else{s-data[s-top]=x;s-top++;}}ElemTypePopSeqStack*s{ElemTypey;ifStackEmptys{printfthestackisempty!\n;return0;}else{y=s-data[s-top];s-top=s-top-1;returny;}}ElemTypeStackTopSeqStack*s{ifStackEmptysreturn0;elsereturns-data[s-top];}voidDec_to_OcxintN/*n是非负的十进制整数,输出等值的八进制数*/{SeqStack*S;/*定义一个顺序栈*/ElemTypex;Init_SeqStackS;/*初始化栈*/ifN0{printf\nErrorThenumbermustbeover0;return;}if!NPushS0;whileN/*自右向左产生八进制的各位数字,并将其进栈*/{PushS,N%8;/*余数入栈*/N=N/8;/*商作为被除数*/}printfNumber%dconvertedtoOCT:N;whileStackEmptyS/*栈非空时退栈输出*/{x=PopS;printf“%d”x;}printf\n;}main{intn;printfInputanumbertoconverttoOCT:\n;scanf%dn;Dec_to_Ocxn;}
六、注意事项
1、进栈、出栈栈顶指针都要改变
2、数制转换余数入栈后商作为被除数
七、思考题
1、实现循环队列的顺序存储实验四树与二叉树
一、实验目的及要求
1、进一步掌握指针变量、动态变量的含义
2、掌握二叉树的结构特性,以及各种存储结构的特点和适用范围
3、掌握用指针类型描述、访问和处理二叉树的运算
二、实验学时4学时
三、实验任务
1、以二叉链表作存储结构,编写前序、中序、后序及层次顺序遍历二叉树的算法
2、以二叉链表作存储结构,编写计算二叉树深度、所有结点总数、叶子结点数、双孩子结点个数、单孩子结点个数的算法
四、实验重点、难点
1、前序、中序、后序及层次顺序遍历二叉树的算法
2、计算二叉树深度、所有结点总数、叶子结点数、双孩子结点个数、单孩子结点个数的算法
五、操作要点
1、分别以顺序存储结构和二叉链表作存储结构,试编程实现前序、中序、后序及层次顺序遍历二叉树的算法顺序存储结构程序代码#includestdio.h#includeiostream.h#defineOK1#defineERROR0#defineMAX_TREE_SIZE100typedefcharTElemType;typedefTElemTypeSqBiTree[MAX_TREE_SIZE];intCreateSqBiTreebtintn//层序创建二叉树的各个节点元素{cout*表示结束创建,/表示空节点endl;TElemTypec;inti=0;cout请按层依次创建各个节点:;cinc;whilec!=*{bt[++i]=c;cinc;}n=i;cout二叉树创建完毕!endl;returnOK;}intLevelOrderTraverseSqBiTreebtintn//层序遍历{inti;fori=1;i=n;i++{ifbt[i]==/continue;elseifi==ncoutbt[i];elsecoutbt[i]-;}coutendl;returnOK;}intPreOrederTraverseSqBiTreebtintiintn//先序遍历{ifi=nifbt[i]!=/coutbt[i]-;if2*i=nPreOrederTraversebt2*in;if2*i+1=nPreOrederTraversebt2*i+1n;returnOK;}intInOrederTraverseSqBiTreebtintiintn//中序遍历{if2*i=nInOrederTraversebt2*in;ifi=nifbt[i]!=/i!=ncoutbt[i]-;elseifbt[i]!=/i==ncoutbt[i];if2*i+1=nInOrederTraversebt2*i+1n;returnOK;}intPosOrederTraverseSqBiTreebtintiintn//后序遍历{if2*i=nPosOrederTraversebt2*in;if2*i+1=nPosOrederTraversebt2*i+1n;ifi=n{ifbt[i]!=/i!=1coutbt[i]-;ifi==1coutbt[i];}returnOK;}voidmain{cout顺序存储结构二叉树endl;SqBiTreeBt;inti=1;intLength;CreateBtLength;cout该二叉树按层序遍历的遍历结果为:;LevelOrderTraverseBtLength;coutendl按先序遍历的结果为:;PreOrederTraverseBtiLength;coutendl;coutendl按中序遍历的结果为:;InOrederTraverseBtiLength;coutendl;coutendl按后序遍历的结果为:;PosOrederTraverseBtiLength;coutendl;cout201240410111周逊endl;}运行结果二叉链表存储结构程序代码#includeiostreamusingnamespacestd;#defineERROR1#defineOK-1typedefcharTElemType;/*二叉树节点的存储类型*/typedefstructBiTNode{TElemTypedata;structBiTNode*lchild*rchild;}BiTNode*BiTree;/*建立二叉树*/intCreateBiTreeBiTreeT{TElemTypech;cinch;ifch==#T=NULL;else{if!T=BiTNode*mallocsizeofBiTNode{coutOverflow!;//noalloctionreturnERROR;}T-data=ch;CreateBiTreeT-lchild;//createlchildCreateBiTreeT-rchild;//createrchild}returnOK;}intPreOrderTraverseBiTreeT//PreOrderTraverssub-function{ifT{coutT-data-;//visiteTifPreOrderTraverseT-lchild//traverselchildifPreOrderTraverseT-rchild//traverserchildreturnOK;returnERROR;}//ifendelsereturnOK;}//PreOrderTraverseendintInOrderTraverseBiTreeT//InOrderTraversesub-function{ifT{ifInOrderTraverseT-lchild//traverselchild{coutT-data-;//visiteTifInOrderTraverseT-rchild//traverserchildreturnOK;}returnERROR;}//ifendelsereturnOK;}//InOrderTraverseendintPostOrderTraverseBiTreeT//PostOrderTraversesub-function{ifT{ifPostOrderTraverseT-lchild//traverselchildifPostOrderTraverseT-rchild//traverserchild{coutT-data-;//visiteTreturnOK;}returnERROR;}elsereturnOK;}//PostOrderTraverseendintmainintargcchar*argv[]{BiTreeT;coutPleaseinputdata/forNULLnode!:;CreateBiTreeT;cout先序遍历二叉树:;PreOrderTraverseT;coutendl;cout中序遍历二叉树:;InOrderTraverseT;coutendl;cout后序遍历二叉树:;PostOrderTraverseT;coutendl;return0;}运行结果
2、以二叉链表作存储结构,试编写计算二叉树深度、所有结点总数、叶子结点数、双孩子结点个数、单孩子结点个数的算法程序代码#includeiostreamusingnamespacestd;#defineERROR1#defineOK-1typedefcharTElemType;/*二叉树节点的存储类型*/typedefstructBiTNode{TElemTypedata;structBiTNode*lchild*rchild;}BiTNode*BiTree;/*建立二叉树*/intCreateBiTreeBiTreeT{TElemTypech;cinch;ifch==#T=NULL;else{if!T=BiTNode*mallocsizeofBiTNode{coutOverflow!;//noalloctionreturnERROR;}T-data=ch;CreateBiTreeT-lchild;//createlchildCreateBiTreeT-rchild;//createrchild}returnOK;}intPreOrderTraverseBiTreeT//PreOrderTraverssub-function{ifT{coutT-data-;//visiteTifPreOrderTraverseT-lchild//traverselchildifPreOrderTraverseT-rchild//traverserchildreturnOK;returnERROR;}//ifendelsereturnOK;}//PreOrderTraverseendintInOrderTraverseBiTreeT//InOrderTraversesub-function{ifT{ifInOrderTraverseT-lchild//traverselchild{coutT-data-;//visiteTifInOrderTraverseT-rchild//traverserchildreturnOK;}returnERROR;}//ifendelsereturnOK;}//InOrderTraverseendintPostOrderTraverseBiTreeT//PostOrderTraversesub-function{ifT{ifPostOrderTraverseT-lchild//traverselchildifPostOrderTraverseT-rchild//traverserchild{coutT-data-;//visiteTreturnOK;}returnERROR;}elsereturnOK;}//PostOrderTraverseendintLeafCountBiTreeT{intmn;if!Treturn0;if!T-lchild!T-rchildreturn1;else{m=LeafCountT-lchild;n=LeafCountT-rchild;returnm+n;}//ifreturnOK;}intNodeCountBiTreeT{if!Treturn0;elsereturnNodeCountT-lchild+NodeCountT-rchild+1;}intonesoncountBiTreeT{ifT==NULLreturn0;elseifT-lchild==NULLT-rchild!=NULL||T-lchild!=NULLT-rchild==NULLreturnonesoncountT-lchild+onesoncountT-rchild+1;elsereturnonesoncountT-lchild+onesoncountT-rchild;}inttwosoncountBiTreeT{ifT==NULLreturn0;elseifT-lchild==NULL||T-rchild==NULLreturntwosoncountT-lchild+twosoncountT-rchild;elseifT-lchild!=NULLT-rchild!=NULLreturntwosoncountT-lchild+twosoncountT-rchild+1;return1;}intBTDepthBiTreeT{if!Treturn0;else{inth1=BTDepthT-lchild;inth2=BTDepthT-rchild;ifh1h2returnh1+1;elsereturnh2+1;}}intmainintargcchar*argv[]{BiTreeT;coutPleaseinputdata/forNULLnode!:;CreateBiTreeT;cout先序遍历二叉树:;PreOrderTraverseT;coutendl;cout中序遍历二叉树:;InOrderTraverseT;coutendl;cout后序遍历二叉树:;PostOrderTraverseT;coutendl;cout二叉树中叶子结点的个数:LeafCountTendl;cout二叉树中结点的个数NodeCountTendl;cout二叉树的深度:BTDepthTendl;cout双孩子结点个数:twosoncountTendl;cout单孩子结点个数onesoncountTendl;return0;}运行结果
3、已知二叉树的前序遍历和中序遍历序列,构造对应的二叉树程序代码#includestdio.h#includestdlib.h#includestring.h#includeconio.h#defineMaxSize100typedefstructNode{chardata;structNode*lchild*rchild;}BitNode*BiTree;voidCreateBiTreeBiTree*Tchar*prechar*inintlen;voidVisitBiTreeTBiTreeprechareinti;voidPrintLevelBiTreeT;voidPrintLRTBiTreeT;voidPrintLevelBiTreeT{BiTreeQueue[MaxSize];intfrontrear;ifT==NULLreturn;front=-1;rear=0;Queue[rear]=T;whilefront!=rear{front++;printf%2cQueue[front]-data;ifQueue[front]-lchild!=NULL{rear++;Queue[rear]=Queue[front]-lchild;}ifQueue[front]-rchild!=NULL{rear++;Queue[rear]=Queue[front]-rchild;}}}voidPrintLRTBiTreeT{ifT!=NULL{PrintLRTT-lchild;PrintLRTT-rchild;printf%2cT-data;}}voidCreateBiTreeBiTree*Tchar*prechar*inintlen{intk;char*temp;iflen=0{*T=NULL;return;}*T=BitNode*mallocsizeofBitNode;*T-data=*pre;fortemp=in;tempin+len;temp++if*pre==*tempbreak;k=temp-in;CreateBiTree*T-lchildpre+1ink;CreateBiTree*T-rchildpre+1+ktemp+1len-1-k;}voidmain{BiTreeTptr=NULL;intlen;charpre[MaxSize]in[MaxSize];T=NULL;printf由先序序列和中序序列构造二叉树\n;printf请你输入先序的字符串序列;getspre;printf请你输入中序的字符串序列;getsin;len=strlenpre;CreateBiTreeTpreinlen;printf你建立的二叉树后序遍历结果是\n;PrintLRTT;printf\n你建立的二叉树层次遍历结果是\n;PrintLevelT;printf\n;}
六、注意事项
1、遍历的思想
七、思考题
1、用非遍历算法如何实现?实验五查找
一、实验目的及要求
1、掌握查找的不同方法,并能用高级语言实现查找算法
2、熟练掌握顺序表的查找方法和有序顺序表的折半查找算法以及静态查找树的构造方法和查找算法
3、掌握二叉排序树的生成、插入、删除、输出运算
二、实验学时3学时
三、实验任务
1、顺序表的顺序查找
2、有序顺序表的二分查找的递归算法
四、实验重点、难点
1、设置一个监视哨
2、mid的变化
3、快速排序
4、二路归并中的一趟归并算法
五、操作要点任务
1、顺序表的顺序查找#includestdio.h#includemalloc.h#includeconio.h#defineMAX_LENGTH11typedefintKeyType;typedefstruct{KeyType*elem;intlength;}SSTable;intSearch_SeqSSTableSTKeyTypekey{inti;ST.elem
[0]=key;fori=ST.length;!ST.elem[i]==key;--i;returni;}intmain{intimn;SSTabletable1;table
1.elem=int*mallocMAX_LENGTH*sizeofint;table
1.length=MAX_LENGTH;printf数组元素:;fori=1;iMAX_LENGTH;i++scanf%dtable
1.elem[i];fori=1;iMAX_LENGTH;i++printf%dtable
1.elem[i];printf\n请输入查找元素:;scanf%dm;n=Search_Seqtable1m;if0==nprintf未找到元素;elseprintf查找的元素的位置为elem.[%d]\nn;getch;return0;}任务
2、有序顺序表的二分查找的算法#includestdio.h#includemalloc.h#includeconio.h#defineMAX_LENGTH11typedefintKeyType;typedefstruct{KeyType*elem;intlength;}SSTable;/*在有序查找表中折半查找其关键字等于key的数据元素*/intSearch_SeqSSTableSTKeyTypekey//Search_Seqfunction{intmidlow=1high=ST.length;whilelow=high{mid=low+high/2;ifkey==ST.elem[mid]returnmid;elseifkeyST.elem[mid]high=mid-1;elselow=mid+1;}return0;}intmain{intimn;SSTabletable1;table
1.elem=int*mallocMAX_LENGTH*sizeofint;table
1.length=MAX_LENGTH;printf数组元素:;fori=1;iMAX_LENGTH;i++scanf%dtable
1.elem[i];fori=1;iMAX_LENGTH;i++printf%dtable
1.elem[i];printf\n请输入查找元素:;scanf%dm;n=Search_Seqtable1m;if0==nprintf未找到元素;elseprintf查找的元素的位置为elem.[%d]\nn;getch;return0;}任务
3、二叉排序树的查找、插入、删除等基本操作的实现#includeiostream.usingnamespacestd;typedefintKeyType;typedefstructtree//声明树的结构{structtree*left;//存放左子树的指针structtree*right;//存放又子树的指针KeyTypekey;//存放节点的内容}BSTNode*BSTree;//声明二叉树的链表BSTreeinsertBSTBSTreetptrKeyTypekey//在二叉排序树中插入结点{//若二叉排序树tptr中没有关键字为key的结点,则插入,否则直接返回BSTreefp=tptr;//p的初值指向根结点whilep//查找插入位置,循环结束时,p是空指针,f指向待插入结点的双亲{ifp-key==key//树中已有key,无须插入returntptr;f=p;//f保存当前查找的结点,即f是p的双亲p=keyp-keyp-left:p-right;}p=BSTreemallocsizeofBSTNode;//生成新结点p-key=key;p-left=p-right=NULL;iftptr==NULL//原树为空,新插入的结点为新的根tptr=p;elseifkeyf-keyf-left=p;elsef-right=p;returntptr;}BSTreecreateBST//建立二叉树{BSTreet=NULL;//根结点KeyTypekey;cinkey;whilekey!=-1{t=insertBSTtkey;cinkey;}returnt;}voidinorder_btreeBSTreeroot//中序遍历打印二叉排序树{BSTreep=root;ifp!=NULL{inorder_btreep-left;coutp-key;inorder_btreep-right;}}intsearchBSTBSTreetKeyTypekey//查找{ifkey==t-keyreturn1;ift==NULLreturn0;ifkeyt-keyreturnsearchBSTt-leftkey;elsereturnsearchBSTt-rightkey;}BSTreedeleteBSTBSTreetptrKeyTypekey//删除{BSTreeptmpparent=NULL;p=tptr;whilep{ifp-key==keybreak;parent=p;p=keyp-keyp-left:p-right;}if!preturnNULL;tmp=p;if!p-right!p-left/*p的左右子树都为空*/{if!parent//要删根,须修改根指针tptr=NULL;elseifp==parent-rightparent-right=NULL;elseparent-left=NULL;freep;}elseif!p-right//p的右子树为空,则重接p的左子树{p=p-left;if!parent//要删根,须修改根指针tptr=p;elseiftmp==parent-leftparent-left=p;elseparent-right=p;freetmp;}elseif!p-left//的左子树为空,则重接p的左子树{p=p-right;if!parent//要删根,须修改根指针tptr=p;elseiftmp==parent-leftparent-left=p;elseparent-right=p;freetmp;}elseifp-rightp-left//p有左子树和右子树,用p的后继覆盖p然后删去后继{//另有方法用p的前驱覆盖p然后删去前驱||合并p的左右子树parent=p;//由于用覆盖法删根,则不必特殊考虑删根p=p-right;whilep-left{parent=p;p=p-left;}tmp-key=p-key;ifp==parent-leftparent-left=NULL;elseparent-right=NULL;freep;}returntptr;}intmain{KeyTypekey;intflagtest;charcmd;BSTreeroot;do{cout请选择你要执行的操作:endl;cout创建一棵二叉排序树:C.退出:E\n;flag=0;do{ifflag!=0cout选择操作错误!请重新选择!\n;fflushstdin;cincmd;flag++;}whilecmd!=ccmd!=Ccmd!=ecmd!=E;ifcmd==c||cmd==C{cout请输入你所要创建的二叉树的结点的值,以-1结束\n;root=createBST;do{flag=0;cout中序遍历二叉树endl;inorder_btreeroot;cout\n请选择你要对这棵二叉树所做的操作:查找:S.插入:I.删除:D.退出:Qendl;do{ifflag!=0cout选择操作错误!请重新选择!\n;fflushstdin;scanf%ccmd;flag++;}whilecmd!=scmd!=Scmd!=icmd!=Icmd!=dcmd!=Dcmd!=qcmd!=Q;switchcmd{cases:caseS:cout请输入你要查找结点的关键字\n;cinkey;test=searchBSTrootkey;iftest==0cout\n对不起,你所查找的结点key不存在!;elsecout\n成功找到结点\nkey;break;casei:caseI:cout请输入你要插入结点的关键字\n;cinkey;root=insertBSTrootkey;//注意必须将值传回根break;cased:caseD:cout请输入你要删除结点的关键字\n;cinkey;root=deleteBSTrootkey;//注意必须将值传回根ifroot==NULLcout\n对不起,你所删除的结点key不存在!\n;elsecout\n成功删除结点key;break;}}whilecmd!=qcmd!=Q;}}whilecmd!=ecmd!=E;return0;}
六、注意事项
1、mid的变化
七、思考题
1、在用拉链法解决冲突的散列表上如何插入元素?。