数据结构实验课教案.docx

授 课 教 案（20162017 学年度第一学期）课程名称：课程编码：总 学 时：课程类别：任课教师：开课单位：职 称：授课专业：授课班级：数据结构B13040009A64总学分：专业课4李素若计算机工程学院教授计算机科学与技术2015 级计算机科学与技术专业1、2 班 2016 年9 月 14 日（9授课进度 第 3 周，第 6 次课（ 2 学时）授课日期月13 日）授课题目(教学章、节 实验一 线性表的顺序存储结构或主题)12.掌握线性表顺序存储结构的特点：逻辑上相邻的数据元素其物理位置上也相邻。.掌握线性表顺序存储结构的插入、删除操作特点移动操作。教学目标1.线性表的顺序存储特点2.线性表的顺序存储的基本算法教学重点1.线性表的顺序存储的基本算法教学难点请选择你授课时所采用的教学方法（在括号中画“”）：讲授法，讨论法，演示法，案例法，发现法，探究法，谈话法，实验法，参观法，考察法，自学辅导法，练习法（习题或操作课），读书指导法，听说法，写生法，视唱法，工序法（技能课），实习作业法，其他教学方法请选择你授课时所采用的教学手段（在括号中画“”）：教学手段实物，多媒体，投影，影像，CAI 课件，PPT，标本，挂图，模型，其他讨论、思考题、作业1李素若，陈万华，游明坤主编.数据结构.北京:中国水利水电出版社，2014.2李素若，陈万华，游明坤主编.数据结构习题集及上机指导.北京:中国水利水参考文献电出版社，2014. 教学过程及内容一、实验内容1234567输入一组整型元素序列，建立顺序表。遍历该顺序表。在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。判断该顺序表中元素是否对称,对称返回1,否则返回0。输入整型元素序列利用有序表插入算法建立一个有序表。利用实验6 建立两个递增有序表并把它们合并成一个递增有序表。二、实验指导1参考程序为：void CreateSqList(SqList *L)int n,idoprintf(请输入数据元素的个数:)scanf(%d,&n)if(n=0)printf(输入错误n)while(n=0)for(i=0ielemi)Llength=n2参考程序为：void PrintList(SqList L)int ifor(i=0iL.lengthi+)printf(%d ,L.elemi)printf(n)3参考程序为：int Findelems(SqList L,ElemType e)int ifor(i=0iL.lengthi+)if(L.elemi=e)return 1return 04分析：从顺序表表头开始扫描，当数据元素为偶数时就从该数开始往后查找，一旦1 教学过程及内容找到奇数，则将该偶数与此奇数交换。顺序表中所有数据全部扫描结束后，所有奇数就排列在表的前端。参考程序为：void ChangeVal(SqList *L)int i,j,tempfor(i=0ilengthi+)if(Lelemi%2=0)for(j=i+1jlengthj+)if(Lelemj%2!=0)temp=LelemiLelemi=LelemjLelemj=tempbreakif(j=Llength)break5参考程序为：int YesNo_Symmetry(SqList L)int i,jj=L.length1for(i=0ij/2i+)if(L.elemi!=L.elemji)return 0return 16参考程序为：void Insert_OrderList(SqList *L,int x)int i,jfor(i=0ilengthi+)if(Lelemix)breakfor(j=Llength1j=ij)2 教学过程及内容Lelemj+1=LelemjLelemi=xLlength+void Create_OrderList(SqList *L)int n,i,inputdoprintf(请输入数据元素的个数:)scanf(%d,&n)if(n=0)printf(输入错误n)while(n=0)for(i=0ilength=0while(jA.length & kB.length)if(A.elemjelemi+=A.elemj+elseCelemi+=B.elemk+if(j=A.length)while(kelemi+=B.elemk+if(k=B.length)while(jelemi+=A.elemj+Clength=ireturn C3 2016 年 9 月21 日（9授课进度 第 4 周，第 8 次课（ 2 学时）授课日期月20 日）授课题目(教学章、节 实验二 单向链表或主题)123掌握线性链表的操作特点，即指针是逻辑关系的映像。掌握动态产生单链表的方法。熟练掌握单链表的插入、删除操作特点，即指针赋值的先后次序。教学目标1掌握动态产生单链表的方法。2熟练掌握单链表的插入、删除操作特点，即指针赋值的先后次序。教学重点1熟练掌握单链表的插入、删除操作特点，即指针赋值的先后次序。教学难点请选择你授课时所采用的教学方法（在括号中画“”）：讲授法，讨论法，演示法，案例法，发现法，探究法，谈话法，实验法，参观法，考察法，自学辅导法，练习法（习题或操作课），读书指导法，听说法，写生法，视唱法，工序法（技能课），实习作业法，其他教学方法请选择你授课时所采用的教学手段（在括号中画“”）：教学手段实物，多媒体，投影，影像，CAI 课件，PPT，标本，挂图，模型，其他讨论、思考题、作业1李素若，陈万华，游明坤主编.数据结构.北京:中国水利水电出版社，2014.2李素若，陈万华，游明坤主编.数据结构习题集及上机指导.北京:中国水利水参考文献电出版社，2014. 教学过程及内容一、实验内容12345随机产生或键盘输入一组元素，建立一个带头结点的单向链表（无序）。遍历单向链表。把单向链表中元素逆置（不允许申请新的结点空间）。在单向链表中删除所有的偶数元素结点。编写在非递减有序链表中插入一个元素使链表元素仍有序的函数，并利用该函数建立一个非递减有序单向链表。67利用实验5 建立两个递增有序单向链表，然后合并成一个递增链表。利用实验1 建立的链表，实现将其分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量利用已知的存储空间）。二、实验指导1参考程序为：LinkList CreateListH(void)/头插法产生带头结点单链表int chLinkList head=(LinkList)malloc(sizeof(LNode)LinkList sheadnext=NULLwhile(scanf(%d,&ch)=1)/输入数据类型错误时结束单链表的生成s=(LinkList)malloc(sizeof(LNode)sdata=chsnext=headnextheadnext=sreturn headLinkList CreateListRand(void)/利用随机函数产生带头结点单链表（头插法）int ch,iLinkList head=(LinkList)malloc(sizeof(LNode)LinkList sheadnext=NULLsrand( (unsigned)time( NULL ) )printf(Please input Create Nnmbers:)scanf(%d,&ch)for(i=0idata=rand()%50/随机产生049 之间的数1 教学过程及内容snext=headnextheadnext=sreturn head2参考程序为：void PrintLinkList(LNode L)LinkList pp=L.nextwhile(p)printf(%d ,pdata)p=pnextprintf(n)3参考程序为：void Inverse_set(LinkList head)LNode *r,*m=NULL,*pp=headnextwhile (p!=NULL)r=m m=pp=pnextmnext=rheadnext=m4参考程序为：void DelEvenLinkList(LinkList head)LinkList q,pp=headnextq=headwhile(p)if(pdata%2=0)qnext=pnextfree(p)2 教学过程及内容p=qnextelseq=pp=pnext5参考程序为：void InsertIncr(LinkList head,ElemType x)/将结点插入递增的单链表LinkList q,p,ss=(LinkList)malloc(sizeof(LNode)sdata=xq=headp=headnextwhile(p & pdatanextsnext=qnextqnext=sLinkList CreateListIncr(void)/通过调用插入有序链表函数生成递增单链表int chLinkList head=(LinkList)malloc(sizeof(LNode)LinkList sheadnext=NULLwhile(scanf(%d,&ch)=1)/输入数据类型错误时结束单链表的生成InsertIncr(head,ch)return head6参考程序为：LinkList LinkListCat(LinkList head1,LinkList head2)LinkList h1,h2,hLinkList head=(LinkList)malloc(sizeof(LNode)headnext=NULL3 教学过程及内容h1=head1nexth2=head2nexth=headwhile(h1 & h2)if(h1datadata)hnext=h1h=hnexth1=h1nextelsehnext=h2h=hnexth2=h2nextif(h1)hnext=h1if(h2)hnext=h2return head7#参考程序为：include includeincludetypedef int ElemType/元素类型typedef struct LNodeElemType datastruct LNode *nextLNode,*LinkListvoid PrintLinkList(LNode L)LinkList pp=L.nextwhile(p)printf(%d ,pdata)p=pnext4 教学过程及内容printf(n)void DecoLinkList(LNode head,LinkList head1,LinkList head2)/将单链表head 拆分奇数链head1 和偶数链head2LinkList h,h1,h2h=head.nexth1=head1h2=head2while(h)if(hdata%2=0)h2next=hh=hnexth2=h2nextelseh1next=hh=hnexth1=h1nexth1next=NULLh2next=NULLmain()LinkList headLinkList head1=(LinkList)malloc(sizeof(LNode)LinkList head2=(LinkList)malloc(sizeof(LNode)head=CreateListIncr()PrintLinkList(*head)DecoLinkList(*head,head1,head2)PrintLinkList(*head1)PrintLinkList(*head2)5 2016 年 9 月28 日（9授课进度 第 5 周，第 10 次课（ 2 学时）授课日期月27 日）授课题目(教学章、节 实验三 栈的存储及基本运算或主题)12.掌握栈这种数据结构特性及其主要存储结构，并能在现实生活中灵活运用。.了解和掌握递归程序设计的基本原理和方法。教学目标123.掌握栈的两种存储结构.栈的基本运算教学重点.了解栈在递归函数中的作用1.掌握栈的两种存储结构.栈的基本运算教学难点2请选择你授课时所采用的教学方法（在括号中画“”）：讲授法，讨论法，演示法，案例法，发现法，探究法，谈话法，实验法，参观法，考察法，自学辅导法，练习法（习题或操作课），读书指导法，听说法，写生法，视唱法，工序法（技能课），实习作业法，其他教学方法请选择你授课时所采用的教学手段（在括号中画“”）：教学手段实物，多媒体，投影，影像，CAI 课件，PPT，标本，挂图，模型，其他讨论、思考题、作业1李素若，陈万华，游明坤主编.数据结构.北京:中国水利水电出版社，2014.2李素若，陈万华，游明坤主编.数据结构习题集及上机指导.北京:中国水利水参考文献电出版社，2014. 教学过程及内容一、实验内容123采用顺序存储实现栈的初始化、入栈、出栈操作。采用链式存储实现栈的初始化、入栈、出栈操作。写一个程序，将输入的十进制数据M 转换为八进制数据M8，将其调试通过。在此基础上修改程序，实现十进制数据M 向N 进制（2 或8 或16）的转换。（1）采用顺序存储结构实现栈。2）采用链表结构实现栈。二、实验指导1#参考程序为：includeincludedefine Stack_Size 100define OK1define ERROR0typedef int ElemTypetypedef struct StackElemType elemStack_Sizeint top/用来存放栈中元素的一维数组/用来存放栈顶元素的下标SqStackint InitStack(SqStack *s)/初始化顺序栈(*s)=(SqStack *)malloc(sizeof(SqStack)if(*s)=NULL)return ERROR*s)top=1return OK(int EmptyStack(SqStack s)/判断栈空if(s.top=1)printf(stack is empty!n)return OKreturn ERRORint GetTop(SqStack s,int *e)/取栈顶元算if(EmptyStack(s)return ERROR*e=s.elems.top1 教学过程及内容return OKint Push(SqStack *s,int e)/入栈if(stop=Stack_Size1)printf(stack is full!n)return ERRORstop+selemstop=ereturn OKvoid PrintStack(SqStack s)/打印栈中数据int ifor(i=0ielemstopstopreturn OKvoid main()int cord,e,x,ySqStack *sdoprintf(n Main Menu n)printf(1Creat Stackn)printf(2Get Top Elementn)printf(3Pushn)printf(4Popn)printf(5Printn)printf(6quitn)scanf(%d,&cord)2 教学过程及内容switch(cord)case 1:InitStack(&s)breakcase 2:case 3:if(GetTop(*s,&y)printf(Stack Top=%dn,y)breakprintf(Please input push element:)scanf(%d,&e)Push(s,e)breakcase 4:if(Pop_Stack(s,&x)printf(Pop stack=%dn,x)breakcase 5:case 6:PrintStack(*s)breakreturnwhile(cord=6)2#参考程序为：include include define Stack_Size 100define OK1define ERROR0typedef int ElemTypetypedef struct stacknodeElemType datastruct stacknode *nextStackNodetypedef structStackNode *top /*栈顶指针*/LinkStack3 教学过程及内容void InitStack(LinkStack *s)/初始化栈stop=NULLint EmptyStack(LinkStack s)/判断栈空if(s.top=NULL)return OKelse return ERRORint GetTop(LinkStack s,int *e)/取栈顶元素if(EmptyStack(s)return ERROR*e=s.topdatavoid Push(LinkStack *s,int e)/入栈StackNode *p=(StackNode *)malloc(sizeof(StackNode)pdata=epnext=stopstop=pint Pop_Stack(LinkStack *s,int *e)/出栈StackNode *pif(EmptyStack(*s)return ERRORp=stop*e=pdatastop=pnextfree(p)return OKvoid PrintStack(LinkStack s)/打印栈中元素StackNode *p=s.topwhile(p)printf(%d ,pdata)p=pnextvoid main()4 教学过程及内容int cord,e,x,yLinkStack sdoprintf(n Main Menu n)printf(1Creat Stackn)printf(2Get Top Elementn)printf(3Pushn)printf(4Popn)printf(5Printn)printf(6quitn)scanf(%d,&cord)switch(cord)case 1:InitStack(&s)breakcase 2:if(GetTop(s,&y)printf(Stack Top=%dn,y)breakcase 3:case 4:printf(Please input push element:)scanf(%d,&e)Push(&s,e)breakif(Pop_Stack(&s,&x)printf(Pop stack=%dn,x)breakcase 5:case 6:PrintStack(s)breakreturnwhile(cordfront = (*Q)rear=0return 1(int QueueEmpty(SqQueue Q)/判断队空return Q.front=Q.rear1 教学过程及内容int QueueFull(SqQueue Q)/判断队满return (Q.rear+1)%MAXSIZE=Q.frontint EnQueue(SqQueue *Q, ElemType e)/入队操作if (QueueFull(*Q)return 0/ 队列满QdataQrear=eQrear=(Qrear+1)%MAXSIZEreturn 1int DeQueue (SqQueue *Q, ElemType *e)/出队操作if (QueueEmpty(*Q)return 0else*e=QdataQfrontQfront=(Qfront+1)%MAXSIZEreturn 12参考程序为：int InitQueue(LinkQueue *Q)/将Q 初始化为一个空的链队列Qfront=Qrear=(QueuePtr)malloc(sizeof(QNode)if (Qfront=NULL)return 0Qfrontnext=NULLreturn 1int QueueEmpty(LinkQueue Q)/判断队空return Q.front=Q.rearint EnQueue(LinkQueue *Q, ElemType e)/入队操作QueuePtr pp=(QueuePtr)malloc(sizeof(QNode)if(!p)return 02 教学过程及内容pdata=epnext=NULLQrearnext=pQrear =preturn 1int DeQueue(LinkQueue *Q,ElemType *e)/出队操作QueuePtr pif(QueueEmpty(*Q)return 0/若队列Q 为空队列p=Qfrontnext*e=pdataQfrontnext=pnextif(Qrear=p)Qrear=Qfront /若Q 只有一个结点free(p)return 13参考程序为：int main()LinkQueue q1,q2int i=0,j=0,numInitQueue(&q1)InitQueue(&q2)srand(unsigned)time(NULL)while( i20 | j20 )num=rand()%100if(num%2=0&i20)EnQueue(&q1,num)i+if(num%2!=0&jdata=chplchild=prchild=NULLif(*b=NULL)*b=pelseswitch(k)case 1:Sttoplchild=pbreakcase 2:Sttoprchild=pbreakj+ch=strjvoid DispBTNode(BTNode *b)/广义表输出二叉树1 教学过程及内容if(b!=NULL)printf(%c,bdata)if(blchild!=NULL|brchild!=NULL)printf()DispBTNode(blchild)if(brchild!=NULL) printf(,)DispBTNode(brchild)printf()2参考代码为：void InOrder(BTree T)/中序递归遍历if (T)InOrder(Tlchild) /*中遍历左子树*/printf(%3c,Tdata)/*访问根结束*/InOrder(Trchild)/*中根遍历右子树*/3参考代码为：void InOrder1(BTree T)/非递归中序遍历SqStack *SBTree P=TInitStack(&S)dowhile(P)Push(S,P)P=Plchild/*从树或子树根出发往左到叶子*/if(Stop!=1) /*P 为NULL 要么是叶子，要么是没有左子树*/Pop(S,&P)printf(%3c,Pdata)P=Prchildwhile(Stop!=1)| P)2 2016 年11 月9 日（11授课进度 第 11 周，第 20 次课（ 2 学时）授课日期月8 日）授课题目(教学章、节 实验五 二叉树（）或主题)12二叉树的常用算法。二叉树线索化及遍历。教学目标1二叉树的常用算法。教学重点1.二叉树的常用算法。教学难点请选择你授课时所采用的教学方法（在括号中画“”）：讲授法，讨论法，演示法，案例法，发现法，探究法，谈话法，实验法，参观法，考察法，自学辅导法，练习法（习题或操作课），读书指导法，听说法，写生法，视唱法，工序法（技能课），实习作业法，其他教学方法请选择你授课时所采用的教学手段（在括号中画“”）：教学手段实物，多媒体，投影，影像，CAI 课件，PPT，标本，挂图，模型，其他讨论、思考题、作业1李素若，陈万华，游明坤主编.数据结构.北京:中国水利水电出版社，2014.2李素若，陈万华，游明坤主编.数据结构习题集及上机指导.北京:中国水利水参考文献电出版社，2014. 教学过程及内容一、实验内容1234求二叉树的宽度。求任意二叉树中第一条最长的路径长度，并输出此路径上各结点的值。输出二叉树中从每个叶子结点到根结点的路径。建立前序线索二叉树，并实现前序遍历。二、实验指导1参考代码为：int BTWidth(BTNode *b) /求二叉树宽度structint lnoBTNode *pQuMaxSize /定义顺序非循环队列/结点的层次编号/结点指针int front,rear/定义队首和队尾指针int lnum,max,i,nfront=rear=0