408数据结构学习强化——常见数据结构定义和算法总结
1.数组2.链表3.栈4.队列5.树6.图7.排序8.查找
·
目录
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数组
int count = 0;
for (int i = 0; i < n; i++) {
if (A[i] > 0 && A[i] <= n){ //当前数组元素为正，并且在数组B的下标范围内
count = A[i];
B[count] = true;
}
}
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]为基准元素，ij为左右指针
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); //快速排序
int i = 0;
while (A[i] <= 0) i++; //找到数组中第一个大于0的元素
if (n == i) return 1; //数组中没有元素大于0，返回1
else {
if (A[i] != 1) return 1; //第一个整数不是1，则返回1
else { //第一个整数为1，找到数组中正整数第一个间断点
int j = i + 1;
while (j < n) {
if (a[j] == a[j - 1]) j++; //相邻元素相等
else if (a[j] == a[j - 1] + 1) j++; //相邻元素是连续数
else return A[j - 1] + 1; //相邻元素是间断点
}//while
}//else
}//else
}
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.将链表排序
LNode *Sort(LinkList L) {
LNode* p = (LNode*)malloc(sizeof(Lnode));
p->next = NULL;
LNode* t = L->next, * tpre = L, *min, *minpre, *r = p;
int m = INT_MAX;
while (t) {
while (t) { //遍历链表
if (t->data < m) { //更新最小值结点
min = t;
minpre = tpre;
m = t->data;
}//if
tpre = t;
t = t->next;
}//while
minpre->next = min->next; //将min从L中删除
r->next = min; //将min插入p
r = min; //r后移
m = INT_MAX; //重新初始化
t = L->next;
tpre = L;
}//while
r->next = NULL;
return p;
}2.3.4.拆分链表
LNode* (LinkList &L) {
LNode *p = (LNode*)malloc(sizeof(LNode);
p->next = NULL; //p为新链的头结点
LNode *q = L->next, *t = NULL, *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 ans(LinkList L) {
LNode* post = L->prior, * pre = L->next; //前后指针
//表中元素为奇数时，终止条件为两者移动到同一结点
//表中元素为偶数时，终止条件为两者后指针的next指向前指针
while (post != pre && post->next != pre) {
if (post->data != pre->data) return false; //前后指针的指针域不相等
pre = pre->next; //前指针前移
post = post->prior; //后指针后移
}
//表对称
return true;
}bool ans(LinkList L) {
LNode* p = L->next;
int len = 0; //记录表中的元素个数
while (p != L) {
p = p->next;
len++;
}
int a = (int*)malloc(len * sizeof(int)); //定义跟链表结点个数相等的长度的数组
len = 0;
p = L->next
while (p != L) { //遍历链表，用数组保存链表中每个结点的值
a[len] = p->next;
p = p->next;
}
//遍历数组，前后指针指向元素的值不相等，返回false
for (int i = 0, j = len - 1; i < j; i++, j--) {
if (a[i] != a[j]) return false;
}
return true;
}2.3.9.依次输出链表中结点值最小的元素
void DeleteMin(LinkList &L) {
LNode *p = L->next, *ppre = L->next, *min, *minpre;
while (L->next != L) {
p = L->next;
ppre = L;
int tempMin = INT_MAX; //当前最小值
while (p != L) {
if (p->data < tempMin) { //当前结点值更小，更新最小结点
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;
}
void ans(LinkList str1, LinkList str2) {
LNode *p = str1->next, *q = str2->next;
int len1 = 0, len2 = 0;
while (p) { //遍历str1，得到str1的长度
len1++;
p = p->next;
}
while (q) { //遍历str2，得到str2的长度
len2++;
q = q->next;
}
int len = abs(len1 - len2); //得到两表长度之差
p = str1->next; //重置pq指向第一个结点
q = str2->next;
if (len1 >= len2) { //长表向前移动，使得两表剩余元素相等
for (int i = 0; i < len; i++) p = p->next;
}
else {
for (int i = 0; i < len; i++) q = q->next;
}
while (p) { //遍历剩余结点，找到两者指向的第一个共同结点
if (p == q) return p;
p = p->next;
q = q->next;
}
return NULL; //两者没有共同后缀
}
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(NODE *L) {
NODE* p = L->next, *f = L->next, *s = L->next, *q, *t;
while (f->next->next && f->next) { //找到前半链的最后一个结点
f = f->next->next; //快指针移动两个结点
s = s->next; //慢指针移动一个结点
}
q = s->next; //q指向后半链的第一个结点
s->next = NULL; //前半链后半链断开
LNode* post = (NODE*)malloc(sizeof(NODE));
post->next = NULL;
while (q) { //后半链逆置
t = q->next;
q->next = post->next;
post->next = q;
q = t;
}
q = post->next; //q指向逆置后的后半链的第一个结点
while (q) {
r = q->next; //r指向后半链的下一个结点
t = p->next; //t指向前半链下一个插入位置
q->next = p->next;
p->next = q;
q = r; //重置pq
p = t;
}
}
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 T[MAXSIZE]; //申明一个长度为MAXSIZE的TreeNode数组
InitTree(T); //初始化树
...
}5.1.3.双亲表示法
#define MAXSIZE 100 //树中最多结点数
typedef struct TreeNode{
int data; //结点数据
int parent; //该结点的双亲结点在数组的下标
}TreeNode;
typedef struct Tree{
TreeNode T[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 T[MAXSIZE]; //定义一个长度为MAXSIZE的树
5.1.5.孩子兄弟表示法
#define MAXSIZE 100
typedef struct CSNode{
struct CSNode *firstChild, *nextSibling; //指向第一个孩子和右兄弟节点
int data; //该结点数据
}CSNode;
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);
}
}typedef struct Stack{
BiTNode *Node[MAXSIZE];
int top;
}Stack;
void PostOrder(BiTree T){
Stack S;
InitStack(S);
BiTNode *p, *pre;
while (p || !IsEmpty(S)）{
if (p) { //往左下走到尽头
Push(p); //p入栈
p = p->lchild; //进入其左子树
} else {
GetTop(S, p); //查看栈顶元素
//栈顶元素的右孩子存在，并且不是上一个访问的结点
if (p->rchild && p->rchild != pre) {
p = p->rchild; //进入栈顶元素的右子树
Push(p); //该结点入栈
p = p->lchild; //进入该结点左子树
} else { //栈顶元素的右孩子被访问过
Pop(S, p); //弹出栈顶元素
visit(p); //访问该结点
pre = p; //用pre标记该结点
p = NULL; //将p置空
}//if
}//if
}//whil
}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]; //递归寻找直到该结点的值为负数（该树的根节点）
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 PreOrder(BiTree T){
if (T) {
//当前结点的左右孩子都存在，count++
if (T->lchild && T->rchild) count++;
if (T->lchild) PreOrder(T->lchild); //递归遍历左子树
if (T->rchild) Preorder(T->rchild); //递归遍历右子树
}
void ans(BiTree T) {
PreOrder(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;
if (T->data == x) { //根节点的值为x，删除整个树并返回
Delete(T);
return;
} else PreOrder(T); //先序遍历x
}void Delete(BiTree &T) { //后序遍历，并删除结点
if (T) {
Delete(T->lchild);
Delete(T->rchild);
free(T);
}
}
void LevelOrder(BiTree &T, int x){
if (T->data == x) { //根节点的值为x，删除整个树，并返回
Delete(T);
return;
}
Queue Q;
InitQueue(Q); //初始化队列
BiTNode *p = T;
EnQueue(Q, p); //根节点入队
while (!IsEmpty(Q)) {
DeQueue(Q, p);
if (p->lchild) {
if (p->lchild->data == x) {
BiTNode *q = p->lchild;
p->lchild = NULL; //左孩子指针置空
Delete(q); //以q为根节点的子树
} else EnQueue(Q, p);
}
if (p->rchild) { {}
if (p->rchild->data == x) {
BiTNode *q = p->rchild;
p->rchild = NULL;
Delete(q);
} else EnQueue(Q, p);
}
}//while
}5.4.5.查找二叉树中两个结点的公共祖先结点
BiTNode *ans(BiTree ROOT, BiTNode *p, BiTNode *q) {
Stack S, Sp, Sq; //Sp和Sq分别用来保存p和q的祖先结点
S.top = -1; //初始化队列
BiTNode* t = ROOT, *pre = NULL;
while (t || S.top >= 0) {
if (t) { //t结点非空
S.data[++S.top] = t; //t结点入队
t = t->lchild; //进入t的左子树
}
else { //t结点为空
t = S.data[S.top]; //查看栈顶元素
//t的右子树存在，并且上一个访问的并不是其右子树
if (t->rchild && t->rchild != pre) {
t = t->rchild; //进入右子树
S.data[++S.top] = t; //入栈该结点
t = t->rchild; //进入左子树
}
else { //右子树不存在，或者存在但是上一个访问的是右子树
S.top--; //出栈该结点，并访问
if (t == p) { //当前结点为p，保存栈中内容，即其所有祖先结点
for (int i = 0; i < S.top; i++) Sp.data[i] = S.data[i];
Sp.top = S.top;
}
if (t == q) { //当前结点为q，保存栈中内容，即其所有祖先结点
for (int i = 0; i < S.top; i++) Sq.data[i] = S.data[i];
Sq.top = S.top;
}
}//if
}//if
}//while
//自栈顶到栈顶分别遍历Sp和Sq找到最接近栈顶的相同祖先结点
for (int i = Sp.top; i >= 0; i--) {
for (int j = Sq.top; i >= 0; j--) {
if (Sp.data[i] == Sq.data[j]) return Sp.data[i];
}
}
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指向当前层的最后一个结点，count记录当前层的结点数，max记录最大结点数
int last = Q.rear, count = 0, max = INT_MIN;
while (!IsEmpty(Q) {
DeQueue(Q, p);
count++; //结点数+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 (count > max) max = temp; //更新最大结点数
count = 0; //结点数归零
}
}//while
return max;
}typedef struct Queue { //足够大的非循环数组
BiTNode *data[MAXSIZE]; //结点数组，保存每个结点
int level[MAXSIZE]; //层数数组，记录每个结点的层数
int front, rear; //头尾指针
}Queue;
int ans(BiTree T) {
BiTNode* p = T;
Queue Q;
Q.rear = Q.front = 0; //初始化队列
if (T) {
Q.data[Q.rear] = T; //根节点入队
Q.level[Q.rear] = 1;
Q.rear++;
while (Q.front < Q.rear) {
p = Q.data[Q.front]; //出队队首元素
int level = Q.level[Q.front]; //保存当前结点的层数
Q.front++;
if (p->lchild) { //左孩子入队
Q.data[Q.rear] = p->lchild;
Q.level[Q.rear] = level + 1;
Q.rear++;
}
if (p->rchild) { //右孩子入队
Q.data[Q.rear] = p->rchild;
Q.level[Q.rear] = level + 1;
Q.rear++;
}
}//while
int max = INT_MIN, i = 0, level = 1;
while (i <= Q.rear) {
int count = 0; //记录当前层的结点数
while (i <= Q.rear && level == Q.level[i]) {
count++;
i++;
}
if (count > max) max = count; //更新每层的最大结点数
level = Q.level[i]; //更新层数，while循环结束时，i指向下一层的第一个结点
}//while
return max; //返回最大结点数
}
else return 0; //空树，返回0
}5.4.7.求二叉树的高度
int Get_Heigh(BiTree T) {
int front = 0, rear = 0; //前后指针
BiTNode* p = T;
BiTNode *data[MAXSIZE]; //足够大的队列，元素是二叉树结点
data[rear++] = p; //根节点入队
int last = rear, level = 0; //rear标记本层最后一个结点, level记录当前层数
while (front < rear) { //循环直到队空
p = data[front++]; //出队队首结点
if (p->lchild) data[Q.rear++] = p->lchild; //左右孩子入队
if (p->rchild) data[Q.rear++] = p->rchild;
if (last == front) { //当前结点为本层的最后一个结点
last = rear; //标记下层的最后一个结点
level++; //层数+1
}
}//while
return level;
}int Get_High(BiTree T){
if (!T) return 0; //空树返回0
else {
int hl = Get_High(T->lchild); //递归求左右子树高度
int hr = Get_High(T->rchild);
int maxH = max(hl, hr) + 1; //树高等于左右子树更高的那个+1
return maxH;
}
}5.4.8.排序二叉树的判定
int pre = INT_MIN; //标记上一个结点的值，初始值为INT类型的最小值
int JudgeBST(BiTree T) {
if (!T) return 1; //空树，是排序二叉树
else {
int l = JudgeBST(T->lchild); //判断左子树
//当前值小于等于pre的值，或左子树不满足排序二叉树定义，返回0
if (T->data <= pre|| l == 0) return 0;
pre = T->data; //更新pre为当前结点值
int r = JudgeBST(T->rchild); //判断右子树
return r;
}
}int A[n]; //足够大的数组，保存每个节点的值
int count = 0; //记录结点个数
void InOrder(BiTree T) {
if (T) {
InOrder(T->lchild);
A[count++] = T->data; //记录当前结点值，并且count+1
InOrder(T->rchild);
}
}
bool ans(BiTree T) {
if (!T) return true; //空树为排序二叉树
else if (!T->lchild && !T->rchild) return true; //只有根节点，是排序二叉树
else {
InOrder(T); //中序遍历二叉树，并且记录每个结点的值
for (int i = 0; i < count - 1; i++) {
if (A[i] >= A[i + 1]) return false; //非排序二叉树
}
return true; //排序二叉树
}
}5.4.9.平衡二叉树的判定
int Get_Height(BiTree T) {
if (!T) return 0;
else {
int hl = Get_Height(T->lchild); //递归求左子树高度
int hr = Get_Height(T->rchild); //递归求右子树高度
int maxH = max(hl, hr) + 1; //树高为左右子树更高的那个 + 1
return maxH;
}
}
bool JudgeBalance(BiTree T) {
if (!T) return true; //空树为平衡二叉树
else {
int hl = Get_Height(T->lchild); //左子树高度
int hr = Get_Height(T->rchild); //右子树高度
//当前结点的左右平衡因子小于等于1，递归判断其左右子树是否满足平衡二叉树
if (abs(hl - hr) <= 1) {
return JudgeBalance(T->lchild) && JudgeBalance(T->rchild);
}
//当前节点左右平衡因子大于1，则已不满足平衡二叉树，无需判断左右子树，返回false
else return false;
}
}5.4.10.完全二叉树的判定
①采用层次遍历的思想，与一般层次遍历的区别是空结点也能入队
②当出队元素为空时（设该结点为P），进入内层循环（即③），逐一出队并检查该结点是否为空。
③若队中剩余元素有不为空的结点，则说明P之后还有结点（这个结点可能是与P同层，或是P的下一层）即不满足完全二叉树的定义；若队中剩余元素皆为空结点，说明P是该树的最后一个结点（最底层的最右结点），满足完全二叉树的定义
bool JudgeComplete(BiTree T) {
BiTNode* data[MAXSIZE]; //足够大的队列
int front = 0, rear = 0; //头尾指针
BiTNode* p = T;
data[rear++] = T; //根节点入队
while (front < rear) { //循环直到队空
p = data[front++]; //出队队首元素
if (p) { //p结点存在，入队左右孩子
data[rear++] = p->lchild;
data[rear++] = p->rchild;
}
else { //p结点不存在，出队剩余元素
while (front < rear) {
p = data[front++];
if (p) return false; //当前元素为非空，则为非完全二叉树
}
}
}
return true;
}5.4.11.真题
int WPL = 0;
void InOrder(BiTree T, int deep){
if (T) {
if (!T->left && !T->right) { //叶子结点
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;
}int Get_WPL(BiTree root) {
BiTNode* data[MAXSIZE]; //足够大的非循环数组
BiTNode* p = root;
int f = 0, r = 0, level = 0, WPL = 0, last = 0;
data[r++] = p; //根节点入队
last = r; //last标记本层的最后一个元素
while (f < r) {
p = data[f++]; //队首元素出队
//该结点为叶子结点，计算WPL
if (!p->lchild && !p->rchild) WPL = WPL + level * p->weight;
if (p->lchild) data[r++] = p->left; //左右孩子入队
if (p->rchild) data[r++] = p->right;
if (last == f) { //该结点为本层的最后一个结点
last = r; //更新last和level
level++;
}
}
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 vex[MAXVEX]; //vexNode类型的一维数组vex
}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
}
华为开发者空间，是为全球开发者打造的专属开发空间，汇聚了华为优质开发资源及工具，致力于让每一位开发者拥有一台云主机，基于华为根生态开发、创新。
更多推荐
63
0- 0
已为社区贡献4条内容
所有评论(0)