2011级本数据结构实验教案

1、数据结构实验数据结构设计性实验项目1. 线性表的合并：已知线性表La和Lb的元素按值非递减排列。归并La和Lb得到新的线性表Lc，Lc的元素也按值非递减排列。分别采用顺序存储结构和链式结构来实现。2. 线性表的逆置：设有一个线性表（e0, e1, , en-2, en-1），请编写一个函数将这个线性表原地逆置，即将线性表内容置换为（en-1, en-2, , e1, e0）。线性表中的数据可以为整数、字符或字符串，试分别采用顺序存储结构和链式结构来实现。3. 约瑟夫环的实现：设有n个人围坐一圈，用整数序列1, 2, 3, , n表示顺序围坐在圆桌周围的人， 现从某个位置 s上的人开始报数，数到

2、m的人出列，接着从出列的下一个人又从1开始重新报数，数到m的人出列，如此下去，直到所有人都出列为此。试设计确定他们的出列次序序列的程序。如 n=8, m=4 ,s=1时， 设每个人的编号依次为 1，2，3，开始报数，则得到的出列次序为4，8，5，2，1，3，7，6。检查程序的正确性和健壮性。(1)采用数组表示作为求解过程中使用的数据结构。(2) 采用单向循环链表作为存储结构模拟整个过程，循环链表可不设头节点,必须注意空表和非空表的界限。4. 数制转换： 利用顺序栈和链栈实现数制转换5. 二叉树的遍历：分别以顺序存储结构和二叉链表作存储结构，试编写前序、中序、后序及层次顺序遍历二叉树的算法。6.

3、 赫夫曼树与赫夫曼编码：已知某系统在通信联络中只可能出现8种字符a,b,c,d,e,f,g,h，其概率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试设计Huffman编码，并计算其平均码长。(1) 初始化：从键盘读入8个字符，以及它们的权值，建立Huffman树。(2)编码：根据建立的Huffman树，求每个字符的Huffman编码。对给定的待编码字符序列进行编码。(3) 译码：利用已经建立好的Huffman树，对上面的编码结果译码。译码的过程是分解电文中的字符串，从根结点出发，按字符0和1确定找左孩子或右孩子，直至叶结点，便求得该子串相应的字符。(4

4、) 打印Huffman树。7. 学生成绩管理查询系统：每个学生的数据信息有准考证号（主关键字）、姓名、语文、英语、数学、和总分等数据项，所有学生的信息构成一个学生成绩表。假设准考证号的头两位表示地区编号。请设计一个管理系统达到如下基本要求：（1） 初始化：建立一个学生成绩表，输入准考证号、姓名、语文、英语、数学，然后计算每个学生的总分，存入相应的数据项；注意：分析数据对象和它们之间的关系，并以合适的方式进行组织（可选择无序的顺序表、有序的顺序表或索引顺序表来进行存储表示）；（2） 查找：综合应用基本查找算法完成数据的基本查询工作，并输出查询的结果；（3） 输出：有选择性地输出满足一定条件的数据

5、记录，如输出地区编号为01，并且总分在550分以上的学生的信息；（4） 计算：计算在等概率情况下该查找表的平均查找长度。8. 排序：编制程序让机器随机产生2000个整数，放入一个数组中；对此2000个随机数序列分别用冒泡排序、快速排序、希尔排序和堆排序方法进行排序，并比较它们的运行时间。注意：每三、四个同学组成一个小组。每个实验中的题目，可分别由不同的同学完成。其它题目可以相互交流，以利于互相提高。数据结构验证性实验项目实验一 线性表的顺序存储实验一、实验目的及要求1、掌握在TC环境下调试顺序表的基本方法2、掌握顺序表的基本操作，插入、删除、查找、以及有序顺序表的合并等算法的实现。二、实验学时

6、2学时三、实验任务1、 生成一个顺序表并动态地删除任意元素和在任意位置插入元素。2、 将两个有序表合并成一个有序表。四、实验重点、难点1、 在顺序表中移动元素。2、 在顺序表中找到正确的插入位置。五、操作要点 (一)顺序表基本操作的实现问题描述 当我们要在顺序表的第i个位置上插入一个元素时，必须先将顺序表中第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。基本要求 要求生成顺序表时，可以键盘上读取元素，用顺序存储结构实现存储。实现提示 要实现基本操作，可用实现的基本操作，也可设计简单的算法实

