首页 > 编程语言 >数据结构-基本算法复习

数据结构-基本算法复习

时间:2023-05-18 18:25:25浏览次数:47  
标签:结点 数据结构 return 复习 int void 算法 二叉树 排序

数据结构-基本算法复习

第八章 排序

插入排序

直接插入排序:\(O(n^2)\) 稳定排序

将一条记录插入到已经排序好的有序表中:

void insertSort(int r[], int len) {
    for (int i = 2; i <= len; i++) {
        if (r[i] < r[i- 1]) {
         	int x = r[i];
            for (int j = i - 1; j >= 1 && x < r[j]; j--) {
                r[j + 1] = r[j];
            }
        	r[j + 1] = x;
        }
    }
}

折半插入排序:\(O(n^2)\) 稳定排序

用二分的方法来查找待插入的位置,但是移动次数不变,所以还是\(O(n^2)\)

void BInsertSort(int A[], int n) {
    for (int i = 2; i <= n; i++) {
        int x = A[i];
        int l = 1, r = i - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (x < A[mid]) r = mid - 1;
            else l = mid + 1;
        }
        for (int j = i - 1; j >= r + 1; j--) A[j + 1] = A[j];
        A[r + 1] = x;
    }
}

希尔排序(缩小增量排序):\(O(n^{1.3}), n \to \infty时,可减少到n(\log_2n)^2\) 不稳定排序

每一趟取间隔\(d\)进行分组,对分组内数据进行排序,二趟间隔要比第一趟间隔取得小,直到间隔为\(1\),直接进行一边插入排序。

void ShellInsert(int A[], int dk, int n) {
    for (int i = dk + 1; i <= n; i++) {
        if (A[i] < A[i - dk]) {
            int j, x = A[i];
            for (j = i - dk; j >= 1 && A[0] < A[j]; j -= dk) {
                A[j + dk] = A[j];
            }
            A[j + dk] = x;
        }
    }
}

void ShellSort(int A[], int dt[], int t) { //dt是预设好的增量
    for (k = 0; k < t; k++) {
        ShellInsert(A, dt[k]);
    }
}

交换排序

冒泡排序:\(O(n^2)\) 稳定排序

两两比较待排序记录的关键字,如果发生逆序就进行交换,从而使得关键字小的记录如起泡一样逐渐往上。

void BubbleSort(int A[], int len) {
    for (int i = 1; i <= len - 1; i++) {
        for (int j = 1; j <= len - i; j++) {
            if (A[j] > A[j + 1]) {
                swap(A[j], A[j + 1]);
            }
        }
    }
}

void sort(int a[], int len) {
 	for (int i = 0; i < len - 1; i++) {
        for (int j = 1; j < len - i - 1; j++) {
            if (A[j] > A[j + 1])
        }
    }    
}

快速排序:\(O(n\log_2n)\) 不稳定 因为不是顺次的移动

对一个区间,选取一个枢纽元\(pri\),经过一次排序后将小于\(pri\)的记录交换到前边,把所有大于\(pri\)的记录交换到后边,递归左右区间。

