数据结构试验报告.docx
- 文档编号:4416114
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:94
- 大小:162.76KB
数据结构试验报告.docx
《数据结构试验报告.docx》由会员分享,可在线阅读,更多相关《数据结构试验报告.docx(94页珍藏版)》请在冰点文库上搜索。
数据结构试验报告
数据结构实验报告
作者:
顾博君
指导老师:
揭安全
时间:
2012年12月
江西师范大学计算机信息工程学院学生实验报告
(一)
专业__物联网姓名_顾博君学号__1108061001日期__2012/12/14
课程名称
数据结构
实验室名称
X4313
实验名称
线性表
指导教师
揭安全
成绩
1、实验目的
掌握线性表的基本操作:
插入、删除、查找以及线性表合并等运算在顺序存储结构
和链接存储结构上的运算。
2、实验原理和内容
原理:
应用单链表的知识,把单链表的首位相接即构成循环单链表。
循环单链表的结构体
和一般单链表的结构体是相同的。
我们要找第i个节点,就需要从head出发,当指
针又指向了head,说明循环链表以遍历完毕。
如果在这之前找到了i,指针就停在
当前位置。
否则给出提示信息,提示第i个节点不存在。
内容:
删除单循环链表中第i个结点的直接前趋结点。
i从键盘输入。
3、实验步骤
(1)分析题目,理清思路,设计算法和数据结构。
(2)上机调试程序,修改程序的语法和逻辑错误。
(3)再次分析题目和算法,优化程序。
(4)根据程序的错误总结经验和教训。
(5)写出实验程序的实验报告。
4、程序及运行结果(或实验数据记录及分析)
●程序源代码:
#include
#include
/**
*单循环链表结构体
*/
typedefstructnode{
intdata;
structnode*next;
}node,*pnode;
/**
*函数功能:
建立一个空的单循环链表
*/
pnodeinit(){
returnNULL;
}
/**
*函数功能:
尾插法建立一个新的单循环链表
*/
pnodecreat(){
pnodehead=NULL,s,r;
intx;
printf("Pleaseinputsomeintegerdata:
\n");
scanf("%d",&x);
while(x!
=0){
s=(pnode)malloc(sizeof(node));
s->data=x;
if(head==NULL)head=r=s;
else{
r->next=s;
r=s;
}
scanf("%d",&x);
}
if(r)r->next=head;
returnhead;
}
/**
*函数功能:
获得循环单链表的最后一个节点的存储地址
*/
pnoderear(pnodehead){
pnodep;
if(!
head)//如果头节点为空,说明单循环链表为空
p=NULL;
else{
p=head;//让p等于头节点
while(p->next!
=head){//如果p没有走回到头节点,说明没有找到最后一个节点
p=p->next;//让p指向下一个节点
}
}
returnp;
}
/**
*函数功能:
输出循环单链表中各个节点的值
*/
voiddisplay(pnodehead){
pnodep;
if(!
head)printf("\n循环单链表是空的!
\n");//如果链表是空的输出提示信息
else{
printf("\n循环单链表各个节点的值非别为:
\n");//输出提示信息
printf("%5d",head->data);//输出头节点所指节点的节点值
p=head->next;//p指向头节点的下一个节点
while(p!
=head){//如果没有走回到头节点
printf("%5d",p->data);//输出该节点的节点值
p=p->next;//p指向下一个节点
}
}
}
/**
*函数功能:
循环单链表中查找值为x的节点的存储地址
*/
pnodefind(pnodehead,intx){
pnodeq;
if(!
head){
printf("\n循环单链表是空的!
无法找指定节点!
");
returnNULL;
}
q=head;//q指向单循环链表的第一个节点,准备查找
while(q->next!
=head&&q->data!
=x)//如果没有走到结尾并且没有找到
q=q->next;//q指向下一个节点,继续向下找
if(q->data==x)returnq;//如果找到了返回q的位置
elsereturnNULL;//如果没有找到返回空
}
/**
*函数功能:
循环单链表第i个节点后插入值为x的新节点
*/
/**
*函数功能:
del
*/
pnodedele(pnodehead,intn){
pnodepre=NULL,q;
inti=1;
if(!
head){
printf("\n循环单链表是空的,无法做删除操作!
\n");
returnhead;
}
q=head;
while(q->next!
=head&&i i++; pre=q; q=q->next; } if(q->next==head&&i! =n){ printf("没有找到第%d个节点! \n",n); } else{ if(q! =head){ pre->next=q->next;free(q); } elseif(head->next==head){ free(q); head=NULL; } else{ pre=head->next; while(pre->next! =q)pre=pre->next; head=head->next; pre->next=head; free(q); } } returnhead; } voidprint(pnodehead){ pnodeq; if(! head){ printf("\n循环单链表是空的! "); return; } q=head;//q指向单循环链表的第一个节点,准备查找 while(q->next! =head){//如果没有走到结尾 printf("%5d",q->data); q=q->next;//q指向下一个节点 } printf("%5d\n",q->data); } intmain(){ pnodehead; head=creat(); print(head); dele(head,1); print(head); } 江西师范大学计算机信息工程学院学生实验报告 (一) 专业__物联网姓名_顾博君学号__1108061001日期__2012/12/14 课程名称 数据结构 实验室名称 X4313 实验名称 线性表 指导教师 揭安全 成绩 1、实验目的 掌握线性表的基本操作: 插入、删除、查找以及线性表合并等运算在顺序存储结构 和链接存储结构上的运算。 掌握双链表的基本操作。 2、实验原理和内容 原理: 应用单链表的知识,将单链表的前后节点相接构成双链表。 双链表的结构体和一般 单链表的结构体稍有不同,我们需要两个指针域。 遍历双链表的方法遍历单链表的 方法基本相同。 双链表的插入,当找到待插入位置时,我们需要把节点的左右指针 都连接好,还要注意第一个节点和最后一个节点的处理。 双链表的删除,当找到待 删除的节点后,我们要处理好,该节点前后的两个节点的连接。 内容: 双链表的基本操作,双链表的插入、删除和创建 3、实验步骤 (1)分析题目,理清思路,设计算法和数据结构。 (2)上机调试程序,修改程序的语法和逻辑错误。 (3)再次分析题目和算法,优化程序。 (4)根据程序的错误总结经验和教训。 (5)写出实验程序的实验报告。 4、 程序及运行结果(或实验数据记录及分析) ●程序源代码: ------------------------------------------------头文件---------------------------------------------- /**双链表的创建、打印、释放操作 *name: dlinklist.h *type: 头文件 *author: gubojun *time: 2012-10-3 */ #include #include typedefintdatatype; typedefstructnode { datatypedata; structnode*llink,*rlink; }dlinknode; typedefdlinknode*dlinklist; /*头插法建立双链表*/ dlinklistcreat1() { dlinklisthead,s; datatypex; head=NULL; printf("Inputsomeintegerdata: \n"); scanf("%d",&x); while(x! =0) { s=(dlinklist)malloc(sizeof(dlinknode)); s->data=x; s->rlink=head; if(head)head->llink=s; head=s; scanf("%d",&x); } returnhead; } /*尾插法建立双链表*/ dlinklistcreat2() { dlinklisthead,r,s; datatypex; head=r=NULL; printf("Inputsomeintegerdata: \n"); scanf("%d",&x); while(x! =0){ s=(dlinklist)malloc(sizeof(dlinknode)); s->data=x; s->llink=NULL; if(head==NULL) head=s; else r->rlink=s,s->llink=r; r=s; scanf("%d",&x); } if(r)r->rlink=NULL; returnhead; } /*输出双链表*/ voidprint(dlinklisthead) { dlinklistp; p=head; printf("Listis: \n"); while(p) { printf("%5d",p->data); p=p->rlink; } printf("\n"); } /*释放双链表的内容*/ voiddelList(dlinklisthead) { dlinklistp=head; while(p) { head=p->rlink; free(p); p=head; } } /** *插入双链表,x插入值为y的节点的前面 *author: gubojun *time: 2012-10-3 */ #include"dlinklist.h" /** *函数名称: charux *函数功能: 插入双链表,x插入值为y的节点的前面 *入口参数: 头节点 *出口参数: 头节点 */ dlinklistcharux(dlinklisthead,intx,inty) { dlinklistp,s; if(! head){ printf("这是空的双链表! \n"); returnNULL; } p=head; while(p){ if(p->data==y){ s=(dlinklist)malloc(sizeof(dlinknode)); s->data=x; if(p==head){ s->llink=NULL; s->rlink=head; head->llink=s; head=s; returnhead; } else{ s->llink=p->llink; p->llink->rlink=s; s->rlink=p; p->llink=s; returnhead; } } p=p->rlink; } if(! p)printf("没有找到%d。 \n",y); returnhead; } intmain() { dlinklisthead; head=creat2(head);//尾插法建立双链表 head=charux(head,2,3); print(head); delList(head); } 江西师范大学计算机信息工程学院学生实验报告 (二) 专业__物联网姓名_顾博君学号__1108061001日期__2012/12/14 课程名称 数据结构 实验室名称 X4313 实验名称 栈与队列 指导教师 揭安全 成绩 1、实验目的 掌握栈与队列的基本操作,并能对其进行简单应用。 熟悉栈和队列的结构和原理, 能熟练的应用栈和队列解决各种问题。 2、实验原理和内容 原理: 应用栈与队列的知识,首先定义一个栈的结构体,然后对十进制数求模,即得到二 进制数的一位,我们将得到每一位二进制数存入栈的结构中,由于产生的二进制数 是从低位到高位产生的,而输出时需要从高位向低位输出。 根据栈的性质,先进后 出,就可以实现把后进栈的高位先输出,从而实现二进制数的输出。 内容: 利用栈的基本操作将一个十进制的正整数转换成二进制的数据,并将其转换结果输 出。 3、实验步骤 (1)分析题目,理清思路,设计算法和数据结构。 (2)上机调试程序,修改程序的语法和逻辑错误。 (3)再次分析题目和算法,优化程序。 (4)根据程序的错误总结经验和教训。 (5)写出实验程序的实验报告。 4、 程序及运行结果(或实验数据记录及分析) ●程序源代码: #include //定义栈的结构体 typedefstruct{ intdata[50]; inttop; }Stack; Stackstac; /** *函数名称: DtoB *函数功能: 将一个十进制数转化为二进制数输出 *入口参数: int十进制数 *出口参数: 无 */ voidDtoB(intn){ inti,j; stac.top=-1; while(n! =0){ i=n%2; n=n/2; stac.data[++stac.top]=i;//进栈 } while(stac.top! =-1){ printf("%d",stac.data[stac.top--]);//出栈打印 } } intmain(){ intn,ans; printf("请输入一个十进制数: \n"); scanf("%d",&n); printf("%d的二进制表示为: \n",n); DtoB(n); } 江西师范大学计算机信息工程学院学生实验报告 (二) 专业__物联网姓名_顾博君学号__1108061001日期__2012/12/14 课程名称 数据结构 实验室名称 X4313 实验名称 栈与队列 指导教师 揭安全 成绩 1、实验目的 掌握栈与队列的基本操作,并能对其进行简单应用。 熟悉栈和队列的结构和原理, 能熟练的应用栈和队列解决各种问题。 2、实验原理和内容 原理: 应用栈与队列的知识,迷宫问题可以采用栈来解决,开始问题是由起始点找到到终 点的出路,从起始点(第一点)开始移动,按一定顺序分别向上下左右方向移动, 移动一步后,这个问题就变为由第二点找到到终点的出路,这样就将问题分解了, 以此类推可以将问题最终归结为倒数第二点到终点的寻找出路问题,从而问题得到 了解决。 内容: 给定一个迷宫,四周是墙壁,设计一个算法求出从入口到出口的路径。 3、实验步骤 (1)分析题目,理清思路,设计算法和数据结构。 (2)上机调试程序,修改程序的语法和逻辑错误。 (3)再次分析题目和算法,优化程序。 (4)根据程序的错误总结经验和教训。 (5)写出实验程序的实验报告。 4、 程序及运行结果(或实验数据记录及分析) ●程序源代码: ---------------------------------------------头文件------------------------------------------------- /** *name: 迷宫求解 *auther: gubojun *time: 2012-10 */ //--------------------------------------------------- #include #include #defineseqstacksize1000/*栈的最大空间大小*/ typedefstruct{ intord;//通道块在路径上的“序号” intseat[2];//通道块在迷宫中的“坐标位置” intdir;//从此通道块走到下一通道块的“方向” }mazeType;//栈的元素类型 //---------------基本操作------------------------------- //构造一个空栈s typedefmazeTypedatatype; typedefstructstack{ datatypedata[seqstacksize];/*向量data用于存储栈数据*/ inttop;/*栈顶指示*/ }seqstack; voidinitstack(seqstack*s)/*栈初始化*/ {s->top=-1; } intstackempty(seqstack*s)/*判栈空*/ {returns->top==-1; } intstackfull(seqstack*s)/*判栈满*/ {returns->top==seqstacksize-1; } /*进栈*/ voidpush(seqstack*s,datatypex) {s->data[++s->top]=x; } /*出栈*/ datatypepop(seqstack*s) {returns->data[s->top--]; } /*取栈顶元*/ datatypestacktop(seqstack*s) {returns->data[s->top]; } /** *name: 迷宫求解 *auther: gubojun *time: 2012-10 *本程序算法来自《数据结构》(严蔚敏版)P51 */ //--------------------------------------------------- #include"Stack.h" #include #defineMAZE_X15 #defineMAZE_Y15 intmaze[MAZE_X][MAZE_Y]; intcurstep=1; //实现光标定位到(x,y) voidgotoxy(intx,inty) { COORDcoord={x,y}; SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),coord); } voidcolorxy(intx,inty) { HANDLEhOut; hOut=GetStdHandle(STD_OUTPUT_HANDLE); SetConsoleTextAttribute(hOut,x|y); } //验证当前位置是否可以通过,即是未曾走到过的通道块 //1可以通过,0不能通过 intPass(intmaze[MAZE_X][MAZE_Y],intcurpos[2]){ if(maze[curpos[0]][curpos[1]]==0)return1; return0; } //留下足迹 voidFootPrint(intmaze[MAZE_X][MAZE_Y],intcurpos[2]){ maze[curpos[0]][curpos[1]]=curstep; } //下一个点 voidNextPos(intcurp[2],inti){ if(i==1)curp[1]++; elseif(i==2)curp[0]--; elseif(i==3)curp[1]--; elseif(i==4)curp[0]++; } //当前位置不可以通过 voidMarkPrint(intmaze[MAZE_X][MAZE_Y],intpos[2]){ maze[pos[0]][pos[1]]=-1; } intMazePath(intmaze[MAZE_X][MAZE_Y],intstart[2],intend[2]){ seqstack*s; mazeType*e; inti; intcurpos[2]; curpos[0]=start[0];curpos[1]=start[1]; curstep=1; s=(seqstack*)malloc(sizeof(seqstack)); e=(mazeType*)malloc(sizeof(mazeType)); initstack(s); do{ if(Pass(maze,curpos)){//当前位置可以通过,即是未曾走到过的通道块 FootPrint(maze,curpos);//留下足迹 //----------------打印---------- gotoxy(curpos[1]*2,curpos[0]); colorxy(0x0a,0x0a); printf("+"); Sleep(200); //------------------------------ e->ord=curstep; e->seat
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 试验报告
![提示](https://static.bingdoc.com/images/bang_tan.gif)