数据结构实验指导书.docx
- 文档编号:12950692
- 上传时间:2023-06-09
- 格式:DOCX
- 页数:165
- 大小:64.49KB
数据结构实验指导书.docx
《数据结构实验指导书.docx》由会员分享,可在线阅读,更多相关《数据结构实验指导书.docx(165页珍藏版)》请在冰点文库上搜索。
数据结构实验指导书
《数据结构》
实验指导书
贵州大学
电子信息学院
通信工程
实验一顺序表的操作
实验学时:
2学时
实验类型:
验证
实验要求:
必修
一、实验目的和要求
1、熟练掌握线性表的基本操作在顺序存储和链式存储上的实现。
2、以线性表的各种操作(建立、插入、删除等)的实现为重点。
3、掌握线性表的动态分配顺序存储结构的定义和基本操作的实现。
二、实验内容及步骤要求
1、定义顺序表类型,输入一组整型数据,建立顺序表。
typedefintElemType;//定义顺序表
structList{
ElemType*list;
intSize;
intMaxSize;
};
2、实现该线性表的删除。
3、实现该线性表的插入。
4、实现线性表中数据的显示。
5、实现线性表数据的定位和查找。
6、编写一个主函数,调试上述算法。
7、完成实验报告。
三、实验原理、方法和手段
1、根据实验内容编程,上机调试、得出正确的运行程序。
2、编译运行程序,观察运行情况和输出结果。
四、实验条件
运行Visualc++的微机一台
五、实验结果与分析
对程序进行调试,并将运行结果进行截图、对所得到的的结果分析。
六、实验总结
记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等,并将其写入实验报告中。
【附录----源程序】
#include
#include
usingnamespacestd;
typedefintElemType;
structList
{
ElemType*list;
intSize;
intMaxSize;
};
//初始化线性表
boolInitList(List&L)
{
L.MaxSize=20;
L.list=newElemType[L.MaxSize];
for(inti=0;i<20&&L.list==NULL;i++)
{
L.list=newElemType[L.MaxSize];
}
if(L.list==NULL)
{
cout<<"无法分配内存空间,退出程序"< returnfalse; } L.Size=0; returntrue; } //向线性表中插入元素 boolInsertList(List&L,intpos,ElemTypeitem) { if(pos>L.Size+1||pos<1) { cout<<"位置无效"< returnfalse; } elseif(L.Size==L.MaxSize) { intk=sizeof(ElemType); L.list=(ElemType*)realloc(L.list,2*L.MaxSize*k); if(L.list==NULL) { cout<<"动态分配内存失败,退出运行"< returnfalse; } L.MaxSize=2*L.MaxSize; } for(inti=L.Size-1;i>=pos-1;i--) { L.list[i+1]=L.list[i]; } L.list[pos-1]=item; L.Size++; returntrue; } //删除线性表中的元素 boolDeleteList(List&L,ElemType&item,intpos) { if(L.Size==0) { cout<<"线性表中没有元素,无法删除"< returnfalse; } if(pos<1||pos>L.Size) { cout<<"位置无效"< returnfalse; } item=L.list[pos-1]; for(inti=pos;i L.list[i-1]=L.list[i]; L.Size--; if(float(L.Size)/L.MaxSize<0.4&&L.Size>10) { intk=sizeof(ElemType); L.list=(ElemType*)realloc(L.list,L.MaxSize*k/2); L.MaxSize=L.MaxSize/2; } returntrue; } //输出线性表 boolPrint(List&L) { if(L.Size==0) { cout<<"线性表中无元素"< returnfalse; } cout<<"线性表为: "< for(inti=0;i { cout< } cout<<"线性表长度为"< returntrue; } //查找数据 boolGetList(ListL,ElemTypeitem,intpos) { if(pos<1||pos>L.Size) { cout<<"位置无效"< returnfalse; } intk; cout<<"按位置查找选择1,按元素查找选择0"< cin>>k; if(k==1) { cout<<"第"< returntrue; } elseif(k==0) { for(inti=0;i { if(L.list[i]==item) cout<<"你要找的元素为"<<": "< if(i==L.Size) { cout<<"没有你要找的元素"< returnfalse; } } } else { cout<<"查找无效,请选择0或1"< returnfalse; } } voidmain() { Listm; InitList(m);//初始化线性表 Print(m); cout<<"请输入十个数据"< for(inti=0;i<10;i++) { cin>>m.list[i]; m.Size++; } Print(m); cout<<"向线性表中第r个位置插入s"< cout<<"请输入r,s"< intr; ElemTypes; cin>>r>>s; cout<<"(m,r,s)"< InsertList(m,r,s); Print(m); cout<<"查找数据s或者查找第r个数据"< cin>>s>>r; GetList(m,s,r); Print(m); ElemTypef=0; cout<<"删除第r个数据"< cin>>r; DeleteList(m,f,r); Print(m); cout<<"删除的数据是"< } 实验二链表操作 实验学时: 2学时 实验类型: 验证 实验要求: 必修 一、实验目的和要求 1、掌握链表的概念,了解线性表的链式存储结构,学会定义线性表的链式存储结构。 2、加深对链式存储数据结构的理解,逐步培养解决实际问题的编程能力。 2、实验内容及步骤要求 1、简单链表的基本操作 (1)编写链表基本操作函数。 ①初始化链表InitList(LIST*L,intms) ②向链表指定位置插入元素InsertList1(LIST*L,intitem,intrc) ③向有序链表指定位置插入元素InsertList2(LIST*L,intitem,intrc) ④删除指定元素之的链表记录DeleteList(LIST*L,intitem) ⑤查找链表中的元素FindList(LIST*L,intitem) (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、编译运行程序,观察运行情况和输出结果。 四、实验条件 运行Visualc++的微机一台 五、实验结果与分析 对程序进行调试,并将运行结果进行截图、对所得到的的结果分析。 六、实验总结 记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等,并将其写入实验报告中。 【附录----简单链表的基本操作源程序】 /*线性表实验程序--单链表*/ #include #include /*抽象数据类型定义*/ typedefintElemType; typedefstructnode { ElemTypedata; structnode*next; }*LKList,LNode; voidInitList(LKList*L);/*初始化线性表*/ voidCreateList(LKList*L);/*创建线性表*/ intGetLength(LKList*L);/*获得线性表的长度*/ intGetElem(LKList*L,inti,ElemType*e);/*取线性表第i个表元素,并放在e指向的的内存中*/ intSetElem(LKList*L,inti,ElemType*e);/*修改第i个表元素*/ intInsertElem(LKList*L,inti,ElemType*e);/*在第i个位置插入元素*/ intDeleteElem(LKList*L,inti);/*删除第i个元素*/ intSearchElem(LKList*L,ElemType*e);/*查找元素*e的位置i*/ intTraversList(LKList*L);/*遍历线性表*/ voidClearList(LKList*L);/*清除线性表*/ LKListFindElem(LKList*L,inti);/*取第i个元素的地址*/ /*抽象数据类型的操作实现*/ voidInitList(LKList*L)/*初始化线性表*/ { *L=NULL; } voidCreateList(LKList*L)/*创建线性表*/ { inti,ok; ElemTypee; InitList(L); i=0; printf("inputendwhileenter-9999! \n"); while (1) { scanf("%d",&e); if(e! =-9999) {ok=InsertElem(L,++i,&e); if(! ok)break; } else break; } } intGetLength(LKList*L)/*获得线性表的长度*/ { inti=0; LKListp=*L; while(p) { i++; p=p->next; } returni; } LKListFindElem(LKList*L,inti) { LKListp=*L; intj=0; if(p==NULL) return0; while(p) { j++; if(j==i)break; p=p->next; } returnp; } intGetElem(LKList*L,inti,ElemType*e)/*取线性表第i个表元素,并放在e指向的的内存中*/ { LKListp=FindElem(L,i); intj=0; if(p==NULL) return0; *e=p->data; return1; } intSetElem(LKList*L,inti,ElemType*e)/*修改第i个表元素*/ { LKListp=FindElem(L,i); intj=0; if(p)p->data=*e; return1; } intInsertElem(LKList*L,inti,ElemType*e)/*在第i个位置插入元素*/ { LKListp=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; return1; } if(p==NULL){ printf("Invalidpositiontoinsert! \n"); return0; } else {s->next=p->next; p->next=s; } return1; } intDeleteElem(LKList*L,inti)/*删除第i个元素*/ { LKListp,q; if(*L==NULL)return0; if(i==1) {p=*L; *L=(*L)->next; free(p); return1; } p=FindElem(L,i-1); if(p) { q=p->next; p->next=q->next; if(q)free(q); } else{ printf("InvalidpositiontoDelete! \n"); return0; } return1; } intSearchElem(LKList*L,ElemType*e)/*查找元素*e的位置i*/ { LNode*p=*L; intj=0; while(p) { j++; if(p->data==*e)break; } returnp? j: 0; } intTraversList(LKList*L)/*遍历线性表*/ { LNode*p=*L; ElemTypee; if(p==NULL) {printf("LineastisEmpty! ! ! \n"); return0; } while(p) {e=p->data; printf("%6d",e); p=p->next; } return1; } voidClearList(LKList*L)/*清除线性表*/ { LNode*p,*q; p=*L; while(p) { q=p->next; free(p); p=q; } *L=NULL; } /***********测试数据结构的正确性*****************/ intdisplayMenu() { printf("\n1.CreateList\n"); printf("2.DisplayList\n"); printf("3.DeleteaElement\n"); printf("4.InsertaElement\n"); printf("5.DisplayListlength\n"); printf("6.Changei'stElementvalue\n"); printf("7.Geti'stElementValue\n"); printf("8.ClearyourList\n"); printf("0.Exitmyprogram! \n"); fflush(stdin); returngetchar(); } voidmain() { LKListL; charch; ElemTypee; inti; InitList(&L); while((ch=displayMenu())! ='0') { switch(ch) { case'1': printf("NowCreateaList! \n"); CreateList(&L); break; case'2': printf("YourListis\n"); TraversList(&L); break; case'3': printf("PleaseEnteraNoofElementyouwanttodelete! \n"); scanf("%d",&i); DeleteElem(&L,i); TraversList(&L); break; case'4': printf("PleaseEnteraElemnetvalueandPositionyouwillInsert! (e,i)\n"); scanf("%d%d",&e,&i); InsertElem(&L,i,&e); TraversList(&L); break; case'5': printf("LengthofListis%d\n",GetLength(&L)); break; case'6': printf("PleaseEnteraElementvalueandpositionyouwillChange! (e,i)\n"); scanf("%d%d",&e,&i); SetElem(&L,i,&e); TraversList(&L); break; case'7': printf("Geti'stElementvalue\nPleaseEnteri: \n"); scanf("%d",&i); GetElem(&L,i,&e); printf("data[%d]=%d\n",i,e); break; case'8': ClearList(&L); if(GetLength(&L)==0) printf("Now,youlisthasnoelement! ! \n"); break; case'0': printf("yourprogramisrunningisover! \n"); break; default: printf("PleaseEntercharactorbetween'0'and'8'! \n"); break; } } } 【附录----约瑟夫环问题源程序】 /*Josephcycle*/ #include #include #include typedefintElemType; typedefstructLNode { ElemTypedata; structLNode*next; }LNode,*POINTER,*LinkList; voidinit_linklist(LinkList*l); voidrelease_linklist(LinkList*l); voidclear_linklist(LinkListl); voidcrt_linklist(LinkList*l); voiddisp_linklist(LinkListl); voidgame(LinkListl); voidexitgame(void); voidinit_linklist(LinkList*l)/*对循环单链表进行初始化*/ { (*l)=(POINTER)malloc(sizeof(structLNode)); (*l)->data=-1; (*l)->next=(*l); } voidclear_linklist(LinkListl)/*对循环单链表清空*/ { POINTERp,useless; p=l->next; l->next=l; while(p! =l) { useless=p; p=p->next; free(useless); } } voidcrt_linklist(LinkList*l)/*输入数据创建约瑟夫环表*/ { intnum; POINTERp; clear_linklist(*l); printf("\n\nInputsomeintnumbers(endingwith-1): \n"); scanf("%d",&num); while(num! =-1) { p=(POINTER)malloc(sizeof(structLNode)); p->data=num; p->next=(*l)->next; (*l)->next=p; scanf("%d",&num); } } voiddisp_linklist(LinkListl)/*显示表中元素内容*/ {inti=1,row=1; POINTERp=l->next; printf("\n\n"); while(p!
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 指导书