数据结构强化篇

2024-12-19 22:22:50

文章目录

  • 1.快速排序
  • 2.划分思想
  • 3.二路归并
  • 4.链表
    • 1>使用计数器统计链表的长度
    • 2>按照关键字条件查找+删除
    • 3>按照关键字条件查找+插入
  • 5.头插法（原地逆置）
  • 6.尾插法（保持原序）
  • 7.二叉树
    • 1>前/中/后序遍历
    • 2>层序遍历
    • 3>求树的高度
    • 4>求树的宽度
    • 5->求WPL（带权路径长度）
    • 6->判定二叉排序树
    • 7->判定二叉树是否平衡
    • 8->判定完全二叉树

1.快速排序

image-20241001220352384

使用条件：必须是”顺序表“，即“数组”。乱序

快排优势：时间复杂度低，代码简洁。

image-20241001183147543
int huafen (int A[],int L,int R){
    int mid = A[L];//选择最左边的作为枢轴
    while(L<R){
        while(A[R]>=mid && L<R) R--;
        A[L]=A[R];
        while(A[L]<=mid && L<R) L++;
        A[R]=A[L];
    }
    A[L]=mid;
    return L;//返回划分的中点位置
}
void Qsort(int A[],int L,int R){
    if(L>=R) return;//递归终止
    int M=huafen(A,L,R);
    Qsort(A,L,M-1);//左半部分快排
    Qsort(A,M+1,R);//右半部分快排
}

image-20241001220305393

image-20241002181930158

11分

int huafen (int A[],int L,int R){
    int mid = A[L];//选择最左边的作为枢轴
    while(L<R){
        while(A[R]>=mid && L<R) R--;
        A[L]=A[R];
        while(A[L]<=mid && L<R) L++;
        A[R]=A[L];
    }
    A[L]=mid;
    return L;//返回划分的中点位置
}
void Qsort(int A[],int L,int R){
    if(L>=R) return;//递归终止
    int M=huafen(A,L,R);
    Qsort(A,L,M-1);//左半部分快排
    Qsort(A,M+1,R);//右半部分快排
}
int func(int A[],int N,int B[],int M){
    int C[N+M];
    for(int i=0;i<N;i++){
        C[i]=A[i];
    }
    for(int i=0;i<M;i++){
        C[i+N]=B[i];
    }
    Qsort(C,0,N+M-1);//对数组使用快排
    return C[(N+M-1)/2];//返回中位数
}
image-20241001221154811

为什么空间复杂度不是log2 (n+m)?

因为我们定义的C数组大于log 2(n+m)。

12分

image-20241004180225725

int Merge(int A[],int n,int B[],int m,int C[]){
    int i=0,j=0,k=0;
    while(i<n && j<m){
        if(A[i]<=B[j]) C[k++]=A[i++];
        else C[k++]=B[j++];
    }
    while(i<n) C[k++]=A[i++];
    while(j<m) C[k++]=B[j++];
    return 1;
}
int func(int A[],int n,int B[],int m){
    int C[n+m];
    Merge(A,n,B,m,C);
    return C[(n+m)/2];
}

Merge 操作的空间复杂度为O(n)。

一趟Merge（归并）的时间复杂度为O(n)。

image-20241001222656277

image-20241002182052160
int huafen (int A[],int L,int R){
    int mid = A[L];//选择最左边的作为枢轴
    while(L<R){
        while(A[R]>=mid && L<R) R--;
        A[L]=A[R];
        while(A[L]<=mid && L<R) L++;
        A[R]=A[L];
    }
    A[L]=mid;
    return L;//返回划分的中点位置
}
void Qsort(int A[],int L,int R){
    if(L>=R) return;//递归终止
    int M=huafen(A,L,R);
    Qsort(A,L,M-1);//左半部分快排
    Qsort(A,M+1,R);//右半部分快排
}
int func(int A[],int N){
    Qsort(A,0,N-1);
    int n=A[N/2];
    int count=0;
    //for(int i=0;i<N;i++){
    //    if(n==A[i]){
    //        count++;
    //    }
    //}//以下是王道的答案；
    for(int i=N/2;i>=0;i--){
        if(n==A[i]){
            count++;
        }
    }
    for(int i=N/2-1;i<N;i++){
        if(n==A[i]){
            count++;
        }
    }
    if(count>N/2){
        return n;
    }else{
        return -1;
    }
}

时间复杂度和空间复杂度就是快速排序的时间复杂度和空间复杂度。

image-20241002182139731

image-20241002182200506
int huafen (int A[],int L,int R){
    int mid = A[L];//选择最左边的作为枢轴
    while(L<R){
        while(A[R]>=mid && L<R) R--;
        A[L]=A[R];
        while(A[L]<=mid && L<R) L++;
        A[R]=A[L];
    }
    A[L]=mid;
    return L;//返回划分的中点位置
}
void Qsort(int A[],int L,int R){
    if(L>=R) return;//递归终止
    int M=huafen(A,L,R);
    Qsort(A,L,M-1);//左半部分快排
    Qsort(A,M+1,R);//右半部分快排
}
int func(int A[],int n){
    Qsort(A,0,n-1);
	int m =-1;
	for(int i=0;i<n;i++){
  	  if(A[i]>0){
  	      m = i;	
   	     break;
 	   }
	}
	if(m == -1) return 1;//如果m等于-1说明，数组A全都是小于0
	if(A[m] != 1) return 1;//如果能走到下一条语句，说明A[m]等于1，无须再判断
	for(m=m+1;m<n;m++){
	    if(A[m]-A[m-1]>1){
	        return A[m-1]+1;//作差后大于1，则返回小的加1
 	   }
	}
	return A[n-1]+1;//返回最后一个值加1，此时数组A所有元素均是紧挨着的
}

