[IT认证]数据结构实验指导书.doc

数据结构 实验指导书朱素英 编 写适用专业： 计算机科学与技术 计算机网络工程 湖南人文科技学院计算机科学技术系2008 年 8 月前 言数据结构课程是计算机科学与技术专业的一门必修的专业基础课。这门课程的主要特点是实践性很强,不仅要学习基本理论知识,更要注重上机实践,通过上机实践验证算法的正确性,掌握和巩固所学理论知识。通过对本课程中算法设计和上机实践的训练，培养学生的数据抽象能力和程序设计的能力，为后续课程，特别是软件课程打下坚实的知识基础。要求学生掌握各种常用数据结构的逻辑结构，存储结构及有关操作的算法。通过本课程的学习，要求学生了解数据结构及其分类、数据结构与算法的密切关系； 熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构； 掌握设计算法的步骤和算法分析方法； 掌握数据结构在排序和查找等常用算法中的应用。为了使学生更好地理解和深刻地把握这些知识，并在此基础上，训练和培养了解数据结构及其分类、数据结构与算法的密切关系； 熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构； 掌握设计算法的步骤和算法分析方法； 掌握数据结构在排序和查找等常用算法中的应用等方面的技能，设置的以下十二个的具体实验项目，这些实验项目中有验证性实验、综合性实验与设计性实验，在每一个具体实验中都有标明。各项实验主要了解、掌握的具体知识，在每个实验中都有说明。本实验指导书对计算机科学与技术专业与网络工程专业均适应。目录实验一：顺序表的基本操作1实验二：单链表的基本操作9实验三：栈的基本操作14实验四：队列的基本操作16实验五：串的模式匹配19实验六：矩阵的基本运算22实验七：二叉树的基本操作29实验八：哈夫曼树与哈夫曼编码34实验九：图的最短路径算法38实验十：哈希表的基本操作40实验十一：各种排序算法44实验十二：银行模拟484实验一：顺序表的基本操作实验学时：2实验类型：验证实验要求：选修一、实验目的1掌握使用VC+进行控制台应用程序编写的基本方法2掌握顺序表的初始化、销毁、数据元素的插入和删除以及顺序表的输出等基本操作。二、实验内容顺序表的初始化、插入和删除三、 程序清单1、运行环境Visual c+ 6.0的微机一台2、程序清单/线性表的顺序结构算法实现 #include "stdio.h" #include "stdlib.h" # define OVERFLOW -2 # define OK 1 #define ERROR 0 /数据类型说明 typedef int ElemType; typedef int Status; # define List_init_size 100/线性表存储空间初始分配量# define Listincrement 10/线性表存储空间分配增量typedef struct ElemType *elem; /存储空间基址 int length; /当前长度 int listsize;/当前分配的存储容量 / (以sizeof(ElemType)为单位)sqlist;/初始化线性表：Status InitList(sqlist &L) /构造一个空线性表L L.elem=(ElemType *) malloc(List_init_size*sizeof(ElemType); if (!L.elem) exit(OVERFLOW); L.length=0; L.listsize= List_init_size; return OK;/在一个空的线性表中输入N个数据：Status sqlistinput(sqlist &L,int n)int i=0; if(n>L.listsize)return ERROR; for(;i<n;i+) scanf("%d",&L.elemi); L.length=n; return OK; /判线性表是否为空Status ListEmpty(sqlist L)if (!L.length) return ERROR; else return OK; /求线性表的长度Status ListLength(sqlist L) return L.length; /将线性表L 的数据输出：Status sqlistoutput(sqlist L)int i; for(i=0;i<ListLength(L);i+) printf("%4d",L.elemi); printf("n"); return OK; /取线性表的第i个元素，其结果保存在e中Status GetElem(sqlist l,int i,ElemType &e) if (i<1 | i>l.length+1) return ERROR; e=l.elemi-1; return OK; /定义两个数据元素相等的比较函数Status equal(ElemType e1,ElemType e2)if (e1=e2) return OK; else return ERROR; /根据compare()函数在线性表中定位元素e的位置int LocateElem_sq(sqlist L,ElemType e,Status (*compare)(ElemType,ElemType) /成功返回位序，否则返回0 int i=1; ElemType *p; p=L.elem; while(i<=L.length &&!(*compare)(*p+,e) +i; if (i<=L.length) return i; else return 0;/ locateElem_sq/在线性表中求某元素的前趋结点，如存在则返回其前趋结点pre_e的值，否则返回出错信息Status PriorElem(sqlist L,ElemType cur_e,ElemType &pre_e) int pos; pos=LocateElem_sq(L,cur_e,equal); if(pos=0) return ERROR; else if(pos=1) return OVERFLOW; /overflow 表示位于第一个 else GetElem(L,pos-1,pre_e); return OK; /在线性表中求某元素的后继结点Status NextElem(sqlist L,ElemType cur_e,ElemType &next_e) int pos; pos=LocateElem_sq(L,cur_e,equal); if(pos=0) return ERROR; else if(pos=L.length) return OVERFLOW; /overflow 表示最后一个 else GetElem(L,pos+1,next_e); return OK; /在线性表中插入一个元素Status Listinsert_sq(sqlist &L,int i,ElemType e) ElemType *p,*q,*newbase; if (i<1 | i>L.length+1) return ERROR; if (L.length>=L.listsize) newbase=(ElemType *) realloc(L.elem, (L.listsize+Listincrement) *sizeof(ElemType); if (!newbase) exit(OVERFLOW); L.elem=newbase; L.listsize+=Listincrement ; q=&(L.elemi-1); for(p=&(L.elemL.length-1);p>=q;-p) *(p+1)=*p; *q=e; +L.length; return OK;/ listinsert_sq;/在线性表中删除第i个元素，其结果保留在e中Status Listdelete_sq(sqlist &l,int i,ElemType &e) ElemType *p,*q; if (i<1|i>l.length+1) return ERROR; p=&(l.elemi-1); e=*p; q=l.elem+l.length-1; for(+p;p<=q;+p) *(p-1)=*p; -l.length; return OK;/ listdelete_sq;/将la和lb线性表归并到lcvoid mergelist_sq(sqlist la,sqlist lb,sqlist &lc) ElemType *pa,*pb,*pc,*pa_last,*pb_last; pa=la.elem; pb=lb.elem; lc.listsize=lc.length=la.length+lb.length; pc=lc.elem=(ElemType*)malloc(lc.listsize*sizeof(ElemType); if (!lc.elem) exit(OVERFLOW); pa_last=la.elem+la.length-1; pb_last=lb.elem+lb.length-1; while (pa<=pa_last)&& (pb<=pb_last) if (*pa<=*pb) *pc+=*pa+; else *pc+=*pb+ ; while(pa<=pa_last) *pc+=*pa+; while(pb<=pb_last) *pc+=*pb+; /mergelist_sq;/对线性表的元素进行排序Status sortsqlist(sqlist &L)/冒泡排序 int i,j,len; ElemType t; len=ListLength(L); for(i=len-1;i>=1;i-) for(j=0;j<i;j+) if (L.elemj>L.elemj+1) t=L.elemj; L.elemj=L.elemj+1 ; L.elemj+1=t; return OK; void main()sqlist la,lb,lc; int n,m,i,e,k,cur_e,pre_e,next_e; /建立线性表，并输入输出线性表的数据 InitList(la);InitList(lb); printf("please input la's numbers:n（请输入线性表la的元素个数n）n"); scanf("%d",&n); printf("please input la n numbers:( 请输入线性表la的n个元素)n"); sqlistinput(la,n); sqlistoutput(la); printf("n"); /调用插入函数，对线性表进行插入操作 printf("请输入要插入的元素的位置和插入的值 n"); scanf("%d%d",&i,&e); Listinsert_sq(la,i,e); sqlistoutput(la); /调用删除函数，对线性表进除删操作 printf("请输入要删除的元素的位置n"); scanf("%d",&i); Listdelete_sq(la,i,e); printf("the dele data is %dn",e); sqlistoutput(la); printf("please input the get data's locaten"); scanf("%d",&i);/调用GetElem()函数，取第I个位置的元素的值。 GetElem(la,i,e); printf("the get data is %dn",e); printf("please input the locateelem's data :cur_en");/调用LocateElem_sq()函数，求元素cur_e的位置。scanf("%d",&cur_e); k=LocateElem_sq(la,cur_e,equal); printf("the locate is %dn",k); /调用PriorElem()函数，求元素cur_e的前驱。 printf("please input the cur_e datan"); scanf("%d",&cur_e); PriorElem(la,cur_e,pre_e); printf("the pre_e is %dn",pre_e); /调用NextElem()函数，求元素cur_e的后继。 printf("please input the cur_e datan"); scanf("%d",&cur_e); NextElem(la,cur_e,next_e); printf("the next_e is %dn",next_e); /建立两个线性表并排序然后归并 printf("please input lb's numbers:mn"); scanf("%d",&m); printf("please input lb m numbers:n"); sqlistinput(lb,m); printf("n"); sqlistoutput(lb); sortsqlist(la); printf("the sort list la is:n"); sqlistoutput(la); sortsqlist(lb); printf("the sort list lb is:n"); sqlistoutput(lb); mergelist_sq(la,lb,lc); printf("la and lb's mergelist is:n"); sqlistoutput(lc);四、思考题1如何实现顺序表的逆置2每次删除操作时，都会使得大量的数据元素移动，删除多个数据元素时，就需多次移动数据元素。能否一次进行删除多个数据元素的操作，使得数据元素的移动只进行一次。实验二：单链表的基本操作实验学时：2实验类型：验证实验要求：必修一、 实验目的1定义单链表的结点类型。2熟悉对单链表的一些基本操作和具体的函数定义。3通过单链表的定义掌握线性表的链式存储结构的特点。4掌握循环链表和双链表的定义和构造方法二、实验内容链表的创建、插入与删除操作三、程序清单1、运行环境装有Visual c+6.0的微机一台2、程序清单/链表的创建及插入、删除操作#include "stdio.h"#include"stdlib.h"#define NULL 0#define error 0#define ok 1#define overflow -2#define infeasible -1/类型定义typedef int Status;typedef int ElemType;/定义链表的存储结构typedef struct LNodeint data; /数据域 struct LNode *next; /指针域 LNode,*LinkList; /链表的类型Status GetElem_l(LinkList L, int i , ElemType &e)/L为带头结点的单链表，当第i 个元素存在时，其值赋给e.int j;LinkList p ;p=L->next; j=1;while(p&&j<i) /顺序找第i个元素.p=p->next; +j;if(!p|j>i) return error;e=p->data;return ok;/逆序创建链表 void CreatList_L1(LinkList &L,int n) /n为元素个数，L为头结点 int i; LinkList p; L=(LinkList)malloc(sizeof(LNode); /生成头结点 L->next=NULL; for(i=n;i>0;i-) /链头插入法 p=(LinkList)malloc(sizeof(LNode); scanf("%d",&p->data); p->next=L->next; L->next=p; /正序创建单链表void CreatList_L2(LinkList &L,int n ) /n为元素个数，L为头结点int i ; LinkList p,q; L=(LinkList )malloc(sizeof(LNode);q=L;for(i=0;i<n;i+) /链尾插入法 p=(LinkList )malloc(sizeof(LNode); scanf("%d",&p->data); q->next=p; q=p; q->next=NULL;/输出链表void print(LinkList L)LinkList p; p=L->next; while(p) printf("%d ",p->data); p=p->next; /链表的插入操作int ListInsert(LinkList &L,int i,int e)LinkList p,s;int j; p=L;j=0; while(p&&j<i-1) p=p->next; +j; if(!p|j>i-1) return error; s=(LinkList)malloc(sizeof(LNode); s->data=e; s->next=p->next; p->next=s; return ok; /链表的删除操作 int ListDelete(LinkList &L,int i,int &e) LinkList p,q; int j; p=L; j=0; while(p->next&&j<i-1) p=p->next; +j; if(!(p->next)|j>i-1) return error; q=p->next;p->next=q->next; e=q->data;free(q); return ok; /对链表的元素进行排序Status sortlinklist(LinkList &L)LinkList p,q,r; ElemType t;p=L->next; /p指向链表第一个元素结点while(p->next!=NULL) q=L->next; /q指向链表第一个元素结点 while(q->next!=NULL) r=q->next; if(q->data>r->data) /相邻两个元素比较、交换 t=q->data; q->data=r->data; r->data=t; q=q->next; p=p->next; return ok ;void mergelist_l(LinkList la, LinkList &lb, LinkList &lc)LinkList pa,pb,pc; pa=la->next; pb=lb->next ; lc=pc=la;while(pa&&pb) if(pa->data <=pb->data) pc->next=pa;pc=pa;pa=pa->next; else pc->next=pb;pc=pb;pb=pb->next;pc->next=pa?pa:pb;free(lb);/主函数通过调用创建、插入、删除用输出函数完成链表的基本操作void main()LinkList L1,L2,L3; int n,ins,del,i;/创建一个先进先出单链表 printf("please input fifo linklist's node number n:n"); scanf("%d",&n); printf("please input the linklist %d nodes data n",n); CreatList_L2(L2,n); print(L2); printf("n");/创建一个后进先出单链表printf("please input lifo linklist's node number n:n"); scanf("%d",&n); printf("please input the linklist %d nodes data n",n); CreatList_L1(L1,n); print(L1); printf("n");/对链表进行插入操作 printf("please input the insert node's locate i and value en"); scanf("%d%d",&i,&ins); ListInsert(L1,i,ins); print(L1); printf("n");/对链表进行删除操作 printf("please input the delete node's locate in"); scanf("%d",&i); ListDelete(L1,i,del); print(L1); printf("n%dn",del);/对链表进行排序sortlinklist(L1);printf("n the L1 list's sort is:n");print(L1);printf("n the L2 list's sort is:n");sortlinklist(L2);print(L2);/对链表进行合并printf("n the merge result is : n" );mergelist_l(L1,L2,L3);print(L3); 四、思考题l.如果需要将新结点插入到第i个数据元素之后，算法将如何改动?2. 双向链表和循环链表的定义和构造方法。实验三：栈的基本操作实验学时：2实验类型：验证实验要求：选修一、实验目的1会定义顺序栈和链栈的结点类型。2掌握顺序栈的插入和删除结点在操作上的特点。3熟悉对顺序栈的一些基本操作和具体的函数定义。二、实验内容栈的初始化、进栈与出栈等基本操作三、程序清单1、运行环境装有Visual 60的微机一台2、程序清单#define stackinitsize 20#define stackincrement 8#include <stdlib.h>#include <stdio.h>typedef struct int *base; int *top; int stacksize;sqstack;int initstack(sqstack &s) s.base=(int * ) malloc(stackinitsize*sizeof(int); s.top=s.base; s.stacksize=stackinitsize; return 1; int push(sqstack &s,int e) s.top)=e; s.top+; return 1; int gettop(sqstack s) return *(s.top-1); int emptystack(sqstack s) if (s.top=s.base) return 1; else return 0; int pop(sqstack &s,int &e) if (emptystack(s) return 0; -s.top; *e=*s.top; return 1; Void main()Sqstack s;Int n,I,e;initstack(s);scanf(“%d”,&n);for(i=1;i<=n;i+) scanf(“%d”,&e); Push(s,e);While(!emptystack(s)pop(s,e); Printf(“%d ”,e);四、思考题 如果两个栈共用一个存储空间，该如何解决?实验四：队列的基本操作实验学时：2实验类型：验证实验要求：选修一、实验目的1会定义循环队列的结点类型。2循环队列的插入和删除结点在操作上的特点。3熟悉对循环队列的一些基本操作和具体的函数定义二、实验内容循环队列的插入与删除三、程序清单1、运行环境装有Visual 60的微机一台2、程序清单/-对列的顺序存储结构-# include "stdlib.h"# include "stdio.h"# include "time.h"/函数结果状态代码# define TURE 1# define FALSE 0# define OK 1# define ERROR 0# define OVERFLOW -2# define maxqsize 100typedef int status;typedef int qelemtype;typedef struct qelemtype *base; int front; int rear;sqqueue;/-循环队列的基本操作的算法描述-status initqueue(sqqueue &Q) /构造一个空队列Q Q.base=(qelemtype*)malloc(maxqsize*sizeof(qelemtype); if(!Q.base) return ERROR; Q.front=Q.rear=0; return OK;int queuelength(sqqueue Q) /返回Q的元素个数，即对列的长度 return (Q.rear-Q.front+maxqsize)%maxqsize;status enqueue(sqqueue &Q,qelemtype e) /插入元素e为Q的新的队尾元素 if(Q.rear+1)%maxqsize=Q.front) return ERROR; /队列满 Q.baseQ.rear=e; Q.rear=(Q.rear+1)%maxqsize; return OK;status dequeue(sqqueue &Q,qelemtype &e) /若队列不空,则删除Q的队头元素,用e返回其值,并返回OK /否则返回ERROR if(Q.front=Q.rear) return ERROR; e=Q.baseQ.front; Q.front=(Q.front+1)%maxqsize; return OK; void main() /测试基本操作 int i,e; sqqueue Q; initqueue(Q); printf("n"); for(i=1;i<=10;i+) e=i; enqueue(Q,e); printf("the length of queue is :%dn",queuelength(Q); for(i=1;i<=10;i+) dequeue(Q,e); printf(" %d",e); 四、思考题 1. 如果循环队列的下标不是从0开始，而是是从1开始，那么头指针加l的操作应如何修改?2. 在循环队列中判断队空和队满的条件能否一样，为什么?3. 用另一种不同与上面算法的方法解决“假上溢”问题。实验五：串的模式匹配实验学时：2实验类型：验证实验要求：选修一、实验目的1会定义定长顺序串的存储结构。2掌握定长顺序串的基本运算。3了解KMP算法。 二、实验内容串的模式匹配算法三、程序清单1、运行环境2、程序清单#include <stdio.h> #include <stdlib.h> #include <time.h> #include <dos.h> #define maxstrlen 255 /用可以在255以内定义最大串长 typedef unsigned char SStringmaxstrlen+1; /0好单元可以存放串的长度 int index(SString S,SString T,int pos) /利用模式串T的next函数求T在主串S中第pos个字符之后的位置 /其中T非空，1<=pos<=strlength(s). int i,j; i=pos;j=1; while(i<=S0&&j<=T0) if(Si=Tj) +i;+j;else i=i-j+2;j=1; if(j>T0) return i-T0; else return 0; /index_kmp void main() SString S=17,'a','c','a','b','a','a','b','a','a','b','c','a','c','a','a','b','c' SString T=6,'a','b','a','a','b','c' printf("nit is :%d ",index(S,T,1); /-改进的模式匹配算法- /-本算法在BC+3.1下调试通过- /-调试时间2002年4月14日- #include <stdio.h> #include <stdlib.h> #define maxstrlen 255 /用可以在255以内定义最大串长 int next7; typedef unsigned char SStringmaxstrlen+1; /0好单元可以存放串的长度 /* */ void get_next(SString T) /求模式串T的next函数值并存入数组next。 int i,j; i=1; next1=0; j=0;/ while(i<T0)if(j=0|Ti=Tj) +i; +j; nexti=j;else j=nextj; printf("nnextj is:"); for(i=1;i<=6;i+) printf("%d",nexti); /get_next int index_kmp(SString S,SString T,int pos) /利用模式串T的next函数求T在主串S中第pos个字符之后的位置 /kmp算法。其中T非空，1<=po