文章目录

6-1 单链表逆转
6-2 逆序数据建立链表
6-3 删除单链表偶数节点
6-4 两个有序链表序列的合并
6-5 带头结点的单链表就地逆置
6-6 单链表插入排序
6-7 双端队列
6-8 有序数组的插入
6-9 线性表元素的区间删除
6-10 在一个数组中实现两个堆栈
6-11 使用函数实现字符串部分复制
6-12 判断回文字符串
6-13 计算最长的字符串长度
6-14 求二叉树高度
6-15 二叉树的遍历
6-16 先序输出叶结点
6-17 二叉树的非递归遍历
6-18 邻接矩阵存储图的深度优先遍历
6-19 邻接表存储图的广度优先遍历
6-20 二分查找

6-1 单链表逆转

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

函数接口定义：

List Reverse( List L );

其中List结构定义如下：

typedef struct Node *PtrToNode;
struct Node {ElementType Data; /* 存储结点数据 */PtrToNode   Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */

L是给定单链表，函数Reverse要返回被逆转后的链表。

裁判测试程序样例：

#include <stdio.h>
#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 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

一种方法是通过三个指针：

List Reverse( List L )
{List tmp, cur = L, pre = NULL;while (cur){tmp = cur->Next;cur->Next = pre;pre = cur;cur = tmp;}return pre;
}

这道题在LeetCode上有类似的：206. 反转链表 - 力扣（LeetCode）

除此以外，还可以借助额外数组：

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* h = head;vector<int> v;while (head != nullptr) {v.push_back(head->val);head = head->next;}head = h;for (int i = v.size() - 1; i >= 0; i--) {h->val = v[i];h = h->next;}return head;}
};

递归：

class Solution {
public:ListNode* reverseList(ListNode* head) {if (head == nullptr || head->next == nullptr) {return head;}ListNode* last = reverseList(head->next);head->next->next = head;head->next = nullptr;return last;}
};

6-2 逆序数据建立链表

本题要求实现一个函数，按输入数据的逆序建立一个链表。

函数接口定义：
struct ListNode *createlist();
函数createlist利用scanf从输入中获取一系列正整数，当读到−1时表示输入结束。按输入数据的逆序建立一个链表，并返回链表头指针。链表节点结构定义如下：
struct ListNode {int data;struct ListNode *next;
};
裁判测试程序样例：
#include <stdio.h>
#include <stdlib.h>struct ListNode {int data;struct ListNode *next;
};struct ListNode *createlist();int main()
{struct ListNode *p, *head = NULL;head = createlist();for ( p = head; p != NULL; p = p->next )printf("%d ", p->data);printf("\n");return 0;
}/* 你的代码将被嵌在这里 */
输入样例：
1 2 3 4 5 6 7 -1
输出样例：
7 6 5 4 3 2 1 

头插法：

struct ListNode *createlist()
{struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));head->next = NULL;int a;scanf("%d", &a);if (a == -1) return NULL;else head->data = a;while (1){scanf("%d", &a);if (a == -1) return head;struct ListNode* tmp = (struct ListNode*)malloc(sizeof(struct ListNode));tmp->data = a;tmp->next = head;head = tmp;}return NULL;
}

6-3 删除单链表偶数节点

本题要求实现两个函数，分别将读入的数据存储为单链表、将链表中偶数值的结点删除。链表结点定义如下：
struct ListNode {int data;struct ListNode *next;
};
函数接口定义：
struct ListNode *createlist();
struct ListNode *deleteeven( struct ListNode *head );
函数createlist从标准输入读入一系列正整数，按照读入顺序建立单链表。当读到−1时表示输入结束，函数应返回指向单链表头结点的指针。

函数deleteeven将单链表head中偶数值的结点删除，返回结果链表的头指针。

裁判测试程序样例：
#include <stdio.h>
#include <stdlib.h>struct ListNode {int data;struct ListNode *next;
};struct ListNode *createlist();
struct ListNode *deleteeven( struct ListNode *head );
void printlist( struct ListNode *head )
{struct ListNode *p = head;while (p) {printf("%d ", p->data);p = p->next;}printf("\n");
}int main()
{struct ListNode *head;head = createlist();head = deleteeven(head);printlist(head);return 0;
}/* 你的代码将被嵌在这里 */
输入样例：
1 2 2 3 4 5 6 7 -1
输出样例：
1 3 5 7 

考察单链表的尾插和删除：

struct ListNode *createlist()
{struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));head->next = NULL;struct ListNode* cur = head;while (1){int a;scanf("%d", &a);if (a == -1) return head;struct ListNode* tmp = (struct ListNode*)malloc(sizeof(struct ListNode));tmp->data = a;tmp->next = NULL;cur->next = tmp;cur = tmp;}return NULL;
}struct ListNode *deleteeven( struct ListNode *head )
{struct ListNode* pre = head, *cur = head->next;while (cur){if (cur->data % 2 == 0){struct ListNode* tmp = cur->next;free(cur);pre->next = tmp;cur = tmp;}else{pre = cur;cur = cur->next;}}return head->next;
}

6-4 两个有序链表序列的合并

本题要求实现一个函数，将两个链表表示的递增整数序列合并为一个非递减的整数序列。