2.划分思想

image-20241003203436018

第K小（或第K大）可理解为，排好序之后的位置，因为数组排好序之后位置与数组下标是有对应关系的；

image-20241003203506512
int huafen (A[],int L,int R){
    int mid=A[0];//选择枢轴
    while(L<R){
        while(A[R]>=mid && L<R) R--;
        A[L]=A[R];
        while(A[L]<=mid && L<R) L++;
        A[R]=A[L];
    }
    A[L]=mid;//划分位置的值
    return L;//返回划分的位置
}
int func(int A[],int n,int K){//找到第K小的元素
    int L=0,R=n-1,M=0;
    while(1){
        M = huafen(A,L,R);
        if(M==K-1) break;
        else if(M > K-1) R=M-1;
        else if(M < K-1) L=M+1;
    }
    return A[K-1];
}

image-20241003205647049

int huafen (A[],int L,int R){
    int mid=A[0];//选择枢轴
    while(L<R){
        while(A[R]>=mid && L<R) R--;
        A[L]=A[R];
        while(A[L]<=mid && L<R) L++;
        A[R]=A[L];
    }
    A[L]=mid;//划分位置的值
    return L;//返回划分的位置
}
int func(int A[],int n,int K){//找到第K小的元素
    int L=1,R=n,M=0;
    while(1){
        M = huafen(A,L,R);
        if(M==K) break;
        else if(M > K) R=M-1;
        else if(M < K) L=M+1;
    }
    return A[K];
}

image-20241003210316211

最优解

int huafen (A[],int L,int R){
    int mid=A[0];//选择枢轴
    while(L<R){
        while(A[R]>=mid && L<R) R--;
        A[L]=A[R];
        while(A[L]<=mid && L<R) L++;
        A[R]=A[L];
    }
    A[L]=mid;//划分位置的值
    return L;//返回划分的位置
}
int func(int A[],int n){//找到第K小的元素
    int K=n/2;
    int L=0,R=n-1,M=0;
    while(1){
        M = huafen(A,L,R);
        if(M==K-1) break;
        else if(M > K-1) R=M-1;
        else if(M < K-1) L=M+1;
    }
    return A[K-1];
}

3.二路归并

image-20241004172245125

int Merge(int A[],int n,int B[],int m,int C[]){
    int i=0,j=0,k=0;
    while(i<n && j<m){
        if(A[i]<=B[j]) C[k++]=A[i++];
        else C[k++]=B[j++];
    }
    while(i<n) C[k++]=A[i++];
    while(j<m) C[k++]=B[j++];
    return 1;
}

Merge 操作的空间复杂度为O(n)。

一趟Merge（归并）的时间复杂度为O(n)。

二路归并中，共需要log2n趟，故时间复杂度为O(nlog2n)

image-20241008205001162

4.链表

1>使用计数器统计链表的长度

//定义单链表结点
typedef struct LNode{
    int data;
    struct 	LNode* next;
}LNode, *LinkList;
//求单链表长度
int listLen(LinkList L){
    int length=0;
    LNode *p=L->next;
    while (p!=NULL){
        length++;
        p=p->next;
    }
    printf("链表的长度 = %d \n",length);
    return length;
}
//返回单链表的中间结点
int findMidNode(LinkList L){
    int length=0;
    LNode *p=L->next;
    while (p!=NULL){
        length++;
        p=p->next;
    }
    int count=0;//计数器
    p= L->next;//让p指向头节点的下一个节点，（从头开始遍历）
    while(p!=NULL){
        if(count == lengtj/2) break;//找到中间结点，跳出循环
        p=p->next;//指向下一个结点
    }
    p=p->next;
    return p;
}

image-20241005204647391

//求单链表长度
int listLen(LinkList L){
    int length=0;
    LNode *p=L->next;
    while (p!=NULL){
        length++;
        p=p->next;
    }
    return length;
}
//返回指针类型
LinkNode *Find_1st_Common(LinkList str1,LinkList str2){
    int len1=listLen(str1),len2=listLen(str2);
    LinkNode *p,*q;
    for(p=str1;len1>len2;len1--) //使 p 指向的链表与 q 指向的链表等长
    	p=p->next;
    for(q=str2;len1<len2;len2--) //使 q 指向的链表与 p 指向的链表等长
   		q=q->next;
    while(p->next!=NULL&&p->next!=q->next){//查找共同后缀起始点
        p=p->next; //两个指针同步向后移动
        q=q->next;
    }
    return p->next; //返回共同后缀的起始点
}

2>按照关键字条件查找+删除

image-20241005204826499

//删除值为X的结点
int deletX(LinkList L,int x){
    LNode *pre = L;  //pre指向p的前驱节点
    LNode *p =pre ->next;//指向pre的下一个结点
    while(p!=NULL){
        if(p->data==x){
            LNode *q = p;//释放值为x的结点
            pre->next = p->next;//删除节点，修改指针
            free(q);
        }else{
            pre = p;//两个指针同时移动
            p= p->next;
        }
    }
}

3>按照关键字条件查找+插入

在这里插入图片描述

void InsertX(LinkList L,int x){
    LNode *pre = L;
    LNode *p = pre->next;
    while (p!=NULL){
        if(p->data >x){
            break;
        }
上一篇：Docker Compose ：轻松管理多容器应用

下一篇：Servlet学习中遇到的一些问题及解决