1-1 顺序表基本操作
本题要求实现顺序表的操作集。
函数接口定义：
Position Find( List L, ElementType X );
bool Insert( List L, ElementType X, Position P );
bool Delete( List L, Position P );
其中List结构定义如下：
typedef int Position;
typedef struct LNode *List;
struct LNode {
ElementType Data[MAXSIZE];
Position Last; /* 保存线性表中最后一个元素的位置 */
};
各个操作函数的定义为：
List MakeEmpty()：创建并返回一个空的线性表；
Position Find( List L, ElementType X )：返回线性表中X的位置。若找不到则返回ERROR；
bool Insert( List L, ElementType X, Position P )：将X插入在位置P并返回true。若空间已满，则打印“FULL”并返回false；如果参数P指向非法位置，则打印“ILLEGAL POSITION”并返回false；
bool Delete( List L, Position P )：将位置P的元素删除并返回true。若参数P指向非法位置，则打印“POSITION P EMPTY”（其中P是参数值）并返回false。
裁判测试程序样例：
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 5
#define ERROR -1
typedef enum {false, true} bool;
typedef int ElementType;
typedef int Position;
typedef struct LNode *List;
struct LNode {
ElementType Data[MAXSIZE];
Position Last; /* 保存线性表中最后一个元素的位置 */
};
List MakeEmpty();
Position Find( List L, ElementType X );
bool Insert( List L, ElementType X, Position P );
bool Delete( List L, Position P );
int main()
{
List L;
ElementType X;
Position P;
int N;
L = MakeEmpty();
scanf("%d", &N);
while ( N-- ) {
scanf("%d", &X);
if ( Insert(L, X, 0)==false )
printf(" Insertion Error: %d is not in.\n", X);
}
scanf("%d", &N);
while ( N-- ) {
scanf("%d", &X);
P = Find(L, X);
if ( P == ERROR )
printf("Finding Error: %d is not in.\n", X);
else
printf("%d is at position %d.\n", X, P);
}
scanf("%d", &N);
while ( N-- ) {
scanf("%d", &P);
if ( Delete(L, P)==false )
printf(" Deletion Error.\n");
if ( Insert(L, 0, P)==false )
printf(" Insertion Error: 0 is not in.\n");
}
return 0;
}
/* 你的代码将被嵌在这里 */
输入样例：
6
1 2 3 4 5 6
3
6 5 1
2
-1 6
输出样例：
FULL Insertion Error: 6 is not in.
Finding Error: 6 is not in.
5 is at position 0.
1 is at position 4.
POSITION -1 EMPTY Deletion Error.
FULL Insertion Error: 0 is not in.
POSITION 6 EMPTY Deletion Error.
FULL Insertion Error: 0 is not in.
我的代码
List MakeEmpty()
{
List L=(List)malloc(sizeof(struct LNode));
L->Last=-1;
return L;
}
Position Find( List L, ElementType X )
{
for(int i=0;i<MAXSIZE;i++){
if(L->Data[i]==X)
return i;
}
return ERROR;
}
bool Insert( List L, ElementType X, Position P )
{
if(L->Last+1==MAXSIZE)
{
printf("FULL");
return false;
}
if(P>L->Last+1||P<0)
{
printf("ILLEGAL POSITION");
return false;
}
for(int i=L->Last;i>=P;i--){
L->Data[i+1]=L->Data[i];
}
L->Data[P]=X;
L->Last++;
return true;
}
bool Delete( List L, Position P )
{
if(P>L->Last||P<0)
{
printf("POSITION %d EMPTY",P);
return false;
}
for(int i=P;i<L->Last;i++){
L->Data[i]=L->Data[i+1];
}
L->Last--;
return true;
}
1-3 递增的整数序列链表的插入
本题要求实现一个函数，在递增的整数序列链表（带头结点）中插入一个新整数，并保持该序列的有序性。
函数接口定义：
List Insert( List L, ElementType X );
其中List结构定义如下：
struct Node {
ElementType Data; /* 存储结点数据 */
PtrToNode Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */
L是给定的带头结点的单链表，其结点存储的数据是递增有序的；函数Insert要将X插入L，并保持该序列的有序性，返回插入后的链表头指针。
裁判测试程序样例：
#include <stdlib.h>
typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
ElementType Data;
PtrToNode Next;
};
typedef PtrToNode List;
List Read(); /* 细节在此不表 */
void Print( List L ); /* 细节在此不表 */
List Insert( List L, ElementType X );
int main()
{
List L;
ElementType X;
L = Read();
scanf("%d", &X);
L = Insert(L, X);
Print(L);
return 0;
}
/* 你的代码将被嵌在这里 */
输入样例：
1 2 4 5 6
3
输出样例：
1 2 3 4 5 6
我的代码
List Insert( List L, ElementType X )
{
List n=L,h;
List p=(List)malloc(sizeof(List));
p->Data=X;
p->Next=NULL;
h=L;
h=h->Next;
if(h==NULL){
L->Next=p;
return L;
}
while(h->Data<X){
n=h;
h=h->Next;
if(h==NULL)
break;
}
n->Next=p;
p->Next=h;
return L;
}
1-5 线性表元素的区间删除
给定一个顺序存储的线性表，请设计一个函数删除所有值大于min而且小于max的元素。删除后表中剩余元素保持顺序存储，并且相对位置不能改变。
函数接口定义：
List Delete( List L, ElementType minD, ElementType maxD );
其中List结构定义如下：
typedef int Position;
typedef struct LNode *List;
struct LNode {
ElementType Data[MAXSIZE];
Position Last; /* 保存线性表中最后一个元素在数组中的位置 */
};
L是用户传入的一个线性表，其中ElementType元素可以通过>、==、<进行比较；minD和maxD分别为待删除元素的值域的下、上界。函数Delete应将Data[]中所有值大于minD而且小于maxD的元素删除，同时保证表中剩余元素保持顺序存储，并且相对位置不变，最后返回删除后的表。
裁判测试程序样例：
#include <stdio.h>
#define MAXSIZE 20
typedef int ElementType;
typedef int Position;
typedef struct LNode *List;
struct LNode {
ElementType Data[MAXSIZE];
Position Last; /* 保存线性表中最后一个元素的位置 */
};
List ReadInput(); /* 裁判实现，细节不表。元素从下标0开始存储 */
void PrintList( List L ); /* 裁判实现，细节不表 */
List Delete( List L, ElementType minD, ElementType maxD );
int main()
{
List L;
ElementType minD, maxD;
int i;
L = ReadInput();
scanf("%d %d", &minD, &maxD);
L = Delete( L, minD, maxD );
PrintList( L );
return 0;
}
/* 你的代码将被嵌在这里 */
输入样例：
10
4 -8 2 12 1 5 9 3 3 10
0 4
输出样例：
4 -8 12 5 9 10
我的代码
List Delete( List L, ElementType minD, ElementType maxD )
{
int j=0;
for(int i=0;i<=L->Last;i++){
if(L->Data[i]<=minD||L->Data[i]>=maxD)
{
L->Data[j]=L->Data[i];
j++;
}
}
L->Last=j-1;
return L;
}
1-8 数组循环左移
本题要求实现一个对数组进行循环左移的简单函数：一个数组a中存有n（>0）个整数，在不允许使用另外数组的前提下，将每个整数循环向左移m（≥0）个位置，即将a中的数据由（a0a1⋯a**n−1）变换为（a**m⋯a**n−1a0a1⋯a**m−1）（最前面的m个数循环移至最后面的m个位置）。如果还需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？
输入格式:
输入第1行给出正整数n（≤100）和整数m（≥0）；第2行给出n个整数，其间以空格分隔。
输出格式:
在一行中输出循环左移m位以后的整数序列，之间用空格分隔，序列结尾不能有多余空格。
输入样例：
8 3
1 2 3 4 5 6 7 8
输出样例：
4 5 6 7 8 1 2 3
我的代码
#include <stdio.h>
#include <stdlib.h>
int main()
{
int n,m,j;
scanf("%d %d",&n,&m);
m=m%n;
int a[n+m];
for(int i=n-m;i<n;i++){
scanf("%d",&a[i]);
}
for(int i=0;i<n-m;i++){
scanf("%d",&a[i]);
}
for(j=0;j<n-1;j++){
printf("%d ",a[j]);
}
printf("%d",a[j]);
return 0;
}
1-9 最长连续递增子序列
给定一个顺序存储的线性表，请设计一个算法查找该线性表中最长的连续递增子序列。例如，(1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8)。
输入格式:
输入第1行给出正整数n（≤105）；第2行给出n个整数，其间以空格分隔。
输出格式:
在一行中输出第一次出现的最长连续递增子序列，数字之间用空格分隔，序列结尾不能有多余空格。
输入样例：
15
1 9 2 5 7 3 4 6 8 0 11 15 17 17 10
输出样例：
3 4 6 8
我的代码
#include <stdio.h>
#include <stdlib.h>
int main()
{
int n,m;
scanf("%d",&n);
if(n<1)
return 0;
else if(n==1)
{
scanf("%d",&m);
printf("%d",m);
return 0;
}
else{
int a[n],x,max=0,l=0,s;
for(int i=0;i<n;i++){
scanf("%d",&x);
a[i]=x;
}
for(int i=0;i<n;i++){
if(a[i]>=a[i+1]){
l++;
if(l>max)
{
max=l;
s=i;
}
l=0;
}
else
{
l++;
}
}
printf("%d",a[s-max+1]);
for(int i=s-max+2;i<=s;i++){
printf(" %d",a[i]);
}
}
return 0;
}
1-10 链表去重
给定一个带整数键值的链表 L，你需要把其中绝对值重复的键值结点删掉。即对每个键值 K，只有第一个绝对值等于 K 的结点被保留。同时，所有被删除的结点须被保存在另一个链表上。例如给定 L 为 21→-15→-15→-7→15，你需要输出去重后的链表 21→-15→-7，还有被删除的链表 -15→15。
输入格式：
输入在第一行给出 L 的第一个结点的地址和一个正整数 N（≤105，为结点总数）。一个结点的地址是非负的 5 位整数，空地址 NULL 用 -1 来表示。
随后 N 行，每行按以下格式描述一个结点：
地址 键值 下一个结点
其中地址是该结点的地址，键值是绝对值不超过104的整数，下一个结点是下个结点的地址。
输出格式：
首先输出去重后的链表，然后输出被删除的链表。每个结点占一行，按输入的格式输出。
输入样例：
00100 5
99999 -7 87654
23854 -15 00000
87654 15 -1
00000 -15 99999
00100 21 23854
输出样例：
00100 21 23854
23854 -15 99999
99999 -7 -1
00000 -15 87654
87654 15 -1
我的代码
#include <stdio.h>
struct Node{
int data;
int next;
} A[100000],B[100000];
int main()
{
int head,n;
scanf("%d %d",&head,&n);
int state[1000]={0};
for(int i=0;i<n;i++){
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
A[a].data=b;
A[a].next=c;
}
int j,p=head,last;
int lastb,headb,suma=0,sumb=0;
while(p!=-1){
j=A[p].data>=0?A[p].data:0-A[p].data;
if(state[j]==0)
{
suma++;
state[j]=1;
last=p;
}
else
{
B[p].data=A[p].data;
if(sumb!=0)
B[lastb].next=p;
else headb=p;
lastb=p;
A[last].next=A[p].next;
sumb++;
}
p=A[p].next;
}
p=head;
for(int i=0;i<suma; i++){
printf("%05d %d ",p,A[p].data);
if(i==suma-1)
printf("-1");
else printf("%05d",A[p].next);
p=A[p].next;
printf("\n");
}
p=headb;
for(int i=0;i<sumb; i++){
printf("%05d %d ",p,B[p].data);
if(i==sumb-1)
printf("-1");
else printf("%05d",B[p].next);
p=B[p].next;
printf("\n");
}
return 0;
}