函数接口定义：
List Merge( List L1, List L2 );
其中List结构定义如下：
typedef struct Node *PtrToNode;
struct Node {ElementType Data; /* 存储结点数据 */PtrToNode   Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */
L1和L2是给定的带头结点的单链表，其结点存储的数据是递增有序的；函数Merge要将L1和L2合并为一个非递减的整数序列。应直接使用原序列中的结点，返回归并后的带头结点的链表头指针。

裁判测试程序样例：
#include <stdio.h>
#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 ); /* 细节在此不表；空链表将输出NULL */List Merge( List L1, List L2 );int main()
{List L1, L2, L;L1 = Read();L2 = Read();L = Merge(L1, L2);Print(L);Print(L1);Print(L2);return 0;
}/* 你的代码将被嵌在这里 */
输入样例：
3
1 3 5
5
2 4 6 8 10
输出样例：
1 2 3 4 5 6 8 10 
NULL
NULL

归并的思想，可以顺带复习下归并排序：八大排序 —— 详细图文讲解_世真的博客-CSDN博客_排序算法

List Merge( List L1, List L2 )
{List res = (List)malloc(sizeof(struct Node));List cur = res;res->Next = NULL;while (L1->Next != NULL && L2->Next != NULL){if (L1->Next->Data < L2->Next->Data){cur->Next = L1->Next;L1->Next = L1->Next->Next;}else{cur->Next = L2->Next;L2->Next = L2->Next->Next;}cur = cur->Next;}while (L1->Next != NULL){cur->Next = L1->Next;L1->Next = L1->Next->Next;cur = cur->Next;}while (L2->Next != NULL){cur->Next = L2->Next;L2->Next = L2->Next->Next;cur = cur->Next;}return res;
}

6-5 带头结点的单链表就地逆置

本题要求编写函数实现带头结点的单链线性表的就地逆置操作函数。L是一个带头结点的单链表，函数ListReverse_L(LinkList &L)要求在不新开辟节点的前提下将单链表中的元素进行逆置，如原单链表元素依次为1,2,3,4，则逆置后为4,3,2,1。

函数接口定义：
void ListReverse_L(LinkList &L);
其中 L 是一个带头结点的单链表。

裁判测试程序样例：
//库函数头文件包含
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>//函数状态码定义
#define TRUE        1
#define FALSE       0
#define OK          1
#define ERROR       0
#define INFEASIBLE -1
#define OVERFLOW   -2typedef int  Status;
typedef int  ElemType; //假设线性表中的元素均为整型typedef struct LNode
{ElemType data;struct LNode *next;
}LNode,*LinkList;Status ListCreate_L(LinkList &L,int n)
{LNode *rearPtr,*curPtr;   //一个尾指针，一个指向新节点的指针L=(LNode*)malloc(sizeof (LNode));if(!L)exit(OVERFLOW);L->next=NULL;               //先建立一个带头结点的单链表rearPtr=L;  //初始时头结点为尾节点,rearPtr指向尾巴节点for (int i=1;i<=n;i++){  //每次循环都开辟一个新节点，并把新节点拼到尾节点后curPtr=(LNode*)malloc(sizeof(LNode));//生成新结点if(!curPtr)exit(OVERFLOW);scanf("%d",&curPtr->data);//输入元素值curPtr->next=NULL;  //最后一个节点的next赋空rearPtr->next=curPtr;rearPtr=curPtr;}return OK;
}
void ListReverse_L(LinkList &L);
void ListPrint_L(LinkList &L){
//输出单链表LNode *p=L->next;  //p指向第一个元素结点while(p!=NULL){if(p->next!=NULL)printf("%d ",p->data);elseprintf("%d",p->data);p=p->next;}
}
int main()
{LinkList L;int n;scanf("%d",&n);if(ListCreate_L(L,n)!= OK) {printf("表创建失败！！！\n");return -1;}ListReverse_L(L);ListPrint_L(L);return 0;
}
/* 请在这里填写答案 */
输入格式：

第一行输入一个整数n，表示单链表中元素个数，接下来一行共n个整数，中间用空格隔开。

输出格式：

输出逆置后顺序表的各个元素，两个元素之间用空格隔开，最后一个元素后面没有空格。

输入样例：
4
1 2 3 4
输出样例：
4 3 2 1

和第一题类似

void ListReverse_L(LinkList &L)
{LinkList tmp, cur = L->next, pre = NULL;while (cur){tmp = cur->next;cur->next = pre;pre = cur;cur = tmp;}L->next = pre;
}

6-6 单链表插入排序

单链表插入排序
###目的：
掌握单链表的应用和插入排序的思想。
###内容：
编写一个函数insertion_sort，对一个无序单链表采用插入排序的方式，将其按递增方式排序，构成有序单链表。系统后台已经给出函数CreateListR和DispList的实现，只需实现函数insertion_sort即可。

###单链表结点类型定义：
typedef int ElemType;    //元素的数据类型typedef struct LNode {ElemType data;        //结点的数据域struct LNode *next;    //指向后继结点
} LinkNode;             //单链表结点类型
函数接口定义：
//尾插法建立单链表,细节不表
void CreateListR(LinkNode *&L, ElemType a[], int n);//输出线性表,细节不表
void DispList(LinkNode *L);//单链表插入排序
void insertion_sort(LinkNode *&L);
其中 L是带附加头结点的单链表的头指针。数组a[] 存放创建无序单链表的元素，n为数组长度，其值不超过3000。

