数据结构第一章.docx

8576 顺序线性表的基本操作
时间限制:1000MS  内存限制:1000K
提交次数:1714 通过次数:300
题型: 编程题   语言: 无限制
Description
编写算法，创建初始化容量为LIST_INIT_SIZE的顺序表T，并实现插入、删除、遍历操作。本题目给出部分代码，请补全内容。
#include<stdio.h>
#include<malloc.h>
#define OK 1
#define ERROR 0
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define ElemType int

typedef struct
{
int *elem;
int length;
int listsize;
}SqList;

int InitList_Sq(SqList &L)
{
// 算法2.3，构造一个空的线性表L，该线性表预定义大小为LIST_INIT_SIZE
// 请补全代码

}

int Load_Sq(SqList &L)
{
// 输出顺序表中的所有元素
int i;
if(_________________________) printf("The List is empty!"); // 请填空
else
{
printf("The List is: ");
for(_________________________) printf("%d ",_________________________); // 请填空
}
printf("\n");
return OK;
}

int ListInsert_Sq(SqList &L,int i,int e)
{
// 算法2.4，在顺序线性表L中第i个位置之前插入新的元素e
// i的合法值为1≤i≤L.length +1
// 请补全代码

}

int ListDelete_Sq(SqList &L,int i, int &e)
{
// 算法2.5,在顺序线性表L中删除第i个位置的元素，并用e返回其值
// i的合法值为1≤i≤L.length
// 请补全代码

}

int main()
{
SqList T;
int a, i;
ElemType e, x;
if(_________________________) // 判断顺序表是否创建成功
{
printf("A Sequence List Has Created.\n");
}
while(1)
{
printf("1:Insert element\n2:Delete element\n3:Load all elements\n0:Exit\nPlease choose:\n");
scanf("%d",&a);
switch(a)
{
case 1: scanf("%d%d",&i,&x);
if(_________________________) printf("Insert Error!\n"); // 判断i值是否合法，请填空
else printf("The Element %d is Successfully Inserted!\n", x);
break;
case 2: scanf("%d",&i);
if(_________________________) printf("Delete Error!\n"); // 判断i值是否合法，请填空
else printf("The Element %d is Successfully Deleted!\n", e);
break;
case 3: Load_Sq(T);
break;
case 0: return 1;
}
}
}

Input
测试样例格式说明：
根据菜单操作：
1、输入1，表示要实现插入操作，紧跟着要输入插入的位置和元素，用空格分开
2、输入2，表示要实现删除操作，紧跟着要输入删除的位置
3、输入3，表示要输出顺序表的所有元素
4、输入0，表示程序结束
Sample Input
1
1 2
1
1 3
2
1
3
0
Sample Output
A Sequence List Has Created.
1:Insert element
2:Delete element
3:Load all elements
0:Exit
Please choose:
The Element 2 is Successfully Inserted!
1:Insert element
2:Delete element
3:Load all elements
0:Exit
Please choose:
The Element 3 is Successfully Inserted!
1:Insert element
2:Delete element
3:Load all elements
0:Exit
Please choose:
The Element 3 is Successfully Deleted!
1:Insert element
2:Delete element
3:Load all elements
0:Exit
Please choose:
The List is: 2
1:Insert element
2:Delete element
3:Load all elements
0:Exit

8577 合并顺序表
时间限制:1000MS  内存限制:1000K
提交次数:1007 通过次数:288
题型: 编程题   语言: 无限制
Description
编写算法，将两个非递减有序顺序表A和B合并成一个新的非递减有序顺序表C。本题不提供代码，请同学们独立完成，所需子函数参考前面完成的内容。 
Input
第一行：顺序表A的元素个数
第二行：顺序表A的各元素（非递减），用空格分开
第三行：顺序表B的元素个数
第四行：顺序表B的各元素（非递减），用空格分开
Output
第一行：顺序表A的元素列表
第二行：顺序表B的元素列表
第三行：合并后顺序表C的元素列表
Sample Input
5
1 3 5 7 9
5
2 4 6 8 10
Sample Output
List A:1 3 5 7 9
List B:2 4 6 8 10
List C:1 2 3 4 5 6 7 8 9 10

8578 顺序表逆置
时间限制:1000MS  内存限制:1000K
提交次数:655 通过次数:285
题型: 编程题   语言: 无限制
Description
设有一顺序表A=（a0,a1,..., ai,...an-1)，其逆顺序表定义为A'=( an-1,..., ai,...,a1, a0)。设计一个算法，将顺序表逆置，要求顺序表仍占用原顺序表的空间。本题不提供代码，请同学们独立完成，所需子函数参考前面完成的内容。 
Input
第一行：输入顺序表的元素个数
第二行：输入顺序表的各元素，用空格分开
Output
第一行：逆置前的顺序表元素列表
第二行：逆置后的顺序表元素列表
Sample Input
10
1 2 3 4 5 6 7 8 9 10
Sample Output
The List is:1 2 3 4 5 6 7 8 9 10
The turned List is:10 9 8 7 6 5 4 3 2 1

8579 链式线性表的基本操作
时间限制:1000MS  内存限制:1000K
提交次数:762 通过次数:243
题型: 编程题   语言: 无限制
Description
编写算法，创建一个含有n个元素的带头结点的单链表L并实现插入、删除、遍历操作。本题目提供部分代码，请补全内容。
#include<stdio.h>
#include<malloc.h>
#define ERROR 0
#define OK 1
#define ElemType int

