6-1 链表逆置（20 分）
本题要求实现一个函数，将给定单向链表逆置，即表头置为表尾，表尾置为表头。链表结点定义如下：
struct ListNode {
int data;
struct ListNode *next;
};
函数接口定义：
struct ListNode *reverse( struct ListNode *head );
其中head是用户传入的链表的头指针；函数reverse将链表head逆置，并返回结果链表的头指针。
裁判测试程序样例：
#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int data;
struct ListNode *next;
};
struct ListNode *createlist(); /*裁判实现，细节不表*/
struct ListNode *reverse( struct ListNode *head );
void printlist( struct ListNode *head )
{
struct ListNode *p = head;
while (p) {
printf("%d ", p->data);
p = p->next;
}
printf(" ");
}
int main()
{
struct ListNode *head;
head = createlist();
head = reverse(head);
printlist(head);
return 0;
}
/* 你的代码将被嵌在这里 */
输入样例：
1 2 3 4 5 6 -1
输出样例：
6 5 4 3 2 1
struct ListNode *reverse( struct ListNode *head ) { struct ListNode *p,*q=NULL,*r=NULL; if(head==NULL) { return NULL; } if(head->next==NULL) { return head; } p=head; while(p!=NULL) { q=p->next; p->next=r; r=p; p=q; } return r; }
6-2 求链式表的表长（10 分）
本题要求实现一个函数，求链式表的表长。
函数接口定义：
int Length( List L );
其中List结构定义如下：
typedef struct LNode *PtrToLNode;
struct LNode {
ElementType Data;
PtrToLNode Next;
};
typedef PtrToLNode List;
L是给定单链表，函数Length要返回链式表的长度。
裁判测试程序样例：
#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct LNode *PtrToLNode;
struct LNode {
ElementType Data;
PtrToLNode Next;
};
typedef PtrToLNode List;
List Read(); /* 细节在此不表 */
int Length( List L );
int main()
{
List L = Read();
printf("%d ", Length(L));
return 0;
}
/* 你的代码将被嵌在这里 */
输入样例：
1 3 4 5 2 -1
输出样例：
5
int Length( List L ) { if(L==NULL) { return 0; } else { int len=1; while(L->Next!=NULL) { len++; L=L->Next; } return len; } }
6-3 链式表操作集（20 分）
本题要求实现链式表的操作集。
函数接口定义：
Position Find( List L, ElementType X );
List Insert( List L, ElementType X, Position P );
List Delete( List L, Position P );
其中List结构定义如下：
typedef struct LNode *PtrToLNode;
struct LNode {
ElementType Data;
PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;
各个操作函数的定义为：
Position Find( List L, ElementType X )：返回线性表中首次出现X的位置。若找不到则返回ERROR；
List Insert( List L, ElementType X, Position P )：将X插入在位置P指向的结点之前，返回链表的表头。如果参数P指向非法位置，则打印“Wrong Position for Insertion”，返回ERROR；
List Delete( List L, Position P )：将位置P的元素删除并返回链表的表头。若参数P指向非法位置，则打印“Wrong Position for Deletion”并返回ERROR。
裁判测试程序样例：
#include <stdio.h>
#include <stdlib.h>
#define ERROR NULL
typedef int ElementType;
typedef struct LNode *PtrToLNode;
struct LNode {
ElementType Data;
PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;
Position Find( List L, ElementType X );
List Insert( List L, ElementType X, Position P );
List Delete( List L, Position P );
int main()
{
List L;
ElementType X;
Position P, tmp;
int N;
L = NULL;
scanf("%d", &N);
while ( N-- ) {
scanf("%d", &X);
L = Insert(L, X, L);
if ( L==ERROR ) printf("Wrong Answer ");
}
scanf("%d", &N);
while ( N-- ) {
scanf("%d", &X);
P = Find(L, X);
if ( P == ERROR )
printf("Finding Error: %d is not in. ", X);
else {
L = Delete(L, P);
printf("%d is found and deleted. ", X);
if ( L==ERROR )
printf("Wrong Answer or Empty List. ");
}
}
L = Insert(L, X, NULL);
if ( L==ERROR ) printf("Wrong Answer ");
else
printf("%d is inserted as the last element. ", X);
P = (Position)malloc(sizeof(struct LNode));
tmp = Insert(L, X, P);
if ( tmp!=ERROR ) printf("Wrong Answer ");
tmp = Delete(L, P);
if ( tmp!=ERROR ) printf("Wrong Answer ");
for ( P=L; P; P = P->Next ) printf("%d ", P->Data);
return 0;
}
/* 你的代码将被嵌在这里 */
输入样例：
6
12 2 4 87 10 2
4
2 12 87 5
输出样例：
2 is found and deleted.
12 is found and deleted.
87 is found and deleted.
Finding Error: 5 is not in.
5 is inserted as the last element.
Wrong Position for Insertion
Wrong Position for Deletion
10 4 2 5
Position Find( List L, ElementType X ) { if(L==NULL) { return ERROR; } else { while(L!=NULL) { if(L->Data==X) { return L; } L=L->Next; } } return ERROR; } List Insert( List L, ElementType X, Position P ) { List a,q; a=L; q=NULL; if(P==L) { q=(Position)malloc(sizeof(struct LNode)); q->Data=X; q->Next=L; return q; } else { while(L->Next!=P&&L->Next!=NULL) { L=L->Next; } if(L->Next==NULL&&P!=NULL) { printf("Wrong Position for Insertion "); return ERROR; } else { q=(Position)malloc(sizeof(struct LNode)); q->Data=X; L->Next=q; q->Next=P; return a; } } } List Delete( List L, Position P ) { List a; a=L; if(L==NULL||P==NULL) { printf("Wrong Position for Deletion "); return ERROR; } else { if(P==L) { a=L->Next; return a; } else { while(L->Next!=P&&L->Next!=NULL) { L = L->Next; } if(L->Next==NULL) { printf("Wrong Position for Deletion "); return ERROR; } else { L->Next=L->Next->Next; return a; } } } }
7-1 两个有序链表序列的合并（20 分）
已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的并集新非降序链表S3。
输入格式:
输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。
输出格式:
在一行中输出合并后新的非降序链表，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。
输入样例:
1 3 5 -1
2 4 6 8 10 -1
输出样例:
1 2 3 4 5 6 8 10
#include<stdio.h> #include<stdlib.h> typedef struct Node* List; struct Node { int data; struct Node *Next; }; List InitList(); void print(List L); void read(List L); void combine(List S1,List S2,List S3); int main() { List S1,S2,S3; S1=InitList(); S2=InitList(); S3=InitList(); read(S1); read(S2); combine(S1,S2,S3); print(S3); return 0; } List InitList() { List L; L=(List)malloc(sizeof(struct Node)); if(!L) { return NULL; } L->Next=NULL; return L; } void print(List L) { L=L->Next; if(L==NULL) { printf("NULL"); return; } while(L) { if(L->Next==NULL) printf("%d",L->data); else printf("%d ",L->data); L=L->Next; } } void read(List L) { List p; int x; scanf("%d",&x); while(x!=-1) { p=(List)malloc(sizeof(struct Node)); if(!p) { return; } p->data=x; p->Next=NULL; L->Next=p; L=p; scanf("%d",&x); } } void combine(List S1,List S2,List S3) { S1=S1->Next; S2=S2->Next; while(S1!=NULL&&S2!=NULL) { if(S1->data>S2->data) { S3->Next=S2; S2=S2->Next; } else { S3->Next=S1; S1=S1->Next; } S3=S3->Next; } if(S1==NULL&&S2==NULL) { return; } if(S1!=NULL) { S3->Next=S1; } else { S3->Next=S2; } return; }
7-2 两个有序链表序列的交集（20 分）
已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的交集新链表S3。
输入格式:
输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。
输出格式:
在一行中输出两个输入序列的交集序列，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。
输入样例:
1 2 5 -1
2 4 5 8 10 -1
输出样例:
2 5
#include<stdio.h> #include<stdlib.h> typedef struct Node* List; struct Node { int data; struct Node *Next; }; List InitList(); void print(List L); void read(List L); void Insersection(List S1,List S2,List S3); int main() { List S1,S2,S3; S1=InitList(); S2=InitList(); S3=InitList(); read(S1); read(S2); Insersection(S1,S2,S3); print(S3); return 0; } List InitList() { List L; L=(List)malloc(sizeof(struct Node)); if(!L) { return NULL; } L->Next=NULL; return L; } void print(List L) { L=L->Next; if(L==NULL) { printf("NULL"); return; } while(L) { if(L->Next==NULL) printf("%d",L->data); else printf("%d ",L->data); L=L->Next; } } void read(List L) { List p; int x; scanf("%d",&x); while(x!=-1) { p=(List)malloc(sizeof(struct Node)); if(!p) { return; } p->data=x; p->Next=NULL; L->Next=p; L=p; scanf("%d",&x); } } void Insersection(List S1,List S2,List S3) { List pa,pb,pc,q; pc=S3; pa=S1->Next; pb=S2->Next; while(pa!=NULL&&pb!=NULL) { if(pa->data<pb->data) { pa=pa->Next; } else if(pa->data>pb->data) { pb=pb->Next; } else { q=(List)malloc(sizeof(struct Node)); q->data=pa->data; pc->Next=q; pc=q; pa=pa->Next; pb=pb->Next; } } pc->Next=NULL; }