算法-查找

线性表的查找

顺序查找

线性表的顺序查找

1
2
3
4
5
6
7
8
9
10
11
12
13
//不考虑链式，其实本质相同，默认元素不重复
typedef int ElemType;
typedef struct{ //查找表的数据结构
    ElemType *elem; //元素存储空间基址，建表时实际长度分配，0号单元留空
    int TableLen;   //表的长度
}SSTable;
//ST.elem[0]为哨兵元素，存储待找元素
int Search_Seq(SSTable ST,ElemType key){
    ST.elem[0] = key;
    int index;
    for(index=ST.TableLen;ST.elem[index]!=key;--index){}
    return index;   //返回数组下标
}

有序表的顺序查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//不考虑链式，其实本质相同，默认元素不重复
typedef int ElemType;
typedef struct{ //查找表的数据结构
    ElemType *elem; //元素存储空间基址，建表时实际长度分配
    int TableLen;   //表的长度
}SSTable;
int Search_SeqOrderly(SSTable ST,ElemType key){
    ST.elem[0] = key;
    int index;
    for(index=ST.TableLen-1;ST.elem[index]!=key;--index){
        if(ST.elem[index]<key){
            return -1;//从后往前，找到比key小还没找到，说明没有
        }
    }
    return index;   //返回数组下标，-1则没有
}

折半查找

有序表的折半查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//只有有序表才能够进行折半查找，不考虑元素重复
typedef int ElemType;
typedef struct{ //查找表的数据结构
    ElemType *elem; //元素存储空间基址，建表时实际长度分配
    int TableLen;   //表的长度
}SSTable;
int Binary_Search(SSTable ST,ElemType key){
    int low = 0;
    int high = ST.TableLen-1;
    int mid;
    while(low<=high){
        mid = (low+high)/2;
        if(ST.elem[mid] == key){
            return mid;
        }else if(ST.elem[mid] > key){
            high = mid - 1;
        }else{
            low = mid + 1;
        }
    }
    return -1;  //上面没有return，则找不到
}

分块查找

局部有序表的折半查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//局部有序，说明索引块之间的最大值是有序的，索引块内部可以无序
typedef struct{ //查找表的索引
    ElemType max; //该索引块中的最大值
    int index;  //索引块的第一个下标
    int IndexLen;   //索引块的长度
}SSTableIndex;
typedef struct{ //查找表的数据结构
    ElemType *elem; //元素存储空间基址，建表时实际长度分配
    int TableLen;   //表的长度
    SSTableIndex *Tableindex; //索引表,存储空间基址，建表时实际长度分配
    int TableIndexLen;   //索引表的长度
}SSTable;
int Block_Search(SSTable ST,ElemType key){
    int indexblock = 0;
    //第一步寻找key可能所在的分块
    while(indexblock<ST.TableIndexLen-1 && ST.Tableindex[indexblock].max<key){  //如果已经是最后一块了，则不用往下找
        indexblock++;
    }
    for(int i=0;i<ST.Tableindex[indexblock].IndexLen;i++){
        if(ST.elem[i+ST.Tableindex[indexblock].index==key]){
            return i+ST.Tableindex[indexblock].index;
        }
    }
    return -1;  //上面没有返回，则没有找到，返回-1
}

查找的应用

字符串匹配

简单的模式匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//C语言，自行封装String
typedef struct{
    char *elem;
    int length; //String长度
}String;
int findStringIndex(String main,String key){
    int i=0,j=0;
    while(i<main.length&&j<key.length){
        if(main.elem[i]==key.elem[j]){
            i++;
            j++;
        }else{
            j=0;
            i=i-j+1;
        }
    }
    if(j==key.length){
        return i-j;  //说明已经找到
    }else{
        return -1;  //说明没有找到
    }
}

