数据结构上机题答案.docx

数据结构上机题答案.docx

《数据结构上机题答案.docx》由会员分享，可在线阅读，更多相关《数据结构上机题答案.docx（36页珍藏版）》请在冰点文库上搜索。

数据结构上机题答案

数据结构上机实验题目

实验一线性表的顺序存储结构

实验学时2学时

背景知识:

顺序表的插入、删除及应用。

目的要求：

1．掌握顺序存储结构的特点。

2．掌握顺序存储结构的常见算法。

实验内容

1．输入一组整型元素序列，建立顺序表。

2．实现该顺序表的遍历。

3．在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。

4．判断该顺序表中元素是否对称,对称返回1,否则返回0。

5．实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。

6．输入整型元素序列利用有序表插入算法建立一个有序表。

7．利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表。

8.利用该顺序结构实现循环队列的入队、出队操作。

8．编写一个主函数,调试上述算法。

#include

#include

#defineOVERFLOW0

#defineMAXSIZE100

typedefintElemType;

typedefstructlist

{ElemTypeelem[MAXSIZE];

intlength;

}Sqlist;

voidCreatlist（Sqlist&L）

{inti;

printf（"请输入顺序表的长度：

"）;//输入一组整型元素序列，建立一个顺序表。

scanf（"%d",&L.length）;

for（i=0;i

scanf（"%d",&L.elem[i]）;

}

voidprintlist（Sqlist&L）//以输出的形式实现对该顺序表的遍历

{inti;

for（i=0;i

printf（"%d",L.elem[i]）;

printf（"\n"）;

}

voidSearchlist（Sqlist&L,intx）//在顺序表中进行顺序查找某一元素x，查找成功则返回其存储位置i，否则返回错误信息

