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

《[IT认证]数据结构实验指导书.doc》由会员分享，可在线阅读，更多相关《[IT认证]数据结构实验指导书.doc（53页珍藏版）》请在三一办公上搜索。

1、 数据结构 实验指导书朱素英 编 写适用专业： 计算机科学与技术 计算机网络工程 湖南人文科技学院计算机科学技术系2008 年 8 月前 言数据结构课程是计算机科学与技术专业的一门必修的专业基础课。这门课程的主要特点是实践性很强,不仅要学习基本理论知识,更要注重上机实践,通过上机实践验证算法的正确性,掌握和巩固所学理论知识。通过对本课程中算法设计和上机实践的训练，培养学生的数据抽象能力和程序设计的能力，为后续课程，特别是软件课程打下坚实的知识基础。要求学生掌握各种常用数据结构的逻辑结构，存储结构及有关操作的算法。通过本课程的学习，要求学生了解数据结构及其分类、数据结构与算法的密切关系； 熟悉各

2、种基本数据结构及其操作，学会根据实际问题要求来选择数据结构； 掌握设计算法的步骤和算法分析方法； 掌握数据结构在排序和查找等常用算法中的应用。为了使学生更好地理解和深刻地把握这些知识，并在此基础上，训练和培养了解数据结构及其分类、数据结构与算法的密切关系； 熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构； 掌握设计算法的步骤和算法分析方法； 掌握数据结构在排序和查找等常用算法中的应用等方面的技能，设置的以下十二个的具体实验项目，这些实验项目中有验证性实验、综合性实验与设计性实验，在每一个具体实验中都有标明。各项实验主要了解、掌握的具体知识，在每个实验中都有说明。本实验指导书对

3、计算机科学与技术专业与网络工程专业均适应。目录实验一：顺序表的基本操作1实验二：单链表的基本操作9实验三：栈的基本操作14实验四：队列的基本操作16实验五：串的模式匹配19实验六：矩阵的基本运算22实验七：二叉树的基本操作29实验八：哈夫曼树与哈夫曼编码34实验九：图的最短路径算法38实验十：哈希表的基本操作40实验十一：各种排序算法44实验十二：银行模拟484实验一：顺序表的基本操作实验学时：2实验类型：验证实验要求：选修一、实验目的1掌握使用VC+进行控制台应用程序编写的基本方法2掌握顺序表的初始化、销毁、数据元素的插入和删除以及顺序表的输出等基本操作。二、实验内容顺序表的初始化、插入和删

4、除三、 程序清单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; /存储空

5、间基址 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(sq

6、list &L,int n)int i=0; if(nL.listsize)return ERROR; for(;in;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;iLi

7、stLength(L);i+) printf(%4d,L.elemi); printf(n); return OK; /取线性表的第i个元素，其结果保存在e中Status GetElem(sqlist l,int i,ElemType &e) if (il.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的位置in

8、t 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,E

9、lemType &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) r

