数据结构实验课教案_数据结构实验二学习
数据结构实验课教案由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构实验二学习”。
授课教案
（2016—2017学年度第一学期）
课程名称： 课程编码： 总学时： 课程类别：
任课教师： 开课单位： 职称： 授课专业： 授课班级：
数据结构 B13040009A 总学分： 专业课 李素若 计算机工程学院
教授 计算机科学与技术
2015级计算机科学与技术专业1、2班 授课进度第3周，第6次课（2学时）授课题目
(教学章、节实验一线性表的顺序存储结构 或主题)
授课日期
016年9月14日（9 2
月13日）
.掌握线性表顺序存储结构的特点：逻辑上相邻的数据元素其物理位置上也相邻。1 2.掌握线性表顺序存储结构的插入、删除操作特点移动操作。
教学
目标
1.线性表的顺序存储特点
教学 2.线性表的顺序存储的基本算法 重点
1.线性表的顺序存储的基本算法
教学 难点
请选择你授课时所采用的教学方法（在括号中画“√”）：
讲授法﹝﹞，讨论法﹝﹞，演示法﹝﹞，案例法﹝﹞，发现法﹝﹞，探究法﹝﹞，教学
谈话法﹝﹞，实验法﹝√﹞，参观法﹝﹞，考察法﹝﹞，自学辅导法﹝﹞，练习
方法
法（习题或操作课）﹝√﹞，读书指导法﹝﹞，听说法﹝﹞，写生法﹝﹞，视唱 法﹝﹞，工序法（技能课）﹝﹞，实习作业法﹝﹞，其他﹝﹞ 教学
实物﹝﹞，多媒体﹝﹞，投影﹝﹞，影像﹝﹞，CAI课件﹝﹞，PPT﹝√﹞，标本
手段
﹝﹞，挂图﹝﹞，模型﹝﹞，其他﹝﹞ 讨 论、思考 题、作业
[ 1]李素若，陈万华，游明坤主编.数据结构.北京:中国水利水电出版社，2014.[ 2]李素若，陈万华，游明坤主编.数据结构习题集及上机指导.北京:中国水利水 请选择你授课时所采用的教学手段（在括号中画“√”）：
参考
电出版社，2014.文献
教学过程及内容
一、实验内容
．输入一组整型元素序列，建立顺序表。1 2 ．遍历该顺序表。3 ．在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。．实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。4 ．判断该顺序表中元素是否对称,对称返回1,否则返回0。5 ．输入整型元素序列利用有序表插入算法建立一个有序表。6 ．利用实验6建立两个递增有序表并把它们合并成一个递增有序表。7
二、实验指导
1．参考程序为：
voidCreateSqList(SqList*L){ intn,i; do{ printf(“请输入数据元素的个数:”);
scanf(“%d”,&n);
if(nelem[i])); L>length=n;
} 2 ．参考程序为：
voidPrintList(SqListL){ inti;
for(i=0;i
intFindelems(SqListL,ElemTypee){ inti;
for(i=0;i
return0;
} 4．分析：从顺序表表头开始扫描，当数据元素为偶数时就从该数开始往后查找，一旦
— 1—
教学过程及内容
找到奇数，则将该偶数与此奇数交换。顺序表中所有数据全部扫描结束后，所有奇数就排列 在表的前端。参考程序为：
voidChangeVal(SqList*L){ inti,j,temp;
for(i=0;ilength;i++){ if(L>elem[i]%2==0){ for(j=i+1;jlength;j++){
if(L>elem[j]%2!=0){
temp=L>elem[i];
L>elem[i]=L>elem[j]; L>elem[j]=temp; break; } } if(j==L>length)break; } } } 5．参考程序为：
intYesNo_Symmetry(SqListL){ inti,j;
j=L.length1; for(i=0;i
return0; } return1;
} 6 ．参考程序为：
voidInsert_OrderList(SqList*L,intx){ inti,j;
for(i=0;ilength;i++)if(L>elem[i]>x)break; for(j=L>length1;j>=i;j)
— 2—
教学过程及内容
L>elem[j+1]=L>elem[j]; L>elem[i]=x; L>length++;
} voidCreate_OrderList(SqList*L){ intn,i,input; do{ printf(“请输入数据元素的个数:”); scanf(“%d”,&n);
if(n
while(n
Insert_OrderList(L,input); } } 7 ．参考程序为：
SqList*Merge_OrderList(SqListA,SqListB)//将有序顺序表A和B合并到有序顺序表C中返回 { inti=0,j=0,k=0;
SqList*C=(SqList*)malloc(sizeof(SqList)); C>length=0;
while(j
C>elem[i++]=A.elem[j++]; else C>elem[i++]=B.elem[k++];
} if(j==A.length)
while(kelem[i++]=B.elem[k++]; if(k==B.length)while(jelem[i++]=A.elem[j++]; C>length=i; returnC;
}
— 3— 授课进度第4周，第8次课（2学时）授课题目
(教学章、节实验二单向链表 或主题)
授课日期
016年9月21日（9 2
月20日）
．掌握线性链表的操作特点，即指针是逻辑关系的映像。1 ．掌握动态产生单链表的方法。2 3 ．熟练掌握单链表的插入、删除操作特点，即指针赋值的先后次序。
教学
目标
1．掌握动态产生单链表的方法。
教学 2．熟练掌握单链表的插入、删除操作特点，即指针赋值的先后次序。重点
1．熟练掌握单链表的插入、删除操作特点，即指针赋值的先后次序。
教学 难点
请选择你授课时所采用的教学方法（在括号中画“√”）：
讲授法﹝﹞，讨论法﹝﹞，演示法﹝﹞，案例法﹝﹞，发现法﹝﹞，探究法﹝﹞，教学
谈话法﹝﹞，实验法﹝√﹞，参观法﹝﹞，考察法﹝﹞，自学辅导法﹝﹞，练习
方法
法（习题或操作课）﹝√﹞，读书指导法﹝﹞，听说法﹝﹞，写生法﹝﹞，视唱 法﹝﹞，工序法（技能课）﹝﹞，实习作业法﹝﹞，其他﹝﹞ 教学
实物﹝﹞，多媒体﹝﹞，投影﹝﹞，影像﹝﹞，CAI课件﹝﹞，PPT﹝√﹞，标本
手段
﹝﹞，挂图﹝﹞，模型﹝﹞，其他﹝﹞ 讨 论、思考 题、作业
[ 1]李素若，陈万华，游明坤主编.数据结构.北京:中国水利水电出版社，2014.[ 2]李素若，陈万华，游明坤主编.数据结构习题集及上机指导.北京:中国水利水 请选择你授课时所采用的教学手段（在括号中画“√”）：
参考
电出版社，2014.文献
教学过程及内容
一、实验内容
．随机产生或键盘输入一组元素，建立一个带头结点的单向链表（无序）。1 ．遍历单向链表。2 3 ．把单向链表中元素逆置（不允许申请新的结点空间）。．在单向链表中删除所有的偶数元素结点。4 5 ．编写在非递减有序链表中插入一个元素使链表元素仍有序的函数，并利用该函数建 立一个非递减有序单向链表。
．利用实验5建立两个递增有序单向链表，然后合并成一个递增链表。6 7 ．利用实验1建立的链表，实现将其分解成两个链表，其中一个全部为奇数，另一个 全部为偶数（尽量利用已知的存储空间）。
二、实验指导
1．参考程序为：
LinkListCreateListH(void)//头插法产生带头结点单链表 { intch;
LinkListhead=(LinkList)malloc(sizeof(LNode)); LinkLists;
head>next=NULL;
while(scanf(“%d”,&ch)==1)//输入数据类型错误时结束单链表的生成 { s=(LinkList)malloc(sizeof(LNode)); s>data=ch;
s>next=head>next; head>next=s; } returnhead;
} LinkListCreateListRand(void)//利用随机函数产生带头结点单链表（头插法）{ intch,i;
LinkListhead=(LinkList)malloc(sizeof(LNode)); LinkLists;
head>next=NULL;
srand((unsigned)time(NULL));
printf(“PleaseinputCreateNnmbers:”); scanf(“%d”,&ch);
for(i=0;i
s>data=rand()%50;//随机产生0~49之间的数
— 1—
教学过程及内容
s>next=head>next; head>next=s; } returnhead; } 2 ．参考程序为：
voidPrintLinkList(LNodeL){ LinkListp; p=L.next; while(p){ printf(“%d”,p>data); p=p>next; } printf(“n”); } 3．参考程序为：
voidInverse_set(LinkListhead){ LNode*r,*m=NULL,*p; p=head>next; while(p!=NULL){ r=m;m=p; p=p>next; m>next=r; } head>next=m; } 4．参考程序为：
voidDelEvenLinkList(LinkListhead){ LinkListq,p; p=head>next; q=head;
while(p){ if(p>data%2==0){ q>next=p>next; free(p);
— 2—
教学过程及内容
p=q>next; } else { q=p;
p=p>next; } } } 5 ．参考程序为：
voidInsertIncr(LinkListhead,ElemTypex)//将结点插入递增的单链表 { LinkListq,p,s;
s=(LinkList)malloc(sizeof(LNode)); s>data=x; q=head;
p=head>next;
while(p&&p>data
p=p>next; } s>next=q>next; q>next=s;
} LinkListCreateListIncr(void)//通过调用插入有序链表函数生成递增单链表 { intch;
LinkListhead=(LinkList)malloc(sizeof(LNode)); LinkLists;
head>next=NULL;
while(scanf(“%d”,&ch)==1)//输入数据类型错误时结束单链表的生成 InsertIncr(head,ch); returnhead; } 6 ．参考程序为：
LinkListLinkListCat(LinkListhead1,LinkListhead2){ LinkListh1,h2,h;
LinkListhead=(LinkList)malloc(sizeof(LNode)); head>next=NULL;
— 3—
教学过程及内容
h1=head1>next; h2=head2>next; h=head; while(h1&&h2){ if(h1>datadata){ h>next=h1; h=h>next;
h1=h1>next; } else { h>next=h2; h=h>next; h2=h2>next; } } if(h1)h>next=h1; if(h2)h>next=h2; returnhead; } 7 ．参考程序为： # include # include # include typedefintElemType;//元素类型 typedefstructLNode { ElemTypedata; structLNode*next; } LNode,*LinkList;
voidPrintLinkList(LNodeL){ LinkListp;
p=L.next; while(p){ printf(“%d”,p>data); p=p>next;
— 4—
教学过程及内容
} printf(“n”);
} voidDecoLinkList(LNodehead,LinkListhead1,LinkListhead2)//将单链表head拆分奇数链head1和偶数链head2 { LinkListh,h1,h2;
h=head.next; h1=head1; h2=head2; while(h){ if(h>data%2==0){ h2>next=h; h=h>next; h2=h2>next; } else { h1>next=h; h=h>next; h1=h1>next; } } h1>next=NULL; h2>next=NULL; } main(){ LinkListhead;
LinkListhead1=(LinkList)malloc(sizeof(LNode)); LinkListhead2=(LinkList)malloc(sizeof(LNode)); head=CreateListIncr();
PrintLinkList(*head);
DecoLinkList(*head,head1,head2); PrintLinkList(*head1); PrintLinkList(*head2);
}
— 5— 授课进度第5周，第10次课（2学时）授课题目
(教学章、节实验三栈的存储及基本运算 或主题)
授课日期
016年9月28日（9 2
月27日）
.掌握栈这种数据结构特性及其主要存储结构，并能在现实生活中灵活运用。1 2.了解和掌握递归程序设计的基本原理和方法。
教学
目标
.掌握栈的两种存储结构 1.栈的基本运算 教学 2.了解栈在递归函数中的作用 重点 3.掌握栈的两种存储结构 1 教学 2.栈的基本运算 难点
请选择你授课时所采用的教学方法（在括号中画“√”）：
讲授法﹝﹞，讨论法﹝﹞，演示法﹝﹞，案例法﹝﹞，发现法﹝﹞，探究法﹝﹞，教学
谈话法﹝﹞，实验法﹝√﹞，参观法﹝﹞，考察法﹝﹞，自学辅导法﹝﹞，练习
方法
法（习题或操作课）﹝√﹞，读书指导法﹝﹞，听说法﹝﹞，写生法﹝﹞，视唱 法﹝﹞，工序法（技能课）﹝﹞，实习作业法﹝﹞，其他﹝﹞ 教学
实物﹝﹞，多媒体﹝﹞，投影﹝﹞，影像﹝﹞，CAI课件﹝﹞，PPT﹝√﹞，标本
手段
﹝﹞，挂图﹝﹞，模型﹝﹞，其他﹝﹞ 讨 论、思考 题、作业
[ 1]李素若，陈万华，游明坤主编.数据结构.北京:中国水利水电出版社，2014.[ 2]李素若，陈万华，游明坤主编.数据结构习题集及上机指导.北京:中国水利水 请选择你授课时所采用的教学手段（在括号中画“√”）：
参考
电出版社，2014.文献
教学过程及内容
一、实验内容
．采用顺序存储实现栈的初始化、入栈、出栈操作。1 2 ．采用链式存储实现栈的初始化、入栈、出栈操作。3 ．写一个程序，将输入的十进制数据M转换为八进制数据M8，将其调试通过。在此 基础上修改程序，实现十进制数据M向N进制（2或8或16）的转换。（1）采用顺序存储结构实现栈。（2）采用链表结构实现栈。
二、实验指导
．参考程序为： 1 # include # include # defineStack_Size100 # defineOK 1 # defineERROR 0 typedefintElemType; typedefstructStack { ElemTypeelem[Stack_Size]; inttop;
//用来存放栈中元素的一维数组
//用来存放栈顶元素的下标
} SqStack;
intInitStack(SqStack**s)//初始化顺序栈 {(*s)=(SqStack*)malloc(sizeof(SqStack));
if((*s)==NULL)returnERROR;(*s)>top=1; returnOK;
} intEmptyStack(SqStacks)//判断栈空 { if(s.top==1)
{ printf(“stackisempty!n”); returnOK; } returnERROR;
} intGetTop(SqStacks,int*e)//取栈顶元算 { if(EmptyStack(s))returnERROR;
*e=s.elem[s.top];
— 1—
教学过程及内容
returnOK;
} intPush(SqStack*s,inte)//入栈 { if(s>top==Stack_Size1)
{ printf(“stackisfull!n”); returnERROR; } s>top++;
s>elem[s>top]=e; returnOK;
} voidPrintStack(SqStacks)//打印栈中数据 { inti;
for(i=0;i
} intPop_Stack(SqStack*s,int*e)//出栈 { if(EmptyStack(*s))
returnERROR; *e=s>elem[s>top]; s>top; returnOK; } voidmain(){ intcord,e,x,y; SqStack*s; do { printf(“nMainMenun”); printf(“1CreatStackn”); printf(“2GetTopElementn”); printf(“3Pushn”); printf(“4Popn”); printf(“5Printn”); printf(“6quitn”); scanf(“%d”,&cord);
— 2—
教学过程及内容
switch(cord){ case1:
InitStack(&s); break; case2:
if(GetTop(*s,&y))
printf(“StackTop=[%d]n”,y); break; case3:
printf(“Pleaseinputpushelement:”); scanf(“%d”,&e); Push(s,e); break; case4:
if(Pop_Stack(s,&x))
printf(“Popstack=[%d]n”,x); break; case5:
PrintStack(*s); break;
case6:
return;
} } while(cord # include # defineStack_Size100 # # defineOK 1 # defineERROR 0 typedefintElemType; typedefstructstacknode { ElemTypedata;
structstacknode*next; } StackNode; typedefstruct { StackNode*top;/*栈顶指针*/ LinkStack; }
— 3—
教学过程及内容
voidInitStack(LinkStack*s)//初始化栈 { s>top=NULL;
} intEmptyStack(LinkStacks)//判断栈空 { if(s.top==NULL)returnOK;
elsereturnERROR;
} intGetTop(LinkStacks,int*e)//取栈顶元素 { if(EmptyStack(s))returnERROR; *e=s.top>data;
} voidPush(LinkStack*s,inte)//入栈 { StackNode*p=(StackNode*)malloc(sizeof(StackNode));
p>data=e;
p>next=s>top; s>top=p;
} intPop_Stack(LinkStack*s,int*e)//出栈 { StackNode*p;
if(EmptyStack(*s))returnERROR;
p=s>top; *e=p>data; s>top=p>next; free(p); returnOK;
} voidPrintStack(LinkStacks)//打印栈中元素 { StackNode*p=s.top; while(p){ printf(“%d”,p>data); p=p>next; } } voidmain()
— 4—
教学过程及内容
{ intcord,e,x,y; LinkStacks; do { printf(“nMainMenun”); printf(“1CreatStackn”); printf(“2GetTopElementn”); printf(“3Pushn”); printf(“4Popn”); printf(“5Printn”); printf(“6quitn”); scanf(“%d”,&cord); switch(cord){ case1:
InitStack(&s); break; case2:
if(GetTop(s,&y))
printf(“StackTop=[%d]n”,y); break; case3:
printf(“Pleaseinputpushelement:”); scanf(“%d”,&e); Push(&s,e); case4: break;
if(Pop_Stack(&s,&x))
printf(“Popstack=[%d]n”,x); break; case5:
PrintStack(s); break;
case6:
return;
} } while(cord
— 5—
教学过程及内容
voidConversion(SqStack*S){ intN,n1,t;
printf(“输入一个十进制数字:n”);
scanf(“%d”,&N);//输入一个十进制数字
printf(“输入要转换的n进制数字（2、8、16):n”); scanf(“%d”,&n1);//输入要转换的进制
while(N){ Push(S,N%n1); N=N/n1; } printf(“该数转化为%d进制数为:t”,n1); if(n1==16){ while(!EmptyStack(*S)){ Pop_Stack(S,&t); if(t==10){printf(“A”);continue;} if(t==11){printf(“B”);continue;} if(t==12){printf(“C”);continue;} if(t==13){printf(“D”);continue;} if(t==14){printf(“E”);continue;} if(t==15){printf(“F”);continue;} printf(“%d”,t);
} } else PrintStack(*S); } voidmain(){ SqStack*S; InitStack(&S); Conversion(S); }（2）
voidConversion(LinkStack*S){ intN,n1,t;
printf(“输入一个十进制数字:n”);
scanf(“%d”,&N);//输入一个十进制数字
— 6—
教学过程及内容
printf(“输入要转换的n进制数字（2、8、16):n”); scanf(“%d”,&n1);//输入要转换的进制 while(N){ Push(S,N%n1); N=N/n1; } printf(“该数转化为%d进制数为:t”,n1); if(n1==16){ while(!EmptyStack(*S)){ Pop_Stack(S,&t); if(t==10){printf(“A”);continue;} if(t==11){printf(“B”);continue;} if(t==12){printf(“C”);continue;} if(t==13){printf(“D”);continue;} if(t==14){printf(“E”);continue;} if(t==15){printf(“F”);continue;} printf(“%d”,t);
} } else PrintStack(*S); } voidmain(){ LinkStackS; InitStack(&S); Conversion(&S); }
— 7— 授课进度第8周，第14次课（2学时）授课题目
(教学章、节实验四队列 或主题)
授课日期
016年10月19日（10 2
月18日）
.掌握队列这种数据结构的逻辑特性及其主要存储结构。1 2.在简单情况下会使用顺序结构的实现队列，熟练掌握循环队列的使用。.在复杂情况下会使用链表结构的队列，并能在现实生活中灵活运用。3 教学
目标
1.熟练掌握循环队列的使用。
教学 2.在复杂情况下会使用链表结构的队列。重点
1.链队列的使用。
教学 难点
请选择你授课时所采用的教学方法（在括号中画“√”）：
讲授法﹝﹞，讨论法﹝﹞，演示法﹝﹞，案例法﹝﹞，发现法﹝﹞，探究法﹝﹞，教学
谈话法﹝﹞，实验法﹝√﹞，参观法﹝﹞，考察法﹝﹞，自学辅导法﹝﹞，练习
方法
法（习题或操作课）﹝√﹞，读书指导法﹝﹞，听说法﹝﹞，写生法﹝﹞，视唱 法﹝﹞，工序法（技能课）﹝﹞，实习作业法﹝﹞，其他﹝﹞ 教学
实物﹝﹞，多媒体﹝﹞，投影﹝﹞，影像﹝﹞，CAI课件﹝﹞，PPT﹝√﹞，标本
手段
﹝﹞，挂图﹝﹞，模型﹝﹞，其他﹝﹞ 讨 论、思考 题、作业
[ 1]李素若，陈万华，游明坤主编.数据结构.北京:中国水利水电出版社，2014.[ 2]李素若，陈万华，游明坤主编.数据结构习题集及上机指导.北京:中国水利水 请选择你授课时所采用的教学手段（在括号中画“√”）：
参考
电出版社，2014.文献
教学过程及内容
一、实验内容
．采用顺序存储实现循环队列的初始化、入队、出队操作。1 2 ．采用链式存储实现队列的初始化、入队、出队操作。3 ．编写一个程序，使用两个链队q1和q2，用来分别存储由计算机随机产生的20个 100以内的奇数和偶数，然后每行输出q1和q2的一个值，即奇数和偶数配对输出，直到任 一队列为空为止。
二、实验说明
．循环队列类型采用如下结构： 1 defineMAXSIZE100//最大队列长度 # typedefintElemType; typedefstruct{ ElemTypedata[MAXSIZE]; intfront,rear;//队头、队尾指针
SqQueue; } ．链队类型采用如下结构： 2 typedefstructQNode { ElemTypedata; structQNode*next;
QNode,*QueuePtr; } typedefstruct { QueuePtrfront; QueuePtrrear;
LinkQueue; }
三、实验指导
1．参考程序为：
intInitQueue(SqQueue**Q)//初始化循环队列 { * Q=(SqQueue*)malloc(sizeof(SqQueue)); if(!(*Q))
return0;
*Q)>front=(*Q)>rear=0;(return1;
} intQueueEmpty(SqQueueQ)//判断队空 { returnQ.front==Q.rear;
}
— 1—
教学过程及内容
intQueueFull(SqQueueQ)//判断队满 { return(Q.rear+1)%MAXSIZE==Q.front;
} intEnQueue(SqQueue*Q,ElemTypee)//入队操作 { if(QueueFull(*Q))
/队列满 return0; /Q>data[Q>rear]=e;
Q>rear=(Q>rear+1)%MAXSIZE; return1;
} intDeQueue(SqQueue*Q,ElemType*e)//出队操作 { if(QueueEmpty(*Q))return0; else { *e=Q>data[Q>front];
Q>front=(Q>front+1)%MAXSIZE; return1; } } 2 ．参考程序为：
intInitQueue(LinkQueue*Q)//将Q初始化为一个空的链队列 { Q>front=Q>rear=(QueuePtr)malloc(sizeof(QNode));
if(Q>front==NULL)
return0;
Q>front>next=NULL; return1;
} intQueueEmpty(LinkQueueQ)//判断队空 { returnQ.front==Q.rear;
} intEnQueue(LinkQueue*Q,ElemTypee)//入队操作 { QueuePtrp;
p=(QueuePtr)malloc(sizeof(QNode)); if(!p)
return0;
— 2—
教学过程及内容
p>data=e;
p>next=NULL; Q>rear>next=p; Q>rear=p; return1;
} intDeQueue(LinkQueue*Q,ElemType*e)//出队操作 { QueuePtrp;
if(QueueEmpty(*Q))return0;//若队列Q为空队列 p=Q>front>next;
*e=p>data;
Q>front>next=p>next; if(Q>rear==p)
Q>rear=Q>front;//若Q只有一个结点 free(p); return1;
} 3 ．参考程序为： intmain(){ LinkQueueq1,q2; inti=0,j=0,num; InitQueue(&q1); InitQueue(&q2);
srand((unsigned)time(NULL)); while(i
— 3—
教学过程及内容
{ DeQueue(&q1,&i);DeQueue(&q2,&j); printf(“%3d%3dn”,i,j);
} free(q1.front); free(q2.front); return0;
}
— 4— 授课进度 授课题目 第9周，第16次课（2学时）授课日期
016年10月26日（10 2
月25日）
(教学章、节实验五二叉树（Ⅰ）或主题)．掌握二叉树的存储实现。1 ．掌握二叉树的遍历思想。2 教学
目标
．掌握二叉树的存储实现。1 ．掌握二叉树的遍历思想。教学 2 重点
1.掌握二叉树的遍历思想。
教学 难点
请选择你授课时所采用的教学方法（在括号中画“√”）：
讲授法﹝﹞，讨论法﹝﹞，演示法﹝﹞，案例法﹝﹞，发现法﹝﹞，探究法﹝﹞，教学
谈话法﹝﹞，实验法﹝√﹞，参观法﹝﹞，考察法﹝﹞，自学辅导法﹝﹞，练习
方法
法（习题或操作课）﹝√﹞，读书指导法﹝﹞，听说法﹝﹞，写生法﹝﹞，视唱 法﹝﹞，工序法（技能课）﹝﹞，实习作业法﹝﹞，其他﹝﹞ 教学
实物﹝﹞，多媒体﹝﹞，投影﹝﹞，影像﹝﹞，CAI课件﹝﹞，PPT﹝√﹞，标本
手段
﹝﹞，挂图﹝﹞，模型﹝﹞，其他﹝﹞ 讨 论、思考 题、作业
[ 1]李素若，陈万华，游明坤主编.数据结构.北京:中国水利水电出版社，2014.[ 2]李素若，陈万华，游明坤主编.数据结构习题集及上机指导.北京:中国水利水 请选择你授课时所采用的教学手段（在括号中画“√”）：
参考
电出版社，2014.文献
教学过程及内容
一、实验内容
1．数据域为字符的一棵二叉树用广义表形式输入，创建一个采用二叉链表存储的二叉 树，并按广义表的形式输出这棵二叉树。
．在实验1的基础上完成这棵二叉树的中序遍历的递归算法。2 ．在实验1的基础上完成这棵二叉树的中序遍历的非递归算法。3
二、实验指导
．参考代码为： 1 # defineMaxSize100 voidCreateBTNode(BTree*b,char*str)//广义表形式输入二叉树，按二叉链表存储二叉树 { BTNode*St[MaxSize],*p=NULL; inttop=1,k,j=0;
charch; *b=NULL; ch=str[j]; while(ch!=' '){ switch(ch){ case'(':top++;St[top]=p;k=1;break; case')':top;break; case',':k=2;break; default:p=(BTNode*)malloc(sizeof(BTNode));
p>data=ch;p>lchild=p>rchild=NULL; if(*b==NULL)*b=p; else { switch(k){ case1:St[top]>lchild=p;break; case2:St[top]>rchild=p;break; } } } j++;
ch=str[j]; } } voidDispBTNode(BTNode*b)//广义表输出二叉树
— 1—
教学过程及内容
{ if(b!=NULL){ printf(“%c”,b>data);
if(b>lchild!=NULL||b>rchild!=NULL){ printf(“(”);
DispBTNode(b>lchild);
if(b>rchild!=NULL)printf(“,”); DispBTNode(b>rchild); printf(“)”); } } } 2 ．参考代码为：
voidInOrder(BTreeT)//中序递归遍历 { if(T){ InOrder(T>lchild);/*中遍历左子树*/ printf(“%3c”,T>data);/*访问根结束*/
InOrder(T>rchild); } } 3 ．参考代码为：
voidInOrder1(BTreeT)//非递归中序遍历 { SqStack*S;BTreeP=T;
InitStack(&S); do{
/*从树或子树根出发往左到叶子*/ while(P){ Push(S,P); P=P>lchild; } if(S>top!=1){/*P为NULL要么是叶子，要么是没有左子树*/
Pop(S,&P);
printf(“%3c”,P>data); P=P>rchild;
} } while((S>top!=1)||P); }
/*中根遍历右子树*/
— 2— 授课进度第11周，第20次课（2学时）授课题目
(教学章、节实验五二叉树（Ⅱ）或主题)．二叉树的常用算法。1 2 ．二叉树线索化及遍历。
授课日期
016年11月9日（11 2
月8日）
教学 目标
1．二叉树的常用算法。
教学 重点
1.二叉树的常用算法。
教学 难点
请选择你授课时所采用的教学方法（在括号中画“√”）：
讲授法﹝﹞，讨论法﹝﹞，演示法﹝﹞，案例法﹝﹞，发现法﹝﹞，探究法﹝﹞，教学
谈话法﹝﹞，实验法﹝√﹞，参观法﹝﹞，考察法﹝﹞，自学辅导法﹝﹞，练习
方法
法（习题或操作课）﹝√﹞，读书指导法﹝﹞，听说法﹝﹞，写生法﹝﹞，视唱 法﹝﹞，工序法（技能课）﹝﹞，实习作业法﹝﹞，其他﹝﹞ 教学
实物﹝﹞，多媒体﹝﹞，投影﹝﹞，影像﹝﹞，CAI课件﹝﹞，PPT﹝√﹞，标本
手段
﹝﹞，挂图﹝﹞，模型﹝﹞，其他﹝﹞ 讨 论、思考 题、作业
[ 1]李素若，陈万华，游明坤主编.数据结构.北京:中国水利水电出版社，2014.[ 2]李素若，陈万华，游明坤主编.数据结构习题集及上机指导.北京:中国水利水 请选择你授课时所采用的教学手段（在括号中画“√”）：
参考
电出版社，2014.文献
教学过程及内容
一、实验内容
．求二叉树的宽度。1 2 ．求任意二叉树中第一条最长的路径长度，并输出此路径上各结点的值。．输出二叉树中从每个叶子结点到根结点的路径。3 4 ．建立前序线索二叉树，并实现前序遍历。
二、实验指导
1．参考代码为：
intBTWidth(BTNode*b)//求二叉树宽度 { struct {
/结点的层次编号 intlno; /BTNode*p; //结点指针
Qu[MaxSize];//定义顺序非循环队列 } intfront,rear;
//定义队首和队尾指针
intlnum,max,i,n;
front=rear=0;//置队列为空
if(b!=NULL){ rear++;
//根结点指针入队 Qu[rear].p=b;
Qu[rear].lno=1; //根结点的层次编号为1
//队列不为空 while(rear!=front)
{ front++;
b=Qu[front].p;
//队头出队 //左孩子入队 lnum=Qu[front].lno; if(b>lchild!=NULL){ rear++; Qu[rear].p=b>lchild; Qu[rear].lno=lnum+1; } if(b>rchild!=NULL){ rear++; Qu[rear].p=b>rchild; Qu[rear].lno=lnum+1; } }
— 1— //右孩子入队
教学过程及内容
max=0;lnum=1;i=1; while(i
while(i
/求每层的结点数 n++;i++; /} lnum=Qu[i].lno; if(n>max)max=n; } returnmax; } else return0; } 2 ．参考代码为：
intBTNodeDepth(BTNode*b)//求二叉树b的深度 { intlchilddep,rchilddep;
if(b==NULL)return(0); else { lchilddep=BTNodeDepth(b>lchild);//左子数的高度 rchilddep=BTNodeDepth(b>rchild);//右子树的高度
return(lchilddep>rchilddep)?(lchilddep+1):(rchilddep+1); } } voidLong(BTreeT){ if(T!=NULL)//在T不为空的情况下
{ printf(“%3c”,T>data);//访问节点
if(BTNodeDepth(T>lchild)>BTNodeDepth(T>rchild))//判断往左走还是往右走 Long(T>lchild); else Long(T>rchild); } } 3．参考代码为：
— 2—
教学过程及内容
voidPrintStack(SqStack*S)//使用线性栈辅助操作 { inti;
for(i=0;itop;i++)printf(“%3c”,S>elem[i]); printf(“n”);
} voidAllPath(BTreeT,SqStack*S)//输出二叉树上从根到所有叶子结点的路径 { charch; if(T){ Push(S,T>data); if(!T>lchild&&!T>rchild)//如果左指针和右指针同时为空，才说明该节点为叶子节
点
PrintStack(S); else { AllPath(T>lchild,S); AllPath(T>rchild,S); } Pop(S,&ch); } } 4．参考代码为：
BiThrTreepre;
voidPreThreading(BiThrTreep)//先序线索化 { if(p){ if(!p>lchild)
{ p>LTag=Thread;
p>lchild=pre; //前驱线索 } if(!pre>rchild)
{ pre>RTag=Thread;
pre>rchild=p; //后继线索 } pre=p; if(p>LTag==Link)
PreThreading(p>lchild);//左子树线索化 if(p>RTag==Link)
— 3—
教学过程及内容
PreThreading(p>rchild);//右子树线索化
} } BiThrTreePreOrderThreading(BiThrTreeT)//先序线索二叉树 { BiThrTreethrt; if(!(thrt=(BiThrTree)malloc(sizeof(BiThrNode))))
returnNULL; thrt>LTag=Link;
thrt>RTag=Thread;//建头结点 thrt>rchild=thrt;//右指针回指 if(!T)thrt>lchild=thrt;//空二叉树 else { thrt>lchild=T; pre=thrt;
PreThreading(T);//先序遍历进行先序线索化
pre>rchild=thrt;pre>RTag=Thread;//最后一个结点线索化 thrt>rchild=pre; } returnthrt;
} voidPreOrderTraverse_Thr(BiThrTreethrt)//先序遍历二叉树 { BiThrTreep;
printf(“先序遍历结果为：”); p=thrt>lchild; while(p!=thrt){ printf(“%3c”,p>data); while(p>LTag==Link){ p=p>lchild;
printf(“%3c”,p>data); } p=p>rchild; } printf(“n”); }
— 4— 授课进度第13周，第24次课（2学时）授课题目
(教学章、节实验六哈夫曼树 或主题)
授课日期
016年11月23日（11 2
月22日）
.理解哈夫曼树的特征及其应用。1.在对哈夫曼树进行理解的基础上，构造哈夫曼树，并用构造的哈夫曼树进行编 2 码和译码。
教学 目标 3.通过该实验，使学生对数据结构的应用有更深层次的理解。
1.哈夫曼树构造。
教学 2.哈夫曼编码和译码。重点
1.哈夫曼树构造。
教学 难点
请选择你授课时所采用的教学方法（在括号中画“√”）：
讲授法﹝﹞，讨论法﹝﹞，演示法﹝﹞，案例法﹝﹞，发现法﹝﹞，探究法﹝﹞，教学
谈话法﹝﹞，实验法﹝√﹞，参观法﹝﹞，考察法﹝﹞，自学辅导法﹝﹞，练习
方法
法（习题或操作课）﹝√﹞，读书指导法﹝﹞，听说法﹝﹞，写生法﹝﹞，视唱 法﹝﹞，工序法（技能课）﹝﹞，实习作业法﹝﹞，其他﹝﹞ 教学
实物﹝﹞，多媒体﹝﹞，投影﹝﹞，影像﹝﹞，CAI课件﹝﹞，PPT﹝√﹞，标本
手段
﹝﹞，挂图﹝﹞，模型﹝﹞，其他﹝﹞ 讨 论、思考 题、作业
[ 1]李素若，陈万华，游明坤主编.数据结构.北京:中国水利水电出版社，2014.[ 2]李素若，陈万华，游明坤主编.数据结构习题集及上机指导.北京:中国水利水 请选择你授课时所采用的教学手段（在括号中画“√”）：
参考
电出版社，2014.文献
教学过程及内容
一、实验内容
1．哈夫曼树问题。
利用哈夫曼编码进行通讯可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据进行预先编码；在接受端将传来的数据 进行解码（复原）对于双工信道（即可以双向传输的信道），每端都要有一个完整的编/译码 系统。试为这样的信息收发站写一个哈夫曼的编译码系统。
基本要求；（1）从终端读入字符集大小为n（即字符的个数），逐一输入n个字符和相应的n个权 值（即字符出现的频度），建立哈夫曼树，进行编码，最后输出并存于文件hfmtree中。
2）利用已建好的哈夫曼编码文件hfmtree，对键盘输入的正文进行译码。输出字符正（文，再输出该文的二进制码。
3）测试数据。（用表2.1中给出的字符集(n=27)和频度的实际统计数据建立哈夫曼树。
表2.1用于测试的字符集合频度
并实现以下报文的译码和输出：“THISPROGRAMISMYFAVORITE”。
2．思考题：利用哈夫曼树及哈夫曼编码的原理编写一个算法，n个自然数之间经过加 减运算后结果最小的值是多少。注意：只能进行加减运算，且最后结果和运算的中间结果不 能为负。
二、实验指导
# include # include # include # include typedefstruct unsignedint unsignedint {
weight; parent,lchild,rchild;
} HTNode,*HuffmanTree; typedefchar **HuffmanCode; typedefstruct{ unsignedint s1; unsignedint s2;
} MinCode;
MinCodeSelect(HuffmanTreeHT,unsignedintn);
HuffmanCodeHuffmanCoding(HuffmanTree*H1,unsignedint*w,char*ch,unsignedintn)//求哈夫曼树及哈夫曼编码，将哈夫曼编码写入文本文件 {
— 1—
教学过程及内容
unsignedinti,s1=0,s2=0; HuffmanTreep,HT; HuffmanCodeHC; char *cd; unsignedintf,c,start,m; MinCodemin; FILE*fp;
if((fp=fopen(“Huffman.txt”,“wt”))==NULL){ printf(“CannotopenfileHuffman.txtanykeyexit!”); exit(1); } if(n
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); for(p=HT,i=0;iweight=*w;p>parent=0; p>lchild=0;p>rchild=0; } for(;iweight=0;p>parent=0; p>lchild=0;p>rchild=0;
} for(i=n+1;i
HT[s1].parent=i;HT[s2].parent=i; HT[i].lchild=s1;HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
} HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); cd=(char*)malloc(n*sizeof(char*)); cd[n1]=' '; for(i=1;i
if(HT[f].lchild==c)cd[start]='0';
— 2—
教学过程及内容
elsecd[start]='1';
HC[i]=(char*)malloc((nstart)*sizeof(char)); strcpy(HC[i],&cd[start]); } free(cd);
for(i=1;i
} MinCodeSelect(HuffmanTreeHT,unsignedintn)//求权值的最小值和次最小值 { unsignedintmin,secmin; unsignedinttemp; unsignedinti,s1,s2; MinCodecode; s1=1;s2=1;
for(i=1;i
} for(;i
s2=i; break;
} for(i=1;i
— 3—
教学过程及内容
s2=i;
} code.s1=s1; code.s2=s2; returncode;
} voidTranscodeing(intn,char*Char_Code,char*Huffman_Code)//从文本文件中读取哈夫曼编码，并字符编码转为哈夫曼编码 { FILE*fp;
charstr[215],ch[50]={' '}; HuffmanCodeHC=NULL; inti=0,len,j,k;
HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); if((fp=fopen(“Huffman.txt”,“rt”))==NULL){ printf(“CannotopenfileHuffman.txtanykeyexit!”); exit(1); } while(!feof(fp)){ memset(str,0,sizeof(str)); fgets(str,215,fp); if(str[0]==0)break; len=strlen(str); ch[i]=str[0];
HC[i]=(char*)malloc((len1)*sizeof(char*)); memcpy(HC[i],&str[1],len2); HC[i][len2]=0; i++; } fclose(fp); i=0;k=0;
while(Char_Code[i]!=' '){ for(j=0;j
— 4—
教学过程及内容
free(HC); } intmain(){ HuffmanTreeHT=NULL; HuffmanCodeHC=NULL; unsignedint*w=NULL,i,n;
charch[50]={' '},Huffman_Code[1024]={' '};
charChar_Code[]=“THISPROGRAMISMYFAVORITE”; printf(“Inputn:n”); scanf(“%d”,&n);
w=(unsignedint*)malloc((n+1)*sizeof(unsignedint)); w[0]=0;
printf(“Enterweight,character:n”); for(i=1;i
Transcodeing(n,Char_Code,Huffman_Code); printf(“%sn”,Huffman_Code); free(w); return0; }
— 5— 授课进度第14周，第26次课（2学时）授课题目
(教学章、节实验七图的遍历（Ⅰ）或主题)
授课日期
016年11月30日（11 2
月29日）
.掌握图常用的邻接矩阵存储存储结构。1.掌握图的邻接矩阵存储结构上的两种遍历图的方法，即深度优先遍历和广度优 2 先遍历。
教学 目标
1.图的邻接存储结构。
教学 2.图的邻接矩阵存储结构下的两种遍历。重点
1.图的邻接矩阵存储结构下的两种遍历。
教学 难点
请选择你授课时所采用的教学方法（在括号中画“√”）：
讲授法﹝﹞，讨论法﹝﹞，演示法﹝﹞，案例法﹝﹞，发现法﹝﹞，探究法﹝﹞，教学
谈话法﹝﹞，实验法﹝√﹞，参观法﹝﹞，考察法﹝﹞，自学辅导法﹝﹞，练习
方法
法（习题或操作课）﹝√﹞，读书指导法﹝﹞，听说法﹝﹞，写生法﹝﹞，视唱 法﹝﹞，工序法（技能课）﹝﹞，实习作业法﹝﹞，其他﹝﹞ 教学
实物﹝﹞，多媒体﹝﹞，投影﹝﹞，影像﹝﹞，CAI课件﹝﹞，PPT﹝√﹞，标本
手段
﹝﹞，挂图﹝﹞，模型﹝﹞，其他﹝﹞ 讨 论、思考 题、作业
[ 1]李素若，陈万华，游明坤主编.数据结构.北京:中国水利水电出版社，2014.[ 2]李素若，陈万华，游明坤主编.数据结构习题集及上机指导.北京:中国水利水 请选择你授课时所采用的教学手段（在括号中画“√”）：
参考
电出版社，2014.文献
教学过程及内容
一、实验内容
图的邻接矩阵存储结构如下：
#defineMaxVerNum100//设置邻接矩阵的最大顶点数 typedefcharVertexType;//设置图的顶点信息为字符
//设置边上权值为整型 typedefintEdgeType;
typedefstruct{ VertexTypevexs[MaxVerNum];//图的顶点信息表
EdgeTypeedges[MaxVerNum][MaxVerNum];//图的邻接矩阵
//图的顶点数和边数 intn,e;
MGraph;//图的邻接矩阵表示结构定义 } 1．键盘输入数据，建立一个图的邻接矩阵，并进行图的深度优先遍历和广度优先遍历。
二、实验指导
．参考代码为： 1 # include # include # defineMaxVerNum100//设置邻接矩阵的最大顶点数 typedefcharVertexType;//设置图的顶点信息为整型
//设置边上权值为整型 typedefintEdgeType;
typedefstruct{ VertexTypevexs[MaxVerNum];//图的顶点信息表
EdgeTypeedges[MaxVerNum][MaxVerNum];//图的邻接矩阵
//图的顶点数和边数 intn,e;
MGraph;//图的邻接矩阵表示结构定义 } typedefenum{FALSE,TRUE}boolean; booleanvisited[MaxVerNum];//顶点访问标记向量 structlinkqueuenode { intdata; structlinkqueuenode*next; } ;
typedefstruct { structlinkqueuenode*front; structlinkqueuenode*rear; linkque; } voidInitQueue(linkque*q){ structlinkqueuenode*p; p=(structlinkqueuenode*)malloc(sizeof(structlinkqueuenode)); p>next=NULL;
— 1—
教学过程及内容
q>front=p;q>rear=p;
} intQueueEmpty(linkqueq){ inti;
if(q.front==q.rear)i=1; elsei=0; return(i); } voidEnQueue(linkque*q,intx){ structlinkqueuenode*p; p=(structlinkqueuenode*)malloc(sizeof(structlinkqueuenode)); p>data=x;p>next=NULL; if(QueueEmpty(*q)){ q>front>next=p; q>rear=p; } else { q>rear>next=p; q>rear=p; } } intDeQueue(linkque*q,int*x){ structlinkqueuenode*p;
if(QueueEmpty(*q)){printf(“queueisempty!n”);return(0);} else { p=q>front>next; *x=p>data;
q>front>next=p>next; if(p>next==NULL)
q>rear=q>front; free(p);
return(1); } } linkqueQ;
voidCreateMGraph(MGraph*g)//建立图g的邻接矩阵表示
— 2—
教学过程及内容
{ inti,j,k,w; intflag;
printf(“创建:有限图选0，无向图选1n”);
scanf(“%d”,&flag);
printf(“请输入顶点数和边数(格式为:顶点数,边数)n”); scanf(“%d,%d”,&g>n,&g>e);
printf(“输入顶点的信息,每个顶点以回车作为结束:n”); for(i=0;in;i++){ getchar();
scanf(“%c”,&(g>vexs[i])); }
/将邻接矩阵数组初始化 for(i=0;in;i++)/for(j=0;jn;j++)g>edges[i][j]=0;//图的遍历算法初始化该值为0 for(k=0;ke;k++){ printf(“输入顶点号i,顶点号j,权值w(非网图权值为1):n”); scanf(“%d,%d,%d”,&i,&j,&w); g>edges[i][j]=w;
//构造无向图 if(flag)
g>edges[j][i]=w;
} } voidDFSM(MGraph*g,inti)//对以邻接矩阵表示的图，以序号为i的顶点为出发点进行深度优先搜索 { intj;
printf(“%c”,g>vexs[i]);//访问序号为i的顶点 visited[i]=TRUE;//将序号为i的顶点设置访问过标记 for(j=0;jn;j++)//扫描邻接矩阵的第i行，做以下操作
if((g>edges[i][j]!=0)&&(!visited[j]))//寻找序号为i的顶点的未访问过的邻接点 设序号为j)（{ printf(“>”);
DFSM(g,j);//以序号为j的顶点为出发点进行深度优先搜索 } } voidDFSMTraverse(MGraph*g,intstart)//对以邻接矩阵表示的图，从最初顶点start出发进行深度优先搜索 { inti;
for(i=0;in;i++)//将图的所有顶点设置为未访问过
— 3—
教学过程及内容
visited[i]=FALSE; DFSM(g,start);//对图进行深度优先搜索 printf(“n”);
} voidBFSM(MGraph*g,intk)//对以邻接矩阵表示的图，以序号为k的顶点为出发点进行广度优先搜索 { inti,j;
InitQueue(&Q);
printf(“%c”,g>vexs[k]);//访问序号为k的顶点 visited[k]=TRUE;//将序号为k是结点设置为已访问过 EnQueue(&Q,k);//将序号为k的顶点入队 while(!QueueEmpty(Q)){ DeQueue(&Q,&i);
for(j=0;jn;j++)//寻找序号为i顶点的邻接点，并做如下处理
if((g>edges[i][j]!=0)&&(!visited[j]))
//若序号为i的顶点有未访问过邻接点 { printf(“>%c”,g>vexs[j]);//访问序号为j的顶点 visited[j]=TRUE;//设置序号为j的顶点访问过标记 EnQueue(&Q,j);//将序号为j的顶点入队 } } } voidBFSMTraverse(MGraph*g,intstart)//对以邻接矩阵表示的图，从最初顶点start开始进行广度优先搜索 { inti;
for(i=0;in;i++)//将所有顶点设置为未访问过 visited[i]=FALSE; BFSM(g,start);//对邻接矩阵表示的图进行广度优先搜索 printf(“n”);
} voidmain(){ MGraph*g=(MGraph*)malloc(sizeof(MGraph));//申请图g的邻接矩阵表示空间 CreateMGraph(g);//建立图
DFSMTraverse(g,0);//从顶点0出发进行图的深度搜索遍历 BFSMTraverse(g,0);//从顶点0出发进行图的广度搜索遍历 }
— 4— 授课进度 授课题目 第15周，第28次课（2学时）授课日期
016年12月7日（12 2
月6日）
(教学章、节实验七图的遍历（Ⅱ）或主题).掌握图常用的邻接表存储存储结构。1.掌握图的邻接表存储结构上的两种遍历图的方法，即深度优先遍历和广度优先 2 遍历。
教学 目标
1.图的邻接表存储结构。
教学 2.图的邻接表存储结构下的两种遍历。重点
1.图的邻接表存储结构下的两种遍历。
教学 难点
请选择你授课时所采用的教学方法（在括号中画“√”）：
讲授法﹝﹞，讨论法﹝﹞，演示法﹝﹞，案例法﹝﹞，发现法﹝﹞，探究法﹝﹞，教学
谈话法﹝﹞，实验法﹝√﹞，参观法﹝﹞，考察法﹝﹞，自学辅导法﹝﹞，练习
方法
法（习题或操作课）﹝√﹞，读书指导法﹝﹞，听说法﹝﹞，写生法﹝﹞，视唱 法﹝﹞，工序法（技能课）﹝﹞，实习作业法﹝﹞，其他﹝﹞ 教学
实物﹝﹞，多媒体﹝﹞，投影﹝﹞，影像﹝﹞，CAI课件﹝﹞，PPT﹝√﹞，标本
手段
﹝﹞，挂图﹝﹞，模型﹝﹞，其他﹝﹞ 讨 论、思考 题、作业
[ 1]李素若，陈万华，游明坤主编.数据结构.北京:中国水利水电出版社，2014.[ 2]李素若，陈万华，游明坤主编.数据结构习题集及上机指导.北京:中国水利水 请选择你授课时所采用的教学手段（在括号中画“√”）：
参考
电出版社，2014.文献
教学过程及内容
一、实验内容
图的邻接表存储结构如下：
#defineMaxVerNum100//定义最大顶点数为100 typedefcharVertexType;//设置图的顶点信息为字符
//边表表结点结构 typedefstructNode{ intadjvex; structNode*next; } EdgeNode;
typedefstructVNode{//顶点结点结构
VertexTypevertex;
EdgeNode*firstedge; } VNode,AdjList[MaxVerNum]; typedefstruct{ AdjListadjlist;
//顶点数和边数 intn,e;
intkind; //有向图为0，无向图为1 } ALGraph;
1．键盘输入数据，建立一个图的邻接邻接表，并进行图的深度优先遍历和广度优先遍 历。
二、实验指导
1．参考代码为：
# include # include # defineMaxVerNum100//定义最大顶点数为100 typedefcharVertexType;//设置图的顶点信息为字符
//边表表结点结构 typedefstructNode{ intadjvex; structNode*next; } EdgeNode;
typedefstructVNode{//顶点结点结构
VertexTypevertex;
EdgeNode*firstedge; } VNode,AdjList[MaxVerNum]; typedefstruct{ AdjListadjlist;
//顶点数和边数 intn,e;
intkind; //有向图为0，无向图为1 } ALGraph;
typedefenum{FALSE,TRUE}boolean; booleanvisited[MaxVerNum];//顶点访问标记向量
— 1—
教学过程及内容
structlinkqueuenode { intdata; structlinkqueuenode*next; } ;
typedefstruct { structlinkqueuenode*front; structlinkqueuenode*rear; linkque; } voidInitQueue(linkque*q){ structlinkqueuenode*p; p=(structlinkqueuenode*)malloc(sizeof(structlinkqueuenode)); p>next=NULL;
q>front=p;q>rear=p;
} intQueueEmpty(linkqueq){ inti;
if(q.front==q.rear)i=1; elsei=0; return(i); } voidEnQueue(linkque*q,intx){ structlinkqueuenode*p; p=(structlinkqueuenode*)malloc(sizeof(structlinkqueuenode)); p>data=x;p>next=NULL; if(QueueEmpty(*q)){ q>front>next=p; q>rear=p; } else { q>rear>next=p; q>rear=p; } } intDeQueue(linkque*q,int*x){
— 2—
教学过程及内容
structlinkqueuenode*p;
if(QueueEmpty(*q)){printf(“queueisempty!n”);return(0);} else { p=q>front>next; *x=p>data;
q>front>next=p>next; if(p>next==NULL)
q>rear=q>front; free(p);
return(1); } } linkqueQ;
voidCreateALGraph(ALGraph*g)//建立图的邻接矩阵表示 { inti,j,k; intflag;
EdgeNode*s1,*s2;
printf(“创建:有向图选0，无向图选1n”);
scanf(“%d”,&flag);
printf(“请输入顶点数和边数(格式为:顶点数,边数)n”); g>kind=flag;
scanf(“%d,%d”,&g>n,&g>e);//输入图的顶点数和边数 printf(“输入顶点的信息,每个顶点以回车作为结束:n”); for(i=0;in;i++)//初始化顶点数组 { scanf(“%c”,&(g>adjlist[i].vertex)); g>adjlist[i].firstedge=NULL; } printf(“输入构成边或弧：顶点号i,顶点号j:n”); if(flag==0)//有向图 { for(k=1;ke;k++){ scanf(“%d,%d”,&i,&j);
s1=(EdgeNode*)malloc(sizeof(EdgeNode)); s1>adjvex=j; s1>next=g>adjlist[i].firstedge; g>adjlist[i].firstedge=s1; } }
— 3—
教学过程及内容
else { //无向图
for(k=1;ke;k++){ scanf(“%d,%d”,&i,&j);
s1=(EdgeNode*)malloc(sizeof(EdgeNode)); s1>adjvex=j;
s2=(EdgeNode*)malloc(sizeof(EdgeNode)); s2>adjvex=i;
s1>next=g>adjlist[i].firstedge; g>adjlist[i].firstedge=s1; s2>next=g>adjlist[j].firstedge; g>adjlist[j].firstedge=s2; } } } voidDFSAL(ALGraph*g,inti)//对以邻接表表示的图，以序号为i的顶点为出发点进行深度优先搜索 { EdgeNode*p;
printf(“%c”,g>adjlist[i].vertex);//访问序号为i的顶点 visited[i]=TRUE;//将序号为i的顶点设置访问过标记 p=g>adjlist[i].firstedge; while(p){ if(!visited[p>adjvex]){ printf(“>”);DFSAL(g,p>adjvex); } p=p>next; } } voidDFSALTraverse(ALGraph*g,intstart)//对以邻接表表示的图，从最初顶点start出发进行深度优先搜索 { inti;
for(i=0;in;i++)//将图的所有顶点设置为未访问过
visited[i]=FALSE; DFSAL(g,start);//对图进行深度优先搜索 printf(“n”);
} voidBFSAL(ALGraph*g,intk)//对以邻接表表示的图，以序号为i的顶点为出发点进行广度优先搜索 { inti;
— 4—
教学过程及内容
EdgeNode*p; InitQueue(&Q); printf(“%c”,g>adjlist[k].vertex);//访问序号为k的顶点 visited[k]=TRUE;//将序号为k是结点设置为已访问过 EnQueue(&Q,k);//将序号为k的顶点入队
while(!QueueEmpty(Q)){ DeQueue(&Q,&i); p=g>adjlist[i].firstedge; while(p){ if(!visited[p>adjvex]){ printf(“>%c”,g>adjlist[p>adjvex].vertex);//访问p>adjvex的顶点
visited[p>adjvex]=TRUE; EnQueue(&Q,p>adjvex); } p=p>next; } } } voidBFSALTraverse(ALGraph*g,intstart)//对以邻接矩阵表示的图，从最初顶点start出发进行广度优先搜索 { inti;
for(i=0;in;i++)//将所有顶点设置为未访问过 visited[i]=FALSE; BFSAL(g,start);//对邻接矩阵表示的图进行广度优先搜索 printf(“n”); } voidmain(){ ALGraph*g=(ALGraph*)malloc(sizeof(ALGraph)); CreateALGraph(g);
DFSALTraverse(g,0);//从顶点0出发进行深度优先搜索 BFSALTraverse(g,0);//从顶点0出发进行广度优先搜索 }
— 5— 授课进度第16周，第30次课（2学时）授课题目
(教学章、节实验八查找 或主题)
授课日期
016年12月14日（12 2
月13日）
．掌握顺序查找、折半查找算法的思想及程序实现。1 2 ．掌握二叉排序树、AVL树的查找、插入、删除、建立算法的思想及程序实现。．掌握散列存储结构的思想，能选择合适散列函数，实现不同冲突处理方法的散 3 教学
目标 列表的查找、建立。
．掌握顺序查找、折半查找算法的思想及程序实现。1 ．掌握散列存储结构的思想，能选择合适散列函数，实现不同冲突处理方法的散 教学 2 重点 列表的查找、建立。
1.掌握散列存储结构的思想，能选择合适散列函数，实现不同冲突处理方法的散
教学 列表的查找、建立。难点
请选择你授课时所采用的教学方法（在括号中画“√”）：
讲授法﹝﹞，讨论法﹝﹞，演示法﹝﹞，案例法﹝﹞，发现法﹝﹞，探究法﹝﹞，教学
谈话法﹝﹞，实验法﹝√﹞，参观法﹝﹞，考察法﹝﹞，自学辅导法﹝﹞，练习
方法
法（习题或操作课）﹝√﹞，读书指导法﹝﹞，听说法﹝﹞，写生法﹝﹞，视唱 法﹝﹞，工序法（技能课）﹝﹞，实习作业法﹝﹞，其他﹝﹞ 教学
实物﹝﹞，多媒体﹝﹞，投影﹝﹞，影像﹝﹞，CAI课件﹝﹞，PPT﹝√﹞，标本
手段
﹝﹞，挂图﹝﹞，模型﹝﹞，其他﹝﹞ 讨 论、思考 题、作业
[ 1]李素若，陈万华，游明坤主编.数据结构.北京:中国水利水电出版社，2014.[ 2]李素若，陈万华，游明坤主编.数据结构习题集及上机指导.北京:中国水利水 请选择你授课时所采用的教学手段（在括号中画“√”）：
参考
电出版社，2014.文献