改进的模式匹配——KMP算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//求next数组
void get_next(String key,int next[]){
    int i =0;
    int j=-1;   //说明正在匹配第一个
    next[0] = -1;
    while(i<key.length){
        if(j==-1||key.elem[i]==key.elem[j]){
            i++;
            j++;
            next[i]=j;
        }else{
            j=next[j];
        }
    }
}
int KMP(String main,String key,int next[],int pos){
    //求Key在main中第pos个字符后的位置
    int i = pos-1;
    int j = -1; //说明正在匹配第一个
    while(i<main.length&&j<key.length){
        if(j==-1||main.elem[i]==key.elem[j]){
            i++;
            j++;
        }else{
            j=next[j];
        }
    }
    return 0;
}

展开全文 >>

算法-排序

线性表的排序

各种排序算法性能比较

希尔排序需要根据步伐大小决定,基数排序需要r个队列,d趟分配和收集

算法种类 最好情况 平均情况 最坏情况 空间复杂度 是否稳定
直接插入排序 O(n) O(n^2) O(n^2) O(1) 是
冒泡排序 O(n) O(n^2) O(n^2) O(1) 是
简单选择排序 O(n^2) O(n^2) O(n^2) O(1) 否
希尔排序 O(1) 否
快速排序 O(nlog2(n)) O(nlog2(n)) O(n^2) O(nlog2(n)) 否
堆排序 O(nlog2(n)) O(nlog2(n)) O(nlog2(n)) O(1) 否
2-路归并排序 O(nlog2(n)) O(nlog2(n)) O(nlog2(n)) O(n) 是
基数排序 O(d(n+r)) O(d(n+r)) O(d(n+r)) O(r) 是

插入排序

直接插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//时间复杂度为o(n^2),count为待排序数组大小,假设从小到大排序
void InsertSortDir(ElemType number[],int count){
    int current;    //从第1个开始，扔到current前面进行排序
    int change=0;
    int changenumber;
    for(current=1;current<count;current++){
        if(number[current]>number[current-1]){ //如果比前面大，则这次已经在正确位置上，不必插入，跳过
            while(change<current&&number[change]<number[current]){
                change++;   //找到待插入元素
            }
            changenumber = number[current];
            for(int j=change+1;j<=current;j++){  //交换后面的位置
                number[j]=number[j-1];
            }
            number[change] = changenumber;  //插入待插入元素
            change = 0;
        }
    }
}

折半插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//时间复杂度为o(n^2),count为待排序数组大小,假设从小到大排序
void InsertSortRed(ElemType number[],int count){
    int current;    //从第1个开始，扔到current前面进行排序
    int change=0;
    int changenumber;
    for(current=1;current<count;current++){
        if(number[current]>number[current-1]){ //如果比前面大，则这次已经在正确位置上，不必插入，跳过
            int low = 0,high = current-1;
            int mid = 0;
            while(low<=high){//查找方式变为折半
                mid = (low+high)/2;
                if(number[mid]>number[current]){
                    high = mid-1;
                }else{
                    low = mid+1;
                }
            }
            change = mid;   //待插入元素位置
            changenumber = number[current];
            for(int j=change+1;j<=current;j++){  //交换后面的位置
                number[j]=number[j-1];
            }
            number[change] = changenumber;  //插入待插入元素
            change = 0;
        }
    }
}

希尔插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//对于希尔排序，前后记录增量为dk,不为1,len为步长
void ShellSort(ElemType number[],int count,int len){
    int change = 0;
    int changenumber = 0;
    for(int dk=len/2;dk>=1;dk=dk/2){
        for(int i = dk;i<2*dk;i++){
            if(number[i]<number[i-dk]){ //相等，则在正确的位置上
                while(change<i&&number[change]<number[i]){
                    change+=dk;   //找到待插入元素
                }
                changenumber = number[i];
                for(int j=change+dk;j<=i;j+=dk){  //交换后面的位置
                    number[j]=number[j-dk];
                }
                number[change] = changenumber;  //插入待插入元素
                change = i-dk;
            }
        }
    }
}