10、eturn 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 (iL.length+1) return ERROR; if (L.length=L.listsize) newbase=(ElemType *) realloc(L.elem, (L.listsize

11、+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;

12、 if (il.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+l

13、b.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=1;i-) for(j=0;jL.elemj+1) t=L.e

14、lemj; 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 las numbers:n（请输入线性表la的元素个数n）n); scanf(%d,&n); printf(please input la n numbers:( 请输入线性表la的n个元素)n); sqlistinput(la,n); sql

15、istoutput(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 datas loca

16、ten); scanf(%d,&i);/调用GetElem()函数，取第I个位置的元素的值。 GetElem(la,i,e); printf(the get data is %dn,e); printf(please input the locateelems 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(pleas

17、e 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 lbs numbers:mn)

18、; 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 lbs mergelist is:n); sqlistoutp

19、ut(lc);四、思考题1如何实现顺序表的逆置2每次删除操作时，都会使得大量的数据元素移动，删除多个数据元素时，就需多次移动数据元素。能否一次进行删除多个数据元素的操作，使得数据元素的移动只进行一次。实验二：单链表的基本操作实验学时：2实验类型：验证实验要求：必修一、 实验目的1定义单链表的结点类型。2熟悉对单链表的一些基本操作和具体的函数定义。3通过单链表的定义掌握线性表的链式存储结构的特点。4掌握循环链表和双链表的定义和构造方法二、实验内容链表的创建、插入与删除操作三、程序清单1、运行环境装有Visual c+6.0的微机一台2、程序清单/链表的创建及插入、删除操作#include std

20、io.h#includestdlib.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为带头结点的单链表，

21、当第i 个元素存在时，其值赋给e.int j;LinkList p ;p=L-next; j=1;while(p&jnext; +j;if(!p|ji) 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;i0;i-) /链头插入法 p=(LinkList)malloc(sizeof(LNode); sca

22、nf(%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;idata); 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; /链表的插入操作i

23、nt ListInsert(LinkList &L,int i,int e)LinkList p,s;int j; p=L;j=0; while(p&jnext; +j; if(!p|ji-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&jnext; +j; if(

24、!(p-next)|ji-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-datar-data) /相邻两个元素比较、交换 t=q-data; q-data=r-d

25、ata; 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 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);/主函数通过调用创建、插入、删除用输出函数完成链表的

26、基本操作void main()LinkList L1,L2,L3; int n,ins,del,i;/创建一个先进先出单链表 printf(please input fifo linklists 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 linklists node number n:n); scanf(%d,&n

27、); printf(please input the linklist %d nodes data n,n); CreatList_L1(L1,n); print(L1); printf(n);/对链表进行插入操作 printf(please input the insert nodes locate i and value en); scanf(%d%d,&i,&ins); ListInsert(L1,i,ins); print(L1); printf(n);/对链表进行删除操作 printf(please input the delete nodes locate in); scanf(%

28、d,&i); ListDelete(L1,i,del); print(L1); printf(n%dn,del);/对链表进行排序sortlinklist(L1);printf(n the L1 lists sort is:n);print(L1);printf(n the L2 lists sort is:n);sortlinklist(L2);print(L2);/对链表进行合并printf(n the merge result is : n );mergelist_l(L1,L2,L3);print(L3); 四、思考题l.如果需要将新结点插入到第i个数据元素之后，算法将如何改动?2.

29、双向链表和循环链表的定义和构造方法。实验三：栈的基本操作实验学时：2实验类型：验证实验要求：选修一、实验目的1会定义顺序栈和链栈的结点类型。2掌握顺序栈的插入和删除结点在操作上的特点。3熟悉对顺序栈的一些基本操作和具体的函数定义。二、实验内容栈的初始化、进栈与出栈等基本操作三、程序清单1、运行环境装有Visual 60的微机一台2、程序清单#define stackinitsize 20#define stackincrement 8#include #include typedef struct int *base; int *top; int stacksize;sqstack;int i

30、nitstack(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(sqsta

31、ck &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循环队列

32、的插入和删除结点在操作上的特点。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 qelemty

33、pe;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+maxqsi

34、ze)%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.fron

35、t; 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. 在循环队列中

36、判断队空和队满的条件能否一样，为什么?3. 用另一种不同与上面算法的方法解决“假上溢”问题。实验五：串的模式匹配实验学时：2实验类型：验证实验要求：选修一、实验目的1会定义定长顺序串的存储结构。2掌握定长顺序串的基本运算。3了解KMP算法。 二、实验内容串的模式匹配算法三、程序清单1、运行环境2、程序清单#include #include #include #include #define maxstrlen 255 /用可以在255以内定义最大串长 typedef unsigned char SStringmaxstrlen+1; /0好单元可以存放串的长度 int index(SStrin

37、g 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&jT0) 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

38、.1下调试通过- /-调试时间2002年4月14日- #include #include #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(iT0)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