typedef struct LNode
{
int data;
struct LNode *next;
}LNode,*LinkList;

int CreateLink_L(LinkList &L,int n){
// 创建含有n个元素的单链表
LinkList p,q;
int i;
ElemType e;
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL; // 先建立一个带头结点的单链表
q = (LinkList)malloc(sizeof(LNode));
q = L;
for (i=0; i<n; i++) {
scanf("%d", &e);
p = (LinkList)malloc(sizeof(LNode)); // 生成新结点
// 请补全代码

}
return OK;
}

int LoadLink_L(LinkList &L){
// 单链表遍历
LinkList p = L->next;
if(___________________________)printf("The List is empty!"); // 请填空
else
{
printf("The LinkList is:");
while(___________________________) // 请填空
{
printf("%d ",p->data);
___________________________ // 请填空
}
}
printf("\n");
return OK;
}

int LinkInsert_L(LinkList &L,int i,ElemType e){
// 算法2.9
// 在带头结点的单链线性表L中第i个位置之前插入元素e
// 请补全代码

}

int LinkDelete_L(LinkList &L,int i, ElemType &e){
// 算法2.10
// 在带头结点的单链线性表L中，删除第i个元素，并用e返回其值
// 请补全代码

}

int main()
{
LinkList T;
int a,n,i;
ElemType x, e;
printf("Please input the init size of the linklist:\n");
scanf("%d",&n);
printf("Please input the %d element of the linklist:\n", n);
if(___________________________) // 判断链表是否创建成功，请填空
{
printf("A Link List Has Created.\n");
LoadLink_L(T);
}
while(1)
{
printf("1:Insert element\n2:Delete element\n3:Load all elements\n0:Exit\nPlease choose:\n");
scanf("%d",&a);
switch(a)
{
case 1: scanf("%d%d",&i,&x);
if(___________________________) printf("Insert Error!\n"); // 判断i值是否合法，请填空
else printf("The Element %d is Successfully Inserted!\n", x);
break;
case 2: scanf("%d",&i);
if(___________________________) printf("Delete Error!\n"); // 判断i值是否合法，请填空
else printf("The Element %d is Successfully Deleted!\n", e);
break;
case 3: LoadLink_L(T);
break;
case 0: return 1;
}
}
}

Input
测试样例格式说明：
根据菜单操作：
1、输入1，表示要实现插入操作，紧跟着要输入插入的位置和元素，用空格分开
2、输入2，表示要实现删除操作，紧跟着要输入删除的位置
3、输入3，表示要输出顺序表的所有元素
4、输入0，表示程序结束
Sample Input
3
3 6 9
3
1
4 12
2
1
3
0
Sample Output
Please input the init size of the linklist:
Please input the 3 element of the linklist:
A Link List Has Created.
The LinkList is:3 6 9
1:Insert element
2:Delete element
3:Load all elements
0:Exit
Please choose:
The LinkList is:3 6 9
1:Insert element
2:Delete element
3:Load all elements
0:Exit
Please choose:
The Element 12 is Successfully Inserted!
1:Insert element
2:Delete element
3:Load all elements
0:Exit
Please choose:
The Element 3 is Successfully Deleted!
1:Insert element
2:Delete element
3:Load all elements
0:Exit
Please choose:
The LinkList is:6 9 12
1:Insert element
2:Delete element
3:Load all elements
0:Exit
Please choose:

8580 合并链表
时间限制:1000MS  内存限制:1000K
提交次数:471 通过次数:257
题型: 编程题   语言: 无限制
Description
设计一个算法将两个非递减有序链表A和B合并成一个新的非递减有序链表C。本题不提供代码，请同学们独立完成，所需子函数参考之前完成的内容。 
Input
第一行：单链表A的元素个数
第二行：单链表A的各元素（非递减），用空格分开
第三行：单链表B的元素个数
第四行：单链表B的各元素（非递减），用空格分开
Output
第一行：单链表A的元素列表
第二行：单链表B的元素列表
第三行：合并后单链表C的元素列表
Sample Input
6
12 24 45 62 84 96
4
15 31 75 86
Sample Output
List A:12 24 45 62 84 96
List B:15 31 75 86
List C:12 15 24 31 45 62 75 84 86 96

8581 线性链表逆置
时间限制:1000MS  内存限制:1000K
提交次数:423 通过次数:254
题型: 编程题   语言: 无限制
Description
设有一线性表A=（a0,a1,..., ai,...an-1)，其逆线性表定义为A'=( an-1,..., ai,...,a1, a0)，设计一个算法，将线性表逆置，要求线性表仍占用原线性表的空间。本题不提供代码，请同学们独立完成，所需子函数参考之前完成的内容。 
Input
第一行：输入n，表示单链表的元素个数
第二行：输入单链表的各元素，用空格分开
Output
第一行：输出单链表逆置前的元素列表
第二行：输出单链表逆置后的元素列表
Sample Input
8
32 97 54 65 35 84 61 75
Sample Output
The List is:32 97 54 65 35 84 61 75
The turned List is:75 61 84 35 65 54 97 32