第一篇：数据结构实验课教案
数据结构教案
实验一：线性表的顺序表示与实现
实验学时：2学时
一．实验目的：
1．掌握线性表的顺序存储结构；
2．掌握在顺序表上进行的插入、删除、查找、修改等操作。
二．实验内容：
1．分别建立顺序表，并输入初始数据；
2．对顺序表分别编写插入、删除、查找、修改等函数。
三．实验重点：
顺序表的建立及操作。
四．实验要求：
1．用C语言编写程序源代码；
2．要分别完成建立、插入、删除、查找、修改五种功能。3．源程序必须编译调试成功，独立完成。
五． 实验器材：
一个装有C语言编译环境的计算机。
六．实验步骤：
顺序表 ：
1．定义头文件和顺序表的存储结构类型等 #define ok 1 #define error 0 #define overflow 0 #define null 0 #include
return overflow;l->length=0;l->listsize=list_init_size;return ok;}
3．编写对顺序表进行插入操作的函数： status listinsert(sqlist *l,int i,elemtype e){ elemtype *newbase,*q,*p;if(i<1||i>listlength(*l)+1)
return error;if(l->length==l->listsize)
{ newbase=(elemtype *)realloc(l->elem,(l->listsize+listincrement)*sizeof(elemtype));
if(!newbase)
return overflow;
l->listsize+=listincrement;
} q=&(l->elem[i-1]);for(p=&(l->elem[l->length])-1;p>=q;--p)
*(p+1)=*p;*q=e;++l->length;return ok;}
4．编写对顺序表进行删除操作的函数：
status listdelete(sqlist *l,int i,elemtype *e){ elemtype *p,*q;if(i<1||i>l->length)
return error;p=&(l->elem[i-1]);*e=*p;q=l->elem+l->length-1;for(++p;p<=q;++p)
*(p-1)=*p;--l->length;return ok;}
5．编写对顺序表进行查找操作的函数： status getelem(sqlist l,int i,elemtype *e){ if(i<1||i>listlength(l))return error;*e=l.elem[i-1];return ok;}
6．编写对顺序表进行修改操作的函数： status locateelem(sqlist l,elemtype e){ int i;for(i=0;i if(l.elem[i]==e) return i+1;return 0;} 7．编写实现两个线性表的归并操作的函数 void mergelist(sqlist la,sqlist lb,sqlist *lc){ int i,j,k;int la_len,lb_len;elemtype ai,bj;i=j=1;k=0;listinit(lc);la_len=listlength(la);lb_len=listlength(lb);while(i<=la_len&&j<=lb_len){ getelem(la,i,&ai);getelem(lb,j,&bj);if(ai<=bj) { listinsert(lc,++k,ai); ++i; } else { listinsert(lc,++k,bj); ++j; } } while(i<=la_len){ getelem(la,i++,&ai);listinsert(lc,++k,ai);} while(j<=lb_len) { getelem(lb,j++,&bj);listinsert(lc,++k,bj); } } 8．销毁线性表、清空线性表、判空、求表长等 status destroylist(sqlist *l){ if(l->elem)free(l->elem),l->elem=null;return ok;} status clearlist(sqlist *l){ l->length=0;return ok;} status listempty(sqlist l){ return(l.length==0);} status listlength(sqlist l){ return l.length;} 9．打印线性表 void print(sqlist l){ int i;printf(“nlist: ”);for(i=0;i 10． 编写主函数 void main(){ int i;int n;elemtype a;sqlist l,la,lb,lc;clrscr();listinit(&l);listinit(&la);listinit(&lb); printf(“please input list number”);scanf(“%d”,&n);printf(“n”);for(i=0;i scanf(“%d”,&a); listinsert(&l,i+1,a);} print(l);printf(“nlist length:%d”,listlength(l)); getelem(l,4,&a);printf(“ngetelem(l,4,&a),%d”,a); listdelete(&l,3,&a);printf(“nlistdelete(&l,3,&a),%d”,a);print(l); printf(“ninput list la”); for(i=0;i<5;i++){ scanf(“%d”,&a); listinsert(&la,i+1,a);} printf(“ninput list lb”);for(i=0;i<7;i++){ scanf(“%d”,&a); listinsert(&lb,i+1,a);} mergelist(la,lb,&lc);print(la);print(lb);print(lc);} 实验二：链表 实验学时：2学时 一．实验目的： 11． 掌握单、双向链表的存储结构； 12． 掌握在单、双向链表上进行的插入、删除、查找、修改等操作。 二．实验内容： 4．分别建立单、双向链表，并输入初始数据； 5．对两种单、双向链表分别编写插入、删除、查找、修改等函数。 三．实验重点： 单向链表的建立及操作。 四．实验要求： 1．用C语言编写程序源代码； 2．要分别完成建立、插入、删除、查找、修改五种功能。6．源程序必须编译调试成功，独立完成。 五． 实验器材： 一个装有C语言编译环境的计算机。 六．实验步骤： 单链表 ： 1．定义头文件和单链表的结构体类型 #include int data; struct LNode *next;}LNode, *LinkList; 2．编写构造单链表的函数 void InitList_L(LinkList L){ LinkList p,q;int i,b,j=0;p=L;printf(“请输入链表中元素的值，用-1表示输入结束：n”);do { scanf(“%d”,&b);q=(LinkList)malloc(sizeof(LNode));q->data=b;p->next=q;p=p->next;j+=1;} while(b!=-1);p->next=NULL;p=L;for(i=1;i 13． 编写对单链表进行插入操作的函数： void ListInsert_L(LinkList L,int r,int e){ LinkList p,s; int q=1,i,j=0; p=L; while(q>=1&&q<=r-1) { p=p->next; ++q; } s=(LinkList)malloc(sizeof(LNode)); s->data=e; s->next=p->next; p->next=s; p=L;while(p->next!=NULL) { p=p->next; j+=1; } p=L; printf(“插入一个新结点后的链表为：n”); for(i=1;i { p=p->next; printf(“%dn”,p->data); } printf(“插入一个新结点后链表结点的个数为:%dn”,j-1); printf(“***************************************n”);} 14． 编写对单链表进行删除操作的函数： void ListDelete_L(LinkList L,int r){ LinkList p,s;int q=1,i,e;p=L;if(r<1||r>k){ printf(“删除的位置不正确n”);printf(“***************************************n”);} else { while(q>=1&&q<=r-1){ p=p->next;++q;} s=p->next;p->next=s->next;e=s->data;k=k-1;printf(“删除的结点的值为：%dn”,e);printf(“删除一个结点后的链表为：n”);p=L;for(i=1;i<=k;i++){ p=p->next;printf(“%dn”,p->data);} printf(“删除一个结点后链表结点的个数为:%dn”,k);printf(“***************************************n”);} } 15． 编写对单链表进行查找操作的函数： void GetElem_L(LinkList L,int r){ LinkList p;int q=1,e;p=L;if(r<1||r>k){ printf(“第%d个元素不存在n”,r);printf(“***************************************n”);} else { while(q>=1&&q<=r){ p=p->next;q++;} e=p->data;printf(“第%d个元素的值为:n%dn”,r,e);printf(“***************************************n”);} } 16． 编写对单链表进行修改操作的函数： void UpdateElem_L(LinkList L,int r){ LinkList p;int q=1,n,i;p=L;if(r<1||r>k) { printf(“第%d个元素不存在n”,r); printf(“***************************************n”);} else { while(q>=1&&q<=r) { p=p->next; q++; } printf(“请输入修改后该结点的值：n”); scanf(“%d”,&n); printf(“***************************************n”); p->data=n; printf(“修改第%d个元素的值后链表为：n”,r); p=L; for(i=1;i<=k;i++) { p=p->next; printf(“%dn”,p->data); } printf(“***************************************n”);} } 17． 编写主函数 void main(){ int m,n=0;LinkList l;l=(LinkList)malloc(sizeof(LNode));InitList_L(l);while(n!=-1){ printf(“请选择对链表进行何种操作:n输入1表示对链表进行插入操作n输入2表示对链表进行删除操作n输入3表示对链表进行查找操作n输入4表示对链表进行修改操作n输入-1表示操作结束n”);printf(“***************************************n”);scanf(“%d”,&n);printf(“***************************************n”);switch(n){ case 1: printf(“请输入在第几个结点之前插入新结点：n”);scanf(“%d”,&m);printf(“***************************************n”);ListInsert_L(l,m);break;case 2: printf(“请输入删除第几个结点：n”);scanf(“%d”,&m);printf(“***************************************n”);ListDelete_L(l,m);break;case 3: printf(“请输入查找第几个结点的值：n”);scanf(“%d”,&m);printf(“***************************************n”);GetElem_L(l,m);break;case 4: printf(“请输入修改第几个结点的值：n”);scanf(“%d”,&m);printf(“***************************************n”);UpdateElem_L(l,m);break;} } printf(“操作结束!n”);} 双向链表 1．定义头文件和双向链表的结构体类型 #include 2．编写构造双向链表的函数 void InitList_DuL(DuLinkList L){ DuLinkList p,q;int i,b=0,j=0;p=L;printf(“请输入链表中元素的值，用-1表示输入结束：n”);while(b!=-1){ scanf(“%d”,&b);q=(DuLinkList)malloc(sizeof(DuLNode));q->data=b;p->next=q;q->prior=p;p=p->next;j+=1;} k=j-1;p->next=NULL;p=L;printf(“***************************************n”);printf(“创建的双向链表为：n”);for(i=1;i 3．对双向链表进行插入操作的函数 void ListInsert_DuL(DuLinkList L,int r){ DuLinkList p,s;int q=1,i,n;p=L;if(r<1||r>k){ printf(“插入的位置不正确!n”);printf(“***************************************n”);} else { while(q>=1&&q<=r-1){ p=p->next;q++;} s=(DuLinkList)malloc(sizeof(DuLNode));printf(“请输入插入的结点的值：n”);scanf(“%d”,&n);printf(“***************************************n”);s->data=n;s->next=p->next;p->next->prior=s;s->prior=p;p->next=s;k=k+1;p=L;printf(“插入一个新结点后的链表为：n”);for(i=1;i<=k;i++){ p=p->next;printf(“%dn”,p->data);} printf(“插入一个新结点后链表结点的个数为:%dn”,k);printf(“***************************************n”);} } 7． 写对双向链表进行删除操作的函数 void ListDelete_DuL(DuLinkList L,int r){ DuLinkList p,s;int q=1,i,e;p=L;if(r<1||r>k) { printf(“删除的位置不正确n”); printf(“***************************************n”);} else { while(q>=1&&q<=r-1) { p=p->next; ++q; } s=p->next; p->next=s->next; s->next->prior=p; e=s->data; k=k-1; printf(“删除的结点的值为：%dn”,e); printf(“删除一个结点后的链表为：n”); p=L; for(i=1;i<=k;i++) { p=p->next; printf(“%dn”,p->data); } printf(“删除一个结点后链表结点的个数为:%dn”,k); printf(“***************************************n”);} } 8． 编写对双向链表进行查找操作的函数 void GetElem_DuL(DuLinkList L,int r){ DuLinkList p;int q=1,e;p=L;if(r<1||r>k) { printf(“第%d个元素不存在n”,r); printf(“***************************************n”);} else { while(q>=1&&q<=r) { p=p->next; q++; } e=p->data; printf(“第%d个元素的值为:n%dn”,r,e); printf(“***************************************n”);} } 9． 编写对双向链表进行修改操作的函数 void UpdateElem_DuL(DuLinkList L,int r){ DuLinkList p;int q=1,n,i;p=L;if(r<1||r>k) { printf(“第%d个元素不存在n”,r); printf(“***************************************n”);} else { while(q>=1&&q<=r) { p=p->next; q++; } printf(“请输入修改后该结点的值：n”); scanf(“%d”,&n); printf(“***************************************n”); p->data=n; printf(“修改第%d个元素的值后链表为：n”,r); p=L; for(i=1;i<=k;i++) { p=p->next; printf(“%dn”,p->data); } printf(“***************************************n”);} } 10． 编写主函数 void main(){ int m,n=0;DuLinkList l;l=(DuLinkList)malloc(sizeof(DuLNode));InitList_DuL(l);while(n!=-1){ printf(“请选择对链表进行何种操作:n输入1表示对链表进行插入操作n输入2表示对链表进行删除操作n输入3表示对链表进行查找操作n输入4表示对链表进行修改操作n输入-1表示操作结束n”); printf(“***************************************n”); scanf(“%d”,&n); printf(“***************************************n”); switch(n) { case 1: printf(“请输入在第几个结点之前插入新结点：n”); scanf(“%d”,&m); printf(“***************************************n”); ListInsert_DuL(l,m); break; case 2: printf(“请输入删除第几个结点：n”); scanf(“%d”,&m); printf(“***************************************n”); ListDelete_DuL(l,m); break; case 3: printf(“请输入查找第几个结点的值：n”); scanf(“%d”,&m); printf(“***************************************n”); GetElem_DuL(l,m); break; case 4: printf(“请输入修改第几个结点的值：n”); scanf(“%d”,&m); printf(“***************************************n”); UpdateElem_DuL(l,m); break; } } printf(“操作结束!n”);} 实验三：栈、队列 实验学时：2学时 一．实验目的： 1．掌握栈、队列的存储结构； 2．掌握在栈、队列上进行的各种操作。 二．实验内容： 1．编写模拟Hanoi塔函数计算的程序，掌握栈在递归中的作用； 2．编写循环队列的进队、出队、初始化等函数。（2选1） 三．实验重点： 对栈、队列的存储结构的理解。 四．实验难点： 循环队列操作函数的编写。 五．实验要求： 1．用C语言编写程序源代码； 2．源程序必须编译调试成功，独立完成。 六．实验器材： 一个装有C语言编译环境的计算机。 七．实验步骤： Hanoi塔程序的编写 1．定义头文件： #include 2．编写move函数： void move(char x,char y){ printf(“%c-->%cn”,x,y);} 3．编写Hanoi塔函数： void hanoi(int n,char a,char b,char c){ if(n==1) move(a,c); else { hanoi(n-1,a,c,b); move(a,c); hanoi(n-1,b,a,c); } } 4．编写主函数： void main(){ int m;printf(“请输入需要移动的盘子数：n”);scanf(“%d”,&m);printf(“%d个盘子通过B从A移动到C的过程如下：n”,m);hanoi(m,'A','B','C');} 循环队列操作函数的编写 1．定义头文件和结构体类型等： #include int front;//顺序存储，即地址，所以用下标表示元素，front是第一个元 //的下标 int rear;//rear是最后一个元素的下标 }SqQueue; 2．编写初始化函数： int InitQueue(SqQueue &Q){ Q.base=(int*)malloc(MAXQSIZE*sizeof(int));if(!Q.base) return 0; else { Q.front=0; Q.rear=0; return 1; } } 3．编写进队函数： void EnQueue(SqQueue &Q,char e){ if((Q.rear+1)%MAXQSIZE==Q.front) printf(“队列满”);else { Q.base[Q.rear]=e;//Q.base表示数组的地址也即数组名；Q.rear表示引用结//构体类型变量Q中的一个成员rear ,也即是数组中下标为rear的元素 Q.rear=(Q.rear+1)%MAXQSIZE; } } 4．编写出队函数： void DeQueue(SqQueue &Q){ char e;if(Q.front==Q.rear) printf(“队列空n”);else { e=Q.base[Q.front]; Q.front=(Q.front+1)%MAXQSIZE; } } 5．编写显示功能函数： void Display(SqQueue Q){ int i; if(Q.front==Q.rear) printf(“队列空n”);else { i=Q.front; printf(“队列中的元素如下:”); do { printf(“%c”,Q.base[i]); i=(i+1)%MAXQSIZE; } while(i!=Q.rear); } } 6．编写主函数： void main(){ SqQueue Q; char r; int i=0; InitQueue(Q); while(i!=-1) { printf(“请选择对队列进行何种操作:n 输入1表示进行入队操作n 输入2表示进行出队操作n 输入-1表示不进行任何操作n”); printf(“********************************************n”); scanf(“%d”,&i); printf(“********************************************n”); switch(i) { case 1: printf(“请输入要入队的元素的值,输入#表示结束:n”); printf(“****************************************n”); scanf(“%c”,&r); while(r!='#') { EnQueue(Q,r); scanf(“%c”,&r); } printf(“****************************************n”); Display(Q); printf(“****************************************n”); break; case 2: DeQueue(Q); Display(Q); break; } } } 实验四：树 实验学时：2学时 一．实验目的： 1．掌握二叉树的存储结构； 2．掌握在二叉树上进行的各种操作。 二．实验内容与基本要求： 1．编写二叉树的各种操作函数，包括建立、初始化、添加、删除、查找等； 2．编写对二叉树进行三种遍历的函数； 3．编写8皇后的模拟计算程序。 (3选2) 三．实验重点： 二叉树的各种操作及遍历的函数。 四．实验难点： 二叉树的三种遍历函数的编写。 五．实验器材： 一个装有C语言编译环境的计算机。 六．实验步骤： 1．建立、初始化二叉树； struct tree //声明树的结构 { struct tree *left; int data; struct tree *right;};typedef struct tree treenode;typedef treenode *b_tree; //声明二叉树链表 //插入二叉树的节点 b_tree insert_node(b_tree root,int node){ b_tree newnode; b_tree currentnode; b_tree parentnode; newnode=(b_tree)malloc(sizeof(treenode)); //建立新节点的内存空间 newnode->data=node; newnode->right=NULL; newnode->left=NULL;if(root=NULL) return newnode; else { currentnode=root; while(currentnode!=NULL) { parentnode=currentnode; if(currentnode->data>node) currentnode=currentnode->left; else currentnode=currentnode->right; } if(parentnode->data>node) parentnode->left=newnode; else parentnode->right=newnode; return root;} } // 建立二叉树 b_tree create_btree(int *data,int len){ b_tree root=NULL; int i; for(i=0;i root=insert_node(root,data[i]);//调用insert_node函数，参数为空指针 //root和数组中元素data[i]，//insert_node函数的返回值赋给 //create_btree函数中定义root，并作为 //create_btree函数的返回值返回 return root;//返回值为root } 2．编写对二叉树进行的各种操作的函数，包括、添加、删除、查找等； 3．编写对二叉树进行三种遍历的函数； //二叉树先序遍历 void preorder(b_tree point){ if(point!=NULL) { preorder(point->left);//递归 printf(“%d”,point->data); preorder(point->right);//递归 } } //二叉树中序遍历 void inorder(b_tree point){ if(point!=NULL) { inorder(point->left);//递归 printf(“%d”,point->data); inorder(point->right);//递归 } } //二叉树后序遍历 void postorder(b_tree point){ if(point!=NULL) { postorder(point->left);//递归 printf(“%d”,point->data); postorder(point->right);//递归 } } //主程序 void main(){ b_tree root=NULL; int index; int value; int nodelist[20]; printf(“n please input the elements of binary tree(exit for 0):n”); index=0; //读取数值存到数组中 scanf(“%d”,&value); while(value!=0) { nodelist[index]=value; index=index+1; scanf(“%d”,&value); } //建立二叉树 root=create_btree(nodelist,index);//主函数调用创建函数，参数为数组名和 //长度，创建函数的返回值(返回的本身 //是root)赋给主函数中定义root，并作//为参数传给inorder函数 //先序遍历二叉树 printf(“nThe preorder traversal result is :”); preorder(root);//主函数调用inorder函数 printf(“n”);//中序遍历二叉树 printf(“nThe inorder traversal result is :”); inorder(root);//主函数调用inorder函数 printf(“n”);//后序遍历二叉树 printf(“nThe postorder traversal result is :”); postorder(root);//主函数调用inorder函数 printf(“n”);} 4．编写8皇后的模拟计算程序。实验五：图 实验学时：2学时 一．实验目的： 1．掌握图的存储结构； 2．掌握在图上进行的各种操作。 二．实验内容与基本要求： 1．编写图的各种操作函数，包括建立、初始化、添加、删除、查找等； 2．编写建立最小生成树的程序； 3．编写计算两点间最短路径的程序。（3选2） 三．实验重点： 掌握图的存储结构 四．实验难点： 编写计算两点间最短路径的程序 五．实验器材： 一个装有C语言编译环境的计算机。 六．实验步骤 计算两点间最短路径： 1．义头文件等 #include #define max 10000//设定一个极大值 2．编写主函数 void main(){ int D[vex][vex][vex];//定义一个三维数组，用来一次一次的迭代，按 //FLOYD算法求出结点之间的最短路径 int arcs[vex][vex]={0,4,11,6,0,2,3,max,0};//邻接矩阵 int i,j,k; for(i=0;i //空间进行初始化 for(k=0;k for(i=0;i for(j=0;j if(D[k-1][i][j] D[k][i][j]=D[k-1][i][j];else D[k][i][j]=D[k-1][i][k]+D[k-1][k][j];//求出每次迭代最小 //值，最后一次即为两个顶点之间的最短路径 printf(“图的邻接矩阵为:n”);for(i=0;i for(j=0;j { printf(“%d ”,arcs[i][j]); } printf(“nn”); }//打印邻接矩阵 printf(“n”); printf(“表示各点间最短路径的矩阵为:n”); for(i=0;i { for(j=0;j { printf(“%d ”,D[vex-1][i][j]); } printf(“nn”); } } 实验六：排序 实验学时：2学时 一．实验目的： 1．掌握二叉查找树的性质及其相关的应用； 2．掌握插入排序、快速排序、选择排序、归并排序、基数排序的算法实现。 二．实验内容与基本要求： 1．编写二叉查找树的生成及应用程序； 2．编写插入排序、快速排序、选择排序、归并排序、基数排序的程序。 三．实验重点： 掌握各种排序算法的思想 四．实验器材： 一个装有C语言编译环境的计算机。 五．实验步骤 插入排序： #include printf(“Please input %d numbers:n”,N);for(i=0;i for(j=i-2;t printf(“%d ”,a[i]);printf(“n”);} 快速排序： #include while(a[i]<=A && i quickSort(a,0,i-1);if(i+1<9) quickSort(&a[i+1],i+1,9);} void main(){ int i,j,a[N]; printf(“Please input %d numbers:n”,N);for(i=0;i printf(“%d ”,a[i]);printf(“n”);} 冒泡排序： #include int a[10];int i,j,t; printf(“input 10 numbers :n”);for(i=0;i<10;i++)scanf(“%d”,&a[i]);for(j=0;j<10;j++)for(i=0;i<10-j;i++)if(a[i]>a[i+1]){ t=a[i];a[i]=a[i+1];a[i+1]=t;} printf(“the sorted numbers:n”);for(i=0;i<10;i++)printf(“%d ”,a[i]);printf(“n”);} 选择排序： #include int i,j,k,t,a[N]; printf(“Please input %d numbers:n”,N); for(i=0;i scanf(“%d”,&a[i]); for(i=0;i for(j=i;j if(a[j] { t=a[j]; a[j]=a[j+1]; a[j+1]=t; } k=a[i]; a[i]=a[j]; a[j]=k;} printf(“the sorted numbers:n”); for(i=0;i printf(“%d ”,a[i]); printf(“n”);} 30 授课教案 （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(n<=0)printf(“输入错误n”); } while(n<=0); for(i=0;i } 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;i 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;i — 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<=0)printf(“输入错误n”); while(n<=0); } for(i=0;i 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(k } — 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>data 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 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 //用来存放栈中元素的一维数组 //用来存放栈顶元素的下标 } 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<=s.top;i++)printf(“%d”,s.elem[i]); printf(“n”); } 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<=6); } 2 ．参考程序为： include 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<=6); } 3 ．参考程序为： 1）（— 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<20||j<20){ num=rand()%100; if(num%2==0&&i<20){ EnQueue(&q1,num); i++; } if(num%2!=0&&j<20){ EnQueue(&q2,num); j++; } } while(!QueueEmpty(q1)&&!QueueEmpty(q2)) — 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<=rear){ n=0; while(i<=rear&&Qu[i].lno==lnum){ /求每层的结点数 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;i<=S>top;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 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<=1){ printf(“Codetoosmall!n”);exit(1);} m=2*n1; HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); for(p=HT,i=0;i<=n;i++,p++,w++){ p>weight=*w;p>parent=0; p>lchild=0;p>rchild=0; } for(;i<=m;i++,p++){ p>weight=0;p>parent=0; p>lchild=0;p>rchild=0; } for(i=n+1;i<=m;i++){ min=Select(HT,i1); s1=min.s1;s2=min.s2; 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<=n;i++){ start=n1; for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) 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<=n;i++)fprintf(fp,“%c%sn”,ch[i],HC[i]); fclose(fp); H1=HT; * returnHC; } MinCodeSelect(HuffmanTreeHT,unsignedintn)//求权值的最小值和次最小值 { unsignedintmin,secmin; unsignedinttemp; unsignedinti,s1,s2; MinCodecode; s1=1;s2=1; for(i=1;i<=n;i++)if(HT[i].parent==0){ min=HT[i].weight; s1=i; break; } for(;i<=n;i++)if(HT[i].weight s2=i; break; } for(i=1;i<=n;i++)if(HT[i].weight — 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<=n;i++){ printf(“w[%d],ch[%d]=”,i,i); scanf(“%d,%c”,&w[i],&ch[i]); } HC=HuffmanCoding(&HT,w,ch,n); 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 //设置边上权值为整型 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;i scanf(“%c”,&(g>vexs[i])); } /将邻接矩阵数组初始化 for(i=0;i //构造无向图 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;j if((g>edges[i][j]!=0)&&(!visited[j]))//寻找序号为i的顶点的未访问过的邻接点 设序号为j)（{ printf(“>”); DFSM(g,j);//以序号为j的顶点为出发点进行深度优先搜索 } } voidDFSMTraverse(MGraph*g,intstart)//对以邻接矩阵表示的图，从最初顶点start出发进行深度优先搜索 { inti; for(i=0;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;j 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;i } 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 //边表表结点结构 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;i s1=(EdgeNode*)malloc(sizeof(EdgeNode)); s1>adjvex=j; s1>next=g>adjlist[i].firstedge; g>adjlist[i].firstedge=s1; } } — 3— 教学过程及内容 else { //无向图 for(k=1;k<=g>e;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;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;i 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.文献 第一次实验 线性表 （一）实验目的和要求： 1.熟悉VC集成环境 2.会定义线性表的顺序结构和链式结构 3.熟悉对线性表的基本操作，如插入、删除等 （二）实验内容和原理或涉及的知识点（综合性实验）： 自己编写程序实现线性表的建立、插入、删除等功能。 写出线性表、顺序表、链表的定义，简单写出主要算法的思路。 （三）实验条件：安装有VC的计算机 （四）实验设计方案 设计的顺序表算法有： 1.初始化顺序表 2.顺序表的插入操作 3.顺序表的删除操作 设计的链表算法有： 1.建立链表 2.链表的插入操作 3.链表的删除操作 4.链表数据元素的访问 （五）实验过程、数据和实验结果记录 程序代码（略） 实验过程中输入/输出数据、程序运行结果的记录。（一定要有！） 第二次实验 栈和队列 （一）实验目的和要求： 1.熟练掌握栈和队列的结构，以及这种数据结构的特点 2.会定义顺序栈、循环队列，能实现栈、队列的基本操作 3.会利用栈解决典型问题，如数制转换等 （二）实验内容和原理或涉及的知识点（综合性实验）： 自己编写程序实现栈（或者队列）的各种基本操作，如初始化、入栈、出栈、判断栈是否为空等 写出栈的定义，简单写出主要算法的思路。 （三）实验条件：安装有VC的计算机 （四）实验设计方案 设计的算法有： 1.初始化栈 2.入栈 3.出栈 4.判断栈是否为空 5.十进制转换为八进制 （五）实验过程、数据和实验结果记录 程序代码（略） 实验过程中输入/输出数据、程序运行结果的记录。（一定要有！） 第三次实验 二叉树 （一）实验目的和要求： 1.熟练掌握二叉树的结构，以及这种数据结构的特点 2.会定义二叉树的链式存储结构 3.能实现二叉树的建立、遍历等功能，需要完成先序遍历、中序遍历和后序遍历递归算法 （二）实验内容和原理或涉及的知识点（综合性实验）： 自己编写程序实现二叉树的各种基本操作，如二叉树的建立（头插法或者尾插法），遍历等 写出二叉树的定义，简单写出主要算法的思路。 （三）实验条件：安装有VC的计算机 （四）实验设计方案 设计的算法有： 1.递归建立二叉树 2.先序遍历二叉树 3.中序遍历二叉树 4.后序遍历二叉树 （五）实验过程、数据和实验结果记录 程序代码（略） 实验过程中输入/输出数据、程序运行结果的记录。（一定要有！） 第四次实验 查找 （一）实验目的和要求： 1.熟练掌握查找算法的基本思想，以及算法的适用条件 2.会定义静态查找表的顺序结构，能实现顺序查找、二分查找 （二）实验内容和原理或涉及的知识点（综合性实验）： 自己编写程序实现顺序查找、二分查找。 写出静态查找表的定义，简单写出主要算法的思路。 （三）实验条件：安装有VC的计算机 （四）实验设计方案 设计的算法有： 1.建立静态查找表 2.顺序查找 3.建立有序的静态查找表 4.二分查找 （五）实验过程、数据和实验结果记录 程序代码（略） 实验过程中输入/输出数据、程序运行结果的记录。（一定要有！） 实验一 预备实验 一、实验项目的目的和要求： 1． 复习C语言指针的用法 2． 复习C语言结构体的用法 3． 理解时间复杂度分析的基本方法 二、实验内容： 1．用指针方式编写程序：从键盘输入N个整型数据，并存入数组，要求将N个数中最大的数与第一个数交换；将其中最小的数最后一个数交换。 基本思想：设两个指针分别指向最大数组元素和最小数组元素。再设一个移动指针从数组的第一个元素开始，依次与最大数组元素指针、最小数组元素指针的内容进行比较，作出相应的变化，一直到移动指针移到最后一个元素。 2．有N 个学生，每个学生的数据包括学号、姓名、三门课的成绩、平均分。要求从键盘依次输入N 个学生的学号、姓名、三门课的成绩，自动计算三门课的平均分数，并将N 个学生的数据输出。 基本思想：对每一名学生循环，再对三门课程循环求平均成绩 三、实验中存在的问题： 实验二 线性表的基本操作 一、实验项目的和要求： 1． 掌握线性表的特点 2． 掌握线性表的顺序存储结构和链式存储结构的基本运算。3． 尽可能考虑算法的健壮性 4． 实验报告中要写出测试数据、错误分析以及收获。 二、实验内容一：线性表两种存储结构的基本运算 1.用结构体类型描述线性表的两种存储结构 2.完成课堂上所讲的两种存储结构的基本运算 3.要求用二级菜单实现 ***************************** * 1-------顺序表 * * 2-------链 表 * * 0-------退 出 * ***************************** 请输入的选择：(0-2)： 线性表的链式存储 ## # 1----前插建立链表 # # 2----后插建立链表 # # 3----访问第i个元素 # # 4----插入 # # 5----删除 # # 6----求线性表的表长 # # 0----退出 # ## 请输入选择(0-6)： 分析：1．使用循环建立菜单 ２．使用switch语句进行选择，执行相应的子函数（每一个运算编写一个子函数） 实验内容二：超市密码存储箱系统的设计与实现 1.顾客使用箱子的流程为“投一元硬币”--------“找到一个空箱子，同时产生密码”（系统完成）--------“打印密码，打开箱子”（系统完成）--------“取密码纸存包，并关闭箱子，入超市购物”--------“购物结束”--------“输入密码”--------“找到对应箱子并打开”（系统完成）--------“取包”。2.现要求设计程序模拟以上系统完成的功能 ①界面：在我们的模拟系统中，箱子在屏幕上被画出来，并编号，空箱为蓝色，被使用时变成红色，再变为空后则恢复蓝色； ②通过按“1”键模拟顾客投币； ③当空箱子被顾客申请得到的同时，系统自动生成6位数密码，此密码不能与正在被使用的任何一个箱子的密码相同。3.设计分析 在设计时，可利用链表来组织所有的箱子，所有的箱子以结点的形式表示，结点中存放箱号、密码（满箱有，空箱无）以及指向下一个结点的指针。空箱结点放在一个链表1中，满箱结点放在另一个链表2中。 若有顾客投币（这里按下“1”键模拟），查看链表1是否为空，若为空，则显示“箱满，请稍侯！”，若非空，则取出一个结点，随机产生一个六位数密码，并将些密码和链表2中所有结点的密码相比较，若有重复，则再随机产生一个新密码，直到无重复；将密码信息写入此结点，并将其插入链表2；将此箱的颜色改为红色。4.密码箱的存储结构类型定义 typedef struct node { int num;/*箱子的号码*/ int password;/*箱子的密码（满箱有，空箱无）*/ struct node *next;/*指向下个结点的指针*/ }Node,*LinkList； 分析：１．初始化，建立一个代表空箱子链表，建立一个只有头结点的实箱子链表． ２．如果想要存包时，就在空箱子链表中进行查找，如果为空，代表箱子已满，否则从空箱子链表中删除一个结点，并给它赋值，将该结点插入到实箱子链表中． ３．如果想要取包时，就输入密码，在实箱子链表中进行匹配，如果成功，就从实箱子链表中删除相应的结点，插入到空箱子链表中． ４．另外还需要的函数有：随意产生密码函数，匹配密码函数 实验内容三：员工通讯录管理系统 1.为某个单位建立一个员工通讯录管理系统，可以方便地查询每一个员工的办公室电话号码、手机号码及电子邮箱。 2.现要求设计程序模拟以上系统完成的功能 其功能包括通讯录链表的建立、员工通讯信息的查询、修改、插入与删除以及整个通讯录表的输出。3.设计分析 在本设计中，整个通讯录可以采用顺序表或链表方式存储。采用前者，可以提高查询速度；采用后者，可以提高插入与删除记录的效率。 4.员工通讯信息的结构类型定义和通讯录链表的结点类型 typedef struct { char num[5];/*员工编号*/ char name[8];/*员工姓名*/ char phone[9];/*办公室电话号码*/ char call[12];/*手机号码*/ }DataType；/*员工通讯信息的结构类型*/ typedef struct node { DataType data;/*结点的数据域*/ struct node *next;/*结点的指针域*/ }ListNode,*LinkList；/*通讯录链表的结构类型*/ 分析：１．建立一个可循环的菜单 ２．使用switch语句，调用子函数实现以下功能 针对每一位员工作为一个结点建立链表． 在该链表上进行查找、插入、删除、修改及输入／出。实验内容四：运动会记分子系统或学生成绩管理子系统 1.参加运动会的N个学校编号为1~N。比赛分成M个男子项目和W个女子项目，每个项目取前3名，得分分别为5，3，2。写一个程序产生各种成绩单和得分报表。2.完成功能包括如下： ①产生一总成绩表，包括：学校编号名、男子团体总分、女子团体总分、团体总分 存储结构要求用线性表的顺序存储。 ②实验报告中要写出测试数据、错误分析以及收获。 ③若选择学生成绩管理子系统，可仿照运动会记分子系统完成相关的插入、删除、查找及各种统计工作。 分析：１．分析顺序表中每个元素的结构（数组元素是一个结构体） ２．建立顺序表 ３．在顺序表进行插入、删除、查找 ４．进行统计 实验中存在的问题： 实验三 栈和队列的应用 一、实验目的和要求： 1． 掌握栈和队列的概念和特点 2． 掌握栈和队列在顺序和链式存储结构下的插入、删除算法 3． 认真分析项目实例中的内容，将相关程序在计算机上运行实现 二、实验内容一：表达式求值问题 1．求一个数学表达式的值：用户输入一个包含正整数、括号和四则运算符（“+”、“—”、“*”、“/”）的算术表达式，计算其结果。2．设计分析 首先置操作数栈为空栈，表达式起始符“#”为运算符栈底元素；依次读入表达式中每个字符，若是操数则进操作数栈，若是操作符则和操作符栈顶的运算符进行比较优先权后作相应的操作，直到整个表达式求值完毕（即操作符栈顶元素和当前读入的字符均为“#”）3．结点结构类型描述如下 typedef struct { char *base,*top;int stacksize;}sqstack;分析：１．判断输入的字符是否为数值 2.比较判断运算符的优先级 3.何时结束循环，不再运算 实验内容二：迷宫求解问题 1.迷宫是一个m行n列的矩阵，其中0表示无障碍，1表示有障碍。设入口为（1，1），出口为（m,n），即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则 沿原路退回，换一个方向再继续探索，直到出口为止。2.迷宫的功能 要求随机生成一个m行n列的矩阵，为了操作方便可以在矩阵外围生成一圏障碍，设置东南西北四个方向，采用链栈进行操作。最后迷宫如不是通路给出“此迷宫元解”，如是通路要求输出所走过的路径。3．结点结构类型描述如下 typedef struct node { int row;int col; struct node *next;};分析：１．建立迷宫，使用二维数组，第一行／列，最后一行／列均初始化为０代表墙不通，这样使其内部的元素均有四个方向进行统一判断，其余元素进行随机产生０代表不通，１代表通． ２．确定入口，出口的坐标． ３．判断该元素是否可通（元素值等于１，一方面代表通，另一方面未走过）． ４．标记每一个走过的元素，将其元素值加１． ５．元素的四个方向用０－３表示，下一个方向的坐标可以从当前坐标及方向就可以确定． 三、实验中存在的问题： 实验四 二叉树两种存储结构的应用 一、实验目的和要求： 1． 掌握二叉树的遍历思想及二叉树的存储实现。2． 掌握二叉树的基本操作：建立二叉树、二叉树的遍历 3． 选择一种形式完成二叉树的显示 4． 掌握二叉树的常见算法的程序实现 5． 实验报告中要写出测试数据、错误分析以及收获 二、实验内容一：二叉树的建立及相关算法的实现 1．完成的功能包括如下几点： ①编程实现建立一棵二叉树，然后对其进行先序、中序和后序遍历。 分析：将要输入的二叉树按照其对应的完全二叉树的顺序输入，若当前位置不存在结点则输入@ ②显示二叉树 ③求二叉树的高度及二叉树的叶子个数等等 ④在主函数中设计一个简单的菜单，分别调试上述算法 实验内容二：哈夫曼编码/译码系统 1．要求编写一程序模拟传输过程，实现在发送前将要发送的字符信息进行编码，然后进行发送，接收后将传来的数据进行译码，即将信息还原成发送前的字符信息。2．设计分析 在本例中的算法主要有：哈夫曼树的建立；哈夫曼编码的生成；对编码信息的翻译。要求设置发送者和接收者两个功能。 发送者的功能包括： ①输入待传送的字符信息；②统计字符信息中出现的字符类数和各字符出现的次数（频率）；③根据字符的种类数和各字符出现的次数建立哈夫曼树；④利用以上哈夫曼树求出各字符的哈夫曼编码；⑤将字符信息转换成对应的编码信息进行传送。接收者的功能包括： ①接收发送者传送来的编码信息；②利用上述哈夫曼树对编码进行翻译，即将编码信息还原成发送前的字符信息。3．结点的类型定义 ①哈夫曼树的存储结构类型定义为： typedef struct { char data;/*编码对应的字符*/ int weight;/*结点的权值*/ int lchild,rchild,parent;/*左右孩子及双亲的下标*/ }HTNode;②哈夫曼编码的存储结构类型定义为： typedef struct { char bits[N];/*存放哈夫曼编码的字符数组*/ int start;/*记录编码的起始位置，因为每种字符的编码长度不同*/ }HCode; 三、实验中存在的问题： 实验五 图子系统一、实验目的和要求： １．掌握图的存储思想及其存储实现 ２．掌握图的深度、广度优先遍历算法思想及其程序实现 ３．掌握图的常见应用算法的思想及其程序实现 二、实验内容一：图的遍历问题 1．键盘输入以下结点数据：太原、成都、北京、上海、天津、大连、河北。建立一个有向图或无向图（自定）的邻接表并输出该邻接表 2．在图的邻接表的基础上计算各顶点的度，并输出 3．以有向图的邻接表为基础实现输出它的拓扑排序序列 4．采用邻接表存储实现无向图的深度优先遍历 5．采用邻接表存储实现无向图的广度优先遍历 6．采用邻接矩阵存储实现无向图的最小生成树的 PRIM 算法 7．在主函数中设计一个简单的菜单，分别调试上述算法 实验内容二：所有顶点对的最短路径 1．设置4个村庄之间的交通，村庄之间的距离用各边上的权值来表示。现在要求从这 4个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院最近。2．设计分析 用有向加权图表示的交通图中，有向边 typedef char vextype;/*顶点数据类型*/ typedef int edgetype;/*边数据类型*/ typedef struct { vextype vex[maxsize];edgetype arc[maxsize][maxsize];int vexnum,arcnum;}Mgraph; 三、实验中存在的问题： 实验六 数据结构综合性实验 一、实验目的和要求： 掌握小型系统开发方法，提高学生综合开发能力。根据实际问题，设计方案，综合运用课程知识，完成《学生成绩管理系统》或《数据结构算法演示系统》的设计、编程与调试工作。 二、实验内容一： 分析、调研数据结构课程所学的算法（功能模块）或学生成绩管理的相关功能模块，采用结构化设计思想、模块分解的规则构成一个易使用的小型管理系统。具体要求见《数据结构实验》课程设计 实验内容二：手机短信中电话号码和手机号码的识别与提取 1.在使用手机收发短信时，收到的短信内容中常会包含对方发来的电话号码或手机号码，为了方便用户能直接提取其中的号码并存入到其手机的通讯录中，现要求开发手机系统软件中的一个子功能，实现从手机短信内容中识别和提取电话号码（7位或8位）和手机号码(11位)，并将其存入通讯录中。2.设计分析 要从手机短信的内容中识别电话号码或手机号码，必须从短信的第一个字符开始查找，找到第一个数值型字符（‘0’～‘9’），然后依次判断其后的字符，若其后有连续的6个或7个数值型字符，则将其识别成电话号码并提取，若其后有连续的10个数值型字符，则将其识别成手机号码并提取。继续向后搜索直到整个短信查找完毕。3.存储结构类型定义 ①短信的存储结构类型定义 typedef struct { char word[200];/*短信内容*/ int length;/*短信长度*/ }Message;②通讯录中记录的存储结构类型的定义 typedef struct { char name[8];/*姓名*/ char phone[11];/*电话号码或手机号码*/ }Note;实验内容三：药店的药品销售统计系统 1.设计一系统，实现医药公司定期对各药品的销售记录进行统计，并按药品编号、单价、销售量或销售额做出排序。2.设计分析 在设计中，首先从数据文件读出各药品的信息记录，存储在顺序表中。各药品的信息包括：药品编号、药品名称、单价、销售量、销售额。其中药品编号共4位，采用字母和数字混合编号，如：B125，前一位为大写字母，后三位为数字。3.存储结构类型定义 ①药品信息的存储结构类型定义 typedef struct node { char num[4];/*药品编号*/ char name[10];/*药品名称*/ float price;/*单价*/ int count;/*销售量*/ float sale;/*销售额*/ }DataType;②存储药品信息的顺序表的定义 typedef struct { DataType r[maxsize];int length;}sequenList;实验内容四：电视大赛观众投票及排名系统 1.在很多电视大赛中，通常当选手表演结束后，现场观众通过手中的按键对参赛选手进行投票，然后对选手获得的票数进行统计，从高到低进行降序排列，从而自动产生冠军、亚军和季军。现要求编写一程序模拟实现上述系统的功能。2.设计分析 在本系统中，首先输入参赛选手的人数（范围为1-9个），然后根据人数通过malloc函数来开辟存放选手信息的顺序表。将选手的编号和姓名依次存入顺序表单元中，观众通过按键进行投票，按“1”表示为1号选手投票，按“2”表示为2号选手投票，依次类推。以按“0”作为投票结束标志。投票结束后进行排序。3.存储结构类型定义 ①选手信息的存储结构类型定义 typedef struct node { char name[8];/*选手姓名*/ int num;/*选手编号*/ int score;/*选手得分*/ int tax;/*选手名次*/ }Node;②开辟空间用于构造存放选手信息的顺序表R：R=(Node *)malloc(n*sizeof(Node));其中n 为参赛选手的人数，在此采用动态空间分配，而不是在开始时直接开辟静态数组，这样是为了避免空间的不足造成浪费。 在投票时，按“1”为1号选手投票的实现： Scanf(“%c”,&k);/*观众按键*/ R［K-48］.score= R［K-48］.score+1;若观众输入的是“1”，则“1”-48即为ASCII-48=1，因此可以实现对1号选手的票数加1，即R［1］=R［1］+1。其他选手类似。 数 据 结 构 实 验 指 导 书 数据结构实验指导书 目录 数据结构实验指导书.......................................................................................................................1 目录...........................................................................................................................................1 实验指导书概述...............................................................................................................................2 上机实验题目...................................................................................................................................3 实验一 C语言相关知识复习................................................................................................3 一、实验目的...................................................................................................................3 二、实验内容...................................................................................................................3 实验二 单链表的插入、删除...............................................................................................3 一、实验目的...................................................................................................................3 二、实验内容...................................................................................................................3 三、实现提示...................................................................................................................4 实验三 栈及其应用.................................................................................................................5 一、实验目的...................................................................................................................5 二、实验内容...................................................................................................................5 实验四 二叉树的递归算法.....................................................................................................6 一、实验目的...................................................................................................................6 二、实验内容...................................................................................................................6 实验五 图的遍历.....................................................................................................................7 一、实验目的...................................................................................................................7 二、实验内容...................................................................................................................7 实验六 有序表的查找.............................................................................................................7 一、实验目的...................................................................................................................7 二、实验内容...................................................................................................................7 实验七 哈希表.........................................................................................................................7 一、实验目的...................................................................................................................7 二、实验内容...................................................................................................................7 实验八 内部排序算法的应用.................................................................................................8 一、实验目的...................................................................................................................8 二、实验内容...................................................................................................................8 实验指导书概述 “数据结构”是计算机专业一门重要的专业技术基础课程，是一门关键性核心课程。本课程系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了多种常用的查找和排序技术，并对其进行了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大难度： 内容多，时间短，给学习带来困难； 贯穿全书的动态链表存储结构和递归技术是学习中的重点和难点； 隐含在各部分的技术和方法丰富，也是学习的重点和难点； 先修课程中所介绍的专业性知识不多，加大了学习难度。 由于数据结构课程的技术性与实践性，《数据结构课程实验》的设置十分必要。为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。 上机实践是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通过上机实践，使学生在可能短的时间内对数据结构知识的实践和应用有一个比较全面和系统的认识，达到理论与实践相结合的目的。 为了达到上述目的，本指导书安排了8个实验题目，它们与教科书的各章有紧密的关系，使学生在实验后能加深对课程内容的理解，增强动手能力。 每个实验题目采取了统一的格式，由问题描述、基本要求、测试数据、实现提示等部分组成。 问题描述旨在为读者建立问题提出的背景环境，指明问题“是什么”； 要求则对问题进一步求精，划出问题的边界，指出具体的参量或前提条件，并规定该题的最低限度要求； 测试部分旨在为检查学生上机作业提供方便，在完成实习题时应自己设计完整和 严格的测试方案，当数据输入量较大时，提倡以文件形式向程序提供输入数据； 实现提示对实现中的难点及其解法思路等问题作了简要提示，个别问题给出了参考实现。 下面带*的题目为选做题目。 上机实验题目 实验一 C语言相关知识复习 一、实验目的 复习C语言中函数、数组、结构体、文件等概念，掌握它们的描述与操作方法；熟悉掌握C++中typedef、引用参数调用（&）的概念及使用方法，为理解数据结构课程的后续内容以及算法书写奠定基础。 二、实验内容 问题描述：编写一个函数，求一个整数数组中的最大、最小值。 要求：在函数声明中采用引用参数传递方式实现最大、最小值的返回。测试：在主函数中输入10个数，调用此函数，打印输出最大和最小值。2 关于指针的使用： 用malloc方式分别申请两个指针，并实现两个指针内容的比较大小操作。要求：此功能在一个函数内实现，该函数接受两个整数值，存储到两个指针内容中，输出两者中的最大值。 测试：从主函数中输入两个数，调用该函数，打印输出交换后的值。 实验二 单链表的插入、删除 一、实验目的 1、熟悉某种数据结构在计算机上实现的方法。 2、掌握单链表的定义、创建、插入、删除、遍历等基本操作的实现。 3、体会单链表操作、有序表插入、删除的一般方法。 二、实验内容 问题描述：已知递增有序的单链表A，编写算法实现向A中插入或删除一个元素，并保持A的有序性。 实验要求： 1、结点的数据均为整型。 2、若表中已经存在此元素，则不插入 三、实现提示 1.在已知的线性表中插入或删除，需要下面的辅助函数：线性表的创建、线性表的遍历 2.在单链表表中插入或删除，需依次实现： a)单链表结构的定义 b)单链表的创建（头插法或尾插法建表）c)单链表的遍历 d)单链表的插入、删除（采用顺序查找方法，顺头指针往后，查找插入或删除位置，再修改指针） //头文件 #include “stdlib.h” //预定义常量 #define NULL 0 //单链表的定义 typedef struct LNode{ int data;struct LNode *next;}LNode,*LinkList;//单链表的创建 void Create_List(LinkList &L){ int data;LinkList p,q;L=(LinkList)malloc(sizeof(LNode));L->next=NULL; q=L; scanf(“%d”,&data);while(data!=0){ p=(LinkList)malloc(sizeof(LNode)); p->data=data; p->next=q->next; q->next=p; q=p; scanf(“%d”,&data);} } //单链表的遍历 void TranverseList(LinkList L){ LinkList p; p=L->next; if(p==NULL) { printf(“niln”); return; } while(p!=NULL) { printf(“%d ”,p->data); p=p->next; } printf(“n”);} 实验三 栈及其应用 一、实验目的 1、熟悉栈的顺序表示与实现。 2、熟悉栈的应用。 3、理解并掌握递归函数的设计与实现。 二、实验内容 问题描述：利用栈实现十进制数n转化为d进制数 要求： 1)输入一个n和d，打印输出d进制数序列。 2)利用顺序栈来实现十进制数n转化为其他d进制数。此时，需要同时实现初始化空栈、入栈、出栈、判栈空等辅助功能。测试数据： （1）输入n:1348 d:8 输出：2504（2）输入n:9 d:8 输出：11（3）输入n:0 d:8 输出：0 2 问题描述：利用栈实现算术表达式求值。要求： 1)参与运算的操作数为10以内的数值。测试数据： 自拟。 实验四 二叉树的递归算法 一、实验目的 1、掌握二叉树的表示与实现。 2、掌握二叉树的定义、创建、遍历等基本操作的实现。 3、熟悉求二叉树深度等递归算法的设计与实现。 二、实验内容 问题描述：已知二叉树t，分别采用顺序存储结构、二叉链表存储结构实现求二叉树的深度，并对二叉树分别进行中序遍历。要求： 1、二叉树分别采用顺序或二叉链表存储。 2、树中的数据类型约定为整型。测试数据： 1、输入序列：-+aØØ*bØØ-cØØdØØ/eØØfØØ创建二叉树； 输出：深度：5 前序序列：-+a*b-cd/ef 中序序列：a+b*c-d-e/f 后序序列：abcd-*+ef/-T:d / e f 2、t=nil 输入：Ø 输出：深度：0 实验五 图的遍历 一、实验目的 熟悉图的基本操作，掌握图遍历的设计与实现。 二、实验内容 问题描述：已知的描述校园景点的图，实现对该图的深度优先和广度优先遍历。要求： 图采用邻接矩阵存储，顶点信息包括景点的名称和简单描述。 实验六 有序表的查找 一、实验目的 1、理解各种查找方法的基本思想 2、熟悉有序表查找方法的算法实现 二、实验内容 已知一有序的序列{1,3,5,7,9}，采用折半法分别查找3和6。 2已知输入一无序的序列{5,1,3,9,7}，创建一棵二叉排序树，然后对其遍历，输出递增有序的序列。 实验七 哈希表 一、实验目的 理解哈希表的概念和基本操作；熟悉哈希表的创建、查找、插入的算法实现。 二、实验内容 问题描述：已知11位好友的名字各不相同，设计并实现一个哈希表，根据好友的名字，可以取得其生日。要求： 1、好友的信息包含名字和生日两个数据项，其中好友的名字为主键，用汉语拼音形式存放； 2、哈希函数采取：好友名字中所有拼音字母ASCII码值的和 MOD 11(除以1取余)； 3、采取线性探测再散列的方式处理冲突。 实验八 内部排序算法的应用 一、实验目的 理解各种内部排序方法的基本思想；熟悉各种内部排序方法的算法实现 二、实验内容 问题描述：已知一序列{503，087，512，061，908，170，897，275，653，426}，分别采取下列排序方法对其进行排序： （1）直接插入排序； （2）简单选择排序； （3）起泡排序；（4）快速排序；（5）堆排序。第二篇：数据结构实验课教案
第三篇：数据结构实验教案
第四篇：数据结构实验教案
第五篇：数据结构 实验指导书
点击咨询 