单选题
函数题
6-1 链式表操作集 (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。
输入样例：
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
代码
#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\n"); } 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 { L = Delete(L, P); printf("%d is found and deleted.\n", X); if ( L==ERROR ) printf("Wrong Answer or Empty List.\n"); } } L = Insert(L, X, NULL); if ( L==ERROR ) printf("Wrong Answer\n"); else printf("%d is inserted as the last element.\n", X); P = (Position)malloc(sizeof(struct LNode)); tmp = Insert(L, X, P); if ( tmp!=ERROR ) printf("Wrong Answer\n"); tmp = Delete(L, P); if ( tmp!=ERROR ) printf("Wrong Answer\n"); for ( P=L; P; P = P->Next ) printf("%d ", P->Data); return 0; } /* 你的代码将被嵌在这里 */ List Insert(List L, ElementType X, Position P) { List head = L; List p = (List)malloc(sizeof(List) ); p->Next = NULL; p->Data = X; // 判断插入的是不是空链表 if (P==L) { p->Next = L; return p; } // 循环遍历链表 while (L) { // 插入条件的筛选 if (P==L->Next) { p->Next = L->Next; L->Next = p; return head; } L = L->Next; } printf("Wrong Position for Insertion\n"); return ERROR; } Position Find(List L, ElementType X) { while (L) { if (L->Data == X) { return L; } L = L->Next; } return ERROR; } List Delete(List L, Position P) { //如果是头结点 if (L == P) { L =L->Next; return L; } List head = L; // 循环遍历链表 while (L) { if (L->Next == P) { L->Next = P->Next; return head; } L = L->Next; } printf("Wrong Position for Deletion\n"); return ERROR; }
6-2 带头结点的链式表操作集 (20分)
本题要求实现带头结点的链式表操作集。
函数接口定义：
List MakeEmpty(); Position Find( List L, ElementType X ); bool Insert( List L, ElementType X, Position P ); bool Delete( List L, Position P );
其中List结构定义如下：
typedef struct LNode *PtrToLNode; struct LNode { ElementType Data; PtrToLNode Next; }; typedef PtrToLNode Position; typedef PtrToLNode List;
各个操作函数的定义为：
List MakeEmpty()：创建并返回一个空的线性表；
Position Find( List L, ElementType X )：返回线性表中X的位置。若找不到则返回ERROR；
bool Insert( List L, ElementType X, Position P )：将X插入在位置P指向的结点之前，返回true。如果参数P指向非法位置，则打印“Wrong Position for Insertion”，返回false；
bool Delete( List L, Position P )：将位置P的元素删除并返回true。若参数P指向非法位置，则打印“Wrong Position for Deletion”并返回false。
输入样例：
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
代码
#include <stdio.h> #include <stdlib.h> #define ERROR NULL typedef enum {false, true} bool; typedef int ElementType; typedef struct LNode *PtrToLNode; struct LNode { ElementType Data; PtrToLNode Next; }; typedef PtrToLNode Position; typedef PtrToLNode List; 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; bool flag; L = MakeEmpty(); scanf("%d", &N); while ( N-- ) { scanf("%d", &X); flag = Insert(L, X, L->Next); if ( flag==false ) printf("Wrong Answer\n"); } 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 { flag = Delete(L, P); printf("%d is found and deleted.\n", X); if ( flag==false ) printf("Wrong Answer.\n"); } } flag = Insert(L, X, NULL); if ( flag==false ) printf("Wrong Answer\n"); else printf("%d is inserted as the last element.\n", X); P = (Position)malloc(sizeof(struct LNode)); flag = Insert(L, X, P); if ( flag==true ) printf("Wrong Answer\n"); flag = Delete(L, P); if ( flag==true ) printf("Wrong Answer\n"); for ( P=L->Next; P; P = P->Next ) printf("%d ", P->Data); return 0; } /* 你的代码将被嵌在这里 */ /* 你的代码将被嵌在这里 */ List MakeEmpty() { List L = (List)malloc(sizeof(List)); L->Next = NULL; return L; } Position Find(List L, ElementType X) { L = L->Next; while (L != NULL) { if (L->Data == X) { return L; } L = L->Next; } return ERROR; } bool Insert(List L, ElementType X, Position P) { // 这个传入的是头结点的下一个，所以不用检验是否为头结点 List q = (List)malloc(sizeof(struct LNode)); q->Data = X; q->Next = P; while (L != NULL) { if (L->Next == P) { L->Next = q; return true; } L = L->Next; } printf("Wrong Position for Insertion\n"); return false; } bool Delete(List L, Position P) { while (L != NULL) { if (L->Next == P) { L->Next = P->Next; return true; } L = L->Next; } printf("Wrong Position for Deletion\n"); return false; }
6-4 共享后缀的链表(25分)
有一种存储英文单词的方法，是把单词的所有字母串在一个单链表上。为了节省一点空间，如果有两个单词有同样的后缀，就让它们共享这个后缀。下图给出了单词“loading”和“being”的存储形式。本题要求你找出两个链表的公共后缀。
函数接口定义：
PtrToNode Suffix( List L1, List L2 );
其中List结构定义如下：
typedef struct Node *PtrToNode; struct Node { ElementType Data; /* 存储结点数据 */ PtrToNode Next; /* 指向下一个结点的指针 */ }; typedef PtrToNode List; /* 定义单链表类型 */
L1和L2都是给定的带头结点的单链表。函数Suffix应返回L1和L2的公共后缀的起点位置。
输入样例：
如图存储的链表
输出样例：
ing
代码
#include <stdio.h> #include <stdlib.h> typedef char ElementType; typedef struct Node *PtrToNode; struct Node { ElementType Data; /* 存储结点数据 */ PtrToNode Next; /* 指向下一个结点的指针 */ }; typedef PtrToNode List; /* 定义单链表类型 */ void ReadInput( List L1, List L2 ); /* 裁判实现，细节不表 */ void PrintSublist( PtrToNode StartP ); /* 裁判实现，细节不表 */ PtrToNode Suffix( List L1, List L2 ); int main() { List L1, L2; PtrToNode P; L1 = (List)malloc(sizeof(struct Node)); L2 = (List)malloc(sizeof(struct Node)); L1->Next = L2->Next = NULL; ReadInput( L1, L2 ); P = Suffix( L1, L2 ); PrintSublist( P ); return 0; } /* 你的代码将被嵌在这里 */ PtrToNode Suffix(List L1, List L2) { int num1 = 0, num2 = 0; List t = L1->Next, a = L1->Next, b = L2->Next; // 先算出两条链表的长度 while (t) { num1++; t = t->Next; } t = L2->Next; while (t) { num2++; t = t->Next; } while (num1 > num2) { num1--; a = a->Next; } while (num2 > num1) { num2--; b = b->Next; } while (a) { // 如果一样a后面的都是 返回a就行 if (a == b) return a; a = a->Next; b = b->Next; } return NULL; }