交换排序

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//时间复杂度为o(n^2)，举例从后往前升序冒泡
void BubbleSort(ElemType number[],int count){
    int i=0;
    int temp=0;
    bool changed=true;
    while(i<count&&changed){
        changed=false;  //本趟排序默认没发生交换
        for(int j=count-1;j>i;j--){ //从前往后则j=0;j<count-i-1;j++，然后比较j与j+1
            if(number[j]<number[j-1]){
                changed = true;
                temp = number[j];   //交换元素
                number[j]=number[j-1];
                number[j-1]=temp;
            }
        }
        i++;
    }
}

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//时间复杂度为o(log2(n))
int Pratition(ElemType number[],int low,int high){
    ElemType pivot = number[low];   //将第一个元素作为轴,这个可以任意,不同情况下取轴可不同
    while(low<high){
        while(low<high&&number[high]>=pivot){
            high--; //将比pivot小的元素放在右侧
        }
        //跳出，说明number[high]<pivot，需要把其放在左侧
        number[low]=number[high];   //第一次的low被记录在pivot里，后续的low记录在前一次的high中
        while(low<high&&number[low]<=pivot){
            low++;
        }
        //跳出,说明number[low]>pivot,需要放在右侧
        number[high]=number[low];   //上一次的high已经存入low，可以直接替换
    }
    number[low]=pivot;  //放回其正确位置
    return low;
}
void QuickSort(ElemType number[],int low,int high){
    if(low<high){
        int pivotpos=Pratition(number,low,high);    //划分，其中pivotpos左侧小于其值，右侧大于，pivotpos为正确的位置
        QuickSort(number, low, pivotpos-1);
        QuickSort(number, pivotpos+1, high);
        
    }
}

选择排序

简单选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//时间复杂度为o(n^2),依次找出最小或最大的
void SelectSort(ElemType number[],int count){
    int minindex = 0;
    int temp = 0;
    for(int i=0;i<count;i++){
        minindex = i;
        for(int j=i+1;j<count;j++){
            if(number[j]<number[minindex]){ //找到最小的那个
                minindex = j;
            }
        }
        temp = number[i];
        number[i]=number[minindex];
        number[minindex] = temp;
    }
}

堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//向下调堆,用于大顶堆
void AdjustDown(ElemType number[],int i,int count){
    int temp = number[i];
    for(int j=2*i+1;j<count;j=2*j+1){   //沿着交大打子节点向下筛选
        if(j+1<count&&number[j]<number[j+1]){   //取左右子节点交大的一个
            j++;
        }
        if(temp>number[j]){ //父节点大于所有子节点，不需要改变
            break;
        }else{  //否则交换位置
            number[i]=number[j];    //大的一个子节点，放在父节点位置，小的父节点下移
            i=j;    //即现在判断的新父节点，为刚刚降下来的那个子节点位置，向下寻找新的次大值
        }
    }
    number[i]=temp;  //最终位置放入开始判断的那个值
}
//在堆栈中删除元素，即将删除的元素与堆底对换，然后向下调整一次替换元素位置
//向上调堆,用于向堆栈中插入元素
void AdjustUp(ElemType number[],int i,int count){
    int temp = number[i];
    int j = (i+1)/2;    //j为i的父亲节点
    while(j>=0&&number[j]<temp){    //父节点比子节点小，父节点下移
        number[i]=number[j];    //子节点被父节点替代
        i=j;
        j = (i+1)/2;    //继续往上调
    }
    number[j]=temp; //找到正确位置
}
//建立大顶堆
void BuildMaxHeap(ElemType number[],int count){
    for(int i=count/2;i>=0;i--){ //从i=[n/2]~1反复调整堆，此为父节点数量
        AdjustDown(number,i,count);
    }
}
//时间复杂度为o(nlog2(n)),堆用数组记录,从number[0]开始记录,每次排序获得最大值
void HeapSort(ElemType number[],int count){
    BuildMaxHeap(number, count);
    int temp = 0;
    //每次number[0]都是当前排序最大的值，放入倒数便可
    for(int i=1;i<count-1;i++){
        temp = number[0];
        number[0] = number[count-i];
        number[count-i] = temp;
        //新堆只有堆顶元素混乱，其他有序，只要向下排一次便可
        AdjustDown(number, 0, count-i);
    }
}

