《2022年本数据结构实验教案.docx》由会员分享，可在线阅读，更多相关《2022年本数据结构实验教案.docx（71页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选学习资料 - - - - - - - - - 数据结构 试验教案授课老师：许四平适用专业：信息与运算科学 使用班级： 13 信计 1、2 授课时间： 20XX年秋季 授课学时： 14 学时使用教材：数据结构试验指导书：数据结构试验指导书,严蔚敏 主编数理学院编, 20XX年版湖北理工学院数理学院名师归纳总结 - - - - - - -第 1 页,共 36 页精选学习资料 - - - - - - - - - 周次日期实验安排表学时试验报试验课题告次数名师归纳总结 33.23线性表的次序储备21第 2 页,共 36 页33.26线性表的次序储备2154.4单链表2154.9单链表2174.20
2、栈、队列3174.23栈、队列3184.27树与二叉树2184.29树与二叉树2195.10树与二叉树2195.10树与二叉树21146.9查找31146.10查找31- - - - - - -精选学习资料 - - - - - - - - - 数据结构设计性试验项目1. 线性表的合并：已知线性表 La 和 Lb 的元素按值非递减排列；归并 La 和 Lb 得到新的线性表 Lc,Lc 的元素也按值非递减排列；分别采纳次序储备结构和链式结构来实现；2. 线性表的逆置：设有一个线性表（e0, e1, , en-2, en-1 ）,请编写一个函数将这个线性表原地逆置,即将线性表内容置换为（en-1 ,
3、 en-2 , , e1, e0）；线性表中的数据可以为整数、字符或字符串,试分别采纳次序储备结构和链式结构来实现；3. 约瑟夫环的实现：设有 n 个人围坐一圈,用整数序列 1, 2, 3, , n 表示顺序围坐在圆桌四周的人,现从某个位置 s 上的人开头报数,数到 m 的人出列,接着从出列的下一个人又从 1 开头重新报数,数到 m的人出列,如此下去,直到全部人都出列为此；试设计确定他们的出列次序序列的程序；如 n=8, m=4 ,s=1 时,设每个人的编号依次为 1 ,2,3, 开头报数,就得到的出列次序为 程序的正确性和健壮性；1 采纳数组表示作为求解过程中使用的数据结构；4, 8,5,2
4、,1,3,7,6；检查2 采纳单向循环链表作为储备结构模拟整个过程,循环链表可不设头节点, 必需留意空表和非空表的界限；4. 数制转换：利用次序栈和链栈实现数制转换5. 二叉树的遍历：分别以次序储备结构和二叉链表作储备结构,试编写前序、中序、后序及层次次序遍历二叉树的算法；6. 赫夫曼树与赫夫曼编码：已知某系统在通信联络中只可能显现 8 种字符a,b,c,d,e,f,g,h,其概率分别为 0.05 ,0.29 ,0.07 ,0.08 ,0.14 ,0.23 ,0.03 ,0.11 ,试设计 Huffman 编码,并运算其平均码长；1 初始化：从键盘读入 8 个字符,以及它们的权值,建立 Huf
5、fman 树；2 编码：依据建立的 Huffman 树,求每个字符的 Huffman 编码；对给定的待编码字符序列进行编码；3 译码：利用已经建立好的 Huffman 树,对上面的编码结果译码；译码的过程是分解电文中的字符串,从根结点动身,按字符0和1确定找左孩子或右孩子,直至叶结点,便求得该子串相应的字符；4 打印 Huffman 树；7. 同学成果治理查询系统：每个同学的数据信息有准考证号（主关键字）、姓名、语文、英语、数学、和总分等数据项,全部同学的信息构成一个同学成果表；假设准考证号的头两位表示地区编号；请设计一个治理系统达到如下基本要求：（ 1） 初始化：建立一个同学成果表,输入准考
6、证号、姓名、语文、英语、数学,然后运算每个同学的总分,存入相应的数据项；留意： 分析数据对象和它们之间的关系,并以合适的方式进行组织（可挑选无序的次序表、有序的次序表或索引次序表来进行存储表示）；（ 2） 查找：综合应用基本查找算法完成数据的基本查询工作,并输出查询的结果；（ 3） 输出：有挑选性地输出满意肯定条件的数据记录,如输出地区编号为 01 ,并且总分在 550 分以上的同学的信息；（ 4） 运算：运算在等概率情形下该查找表的平均查找长度；8. 排序：编制程序让机器随机产生2000 个整数,放入一个数组中；对此2000 个随机数序列分别用冒泡排序、快速排序、希尔排序和堆排序方法进行排序
7、,并比较它们的运行时间；留意：每三、四个同学组成一个小组；每个试验中的题目,可分别由不同的同学完成；其它题目可以相互沟通,以利于相互提高；名师归纳总结 - - - - - - -第 3 页,共 36 页精选学习资料 - - - - - - - - - 数据结构验证性试验项目试验一 线性表的次序储备一、试验目的及要求 1、把握在 TC环境下调试次序表的基本方法2、把握次序表的基本操作,插入、删除、查找、以及有序次序表的合并等算法的 实现；二、试验学时2学时 三、试验任务 1、 生成一个次序表并动态地删除任意元素和在任意位置插入元素；2、 将两个有序表合并成一个有序表；四、试验重点、难点1、 在次
8、序表中移动元素；2、 在次序表中找到正确的插入位置；五、操作要点 一 次序表基本操作的实现i 个元素之后 i 个元素 问题描述 当我们要在次序表的第i 个位置上插入一个元素时,必需先将次序表中第的全部元素依次后移一个位置,以便腾空一个位置,再把新元素插入到该位置；如是欲删除第时,也必需把第 i 个元素之后的全部元素前移一个位置； 基本要求 要求生成次序表时,可以键盘上读取元素,用次序储备结构实现储备； 实现提示 要实现基本操作,可用实现的基本操作,也可设计简洁的算法实现； 程序实现 #include #include typedef int DataType ; # define maxnum
9、 20 typedef struct int datamaxnum; int length; SeqList; /* 插入函数 */ int insertSeqList *L , int i , DataType x /* 将新结点 x 插入到次序表L 第 i 个位置 */ int j ; if i*L.length +1 printf n i 值不合法 . ; return 0; if* L.length =maxnum-1 printf n 表满不能插入 .; return 0; forj=*L.length;j=i;j- *L.dataj+1=*L.dataj; *L.datai = x
10、; *L.length+; return 1; 名师归纳总结 - - - - - - -第 4 页,共 36 页精选学习资料 - - - - - - - - - /* 删除函数 */ int delete SeqList *L ,int i /* 从次序 L 中删除第 i 个结点 */ int j ; if i*L.length printf n 删除位置错误 . ; return 0; forj=i+1;j=*L.length;j+ *L.dataj-1 =*L.dataj; *L.length-; return 1; /* 生成次序表 */ void creatlistSeqList *
11、L int n , i , j ; printf 请输入次序表 L 的数据个数： n ; scanf%d , &n ; fori=0 ; in ; i+ printfdata%d = , i ; scanf%d,&*L.datai; *L.length=n-1; printfn ; /*creatlist */ /* 输出次序表 L*/ printoutSeqList * L int i ; for i=0 ; i=* L.length ; i+ printf data%d=, i ; printf%d, *L.datai; /*printout */ printfn; main SeqLis
12、t *L ; char cmd ; int i , t , x; clrscr ; creatlistL; do printfni , I - 插入 n ; printfd , D - 删除 n ; printfq , Q - 退出 n ; do cmd=getchar ; whilecmd.=i&cmd.=I&cmd.=d&cmd.=D&cmd.=q&cmd.=Q; switchcmd case i: case I: printfnPlease input the DATA: ; 名师归纳总结 - - - - - - -第 5 页,共 36 页精选学习资料 - - - - - - - - -
13、 scanf%d,&x ; printfnWhere. ; scanf%d,&i ; insertL,i,x ; printoutL; break ; case d: case D : printfnWhere to Delete. ; scanf%d,&i; deleteL,i; printoutL; break ; whilecmd.=q&cmd.=Q; （二）有序次序表的合并 问题描述 已知次序表 la 和 lb 中的数据元素按非递减有序排列,将成为一个新的次序表 lc la 和lb 表中的数据元素,合并 基本要求 lc中的数据元素仍按非递减有序排列,并且不破坏la 和lb 表 程序实现
14、 #include #include # define OK 1 # define ERROR 0 /* 定义 ElemType 为 int或别的自定义类型 */ typedef int ElemType; /* 链式储备类型 */ typedef struct LNode ElemType data; struct LNode *next; LNode,*LinkList; /* 单链表的建立 头插法 */ void CreateList_LLinkList &L,int n /CreateList_L function /To Creatre a LinkList L with HeadN
15、ode int i; LNode *p; L=LinkListmallocsizeofLNode; L-next=NULL; printfPlease input the data for LinkList Nodes: n; fori=n;i0;-i p=LinkListmallocsizeofLNode; scanf%d,&p-data; /Reverse order inputing for Creating a LinkList p-next=L-next; L-next=p; /end of for ifn printfSuccess to Create a LinkList .n;
16、 名师归纳总结 - - - - - - -第 6 页,共 36 页精选学习资料 - - - - - - - - - else printfA NULL LinkList have been created .n; /end of CreateList function void MergeList_LLinkList &La,LinkList &Lb,LinkList &Lc LinkList pa,pb,pc; pa=La-next;pb=Lb-next; Lc=pc=La; whilepa&pb ifpa-datadata pc-next=pa;pc=pa;pa=pa-next; else
17、 pc-next=pb;pc=pb;pb=pb-next; pc-next=pa.pa:pb; freeLb; void main LinkList La,Lb,Lc,p; int n; printf 请输入 La 的长度 n:; scanf%d,&n; CreateList_LLa,n; printf 输出 La 的内容： ; p=La-next; whilep printf%d-,p-data; p=p-next; printfn; printf 请输入 Lb 的长度 n:; scanf%d,&n; CreateList_LLb,n; printf 输出 Lb 的内容： ; p=Lb-ne
18、xt; whilep printf%d-,p-data; p=p-next; printfn; MergeList_LLa,Lb,Lc; 名师归纳总结 - - - - - - -第 7 页,共 36 页精选学习资料 - - - - - - - - - printf 输出 Lc 的内容： ; p=Lc-next; whilep printf%d-,p-data; p=p-next; printfn; 六、留意事项 1、 删除元素或插入元素表的长度要变化；2、在合并表中当某一个表到表尾了就不用比较了,直接将另一个表的元素复制到 总表去即可；试验二 单链表一、试验目的及要求 1、把握用在 TC环境下
19、上机调试单链表的基本方法 2、把握单链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现 3、进一步把握循环单链表的插入、删除、查找算法的实现名师归纳总结 - - - - - - -第 8 页,共 36 页精选学习资料 - - - - - - - - - 二、试验学时2学时三、试验任务1、在带头结点的单链表h中第 i 个数据元素之前插入一个数据元素；2、将两个有序单链表合并成一个有序单链表；3、生成一个循环单链表；4、在循环单链表中删除一个节点；四、试验重点、难点1、 在单链表中查找到第i-1 个结点并用指针p指示；2、 比较两个单链表的节点数据大小；3、循环单链表中只有一个节点的判定
20、条件；4、在循环单链表中删除一个节点；五、操作要点（一）单链表基本操作的实现 1、实现栈的次序储备和链式储备；#include #include # define STACK_INIT_SIZE 100 # define STACKINCREMENT 10 # define MAXQSIZE 100 # define OK 1 # define ERROR 0 /* 定义 SElemType为 int或别的自定义类型 */ typedef int SElemType; /* 链式栈的储备类型 */ typedef struct SNode SElemType data; struct SNod
21、e *next; SNode,*LinkStack; /* 取链式栈顶元素 */ int GeTop_LLinkStack top,SElemType &e if.top-next printfError.Its an empty LinkStack.n; return ERROR; else e=top-next-data; return OK; /* 将元素压入链式栈 */ int Push_LinkStack top,SElemType &e 名师归纳总结 - - - - - - -第 9 页,共 36 页精选学习资料 - - - - - - - - - SNode *q; q=Link
22、StackmallocsizeofSNode; q-data=e; q-next=top-next; top-next=q; returnOK; /* 将元素弹出链式栈 */ int Pop_LLinkStack top,SElemType &e SNode *q; e=top-next-data; q=top-next; top-next=q-next; freeq; returnOK; /* 定义 SElemType为 int或别的自定义类型 */ typedef int SElemType; /* 次序栈的储备类型 */ /define structure SqStack typedef
23、 struct SElemType *base; SElemType *top; int stacksize; SqStack; /* 构造空次序栈 */ int InitStackSqStack &S /InitStack sub-function S.base=SElemType *mallocSTACK_INIT_SIZE*sizeofSElemType; if.S.base printfAllocate space failure .n; return ERROR; S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; /InitS
24、tack end /* 取次序栈顶元素 */ int GetTopSqStack S,SElemType &e /GetTop sub-function ifS.top=S.base printfIts a empty SqStack .n; /if empty SqStack return ERROR; e=*S.top-1; return OK; /GetTop end 名师归纳总结 - - - - - - -第 10 页,共 36 页精选学习资料 - - - - - - - - - /* 将元素压入次序栈 */ int PushSqStack &S,SElemType e /Push s
25、ub-function *S.top+=e; return OK; /Push end /* 将元素弹出次序栈 */ int PopSqStack &S,SElemType &e /Pop sub-function e=*-S.top; return OK; /Pop end void main int i,j; SqStack s; LinkStack s1; SElemType e; InitStacks; s1=LinkStackmallocsizeofSNode; s1 - next = NULL; printf 次序栈的元素： n; fori=1;i=8;i+ scanf%d,&e;
26、 Pushs,e; printf 次序栈出栈： n; fori=1;i=8;i+ Pops,e; printf%d ,e; printfn; printf 链式栈的元素： n; forj = 1;j next Pop_Ls1,e; printf%d ,e; printfn; 名师归纳总结 - - - - - - -第 11 页,共 36 页精选学习资料 - - - - - - - - - 2、利用次序栈或链栈实现数制转换；#include #include # define STACK_INIT_SIZE 100 # define STACKINCREMENT 10 # define MAXQ
27、SIZE 100 # define OK 1 # define ERROR 0 /* 定义 SElemType为 int或别的自定义类型 */ typedef int SElemType; /* 次序栈的储备类型 */ /define structure SqStack typedef struct SElemType *base; SElemType *top; int stacksize; SqStack; /* 构造空次序栈 */ int InitStackSqStack &S /InitStack sub-function S.base=SElemType *mallocSTACK_I
28、NIT_SIZE*sizeofSElemType; if.S.base printfAllocate space failure .n; return ERROR; S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; /InitStack end int StackEmptySqStack S ifS.top=S.base return OK; else return ERROR; /* 取次序栈顶元素 */ int GetTopSqStack S,SElemType &e /GetTop sub-function ifS.top=S.b
29、ase printfIts a empty SqStack .n; /if empty SqStack return ERROR; e=*S.top-1; 名师归纳总结 - - - - - - -第 12 页,共 36 页精选学习资料 - - - - - - - - - return OK; /GetTop end /* 将元素压入次序栈 */ int PushSqStack &S,SElemType e /Push sub-function *S.top+=e; return OK; /Push end /* 将元素弹出次序栈 */ int PopSqStack &S,SElemType &
30、e /Pop sub-function e=*-S.top; return OK; /Pop end /* 利用次序栈实现对于输入的任意一个非负十进制整数,输出与其等值的八进制数；*/ void Conversion SqStack S; SElemType N,e; InitStackS; scanf%u,&N; whileN PushS,N%8; N=N/8; printfConversed to Oct.number=; while.StackEmptyS PopS,e; printf%d,e; printfn; void main Conversion; 3、实现循环队列的储备和链队列
31、的基本操作； #include #include # define OK 1 # define ERROR 0 typedef int QElemType; 名师归纳总结 - - - - - - -第 13 页,共 36 页精选学习资料 - - - - - - - - - /* 链队列的储备类型 */ typedef struct QNode /define structure QNode QElemType data; struct QNode *next; QNode,*QueuePtr; typedef struct LinkQueue QueuePtr front; QueuePtr
32、rear; LinkQueue; /* 构造空链式队列 */ /define structure LinkQueue int InitQueueLinkQueue &Q /InitQueue sub-function Q.front=Q.rear=QueuePtrmallocsizeofQNode; if.Q.front printfOverflow .n; return ERROR; Q.front-next=NULL; return OK; /InitQueue end /* 销毁链式队列 */ int DestroyQueueLinkQueue &Q whileQ.front Q.rea
33、r=Q.front-next; freeQ.front; Q.front=Q.rear; return OK; /DestroyQueue end /* 在链式队列尾插入新元素*/ /DestroyQueue sub-function int EnQueueLinkQueue &Q,QElemType e /EnQueue sub-function QNode *p; p=QueuePtrmallocsizeofQNode; if.p printfOverflow .n; return ERROR; p-data=e; p-next=NULL; ifQ.front=NULL Q.front=Q
34、.rear=p; return OK; Q.rear-next=p; Q.rear=p; return OK; /EnQueue end /* 在链式队列头删除旧元素 */ int DeQueueLinkQueue &Q,QElemType &e ifQ.front=Q.rear /DeQueue sub-function 名师归纳总结 - - - - - - -第 14 页,共 36 页精选学习资料 - - - - - - - - - printfIf it was deleted, its empty .n; return ERROR; QNode *p; p=Q.front-next;
35、e=p-data; Q.front-next=p-next; freep; return OK; /DeQueue end void main LinkQueue L; int i, n, e; if.InitQueueL exit0; printf请输入要写入队列的元素的个数：; scanf%d,&n; printf请输入要写入队列的元素：; fori = 0; itop=0; return 1; int StackEmptySeqStack *s ifs-top=0 return 1; else return 0; int StackFullSeqStack *s ifs-top=MAXSIZE-1 return 1; else return 0; void PushSeqStack *s,int x if StackFull