经典数据结构上机题—答案.docx

该【经典数据结构上机题—答案 】是由【东风倩倩】上传分享，文档一共【26】页，该文档可以免费在线阅读，需要了解更多关于【经典数据结构上机题—答案 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。数据结构上机实验题目
实验一线性表的序次储藏结构
实验学时2学时
背景知识:序次表的插入、删除及应用。
目的要求:
。
。
实验内容
,建立序次表。
。
,查找成功返回1,否则返回0。
,对称返回1,否则返回0。
,即表的前面为奇数,后边为
偶数。
。

表。
利用该序次结构实现循环队列的入队、出队操作。
,调试上述算法。
#include<>
#include<>
#defineOVERFLOW0
#defineMAXSIZE100
文档
typedefintElemType;
typedefstructlist
{ElemTypeelem[MAXSIZE];
intlength;
}Sqlist;
voidCreatlist(Sqlist&L)
{inti;
printf("请输入序次表的长度:");//输入一组整型元素序列,建立一个顺
序表。
scanf("%d",&);
for(i=0;i<;i++)
scanf("%d",&[i]);
}
voidprintlist(Sqlist&L)//以输出的形式实现对该序次表的遍历
{inti;
for(i=0;i<;i++)
printf("%d",[i]);
printf("\n");
}
voidSearchlist(Sqlist&L,intx)//在序次表中进行序次查找某一元素x,查
找成功则返回其储藏地址i,否则返回错误信息
{inti,k=-1;
for(i=0;i<;i++)
if([i]==x){
k=i+1;printf("%d",k);}
if(k==-1)
printf("error!");
printf("\n");
}
voidInseri(Sqlist&L,inti,intx)//在序次表的第i个地址上插入一个元素x
{intj;
for(j=;j>=i;j--)
[j]=[j-1];
[j]=x;
++;
}
voidDelete(Sqlist&L,inti)//删除序次表中第i个元素
{intj;
for(j=i;j<;j++)
[j-1]=[j];
--;
}
voidInsert(Sqlist&L,intx)//输入一个元素x,把它插入到有序表中,使顺
序表仍旧有序。
文档
{inti,j;
if(==MAXSIZE)exit(OVERFLOW);//表满,不能够插入for(i=1;i<=&&[i-1]<=x;i++);
for(j=;j>=i;j--)
[j]=[j-1];
[i-1]=x;
++;
}
voidCreatlist_sorted(Sqlist&L)//利用有序表插入算法建立一个有序表
{inti,num;
ElemTypex;
=0;
printf("请输入序次表的长度:");
scanf("%d",&num);
for(i=1;i<=num;i++)
{
scanf("%d",&x);
Insert(L,x);
}
}
voidMerger(Sqlist&p,Sqlist&r,Sqlist&c)//建立两个非递减有序表,并把它们合并成一个非递减有序表
{
ElemType*a,*b,i=0,j=0,k=0;
a=&[0];
b=&[0];
=+;
while(i<&&j<)
{if(*a>=*b)
{[k]=*b;b++;k++;j++;}
else{[k]=*a;a++;k++;i++;}
}
if(j==)
for(;k<;k++)
{[k]=*a;a++;}
elseif(i==)
for(;k<;k++)
{[k]=*b;b++;}
}
voidmain()
{SqlistL,M,N;
intx,i,n;
printf(".\n");
文档
printf("2.
以输出的形式对该序次表遍历.\n");
printf("3.
在序次表中进行序次查找某一元素x.\n");
printf("4.
在序次表的第i个地址上插入一个元素x.\n");
printf("5.
删除序次表中第i个元素.\n");
printf("6.
利用有序表插入算法建立一个有序表.\n");
printf("7.
建立两个非递减有序表,并把它们合并成一个非递减有序表
.\n");
printf("8.
输入一个元素x,把它插入到有序表中,使序次表仍旧有序
.\n");
while(1){
printf("请选择:");
scanf("%d",&n);
switch(n)
{case1:Creatlist(L);break;
case2:printlist(L);break;
case3:printf("请输入要查找的元素x:");
scanf("%d",&x);
Searchlist(L,x);break;
case4:printf("请输入要插入的地址i:");
scanf("%d",&i);
if(i<1||i>+1){
printf("error!\n");break;}
printf("请输入要插入的值x:");
scanf("%d",&x);
Inseri(L,i,x);
printlist(L);break;
case5:printf("请输入要删去的元素的地址i:");
scanf("%d",&i);
if(i<1||i>){
printf("error!\n");break;}
Delete(L,i);
printlist(L);break;
case6:Creatlist_sorted(L);
printlist(L);break;
case7:Creatlist_sorted(L);
Creatlist_sorted(M);
Merger(L,M,N);
printlist(N);break;
case8:Creatlist_sorted(L);
printf("请输入要插入的元素x:");
scanf("%d",&x);
Insert(L,x);
printlist(L);break;
}
}
文档
}
实验二链式储藏结构(一)----单向链表的有关操作
实验学时3学时
背景知识:单向链表的插入、删除及应用。
目的要求
。
、删除算法及其应用算法的程序实现。
实验内容
,建立一个带头结点的单向链表(无
序)。
。
(不一样意申请新的结点空间)。
。
,
并利用该函数建立一个非递减有序单向链表。
,尔后合并成一个非递加
链表。
,尔后合并成一个非递减
链表。
,实现将其分解成两个链表,其中一个全部
为奇数,另一个全部为偶数(尽量利用已知的储藏空间)。
文档
。
,分别调试上述算法。
*:利用链表实现一个班级学生信息管理(数据录入、插入、删除、排序、
查找等,并能够实现将数据储藏到文件中)
/*单向链表的有关操作示例*/
/*种类定义及头文件部分,*/
#include<>
#include<>
typedefintElemType;//元素实质种类
typedefstructLNode{
ElemTypedata;
structLNode*next;
}LNode,*LinkList;//定义结点、指针种类名
//头插法建立无序链表
voidCreateList(LinkList&L){
LinkListp;
ElemTypee;
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;
printf("头插法建立链表,以0结束\n");
scanf("%d",&e);
while(e){
p=(LinkList)malloc(sizeof(LNode));
p->data=e;
p->next=L->next;
L->next=p;
scanf("%d",&e);
}
}
/*非递减有序单向链表L插入元素e序列仍有序*/
voidInsert_Sort(LinkList&L,ElemTypee){
LinkListp,s;
s=(LinkList)malloc(sizeof(LNode));
s->data=e;
p=L;
while(p->next&&p->next->data<=e)
p=p->next;/*查找插入地址*/
s->next=p->next;/*插入语句*p结点后插入*s结点*/p->next=s;
}
/*建立递加有序的单向链表*/
文档
voidCreate_Sort(LinkList&L){
ElemTypee;
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;
printf("建立有序表,输入任意个整型数据以0结束\n");
scanf("%d",&e);
while(e){
Insert_Sort(L,e);
scanf("%d",&e);
}
}
/*单向链表的遍历*/
voidTraverse(LinkListL){
LinkListp;
printf("遍历链表");
for(p=L->next;p;p=p->next)
printf("%5d",p->data);
printf("\n");
}
/*在单向链表删除元素e*/
voidDelete(LinkList&L,ElemTypee){
LinkListp,q;
p=L;
q=L->next;
while(q&&q->data!=e){//查找元素的删除地址
p=q;
q=q->next;
}
if(!q)printf("\nnotdeleted");/*未找到元素e*/
else{p->next=q->next;/*找到删除*/
free(q);}
}
/*单向链表的逆置*/
voidexch(LinkList&L){
LinkListp,s;
p=L->next;
L->next=NULL;
while(p){
s=p;
p=p->next;
s->next=L->next;
L->next=s;
}
}
文档
/*两个非递减有序单向链表合并后仍为非递减序列*/
voidMergeIncrease(LinkListLa,LinkListLb,LinkList&Lc){
LinkListp,q,s,rear;
p=La->next;
q=Lb->next;
Lc=rear=La;
free(Lb);
while(p&&q){
if(p->data<q->data){s=p;p=p->next;}
else{s=q;q=q->next;}
rear->next=s;/*较小元素插入表尾*/
rear=rear->next;
}
if(p)rear->next=p;elserear->next=q
实验三迷宫问题求解
实验学时3学时
背景知识:栈的操作。
目的要求
。
。
实验内容:
以一个mxn的长方阵表示迷宫,0和1分别表示迷宫中的通路和障
碍。设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通
路,或得出没有通路的结论。
要求:第一实现一个序次或链表做储藏结构的栈种类,尔后编写一个
求解迷宫的非递归程序。求得的通路以三元组(i,j,d)的形式输出,其
中:(i,j)表示迷宫的坐标,d表示走到下一坐标的方向。如对下边的
文档
迷宫,输出的一条通路为:(1,1,1),(1,2,2),(2,2,2),(3,
2,3),(3,1,2),...
迷宫约定,x方向为行方向,y方向为列方向,迷宫开始坐标(左上
角)为(1,1)。
#include<>
#include<>
#include<>
structnode
{
intsign;//表记,0什么都不在,1在open中,2在closed中
intflag;//标志位0/1,0能够走,1不能够够走
intf,g,h;//判断函数
intx,y;//坐标
intold;//可否old节点,0非,1是
};
structlink
{
nodefnode;
link*next;
link*pri;
};
文档
link*open,*closed,*bestnode,*successor,*p,*q,*r,*s;
intmaze_flag[7][7]={{0,1,0,0,0,0,0},
{0,1,0,1,0,1,0},
{0,1,0,0,0,1,0},
{0,1,0,1,0,1,0},
{0,0,0,1,0,0,0},
{1,1,0,1,0,1,0},
{0,0,0,0,0,1,0}};//表示迷宫的数组,0能够走,1不能够够走
nodemaze[7][7];
intjudge(noden)//判断函数,判断n节点可否能够走
{
if(==1)
return(1);
else
return(0);
}
voidin_open(noden)//将n节点放入open表
{
p=open;
while(p->next!=open)
{
if(>=p->)
{
p->next->pri=(link*)malloc(sizeof(link));
p->next->pri->pri=p;
p=p->next;
p->pri->next=p;
p->pri->pri->next=p->pri;
p=p->pri;
p->=;
p->=;
p->=;
p->=;
p->=;
p->=;
p->=;
p->==1;
}
else
p=p->next;
文档