数据结构实验一 顺序结构程序设计.docx
《数据结构实验一 顺序结构程序设计.docx》由会员分享，可在线阅读，更多相关《数据结构实验一 顺序结构程序设计.docx（26页珍藏版）》请在冰点文库上搜索。
数据结构实验一顺序结构程序设计
实验一顺序结构程序设计
实验课程名：
线性表的实验
专业班级：
计算机科学与技术学号：
姓名：
实验时间：
11.6-11.13实验地点：
指导教师：
一、实验目的
1、掌握用VisualC++6.0上机调试顺序表的基本方法
2、掌握顺序表的基本操作，插入、删除、查找、以及有序顺序表的合并等算法的实现
3、掌握用VisualC++6.0上机调试单链表的基本方法
4、掌握单链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现
5、进一步掌握循环单链表和双链表的插入、删除、查找算法的实现
（二）下面是顺序表的部分基本操作实现的算法，请同学们自己设计主函数和部分算法，调用这些算法，完成下面的实验任务。
1、顺序表基本操作的实现。
要求生成顺序表时，可以键盘上读取元素，用顺序存储结构实现存储。
#defineMAXSIZE100//MAXSIZE为线性表可能的最大长度
#include
#include
typedefintElemType;
typedefstruct
{
ElemTypedata[MAXSIZE];
intlength;//length为线性表的长度
}SqList;
SqListl;//线性表定义
voidInitList（SqList&L）//初始化操作，将线性表L置空
{
L.length=0;//g给顺序表长度初始化为0
}
voidCreatSqlist（SqList&L,intn）//建立一个顺序存储的线性表
{
printf（"请输入节点"）;
inti;
for（i=0;iscanf（"%d",&L.data[i]）;//读取元素
L.length=n;//表的长度就是元素的个数
fflush（stdin）;//清除一个流
}
voidOutput（SqList&L）//输出顺序表L
{
inti;
for（i=0;iprintf（"%5d",L.data[i]）;//每个数据占5列
printf（"\n"）;
}
intDELETE（SqList&L,inti）//删除一个元素
{
intj;
if（i<1||i>L.length）//删除位置错误
{printf（"error"）;return0;}
else
{
for（j=i;jL.data[j-1]=L.data[j];//依次把后一个元素往前移动一个位置
L.length--;//删除之后长度减1
}
return1;
}
intINSERT（SqList&L,intx,inti）//指定位置插入元素
{
intj;
if（L.length>=MAXSIZE-1）
{printf（"overflow"）;return1;}//上溢
elseif（（i<1）||（i>L.length+1））
{printf（"error"）;return1;}
else
{for（j=L.length;j>=i-1;j--）
L.data[j+1]=L.data[j];//元素位置依次后移一位
L.data[i-1]=x;//在第i个节点上插入x
L.length=L.length+1;//插入之后长度加1
}
return0;
}
intGET（SqList&L,inti）//从表中获得一个元素
{
intm;
if（（i<0）||（i>L.length））{printf（"overflow"）;return1;}
elseif（（i>=1）&&（i<=L.length））
{
m=L.data[i-1];
}printf（"%d",m）;
return0;
}
intchazhao（SqList&L,intx）//从表中查找元素
{
inti,k;
printf（"\n请输入你要查找的元素x=?
"）;
scanf（"%d",&x）;
for（i=0;i<=（L.length+1）;i++）//从第一个元素开始查找，与X比较。
{
if（x==L.data[i]）
{printf（"要查找的元素%d位于%d上\n\n",x,i+1）;
k=0;
break;
}
}
if（k!
=0）printf（"%d不在表中",x）;
return0;
}
intPUEGE（SqList&L）//删除线性表中重复出现的多余节点
{
inti=1,j,x,y;
while（i{x=L.data[i];
j=i+1;
/*for（j=i+1;jwhile（j{
y=L.data[j];
if（x==y）DELETE（l,j）;
elsej++;
}
i++;
}
return0;
}
intmain（）
{intn,i,k,x;
InitList（l）;
printf（"请输入线性表的长度"）;
scanf（"%d",&n）;
CreatSqlist（l,n）;
Output（l）;
printf（"请输入你要删除元素的位置=?
"）;
scanf（"%d",&k）;
DELETE（l,k）;Output（l）;
printf（"请输入想要插入的数和位置x,i=?
"）;
scanf（"%d,%d",&x,&i）;
INSERT（l,x,i）;Output（l）;
printf（"请输入你要取的数在的节点位置"）;
scanf（"%d",&i）;
GET（l,i）;
chazhao（l,x）;
PUEGE（l）;
return0;
}
运行结果：
2、已知顺序表la和lb中的数据元素按非递减有序排列，将la和lb表中的数据元素，合并成为一个新的顺序表lc，lc中的数据元素仍按非递减有序排列，并且不破坏la和lb表。
#include
#definemaxnum20
typedefintDataType;
typedefstruct
{DataTypedata[maxnum];
intlength;
}SeqList;
intMergeQL（SeqListla,SeqListlb,SeqList*lc）
{inti,j,k;
if（la.length+1+lb.length+1>maxnum）
{printf（"\narrayoverflow!
"）;
return0;
}
i=j=k=0;
while（i<=la.length&&j<=lb.length）
{if（la.data[i]<=lb.data[j]）
lc->data[k++]=la.data[i++];
else
lc->data[k++]=lb.data[j++];
}
/*处理剩余部分*/
while（i<=la.length）lc->data[k++]=la.data[i++];
while（j<=lb.length）lc->data[k++]=lb.data[j++];
lc->length=k-1;
return1;
}
voidmain（）
{SeqListla={{3,4,7,12,15},4};
SeqListlb={{2,5,7,15,18,19},5};
SeqListlc;
inti;
if（MergeQL（la,lb,&lc））
{printf（"\n"）;
for（i=0;i<=lc.length;i++）
printf（"%4d",lc.data[i]）;
}
}
}
运行结果：
3．从有序顺序表A中删除那些在顺序表B和顺序表C中都出现的元素.
代码：
#include
#include
#include
#include
#defineLIST_INIT_SIZE10
#defineLISTINCREMENT10
#defineOK1
#defineERROR0
typedefintElemType;
typedefstruct/*顺序存储类型*/
{int*elem;intlength;intlistsize;}SqList;
intInitList（SqList&L）/*构造一个空线性表算法*/
{L.elem=（int*）malloc（LIST_INIT_SIZE*sizeof（int））;
if（!
L.elem）return（0）;
L.length=0;
L.listsize=LIST_INIT_SIZE;
returnOK;
}
intinput（SqList&L）/*输入*/
{inti;cout<<"输入线性表元素的个数:
";cin>>L.length;
for（i=0;i{cout<<"输入第"<";
cin>>L.elem[i];
}
returnOK;
}
intrank（SqList&L）/*线性表的排序*/
{inti,j,k;
for（i=0;ifor（j=0;jif（L.elem[j]>L.elem[j+1]）
{k=L.elem[j];L.elem[j]=L.elem[j+1];L.elem[j+1]=k;};
returnERROR;
returnOK;
}
intoutput（SqListL）/*输出*/
{inti;for（i=0;icout<returnERROR;
}
voidmain（）
{SqListLA,LB,LC;
InitList（LA）;
InitList（LB）;
InitList（LC）;
cout<<"创建线性表LA：
"<input（LA）;
cout<<"创建线性表LB：
"<input（LB）;
cout<<"创建线性表LC：
"<input（LC）;
rank（LA）;
rank（LB）;
rank（LC）;
cout<<"输出线性表LB各元素的值：
";
output（LB）;
cout<cout<<"输出线性表LC各元素的值：
";
output（LC）;
cout<cout<<"输出原线性表LA各元素的值：
";
output（LA）;
cout<inti,j,k;
for（i=0;ifor（j=0;jif（LA.elem[i]==LB.elem[j]）
{for（k=i;kLA.elem[k]=LA.elem[k+1];
LA.length--;
}
for（i=0;ifor（j=0;jif（LA.elem[i]==LC.elem[j]）
{for（k=i;kLA.elem[k]=LA.elem[k+1];
LA.length--;
}
cout<<"输出新的线性表LA各元素的值：
";
output（LA）;
cout<}
运行结果：
4．将一顺序存储的线性表（设元素均为整型量）中所有零元素向表尾集中，其他元素则顺序向表头方向集中。
若输入：
1230050478
则输出：
1235478000
运行代码：
#include
#include
#include
#include
#defineLIST_INIT_SIZE10
#defineLISTINCREMENT10
#defineOK1
#defineERROR0
typedefintElemType;
typedefstruct/*顺序存储类型*/
{int*elem;
intlength;
intlistsize;}SqList;
intInitList（SqList&L）/*构造一个空线性表算法*/
{L.elem=（int*）malloc（LIST_INIT_SIZE*sizeof（int））;
if（!
L.elem）return（0）;
L.length=0;
L.listsize=LIST_INIT_SIZE;
returnOK;
}
intinput（SqList&L）/*输入*/
{inti;cout<<"输入线性表元素的个数:
";
cin>>L.length;
for（i=0;i{cout<<"输入第"<";
cin>>L.elem[i];
}
returnOK;
}intoutput（SqListL）/*输出*/
{inti;
cout<<"输出新的线性表各元素的值：
";
for（i=0;icout<returnERROR;
}
voidmain（）
{SqListL;
InitList（L）;
input（L）;
output（L）;
cout<inti,j,k;
for（i=0;ifor（j=0;jif（L.elem[j]==0）
{k=L.elem[j];L.elem[j]=L.elem[j+1];L.elem[j+1]=k;}
output（L）;
cout<}
运行结果：
5、单链表基本操作的实现。
要求生成单链表时，可以键盘上读取元素，用链式存储结构实现存储。
代码：
#include
#include
#include
#include
typedefintelemtype;
typedefstructlnode
{
elemtypedate;
structlnode*next;
}lnode;
lnode*creat（void）
{
lnode*p2,*p1;
lnode*head;
intn;
n=0;
p1=p2=（lnode*）malloc（sizeof（lnode））;
head=NULL;
cin>>p1->date;
while（p1->date>0）
{
n=n+1;
if（n==1）
head=p1;
else
p2->next=p1;
p2=p1;
p1=（lnode*）malloc（sizeof（lnode））;
cin>>p1->date;
}
p2->next=NULL;
returnhead;
}
voidprint（lnode*head）
{
lnode*p;
p=head;
if（head==NULL）
cout<<"空表";
if（head!
=NULL）
do
{
cout<date;
p=p->next;
}while（p!
=NULL）;
cout<}
lnode*del（lnode*&head,inti）
{
lnode*p1,*p2;
intj=0;
p1=head;
if（head==NULL）
return0;
if（i==1）
{
head=head->next;
free（p1）;
}
else
{
while（p1->next&&j{
p2=p1;
p1=p1->next;
j++;
}
if（p1->next==0||j>i-1）
cout<<"没有发现"<else
{
p2->next=p1->next;
free（p1）;
}
}
returnhead;
}
lnode*insert（lnode*&head,inti,elemtypee）
{
lnode*p1,*p2,*s;
intj=0;
p1=head;
s=（lnode*）malloc（sizeof（lnode））;
s->date=e;
if（head==NULL&&i==1）
head=s;
else
{
while（p1->next&&j{
p2=p1;
p1=p1->next;
j++;
}
p2->next=s;
s->next=p1;
}
returnhead;
}
intmain（）
{
lnode*head;
head=creat（）;
inti;
elemtypee;
print（head）;
intnum;
cout<<"请输入要删除的第几位数：
"<cin>>num;
del（head,num）;
print（head）;
cout<<"请输入在第几位插入什么数：
"<cin>>i>>e;
insert（head,i,e）;
print（head）;
return0;
}
运行结果：
6、已知单链表la和lb中的数据元素按非递减有序排列，将la和lb中的数据元素,合并为一个新的单链表lc,lc中的数据元素仍按非递减有序排列。
要求①不破坏la表和lb表的结构。
②破坏la表和lb表的结构。
7、编程实现两个循环单链表的合并。
代码：
#include
#include
typedefintElemType;
typedefstructLNode
{ElemTypedata;
structLNode*next;
}LNode,*LinkList;
intprint（LinkList&L,intn）;
inthebing（LinkListL1,intn,LinkListL2,intm,LinkList&L）;
voidcreat（LinkList&L,intn）
{
LNode*p1,*p2;
p1=p2=（LNode*）malloc（sizeof（LNode））;
L=NULL;
inti;
for（i=0;i{
cin>>p1->data;
if（i==0）
L=p1;
else
p2->next=p1;
p2=p1;
p1=（LNode*）malloc（sizeof（LNode））;
}
p2->next=L;
}
intmain（）
{
LNode*L1,*L2,*L;
cout<<"请输入第一个单链表的长度：
"<intn,m;
cin>>n;
creat（L1,n）;
print（L1,n）;
cout<<"请输入第二个单链表的长度：
"<cin>>m;
creat（L2,m）;
print（L2,m）;
cout<<"合并后"<hebing（L1,n,L2,m,L）;
print（L,m+n）;
return0;
}
intprint（LinkList&L,intn）
{
inti;
for（i=0;i{
cout<data<<"";
L=L->next;
}
return0;
}
inthebing（LinkListL1,intn,LinkListL2,intm,LinkList&L）
{
inti;
LNode*p1;
L=L1;
p1=L1;
for（i=1;ip1=p1->next;
for（i=1;iL2=L2->next;
p1->next=L2->next;
return0;
}
运行结果：
8、线性表的逆置：
设有一个线性表（e0,e1,…,en-2,en-1），请编写一个函数将这个线性表原地逆置，即将线性表内容置换为（en-1,en-2,…,e1,e0）。
线性表中的数据可以为整数、字符或字符串，试分别采用顺序存储结构和链式结构来实现。
程序代码：
#include
#include
typedefintElemType;
typedefstructLNode
{ElemTypedata;
structLNode*next;
}LNode,*LinkList;
intprint（LinkList&L,intn）;
intnizhi（LNode*&L,intn）;
voidcreat（LinkList&L,intn）
{
LNode*p1,*p2;
p1=p2=（LNode*）malloc（sizeof（LN
升级会员 