王道考研编程题总结

我还在完善中，边复习边完善（这个只是根据我自身总结的）

一、线性表

1. 结构体

#define MaxSize 40
typedef struct{ElemType data[MaxSize]；int length;
}SqList

2. 编程题

1. 删除最小值

题意：从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删函数的值，空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行。
思路：搜索整个顺序表，查找最小值元素并记住其位置，搜索结束后用最后一个元素填补空出的原最小值元素的位置。

【注意】：别忘了边界条件和线性表长度要－1，因为属于改变线性表内容，所以传进去的是地址

bool Delete(SqList &L, ElemType &x) //此处不能用int,因为不明确是啥类型
{/*1. 判断是否为空2. 删除最小值，若线性表只有一个数，则返回3. 用最后一个位置填补空出的位置*/if(L.length == 0) return false;int ElemType = L.data[0];int pos = 0;for(int i = 1; i < L.length; i ++){if(L.data[i] < x){x = L.data[i];pos = i;}}L.length --;//if(L.length == 0) return true; 该步可以不用要（不需要太注意题目未提的边界）L.data[pos] = L.data[L.length];return true;
}

2. 元素逆置

void Reverse(SqList &L)
{int l = 0, r = L.length-1;while(l < r){int temp = L.data[l];L.data[l] = L.data[r];L.data[r] = temp;r --; l ++;}
}

3. 删除所有值为x的数

别忘了更新长度，以及&符

/*
用cnt统计值不为x的数字的个数，当遍历到某数（值不为x）时，将其移动到线性表中表cnt-1的位置。
*/void Delete_x(SqList &L, int x)
{int cnt = 0;for(int i = 0; i < L.length; i ++){if(L.data[i] != x){cnt ++;L.data[cnt-1] = L.data[i];}}L.length = cnt; //不要忘了更新长度
}

5. 删除所有值重复的元素

题目已说是有序的

/*
与第三题的思想一致
用cnt记录未重复的元素的个数
初始时视第一个数为不重复的数，从左向右移动，若该数与前一个数不相同，则可视为不重复的数。
若该数为第cnt个不重复的数，则将其插入到数组中的第cnt个位置上
*/void DisSame(SqList &L)
{int cnt = 1;for(int i = 1; i < L.length; i ++){if(L.data[i] != L.data[i-1]){cnt ++;L.data[cnt-1] = L.data[i];}}L.length = cnt; //不要忘了更新长度
}

10. 数组的循环左移

/*
法一，利用公式i=(i-p+n)%n(需要开辅助数组)
正解：翻转三次
*/void Reverse(int a[], int l, int r)
{for(int i = 0; i < (r-l+1)/2; i ++) //不是等于（利用正数第i与倒数第i的思想）{int temp = a[r-i];a[r-i] = a[l+i]a[l+i] = temp;}
}void LeftMove(int a[], int n, int p)
{Reverse(a, 0, p-1);Reverse(a, p, n-1);Reverse(a, 0, n-1);
}

二、链表

1. 结构体

typedef struct LNode
{ElemType data;struct LNode *next;
}LNode, *LinkList;

2. 基础用法

要注意的地方

定义完一个指针后(LNode *q)

如果需要给它赋值（即需要使用空间）

需要这样做

q = (LNode*)malloc(sizeof(LNode));

1. 初始化

bool InitList(LinkList &L)
{L = (LNode*)malloc(sizeof(LNode)); //创建头结点L->next = NULL;return true;
}

2. 头插法

//头插法建立单链表（倒序）
void HeadInsert(LinkList &L)
{LNode *q; int x;int n; scanf("%d", &n);for(int i = 0; i < n; i ++){scanf("%d", &x);q = (LNode*)malloc(sizeof(LNode));q->data = x;q->next = L->next;L->next = q;}
}

3. 尾插法