7、现。程序实现#include #include typedef int DataType ;# define maxnum 20typedef structint datamaxnum;int length;SeqList;/*插入函数*/int insert(SeqList *L , int i , DataType x)/* 将新结点x插入到顺序表L第i个位置 */ int j ;if( i(*L).length +1) printf( n i 值不合法 ! ); return 0;if(* L).length =maxnum-1) printf( n 表满不能插入!); return 0

8、; for(j=(*L).length;j=i;j-) (*L).dataj+1=(*L).dataj;(*L).datai = x;(*L).length+;return 1;/*删除函数*/int delete( SeqList *L ,int i) /*从顺序L中删除第i个结点*/ int j ;if( i(*L).length ) printf( n 删除位置错误 ! ) ;return 0;for(j=i+1;j=(*L).length;j+)(*L).dataj-1 =(*L).dataj;(*L).length-;return 1;/*生成顺序表*/void creatlist(

9、SeqList * L) int n , i , j ;printf(请输入顺序表 L 的数据个数：n) ;scanf(%d , &n) ;for(i=0 ; in ; i+) printf(data%d = , i) ; scanf(%d,&(*L).datai);(*L).length=n-1;printf(n) ;/*creatlist */*输出顺序表 L*/printout(SeqList * L) int i ;for (i=0 ; i=(* L).length ; i+) printf( data%d=, i) ; printf(%d, (*L).datai);/*printou

10、t */printf(n);main() SeqList *L ;char cmd ;int i , t , x;clrscr() ;creatlist(L);doprintf(ni , I - 插入n) ;printf(d , D - 删除n) ;printf(q , Q - 退出n) ;docmd=getchar() ;while(cmd!=i)&(cmd!=I)&(cmd!=d)&(cmd!=D)&(cmd!=q)&(cmd!=Q);switch(cmd) case i: case I:printf(nPlease input the DATA: );scanf(%d,&x) ;prin

11、tf(nWhere? );scanf(%d,&i) ;insert(L,i,x) ;printout(L);break ;case d:case D :printf(nWhere to Delete? );scanf(%d,&i);delete(L,i);printout(L);break ;while(cmd!=q)&(cmd!=Q);（二）有序顺序表的合并问题描述 已知顺序表la和lb中的数据元素按非递减有序排列，将la和lb表中的数据元素，合并成为一个新的顺序表lc基本要求 lc中的数据元素仍按非递减有序排列，并且不破坏la和lb表程序实现# include # define maxnu