归并排序

2-路归并排序的递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
int count;  //数组大小
ElemType *numbertemp = (ElemType *)malloc((count+1)*sizeof(ElemType));  //辅助数组，用于存结果
void Merge(ElemType number[],int low,int mid,int high){
    //number[low~mid]与number[mid~high]各自有序，现在进行归并
    for(int i=low;i<high;i++){
        numbertemp[i] = number[i];
    }
    int i=low,j=mid+1;
    int k=low;
    while(i<mid&&j<=high){
        if(numbertemp[i]<numbertemp[j]){
            number[k] = numbertemp[i];
            i++;
            k++;
        }else{
            number[k] = numbertemp[j];
            j++;
            k++;
        }
    }
    while (i<=mid) {    //左侧没有复制完
        number[k]=numbertemp[i];
        k++;
        i++;
    }
    while (j<=high) {    //右侧没有复制完
        number[k]=numbertemp[j];
        k++;
        j++;
    }
}
//时间复杂度为o(nlog2(n)),此处的hign为最后一个元素下标
void MergeSort(ElemType number[],int low,int high){
    if(low<high){
        int mid = (low+high)/2; //从中间划分成2个子序列
        MergeSort(number, low, mid);    //递归左侧
        MergeSort(number, mid+1, high); //递归右侧
        Merge(number,low,mid,high); //进行归并
    }
}

展开全文 >>

数据结构-图

图

图的存储

图的顺序存储-邻接矩阵法-数据结构

1
2
3
4
5
6
7
8
9
10
//顺序存储，将所有的点根据矩阵按序存入
#define MaxVertexNum 100 //定义顶点数量的最大值
typedef char VertexType;    //定义顶点的数据类型
typedef int EdgeType;   //带权图边上的权值的数据类型
typedef struct{
    VertexType Vex[MaxVertexNum];   //顶点表
    //A[i][j]表示边，为0则没有联通，为1则联通，其他数则为其权值
    EdgeType Edge[MaxVertexNum][MaxVertexNum];    //边表
    int vexnum,arcnum;  //记录图的当前顶点数与弧数
}MGragh;

图的链式存储-邻接表法-数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//邻接表法类似树的孩子兄弟表示法，有顶点表，和一串与该顶点相连的链表
#define MaxVertexNum 100 //定义顶点数量的最大值
typedef char VertexType;    //定义顶点的数据类型
typedef int EdgeType;   //带权图边上的权值的数据类型
typedef struct ArcNode{ //边表结点
    int adjvex; //该弧指向的顶点位置
    struct ArcNode *next;   //指向下一条弧的指针
}ArcNode;
typedef struct VNode{   //邻接表
    VertexType data;    //顶点信息
    ArcNode *first; //指向第一条依附于该顶点的边的指针
}VNode,AdjList[MaxVertexNum];   //顶点表与顶点结点
typedef struct{
    AdjList vertices;   //邻接表，顶点表
    int vexnum,arcnum;  //记录图的当前顶点数与弧数
}ALGraph;   //ALGraph是以邻接表存储的图类型

图的链式存储-十字链表法-数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//用于表示有向图，十字链表法是邻接矩阵法的拓展，相当于增加了边的前后驱，能更快的遍历相同入度或相同出度的边
#define MaxVertexNum 100 //定义顶点数量的最大值
typedef char VertexType;    //定义顶点的数据类型
typedef int EdgeType;   //带权图边上的权值的数据类型
typedef string InfoType;    //边信息的数据类型
typedef struct ArcNode{ //边表结点
    int tailvex,headvex;    //该弧的头尾结点
    ArcNode *hlink,*tlink;  //分别指向弧头相同和弧尾相同的结点
    InfoType info;  //边相关信息
}ArcNode;
typedef struct VNode{   //顶点表结点
    VertexType data;    //顶点信息
    ArcNode *firstin,*firstout; //指向第一条入弧和出弧
}VNode,GLlist[MaxVertexNum];
typedef struct{
    //VNode GLlist[MaxVertexNum];  //邻接表
    GLlist GLlist;  //邻接表
    int vexnum,arcnum;  //图的顶点数和弧数
}GLGraph;   //GLGraph是以邻接表存储的图类型

