目录
1.数组
1.1.将一个数组前后翻转
bool Delete_Min(int A[], n, &min) {
if (!n) return false; //数组长度为0，返回false
int temp = INT_MAX, m; //INT_MAX为int类型的最大值
for (int i = 0; i < n; i++) { //遍历数组，找到数组当前的最小元素
if (A[i] < temp) {
temp = A[i]; //更新数组最小值
m = i; //记录数组下标
}
}
min = temp; //min保存最小值
A[m] = A[n - 1]; //m用数组中最后一个元素替换
return true;
}1.2.删除数组中值为x的元素
int DeleteX(int A[], x, n){
int i = 0, j = 0;
for (i = 0; i < n; i++) {
if (A[i] != x) { //当前元素的值不为x
A[j] = A[i]; //将其保存到数组下标为j的元素中
j++;
}
}
n = j;
return n; //返回删除x后的数组元素个数
}1.3.将两个有序数组合并成一个有序数组
int* Merge(int A[], B[], lenA, lenB) {
int *C = (int*)malloc((lenA + lenB) * sizeof(int));
int a = 0, b = 0, c = 0;
for (c = 0; a < lenA && b < lenB; c++) { //选择两个数组中的较小值放入数组C中
if (A[a] <= B[b]) C[c] = A[a++];
else C[c] = B[b++];
}
while (a < lenA) C[c++] = A[a++]; //将剩余数组放入C中
while (b < lenB) C[c++] = B[b++];
return C;
}1.4.真题
void ans(int A[], n, p){
int B[n], i, j;
for (i = 0, j = p; j < n; i++, j++) B[i] = A[j]; //数组后部分前移
for (j = 0; j < p; i++, j++) B[i] = A[j]; //数组前部分后移
for (i = 0; i < n; i++) cout << B[i]; //输出循环前移后的数组
}
int res(int A[], int B[], int n){
int i, j, k, mid;
for (i = 0, j = 0, k = 0; k < n; k++){
if (A[i] <= B[j]) { //当前A数组的元素小，保存A[i]
mid = A[i];
i++;
} else { //当前B数组的元素小，保存B[j]
mid = B[j];
j++;
}
}
return mid;
}void Qsort(int A[], L, R){
if (L >= R) return; //当前数组区间<= 1，返回
随机选择数组中一个元素和A[L]交换 //快速排序优化，使得基准元素的选取随机
int key = A[L], i = L, j = R; //选择A[L]作为基准元素，i和j分别为左右指针
while(i < j) {
while (i < j && key < A[j]) j--;
while (i < j && A[i] <= key) i++;
if (i < j) swap(A[i], A[j]); //交换A[i]和A[j]
}
swap(A[i], A[L]);
Qsort(A, L, i - 1); //递归排序左区间
Qsort(A, i + 1, R); //递归排序右区间
}
int ans(int A[], int B[], int n) {
int C[2n], i, j;
for (i = 0; i < n; i++) C[i] = A[i]; //复制数组A和数组B的元素
for (j = 0; j < n; i++, j++) C[i] = B[j];
Qsort(C, 0, 2n - 1); //对数组C进行快速排序
return C[n - 1]; //返回中位数
}
int ans(int A[], n){
int count[n];
for (int i = 0; i < n; i++) count[i] = 0; //初始化count数组
//遍历A数组，其元素的值作为count数组下标的元素+1，表示该元素在A数组中出现次数
for (int i = 0; i < n; i++) count[A[i]]++;
for (int i = 0; i < n; i++) { //当前元素出现次数符合主元素定义
if (count[i] > n / 2) return i; //返回i，即该元素的值
}
return -1; //没有元素符合主元素定义
}
int ans(int A[], n) {
bool B[n + 2]; //B用来标记数组中出现的正整数
for (int i = 0; i < n; i++) B[i] = false; //初始化B数组
for (int i = 0; i < n; i++) {
if (A[i] > 0) B[A[i]] = true; //该元素大于0，则在B数组中标记为已经出现
}
for (int i = 1; i < n; i++) {
if (B[i] == false) return i; //返回数组B中第一个false的元素下标
}
}void Qsort(int A[], L, R){
if (L >= R) return; //当前数组的区间<=1，返回
随机选择数组中一个元素和A[L]交换 //快速排序优化，使得基准元素的选择随机
int key = A[L], i = L, j = R; //选择A[L]作为基准元素，i和j分别为左右指针
while(i < j){
while(i < j && key < A[j]) j--;
while(i < j && A[i] <= key) i++;
if (i < j) swap(A[i], A[j]; //交换A[i]和A[j]
}
swap(A[L], A[i];
Qsort(A, L, i - 1); //递归排序左区间
Qsort(A, i + 1, R); //递归排序右区间
}
int ans(int A[], n){
Qsort(A, 0, n -1); //对数组A进行快速排序
int i = 0;
if (A[n - 1] <= 0) return 1; //数组中最大元素非正数，return 1
while (A[i] <= 0) i++; //移动到数组中第一个大于0的元素
if (A[i] != 0) return 1; //数组中第一个大于0的元素不是1，返回1
else {
while (A[i] != A[i + 1] - 1) i++; //找到第一个间断点
return i + 1;
}
}
int Dis(int a, b, c){
int res = abs(a - b) + abs(a - c) + abs(b - c); //计算绝对值
return res;
}
int Ans(int A[], int B[], int C[], int n1, int n2, int n3){
int min = INT_MAX, i, j, k, temp; //min取整型的最大值
for (int i = 0; i < n1; i++) { //循环遍历数组A
for (int j = 0; j < n2; j++) { //循环遍历数组B
for (int k = 0; k < n3; k++) { //循环遍历数组C
temp = Dis(A[i], B[j], C[k]);
if (temp < min) min = temp; //当前元素之间的距离更小，更新最小距离
}//for
}//for
}//for
return min; //返回最小距离
}2.链表
2.1.链表的数据结构定义
2.1.1.单链表
typedef struct LNode {
struct LNode *next;
int data;
}LNode, *LinkList;2.1.2.双链表
typedef struct LNode {
struct LNode *prior, *next;
int data;
}LNode, *LinkList;2.2.链表的操作
2.2.1.头插法（插入到链表头）
void HeadInsert(LinkList &L, int key) {
LNode *p = (LNode*)malloc(sizeof(LNode));
p->data = key;
p->next = L->next;
L->next = q;
}2.2.2.尾插法（插入到链表尾）
void TailInsert(LinkList &L, int key) {
LNode *q = (LNode*)malloc(sizeof(LNode);
q->data = key;
q->next = NULL;
LNode *p = L->next, *pre = L;
while (!p) {
pre = p;
p = p->next;
}
pre->next = q;
}2.2.3.链表逆置（头插法实现）
void Reverse(LinkList &L) {
LNode *p = L->next, *q = NULL;
L->next = NULL; //将L表断开
while (!p) {
q = p->next; //q指向p的下一个结点
p->next = L->next; //头插法
L->next = p;
p = q;
}
}2.2.4.链表的遍历
LNode *p = L->next;
while (!p) {
visit(p);
p = p->next;
}2.2.5.链表的删除
void Delete(LinkList &L, int &key) {
LNode *p = L->next, *pre = L;
移动p和pre到指定结点 //pre指向p的前驱结点
key = p->data; //key保存p的data领
pre->next = p->next; //pre的next指针指向p的后继节点
free(p);
}2.3.链表算法题
2.3.1.删除值为x的结点
void DeleteX(LinkList &L, int x){
LNode *p = L->next, *pre = L;
while (p) {
if (p->data == x) { //当前元素值为x
pre->next = p->next;
free(p);
p = pre->next;
} else { //当前元素值非x，p和pre向后移动
p = p->next;
pre = pre->next;
}
}
}2.3.2.单链表就地逆置
void reverse(LinkList &L){
LNode *p = L->next, *q;
L->next = NULL; //断链
while (p) {
q = p->next; //q指向p的下一个结点
p->next = L->next; //头插法
L->next = p;
p = q;
}
}2.3.3.将链表排序
void Sort(LinkList L) {
LNode *p = (LNode*p)malloc(sizeof(LNode));
p->next = NULL; //p的next指针置空
LNode *q = L->next, *qpre = L, *t, *tpre;
while (q) {
while (q) { //遍历单链表找到当前剩余元素中最小值
int min = INT_MAX;
if (q->data < min) { //更新最小值
min = q->data;
t = q; //用t和tpre保存当前的最小值元素和其前驱
tpre = qpre;
}
qpre = q; //q和qpre向后移动
q = q->next;
}
tpre->next = t->next; //将t从原链表中删除
t->next = p->next; //使用头插法将t插入到p后
p->next = t;
q = L->next; //将q重新指向第一个元素
qpre = L;
}
return p;
}2.3.4.拆分链表
LNode* (LinkList &L) {
LNode *p = (LNode*)malloc(sizeof(LNode);
p->next = NULL; //p为新链的头结点
LNode *q = L->next, *t = tpre->next, *r = L;
r->next = NULL; //r结点始终指向L的最后一个结点
while (q) {
t = q->next;
r->next = q; //奇数结点尾插法
r = q;
q = t;
t = q->next;
q->next = p->next; //偶数节点头插法
p->next = q;
q = t;
}
r->next = NULL; //将r的next指针置空
return p;
}2.3.5.删除链表中的重复元素
void Delete(LinkList &L) {
LNode *p = L->next;
while (p) {
LNode *post = p->next; //post指向p的下一个结点
while (post && post->data == p->data) { //post存在并且值和p相等时
LNode *temp = post; //temp指向post
post = post->next; //post向后移动
p->next = post; //将p的下一个结点修改为post
free(temp);
}
p = p->next;
}
}2.3.6.将两个递增链表合并成一个递减链表
void Merge(LinkList &L1, LinkList L2) {
LNode *p = L1->next, *q = L2->next, *temp;
L1->next = NULL; //L1断链
while (p && q) {
if (p->data <= q->data) { //当前p指向的元素更小
temp = p->next; //temp指向p的下一个结点
p->next = L1->next; //将p用头插法插入L1
L1->next = p;
p = temp; //p指向temp
} else { //当前q指向的元素更小
temp = q->next;
q->next = L1->next;
L1->next = q;
q = temp;
}
}//while
while (p) { //将剩余节点插入L1
temp = p->next;
p->next = L1->next;
L1->next = p;
p = temp;
}
while (q) {
temp = q->next;
q->next = L1->next;
L1->next = q;
q = temp;
}
return;
}2.3.7.将两个递增链表合并为一个递增链表
LNode *Merge(LinkList L1, LinkList L2) {
LNode *p = L1->next, *q = L2->next, *r, *temp;
LNode *L = (LNode*)malloc(sizeof(LNode));
L->next = NULL;
r = L;
while (p && q) {
if (p->data <= q->data) { //当前p指向的结点小于等于q
temp = p->next;
r->next = p; //p尾插法插入L中
r = p;
p = temp;
} else {
temp = q->next;
r->next = q;
r = q;
q = temp;
}
}
while (p) { //插入剩余结点
temp = p->next;
r->next = p;
r = p;
p = temp;
}
while (q) {
temp = q->next;
r->next = q;
r = q;
q = temp;
}
r->next = NULL; //将r的next指针置空
return L;
}
2.3.8.判断链表是否对称
bool IsSymmetry(LinkList L) {
LNode *pre = L->next, *post = L->prior, *f = L->next;
while (f != L && f->next != L) {
if (pre->data != post->data) return false; //前后指针data域不相等，返回false
f = f->next->next; //快指针往前移动两格
pre = pre->next; //前指针向后移动
post = post->prior; //后指针向前移动
}
return true; //对称
}2.3.9.依次输出链表中结点值最小的元素
void DeleteMin(LinkList &L) {
LNode *p = L->next, *ppre = L->next, *t, *min, *minpre;
while (L->next != L) {
p = L->next;
ppre = L;
int tempMin = INT_MAX; //当前最小值
while (p != L) {
if (p->data < INT_MAX) { //当前结点值更小，更新最小结点
min = p;
minpre = ppre;
} //p向后移动
ppre = p;
p = p->next;
}
cout << min->data; //输出最小结点的值
minpre->next = min->next; //删除min结点
free(min);
}//while
free(L); //删除头结点
}2.3.10.真题
void ans(LinkList L, int k){
LNode *p = L->link, *q = L->link;
for (int i = 0; i < k; i++) p = p->link; //p指针向后移动k个结点
while (p) {
p = p->link;
q = q->link;
}
cout << q->data;
}
LNode *ans(LinkList str1, LinkList str2){
LNode *p = str1->next;
int len1 = 0, len2 = 0;
while (p) { //得到str1的结点个数
p = p->next;
len1++;
}
p = str2->next;
while (p) { //得到str2的结点个数
p = p->next;
len2++;
}
LNode *q = str1->next, *r = str2->next;
if (len1 <= len2) { //str2为长表，q向后移动两表长度之差的值，使得两表剩余结点数相同
int len = len2 - len1;
while (len) {
r = r->next;
len--;
}
} else { //str1为长表
int len = len1 - len2;
while (len) {
q = q->next;
len--;
}
}
while (q != s) { //遍历剩余结点，找到两链表的共同后缀
q = q->next;
s = s->next;
}
return q;
}
void ans(LinkList &L){
bool A[n + 1]; //长度为n + 1的数组，用来标记该数是否出现过
for (int i = 0; i < n + 1; i++) A[i] = false; //初始化A数组
LNode *p = head->next, *pre = head;
while (p) {
int t = abs(p->data); //取当前结点值的绝对值
if (A[t]) { //该值出现过，删除该结点
LNode *r = p->next;
pre->next = r;
free(p);
p = r;
} else { //该值没有出现过，在数组A中标记该值，p和pre向后移动
A[t] = true;
pre = p;
p = p->next;
}
}//while
}
void ans(LinkList &L){
NODE *f = L->next, *s = L->next;
while (f && f->next) {
s = s->next; //慢指针每次向后移动一个结点
f = f->next->next; //快指针每次移动两个结点
}
s = s->next; //慢指针指向后半链的第一个结点
NODE *h = (NODE*)malloc(sizeof(NODE));
h->next = NULL;
while (s) { //头插法将后半链逆置
NODE *t = s->next;
s->next = h->next;
h->next = s;
s = t;
}
NODE *p = L->next; //p指向前半链的第一个结点
s = h->next; //s指向逆置后的后半链的第一个结点
while (s) {
NODE *t = s->next; //t指向s的下一个结点
s->next = p->next; //将s插入到p后
p->next = s;
p = s->next; //p指向下一个前半链的插入点
s = t; //s指向后半链的下一个结点
}
}3.栈
3.1.栈的数据结构定义
3.1.1.顺序栈
#define MAXSIZE 100
typedef struct Stack {
int data[MAXSIZE];
int top = -1;
}Stack;
3.1.2.链栈
typedef struct LStack {
int data;
struct LStack *next;
}SNode, *LStack;3.2.顺序栈的操作
3.2.1.栈的初始化
void InitStack (Stack &S) {
S.top = -1;
}3.2.1.入栈
bool Push(Stack &S, int key) {
if (S.top == MAXSIZE - 1) return false; //栈满
S.data[++top] = key;
return true;
}3.2.2.出栈
bool Pop (Stack &S, int &key) {
if (S.top == -1) return false; //栈空
key = S.data[top--];
return true;
}3.2.3.判断栈空
bool IsEmpty (Stack S) {
if (S.top == -1) return true;
else return false;
}3.3.链栈的基本操作
3.3.1.初始化
void InitStack (LStack &S) {
SNode *s = (SNode*)malloc(Sizeof(SNode));
S->next = NULL;
}3.3.2.入栈
void Push (LStack &S, int key) {
SNode *p = (SNode*)malloc(sizeof(SNode));
p->data = key;
p->next = S->next; //头插法
S->next = p;
}3.3.3.出栈
bool Pop (LStack &S, int &key) {
if (S->next == NULL) return false; //栈空
SNode *p = S->next;
key = p->data; //key保存栈顶元素的值
S->next = p->next;
free(p);
}3.3.4.判断栈空
bool IsEmpty(LStack &S) {
if (S->next == NULL) return true;
else return false;
}4.队列
4.1.队列的数据结构定义
4.1.1.顺序队列
#define MAXSIZE 100
typedef struct Queue {
int data[MAXSIZE];
int front, rear;
}Queue;4.1.2.链式队列
typedef struct LNode{
struct LNode *next;
int data;
}LNode;
typedef struct Queue{
LNode *front, *rear;
}Queue;4.2.顺序队列的基本操作
4.2.1.初始化
void InitQueue(Queue &Q){
Q.front = Q.rear = 0;
}4.2.2.入队
bool EnQueue(Queue &Q, int key){
if (Q.front == (Q.rear + 1) % MAXSIZE) return false; //队满
Q.data[rear] = key;
Q.rear = (Q.rear + 1) % MAXSIZE;
return true;
}4.2.3.出队
bool DeQueue(Queue &Q, int &key){
if (Q.rear == Q.front) return false; //队空
key = Q.front;
Q.front = (Q.front + 1) % MAXSIZE;
return true;
}4.2.4.判断队空
bool IsEmpty(Queue Q){
if (Q.front == Q.rear) return true;
else return false;
}4.3.链式队列的基本操作
4.3.1.初始化
void InitQueue(Queue &Q){
Q.front = Q.rear = (LNode*)maloc(sizeof(LNode));
Q.front->next = NULL;
}4.3.2.入队
void Queue(Queue &Q, int key){
LNode *p = (LNode*)malloc(sizeof(LNode)); //申明一个新结点
p->data = key;
p->next = NULL;
Q.rear->next = p; //尾插法插入到rear后
Q.rear = p; //更新rear
}4.3.3.出队
bool DeQueue(Queue &Q, int &key){
if (Q.front == Q.rear) return false; //队空
LNode *p = Q.front->next;
key = p->data; //保存队首元素的数据
Q.front->next = p->next;
if (Q.rear == p) Q.rear = Q.front; //队列中只有一个元素
free(p);
return true;
}4.3.4.判断队空
bool IsEmpty(Queue Q){
if (Q.rear == Q.front) return true;
else return false;
}5.树
5.1.树的数据结构定义
5.1.1.二叉树的链式存储
typedef struct BiTree{
sturct BiTree *lchild, *rchild; //左右孩子指针
int value; //结点数据
}BiTNode, *BiTree;5.1.2.二叉树的顺序存储
#define MAXSIZE 100
typedef struct TreeNode{
int value; //结点数据
bool IsEmpty; //该结点是否存在
}TreeNode;
void InitTree(TreeNode T[], int len){
for (int i = 0; i < len; i++) T[i].IsEmpty = true; //将该结点初始化为空结点
}
int main(){
TreeNode[MAXSIZE]; //申明一个长度为MAXSIZE的TreeNode数组
InitTree(T); //初始化树
...
}5.1.3.双亲表示法
#define MAXSIZE 100 //树中最多结点数
typedef struct TreeNode{
int data; //结点数据
int parent; //该结点的双亲结点在数组的下标
}TreeNode;
typedef struct Tree{
TreeNode[MAXSIZE]; //长度为MAXSIZE的TreeNode类型的数组
int treeNum; //结点数
}Tree;5.1.4.孩子表示法
#define MAXSIZE 100
//孩子结点
typedef struct Child{
int index; //该结点的编号
struct Child *next; //指向该结点的下一个孩子结点的指针
}Child;
//结点信息
typedef struct TreeNode{
Child *firstTNode; //指向该结点的第一个孩子结点的指针
int data; //该结点数据
}TreeNode;
TreeNode[MAXSIZE]; //定义一个长度为MAXSIZE的树5.1.5.孩子兄弟表示法
#define MAXSIZE 100
typedef struct CSNode{
struct CSNode *firstChild, *nextSibling; //指向第一个孩子和右兄弟节点
int data; //该结点数据
}CSNode;
CSNode[MAXSIZE];5.1.6.线索二叉树
typedef struct ThreadNode{
struct ThreadNode *lchild, *rchild; //左右孩子指针
int ltag, rtag; //左右线索标志
int data; //结点数据
}ThreadNode, *ThreadTree;5.2.二叉树的基本操作
5.2.1.先序遍历
void PreOrder(BiTree T){
if (T) {
visit(T);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
5.2.2.中序遍历
void InOrder(BiTree T){
if (T) {
InOrder(T->lchild);
visit(T);
InOrder(T->rchild);
}
}5.2.3.后序遍历
void PostOrder(BiTree T){
if (T) {
PostOrder(T->lchild);
PostOrder(T->rchild);
visit(T);
}
}5.2.4.层次遍历
void LevelOrder(BiTree T){
InitQueue(Q);
EnQueue(Q, T);
BiTNode *p;
while (!IsEmpty(Q)) {
DeQueue(Q, p);
visit(p);
if (p->lchild) EnQueue(Q, p->lchild);
if (p->rchild) EnQueue(Q, p->rchild);
}
}5.3.并查集
5.3.1.并查集的定义和初始化
#define MAXSIZE 100
int UFSet[MAXSIZE]; //并查集通过数组表示
void InitSet(int S[]){
for(int i = 0; i < MAXSIZE; i++) S[i] = -1;
}5.3.2.FIND操作
//FIND操作用于查找该结点的所属集合
int Find(int S[], int x) {
while (S[x] >= 0) x = S[x]; //递归寻找直到该结点的值为-1
return x;
}5.3.3.UNION操作
void Union(int S[], root1, root2) {
//要求root1和root2是不同的集合
if (root1 == root2) return;
//将root2合并到root1中
S[root2] = root1;
}5.3.4.FIND优化——压缩路径
//先找到根节点，然后进行压缩路径
int Find(int S[], x) {
int root = x;
while (S[root] >= 0) root = S[root]; //循环找到当前结点的根节点
while (x != root) { //循环直到x指向根节点
int temp = S[x]; //用temp保存x的父结点
S[x] = root; //将结点x的父节点修改为根节点
x = temp; //x更新为原父节点
}
}5.3.5.UNION优化——小树合并大树
//数组中根节点的值为其集合中结点的总数
void Union(int S[], root1, root2){
if (root1 == root2) return;
if (root1 <= root2) { //root1的结点数更多或者二者相等
S[root1] += S[root2]; //更新root1的结点数为root1和root2的总和
S[root2] = root1; //将root2合并到root1中
} else { //root2的结点数更多
S[root2] += S[root1];
S[root1] = root2;
}
}5.4.二叉树算法题
5.4.1.计算二叉树中双分支结点的个数
int count = 0; //双分支结点个数
void InOrder(BiTree T){
if (T) {
//当前结点的左右孩子都存在，count++
if (T->lchild && T->rchild) count++;
if (T->lchild) InOrder(T->lchild); //递归遍历左子树
if (T->rchild) Inorder(T->rchild); //递归遍历右子树
}
void ans(BiTree T) {
InOrder(T); //先序遍历该树
cout << count; //输出双分支结点个数
}5.4.2.交换二叉树中所有左右子树
void PostOrder(BiTree &T){
if (T) {
PostOrder(T->lchild);
PostOrder(T->rchild);
BiTNode *t = T->lchild;
T->lchild = T->rchild;
T->rchild = t;
}
}
void ans(BiTree &T){
Post(Order(T));
return
}5.4.3.求先序遍历第k个元素
int t = 0;
int res = 0;
void PreOrder(BiTree T) {
if (T) {
t--;
if (t == 0) res = T->data; //第k个结点，用res保存当前结点的值
PreOrder(T->lchild); //递归访问左子树
PreOrder(T->rchild); //递归访问右子树
}
}
void ans(BiTree T, int k) {
t = k;
PreOrder(T);
cout << res; //输出第k个结点的值
}5.4.4.删去值为x的子树
int k;
void Delete(BiTree &T){ //后序遍历的方式删除结点
if (T) {
DeleteX(T->lchild);
DeleteX(T->rchild);
free(T);
}
}
void PreOrder(BiTree &T) {
if (T) {
BiTNode *t;
if (T->lchild->data == k) { //左子树的值为x，删除左子树
t = T->lchild;
T->lchild = NULL;
Delete(t);
}
if (T->rchild->data == k) { //右子树的值为x，删除右子树
t = t->rchild;
T->rchild = NULL;
Delete(t);
}
if (T->lchild) PreOrder(T->lchild); //递归遍历左子树
if (T->rchild) PreOrder(T->rchild); //递归遍历右子树
}//if
}
void ans(BiTree &T, int x){
k = x;
PreOrder(T); //先序遍历x
}5.4.5.查找二叉树中两个结点的公共祖先结点
typedef struct Stack{
BiTNode *data[MAXSIZE]; //足够大的data数组
int top;
}Stack;
BiTNode* ans(BiTree T, BiTNode *p, *q){
Stakc S, Sp, Sq; //Sp和Sq分别保存p和q的祖先结点
InitStack(S); //初始化S、Sp和Sq
InitStack(Sp);
InitStack(Sq);
BiTNode *r = T, *pre; //p指向当前结点，pre指向上一个访问的结点
while (r || !IsEmpty(S)){
if (r) { //r存在，将r入栈，进入r的左子树
push(S, r);
r = r->lchild;
} else { //r不存在
GetTop(S, r); //查看栈顶元素
//栈顶元素的右孩子存在，并且上一个访问的不是该结点
if (r->rchild && r->rchild != pre) {
r = r->rchild; //r进入r的右子树
Push(S, r); //将r压入栈中
r = r->lchild; //r进入r的左子树
} else { //r的右孩子不存在或者r的右孩子是上一个访问的结点，访问该栈顶元素
pop(S, r); //弹出栈顶元素
if (r == p) { //当前元素是p，将S栈中的元素逐一复制到Sp中
for (int i = 0; i < S.top; i++) Sp.data[i] = S.data[i];
Sp.top = S.top;
}
if (r == q) { //当前元素是q，将S栈中的元素逐一复制到Sq中
for (int i = 0; i < S.top; i++) Sq.data[i] = S.data[i];
Sq.top = S.top;
}
pre = r; //用pre标记该元素
r = NULL; //将r置空
}
}//if
}//while
for (int i = Sp.top; i >= 0; i--) { //找到sp和sq中的最接近栈顶的相同元素
for (int j = Sq.top; j>= 0; j--) {
if (Sp.data[j] == Sq.data[i] return Sp.data[j];
}
}
return NULL; //无公共祖先
}5.4.6.求二叉树的宽度
typedef struct Queue{
BiTNode *data[MAXSIZE]; //足够大的数组
int front, rear;
}Queue;
int ans(BiTree T){
if (!T) return 0; //空树，返回0
BiTNode *p = T;
Queue Q;
InitQueue(Q); //初始化队列
EnQueue(Q, p); //将p入队
//rear指向当前层的最后一个结点，temp记录当前层的结点数，max记录最大结点数
int last = 0, temp = 0, max = INT_MIN;
while (!IsEmpty(Q) {
DeQueue(Q, p);
temp++; //结点数+1
if (p->lchild) EnQueue(Q, p->lchild); //p的左子树存在，左子树入队
if (p->rchild) EnQueue(Q, p->rchild); //p的右孩子存在，右孩子入队
if (last == Q.front) {
last = Q.rear; //last指向下一层的最后一个结点
if (temp > max) max = temp; //更新最大结点数
temp = 0; //结点数归零
}
}//while
return max;
}5.4.7.求二叉树的高度?
typedef struct Queue{
BiTNode *data[MAXSIZE]; //足够大的数组
int rear, front; //前后指针
}Queue;
int ans(BiTree T){
if (!T) return 0; //空树，返回0
int last = 0, level = 0; //level记录树高，last标记当前层的最后一个结点
BiTNode *p = T;
Queue Q;
InitQueue(Q); //初始化队列
EnQueue(Q, p); //根节点入队
while (!IsEmpty(Q)){
DeQueue(Q, p);
if (p->lchild) EnQueue(Q, p->lchild); //左右孩子入队
if (p->rchild) EnQueue(Q, p->rchild);
if (last == Q.front) { //该结点是本层的最后一个结点
level++; //层数+1
last = Q.rear; //指向下一层的最后一个结点
}
}//while
return level;
}int Get_High(BiTree T){
int hl, hr, maxH;
if (!T) return 0; //空树返回0
else {
hl = Get_High(T->lchild); //递归求左右子树高度
hr = Get_High(T->rchild);
maxH = max(hl, hr) + 1; //树高等于左右子树更高的那个+1
}
return maxH;
}5.4.8.排序二叉树的判定
int t = INT_MIN; //标记中序遍历上一个结点的值，初始值设为整型的最小值
bool p = true; //标记当前遍历过的所有结点是否满足排序二叉树的定义
void InOrder(BiTree T) {
if (T) {
if (T->lchild) InOrder(T->lchild);
if (T->data < t) p = false; //当前值比上一个结点更小
t = T->data; //保存当前结点的值
if (T->rchild) InOrder(T->rchild);
}
}
bool ans(BiTree T) {
InOrder(T);
if (p) return true; //该树为排序二叉树
else return false; //该树不为排序二叉树
}int A[n]; //申明一个足够大的数组
int t = 0; //标记结点个数
void InOrder(BiTree T){
if (T) {
if (T->lchild) InOrder(T->lchild);
A[t] = T->data; //保存当前节点的值
t++; //结点个数+1
if (T->rchild) InOrder(T->lchild);
}
}
bool ans(BiTree T){
InOrder(T); //中序遍历该树
for (int i = 0; i < t - 1; i++) {
if (A[i] > A[i + 1]) return false; //当前结点的值比中序序列中后一个结点更大
}
return true;
}5.4.9.平衡二叉树的判定
int GetHigh(BiTree T){
int hl, hr, maxH;
if (!T) return 0; //根节点，树高为0
hl = GetHigh(T->lchild); //递归求左子树高度
hr = GetHigh(T->rchild); //递归求右子树高度
maxH = max(hl, hr) + 1; //树高为左右子树更高的子树+1
return maxH;
}
bool IsBalance(BiTree T){
int hl, hr;
if (!T) return true; //空树为平衡二叉树
else {
hl = GetHigh(T->lchild); //求左右子树高度
hr = GetHigh(T->rchild);
if (abs(hl - hr) <= 1) {
//当前结点的左右子树满足平衡树定义，判断其左右子树
//只有其左右子树都满足平衡二叉树定义时，才返回true
return IsBalance(T->rchild) && IsBalance(T->lchild);
}
else return false; //左右子树平衡因子 > 1，非平衡二叉树
}
}5.4.10.完全二叉树的判定
typedef struct Queue{
BiTNode *p;
int front, rear;
}Queue;
bool IsComplete(BiTree T){
if (!T) return true; //空树为满二叉树
Queue Q;
InitQueue(Q); //初始化队列
BiTNode *p = T;
EnQueue(Q, p); //根节点入队
while (!IsEmpty(Q)) {
DeQueue(Q, p);
if (p) { //当前结点存在，入队左右子树
EnQueue(p->lchild);
EnQueue(p->rchild);
} else { //当前结点不存在，出队所有元素
while (!IsEmpty(Q)) {
DeQueue(Q, p);
if (p) return false; //结点非空，非完全二叉树
}
}//if
}//while
return true;
}
5.4.11.真题
int WPL = 0;
void InOrder(BiTree T, int deep){
if (T) {
if (!T->lchild && !T->rchild) { //叶子结点
WPL = WPL + T.weight * deep; //更新WPL
}
if (T->left) InOrder(T->left, deep + 1);
if (T->right) InOrder(T->right, deep + 1);
}
}
int ans(BiTree T){
InOrder(T, 0);
return WPL;
}
void InOrder(BiTree T, int deep){
if (T) {
if (deep > 1 && (T->lchild || T->rchild)) cout << '('; //分支节点打印左括号
if (T->lchild) InOrder(T->lchild, deep + 1);
cout << T->data;
if (T->rchild) InOrder(T->rchild, deep + 1);
if (deep > 1 && (T->lchild || T->rchild)) cout << ')'; //分支节点打印右括号
}
}
void ans(BiTree T){
InOrder(T, 1);
}6.图
6.1.图的数据结构定义
6.1.1.邻接矩阵
#define MAXVEX 100
typedef struct Graph {
int data[MAXVEX]; //一维数组，存放顶点数据
int edge[MAXVEX][MAXVEX]; //二维数组，存放边数据（权值）
int vexNum, edgeNum; //顶点总数和边总数
}Graph;6.1.2.邻接表
#define MAXVEX 100
typedef struct edgeNode { //边
struct edgeNode *next; //指向下一条邻接边的指针
int weight; //该邻接边权值
int adjVex; //该邻接边指向的顶点编号
}edgeNode;
typedef struct vexNode { //顶点
edgeNode *firstEdge; ///指向该顶点的第一条邻接边
int vexData; //该顶点数据
}vexNode;
typedef struct Graph { //图
int vexNum, edgeNum; //顶点数，边数
vexNode[MAXVEX]; //vexNode类型的一维数组
}Graph;6.2.图的遍历
6.2.1.深度优先遍历
#define MAXVEX 100
bool visited[MAXVEX]; //visited数组记录该顶点是否被访问过
void DFSTraverse (Graph G) {
for (int i = 0; i < G.vexNum; i++) {
visited[i] = false; //初始化visited数组
}
for (int i = 0; i < G.vexNum; i++) {
if (!visited[i]) DFS (G, i); //当前顶点未被访问过，则访问
}
}
void DFS (Graph G, int v) {
visit (v); //访问顶点v（具体操作）
visited[v] = true; //更新visited数组
for (int w = FirstNeighbor (G, v); w >= 0; w = NextNeighbor (G, v, w)){
if (!visited[w]) DFS(G, w); //递归调用DFS
}
}6.2.2.广度优先遍历
#define MAXVEX 100
Queue Q;
bool visited[MAXVEX];
void BFSTraverse (Graph G) {
for (int i = 0; i < G.vexNum; i++) { //初始化visited数组
visited[i] = false;
}
InitQueue Q; //初始化队列Q
for (int i = 0; i < G.vexNum; i++) { //遍历图
if (!visited[i]) BFS(G, i);
}
}
void BFS (Graph G, int v) {
visit(v); //访问该顶点（具体操作）
visited[v] = true; //更新visited数组
EnQueue(Q, v); //将v结点入队
int w;
while(!IsEmpty(Q)) {
DeQueue(Q, v); //队首元素出队
for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
if (!visited[w]) { //顶点未被访问过
visit(w);
visited[w] = true;
EnQueue(Q, w);
}
}//for
}//while
}6.3.单源最短路径
#define MAXVEX 100
bool visited[MAXVEX];
int dis[MAXVEX];
Queue Q;
void Min_Dis (Graph G, int v) {
for (int i = 0; i < G.vexNum; i++) { //初始化visited数组和dis数组
visited[i] = false;
dis[i] = INT_MAX;
}
visited[v] = true;
dis[v] = 0;
InitQueue(Q);
EnQueue(Q, v);
int w;
while (!IsEmpty(Q)) {
DeQueue(Q, v);
for (w = FisrtNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w) {
if (!visited[w]) {
visited[w] = true;
dis[w] = dis[v] + 1;
}
}//for
}//while
}6.4.真题
int IsExistEL(MGraph G){
int count = 0; //记录该图中度为奇数的顶点个数
int i, j;
for (i = 0; i < G.numVertices; i++){ //行遍历邻接矩阵
int degree = 0;
for (j = 0; j < G.numVertices; j++){ //列遍历当前行
if (Edge[i][j] > 0) degree++; //当前数组元素不为0，则度+1
}
if (degree % 2) count++; //当前顶点的度为奇数，count++
}
if (count == 0 || count == 2) return 1; //奇数顶点个数为0或者2，有EL路径
else return 0; //奇数顶点个数不为0或者2，没有EL路径
}7.快速排序
void QSort(int A[], L, R) { //快速排序
if (L >= R) return; //当前数组长度 <= 1，返回
随机选择数组中一元素和A[L]互换 //快排优化，使得基准元素的选取随机
int key = A[L], i = L, j = R;
while (i < j) {
while (i < j && key < A[j]) j--;
while (i < j && A[i] <= key) i++;
if (i < j) swap (A[i], A[j]); //交换A[i]和A[j]
}
swap (A[i], A[L]);
Qsort (A, L, i - 1); //递归处理左区间
Qsort (A, i + 1, R); //递归处理右区间
}8.折半查找
int Binary_Search (int A, L, R, key) {
int mid;
while (L < R) { //L >= R时，范围错误
mid = (L + R) / 2; //选择中间数，向下取整
if (key <= A[mid]) R = mid; //更新范围
else L = mid + 1;
}
if (A[mid] == key) return mid; //查找成功，返回数组下标
else return -1; //查找失败，返回-1
}