12、m 20typedef int DataType ;typedef struct DataType datamaxnum ; int length ;SeqList ;int MergeQL(SeqList la , SeqList lb , SeqList *lc) int i , j , k ;if (la.length+1 + lb.length+1maxnum) printf(narray overflow!) ;return 0;i=j=k=0;while(i=la.length & j=lb.length) if (la.dataidatak+=la.datai+ ;else lc

13、-datak+=lb.dataj+;/* 处理剩余部分 */while (idatak+=la.datai+;while (jdatak+=lb.dataj+;lc-length=k-1;return 1;main() SeqList la=3,4,7,12,15,4 ;SeqList lb=2,5,7,15,18,19,5 ;SeqList lc ;int i ;if (MergeQL(la,lb,&lc) printf(n) ;for(i=0;i=lc.length ; i+)printf(%4d,lc.datai); 六、注意事项1、 删除元素或插入元素表的长度要变化。2、 在合并表中当

14、某一个表到表尾了就不用比较了，直接将另一个表的元素复制到总表去即可。实验二 单链表实验一、实验目的及要求1、掌握用在TC环境下上机调试单链表的基本方法2、掌握单链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现3、进一步掌握循环单链表的插入、删除、查找算法的实现二、实验学时4学时三、实验任务1、在带头结点的单链表h中第i个数据元素之前插入一个数据元素。2、将两个有序单链表合并成一个有序单链表。3、生成一个循环单链表。4、在循环单链表中删除一个节点。四、实验重点、难点1、 在单链表中寻找到第i-1个结点并用指针p指示。2、 比较两个单链表的节点数据大小。3、循环单链表中只有一个节点的判

15、断条件。4、在循环单链表中删除一个节点。五、操作要点（一）单链表基本操作的实现问题描述要在带头结点的单链表h中第i个数据元素之前插入一个数据元素x ，首先需要在单链表中寻找到第i-1个结点并用指针p指示，然后申请一个由指针s 指示的结点空间，并置x为其数据域值，最后修改第i-1个结点，并使x结点的指针指向第i个结点，要在带头结点的单链表h中删除第i个结点，首先要计数寻找到第i个结点并使指针p指向其前驱第i-1个结点，然后删除第i个结点并释放被删除结点空间。基本要求用链式存储结构实现存储实现提示链式存储结构不是随机存储结构，即不能直接取到单链表中某个结点，而要从单链表的头结点开始一个一个地计数寻

16、找。程序实现# include # include typedef char DataType ;typedef struct node DataType data; /*结点的数据域*/ struct node *next; /*结点的指针域*/ListNode;void Init_List(ListNode *L)(*L)=(ListNode *)malloc(sizeof(ListNode);/*产生头结点*/(*L)-next=NULL;int List_Length(ListNode *L )int n=0;ListNode *p=L-next;while(p!=NULL)n+;p=

17、p-next;return n;ListNode* GetNode(ListNode *L,int i) int j; ListNode *p; p=L;j=0; /*从头结点开始扫描*/ while(p-next&j!=i) /*顺指针向后扫描,直到p-next为NULL或i=j为止*/ p=p-next; j+; if(i=j) return p; /*找到了第i个结点*/ else return NULL; /*当i0时,找不到第i个结点*/ void InsertList(ListNode *L,DataType x,int i) ListNode *p,*s; p=GetNode(L

18、,i-1); /*寻找第i-1个结点*/ if (p=NULL) /*in+1时插入位置i有错*/ printf(position error); return ; s=(ListNode *)malloc(sizeof(ListNode); s-data=x;s-next=p-next;p-next=s; void DeleteList(ListNode *L ,int i)ListNode *p,*r;p=GetNode(L,i-1); /*找到第i-1个结点*/if (p=NULL|p-next=NULL) /*in时,删除位置错*/ printf(position error); re

19、turn ; r=p-next; /*使r指向被删除的结点a*/p-next=r-next; /*将ai从链上删除*/free(r); /*使用头插法建立带头结点链表算法*/ListNode * CreatListF(void)char ch;ListNode *head=(ListNode *)malloc(sizeof(ListNode); /*生成头结点*/ListNode *s; /*工作指针*/head-next=NULL; ch=getchar(); /*读入第1个字符*/while(ch!=n) s=(ListNode *)malloc(sizeof(ListNode); /*生

20、成新结点*/ s-data=ch; /*将读入的数据放入新结点的数据域中*/ s-next=head-next; head-next=s; ch=getchar(); /*读入下一字符*/return head; /*使用尾插法建立带头结点链表算法*/ListNode * CreatListR1(void) char ch; ListNode *head=(ListNode *)malloc(sizeof(ListNode); /*生成头结点*/ ListNode *s,*r; /*工作指针*/ r=head; /*尾指针初值也指向头结点*/ while(ch=getchar()!=n) s=

21、(ListNode *)malloc(sizeof(ListNode); s-data=ch; r-next=s; r=s; r-next=NULL; /*终端结点的指针域置空,或空表的头结点指针域置空*/ return head; /*复制链表A中的内容到表B中*/ void copy(ListNode *a, ListNode *b) ListNode *pa=a-next; ListNode *u; ListNode *rb=b; while(pa!=NULL) u=( ListNode *)malloc(sizeof(ListNode); u-data=pa-data; rb-next

22、=u; rb=u; pa=pa-next;rb-next=NULL;/*输出带头结点的单链表*/void DisplaySL(ListNode *la, char *comment) ListNode *p ; p=la-next ; if(p) printf(n%sn , comment) ; while(p)printf(%4c,p-data);p=p-next; printf(n) ;/*主函数*/main( ) ListNode *la ,*lb,*lc, *p ;int n,x,i;printf(n用头插法建立链表la，请输入节点内容:);la=CreatListF();Displa

23、ySL(la,新生成链la节点内容:); printf(n链表la的长度: %2d,List_Length(la);printf(n请输入要插入的元素: );scanf(%c,&x) ;printf(n请输入要插入的位置：);scanf(%d,&i) ;InsertList(la,x,i);DisplaySL(la,插入后链la节点内容);printf(n请输入要删除元素的位置：);scanf(%d,&i);DeleteList(la,i);DisplaySL(la, 删除后链la节点内容);printf(n用尾插法建立链表lb，请输入节点内容:);fflush(stdin);lb=Creat

24、ListR1();DisplaySL(lb,新生成链lb节点内容:); Init_List(&lc);copy(la,lc);DisplaySL(lc,复制生成的链lc节点内容:); （二）有序单链表的合并问题描述 已知单链表la和lb中的数据元素按非递减有序排列，将la和lb中的数据元素,合并为一个新的单链表lc,lc中的数据元素仍按非递减有序排列。基本要求 不破坏la表和lb表的结构。程序实现#include #include#define NULL 0typedef int DataType;typedef struct SLNode DataType data; struct SLNo

25、de * next; slno;int MergeSL(slno *la,slno *lb,slno *lc);int CreateSL(slno *la,int n);void DisplaySL(slno *la , char * comment);void main( ) slno *la, *lb, *lc ;int n,m;la=(slno *)malloc(sizeof(slno);la-next=NULL;lb=(slno *)malloc(sizeof(slno);lb-next=NULL;lc=(slno *)malloc(sizeof(slno);lc-next=NULL;

26、printf(n 输入链la节点数:);scanf(%d,&n);printf(n 输入链la 节点内容:);CreateSL(la,n);DisplaySL(la,链la 节点内容:);printf(n 输入链lb节点数:);scanf(%d,&m);printf(n 输入链lb节点内容:);CreateSL(lb,m);DisplaySL(lb,链lb 节点内容:);if(MergeSL(la,lb,&lc) DisplaySL(lc,合成后的链lc:);getchar();int MergeSL(slno * la , slno *lb,slno *lc) slno * pa, * pb

27、, * pc; *lc=(slno *)malloc(sizeof(slno); pa=la-next; pb=lb-next; pc= *lc; while(pa&pb) pc-next=(slno*)malloc(sizeof(slno); pc=pc-next; if(pa-datadata) pc-data=pa-data; pa=pa-next; else pc-data=pb-data; pb=pb-next; while (pa) /*插入la链的剩余段 */ pc-next=(slno*)malloc(sizeof(slno); pc=pc-next; pc-data=pa-d

28、ata; pa=pa-next; /*插入lb链的剩余段*/ while(pb) pc-next=(slno*)malloc(sizeof(slno); pc=pc-next; pc-data=pb-data; pb=pb-next; pc-next=NULL; return 1;/*生成单链表*/int CreateSL(slno *la ,int n) int i ;slno *p , *q ;q=la ;for (i=1 ; idata) ;q-next=p;q=p;q-next=NULL ;return 1 ;/*输出单链表*/void DisplaySL(slno *la, char

29、 *comment) slno *p ;p=la-next ;if(p) printf(n%sn , comment) ;while(p) printf(n%3d , p-data);p=p-next ;printf(n) ;printf(n) ;（三） 约瑟夫环问题问题描述设有N个人围坐一圈，现从某个人开始报数，数到M的人出列，接着从出列的下一个人开始重新报数，数到M的人以出列，如此下去，直到所有人都出列为此。试设计确定他们的出列次序序列的程序。基本要求 选择单向循环链表作为存储结构模拟整个过程，并依次输出列的各人的编号。实现提示 程序运行之后，首先要求用户指定初始报数的下限值，可以n=30

30、,此题循环链表可不设头节点，而且必须注意空表和非空表的界限。如 n=8, m=4 时，若从第一个人， 设每个人的编号依次为 1，2，3，开始报数，则得到的出列次序为4，8，5，2，1，3，7，6，如下图所示，内层数字表示人的编号 ，每个编号外层的数字代表人出列的序号。程序实现#include #include typedef struct node int num; struct node *next; linklist;linklist *creat(head,n) /*使n个人围成一圈，并给每个人标识号数*/ linklist *head; int n ; linklist *s,*p;

31、int i; s=(linklist * )malloc(sizeof(linklist); head=s; s-num=1; p=s; for(i=2;inum=i; p-next=s; p=s; p-next=head; return(head); /* creat */linklist * select(linklist *head, int m) linklist *p, *q; int i, t; p=head; t=1; q=p; /* q为p的前趋指针*/ p=p-next; do t=t+1 ; /*报一次数*/ if(t%m=0) printf(%4d, p-num); q-

32、next=p-next; free(p); p=q-next; else q=p; p=p-next; while(q!=p); head=p; printf(%4d,p-num); return (head); /* select */main( ) int n,m; linklist *head; printf(ninput the total number:n=); scanf(%d, &n); printf(ninput the number to call:m=); scanf(%d, &m); head=creat(head,n); head=select(head,m); pri

33、ntf(nthe last one is :%d, head-num); /* main */六、注意事项 1、在第i个节点前删除或插入节点需要用指针来表示第i-1个节点。2、在合并链表时需要设置多个指针变量。3、如果不是要删除的节点则指针后移，否则删除该节点。七、思考题1、编程实现两个循环单链表的合并。实验三 栈、队列的实现及应用一、实验目的及要求1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。2、掌握栈和队列的特点，即先进后出与先进先出的原则。3、掌握栈和队列的基本操作实现方法。二、实验学时2学时三、实验任务1. 实现栈的顺序存储2. 利用栈实现数制转换四、实验重点

34、、难点1. 进栈、出栈栈顶指针都要改变。2. 数制转换结束的判断条件。五、操作要点（一）实现栈的顺序存储# define MAXSIZE 100 typedef int ElemType;typedef struct ElemType dataMAXSIZE; int top;SeqStack; void InitStack(SeqStack *s) s-top=0; return 1;int StackEmpty(SeqStack *s) if(s-top=0) return 1; else return 0;int StackFull(SeqStack *s) if(s-top=MAXSI

35、ZE-1) return 1; else return 0; void Push(SeqStack *s,int x) if (StackFull(s) printf(the stack is overflow!n); return 0; else s-datas-top=x; s-top+; void Display(SeqStack *s) if(s-top=0) printf(the stack is empty!n); else while(s-top!=0) printf(%d-,s-datas-top); s-top=s-top-1; ElemType Pop(SeqStack *

36、s) if(StackEmpty(s) return 0; else return s-data-s-top; ElemType StackTop(SeqStack *s) int i;if(StackEmpty(s) return 0; else i=s-top-1;return s-datai; /*返回栈顶元素的值，但不改变栈顶指针*/ main(SeqStack *p) int n,i,k,h,x1,x2,select; printf(create a empty stack!n); InitStack(p); printf(input a stack length:n); scanf

37、(%d,&n); for(i=0;i%dn,x1); display(p); break; case 4:x2=StackTop(p);printf(x2-%d,x2);break; （二）利用栈实现数制转换 # define MAXSIZE 100typedef int ElemType； /*将顺序栈的元素定义为整型*/typedef struct ElemType dataMAXSIZE; int top;SeqStack; void InitStack(SeqStack *s) s-top=0; return 1;int StackEmpty(SeqStack *s) if(s-top

38、=0) return 1; else return 0;int StackFull(SeqStack *s) if(s-top=m-1) return 1; else return 0; void Push(SeqStack *s,int x) if (StackFull(s) printf(the stack is overflow!n); return 0; else s-datas-top=x; s-top+; ElemType Pop(SeqStack *s) ElemType y; if(StackEmpty(s) printf(the stack is empty!n); retu

39、rn 0; else y=s-datas-top; s-top=s-top-1; return y; ElemType StackTop(SeqStack *s) if(StackEmpty(s) return 0; else return s-datas-top;void Dec_to_Ocx (int N) /* n是非负的十进制整数，输出等值的八进制数*/SeqStack *S； /*定义一个顺序栈*/ElemType x； Init_SeqStack(S)； /*初始化栈*/if(Ndata=x; t-lchild=creat(); t-rchild=creat(); return(t

40、);/*creat*/* 前序遍历二叉树t */void preorder(BiTree t) if(t!=NULL) printf(%4d,t-data); preorder(t-lchild);preorder(t-rchild); /* 中序遍历二叉树t */void inorder(BiTree t) if(t!=NULL) inorder(t-lchild); printf(%4d,t-data); inorder(t-rchild); /* 后序遍历二叉树t */void postorder(BiTree t) if(t!=NULL) postorder(t-lchild); po

41、storder(t-rchild); printf(%4d,t-data); void enqueue(BitTNode *t)if (front!=(rear+1)%M) rear=(rear+1)%M; querear=t; /*enqueue*/BitTNode * delqueue() if(front=rear)return NULL; front=(front+1)%M; return (quefront); /*delqueue*/* 按层次遍历二叉树t */void levorder(BiTree t) BitTNode *p; if(t!=NULL) enqueue(t);

42、while (front!=rear) p=delqueue(); printf(%4d,p-data); if(p-lchild!=NULL) enqueue(p-lchild); if(p-rchild!=NULL) enqueue(p-rchild); /* levorder */main()BitTNode *root; root=creat();printf(n按先序遍历次序生成的二叉树); printf(n前序遍历二叉树); preorder(root);printf(n中序遍历二叉树); inorder(root);printf(n后序遍历二叉树); postorder(root); printf(