void quickSort(int q[], int l, int r) {
    if (l >= r) return;
    int x = q[(l + r + 1) >> 1], i = l - 1, j = r + 1;
    while (i < j) {
        do i++; while(q[i] < x);
        do j--; while(q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    
    quickSort(q, l, i - 1);
    quickSort(q, i, r);
}

void quick_sort(int q[], int l, int r) {
    if (l >= r) return;
    int x = q[(l + r + 1) >> 1], i = l - 1, j = r + 1;
    while (i < j) {
        do i++; while(q[i] < x);
        do j--; while(q[i] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, i - 1);
    quick_sort(q, i, r);
}
              
              

选择排序

直接选择排序:\(O(n^2)\) 不稳定,因为相同大小的元素会记录在后边的那个下标

从\(r[1]\)开始,通过依次往后比较,找到最小的元素与它交换,以此类推。

void SelectSort(int r[], int n) {
    for (int i = 1; i <= n; i++) {
        int k = i, j = i;
        for (j = i + 1; j <= n; j++) {
            if (r[j] < r[k]) k = j;
        }
        if (k != j) swap(r[j], r[k]);
    }
}

堆排序(树形选择排序):\(O(n log_2n)\) 不稳定排序:最简单的例子 8 2 2,小根堆调整的时候2与8交换谁都行

大根堆,小根堆,就是用的priority_queue

 void HeapAdjust(int a[], int s, int n) { //维护堆 O(logN)
	int root = a[s];
    for (int j = s * 2; j <= n; j *= 2) {
        if (j < n && a[j] < a[j + 1]) j++;
        if (root >= a[j]) break;
        a[s] = a[j];
        s = j;
    }
    a[s] = root;
}

void CreatHeap(int a[], int n) { //建堆 O(N)
    for (int i = n / 2; i > 0; i--) {
        HeapAdjust(a, i, n);
    }
}

void HeapSort(int a[], int n) {
    CreatHeap(a, n);
    for (int i = n; i > 1; i--) {
        swap(a[i], a[1]);
        HeapAdjust(a, 1, i - 1);
    }
}

归并排序:\(O(n log_2n)\) 稳定排序

int tmp[100];

void mergeSort(int q[], int l, int r) {
    if (l >= r) return;
    int mid = l + r >> 1;
    merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (q[i] <= q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
    }
    while (i <= mid) tmp[k++] = q[j++];
    while (j <= r) tmp[k++] = q[j++];
    for (int i = l, j = 0; i <= r; i++, j++) {
        q[i] = tmp[j];
    }
}

基数排序:\(O(d * (n + b))\) \(d\)是最大数字的位数也就是几次排序、\(n\)是数字个数、b是数字进制数 稳定排序

按照每一位开始排序,先根据最后一位排序,依次往前,可以用于链式结构。

外部排序

分批次调入内存排序,排好序后再调到外存,然后逐渐归并。

注意:由于内存容量的限制不能满足同时将2个归并段完全归并,只能不断的取2个归并段中每一小部分进行归并,然后不断地读数据和往外存写数据,直到归并成一个大的文件为止。

总结一下:稳定的排序有插入排序,冒泡排序,归并排序,其他的都不稳定

第七章 查找

线性表查找:

顺序查找、二分查找;

分块查找:分成\(\sqrt n\)个长度为\(\sqrt n\)的块,然后建立一个索引表,索引表存放块的起始地址和最大值,这样查找一个值的时候只需要比对最大值,即可知道在哪个块。

树表查找:

二叉排序树:每个结点的左子树的值都比他小,每个结点右子树的值都比他大。

二叉平衡树:是二叉排序树的一种,因为可能出现的极端情况是一条链,这样二叉排序树的优势会丧失;二叉平衡树是平衡因子不超过\(1\)的树,分为\(LL\)、\(RR\)、\(LR\)、\(RL\)调整。

最近不平衡点:从新插入的点顺着与根节点的那一条路径网上找最近的不平衡的点进行调整。

找到最近不平衡的点之后顺着往下找三个点进行调整:

LL:根直接向左转

RR:根直接向右转

LR:中间结点先L(左旋),根结点R(右旋)

RL:中间节点先R(右旋),根节点L(左旋)

散列表:(哈希表)

构造方法:直接哈希法、除留余数法(就是取余)、平方取中法、数字分析法(就是找出现数字频率比较少的然后随便搞一下进行哈希)。

处理冲突的方法:

(1)开放寻址法(从冲突的地方顺着往下探测,,-12,22,-2^2...;随机一个数进行)

顺序探测法:1,2,3。。顺着往下一个一个的找

二次探测法:1^2 ;-1^2; 2^2; 3^3...等等

伪随机探测法:随机一个数给他重新进行取模哈希

(2)拉链法

第六章 图

一些我自己不太熟悉的基本概念:

完全图:有\(\cfrac{n(n - 1)}{2}\)条边的图。

稠密图与稀疏图:\(e < nlog_2n\)(\(e\)为边数,\(n\)为点数),是稀疏图,反之为稠密图

图与网:带权图叫做网

简单路径:序列中顶点不重复出现的路径叫做简单路径

简单回路:除了第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路,称为简单回路简单环

连通分量是就无向图而言的,强连通分量是就有向图而言的。

图的存储方式:

邻接矩阵:好处是可以表达两点之间是否有边相连,还容易计算每个结点的度数,缺点是浪费空间,并且不便于增加和删除顶点。

邻接表:

#define MVNum 100
typedef struct ArcNode { //边结点
	int adjvex;			 //边右边相邻的点
    struct ArcNode *nextarc;	//下一条边
    OtherInfo info;
}ArcNode;

typedef struct VNode {
    VerTexType data; 	//结点的值
    ArcNode *firstarc;	//该顶点连接的第一条边
}VNode, AdjList[MVNum]; 

typedef struct {
    AdjList vertices;	//点集
    int vexnum, arcnum; //图的当前定点数和边数
}ALGraph;

图的遍历:

\(DFS:\)从某个顶点\(v\)出发,找一条路搜到底,然后回溯。

\(BFS:\)从顶点\(v\)出发,将\(v\)入队,然后一层一层的扩展即可。

最小生成树:

n - 1条边

\(Prim\) \(时间复杂度 O(n^2) \,\, 只与点有关\)(加点法,类似于\(Dijkstra\),可以用堆进行优化)。

\(Kruskal\) \(时间复杂度O(elog_2e) \,\,复杂度全在对边的排序上\)

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

struct Edge {
    int a, b, w;
}edges[N];

int main() {
    //输入 边n条 
    sort(edges, edges + n, [&](Edge A, Edge B) {
        return A.w < B.w;
    });
    for (int i = 0; i < n; i++) {
        int fa = find(edges[i].a), fb = find(edges[i].b), w = edges[i].w;
        if (fa != fb) {
            f[fa] = fb;
            res += w;
            cnt++;
        }
    }
    if (cnt < n - 1) 没有生成树
    else 输出res表示最小生成树边权和
}


最短路径

\(Dijkstra\)

原来是\(O(n^2)\),优化后是 \(O(m\log_2n) m是边数 n是结点数 往堆里插是 \log n\)

typedef pair<int, int> PII;
void Dijkstra() {
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    heap.push({0, 1});
    while (heap.size()) {
     	PII t = heap.top();
        heap.pop();
        
        int var = t.second, distance = t.first;
        if (st[var]) continue;
        st[var] = true;
       
        for (int i = h[var]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > distance + w[i]) {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }
    if (dist[n] = 0x3f3f3f3f) return -1;
    return dist[n];
}

\(Floyd\)

for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (g[i][k] != 0x3f3f3f3f && g[k][j] != 0x3f3f3f3f) {
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
            }
        }
    }
}

//初始化
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        if (i == j) g[i][j] = 0;
        else g[i][j] = 0x3f3f3f3f;
    }
}