裁判测试程序样例：
#include <stdio.h>
#include <stdlib.h>typedef int ElemType;    //元素的数据类型typedef struct LNode {ElemType data;        //结点的数据域struct LNode *next;    //指向后继结点
} LinkNode;             //单链表结点类型//尾插法建立单链表,细节不表
void CreateListR(LinkNode *&L, ElemType a[], int n);//输出线性表,细节不表
void DispList(LinkNode *L);//单链表插入排序：元素递增排序
void insertion_sort(LinkNode *&L);int main() 
{int n;scanf("%d", &n);ElemType a[n];for (int i = 0; i < n; i++)scanf("%d", &a[i]);LinkNode *A;CreateListR(A, a, n);insertion_sort(A);printf("排序后的单链表: ");DispList(A);return 0;
}/* 请在下面填写答案 */
输入样例：

输入有2行。
第1行为单链表的元素个数，接下来的一行为单链表的元素，以空格分隔。
5
4 2 5 1 3
输出样例：

输出有1行。
首先输出"排序后的单链表: "，之后输出排序后的单链表的元素，元素之间以一个空格分隔，行尾无多余的空格。
排序后的单链表: 1 2 3 4 5

首先复习一下插入排序：八大排序 —— 详细图文讲解_世真的博客-CSDN博客_排序算法

其次要注意有序部分，也就是 end 边界的控制，如果 end+1 比前面的有序部分的元素都大，说明 end+1 结点不需要挪动，那么 i 就往后移。反之，end+1 处的结点被插入到前面的某个位置，i 指向的结点就会自动的往后挪一位，也就不需要手动让 i 往后移了

void insertion_sort(LinkNode *&L)
{if (L->next == nullptr) return;LinkNode* i = L->next;while (i->next != nullptr){LinkNode* end = i;LinkNode* tmp = end->next;LinkNode* cur = L->next, *pre = L;while (cur != end->next){if (cur->data >= tmp->data){end->next = end->next->next;pre->next = tmp;tmp->next = cur;break;}pre = cur;cur = cur->next;}if (cur == end->next){i = i->next;}}
}

6-7 双端队列

双端队列（deque，即double-ended queue的缩写）是一种具有队列和栈性质的数据结构，即可以（也只能）在线性表的两端进行插入和删除。若以顺序存储方式实现双端队列，请编写例程实现下列操作：

Push(X,D)：将元素X插入到双端队列D的头；
Pop(D)：删除双端队列D的头元素，并返回；
Inject(X,D)：将元素X插入到双端队列D的尾部；
Eject(D)：删除双端队列D的尾部元素，并返回。

函数接口定义：

bool Push( ElementType X, Deque D );
ElementType Pop( Deque D );
bool Inject( ElementType X, Deque D );
ElementType Eject( Deque D );

其中Deque结构定义如下：

typedef int Position;
typedef struct QNode *PtrToQNode;
struct QNode {ElementType *Data;      /* 存储元素的数组   */Position Front, Rear;   /* 队列的头、尾指针 */int MaxSize;            /* 队列最大容量     */
};
typedef PtrToQNode Deque;

注意：Push和Inject应该在正常执行完操作后返回true，或者在出现非正常情况时返回false。当Front和Rear相等时队列为空，Pop和Eject必须返回由裁判程序定义的ERROR。

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>#define ERROR -1
typedef int ElementType;
typedef enum { push, pop, inject, eject, end } Operation;
typedef enum { false, true } bool;
typedef int Position;
typedef struct QNode *PtrToQNode;
struct QNode {ElementType *Data;      /* 存储元素的数组   */Position Front, Rear;   /* 队列的头、尾指针 */int MaxSize;            /* 队列最大容量     */
};
typedef PtrToQNode Deque; Deque CreateDeque( int MaxSize )
{   /* 注意：为区分空队列和满队列，需要多开辟一个空间 */Deque D = (Deque)malloc(sizeof(struct QNode));MaxSize++;D->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));D->Front = D->Rear = 0;D->MaxSize = MaxSize;return D;
}bool Push( ElementType X, Deque D );
ElementType Pop( Deque D );
bool Inject( ElementType X, Deque D );
ElementType Eject( Deque D );Operation GetOp();          /* 裁判实现，细节不表 */
void PrintDeque( Deque D ); /* 裁判实现，细节不表 */int main()
{ElementType X;Deque D;int N, done = 0;scanf("%d", &N);D = CreateDeque(N);while (!done) {switch(GetOp()) {case push: scanf("%d", &X);if (!Push(X, D)) printf("Deque is Full!\n");break;case pop:X = Pop(D);if ( X==ERROR ) printf("Deque is Empty!\n");else printf("%d is out\n", X);break;case inject: scanf("%d", &X);if (!Inject(X, D)) printf("Deque is Full!\n");break;case eject:X = Eject(D);if ( X==ERROR ) printf("Deque is Empty!\n");else printf("%d is out\n", X);break;case end:PrintDeque(D);done = 1;break;}}return 0;
}/* 你的代码将被嵌在这里 */

输入样例：

3
Pop
Inject 1
Pop
Eject
Push 2
Push 3
Eject
Inject 4
Inject 5
Inject 6
Push 7
Pop
End