图的链式存储-邻接多重表法-数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//用于表示无向图，与有向图的十字链表法类似
#define MaxVertexNum 100 //定义顶点数量的最大值
typedef char VertexType;    //定义顶点的数据类型
typedef int EdgeType;   //带权图边上的权值的数据类型
typedef string InfoType;    //边信息的数据类型
typedef struct ArcNode{ //边表结点
    bool mark;  //访问标记
    int ivex,jvex;  //分别指向该弧的两个结点
    ArcNode *ilink,*jlink;  //分别指向两个顶点的下一条边
    InfoType info;  //相关边的信息
}ArcNode;
typedef struct VNode{   //顶点表结点
    VertexType data;    //顶点信息
    ArcNode *firstedge; //指向第一条依附该顶点的边
}VNode,Adjmulist[MaxVertexNum];
typedef struct{
    Adjmulist adjmulist;    //邻接表
    int vexnum,arcnum;  //图的顶点数和弧数
}AMLGraph;
more >>

展开全文 >>

数据结构-树和森林

树

树的存储

树的顺序存储-双亲表示法

1
2
3
4
5
6
7
8
9
10
11
12
//双亲表示法是使用一组连续的空间来存储每个结点，同时每个结点增设一个伪指针为数组下标，表示其父亲的位置
#define MaxSize 100  //树中最多结点数
typedef struct{    //树的结点定义
    ElemType data;  //数据元素
    int parent; //双亲位置，数组下标，父亲唯一，所有该值唯一
}PTNode;
typedef struct{
    PTNode nodes[MaxSize];  //存储所有的结点，相当于树的顺序存储
    int n;  //结点数
}PTree;

树的链式存储-孩子表示法

1
2
3
4
5
6
7
8
9
10
11
12
13
//孩子表示法，将所有结点存入数组内。这种方法寻找双亲需要遍历所有结点。每个结点含有的1个指向
typedef struct CNode{
    int index;  //该孩子在结点表中的数组下标
    CNode *nextchild;  //指向下一个孩子
}CNode;
typedef struct{
    ElemType data;  //数据域
    CNode *child;   //指向其第一个孩子
}CMNode;
typedef struct{
    CMNode nodes[MaxSize];  //结点表数组
    int count;  //结点数量
}CTree;

树的链式存储-孩子兄弟表示法

1
2
3
4
5
//孩子兄弟表示法，只包括3个数据：1.数据域；2.指向该结点的第一个结点；3.指向与该结点同层兄弟结点
typedef struct CSNode{
    ElemType data;  //数据域
    CSNode *firstchild,*nextsibling;    //第一个孩子和下一个兄弟（可以便于层次搜索）
}CSNode,*CSTree;
more >>

展开全文 >>

数据结构-二叉树

二叉树

二叉树的存储

二叉树的顺序存储-数据结构

1
2
3
4
5
6
7
8
9
//顺序存储，从树顶到底，从上到下，从左往右存入结点，不存在则标记
//顺序存储常用于满二叉树和完全二叉树
#define MaxSize 50	//定义树中元素的最大个数
typedef struct{    //树的结点定义
    ElemType data;  //数据元素
}BiTNode;
typedef struct{
	BiTNode nodes[MaxSize];	//存放栈中元素
}BiTree;	//

二叉树的链式存储-数据结构

1
2
3
4
5
//主要使用链式存储，之后也只讨论链式的方法
typedef struct BiTNode{
    ElemType data;  //数据域
    BiTNode *lchild,*rchild;    //左右孩子指针
}BiTNode,*BiTree;
more >>

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

很惭愧<br><br>只做了一点微小的工作<br>谢谢大家