数据结构实验指导书样本.doc

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。数据结构实验指导书贵州大学电子信息学院通信工程目 录实验一 顺序表的操作3实验二 链表操作8实验三 集合、 稀疏矩阵和广义表19实验四 栈和队列42实验五 二叉树操作、 图形或网状结构55实验六 查找、 排序88贵州大学实验报告109实验一 顺序表的操作实验学时: 2学时实验类型: 验证实验要求: 必修一、 实验目的和要求1、 熟练掌握线性表的基本操作在顺序存储和链式存储上的实现。2、 以线性表的各种操作( 建立、 插入、 删除等) 的实现为重点。3、 掌握线性表的动态分配顺序存储结构的定义和基本操作的实现。二、 实验内容及步骤要求1、 定义顺序表类型, 输入一组整型数据, 建立顺序表。 typedef int ElemType; /定义顺序表 struct List ElemType *list; int Size; int MaxSize; ;2、 实现该线性表的删除。3、 实现该线性表的插入。4、 实现线性表中数据的显示。5、 实现线性表数据的定位和查找。6、 编写一个主函数, 调试上述算法。7、 完成实验报告。三、 实验原理、 方法和手段1、 根据实验内容编程, 上机调试、 得出正确的运行程序。2、 编译运行程序, 观察运行情况和输出结果。四、 实验条件 运行Visual c+的微机一台五、 实验结果与分析对程序进行调试, 并将运行结果进行截图、 对所得到的的结果分析。六、 实验总结 记录实验感受、 上机过程中遇到的困难及解决办法、 遗留的问题、 意见和建议等, 并将其写入实验报告中。【附录-源程序】#include#includeusing namespace std;typedef int ElemType;struct ListElemType *list;int Size;int MaxSize;/初始化线性表bool InitList(List &L)L.MaxSize=20;L.list=new ElemTypeL.MaxSize;for(int i=0;i20&L.list=NULL;i+)L.list=new ElemTypeL.MaxSize;if(L.list=NULL)cout无法分配内存空间, 退出程序L.Size+1|pos1)cout位置无效endl;return false;else if(L.Size=L.MaxSize)int k=sizeof(ElemType);L.list=(ElemType*)realloc(L.list,2*L.MaxSize*k);if(L.list=NULL)cout动态分配内存失败, 退出运行=pos-1;i-)L.listi+1=L.listi;L.listpos-1=item;L.Size+;return true;/删除线性表中的元素bool DeleteList(List &L,ElemType &item,int pos)if(L.Size=0)cout线性表中没有元素, 无法删除endl;return false; if(posL.Size)cout位置无效endl;return false;item=L.listpos-1;for(int i=pos;iL.Size;i+)L.listi-1=L.listi;L.Size-;if(float(L.Size)/L.MaxSize10)int k=sizeof(ElemType);L.list=(ElemType*)realloc(L.list,L.MaxSize*k/2);L.MaxSize=L.MaxSize/2;return true;/输出线性表bool Print(List &L)if(L.Size=0)cout线性表中无元素endl;return false;cout线性表为: endl;for(int i=0;iL.Size;i+)coutL.listi ;cout线性表长度为L.Sizeendl;return true;/查找数据bool GetList(List L,ElemType item,int pos)if(posL.Size)cout位置无效endl;return false; int k;cout按位置查找选择1, 按元素查找选择0k;if(k=1)cout第pos个元素为L.listpos-1endl;return true;else if(k=0)for(int i=0;iL.Size;i+)if(L.listi=item)cout你要找的元素为:item在第i+1个endl;if(i=L.Size)cout没有你要找的元素endl;return false;elsecout查找无效, 请选择0或1endl;return false;void main()List m; InitList(m);/初始化线性表 Print(m);cout请输入十个数据endl;for(int i=0;im.listi;m.Size+;Print(m);cout向线性表中第r个位置插入sendl;cout请输入r, srs;cout(m,r,s)endl;/向线性表中插入元素InsertList(m,r,s);Print(m);cout查找数据s或者查找第r个数据sr;GetList(m,s,r);Print(m);ElemType f=0;cout删除第r个数据r;DeleteList(m,f,r);Print(m);cout删除的数据是fendl;实验二 链表操作实验学时: 2学时实验类型: 验证实验要求: 必修 一、 实验目的和要求 1、 掌握链表的概念, 了解线性表的链式存储结构, 学会定义线性表的链式存储结构。 2、 加深对链式存储数据结构的理解, 逐步培养解决实际问题的编程能力。二、 实验内容及步骤要求 1、 简单链表的基本操作 (1) 编写链表基本操作函数。 初始化链表InitList(LIST *L,int ms) 向链表指定位置插入元素InsertList1(LIST *L,int item,int rc) 向有序链表指定位置插入元素InsertList2(LIST *L,int item,int rc) 删除指定元素之的链表记录DeleteList(LIST *L,int item) 查找链表中的元素FindList(LIST *L,int item) (2) 调用上述函数实现下列操作, 操作步骤如下: 从键盘输入一个数据元素x, 插入到线性表中第i( 包含1号位置) 个位置; 从键盘输入一个数据元素关键字x或位置i( 包含1号位置) , 从线性表中删除相应数据元素。 2、 约瑟夫环问题 (1) 约瑟夫( Joeph) 问题的一种描述: 编号为1,2,n的n个人按顺时针方向围坐一圈, 每人持有一个密码( 正整数) 。一开始任选一个正整数作为报数上限值m, 从第一个人开始按顺时针方向自1开始顺序报数, 报到m时停止报数。报m的人出列, 将她的密码作为新的m值, 从她在顺时针方向上的下一个人开始重新从1报数, 如此下去, 直至所有人全部出列为止。 (2) 编程实现约瑟夫环问题, 利用单向循环链表存储结构模拟此过程, 按照出列的顺序印出各人的编号。 (3) 试设计一个程序求出出列顺序。并设m的初值为20; 密码: 3, 1, 7, 2, 4, 8, 4( 正确的结果应为6, 1, 4, 7, 2, 3, 5) 。 3、 完成实验报告。三、 实验原理、 方法和手段 1、 根据实验内容编程, 上机调试、 得出正确的运行程序。 2、 编译运行程序, 观察运行情况和输出结果。四、 实验条件 运行Visual c+的微机一台五、 实验结果与分析对程序进行调试, 并将运行结果进行截图、 对所得到的的结果分析。六、 实验总结 记录实验感受、 上机过程中遇到的困难及解决办法、 遗留的问题、 意见和建议等, 并将其写入实验报告中。【附录-简单链表的基本操作源程序】/* 线性表实验程序-单链表*/#include #include /*抽象数据类型定义*/typedef int ElemType;typedef struct node ElemType data; struct node *next;*LKList,LNode;void InitList(LKList *L); /*初始化线性表*/void CreateList(LKList *L); /*创立线性表*/int GetLength(LKList *L); /*获得线性表的长度*/int GetElem(LKList *L,int i,ElemType *e); /*取线性表第i个表元素, 并放在e指向的的内存中*/int SetElem(LKList *L,int i,ElemType *e); /*修改第i个表元素*/int InsertElem(LKList *L,int i, ElemType *e); /*在第i个位置插入元素*/int DeleteElem(LKList *L,int i); /*删除第i个元素*/int SearchElem(LKList *L,ElemType *e); /*查找元素*e的位置i*/int TraversList(LKList *L); /*遍历线性表*/void ClearList(LKList *L); /*清除线性表*/LKList FindElem(LKList *L,int i); /*取第i个元素的地址*/*抽象数据类型的操作实现*/void InitList(LKList *L) /*初始化线性表*/*L=NULL;void CreateList(LKList *L) /*创立线性表*/int i,ok; ElemType e;InitList(L); i=0;printf(input end while enter -9999!n); while(1)scanf(%d,&e);if(e!=-9999) ok=InsertElem(L,+i,&e); if(!ok) break; else break;int GetLength(LKList *L) /*获得线性表的长度*/ int i=0; LKList p=*L; while(p) i+; p=p-next; return i;LKList FindElem(LKList *L,int i) LKList p=*L; int j=0; if(p=NULL) return 0; while(p) j+; if(j=i) break; p=p-next; return p;int GetElem(LKList *L,int i,ElemType *e) /*取线性表第i个表元素, 并放在e指向的的内存中*/ LKList p=FindElem(L,i); int j=0; if(p=NULL) return 0; *e=p-data; return 1;int SetElem(LKList *L,int i,ElemType *e) /*修改第i个表元素*/ LKList p=FindElem(L,i); int j=0; if(p) p-data=*e; return 1;int InsertElem(LKList *L,int i, ElemType *e) /*在第i个位置插入元素*/ LKList p=FindElem(L,i-1);LNode *s; s=(LNode*)malloc(sizeof(LNode);s-data=*e;s-next=NULL; if(i=1) s-next=*L;*L=s;return 1;if(p=NULL)printf(Invalid position to insert!n); return 0;else s-next=p-next; p-next=s;return 1;int DeleteElem(LKList *L,int i) /*删除第i个元素*/ LKList p,q;if(*L=NULL)return 0;if(i=1) p=*L;*L=(*L)-next; free(p);return 1; p=FindElem(L,i-1);if(p) q=p-next; p-next=q-next; if(q)free(q);elseprintf(Invalid position to Delete!n); return 0;return 1;int SearchElem(LKList *L,ElemType *e) /*查找元素*e的位置i*/LNode *p=*L; int j=0;while(p)j+;if(p-data=*e)break;return p?j:0;int TraversList(LKList *L) /*遍历线性表*/LNode *p=*L;ElemType e;if(p=NULL)printf(Lineast is Empty!n); return 0; while(p) e=p-data; printf(%6d,e); p=p-next; return 1;void ClearList(LKList *L) /*清除线性表*/LNode *p,*q;p=*L;while(p)q=p-next;free(p);p=q;*L=NULL;/*测试数据结构的正确性*/int displayMenu()printf(n1.CreateListn);printf(2.Display Listn);printf(3.Delete a Elementn);printf(4.Insert a Elementn);printf(5.Display List lengthn);printf(6.Change ist Element valuen);printf(7.Get ist Element Valuen);printf(8.Clear your Listn);printf(0.Exit my program!n);fflush(stdin);return getchar();void main( ) LKList L; char ch; ElemType e; int i; InitList(&L); while(ch=displayMenu()!=0) switch(ch) case 1:printf(Now Create a List!n); CreateList(&L);break; case 2:printf(Your List is n); TraversList(&L);break; case 3:printf(Please Enter a No of Element you want to delete!n); scanf(%d,&i);DeleteElem(&L,i);TraversList(&L);break; case 4:printf(Please Enter a Elemnet value and Position you will Insert!(e,i)n); scanf(%d%d,&e,&i);InsertElem(&L,i,&e);TraversList(&L);break; case 5:printf(Length of List is %dn,GetLength(&L); break; case 6:printf(Please Enter a Element value and position you will Change!(e,i)n); scanf(%d%d,&e,&i);SetElem(&L,i,&e);TraversList(&L);break; case 7:printf(Get ist Element valuenPlease Enter i:n); scanf(%d,&i); GetElem(&L,i,&e);printf(data%d=%dn,i,e);break; case 8:ClearList(&L); if(GetLength(&L)=0)printf(Now,you list has no element!n);break; case 0: printf(your program is running is over!n);break; default: printf(Please Enter charactor between 0and 8!n);break; 【附录-约瑟夫环问题源程序】/* Joseph cycle*/#include #include #include typedef int ElemType;typedef struct LNodeElemType data;struct LNode *next; LNode,*POINTER,*LinkList;void init_linklist(LinkList *l);void release_linklist(LinkList *l);void clear_linklist(LinkList l);void crt_linklist(LinkList *l);void disp_linklist(LinkList l);void game(LinkList l);void exitgame(void);void init_linklist(LinkList *l)/*对循环单链表进行初始化*/(*l)=(POINTER)malloc(sizeof(struct LNode);(*l)-data=-1;(*l)-next=(*l);void clear_linklist(LinkList l)/*对循环单链表清空*/POINTER p,useless;p=l-next;l-next=l;while(p!=l)useless=p;p=p-next;free(useless);void crt_linklist(LinkList *l)/*输入数据创立约瑟夫环表*/int num;POINTER p;clear_linklist(*l);printf(nnInput some int numbers (ending with -1) :n);scanf(%d,&num);while(num!=-1)p=(POINTER)malloc(sizeof(struct LNode);p-data=num;p-next=(*l)-next;(*l)-next=p;scanf(%d,&num);void disp_linklist(LinkList l)/*显示表中元素内容*/ int i=1,row=1;POINTER p=l-next;printf(nn);while(p!=l)if(row=7)row=1;printf(n);printf(%5d:%-5d|,i,p-data);i+;row+;p=p-next;void game(LinkList l)/*元素依次根据密码值出圈*/int m,k=0;POINTER p=l,pre,u;printf(nnCount Number m=? );scanf(%d,&m);printf(nnnn%40snn,GAME START);while(p-next!=p)pre=p;p=p-next;if(p=l) pre=p; p=p-next;+k;if(k=m) printf( %d,p-data);pre-next=p-next;u=p;free(u);p=pre;k=0;printf(nn%40s,GAME OVER);void exitgame()printf(nn%40s,GOOD_BYE_GOOD !);void release_linklist(LinkList *l)/*销毁循环单链表( 约瑟夫环) */clear_linklist(*l);free(*l);void main()/*主控函数*/int select;LinkList list;init_linklist(&list);doprintf(%s%15s%15s%15s%15s,nnnnnn,1:Create,2:Display,3:Game,4:Exit);printf(nn%33c, );select=getche();switch(select)case 1: crt_linklist(&list);disp_linklist(list);break;case 2: disp_linklist(list);break;case 3: game(list);break;case 4: exitgame();break;default: printf(nWrong select ! Try again. );/*switch*/while(select!=4);release_linklist(&list);getch();实验三 集合、 稀疏矩阵和广义表实验学时: 2学时实验类型: 验证实验要求: 必修一、 实验目的及要求: 1、 掌握集合的基本运算 2、 掌握稀疏矩阵的简单运算 3、 掌握广义表的基本操作二、 实验内容及步骤要求1、 集合的运算 存储结构采用顺序表或链表; 主函数设计一个菜单, 经过菜单进入各模块测试 在集合并运算时, 检索两个集合, 将第二个集合中与第一个集合中不同的元素, 插入第一个集合。 集合交运算时, 检索两个集合, 将第一个集合中与第二个集合不同元素, 删除。 集合差运算时, 检索两个集合, 将第一个集合中与第二个集合中相同元素删除。 2、 稀疏矩阵 创立稀疏矩阵 在主程序设计一个菜单, 经过菜单进入各模块测试 实现矩阵的加、 减、 乘功能。 3、 广义表 创立广义表 在主程序设计一个菜单, 经过菜单选择要完成的操作 输入正确格式的广义表, 如 (a,b,c) 选择任意键继续, 课继续操作, 可退出三、 实验原理、 方法和手段 1、 根据实验内容编程, 上机调试、 得出正确的运行程序。 2、 编译运行程序, 观察运行情况和输出结果。四、 实验条件运行Visual c+的微机一台五、 实验结果与分析对程序进行调试, 并将运行结果进行截图、 对所得到的的结果分析。六、 实验总结记录实验感受、 上机过程中遇到的困难及解决办法、 遗留的问题、 意见和建议等, 并将其写入实验报告中。【附录-源程序】1、 集合的运算#include #include #include #define MAXSIZE 100 typedef int DataType;typedef struct node int length; DataType dataMAXSIZE; SeqList,*PSeqList;PSeqList Init_SeqList(void)/初始化PSeqList PL;PL=(PSeqList)malloc(sizeof(SeqList);if(PL)PL-length=0;return (PL); int Location_SeqList(PSeqList L, DataType x)/检索int i=0;while (ilength & L-datai!=x)i+;if(i=L-length) return 0;else return (i+1);int Insert_SeqList(PSeqList PL,int i,DataType x)/插入int j;if(!PL)printf(表不存在);return(-2);if(PL-length=MAXSIZE)printf(表溢出);return(-1);if(iPL-length+1)printf(插入位置不合法);return(0);for(j=PL-length-1; j=i-1; j-)PL-datai=x;PL-length+;return(1);int Delete_SeqList(PSeqList PL, int i)/删除int j;if(!PL)printf(表不存在);return(-1);if(iPL-length)printf(删除位置不合法);return(0);for(j=i;jlength;j+)PL-dataj-1=PL-dataj;PL-length-;return(1);void Inter_sec(PSeqList A,PSeqList B)/交集int i,j;for (i=0;ilength;+i)if(!Location_SeqList(B, A-datai)Delete_SeqList(A, i+1);for (j = 0; j length; j+) printf(%d ,A-dataj);void Merge_sec (PSeqList A, PSeqList B)/并集 int i,j;for (i=0; ilength; i+)if(!Location_SeqList(A, B-datai)Insert_SeqList(A,A-length,B-datai); for (j = 0; j length; j+)printf(%d ,A-dataj);void cha_sec (PSeqList A, PSeqList B)/差集int i,j,k;for (i=0;ilength;i+) if(k = Location_SeqList(A, B-datai)Delete_SeqList(A, k);for (j = 0; j length; j+)printf(%d ,A-dataj);void main ()PSeqList A,B;int i, k, m, x, y, menu, aMAXSIZE, bMAXSIZE;char re;A = Init_SeqList();B = Init_SeqList();printf(1 存入两个集合n);printf(2 集合的交集n);printf(3 集合的并集n);printf(4 集合的差集n);printf(0 退出n);pri