输出样例：

Deque is Empty!
1 is out
Deque is Empty!
2 is out
Deque is Full!
Deque is Full!
3 is out
Inside Deque: 4 5

考察循环队列的实现：

bool Full(Deque D)
{return (D->Rear + 1) % D->MaxSize == D->Front;
}bool Empty(Deque D)
{return D->Front == D->Rear;
}bool Push( ElementType X, Deque D )
{if (Full(D)) return false;D->Front = (D->Front - 1 + D->MaxSize) % D->MaxSize;D->Data[D->Front] = X;return true;
}ElementType Pop( Deque D )
{if (Empty(D)) return ERROR;ElementType ret = D->Data[D->Front];D->Front = (D->Front + 1) % D->MaxSize;return ret;
}bool Inject( ElementType X, Deque D )
{if (Full(D)) return false;D->Data[D->Rear] = X;D->Rear = (D->Rear + 1) % D->MaxSize;return true;
}ElementType Eject( Deque D )
{if (Empty(D)) return ERROR;D->Rear = (D->Rear - 1 + D->MaxSize) % D->MaxSize;return D->Data[D->Rear];
}

6-8 有序数组的插入

本题要求将任一给定元素插入从大到小排好序的数组中合适的位置，以保持结果依然有序。

函数接口定义：
bool Insert( List L, ElementType X );
其中List结构定义如下：
typedef int Position;
typedef struct LNode *List;
struct LNode {ElementType Data[MAXSIZE];Position Last; /* 保存线性表中最后一个元素的位置 */
};
L是用户传入的一个线性表，其中ElementType元素可以通过>、==、<进行比较，并且题目保证传入的数据是递减有序的。函数Insert要将X插入Data[]中合适的位置，以保持结果依然有序（注意：元素从下标0开始存储）。但如果X已经在Data[]中了，就不要插入，返回失败的标记false；如果插入成功，则返回true。另外，因为Data[]中最多只能存MAXSIZE个元素，所以如果插入新元素之前已经满了，也不要插入，而是返回失败的标记false。

裁判测试程序样例：
#include <stdio.h>
#include <stdlib.h>#define MAXSIZE 10
typedef enum {false, true} bool;
typedef int ElementType;typedef int Position;
typedef struct LNode *List;
struct LNode {ElementType Data[MAXSIZE];Position Last; /* 保存线性表中最后一个元素的位置 */
};List ReadInput(); /* 裁判实现，细节不表。元素从下标0开始存储 */
void PrintList( List L ); /* 裁判实现，细节不表 */
bool Insert( List L, ElementType X );int main()
{List L;ElementType X;L = ReadInput();scanf("%d", &X);if ( Insert( L, X ) == false )printf("Insertion failed.\n");PrintList( L );return 0;
}/* 你的代码将被嵌在这里 */
输入样例1：
5
35 12 8 7 3
10
输出样例1：
35 12 10 8 7 3
Last = 5
输入样例2：
6
35 12 10 8 7 3
8
输出样例2：
Insertion failed.
35 12 10 8 7 3
Last = 5

使用二分查找找到要插入的位置，如果找到相同的就返回false，然后就是正常的数组插入逻辑，挪数据，然后填数。

二分查找挺容易错的，主要是注意区间的开闭：[LeetCode刷题]带你手撕二分法，区间开闭如何理解，一文学会_世真的博客-CSDN博客_二分法区间是开还是闭

bool Insert( List L, ElementType X )
{if (L->Last == MAXSIZE - 1) return false;int l = 0, r = L->Last;while (l <= r){int mid = (l + r) / 2;if (L->Data[mid] < X){r = mid - 1;}else if (L->Data[mid] > X){l = mid + 1;}else if (L->Data[mid] == X){return false;}}int end;for (end = L->Last; end > r; --end){L->Data[end + 1] = L->Data[end];}L->Data[end + 1] = X;++L->Last;return true;
}

6-9 线性表元素的区间删除

给定一个顺序存储的线性表，请设计一个函数删除所有值大于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 )
{List res = (List)malloc(sizeof(struct LNode));res->Last = -1;for (int i = 0; i <= L->Last; ++i){if (L->Data[i] <= minD || L->Data[i] >= maxD){res->Data[res->Last + 1] = L->Data[i];++res->Last;}}return res;
}

6-10 在一个数组中实现两个堆栈

本题要求在一个数组中实现两个堆栈。

函数接口定义：

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 <stdio.h>
#include <stdlib.h>#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("%d", &N);S = CreateStack(N);while ( !done ) {switch( GetOp() ) {case push: scanf("%d %d", &Tag, &X);if (!Push(S, X, Tag)) printf("Stack %d is Full!\n", Tag);break;case pop:scanf("%d", &Tag);X = Pop(S, Tag);if ( X==ERROR ) printf("Stack %d is Empty!\n", Tag);break;case end:PrintStack(S, 1);PrintStack(S, 2);done = 1;break;}}return 0;
}/* 你的代码将被嵌在这里 */

输入样例：

5
Push 1 1
Pop 2
Push 2 11
Push 1 2
Push 2 12
Pop 1
Push 2 13
Push 2 14
Push 1 3
Pop 2
End

输出样例：