拓扑排序

//统计入度为0的点
bool topsort() {
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (!d[i]) q.push(i); 
    }
    while (q.size()) {
        int t = q.front();
        q.pop();
        topseq[++cnt] = t;
        for (int i = h[i]; i != -1; i = ne[i]) {
            int j = e[i];
            if (!--d[j]) q.push(j);
        }
    }
    return cnt == n;
}

第五章 树和二叉树

首先学的几种树

二叉树:每个顶点最多只有两个孩子节点的树

满二叉树(完美二叉树):每一层都是最大结点数,即\(2^{i - 1}\)

完全二叉树:对二叉树从上到下,从左到右进行编号,与满二叉树编号后一一对应。

二叉排序树,平衡二叉树上边都有写

哈夫曼树:带权路径长度最小的二叉树称为最优二叉树或者哈夫曼树,这玩意就是贪心

二叉树的一些性质:

(1)二叉树第\(i\)层,最多有\(2^{i - 1}\)个结点。

(2)深度为\(k\)的二叉树,最多有\(2^k - 1\)个结点。

(3)设叶子节点数目为\(n_0\),度为\(2\)的结点为\(n_2\),那么有\(n0 = n2 + 1\)

(4)具有\(n\)个结点的完全二叉树深度为\(\lfloor \log_2n \rfloor + 1\)

存储结构

