数据结构实验课教案

授课教案（课程名称：课程编码：总学时：课程类别：任课教师：开课单位：职称：授课专业：授课班级：数据结构B13040009A总学分：专业课4李素若计算机工程学院教授计算机科学与技术2015级计算机科学与技术专业、2班2016年9月14日（9授课进度第3周，第62授课日期月13日）授课题目实验一或主题)12教学目标线性表的顺序存储特点教学重点教学难点谈话法﹝﹞，实验法﹝√﹞，参观法﹝﹞，考察法﹝﹞，自学辅导法﹝﹞，练习法（习题或操作课）﹝√﹞，读书指导法﹝﹞，听说法﹝﹞，写生法﹝﹞，视唱教学方法教学手段PPT讨论、思考题、作业[[2]李素若，陈万华，游明坤主编.数据结构习题集及上机指导.北京:中国水利水参考文献电出版社，2014.教学过程及内容一、实验内容1234567查找成功返回否则返回。,,对称返回否则返回。．利用实验6二、实验指导1void{请输入数据元素的个数:");输入错误}while(n<=0);scanf("%d",&(L­>elem[i]));}2voidPrintList(SqList{",L.elem[i]);}3{for(i=0;i<L.length;i++)if(L.elem[i]==e)1;0;}4—1—教学过程及内容void{i,j,temp;{if(L­>elem[i]%2==0){for(j=i+1;j<L­>length;j++){{}}}}}5{i,j;{0;}1;}6voidx){—2—教学过程及内容}voidCreate_OrderList(SqList{n,i,input;请输入数据元素的个数:");输入错误}{}}7{将有序顺序表A和B合并到有序顺序表C&&{}while(k<B.length)C­>elem[i++]=B.elem[k++];}—3—2年9月日（9授课进度第4周，第82授课日期月日）授课题目实验二或主题)123教学目标2教学重点教学难点谈话法﹝﹞，实验法﹝√﹞，参观法﹝﹞，考察法﹝﹞，自学辅导法﹝﹞，练习法（习题或操作课）﹝√﹞，读书指导法﹝﹞，听说法﹝﹞，写生法﹝﹞，视唱教学方法教学手段PPT讨论、思考题、作业[[2]李素若，陈万华，游明坤主编.数据结构习题集及上机指导.北京:中国水利水参考文献电出版社，2014.教学过程及内容一、实验内容1234567．利用实验5．利用实验1二、实验指导1{{}}{NULL));inputCreateNnmbers:");{随机产生—1—教学过程及内容}}2void{{",p­>data);}}3void{{}}4void{q,p;{{—2—教学过程及内容}{}}}5voidx){q,p,s;s­>data=x;&&p­>data<x){}q­>next=s;}CreateListIncr(void){}6{—3—教学过程及内容&&{{}{}}}7###元素类型{data;}void{{",p­>data);—4—教学过程及内容}}void{将单链表拆分奇数链和偶数链{{}{}}}{head=CreateListIncr();}—5—2年9月日（9授课进度第5周，第2授课日期月日）授课题目实验三或主题)12教学目标123掌握栈的两种存储结构栈的基本运算教学重点1掌握栈的两种存储结构栈的基本运算教学难点2谈话法﹝﹞，实验法﹝√﹞，参观法﹝﹞，考察法﹝﹞，自学辅导法﹝﹞，练习法（习题或操作课）﹝√﹞，读书指导法﹝﹞，听说法﹝﹞，写生法﹝﹞，视唱教学方法教学手段PPT讨论、思考题、作业[[2]李素若，陈万华，游明坤主编.数据结构习题集及上机指导.北京:中国水利水参考文献电出版社，2014.教学过程及内容一、实验内容123．写一个程序，将输入的十进制数据M转换为八进制数据M8基础上修改程序，实现十进制数据M向N2或8或16（（12二、实验指导1#####Stack_Size100OK10{elem[Stack_Size];top;}初始化顺序栈{(*)malloc(sizeof(SqStack));ERROR;OK;(}EmptyStack(SqStacks)//判断栈空{if(s.top==­1){isOK;}ERROR;}s,int取栈顶元算{ERROR;—1—教学过程及内容OK;}Push(SqStack入栈{{isfull!\n");ERROR;}OK;}voidPrintStack(SqStacks)//打印栈中数据{",s.elem[i]);}Pop_Stack(SqStack出栈{ERROR;OK;}void{{MainMenu\n");Element\n");—2—教学过程及内容{case1:case2:case3:inputelement:");case4:stack=[%d]\n",x);case5:case6:}}}2#####Stack_Size100OK10stacknode{data;stacknode*next;}struct{栈顶指针}—3—教学过程及内容voidInitStack(LinkStack初始化栈{}EmptyStack(LinkStacks)//判断栈空{OK;returnERROR;}s,int取栈顶元素{ERROR;}voidPush(LinkStack入栈{}Pop_Stack(LinkStack*s,int出栈{ERROR;OK;}voidPrintStack(LinkStacks)//打印栈中元素{{",p­>data);}}void—4—教学过程及内容{s;{MainMenu\n");Element\n");{case1:case2:case3:case4:inputelement:");stack=[%d]\n",x);case5:case6:}}}31）（—5—教学过程及内容voidConversion(SqStack{N,n1,t;输入要转换的n(2、816):\n");输入要转换的进制{N=N/n1;}该数转化为%d进制数为{{");continue;}");continue;}");continue;}");continue;}",t);}}}void{}（2）voidConversion(LinkStack{N,n1,t;—6—教学过程及内容输入要转换的n(2、816):\n");输入要转换的进制{N=N/n1;}该数转化为%d进制数为{{");");");");");");",t);}}}void{}—7—2年月授课进度第8周，第2授课日期月日）授课题目实验四队列或主题)123教学目标教学重点教学难点谈话法﹝﹞，实验法﹝√﹞，参观法﹝﹞，考察法﹝﹞，自学辅导法﹝﹞，练习法（习题或操作课）﹝√﹞，读书指导法﹝﹞，听说法﹝﹞，写生法﹝﹞，视唱教学方法教学手段PPT讨论、思考题、作业[[2]李素若，陈万华，游明坤主编.数据结构习题集及上机指导.北京:中国水利水参考文献电出版社，2014.教学过程及内容一、实验内容123．编写一个程序，使用两个链队q1和20个100以内的奇数和偶数，然后每行输出q1和q2二、实验说明1#100struct{front,rear;}2QNode{data;*next;}struct{rear;}三、实验指导1(SqQueue{*0;=(*Q)­>rear=0;1;(}Q)//判断队空{Q.front==Q.rear;}—1—教学过程及内容QueueFull(SqQueueQ)//判断队满{}EnQueue(SqQueue入队操作{if(QueueFull(*Q))0;//队列满Q­>data[Q­>rear]=e;1;}(SqQueue出队操作{if0;{1;}}2将Q{if0;1;}Q)//判断队空{Q.front==Q.rear;}入队操作{0;—2—教学过程及内容Q­>rear1;}DeQueue(LinkQueue出队操作{if(QueueEmpty(*Q))0;//若队列Q若Q1;}3{q1,q2;i<20||j<20){num=rand()%100;{i++;}{j++;}}—3—教学过程及内容{}printf("%3d%3d\n",i,j);0;}—4—2年月授课进度授课题目第9周，第2授课日期月日）实验五或主题)12教学目标12教学重点教学难点谈话法﹝﹞，实验法﹝√﹞，参观法﹝﹞，考察法﹝﹞，自学辅导法﹝﹞，练习法（习题或操作课）﹝√﹞，读书指导法﹝﹞，听说法﹝﹞，写生法﹝﹞，视唱教学方法教学手段PPT讨论、思考题、作业[[2]李素若，陈万华，游明坤主编.数据结构习题集及上机指导.北京:中国水利水参考文献电出版社，2014.教学过程及内容一、实验内容123．在实验1．在实验1二、实验指导1#．参考代码为：MaxSize100void{top=­1,k,j=0;ch=str[j];{{*)malloc(sizeof(BTNode));{{casecase}}}ch=str[j];}}void广义表输出二叉树—1—教学过程及内容{{printf("%c",b­>data);{printf("(");printf(",");printf(")");}}}2void中序递归遍历{if{中遍历左子树访问根结束中根遍历右子树}}3void非递归中序遍历{P=T;}为要么是叶子，要么是没有左子树printf("%3c",P­>data);}}P);}—2—2年月9授课进度第周，第2学时）授课日期月8日）授课题目实验五或主题)12教学目标1教学重点教学难点谈话法﹝﹞，实验法﹝√﹞，参观法﹝﹞，考察法﹝﹞，自学辅导法﹝﹞，练习法（习题或操作课）﹝√﹞，读书指导法﹝﹞，听说法﹝﹞，写生法﹝﹞，视唱教学方法教学手段PPT讨论、思考题、作业[[2]李素若，陈万华，游明坤主编.数据结构习题集及上机指导.北京:中国水利水参考文献电出版社，2014.教学过程及内容一、实验内容1234二、实验指导1求二叉树宽度{{Qu[MaxSize];结点的层次编号结点指针}front,rear;front=rear=0;{{根结点的层次编号为1队列不为空队头出队左孩子入队{}右孩子入队{}}—1—教学过程及内容{{n++;i++;}}0;}}2求二叉树b{{左子数的高度右子树的高度}}void{在T不为空的情况下{访问节点}}3—2—教学过程及内容voidPrintStack(SqStack使用线性栈辅助操作{printf("\n");}voidSqStack{{如果左指针和右指针同时为空，才说明该节点为叶子节点{}}}4void先序线索化{{{}前驱线索{后继线索}左子树线索化—3—教学过程及内容右子树线索化}}{thrt;NULL;建头结点右指针回指空二叉树{pre=thrt;先序遍历进行先序线索化}}voidthrt){先序遍历结果为：");{printf("%3c",p­>data);{printf("%3c",p­>data);}}printf("\n");}—4—2年月授课进度第周，第2学时）授课日期月日）授课题目实验六或主题)1.在对哈夫曼树进行理解的基础上，构造哈夫曼树，并用构造的哈夫曼树进行编2码和译码。教学目标教学重点教学难点谈话法﹝﹞，实验法﹝√﹞，参观法﹝﹞，考察法﹝﹞，自学辅导法﹝﹞，练习法（习题或操作课）﹝√﹞，读书指导法﹝﹞，听说法﹝﹞，写生法﹝﹞，视唱教学方法教学手段PPT讨论、思考题、作业[[2]李素若，陈万华，游明坤主编.数据结构习题集及上机指导.北京:中国水利水参考文献电出版社，2014.教学过程及内容一、实验内容1译码基本要求；（1）从终端读入字符集大小为n个字符和相应的n个权中。2）利用已建好的哈夫曼编码文件3（（用表2.1表2.1ISMYn能为负。二、实验指导####struct{}charstruct{s1;s2;}{—1—教学过程及内容i,s1=0,s2=0;HC;{fileanykeyexit!");exit(1);}{small!\n");exit(1);}{}{}{}*));*));cd[n­1]='\0';{start=n­1;cd[­­start]='0';—2—教学过程及内容cd[­­start]='1';strcpy(HC[i],&cd[start]);}fprintf(fp,"%c%s\n",ch[i],HC[i]);H1=HT;HC;*}{i,s1,s2;code;s1=1;s2=1;{s1=i;}{s1=i;}{s2=i;}{—3—教学过程及内容s2=i;}code.s1=s1;code.s2=s2;code;}void*{str[215],ch[50]={'\0'};HC=NULL;i=0,len,j,k;*));{fileanykeyexit!");exit(1);}{if(str[0]==0)break;len=strlen(str);ch[i]=str[0];*));memcpy(HC[i],&str[1],len­2);HC[i][len­2]=0;i++;}{if(Char_Code[i]==ch[j]){k+=strlen(HC[j]);}i++;}—4—教学过程及内容}{ch[50]={'\0'},Huffman_Code[1024]={'\0'};MY*)malloc((n+1)*sizeof(unsignedint));w[0]=0;weight,character:\n");{}0;}—5—2年月授课进度第周，第2学时）授课日期月日）授课题目实验七或主题)1.掌握图的邻接矩阵存储结构上的两种遍历图的方法，即深度优先遍历和广度优2先遍历。教学目标教学重点教学难点谈话法﹝﹞，实验法﹝√﹞，参观法﹝﹞，考察法﹝﹞，自学辅导法﹝﹞，练习法（习题或操作课）﹝√﹞，读书指导法﹝﹞，听说法﹝﹞，写生法﹝﹞，视唱教学方法教学手段PPT讨论、思考题、作业[[2]李素若，陈万华，游明坤主编.数据结构习题集及上机指导.北京:中国水利水参考文献电出版社，2014.教学过程及内容一、实验内容100设置邻接矩阵的最大顶点数设置图的顶点信息为字符struct{设置边上权值为整型图的顶点信息表图的邻接矩阵}//图的邻接矩阵表示结构定义二、实验指导1###100设置邻接矩阵的最大顶点数设置图的顶点信息为整型struct{设置边上权值为整型图的顶点信息表图的邻接矩阵}//图的邻接矩阵表示结构定义顶点访问标记向量linkqueuenode{};struct{*rear;}void{linkqueuenode));—1—教学过程及内容}QueueEmpty(linkqueq){if(q.front==q.rear)i=1;i=0;}voidx){linkqueuenode));{}{}}{isempty!\n");return(0);}{}}Q;voidCreateMGraph(MGraph建立图g2——教学过程及内容{i,j,k,w;创建有限图选0，无向图选(,)\n");,{getchar();scanf("%c",&(g­>vexs[i]));}图的遍历算法初始化该值为0{输入顶点号顶点号权值非网图权值为1):\n");if}}voidDFSM(MGraphi){对以邻接矩阵表示的图，以序号为i访问序号为i将序号为i扫描邻接矩阵的第iif((g­>edges[i][j]!=0)&&(!visited[j]))//寻找序号为i(设序号为j){printf("­­>");以序号为j}}voidstart){对以邻接矩阵表示的图，从最初顶点—3—教学过程及内容DFSM(g,start);}void{对以邻接矩阵表示的图，以序号为k访问序号为k的顶点将序号为k是结点设置为已访问过将序号为k的顶点入队{寻找序号为i{若序号为i访问序号为j的顶点设置序号为j将序号为j}}}voidstart){对以邻接矩阵表示的图，从最初顶点}void{申请图g建立图从顶点0从顶点0}—4—2年月7授课进度授课题目第周，第2学时）授课日期月6日）实验七或主题)1.掌握图的邻接表存储结构上的两种遍历图的方法，即深度优先遍历和广度优先2遍历。教学目标图的邻接表存储结构。教学重点教学难点谈话法﹝﹞，实验法﹝√﹞，参观法﹝﹞，考察法﹝﹞，自学辅导法﹝﹞，练习法（习题或操作课）﹝√﹞，读书指导法﹝﹞，听说法﹝﹞，写生法﹝﹞，视唱教学方法教学手段PPT讨论、思考题、作业[[2]李素若，陈万华，游明坤主编.数据结构习题集及上机指导.北京:中国水利水参考文献电出版社，2014.教学过程及内容一、实验内容100定义最大顶点数为100设置图的顶点信息为字符adjvex;边表表结点结构Node}顶点结点结构*firstedge;}struct{adjlist;顶点数和边数有向图为0，无向图为1}历。二、实验指导1###100定义最大顶点数为100设置图的顶点信息为字符adjvex;边表表结点结构Node}顶点结点结构*firstedge;}struct{adjlist;顶点数和边数有向图为0，无向图为1}顶点访问标记向量—1—教学过程及内容linkqueuenode{};struct{*rear;}void{linkqueuenode));}QueueEmpty(linkqueq){if(q.front==q.rear)i=1;i=0;}voidx){linkqueuenode));{}{}}{—2—教学过程及内容isempty!\n");return(0);}{}}Q;voidCreateALGraph(ALGraph建立图的邻接矩阵表示{创建有向图选，无向图选(,)\n");输入图的顶点数和边数,{scanf("%c",&(g­>adjlist[i].vertex));}输入构成边或弧：顶点号顶点号有向图{{}}—3—教学过程及内容{无向图{}}}void{对以邻接表表示的图，以序号为i访问序号为i的顶点将序号为i{{}}}voidstart){对以邻接表表示的图，从最初顶点start}voidBFSAL(ALGraph{对以邻接表表示的图，以序号为i—4—教学过程及内容访问序号为k的顶点将序号为k是结点设置为已访问过将序号为k的顶点入队{{{访问的顶点}}}}voidstart){对以邻接矩阵表示的图，从最初顶点}void{ALGraph*g=(ALGraph*)malloc(sizeof(ALGraph));从顶点0出发进行深度优先搜索从顶点0}—5—2年月授课进度第周，第2学时）授课日期月日）授课题目实验八查找或主题)123．掌握二叉排序树、AVL树的查找、插入、删除、建立算法的思想及程序实现。教学目标12教学重点教学难点谈话法﹝﹞，实验法﹝√﹞，参观法﹝﹞，考察法﹝﹞，自学辅导法﹝﹞，练习法（习题或操作课）﹝√﹞，读书指导法﹝﹞，听说法﹝﹞，写生法﹝﹞，视唱教学方法教学手段PPT讨论、思考题、作业[[2]李素若，陈万华，游明坤主编.数据结构习题集及上机指导.北京:中国水利水参考文献电出版社，2014.教学过程及内容一、实验内容1{36210185749}关键字52{12345678910}查找关键字934（（1:%P(其中P=13),2:%P(其中P=13),编写程序建立哈希查找表，运行程序在表中查找6899。二、实验指导1##struct{}SeqSearch(SqList{return(­1);}{R[]={3,6,2,10,1,8,5,7,4,9};if(i==­1)Found!\n");0;}—1—教学过程及内容2##struct{}R[],int{{{}}if(find==0)return(­1);}{R[]={1,2,3,4,5,6,7,8,9,10};if(i==­1)Found!\n");0;}3##—2—教学过程及内容左右孩子指针Node}在二叉排序树T中，查找关键字值K。找到将该结点指针赋给q返回，函数返回1/若未找到，q返回查找过程中最后结点指针，函数返回0为p的双亲，初始为空二叉排序树为空，查找失败1;}找到{f=p;p=p­>rchild;}}*q=f;return0;//p}void{查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子,在此插入新的结点。作为根结点插入}若T中无则将其作为q{作为q的左孩子插入q­>rchild=p;作为q的右孩子插入}}}void二叉树中序遍历{{—3—教学过程及内容}}void{q,s,ps,pc;指向q的双亲查找K结点，使q//找到if(K<q­>key){ps=q;q=q­>lchild;}//若大于，走右子树}没有找到保存要删除结点要删除的结点有两棵子树转换为(1)、(2)找到左子树最右下结点、s值互换,q指向s}指向q的孩子结点，最多只有1要删除的是根结点if(q==ps­>lchild)ps­>lchild=pc;//q是的左孩子是的右孩子free(q);}{");srand((int)time(0));{t=rand()%50;}printf("\n");—4—教学过程及内容printf("\n");0;}4（1）###M13}Hash(int散列函数{(int)(key%M);}构造散列表函数{i=Hash(k);确定链表头指针存放位置给结点分配空间}查找函数{i=Hash(k);链表头指针{return—5—教学过程及内容NULL;}}void{*p,*h[12];数据存入数组从数组中取数，依次加入散列表输出散列表中元素{printf("\n");}输入待查数据查找*/找到元素未找到元素!");}（2）####<string.h>MAX50NULLKEY­1struct{}void{}Hash(int{—6—教学过程及内容}ht,{{for(i=1;i<=MAX­1;i++){{}}}1;}{InsertHash(ht,record[i]);1;}{NULLKEY;用线性探测再散列法解决冲突{i;intpi;—7—教学过程及内容for(i=1;i<=MAX­1;i++){NULLKEY;if(ht[pi].key_num==key)pi;}}NULLKEY;}{=NULLKEY;ht;printf("\n）printf("\nprintf("\nPleasethekeySearch:\n");:0;}—8—2年月授课进度第周，第2学时）授课日期月日）授课题目实验九排序或主题)12教学目标12教学重点教学难点谈话法﹝﹞，实验法﹝√﹞，参观法﹝﹞，考察法﹝﹞，自学辅导法﹝﹞，练习法（习题或操作课）﹝√﹞，读书指导法﹝﹞，听说法﹝﹞，写生法﹝﹞，视唱教学方法教学手段PPT讨论、思考题、作业[[2]李素若，陈万华，游明坤主编.数据结构习题集及上机指导.北京:中国水利水参考文献电出版社，2014.教学过程及内容一、实验内容1（（（（（（（123456723．编写算法实现一个最多4二、实验指导1#####．2{关键字码}s[50][2];/*辅助栈voidR[],int{}void用直接插入排序法对进行排序{temp;for(i=0;i<=n­2;i++){j=i;—1—教学过程及内容(temp.key<=R[j].key&&j>­1){R[j+1]=R[j];j­­;}}}void{++i)<r[i­dk].key)将r[i]{&&j­=dk)记录后移=插入到正确位置}}voiddlta[],int希尔排序{//按增量序列对顺序表Lk;一趟增量为的插入排序}void{Sleep(1000);NULL));}voidR[],int冒泡排序{—2—教学过程及内容{{{}}}}r[],int快