Stack 2 Empty
Stack 2 is Empty!
Stack Full
Stack 1 is Full!
Pop from Stack 1: 1
Pop from Stack 2: 13 12 11

共享栈的实现，有点类似内存中栈区和堆区的关系

bool Full(Stack S)
{return S->Top1 + 1 == S->Top2;
}bool Tag1Empty(Stack S)
{return S->Top1 == -1;
}bool Tag2Empty(Stack S)
{return S->Top2 == S->MaxSize;
}Stack CreateStack( int MaxSize )
{Stack ret = (Stack)malloc(sizeof(struct SNode));ret->Data = (ElementType*)malloc(MaxSize * sizeof(ElementType));ret->Top1 = -1;ret->Top2 = MaxSize;ret->MaxSize = MaxSize;return ret;
}bool Push( Stack S, ElementType X, int Tag )
{if (Full(S)){printf("Stack Full\n");return false;}if (Tag == 1){S->Data[S->Top1 + 1] = X;++S->Top1;}else if (Tag == 2){S->Data[S->Top2 - 1] = X;--S->Top2;}return true;
}ElementType Pop( Stack S, int Tag )
{if (Tag == 1){if (Tag1Empty(S)){printf("Stack 1 Empty\n");return ERROR;}--S->Top1;return S->Data[S->Top1 + 1];}else if (Tag == 2){if (Tag2Empty(S)){printf("Stack 2 Empty\n");return ERROR;}++S->Top2;return S->Data[S->Top2 - 1];}return 0;
}

6-11 使用函数实现字符串部分复制

本题要求编写函数，将输入字符串t中从第m个字符开始的全部字符复制到字符串s中。

函数接口定义：
void strmcpy( char *t, int m, char *s );
函数strmcpy将输入字符串char *t中从第m个字符开始的全部字符复制到字符串char *s中。若m超过输入字符串的长度，则结果字符串应为空串。

裁判测试程序样例：
#include <stdio.h>
#define MAXN 20void strmcpy( char *t, int m, char *s );
void ReadString( char s[] ); /* 由裁判实现，略去不表 */int main()
{char t[MAXN], s[MAXN];int m;scanf("%d\n", &m);ReadString(t);strmcpy( t, m, s );printf("%s\n", s);return 0;
}/* 你的代码将被嵌在这里 */
输入样例：
7
happy new year
输出样例：
new year

void strmcpy( char *t, int m, char *s )
{int len = strlen(t);if (m > len){s[0] = '\0';return;}int j = 0;for (int i = m - 1; i <= len; ++i){s[j++] = t[i];}
}

6-12 判断回文字符串

本题要求编写函数，判断给定的一串字符是否为“回文”。所谓“回文”是指顺读和倒读都一样的字符串。如“XYZYX”和“xyzzyx”都是回文。

函数接口定义：
bool palindrome( char *s );
函数palindrome判断输入字符串char *s是否为回文。若是则返回true，否则返回false。

裁判测试程序样例：
#include <stdio.h>
#include <string.h>#define MAXN 20
typedef enum {false, true} bool;bool palindrome( char *s );int main()
{char s[MAXN];scanf("%s", s);if ( palindrome(s)==true )printf("Yes\n");elseprintf("No\n");printf("%s\n", s);return 0;
}/* 你的代码将被嵌在这里 */
输入样例1：
thisistrueurtsisiht
输出样例1：
Yes
thisistrueurtsisiht
输入样例2：
thisisnottrue
输出样例2：
No
thisisnottrue

bool palindrome( char *s )
{int len = strlen(s);int l = 0, r = len - 1;while (l < len){if (s[l] != s[r]) return false;++l;--r;}return true;
}

6-13 计算最长的字符串长度

本题要求实现一个函数，用于计算有n个元素的指针数组s中最长的字符串的长度。

函数接口定义：
int max_len( char *s[], int n );
其中n个字符串存储在s[]中，函数max_len应返回其中最长字符串的长度。

裁判测试程序样例：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>#define MAXN 10
#define MAXS 20int max_len( char *s[], int n );int main()
{int i, n;char *string[MAXN] = {NULL};scanf("%d", &n);for(i = 0; i < n; i++) {string[i] = (char *)malloc(sizeof(char)*MAXS);scanf("%s", string[i]);}printf("%d\n", max_len(string, n));return 0;
}/* 你的代码将被嵌在这里 */
输入样例：
4
blue
yellow
red
green
输出样例：
6

int max_len( char *s[], int n )
{int res = 0;for (int i = 0; i < n; ++i){int len = strlen(s[i]);res = res < len ? len : res;}return res;
}

6-14 求二叉树高度

本题要求给定二叉树的高度。

函数接口定义：
int GetHeight( BinTree BT );
其中BinTree结构定义如下：
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{ElementType Data;BinTree Left;BinTree Right;
};
要求函数返回给定二叉树BT的高度值。

