华南农业大学数据结构OJ题目不含答案.docx
《华南农业大学数据结构OJ题目不含答案.docx》由会员分享，可在线阅读，更多相关《华南农业大学数据结构OJ题目不含答案.docx（91页珍藏版）》请在冰点文库上搜索。
华南农业大学数据结构OJ题目不含答案
Description编写算法，创建初始化容量为LIST_INIT_SIZE的顺序表T，并实现插入、删除、遍历操作。
本题目给出部分代码，请补全内容。
#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
//请补全代码
}
intLoad_Sq（SqList&L）
{
//输出顺序表中的所有元素
inti;
if（_________________________）printf（"TheListisempty!
"）;//请填空
else
{
printf（"TheListis:
"）;
for（_________________________）printf（"%d",_________________________）;//请填空
}
printf（"\n"）;
returnOK;
}
intListInsert_Sq（SqList&L,inti,inte）
{
//算法2.4，在顺序线性表L中第i个位置之前插入新的元素e
//i的合法值为1≤i≤L.length+1
//请补全代码
}
intListDelete_Sq（SqList&L,inti,int&e）
{
//算法2.5,在顺序线性表L中删除第i个位置的元素，并用e返回其值
//i的合法值为1≤i≤L.length
//请补全代码
}
intmain（）
{
SqListT;
inta,i;
ElemTypee,x;
if（_________________________）//判断顺序表是否创建成功
{
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（_________________________）printf（"InsertError!
\n"）;//判断i值是否合法，请填空
elseprintf（"TheElement%disSuccessfullyInserted!
\n",x）;
break;
case2:
scanf（"%d",&i）;
if（_________________________）printf（"DeleteError!
\n"）;//判断i值是否合法，请填空
elseprintf（"TheElement%disSuccessfullyDeleted!
\n",e）;
break;
case3:
Load_Sq（T）;
break;
case0:
return1;
}
}
}
输入格式
测试样例格式说明：
根据菜单操作：
1、输入1，表示要实现插入操作，紧跟着要输入插入的位置和元素，用空格分开
2、输入2，表示要实现删除操作，紧跟着要输入删除的位置
3、输入3，表示要输出顺序表的所有元素
4、输入0，表示程序结束
输入样例
1
12
1
13
2
1
3
0
输出样例
ASequenceListHasCreated.
1:
Insertelement
2:
Deleteelement
3:
Loadallelements
0:
Exit
Pleasechoose:
TheElement2isSuccessfullyInserted!
1:
Insertelement
2:
Deleteelement
3:
Loadallelements
0:
Exit
Pleasechoose:
TheElement3isSuccessfullyInserted!
1:
Insertelement
2:
Deleteelement
3:
Loadallelements
0:
Exit
Pleasechoose:
TheElement3isSuccessfullyDeleted!
1:
Insertelement
2:
Deleteelement
3:
Loadallelements
0:
Exit
Pleasechoose:
TheListis:
2
1:
Insertelement
2:
Deleteelement
3:
Loadallelements
0:
Exit
Pleasechoose:
顺序表的基本操作代码如下：
#include
#include
#defineOK1
#defineERROR0
#defineLIST_INIT_SIZE100
#defineLISTINCREMENT10
#defineElemTypeint
typedefintStatus;
typedefstruct
{
int*elem;
intlength;
intlistsize;
}SqList;
StatusInitList_Sq（SqList&L）
{//算法2.3
//构造一个空的线性表L。
L.elem=（ElemType*）malloc（LIST_INIT_SIZE*sizeof（ElemType））;
if（!
L.elem）returnOK;//存储分配失败
L.length=0;//空表长度为0
L.listsize=LIST_INIT_SIZE;//初始存储容量
returnOK;
}//InitList_Sq
StatusListInsert_Sq（SqList&L,inti,ElemTypee）
{//算法2.4
//在顺序线性表L的第i个元素之前插入新的元素e，
//i的合法值为1≤i≤ListLength_Sq（L）+1
ElemType*p;
if（i<1||i>L.length+1）returnERROR;//i值不合法
if（L.length>=L.listsize）{//当前存储空间已满，增加容量
ElemType*newbase=（ElemType*）realloc（L.elem,
（L.listsize+LISTINCREMENT）*sizeof（ElemType））;
if（!
newbase）returnERROR;//存储分配失败
L.elem=newbase;//新基址
L.listsize+=LISTINCREMENT;//增加存储容量
}
ElemType*q=&（L.elem[i-1]）;//q为插入位置
for（p=&（L.elem[L.length-1]）;p>=q;--p）*（p+1）=*p;
//插入位置及之后的元素右移
*q=e;//插入e
++L.length;//表长增1
returnOK;
}//ListInsert_Sq
StatusListDelete_Sq（SqList&L,inti,ElemType&e）
{//算法2.5
//在顺序线性表L中删除第i个元素，并用e返回其值。
//i的合法值为1≤i≤ListLength_Sq（L）。
ElemType*p,*q;
if（i<1||i>L.length）returnERROR;//i值不合法
p=&（L.elem[i-1]）;//p为被删除元素的位置
e=*p;//被删除元素的值赋给e
q=L.elem+L.length-1;//表尾元素的位置
for（++p;p<=q;++p）*（p-1）=*p;//被删除元素之后的元素左移
--L.length;//表长减1
returnOK;
}//ListDelete_Sq
编写算法，将两个非递减有序顺序表A和B合并成一个新的非递减有序顺序表C。
输入格式
第一行：
顺序表A的元素个数
第二行：
顺序表A的各元素（非递减），用空格分开
第三行：
顺序表B的元素个数
第四行：
顺序表B的各元素（非递减），用空格分开
输出格式
第一行：
顺序表A的元素列表
第二行：
顺序表B的元素列表
第三行：
合并后顺序表C的元素列表
输入样例
5
13579
5
246810
输出样例
ListA:
13579
ListB:
246810
ListC:
12345678910
顺序表的基本操作代码如下：
#include
#include
#defineOK1
#defineERROR0
#defineLIST_INIT_SIZE100
#defineLISTINCREMENT10
#defineElemTypeint
typedefintStatus;
typedefstruct
{
int*elem;
intlength;
intlistsize;
}SqList;
StatusInitList_Sq（SqList&L）
{//算法2.3
//构造一个空的线性表L。
L.elem=（ElemType*）malloc（LIST_INIT_SIZE*sizeof（ElemType））;
if（!
L.elem）returnOK;//存储分配失败
L.length=0;//空表长度为0
L.listsize=LIST_INIT_SIZE;//初始存储容量
returnOK;
}//InitList_Sq
StatusListInsert_Sq（SqList&L,inti,ElemTypee）
{//算法2.4
//在顺序线性表L的第i个元素之前插入新的元素e，
//i的合法值为1≤i≤ListLength_Sq（L）+1
ElemType*p;
if（i<1||i>L.length+1）returnERROR;//i值不合法
if（L.length>=L.listsize）{//当前存储空间已满，增加容量
ElemType*newbase=（ElemType*）realloc（L.elem,
（L.listsize+LISTINCREMENT）*sizeof（ElemType））;
if（!
newbase）returnERROR;//存储分配失败
L.elem=newbase;//新基址
L.listsize+=LISTINCREMENT;//增加存储容量
}
ElemType*q=&（L.elem[i-1]）;//q为插入位置
for（p=&（L.elem[L.length-1]）;p>=q;--p）*（p+1）=*p;
//插入位置及之后的元素右移
*q=e;//插入e
++L.length;//表长增1
returnOK;
}//ListInsert_Sq
StatusListDelete_Sq（SqList&L,inti,ElemType&e）
{//算法2.5
//在顺序线性表L中删除第i个元素，并用e返回其值。
//i的合法值为1≤i≤ListLength_Sq（L）。
ElemType*p,*q;
if（i<1||i>L.length）returnERROR;//i值不合法
p=&（L.elem[i-1]）;//p为被删除元素的位置
e=*p;//被删除元素的值赋给e
q=L.elem+L.length-1;//表尾元素的位置
for（++p;p<=q;++p）*（p-1）=*p;//被删除元素之后的元素左移
--L.length;//表长减1
returnOK;
}//ListDelete_Sq
设有一顺序表A=（a0,a1,...,ai,...an-1），其逆顺序表定义为A'=（an-1,...,ai,...,a1,a0）。
设计一个算法，将顺序表逆置，要求顺序表仍占用原顺序表的空间。
输入格式
第一行：
输入顺序表的元素个数
第二行：
输入顺序表的各元素，用空格分开
输出格式
第一行：
逆置前的顺序表元素列表
第二行：
逆置后的顺序表元素列表
输入样例
10
12345678910
输出样例
TheListis:
12345678910
TheturnedListis:
10987654321
Description编写算法，创建一个含有n个元素的带头结点的单链表L并实现插入、删除、遍历操作。
本题目提供部分代码，请补全内容。
#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））;//生成新结点
//请补全代码
}
returnOK;
}
intLoadLink_L（LinkList&L）{
//单链表遍历
LinkListp=L->next;
if（___________________________）printf（"TheListisempty!
"）;//请填空
else
{
printf（"TheLinkListis:
"）;
while（___________________________）//请填空
{
printf（"%d",p->data）;
___________________________//请填空
}
}
printf（"\n"）;
returnOK;
}
intLinkInsert_L（LinkList&L,inti,ElemTypee）{
//算法2.9
//在带头结点的单链线性表L中第i个位置之前插入元素e
//请补全代码
}
intLinkDelete_L（LinkList&L,inti,ElemType&e）{
//算法2.10
//在带头结点的单链线性表L中，删除第i个元素，并用e返回其值
//请补全代码
}
intmain（）
{
LinkListT;
inta,n,i;
ElemTypex,e;
printf（"Pleaseinputtheinitsizeofthelinklist:
\n"）;
scanf（"%d",&n）;
printf（"Pleaseinputthe%delementofthelinklist:
\n",n）;
if（___________________________）//判断链表是否创建成功，请填空
{
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（___________________________）printf（"InsertError!
\n"）;//判断i值是否合法，请填空
elseprintf（"TheElement%disSuccessfullyInserted!
\n",x）;
break;
case2:
scanf（"%d",&i）;
if（___________________________）printf（"DeleteError!
\n"）;//判断i值是否合法，请填空
elseprintf（"TheElement%disSuccessfullyDeleted!
\n",e）;
break;
case3:
LoadLink_L（T）;
break;
case0:
return1;
}
}
}
输入格式
测试样例格式说明：
根据菜单操作：
1、输入1，表示要实现插入操作，紧跟着要输入插入的位置和元素，用空格分开
2、输入2，表示要实现删除操作，紧跟着要输入删除的位置
3、输入3，表示要输出顺序表的所有元素
4、输入0，表示程序结束
输入样例
3
369
3
1
412
2
1
3
0
输出样例
Pleaseinputtheinitsizeofthelinklist:
Pleaseinputthe3elementofthelinklist:
ALinkListHasCreated.
TheLinkListis:
369
1:
Insertelement
2:
Deleteelement
3:
Loadallelements
0:
Exit
Pleasechoose:
TheLinkListis:
369
1:
Insertelement
2:
Deleteelement
3:
Loadallelements
0:
Exit
Pleasechoose:
TheElement12isSuccessfullyInserted!
1:
Insertelement
2:
Deleteelement
3:
Loadallelements
0:
Exit
Pleasechoose:
TheElement3isSuccessfullyDeleted!
1:
Insertelement
2:
Deleteelement
3:
Loadallelements
0:
Exit
Pleasechoose:
TheLinkListis:
6912
1:
Insertelement
2:
Deleteelement
3:
Loadallelements
0:
Exit
Pleasechoose:
线性链表的基本操作如下：
#include
#include
#defineERROR0
#defineOK1
#defineElemTypeint
typedefintStatus;
typedefstructLNode
{
intdata;
structLNode*next;
}LNode,*LinkList;
StatusListInsert_L（LinkList&L,inti,ElemTypee）{//算法2.9
//在带头结点的单链线性表L的第i个元素之前插入元素e
LinkListp,s;
p=L;
intj=0;
while（p&&jp=p->next;
++j;
}
if（!
p||j>i-1）returnERROR;//i小于1或者大于表长
s=（LinkList）malloc（sizeof（LNode））;//生成新结点
s->data=e;s->next=p->next;//插入L中
p->next=s;
returnOK;
}//LinstInsert_L
StatusListDelete_L（LinkList&L,inti,ElemType&e）{//算法2.10
//在带头结点的单链线性表L中，删除第i个元素，并由e返回其值
LinkListp,q;
p=L;
intj=0;
while（p->next&&jp=p->next;
++j;
}
if（!
（p->next）||j>i-1）returnERROR;//删除位置不合理
q=p->next;
p->next=q->next;//删除并释放结点
e=q->data;
free（q）;
r
升级会员 