{inti,k=-1;

for（i=0;i

if（L.elem[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=L.length;j>=i;j--）

L.elem[j]=L.elem[j-1];

L.elem[j]=x;

L.length++;

}

voidDelete（Sqlist&L,inti）//删除顺序表中第i个元素

{intj;

for（j=i;j

L.elem[j-1]=L.elem[j];

L.length--;

}

voidInsert（Sqlist&L,intx）//输入一个元素x，把它插入到有序表中，使顺序表依然有序。

{inti,j;

if（L.length==MAXSIZE）exit（OVERFLOW）;//表满，不能插入

for（i=1;i<=L.length&&L.elem[i-1]<=x;i++）;

for（j=L.length;j>=i;j--）

L.elem[j]=L.elem[j-1];

L.elem[i-1]=x;

L.length++;

}

voidCreatlist_sorted（Sqlist&L）//利用有序表插入算法建立一个有序表

{inti,num;

ElemTypex;

L.length=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=&p.elem[0];

b=&r.elem[0];

c.length=p.length+r.length;

while（i

{if（*a>=*b）

{c.elem[k]=*b;b++;k++;j++;}

else{c.elem[k]=*a;a++;k++;i++;}

}

if（j==r.length）

for（;k

{c.elem[k]=*a;a++;}

elseif（i==p.length）

for（;k

{c.elem[k]=*b;b++;}

}

voidmain（）

{SqlistL,M,N;

intx,i,n;

printf（"1.建立一个顺序表.\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>L.length+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>L.length）{

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学时

背景知识：

单向链表的插入、删除及应用。

目的要求

1．掌握单向链表的存储特点及其实现。

2．掌握单向链表的插入、删除算法及其应用算法的程序实现。

实验内容

1．随机产生或键盘输入一组元素，建立一个带头结点的单向链表（无序）。

2．遍历单向链表。

3．把单向链表中元素逆置（不允许申请新的结点空间）。

4．在单向链表中删除所有的偶数元素结点。

5．编写在非递减有序链表中插入一个元素使链表元素仍有序的函数，并利用该函数建立一个非递减有序单向链表。

6．利用算法5建立两个非递减有序单向链表，然后合并成一个非递增链表。

7．利用算法5建立两个非递减有序单向链表，然后合并成一个非递减链表。

8．利用算法1建立的链表，实现将其分解成两个链表，其中一个全部为奇数，另一个全部为偶数（尽量利用已知的存储空间）。

*9．采用单向链表实现一元多项式的存储并实现两个多项式相加并输出结果。

10．在主函数中设计一个简单的菜单，分别调试上述算法。

*11．综合训练：

利用链表实现一个班级学生信息管理（数据录入、插入、删除、排序、查找等，并能够实现将数据存储到文件中）

/*单向链表的有关操作示例*/

/*类型定义及头文件部分,文件名为sllink.h*/

#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->datadata）{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学时

背景知识：

栈的操作。

目的要求

1．掌握栈的存储特点及其实现。

2．掌握栈的出栈和入栈操作。

实验内容：

以一个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（n.flag==1）

return

（1）;

else

return（0）;

}

voidin_open（noden）//将n节点放入open表

{

p=open;

while（p->next!

=open）

{

if（n.f>=p->fnode.f）

{

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->fnode.flag=n.flag;

p->fnode.f=n.f;

p->fnode.g=n.g;

p->fnode.h=n.h;

p->fnode.x=n.x;

p->fnode.y=n.y;

p->fnode.old=n.old;

p->fnode.sign=n.sign=1;

}

else

p=p->next;

}

open->pri=（link*）malloc（sizeof（link））;

open->pri->pri=p;

open->pri->next=open;

p->next=open->pri;

p=p->next;

p->fnode.flag=n.flag;

p->fnode.f=n.f;

p->fnode.g=n.g;

p->fnode.h=n.h;

p->fnode.x=n.x;

p->fnode.y=n.y;

p->fnode.old=n.old;

p->fnode.sign=n.sign=1;

}

voidout_open（noden）//将n节点从open表中移出

{

p=open;

while（p->next!

=open）

{

if（n.f=p->fnode.f）

{

link*p1;

p1=p->next;

p->next=p->next->next;

p->next->pri=p;

free（p1）;

n.sign=0;

}

else

p=p->next;

}

}

voidin_closed（noden）//将n节点放入closed表

{

while（q->next!

=closed）

{

if（n.f>=q->fnode.f）

{

q->next->pri=（link*）malloc（sizeof（link））;

q->next->pri->pri=q;

q=q->next;

q->pri->next=p;

q->pri->pri->next=q->pri;

q=q->pri;

q->fnode.flag=n.flag;

q->fnode.f=n.f;

q->fnode.g=n.g;

q->fnode.h=n.h;

q->fnode.x=n.x;

q->fnode.y=n.y;

q->fnode.old=n.old;

q->fnode.sign=n.sign=2;

}

else

q=q->next;

}

closed->pri=（link*）malloc（sizeof（link））;

closed->pri->pri=q;

closed->pri->next=closed;

q->next=closed->pri;

q=q->next;

q->fnode.flag=n.flag;

q->fnode.f=n.f;

q->fnode.g=n.g;

q->fnode.h=n.h;

q->fnode.x=n.x;

q->fnode.y=n.y;

q->fnode.old=n.old;

q->fnode.sign=n.sign=2;

}

voidout_closed（noden）//将n节点从closed表中移出

{

q=closed;

while（q->next!

=closed）

{

if（n.f=q->fnode.f）

{

link*q1;

q1=q->next;

q->next=q->next->next;

q->next->pri=q;

free（q1）;

n.sign=0;

}

else

q=q->next;

}

}

voidin_bestnode（noden）//将n节点设为bestnode节点

{

while（r->next!

=bestnode）

{

if（n.f>=r->fnode.f）

{

r->next->pri=（link*）malloc（sizeof（link））;

r->next->pri->pri=r;

r=r->next;

r->pri->next=r;

r->pri->pri->next=r->pri;

r=r->pri;

r->fnode.flag=n.flag;

r->fnode.f=n.f;

r->fnode.g=n.g;

r->fnode.h=n.h;

r->fnode.x=n.x;

r->fnode.y=n.y;

r->fnode.old=n.old;

}

else

r=r->next;

}

bestnode->pri=（link*）malloc（sizeof（link））;

bestnode->pri->pri=r;

bestnode->pri->next=bestnode;

r->next=bestnode->pri;

r=r->next;

r->fnode.flag=n.flag;

r->fnode.f=n.f;

r->fnode.g=n.g;

r->fnode.h=n.h;

r->fnode.x=n.x;

r->fnode.y=n.y;

r->fnode.old=n.old;

}

voidout_bestnode（noden）//将n节点的bestnode去掉

{

r=bestnode;

while（r->next!

=bestnode）

{

if（n.f=p->fnode.f）

{

link*r1;

r1=r->next;

r->next=r->next->next;

r->next->pri=r;

free（r1）;

}

else

r=r->next;

}

}

voidin_successor（noden）//将n节点设置为successor节点

{

s=successor;

while（s->next!

=successor）

{

if（n.f>=s->fnode.f）

{

s->next->pri=（link*）malloc（sizeof（link））;

s->next->pri->pri=s;

s=p->next;

s->pri->next=s;

s->pri->pri->next=s->pri;

s=s->pri;

s->fnode.flag=n.flag;

s->fnode.f=n.f;

s->fnode.g=n.g;

s->fnode.h=n.h;

s->fnode.x=n.x;

s->fnode.y=n.y;

s->fnode.old=n.old;

}

else

s=s->next;

}