裁判测试程序样例：
#include <stdio.h>
#include <stdlib.h>typedef char ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{ElementType Data;BinTree Left;BinTree Right;
};BinTree CreatBinTree(); /* 实现细节忽略 */
int GetHeight( BinTree BT );int main()
{BinTree BT = CreatBinTree();printf("%d\n", GetHeight(BT));return 0;
}
/* 你的代码将被嵌在这里 */
输出样例（对于图中给出的树）：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-atiTGova-1664628378706)(https://images.ptausercontent.com/40)]
4

本题详解以及其他二叉树的内容：[数据结构](9)二叉树的遍历_世真的博客-CSDN博客

int GetHeight( BinTree BT )
{if (BT == NULL) return 0;int leftHeight = GetHeight(BT->Left);int rightHeight = GetHeight(BT->Right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

6-15 二叉树的遍历

本题要求给定二叉树的4种遍历。

函数接口定义：

void InorderTraversal( BinTree BT );
void PreorderTraversal( BinTree BT );
void PostorderTraversal( BinTree BT );
void LevelorderTraversal( BinTree BT );

其中BinTree结构定义如下：

typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{ElementType Data;BinTree Left;BinTree Right;
};

要求4个函数分别按照访问顺序打印出结点的内容，格式为一个空格跟着一个字符。

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>typedef char ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{ElementType Data;BinTree Left;BinTree Right;
};BinTree CreatBinTree(); /* 实现细节忽略 */
void InorderTraversal( BinTree BT );
void PreorderTraversal( BinTree BT );
void PostorderTraversal( BinTree BT );
void LevelorderTraversal( BinTree BT );int main()
{BinTree BT = CreatBinTree();printf("Inorder:");    InorderTraversal(BT);    printf("\n");printf("Preorder:");   PreorderTraversal(BT);   printf("\n");printf("Postorder:");  PostorderTraversal(BT);  printf("\n");printf("Levelorder:"); LevelorderTraversal(BT); printf("\n");return 0;
}
/* 你的代码将被嵌在这里 */

输出样例（对于图中给出的树）：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qY2qcZZ5-1664628378712)(https://images.ptausercontent.com/45)]

Inorder: D B E F A G H C I
Preorder: A B D F E C G H I
Postorder: D E F B H G I C A
Levelorder: A B C D F G I E H

这里的队列可以用数组模拟，代码量会少一些，我这边是以前实现过一个队列，就直接复制过来了。

详解：[数据结构](9)二叉树的遍历_世真的博客-CSDN博客

void InorderTraversal(BinTree BT)
{if (BT == NULL) return;InorderTraversal(BT->Left);printf(" %c", BT->Data);InorderTraversal(BT->Right);
}void PreorderTraversal(BinTree BT)
{if (BT == NULL) return;printf(" %c", BT->Data);PreorderTraversal(BT->Left);PreorderTraversal(BT->Right);
}void PostorderTraversal(BinTree BT)
{if (BT == NULL) return;PostorderTraversal(BT->Left);PostorderTraversal(BT->Right);printf(" %c", BT->Data);
}typedef BinTree QDataType;
typedef enum { false, true } bool;typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QNode;typedef struct queue
{QNode* head;QNode* tail;
}queue;void QueueInit(queue* pq)
{pq->head = pq->tail = NULL;
}void QueueDestroy(queue* pq)
{QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;
}
void QueuePush(queue* pq, QDataType x)
{QNode* newnode = (QNode*)malloc(sizeof(QNode));newnode->data = x;newnode->next = NULL;if (pq->tail == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}
}
void QueuePop(queue* pq)
{if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}
}
bool QueueEmpty(queue* pq)
{return pq->head == NULL;
}size_t QueueSize(queue* pq)
{QNode* cur = pq->head;size_t size = 0;while (cur){size++;cur = cur->next;}return size;
}QDataType QueueFront(queue* pq)
{return pq->head->data;
}QDataType QueueBack(queue* pq)
{return pq->tail->data;
}void LevelorderTraversal(BinTree BT)
{queue q;QueueInit(&q);if (BT) QueuePush(&q, BT);while (!QueueEmpty(&q)){BinTree front = QueueFront(&q);QueuePop(&q);printf(" %c", front->Data);if (front->Left) QueuePush(&q, front->Left);if (front->Right) QueuePush(&q, front->Right);}QueueDestroy(&q);
}

6-16 先序输出叶结点

本题要求按照先序遍历的顺序输出给定二叉树的叶结点。

函数接口定义：
void PreorderPrintLeaves( BinTree BT );
其中BinTree结构定义如下：
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{ElementType Data;BinTree Left;BinTree Right;
};
函数PreorderPrintLeaves应按照先序遍历的顺序输出给定二叉树BT的叶结点，格式为一个空格跟着一个字符。

裁判测试程序样例：
#include <stdio.h>
#include <stdlib.h>typedef char ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{ElementType Data;BinTree Left;BinTree Right;
};BinTree CreatBinTree(); /* 实现细节忽略 */
void PreorderPrintLeaves( BinTree BT );int main()
{BinTree BT = CreatBinTree();printf("Leaf nodes are:");PreorderPrintLeaves(BT);printf("\n");return 0;
}
/* 你的代码将被嵌在这里 */
输出样例（对于图中给出的树）：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-G2aA7gRN-1664628378713)(https://images.ptausercontent.com/81)]
Leaf nodes are: D E H I

前序遍历，额外判断是不是叶子结点：

void PreorderPrintLeaves( BinTree BT )
{if (BT == NULL) return;if (BT->Left == NULL && BT->Right == NULL) printf(" %c", BT->Data);PreorderPrintLeaves(BT->Left);PreorderPrintLeaves(BT->Right);
}

6-17 二叉树的非递归遍历

本题要求用非递归的方法实现对给定二叉树的 3 种遍历。

函数接口定义：

void InorderTraversal( BinTree BT );
void PreorderTraversal( BinTree BT );
void PostorderTraversal( BinTree BT );

其中BinTree结构定义如下：

typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{ElementType Data;BinTree Left;BinTree Right;int flag;
};

要求 3 个函数分别按照访问顺序打印出结点的内容，格式为一个空格跟着一个字符。

此外，裁判程序中给出了堆栈的全套操作，可以直接调用。

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>
typedef enum { false, true } bool;typedef char ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{ElementType Data;BinTree Left;BinTree Right;int flag;
};/*------堆栈的定义-------*/
typedef Position SElementType;
typedef struct SNode *PtrToSNode;
struct SNode {SElementType Data;PtrToSNode Next;
};
typedef PtrToSNode Stack;/* 裁判实现，细节不表 */
Stack CreateStack();
bool IsEmpty( Stack S );
bool Push( Stack S, SElementType X );
SElementType Pop( Stack S ); /* 删除并仅返回S的栈顶元素 */
SElementType Peek( Stack S );/* 仅返回S的栈顶元素 */
/*----堆栈的定义结束-----*/BinTree CreateBinTree(); /* 裁判实现，细节不表 */
void InorderTraversal( BinTree BT );
void PreorderTraversal( BinTree BT );
void PostorderTraversal( BinTree BT );int main()
{BinTree BT = CreateBinTree();printf("Inorder:");    InorderTraversal(BT);    printf("\n");printf("Preorder:");   PreorderTraversal(BT);   printf("\n");printf("Postorder:");  PostorderTraversal(BT);  printf("\n");return 0;
}
/* 你的代码将被嵌在这里 */

输入样例：

如图

输出样例：

Inorder: D B E F A G H C I
Preorder: A B D F E C G H I
Postorder: D E F B H G I C A

void InorderTraversal( BinTree BT )
{Stack st = CreateStack();BinTree cur = BT;while (cur || !IsEmpty(st)){while (cur){Push(st, cur);cur = cur->Left;}BinTree top = Peek(st);printf(" %c",top->Data);Pop(st);cur = top->Right;}
}void PreorderTraversal( BinTree BT )
{Stack st = CreateStack();BinTree cur = BT;while (cur || !IsEmpty(st)){while (cur){printf(" %c", cur->Data);Push(st, cur);cur = cur->Left;}BinTree top = Peek(st);Pop(st);cur = top->Right;}
}void PostorderTraversal( BinTree BT )
{Stack st = CreateStack();BinTree cur = BT, pre = NULL;while (cur || !IsEmpty(st)){while (cur){Push(st, cur);cur = cur->Left;}BinTree top = Peek(st);if (top->Right == NULL || top->Right == pre){printf(" %c", top->Data);Pop(st);pre = top;}else{cur = top->Right;}}
}

6-18 邻接矩阵存储图的深度优先遍历

试实现邻接矩阵存储图的深度优先遍历。

函数接口定义：
void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) );
其中MGraph是邻接矩阵存储的图，定义如下：
typedef struct GNode *PtrToGNode;
struct GNode{int Nv;  /* 顶点数 */int Ne;  /* 边数   */WeightType G[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵 */
};
typedef PtrToGNode MGraph; /* 以邻接矩阵存储的图类型 */
函数DFS应从第V个顶点出发递归地深度优先遍历图Graph，遍历时用裁判定义的函数Visit访问每个顶点。当访问邻接点时，要求按序号递增的顺序。题目保证V是图中的合法顶点。

裁判测试程序样例：
#include <stdio.h>typedef enum {false, true} bool;
#define MaxVertexNum 10  /* 最大顶点数设为10 */
#define INFINITY 65535   /* ∞设为双字节无符号整数的最大值65535*/
typedef int Vertex;      /* 用顶点下标表示顶点,为整型 */
typedef int WeightType;  /* 边的权值设为整型 */typedef struct GNode *PtrToGNode;
struct GNode{int Nv;  /* 顶点数 */int Ne;  /* 边数   */WeightType G[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵 */
};
typedef PtrToGNode MGraph; /* 以邻接矩阵存储的图类型 */
bool Visited[MaxVertexNum]; /* 顶点的访问标记 */MGraph CreateGraph(); /* 创建图并且将Visited初始化为false；裁判实现，细节不表 */void Visit( Vertex V )
{printf(" %d", V);
}void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) );int main()
{MGraph G;Vertex V;G = CreateGraph();scanf("%d", &V);printf("DFS from %d:", V);DFS(G, V, Visit);return 0;
}/* 你的代码将被嵌在这里 */
输入样例：给定图如下

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8bNZg7ih-1664628378714)(https://images.ptausercontent.com/101)]
5
输出样例：
DFS from 5: 5 1 3 0 2 4 6

void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) ){Visit(V);Visited[V] = true;for(int w = 0; w < Graph->Nv; ++w){if(Graph->G[V][w] == 1){if(!Visited[w])DFS(Graph, w, Visit);}}
}

