数据结构强化篇

news/2024/12/19 18:52:40/

文章目录

  • 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全都是小于0if(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;}else{pre = p;p = p->next;}}LNode *q= (LNode *)malloc(sizeof(LNOde));//等价与LinkList q = (LinkList)malloc(sizeof(*q));q->data = x;q->next=p;pre->next = q;
}

image-20241006200828063

typedef struct LNode{int data;struct LNode* next;
}LNode,*LinkList;// 函数功能:删除链表中绝对值重复出现的节点,只保留第一次出现的节点
void Del(LinkList L,int n){// 遍历链表,将负数节点的值取绝对值LNode *p = L;while (p!=NULL){if(p->data <0){p->data = -p->data; }p = p->next;}// 创建辅助数组,用于标记已出现的绝对值int a[n + 1] = {0};// prev 用于指向当前节点的前一个节点LNode *prev = NULL;// 重新将 p 指向链表头节点,开始处理链表p = L;while (p!=NULL){// 获取当前节点值的绝对值int Data = p->data;if (a[Data] == 0) {// 如果该绝对值第一次出现// 将辅助数组中对应位置标记为已出现a[Data] = 1;// prev 指向当前节点prev = p;// p 指向下一个节点,继续遍历p = p->next;} else {// 如果该绝对值不是第一次出现// 将当前节点存储在 toDelete 中,准备删除LNode *toDelete = p;// p 指向下一个节点,继续遍历p = p->next;if (prev!= NULL) {// 如果当前节点不是头节点,将 prev 的 next 指针指向当前节点的下一个节点prev->next = p;} else {// 如果当前节点是头节点,更新头指针L = p;}// 释放要删除的节点的内存空间free(toDelete);}}
}

5.头插法(原地逆置)

image-20241008192516462

1493b4f6e2da4a3fa5ea5fdcdeacb08

void ListReserve(LinkList L){//分配一个辅助头结点LinkList head = (LNOde *) malloc (sizeof(LNOde));head->next = NULL;while (L->next != NULL){LNode *p = L->next; //按顺序拆下每个结点L->next = L->next->next;p->next = head->next;//头插法head->next = p;//将头结点链接到第一个元素}L->next = head->next;//将逆置好的链表链接回原链表free(head);//释放辅助头结点
}

6.尾插法(保持原序)

image-20241008195132262

LinkList A;//用于尾插法
LinkList B;//用于头插法
void func(LinkList C){//分配A、B两个头结点A = (LNode *) malloc(sizeof(LNode));A->next = NULL;LNode *tailA = A;//tailA 一直指向A的链尾B = (LNode *)malloc(sizeof(LNode));B->next = NULL;int count =1;while(C-next != NULL){LNode *p =C-next;//按照顺序拆下每个结点;指向C的第一个元素C->next = C->next->next;if(count %2==1){//原序tailA->next = p;//将新的结点链接到尾结点p->next = NULL;//将尾结点执指向NULLtailA = p;//尾指针移动到新的尾结点}else{//逆序p->next = B->next;//头插法B->next = p;}count++;}
}

image-20241008204748125

7.二叉树

image-20241009193926662

1>前/中/后序遍历

image-20241009203247432