//尾插法（正序）
void TailInsert(LinkList &L)
{LNode *q, *p; int x;p = L;int n; scanf("%d", &n);for(int i = 0; i < n; i ++){scanf("%d", &x);q = (LNode*)malloc(sizeof(LNode)); //这步不能省，要赋值的指针就需要开空间q->data = x;p->next = q;p = q;}p->next = NULL;
}

3. 编程题

1. 找中间结点

算法思想：设置两个指针p和q,指针p每次走一步，指针q每次走两步，当指针q到达链尾时，指针p恰好在链表的中间结点

【注意】最后可能不足两步，故要看临界条件

void work(LNode *h)
{LNode *p, *q;//寻找中间结点p = q = h;while(q->next != NULL){p = p->next; //p走一步q = q->next;if(q->next != NULL) q = q->next; //q走两步}
}

17. 找倒数第k个位置的结点

/*
算法思想
指针p先向前走k步走到第k个结点时，令指针q指向头结点，随后让指针p和指针q同时向后走，
当指针p走到尾时，指针q所指向的结点即为倒数第k个位置的结点
当指针p还未走到第k个结点就到链表尾，则返回0
*/bool Find(LinkList L, int k)
{LNode *p, *q;p = q = L;for(int i = 0; i < k; i ++){p = p->next;if(!p) return 0;}while(p != NULL){p = p->next;q = q->next;}printf("%d", q->data);return 1;
}

2. 将某段链表逆置

利用头插法的思想

题目：将一个链表（已经插好的）进行逆置

void reverse(LNode *h)
{LNode *p = h->next; //p指向链表的第一个结点，同时也是逆转后的最后一个结点if(p == NULL) return ;LNode *q = p->next;while(q != NULL){p->next = q->next; //将q摘下q->next = h->next;h->next = q; //将q插入头结点q = p->next; //更新}
}

18. 公共后缀的起始位置

要注意，主函数中，传的参数是指针，返回的也是指针类型

/*
算法思想：
指针p、q分别指向两个单词所在链表的头节点，遍历一遍链表，分别得到两个链表的长度，
假设一个链表比另一个链表的长度长k,那么指向该链表的指针先向前移动k步，之后同步遍历两个链表，
当p、q指向的结点为同一结点时，该结点即为第一个公共结点。
*//*
要注意，主函数中，传的参数是指针，返回的也是指针类型
*///求链表长度的函数
int GetLen(LNode *p)
{int len = 0;while(p->next != NULL){len ++;p = p->next;}return len;
}SNode *Find(LNode *str1, LNode *str2)
{int m = 0, n = 0; //两个链表的长度LNode *p = str1->next, *q = str2->next;m = GetLen(str1);  //求链表长度n = GetLen(str2);for(int i = m; m > n; m --) //若m>n,移动p指针p = p->next;for(int i = n; n > m; n --) //若n>m，移动q指针q = q->next;while(p != q && p != NULL) //寻找共同后缀的起始地址{p = p->next;q = q->next;}return p;
}

19. 去掉绝对值重复的结点

注意：

1. 题目需要给出数据类型定义

2. struct node *link; //题目要求用link,故此处不能用data

3. 删除结点时，要释放结点空间

free(q); //释放该结点的空间

/*
算法思想：
该算法使用空间换时间的思想，开一个大小为n+1的数组a;各元素的初值为0.从头一次扫描链表
中的各结点。同时检查a[|data|]的值，若为0则保留该结点，并令a[|data|]=1；否则将该结点
从链表中删除
*/
typedef struct LNode
{int data;struct node *link; //题目要求用link,故此处不能用data
}LNode;void work(LNode *h, int n) //头指针和数值范围是已经给出的，放在函数传参里即可
{int a[n + 1];LNode *p = h， *q;while(p->next != NULL){int x = p->next->data;if(x < 0) x = -x; //绝对值if(a[x] == 0) //该绝对值未出现过a[x] = 1;else //该绝对值出现过，则删除该结点{q = p->next;p->next = q->next;free(q); //释放该结点的空间}}
}

20. 重新交叉排列

【考察知识点】

1. 寻找中间结点

2. 将一段结点逆置

算法思想：

（1）先找出算法L的中间结点，为此设置两个指针p和q,指针p每次走一步，指针q每次走两步，当指针q到达链尾时，指针p恰好在链表的中间结点

（2）利用头插法将L的后半段结点原地逆置

（3）将后半段的结点按照题目要求依次插入前半段结点中

void work(LNode *h)
{LNode *p, *q, *r, *s;//寻找中间结点p = q = h;while(q->next != NULL){p = p->next; //p走一步q = q->next;if(q->next != NULL) q = q->next; //q走两步}q = p->next; //p为中间结点，q为后半段头结点//开始逆置while(q->next != NULL){r = q->next;q->next = r->next; //摘下r->next = p->next;p->next = r;}q->next = NULL;//将后半段结点插到前半段s = h->next; //s指向前半段的第一个结点q = p->next;while(q != NULL){p->next = q->next;q->next = s->next;s->next = q;s = q->next;q = p->next;}
}

三、栈

四、队列

五、括号序列

六、树

1. 结构体

typedef struct BiTNode{ElemType elem;  //数据域struct BiTNode *lchild, *rchild; //左、右孩子
}BiTNode, *BiTree;

2. 递归遍历

先序

void PreOrder(BiTree T)
{if(T != NULL){visit(T);PreOrder(T->lchild);PreOrder(T->rchild);}
}

中序

void PreOrder(BiTree T)
{if(T != NULL){PreOrder(T->lchild);visit(T);PreOrder(T->rchild);}
}

后序

void PreOrder(BiTree T)
{if(T != NULL){PreOrder(T->lchild);PreOrder(T->rchild);visit(T);}
}

3. 非递归遍历

需要用到栈

先序遍历

void PreOrder2(BiTree T)
{BiTree p = T;InitStsck(S);while(!Empty(S) || p){if(p){visit(p);Push(S, p); //保留p是为了之后探索它的右孩子p = p->lchild;}else{Pop(s, p);p = p->rchild;}}}

中序遍历

中序遍历和先序遍历的思想是一样的，只是改变了访问的结点的位置

void InOrder2(BiTree T)
{BiTree p = T;InitStsck(S);while(!Empty(S) || p){if(p){Push(S, p); //保留p是为了之后探索它的右孩子p = p->lchild;}else{//此时已经遍历完左子树了，才能访问根节点Pop(s, p);visit(p); p = p->rchild;}}}

4. 层次遍历

（1）上到下，左到右

void LevelOrder(BiTree T)
{BiTree p; //用来接收队头InitQueue(Q);EnQueue(Q, T);while(!IsEmpty(Q)){DeQueue(Q, p);visit(p);if(p->lchild != NULL) EnQueue(Q, p->lchild);if(p->rchild != NULL) EnQueue(Q, p->rchild);}}

（2）下到上，右到左

算法思想：利用原有的层次遍历算法，出队的同时将各结点指针入栈，在所有的结点入栈后再从栈顶开始依次访问结点

void InvertLevel(BiTree T)
{InitQueue(Q);InitStack(S);EnQueue(Q, T);BiTree p;while(IsEmpty(Q) == false){DeQueue(Q, p); //注意，不是p = Dequeue(Q);Push(S, p); //出队，入栈if(p->lchild)EnQueue(Q, p->lchild);if(p->rchild)EnQueue(Q, p->rchild);}//自下而上，从右到左的层次遍历while(IsEmpty(S) == false){Pop(S, p); //注意，不是p = Pop(S);visit(p->data); //遍历的是值}
}

5. 求二叉树高度

(1) 递归

int GetGigh(BiTree T)
{if(T == NULL) return 0;int lhigh = GetHigh(T->lchild);int rhigh = GetHigh(T->rchild);int high =  1 + (lchild > rchild ? lchild : rchild);return high;
}

(2)非递归

有点难度

P168

算法思想：采用层次遍历算法，设置变量level来记录当前结点所在的层数，设置变量last指向当前层的最右结点，每次层次遍历出队时队头指针与last比较，若相等，则lever加一，并让last指向下一层的最右结点，即当前的队尾结点，直到遍历完成，level即为二叉树的高度

注意事项

此处因为需要用到队尾元素，所以用的是数组队列

数组队列存的是结点，所以类型应为BiTree

int GetHigh(BiTree T)
{int level = 0; //记录高度int last = 0; //记录当前层的最右结点int front = -1, rear = -1; //队头和队尾指针BiTree Q[MaxSize]; //队列类型为结点Q[++rear] = T;BiTree p;while(IsEmpty(Q) == false) //队列不为空时{p = Q[++front];if(p->lchild)Q[++rear] = p->lchild; //左孩子入队if(p->rchild)Q[++rear] = p->rchild; //右孩子入队   if(last == front) //处理该层的最右结点；{level ++;last = rear;}}return level;
}

6. 判断是否是完全二叉树

算法思想：采用层次遍历算法，遇到空节点时，查看其后是否有非空节点（不需要遍历完所有结点,当某层结点都为空时，自然没有后代），若有，则二叉树不是完全二叉树

void InvertLevel(BiTree T)
{InitQueue(Q);EnQueue(Q, T);BiTree p;while(IsEmpty(Q) == false){DeQueue(Q, p); //注意，不是p = Dequeue(Q);if(p){EnQueue(Q, p->lchild);EnQueue(Q, p->rchild);}else //遇到空结点{while(IsEmpty(Q) == false) //判断队列中的剩余结点是否都为空{DeQueue(Q, p);if(p) return false;}}}return true;
}

7. 统计双分支结点个数

法一：递归遍历+全局变量

法二：递归遍历，但不用全局变量

 int Work(BiTree T)
{if(T == NULL) return 0; //别忘了空节点也要有返回值   if(T->lchild && T->rchild) //自身是双分支结点return (Work(T->lchild) + Work(T->rchild)) + 1;elsereturn Work(T->lchild) + Work(T->rchild);
}

8. 将树中所有结点的左右结点交换

算法思想：采用后序递归算法，对于b结点，先交换b结点左孩子的左右子树，再交换b结点右孩子的左右子树，最后再交换b结点的左右孩子

[注意]：交换的时候要链表一样防止链接丢失

void Work(BiTree T)
{if(T != NULL){Work(T->lchild);Work(T->rchild);//交换三部曲BiTree temp = T->lchild;T->lchild = T->rchild;T->rchild = temp;}
}

9. 求先序遍历中第k个结点的值

难点：返回时要一层一层递归返回

方法：使用全局变量来记录是否已经找到该值，并将该值记录在全局变量中

【当不知道要记录的值的类型时，用EmemType来赋值】

int flag = 0; //是否找到第k个数
ElemType ans; //记录该结点数据（当不知道类型时，用英文）
int res = 0; //res为当前遍历的数的序号
int Work(BiTree T, int k)
{if(flag == 1) return ans;res ++;if(res == k){flag = 1; //找到了；ans = T->data;return ans;}if(T->lchild) Work(T->lchild, k); //只遍历存在的结点if(T->rchild) Work(T->rchild, k);
}

10. 删除子树

题目：对于树中每个元素值为x的结点，删除以它为根的子树，并释放相应的空间

1. 删除子树使用后序遍历，因为要先删完子孙后代再删自身

2. 释放内存用free();

3. Work函数之所以写得比较复杂是因为：

值为x的结点的父亲在删完子树后，需要指向NULL,所以通过父亲来判断孩子的值是否为x;

void Delete(BiTree &bt) //删除以bt为根的子树//注意，传入的是地址
{if(bt){Delete(bt->lchild);Delete(bt->rchild);free(bt);}
}void Work(BiTree T, ElemType x)
{if(!T) return ;if(T->data == x)Delete(T);else{if(T->lchild->data == x) //孩子值为x，删掉，并将孩子位置换成NULL{Delete(T->lchild);T->lchild = NULL;}elseWork(T->lchild, x);if(T->rchild->data == x){Delete(T->rchild);T->rchild = NULL;}elseWork(T->rchild, x);}
}

11. 求非空二叉树宽度

宽度：具有结点数最多的那一层

可以利用第五题：非递归求高度的思想求最大宽度

当last == front时，cnt = rear - front;

ans = max(ans, cnt);

12. 知先序求后序

题目：设有一棵满二叉树，已知其先序序列为pre(字符串)，设计一个算法求其后序序列post。

对于一般二叉树而言，仅根据先序或后序序列，不能确定另一个遍历序列。但对于满二叉树，可以确定

可以自己画画，很容易找规律，使用递归

#include<stdio.h>void work(char pre[], int l, int r)
{if(l == r) {printf("%c", pre[l]);return ;}work(pre, l+1, l+(r-l)/2);work(pre, l+(r-l)/2+1, r);printf("%c", pre[l]);
}int main()
{char pre[100] = "01245367";work(pre, 1, 7);return 0;
}

13. 将叶节点连成单链表

题目：将二叉树的结点按从左到右的顺序连成一个单链表，表头指针为head,二叉树按二叉链表方式存储，链接时用叶结点的右指针域来存放单链表指针

算法思想：使用先序遍历遍历到的叶节点的顺序就是从左到右的，故用pre指针记录前一个叶节点即可。

LinkList head, pre = NULL;
LinkList Work(BiTree T)
{if(T){if(T->lchild==NULL && T->rchild==NULL){if(pre == NULL){head = L;pre = L;}else{pre->rchild = T;pre = T;}}Work(T->lchild);Work(T->rchild);}return head;
}

七、图

对于默认图（即不带权），在邻接矩阵中，如两点之间存在边，则g[a][b]=1.否则为0

1. 出度大于入度的顶点个数

算法思想：在邻接矩阵中，对于每个顶点，其所在行中1的个数为该顶点对应的出度，其所在列1的个数为该顶点对应的入度。因此可以枚举每个顶点，用count1记录出度，用count2记录入度，用ans来记录K顶点的个数，当count1>count2时，输入该顶点，ans加一。最后返回ans的值。

int printVertices(MGraph G)
{int ans = 0; //K顶点个数for(int i = 0; i < G.numVertices; i ++) //枚举顶点{int count1 = 0; //记录出度int count2 = 0; //记录入度for(int j = 0; j < G.numVertices; j ++) //对行count1 += G.Edge[i][j]);for(int j = 0; j < G.numVertices; j ++) //对列count2 += G.Edge[j][i])if(count1 > count2) {printf("%c ", G.VerticesList[i]);ans ++;}}return ans;
}

八、查找

1. 折半查找

#define MaxSize 40
typedef struct{
ElemType data[MaxSize]；
int length;
}SqList

题目：写出折半查找的递归算法(要写递归的二分), low为1， high为ST.length(对线性表操作)

//自己定义线性表
#define MaxSize 40
typedef struct{ElemType data[MaxSize]；int length;
}SqListint find(int a[], int low, int high, int x)
{int pos;int mid = (low + high)/2;if(ST.data[mid] > x) pos = find(a, low, mid-1, x);else if(ST.data[mid] < x)pos = find(a, mid+1, high, x);else pos = mid;return pos;
}

2. 矩阵查找

算法思想：从矩阵A的右上角即第一行的最后一列的那个元素开始比较，若当前元素小于目标值，则向下移动一行，若当前元素大于目标值，则向左移动一列，若当前元素等于目标值，则返回true,如果移动的过程越界了，说明矩阵中不存在该目标值，返回false。

九、并查集

初始化操作

void Init(int p[])
{for(int i = 0; i < SIZE; i ++)p[i] = i;
}

1. 压缩路径

改进了Find操作

int find(int p[], int x)
{if(x != p[x]) p[x] = find(p[x]);return p[x];
}

十、图

1. 与二叉树不一样（树没有环），dfs和bfs遍历图需要用visit[ ]来记录该结点是否访问过，防止重复访问

书本p227

2. BFS求解单元最短路问题时需要用d[ ]来记录当前距离

d[ ]要初始化为无穷大

3. 知道图怎么存就可以写题了，那些扩展都在搜索图的基础上进行的