6-19 邻接表存储图的广度优先遍历

试实现邻接表存储图的广度优先遍历。

函数接口定义：

void BFS ( LGraph Graph, Vertex S, void (*Visit)(Vertex) );

其中LGraph是邻接表存储的图，定义如下：

/* 邻接点的定义 */
typedef struct AdjVNode *PtrToAdjVNode; 
struct AdjVNode{Vertex AdjV;        /* 邻接点下标 */PtrToAdjVNode Next; /* 指向下一个邻接点的指针 */
};/* 顶点表头结点的定义 */
typedef struct Vnode{PtrToAdjVNode FirstEdge; /* 边表头指针 */
} AdjList[MaxVertexNum];     /* AdjList是邻接表类型 *//* 图结点的定义 */
typedef struct GNode *PtrToGNode;
struct GNode{  int Nv;     /* 顶点数 */int Ne;     /* 边数   */AdjList G;  /* 邻接表 */
};
typedef PtrToGNode LGraph; /* 以邻接表方式存储的图类型 */

函数BFS应从第S个顶点出发对邻接表存储的图Graph进行广度优先搜索，遍历时用裁判定义的函数Visit访问每个顶点。当访问邻接点时，要求按邻接表顺序访问。题目保证S是图中的合法顶点。

裁判测试程序样例：

