数据结构题库

4-1 单链表逆转 (20分)

本题要求实现一个函数，将给定的单链表逆转。 函数接口定义：

List Reverse( List L ); 其中List结构定义如下： typedef struct Node *PtrToNode; struct Node { ElementType Data; /* 存储结点数据 */ PtrToNode Next; /* 指向下一个结点的指针 */ }; typedef PtrToNode List; /* 定义单链表类型 */ L是给定单链表，函数Reverse要返回被逆转后的链表。 裁判测试程序样例： #include #include typedef int ElementType; typedef struct Node *PtrToNode; struct Node { ElementType Data; PtrToNode Next; }; typedef PtrToNode List; List Read(); /* 细节在此不表 */ void Print( List L ); /* 细节在此不表 */ List Reverse( List L ); int main() { List L1, L2; L1 = Read(); L2 = Reverse(L1); Print(L1); Print(L2); return 0; } /* 你的代码将被嵌在这里 */ 输入样例：

5 1 3 4 5 2 输出样例：

1 2 5 4 3 1

4-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 int Position; typedef struct LNode *List; struct LNode { ElementType Data[MAXSIZE]; Position Last; /* 保存线性表中最后一个元素的位置 */ }; 各个操作函数的定义为： List MakeEmpty()：创建并返回一个空的线性表； Position Find( List L, ElementType X )：返回线性表中X的位置。若找不到则返回ERROR； X插入在位置P并返回true。若空间已满，则打印“FULL”并返回false；如果参数P指向非法位置，则打印“ILLEGAL POSITION”并返回false； bool Insert( List L, ElementType X, Position P )：将P的元素删除并返回true。若参数P指向非法位置，则打印“POSITION P EMPTY”（其中P是参数值）并返回false。 裁判测试程序样例： #include #include #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(\ while ( N-- ) { scanf(\ if ( Insert(L, X, 0)==false ) printf(\ } scanf(\ while ( N-- ) { scanf(\ P = Find(L, X); if ( P == ERROR ) printf(\ else bool Delete( List L, Position P )：将位置 printf(\ } scanf(\ while ( N-- ) { scanf(\ if ( Delete(L, P)==false ) printf(\ if ( Insert(L, 0, P)==false ) printf(\ } 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.

4-7 在一个数组中实现两个堆栈 (20分) 本题要求在一个数组中实现两个堆栈。 函数接口定义：

Stack CreateStack( int MaxSize ); bool Push( Stack S, ElementType X, int Tag ); ElementType Pop( Stack S, int Tag ); 其中Tag是堆栈编号，取1或2；MaxSize堆栈数组的规模；Stack结构定义如下： typedef int Position; struct SNode { ElementType *Data; Position Top1, Top2; int MaxSize; }; typedef struct SNode *Stack; 注意：如果堆栈已满，Push函数必须输出“Stack Full”并且返回false；如果某堆栈是空的，则Pop函数必须输出“Stack Tag Empty”（其中Tag是该堆栈的编号），并且返回ERROR。 裁判测试程序样例： #include #include #define ERROR 1e8 typedef int ElementType; typedef enum { push, pop, end } Operation; typedef enum { false, true } bool; typedef int Position; struct SNode { ElementType *Data; Position Top1, Top2; int MaxSize; }; typedef struct SNode *Stack; Stack CreateStack( int MaxSize ); bool Push( Stack S, ElementType X, int Tag ); ElementType Pop( Stack S, int Tag ); Operation GetOp(); /* details omitted */ void PrintStack( Stack S, int Tag ); /* details omitted */ int main() { int N, Tag, X; Stack S; int done = 0; scanf(\ S = CreateStack(N);