typedef struct BiTNode {
    int data;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

遍历:

前序遍历:中左右;

中序遍历:左右中;

后序遍历:左右中

一些应用:

先序遍历创建二叉树:就是先创见结点,然后递归先后左右子树即可。

复制二叉树:没啥好说的

计算二叉树深度:

int Depth(BiTree T) {
    if (T == NULL) return 0;
    else {
        n = Depth(T->lchild);
        m = Depth(T->rchild);
        if (n > m) return n + 1;
        else return m + 1;
    }
}

统计树结点个数:

int NodeCount(BiTree T) {
    if (T == NULL) return 0;
    else return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
}

线索二叉树:

拿中序线索二叉树举例:就是求出中序遍历,然后再树中让那些有空指针的结点指向它们的前驱或者后继即可。

第四章 串、数组和广义表

两种匹配算法

BF \(O(n^2)\)

无脑暴力。

KMP \(O(n + m)\)

next记录当前串的后缀与前缀,看代码

cin >> n >> p + 1 >> m >> s + 1; //p是模式串 s是原来串

for (int i = 2, j = 0; i <= n; i++) {	//求next
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j++;
   	ne[i] = j;
}

for (int i = 1, j = 0; i <= m; i++) {
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (S[i] == p[j + 1]) j++;
    if (j == n) {
        cout << "success" << "\n";
        if want to continue j = ne[j]; //if want to break
        else break;
    }
}

广义表:

有两种不同的结构(原子和列表)

举个栗子:\(D = ((), (e), (a, (bcd)))\)

GetHead(D) = ();
GetTail(D) = ((2), (a, (bcd)));

第三章 栈和队列

栈:后进先出,用于递归。

应用:

​ 括号匹配:遇到左括号入栈,遇到右括号出栈。

​ 表达式求值:准备两个栈,一个存运算符,一个存数字,遍历字符串,

​ 如果遇到字符,那么统计数字入数字栈

​ 如果遇到\('('\),那么压栈;如果遇到\(')'\),一直算到\('('\);

​ 如果是运算符,判断运算符栈顶的运算符优先级,那么先计算,再将新运算符入运算符栈

递归:

​ 斐波那契额

​ 汉诺塔

void move(char c1, int n, char c2) {
    printf("move %d from %c to %c\n", n, c1, c2);
}

void Hannoi(int n, char A, char B, char c) {
    if (n == 1) move(A, 1, C);
    else {
        Hannoi(n - 1, A, C, B); //将n-1个从A借助C移到B
        move(A, 1, C);
        Hannoi(n - 1, B, A, C);
    }
}

队列:先进先出,用于BFS。

假溢出概念:队列后边满了,但是前边是空的,所以用循环队列解决这个问题。

循环队列:

队空的条件:Q.front = Q.rear
队满的条件:(Q.rear + 1) % MAXSIZE = Q.front //尾巴追上了头

第二章 线性表

逻辑相邻,物理次序也相邻。

顺序存储:随机存取,便于查询取值,但是需要提前申请空间,存储密度大。

链式存储:便于插入和删除,只要内存够,不需要提前申请空间,可以边用边申请,存储密度为\(50\%\),浪费。

循环链表:尾巴指向头

双向链表:每个结点都可以指向它前边。

第一章 绪论

一些概念:

数据:客观事物的符号表示。

数据元素:数据基本单位,如成绩表中的一行。

数据项:如成绩表中的姓名,科目名字等等。

数据对象:性质相同的数据元素的集合,是数据的一个子集。

逻辑结构:集合、线性、树、图或网

存储结构(物理结构):顺序,链式

算法:

​ 定义:解决某一问题而规定的一个有限长的操作序列。

​ 特性:有穷性、确定性、可行性、输入、输出

​ 时间复杂度定义:

​ 算法中基本语句重复次数是问题规模\(n\)的某个函数\(f(n)\),算法的时间量度记作\(T(n) = O(f(n))\),随问题规模n增大, 算法执行时间增长率和\(f(n)\)增长率相同,称作时间复杂度。\(O\)表示数量级。

标签:结点,数据结构,return,复习,int,void,算法,二叉树,排序
From: https://www.cnblogs.com/ZhengLijie/p/17412952.html

相关文章

  • 排序算法(一):插入排序
    #author:闫振兴#datetime:2020/5/2018:14#software:PyCharm"""文件说明:"""#encoding:utf-8#插入排序:将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。#从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序......
  • Java实现输出九九乘法表—for循环和递归算法
    Java实现输出99乘法表for循环publicclassninenine{publicstaticvoidmain(String[]args){for(inti=1;i<10;i++){for(intj=1;j<=i;j++){System.out.printf("%d*%d=%d\t",j,i,j*i);}......
  • python中对列表元素大小排序(冒泡排序法,选择排序法和插入排序法)—排序算法
    前言排序(Sorting)是计算机程序设计中的一种重要操作,它的功能是将一个数据元素(或记录)的任意序列,重新排列成一个关键字有序的序列。本文主要讲述python中经常用的三种排序算法,选择排序法,冒泡排序法和插入排序法及其区别。通过对列表里的元素大小排序进行阐述。一、选择排序法选择......
  • [SEO知识讲解] 百度推出惊雷算法SEO大神100条实战经验(二)!(完结)
    本文转载自:[SEO知识讲解]百度推出惊雷算法SEO大神100条实战经验(二)!(完结)更多内容请访问钻芒博客:https://www.zuanmang.net[SEO知识讲解]百度推出惊雷算法SEO大神100条实战经验(一)接后续:四、关键词研究57、关键字是你的指南针——如果你不了解你的关键词,你不知道你的关键词......
  • [SEO知识讲解] 百度推出惊雷算法
    本文转载自:[SEO知识讲解]百度推出惊雷算法更多内容请访问钻芒博客:https://www.zuanmang.net利用点击等用户行为,来提升网站关键词排名,已经是seo行业公开的秘密。对于这个行为,百度是不会不知晓的,百度准备推出惊雷算法,来打击刷点击作弊行为,就是在这个背景下产生的。据相关渠道获悉......
  • [SEO知识讲解] 百度推出惊雷算法 SEO大神100条实战经验(一)
    本文转载自:[SEO知识讲解]百度推出惊雷算法SEO大神100条实战经验(一)更多内容请访问钻芒博客:https://www.zuanmang.net文章是老的,东西是好(经典)的。做SEO的必读!这是一篇翻译的文章,原作者是BrianDean,一个很厉害的SEO工作者。他通过自身5年的SEO工作经验总结了100个经验教训,涉......
  • 代码随想录算法训练营第九天|28. 找出字符串中第一个匹配项的下标、459. 重复的子字符
    【参考链接】28.找出字符串中第一个匹配项的下标【注意】1.kmp解决的就是字符串匹配的问题。2.kmp如何知道匹配过哪些字符串,并跳到匹配过的内容后面的字符。---前缀表3.找到一个子字符串里它的最长相等前后缀。4.前缀是包含首字母,不包含尾字母的所有子串;后缀只包含尾字母,不......
  • 八大常见的数据结构(一)数组、链表、栈、队列
    1、数组数组是用于储存有限个相同类型数据的集合。数组中的各元素的存储是有先后顺序的,它们在内存中按照这个先后顺序连续存放在一起。可通过数组名和下标进行数据的访问和更新。下标从0开始。2、链表链表是一种物理存储单元上非连续、非顺序的存储结构。链表相较于数组,......
  • 基于算法通信过程中的常用协议介绍
    基于算法通信过程中的常用协议介绍1、HTTP(HypertextTransferProtocol):HTTP是一种应用层协议,用于客户端和服务器之间的通信。它基于请求-响应模型,通过发送HTTP请求和接收HTTP响应来进行通信。HTTP协议常用于Web应用中,可以用于传输算法请求和响应数据。2、REST(Representation......
  • 基于爬山优化算法的三维曲面极值搜索matlab仿真
    1.算法仿真效果matlab2022a仿真结果如下:   2.算法涉及理论知识概要       爬山法是一种优化算法,其一般从一个随机的解开始,然后逐步找到一个最优解(局部最优)。假定所求问题有多个参数,我们在通过爬山法逐步获得最优解的过程中可以依次分别将某个参数的值增加或者......