#include <stdio.h>typedef enum {false, true} bool;
#define MaxVertexNum 10   /* 最大顶点数设为10 */
typedef int Vertex;       /* 用顶点下标表示顶点,为整型 *//* 邻接点的定义 */
typedef struct AdjVNode *PtrToAdjVNode; 
struct AdjVNode{Vertex AdjV;        /* 邻接点下标 */PtrToAdjVNode Next; /* 指向下一个邻接点的指针 */
};/* 顶点表头结点的定义 */
typedef struct Vnode{PtrToAdjVNode FirstEdge; /* 边表头指针 */
} AdjList[MaxVertexNum];     /* AdjList是邻接表类型 *//* 图结点的定义 */
typedef struct GNode *PtrToGNode;
struct GNode{  int Nv;     /* 顶点数 */int Ne;     /* 边数   */AdjList G;  /* 邻接表 */
};
typedef PtrToGNode LGraph; /* 以邻接表方式存储的图类型 */bool Visited[MaxVertexNum]; /* 顶点的访问标记 */LGraph CreateGraph(); /* 创建图并且将Visited初始化为false；裁判实现，细节不表 */void Visit( Vertex V )
{printf(" %d", V);
}void BFS ( LGraph Graph, Vertex S, void (*Visit)(Vertex) );int main()
{LGraph G;Vertex S;G = CreateGraph();scanf("%d", &S);printf("BFS from %d:", S);BFS(G, S, Visit);return 0;
}/* 你的代码将被嵌在这里 */

输入样例：给定图如下

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1FwP5Fgh-1664628378714)(https://images.ptausercontent.com/102)]

输出样例：

BFS from 2: 2 0 3 5 4 1 6

void BFS ( LGraph Graph, Vertex S, void (*Visit)(Vertex) )
{Vertex queue[101];int l = 0, r = 0;queue[r++] = S;Visit(S);Visited[S] = true;PtrToAdjVNode tmp;while (l != r){tmp = Graph->G[queue[l++]].FirstEdge;while (tmp){Vertex pos = tmp->AdjV;if (!Visited[pos]){Visit(pos);Visited[pos] = true;queue[r++] = pos;}tmp = tmp->Next;}}
}

6-20 二分查找

本题要求实现二分查找算法。

函数接口定义：
Position BinarySearch( List L, ElementType X );
其中List结构定义如下：
typedef int Position;
typedef struct LNode *List;
struct LNode {ElementType Data[MAXSIZE];Position Last; /* 保存线性表中最后一个元素的位置 */
};
L是用户传入的一个线性表，其中ElementType元素可以通过>、==、<进行比较，并且题目保证传入的数据是递增有序的。函数BinarySearch要查找X在Data中的位置，即数组下标（注意：元素从下标1开始存储）。找到则返回下标，否则返回一个特殊的失败标记NotFound。

裁判测试程序样例：
#include <stdio.h>
#include <stdlib.h>#define MAXSIZE 10
#define NotFound 0
typedef int ElementType;typedef int Position;
typedef struct LNode *List;
struct LNode {ElementType Data[MAXSIZE];Position Last; /* 保存线性表中最后一个元素的位置 */
};List ReadInput(); /* 裁判实现，细节不表。元素从下标1开始存储 */
Position BinarySearch( List L, ElementType X );int main()
{List L;ElementType X;Position P;L = ReadInput();scanf("%d", &X);P = BinarySearch( L, X );printf("%d\n", P);return 0;
}/* 你的代码将被嵌在这里 */
输入样例1：
5
12 31 55 89 101
31
输出样例1：
2
输入样例2：
3
26 78 233
31
输出样例2：
0

[LeetCode刷题]带你手撕二分法，区间开闭如何理解，一文学会_世真的博客-CSDN博客_二分法区间是开还是闭

Position BinarySearch( List L, ElementType X )
{int l = 0, r = L->Last;while (l <= r){int mid = (l + r) / 2;if (L->Data[mid] < X){l = mid + 1;}else if (L->Data[mid] > X){r = mid - 1;}else{return mid;}}return NotFound;
}