Data Structure Algorithm

数据结构算法

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.2.入栈

bool Push(Stack &S, int key) {
    if (S.top == MAXSIZE - 1) return false;    //栈满
    S.data[++top] = key;
    return true;
}

3.2.3.出栈

bool Pop (Stack &S, int &key) {
    if (S.top == -1) return false;    //栈空
    key = S.data[top--];
    return true;
}

3.2.4.判断栈空

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
}