//二叉树的结点定义(链式存储)
typedef struct BiTNode {int data;struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//此处可写对根节点的操作
void visit(BiTree T, int level) {if (T!= NULL) {printf("节点 %d 在第 %d 层\n", T->data, level);}
}// 计算平衡因子的辅助函数
int getBalanceFactor(BiTree T) {if (T == NULL) {return 0;}int leftHeight = treeHeight(T->lchild);int rightHeight = treeHeight(T->rchild);return leftHeight - rightHeight;
}
// 前序遍历
void preOrder(BiTree T,int level) {if (T == NULL) {return;}int BalanceFactor= getBalanceFactor(T);visit(T, level);//访问根节点,结点所在层数printf("输出平衡子:%d",BalanceFactor);if(BalanceFactor >1 or BalanceFactor <-1) return 1preOrder(T->lchild,level + 1);//遍历左子树preOrder(T->rchild,level + 1);//遍历右子树
}// 中序遍历
void inOrder(BiTree T,int level) {if (T == NULL) {return;}inOrder(T->lchild,level + 1);visit(T, level);inOrder(T->rchild,level + 1);
}// 后序遍历
void postOrder(BiTree T,int level) {if (T == NULL) {return;}postOrder(T->lchild,level + 1);//左postOrder(T->rchild,level + 1);//右visit(T, level);
}

2>层序遍历

image-20241015195811845

image-20241015194514608

注意:更容易靠简答题;如果考算法题直接使用辅助队列即可

//二叉树的结点定义(链式存储)
typedef struct BiTNode{int data;//数据域struct BiTNode *lchild,*rchild;//左、右孩子指针
}BiTNode,*BiTree;//层序遍历
void LevelOrder(BiTree T){Queue Q;InitQueue(Q);//辅助函数(初始化辅助队列)BiTree p;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);//右孩子入队}}
}

3>求树的高度

image-20241015201436240

image-20241015202137084

//二叉树的结点定义(链式存储)
typedef struct BiTNode {int data;struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
// 求二叉树的高度
//方法一(先序遍历的改版)
int height =0;
void PreOrder (BiTree,int n){if(T==NULL) return;if(n>height) height=n;//更新树的高度PreOrder(T->lchild,n+1);//遍历左子树PreOrder(T->rchild,n+1);//遍历右子树
}
//方法二
int treeHeight(BiTree T) {if (T == NULL) {return 0;}int leftHeight = treeHeight(T->lchild);int rightHeight = treeHeight(T->rchild);return (leftHeight > rightHeight? leftHeight : rightHeight) + 1;//找到最大的然后加1;(加1是,加上根节点)
}

4>求树的宽度

image-20241016190024645

image-20241016190001908

//二叉树的结点定义(链式存储)
typedef struct BiTNode {int data;struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//使用先序遍历统计,同时各层结点总数
int width[MAX];//用于统计各层结点总数
void ProOrder(BiTree T,int level){if(T==NULL) return;width[level]++;//累加该层节点总数ProOrder(T->lchild,level+1);//遍历左子树ProOrder(T->rchild,level+1)//遍历右子树
}
//求树的宽度
void treeWidth(BiTree T){for(int i=0;i<MAX;i++)width[i]=0;ProOrder(T,0);//先序遍历二叉树,统计各层结点总数int maxWidth = 0;//最大宽度for(int i=0;i<MAX;i++){if(width[i] > maxWidth)maxWidth = width[i];}printf("树的宽度是%d",maxwidth);
}

5->求WPL(带权路径长度)

image-20241016193651266

image-20241016193711732

//二叉树的结点定义(链式存储)
typedef struct BiTNode {int weight;struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
int WPL=0;
//先序遍历
void PreOrder(BiTree T,int level){if(T == NULL) return;//处理,如果是叶子节点,叶子节点的权值乘以层数if(T->lchild == NULL&&T->rchild == NULL){WPL += level*T->weight; //累加叶结点带权路径长度}PreOrder(T->lchild,level + 1);//遍历左子树PreOrder(T->rchild,level + 1);//遍历右子树
}

6->判定二叉排序树

image-20241021221131478

//二叉树的结点定义(链式存储)
typedef struct BiTNode {int weight;struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;int temp = MIN_INT;
bool isBST=true;
void InOrder(BiTree T){if(T == NULL) return;InOrder(T-lchild);if(T->data >= temp) temp = T->data;else isBST = false;InOrder(T->rchild);
}

7->判定二叉树是否平衡

image-20241021224728746

//二叉树的结点定义(链式存储)
typedef struct BiTNode {int weight;struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;bool isBalance = true;
int PostOrder(BiTree T){if(T == NULL) return 0;int left = PostOrder(T->lchild);int right = PostOrder(T->rchild);if(left-right > 1) isBalance = false;if(left-right < -1) isBalance = false;//树的深度=MAX(左子树深度-右子树深度) + 1if(left > right) return left +1;else return right +1;
}

8->判定完全二叉树

image-20241022224726892

image-20241022224821177

image-20241022224914794

想象层序遍历的过程:出队一个元素,入队该元素的所有孩子结点

:在完全二叉树中,一旦出现了叶子节点或者只有左孩子的分支节点,那么后续的节点必须都是叶子节点,不能再有有孩子的节点。

//二叉树的结点定义(链式存储)
typedef struct BiTNode{int data;//数据域struct BiTNode *lchild,*rchild;//左、右孩子指针
}BiTNode,*BiTree;//层序遍历
void LevelOrder(BiTree T){Queue Q;InitQueue(Q);//辅助函数(初始化辅助队列)BiTree p;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);//右孩子入队}}
}bool isComplete = true; //是否为完全二叉树
bool flag = false;  //flag = true,表示层序遍历时出现过叶子或只有做孩子的分支节点void visit(BiTNode *p){//既没有左孩子也没有右孩子,还不能判断不是完全二叉树if(p->lchild == Null && p->rchild ==NULL)  flag = true;if(p->lchild == Null && p->rchild !=NULL)  isComplete = false;//只有右孩子没有左孩子,直接判定不是完全二叉树if(p->lchild != NULL && p->child == NULL){  //有左无右if(flag) isComplete = false;  //如果flag=true说明之前出现了叶子节点,此时可直接判定不是完全二叉树flag = true;  //否则此结点可能为完全二叉树}if(p->lchild != NULL && p->rchild != NULL){  //有左有右if(flag)  isComplete = false;  //如果flag=true说明之前出现了叶子节点,此时可直接判定不是完全二叉树}
}

http://www.ppmy.cn/news/1556454.html

相关文章

R语言函数简介

【图书推荐】《R语言医学数据分析实践》-CSDN博客 《R语言医学数据分析实践 李丹 宋立桓 蔡伟祺 清华大学出版社9787302673484》【摘要 书评 试读】- 京东图书 (jd.com) R语言医学数据分析实践-R语言的数据结构-CSDN博客 R语言中的函数&#xff08;function&#xff09;是一…

前端成长之路:HTML(4)

前文提到&#xff0c;在HTML中&#xff0c;表格是为了展示数据&#xff0c;表单是为了提交数据。表单标签是十分重要的标签&#xff0c;在网页中&#xff0c;需要和用户进行交互&#xff0c;收集用户信息等&#xff0c;此时就需要使用表单。表单可以将前端收集到的用户输入的信…

Flutter-Web首次加载时添加动画

前言 现在web上线后首次加载会很慢&#xff0c;要5秒以上&#xff0c;并且在加载的过程中界面是白屏。因此想在白屏的时候放一个加载动画 实现步骤 1.找到web/index.html文件 2.添加以下<style>标签内容到<head>标签中 <style>.loading {display: flex;…

Linux-设备树

一、设备树 设备树(Device Tree)&#xff0c;将这个词分开就是“设备”和“树”&#xff0c;描述设备树的文件叫做 DTS(Device Tree Source)&#xff0c;这个 DTS 文件采用树形结构描述板级设备&#xff0c;也就是开发板上的设备信息&#xff0c;比如CPU 数量、 内存基地址、I…

MySQL 实战:小型项目中的数据库应用(二)

小型项目里 MySQL 的安全与性能管理 用户权限管理 在小型项目中&#xff0c;合理的用户权限管理对于保障 MySQL 数据库的安全性至关重要。MySQL 的权限系统有着细致的层级划分和丰富的权限类型&#xff0c;能让管理员精确控制不同用户对数据库的访问与操作能力。 首先是权限…

智能算法驱动:中阳科技量化交易模型的革新之路

在金融智能化和自动化浪潮中&#xff0c;中阳科技率先以量化交易模型为核心&#xff0c;构建高效的投资生态&#xff0c;成为智能交易领域的领导者。本文将深入剖析中阳科技在模型设计、数据整合、技术创新以及未来发展策略中的核心优势&#xff0c;为读者展示其领先的技术应用…

基于 Spring Boot + Vue 的宠物领养系统设计与实现

引言 近年来&#xff0c;随着人们生活水平的提高&#xff0c;宠物逐渐成为许多家庭的重要成员。然而&#xff0c;宠物的流浪和弃养问题日益严重&#xff0c;这促使社会对宠物领养的需求不断增长。为解决宠物领养中信息不对称、领养流程复杂等问题&#xff0c;设计并实现一个基…

Django+React---从0搭建一个听音乐+聊天室的网站

文档、网站、Github地址&#xff1a; 需要梯子&#xff1a; 写开发文档的时候&#xff0c;用的就是Colab(ipython)&#xff0c;不太好转过来&#xff0c;所以这里就放个链接吧&#xff1a;Dev Note Colab 不需要梯子&#xff1a; Github地址&#xff08;有的时候需要梯子&…