数据结构试验线性表的操作.docx
《数据结构试验线性表的操作.docx》由会员分享，可在线阅读，更多相关《数据结构试验线性表的操作.docx（24页珍藏版）》请在冰点文库上搜索。
数据结构试验线性表的操作
01顺序线性表的基本操作
#include
#include
#defineOK1
#defineERROR0
#defineLIST_INIT_SIZE100
#defineLISTINCREMENT10
#defineElemTypeint
typedefstruct
{
int*elem;
intlength;
intlistsize;
}SqList;
intInitList_Sq（SqList&L）
{
//算法2.3，构造一个空的线性表L，该线性表预定义大小为LIST_INIT_SIZE
L.elem=（ElemType*）malloc（LIST_INIT_SIZE*sizeof（ElemType））;
L.length=0;
L.listsize=LIST_INIT_SIZE;
returnOK;
}
intLoad_Sq（SqList&L）
{
//输出顺序表中的所有元素
inti;
if（L.length==0）printf（"TheListisempty!
"）;//请填空
else
{
printf（"TheListis:
"）;
for（i=0;i}
printf（"\n"）;
returnOK;
}
intListInsert_Sq（SqList&L,inti,inte）
{
//算法2.4，在顺序线性表L中第i个位置之前插入新的元素e
if（i<1||i>L.length+1）returnERROR;
ElemType*newbase,*q,*p;
if（L.length>=L.listsize）
{
newbase=（ElemType*）realloc（L.elem,（L.listsize+LISTINCREMENT）*sizeof（ElemType））;
L.elem=newbase;
L.listsize+=LISTINCREMENT;
}
q=&（L.elem[i-1]）;
for（p=&（L.elem[L.length-1]）;p>=q;--p）
*（p+1）=*p;
*q=e;
++L.length;
returnOK;
}
intListDelete_Sq（SqList&L,inti,int&e）
{
//算法2.5,在顺序线性表L中删除第i个位置的元素，并用e返回其值
ElemType*p,*q;
if（i<1||i>L.length）returnERROR;
p=&（L.elem[i-1]）;
e=*p;
q=L.elem+L.length-1;
for（++p;p<=q;++p）
*（p-1）=*p;
--L.length;
returnOK;
}
intmain（）
{
SqListT;
inta,i;
ElemTypee,x;
if（InitList_Sq（T））//判断顺序表是否创建成功
{
printf（"ASequenceListHasCreated.\n"）;
}
while
（1）
{
printf（"1:
Insertelement\n2:
Deleteelement\n3:
Loadallelements\n0:
Exit\nPleasechoose:
\n"）;
scanf（"%d",&a）;
switch（a）
{
case1:
scanf（"%d%d",&i,&x）;
if（!
ListInsert_Sq（T,i,x））printf（"InsertError!
\n"）;//判断i值是否合法，请填空
elseprintf（"TheElement%disSuccessfullyInserted!
\n",x）;
break;
case2:
scanf（"%d",&i）;
if（!
ListDelete_Sq（T,i,e））printf（"DeleteError!
\n"）;//判断i值是否合法，请填空
elseprintf（"TheElement%disSuccessfullyDeleted!
\n",e）;
break;
case3:
Load_Sq（T）;
break;
case0:
return1;
}
}
}
02合并顺序表
#include"stdio.h"
#include"malloc.h"
#defineOK1
#defineERROR0
#defineLIST_INIT_SIZE100
#defineLISTINCREMENT10
#defineElemTypeint
typedefstruct
{
int*elem;
intlength;
intlistsize;
}SqList;
intInitList_Sq（SqList&L）
{
//算法2.3，构造一个空的线性表L，该线性表预定义大小为LIST_INIT_SIZE
L.elem=（ElemType*）malloc（LIST_INIT_SIZE*sizeof（ElemType））;
L.length=0;
L.listsize=LIST_INIT_SIZE;
returnOK;
}
intLoad_Sq（SqList&L）
{
inti;
for（i=0;iprintf（"%d",L.elem[i]）;
printf（"\n"）;
returnOK;
}
intListLength（SqListL）
{
returnL.length;
}
intGetElem（SqListL,inti,ElemType&e）
{
e=L.elem[i-1];
returnOK;
}
intListInsert_Sq（SqList&L,inti,inte）
{
if（i<1||i>L.length+1）returnERROR;
ElemType*newbase,*q,*p;
if（L.length>=L.listsize）
{
newbase=（ElemType*）realloc（L.elem,（L.listsize+LISTINCREMENT）*sizeof（ElemType））;
L.elem=newbase;
L.listsize+=LISTINCREMENT;
}
q=&（L.elem[i-1]）;
for（p=&（L.elem[L.length-1]）;p>=q;--p）
*（p+1）=*p;
*q=e;
++L.length;
returnOK;
}
voidMergeList（SqListLa,SqListLb,SqList&Lc）
{
inti,j,k,La_len,Lb_len;
intai,bj;
i=j=1;k=0;
InitList_Sq（Lc）;
La_len=ListLength（La）;
Lb_len=ListLength（Lb）;
while（（i<=La_len）&&（j<=Lb_len））
{
GetElem（La,i,ai）;
GetElem（Lb,j,bj）;
if（ai<=bj）
{
ListInsert_Sq（Lc,++k,ai）;
++i;
}
else
{
ListInsert_Sq（Lc,++k,bj）;
++j;
}
}
while（i<=La_len）
{
GetElem（La,i++,ai）;
ListInsert_Sq（Lc,++k,ai）;
}
while（j<=Lb_len）
{
GetElem（Lb,j++,bj）;
ListInsert_Sq（Lc,++k,bj）;
}
Load_Sq（Lc）;
}
intmain（）
{
intan,bn,i,e;
SqListLa,Lb,Lc;
InitList_Sq（La）;
scanf（"%d",&an）;
for（i=1;i<=an;i++）
{
scanf（"%d",&e）;
ListInsert_Sq（La,i,e）;
}
printf（"ListA:
"）;
Load_Sq（La）;
InitList_Sq（Lb）;
scanf（"%d",&bn）;
for（i=1;i<=bn;i++）
{
scanf（"%d",&e）;
ListInsert_Sq（Lb,i,e）;
}
printf（"ListB:
"）;
Load_Sq（Lb）;
printf（"ListC:
"）;
MergeList（La,Lb,Lc）;
}
03顺序表逆置
#include"stdio.h"
#include"malloc.h"
#defineOK1
#defineERROR0
#defineLIST_INIT_SIZE100
#defineLISTINCREMENT10
#defineElemTypeint
typedefstruct
{
ElemType*elem;
intlength;
intlistsize;
}SqList;
intInitList_Sq（SqList&L）
{
L.elem=（ElemType*）malloc（LIST_INIT_SIZE*sizeof（ElemType））;
L.length=0;
L.listsize=LIST_INIT_SIZE;
returnOK;
}
intListInsert_Sq（SqList&L,inti,inte）
{
if（i<1||i>L.length+1）returnERROR;
ElemType*newbase,*q,*p;
if（L.length>=L.listsize）
{
newbase=（ElemType*）realloc（L.elem,（L.listsize+LISTINCREMENT）*sizeof（ElemType））;
L.elem=newbase;
L.listsize+=LISTINCREMENT;
}
q=&（L.elem[i-1]）;
for（p=&（L.elem[L.length-1]）;p>=q;--p）
*（p+1）=*p;
*q=e;
++L.length;
returnOK;
}
intListDelete_Sq（SqList&L,inti,int&e）
{
ElemType*p,*q;
if（i<1||i>L.length）returnERROR;
p=&（L.elem[i-1]）;
e=*p;
q=L.elem+L.length-1;
for（++p;p<=q;++p）
*（p-1）=*p;
--L.length;
returnOK;
}
intLoad_Sq（SqList&L）
{
inti;
for（i=0;iprintf（"%d",L.elem[i]）;
printf（"\n"）;
returnOK;
}
intmain（）
{
SqListT;
intn,i,l;
ElemTypee,x;
InitList_Sq（T）;
scanf（"%d",&n）;
for（i=1;i<=n;i++）
{
scanf（"%d",&e）;
ListInsert_Sq（T,i,e）;
}
printf（"TheListis:
"）;
Load_Sq（T）;
l=n/2;
for（i=l;i>0;i--）
{
ListDelete_Sq（T,n+1-i,x）;
ListDelete_Sq（T,i,e）;
ListInsert_Sq（T,i,x）;
ListInsert_Sq（T,n+1-i,e）;
}
printf（"TheturnedListis:
"）;
Load_Sq（T）;
}
04链式线性表的基本操作
#include
#include
#defineERROR0
#defineOK1
#defineElemTypeint
typedefstructLNode
{
intdata;
structLNode*next;
}LNode,*LinkList;
intCreateLink_L（LinkList&L,intn）{
//创建含有n个元素的单链表
LinkListp,q;
inti;
ElemTypee;
L=（LinkList）malloc（sizeof（LNode））;
L->next=NULL;//先建立一个带头结点的单链表
q=（LinkList）malloc（sizeof（LNode））;
q=L;
for（i=0;iscanf（"%d",&e）;
p=（LinkList）malloc（sizeof（LNode））;//生成新结点
p->data=e;
p->next=q->next;
q->next=p;
q=q->next;
}
returnOK;
}
intLoadLink_L（LinkList&L）{
//单链表遍历
LinkListp=L->next;
if（p==NULL）printf（"TheListisempty!
"）;//请填空
else
{
printf（"TheLinkListis:
"）;
while（p!
=NULL）//请填空
{
printf（"%d",p->data）;
p=p->next;//请填空
}
}
printf（"\n"）;
returnOK;
}
intLinkInsert_L（LinkList&L,inti,ElemTypee）{
LNode*p=L,*s;
intj=0;
while（p&&j{
p=p->next;
++j;
}
if（!
p||j>i-1）returnERROR;
s=（LinkList）malloc（sizeof（LNode））;
s->data=e;s->next=p->next;
p->next=s;
returnOK;
}
intLinkDelete_L（LinkList&L,inti,ElemType&e）{
LNode*p=L,*q;
intj=0;
while（p->next&&j{
p=p->next;
++j;
}
if（!
（p->next）||jq=p->next;p->next=q->next;
e=q->data;
free（q）;
returnOK;
}
intmain（）
{
LinkListT;
inta,n,i;
ElemTypex,e;
printf（"Pleaseinputtheinitsizeofthelinklist:
\n"）;
scanf（"%d",&n）;
printf（"Pleaseinputthe%delementofthelinklist:
\n",n）;
if（CreateLink_L（T,n））//判断链表是否创建成功，请填空
{
printf（"ALinkListHasCreated.\n"）;
LoadLink_L（T）;
}
while
（1）
{
printf（"1:
Insertelement\n2:
Deleteelement\n3:
Loadallelements\n0:
Exit\nPleasechoose:
\n"）;
scanf（"%d",&a）;
switch（a）
{
case1:
scanf（"%d%d",&i,&x）;
if（!
LinkInsert_L（T,i,x））printf（"InsertError!
\n"）;//判断i值是否合法，请填空
elseprintf（"TheElement%disSuccessfullyInserted!
\n",x）;
break;
case2:
scanf（"%d",&i）;
if（!
LinkDelete_L（T,i,e））printf（"DeleteError!
\n"）;//判断i值是否合法，请填空
elseprintf（"TheElement%disSuccessfullyDeleted!
\n",e）;
break;
case3:
LoadLink_L（T）;
break;
case0:
return1;
}
}
}
05合并链表
#include
#include
#defineERROR0
#defineOK1
#defineElemTypeint
typedefstructLNode
{
intdata;
structLNode*next;
}LNode,*LinkList;
intCreateLink_L（LinkList&L,intn）{
//创建含有n个元素的单链表
LinkListp,q;
inti;
ElemTypee;
L=（LinkList）malloc（sizeof（LNode））;
L->next=NULL;//先建立一个带头结点的单链表
q=（LinkList）malloc（sizeof（LNode））;
q=L;
for（i=0;iscanf（"%d",&e）;
p=（LinkList）malloc（sizeof（LNode））;//生成新结点
p->data=e;
p->next=q->next;
q->next=p;
q=q->next;
}
returnOK;
}
intLoadLink_L（LinkList&L）{
//单链表遍历
LinkListp=L->next;
if（p==NULL）printf（"TheListisempty!
"）;//请填空
else
{
while（p!
=NULL）//请填空
{
printf（"%d",p->data）;
p=p->next;//请填空
}
}
printf（"\n"）;
returnOK;
}
intLinkInsert_L（LinkList&L,inti,ElemTypee）{
LNode*p=L,*s;
intj=0;
while（p&&j{
p=p->next;
++j;
}
if（!
p||j>i-1）returnERROR;
s=（LinkList）malloc（sizeof（LNode））;
s->data=e;s->next=p->next;
p->next=s;
returnOK;
}
intLinkDelete_L（LinkList&L,inti,ElemType&e）{
LNode*p=L,*q;
intj=0;
while（p->next&&j{
p=p->next;
++j;
}
if（!
（p->next）||jq=p->next;p->next=q->next;
e=q->data;
free（q）;
returnOK;
}
voidMergeList_L（LinkList&La,LinkList&Lb,LinkList&Lc）
{
LinkListpa,pb,pc;
pa=La->next;pb=Lb->next;
Lc=pc=La;
while（pa&&pb）
{
if（pa->data<=pb->data）
{
pc->next=pa;
pc=pa;
pa=pa->next;
}
else
{
pc->next=pb;
pc=pb;
pb=pb->next;
}
}
pc->next=pa?
pa:
pb;
free（Lb）;
}
intmain（）
{
LinkListLa,Lb,Lc;
intn;
scanf（"%d",&n）;
CreateLink_L（La,n）;
printf（"ListA:
"）;
LoadLink_L（La）;
scanf（"%d",&n）;
CreateLink_L（Lb,n）;
printf（"ListB:
"）;
LoadLink_L（Lb）;
MergeList_L（La,Lb,Lc）;
printf（"ListC:
"）;
LoadLink_L（Lc）;
}
06线性链表逆置
#include
#include
#defineERROR0
#defineOK1
#defineElemTypeint
typedefstructLNode
{
intdata;
structLNode*next;
}LNode,*LinkList;
intCreateLink_L（LinkList&L,intn）{
//创建含有n个元素的单链表
LinkListp,q;
inti
升级会员 