数据结构

第一章 绪论

1.1 数据结构的基本概念

1.1.1 数据结构的基本概念

数据对象

• 数据项相当于struct里面的变量，数据元素相当于struct类型，数据对象是struct的数组，数据是所有数据的集合

数据结构

1.1.2 数据结构的三要素

逻辑结构

数据结构的三要素

物理结构

顺序存储

链式存储

索引存储

散列存储

数据类型

1.2.1 算法的基本概念

算法的特性

有穷性

确定性

可行性

1.2.2 算法的时间复杂度

练习

1.2.3 算法的空间复杂度

程序运行时的内存需求

函数递归调用带来的内存开销

第二章 线性表

• 逻辑结构是指数据之间的关系。如树、图、表。
• 物理结构是指数据的存放方式。如链式、顺序、复合。

2.1 线性表的定义和基本操作

线性表的定义

线性表的基本操作

2.2 线性表的顺序表示

2.2.1 顺序表的定义

• 顺序表：用顺序存储方式来实现的线性表

顺序表的定义

顺序表的实现——静态分配

• 函数内定义的数组是随机值，函数外的数组一定都是0（int main（）函数），即局部变量随机，全局变量都是0（原因是内存上面是栈存放指令，下面是堆负责存放数据，堆是虚拟的，用一块开一块内存，最开始标记为全部指向零，但栈是开多少就是多少，里面的值不会清空
  C++默认的栈空间是一M，不够大定义很大会报错，函数外面的变量会放在堆空间里面，没有长度限制只有内存限制

• 一定要将length的初始值设为0

顺序表的实现——动态分配

#include <iostream>
#include <cstring>//sizeof头文件
#include <stdlib.h>//malloc函数的头文件
using namespace std;
const int inisize 10;
const int N =100010;
//定义一个int类型的数据表
struct Selist{
    int *data;//指向顺序表中的第一个数据元素
    int maxsize;//顺序表的最大容量
    int length;//顺序表的当前长度
}selist[N];
//初始化顺序表
void ini(Sqlist &L){
    L.data=(int *)malloc(inisize *sizeof(int))//用malloc函数申请一片连续的内存空间,把malloc返回的指针转化为int类型
        L.length=0;
    L.maxsize=inisize;
}
//增加动态数组的长度
void addsize(Sqlist &L,int len){
    int *p=L.data;//定一个个指针指向data，记录顺序表的原起始地址
    L.data=(int *)malloc((L.maxsize+len)*sizeof(int));//扩展顺序表的起始地址，改变顺序表的长度
    for(int i = 0;i<L.length;i++){
        L.data[i]=p[i];//把原顺序表的数据整体移位，将数据复制到新区域
    }
    L.maxsize=L.maxsize+len;//顺序表的最大长度增加len
    free(p);//释放原来的内存空间
}

• 改变data前

• 改变data后

• 释放内存空间后

• 由于p这个变量是一个局部域这个函数的变量，所以当这个函数执行结束以后，存储p这个变量的这些内存空间会被系统自动地回收

顺序表的实现

2.2.2.1 顺序表的插入删除

顺序表的基本操作——插入

#include <iostream>
#include <cstring>
#include <stdlib.h>
using namespace std;
const int maxsize=10;
const int inisize=10;
const int N =100010;
//定义顺序表
struct Sqlist{
    int data[maxsize];
    int length;
}sqlist[N];
void insert(Sqlist &L,int i,int e){//在顺序表L的位序i处插入元素e
    for(int j = L.length;j>=i;j--)//从后往前循环到i，因为i前面的元素不需要变动，只需要把i及其后面的元素往后移一位
        L.data[j]=L.data[j-1];//把i后面的元素移一位
    L.data[i-1]=e;//因为数组从0开始，所以位序=数组下标+1，在位置i处放入e
    L.length++;//总长度加1
}
//带合法性判断的顺序表插入
bool insert(Sqlist &L,int i , int e){
    if(i<1||i>L.length+1)
        return false;
    for(int j =L.length;j>=i;j--)
        L.data[j]=L.data[j-1];
    L.data[i-1]=e;
    L.length++;
    return true;
}
int main(){
  ini(L);
  insert(L,3,3);
    return 0;
}

插入操作的时间复杂度

顺序表的基本操作——删除

​

#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <cstdio.h>
using namespace std;
const int N =10010;
const maxsize=10;
struct Sqlist{
    int data[maxsize];
    int length;
}sqlist[N];//声明一个静态顺序表
void ini(Sqlist &L){
    for(int i = 0;i<L.length;i++)
        L.data[i]=0;
}
bool delete(Sqlist &L,int i,int &e){
    if(i<1||i>L.length)
        return false;//判断位序i是否合法
    e=L.data[i-1];//用e记录被删除的元素
    for(int j = i;j<L.length;j++)
        L.data[j-1]=L.data[j];//将i后的元素前移
    L.length--;//线性表长度-1
    return true;
}
int main(){
   	ini(L);//初始化
    int e = -1;//用变量e把删除的元素”带回来“
    if(delete(L,3,e))
        printf("已删除第3个元素，删除元素值为%d\n",e);
    else
        printf("位序i不合法发，删除失败\n");
    return 0;
}

删除操作的时间复杂度

2.2.2.2 顺序表的查找

顺序表的按位查找

//静态顺序表的按位查找
#include <iostream>
#include <cstring>
#incldue <stdlib.h>
#include <cstdio>
using namespace std;
const int  N =10;
struct Sqlist{
    int length;
    lnt data;
}sqlist[N];
void init(Sqlist &L){
    for(int i=0;i<L.length;i++)
        L.data[i]=0;
}
int getnum(Sqlist L,int i ){
    return L.data[i-1];//位序和数组下标的关系
}

//动态顺序表的按位查找
#include <iostream>
#include <cstring>
#incldue <stdlib.h>
using namespace std;
const int N =10;
struct Seqlist{
    int *data;
    int maxsize;
    int length;
}seqlist[N];
void init(Seqlist &L){
    L.data=(int *)malloc(N*sizeof(int));
    L.length =0;
    L.maxsize=N;
}
int getnum(Seqlist L,int i){
    return L.data[i-1];
}

按位查找的时间复杂度

顺序表的按值查找

//爆搜，最好不用，可以自己写二分
#include <iostream>
using namespace std;
const int N =10;
struct Seqlist{
    int *data;
    int maxsize;
    int length;
}seqlist[N];
void init(Seqlist &L){
    L.data=(int *)malloc(N*sizeof(int));
    	L.length=0;
    L.maxsize=N;
}
//爆搜
int loc(Seqlist L,int e){
    for(int i = 0;i<L.length;i++)
        if(L.data[i]==e)
            return i+1;
    return 0;
}
//二分查找
int binary(int l, int r,int x)//l=0,r=length-1;x为想要找的值
{
    while(l<r){
        int mid = l+r>>1;
        if(mid>=x) r = mid;
        else l = mid+1;
    }
    return l;
}

结构类型的比较

//在C++中可以重载小于号，比如：
struct Edge{
	int a,b,w; //边a,b,权重w
    bool operator<(const Edge &W)const{
        return w<W.w;
    }
}edges[M];

按值查找的时间复杂度

2.3 线性表的链式表示

2.3.1 单链表的定义

用代码定义一个单链表

struct Node{
    int val;
 	Node* next;
}*head;
//上面的代码定义可运行，没问题
int main(){
        Node* p = new Node();//定义一个新节点
        p->val = x;//p的值为x;
    	p->next = head;//头插法，p是新的头结点，所以原head是p的下一个节点;
    	head = p;//头结点变为p
		//遍历链表
    for(Node* p  =head;p;p=p->next)
        cout<<p->val<<' ';
    cout<<endl;
    return 0;
}
//yxc版

typedef struct Node{
    int data;
    struct Node* next;
}Node,*head;
Node* p=(Node* )malloc(sizeof(Node))
    //王道书版

不带头结点的单链表

typedef struct Node{
    int data;
    struct Node *next;
}Node,*head;
//初始化一个空的单链表
bool init(head &L){
    L = NULL;//空表，暂时还没有任何节点
    return true;
}
void test(){
    head L;//声明一个指向单链表的指针
    init(L);//初始化一个空表
}
//判断单链表是否为空
bool empty(head L){
    if(L==NULL)
        return true;
    else 
        return false;
}
//判断单链表是否为空简洁版
bool empty(head l){
    return (L=NULL);
}

带头结点的单链表

struct Node{
    int val;
 	Node* next;
}*head;
//上面的代码定义可运行，没问题
int main(){
        Node* p = new Node();//定义一个新节点
        p->val = x;//p的值为x;
    	p->next = head;//头插法，p是新的头结点，所以原head是p的下一个节点;
    	head = p;//头结点变为p
		//遍历链表
    for(Node* p  =head;p;p=p->next)
        cout<<p->val<<' ';
    cout<<endl;
    return 0;
}
//yxc版

typedef struct Node{
	int val;
    Node* next;
}Node,*head;
//初始化一个单链表（带头结点）
bool init(head &L){
    L = (Node* )malloc(sizeof(Node));//分配一个头结点
    if(L==NULL)//内存不足，分配失败
        	return false;
    L->next = NULL;//头结点之后暂时还没有节点
    return true;
}
void test(){
    head L;//声明一个指向单链表的指针
    init(L);//初始化一个空表
}
//判断单链表是否为空（带头结点）
bool empty(head L){
    if(L->next ==NULL)
        return true;
    else 
        return false;
}
//王道书版

不带头结点 vs 带头结点

2.3.2.1 单链表的插入删除

关于简化图示的说明

按位序插入（带头结点）

struct Node{
    int val;
 	Node* next;
}*head;
//上面的代码定义可运行，没问题
int main(){
        Node* p = new Node();//定义一个新节点
        p->val = x;//p的值为x;
    	p->next = head;//头插法，p是新的头结点，所以原head是p的下一个节点;
    	head = p;//头结点变为p
		//遍历链表
    for(Node* p  =head;p;p=p->next)
        cout<<p->val<<' ';
    cout<<endl;
    return 0;
}
//yxc版

typedef struct Node{
	int val;
    Node* next;
}Node,*head;
//初始化一个单链表（带头结点）
bool init(head &L){
    L = (Node* )malloc(sizeof(Node));//分配一个头结点
    if(L==NULL)//内存不足，分配失败
        	return false;
    L->next = NULL;//头结点之后暂时还没有节点
    return true;
}
void test(){
    head L;//声明一个指向单链表的指针
    init(L);//初始化一个空表
}
//在第i个位置插入元素e（带头结点）
bool insert(head &L,int i ,int e){
    if(i<1)//i不合法
        return false;
    Node* p;//指针p指向当前扫描到的节点
    int j = 0;//当前p指向的是第几个节点
    p = L;//L指向头结点，头结点是第0个节点（不存数据）
    while(p!=NULL && j<i-1){//循环找到第i-1个节点
        p=p->next;
        j++;
    }
    if(p==NULL)//i值不合法
        return false;
    Node *s = (LNode *)malloc(sizeof(Node));//定义一个新节点，此即要插入的节点
    s->val=e;//新插入的节点的值为e
    s->next=p->next;//插入，把s指向头结点的下一个节点
    p->next = s;//s变为头结点的下一个节点，将节点s连到p之后
    return true;//插入成功
}

• 顺序颠倒会导致原头结点的下一个节点数据的丢失

按位序插入（不带头结点）

typedef struct Node{
    int val;
    struct Node* next;
}Node,*head;
bool insert(head &L,int i ,int e){
    if(i<1)//位序的合法性判断
        return false;
    if(i==1){//插入第1个节点的操作与其他节点操作不同
        Node* s = (Node*)malloc(sizeof(Node));
        s->data=e;//赋值
        s->next=L;//s成为第一个节点，下一个节点是L
        L=s;//头指针指向新节点
        return true;
    }
    Node* p;//指针p指向当前扫描到的节点
    int j = 1;//当前p指向的是第几个节点
    p  = L;//p指向第1个节点（注意：不是头结点），准备从头开始bianli 
    while(p!=NULL&&j<i-1){//循环找到第i-1个节点
        p = p->next;//往下一个节点走
        j++;//当前扫描的节点
    }
    if(p=NULL)//i值不合法
        return false;
    Node* s= (Node*) malloc(sizeof(Node));//找到位置，准备插入，开辟一个新节点
    s->val = e;//要插入的值
    s->next = p->next;//插入
    p->next = s;
    return true;
}

指定节点的后插操作

//后插操作：在p结点之后插入元素e
bool insertnext(Node *p,int e){
    if(p==NULL)
        return false;
    Node* s=(Node *)malloc(sizeof (Node));//申请节点空间
    if(s==NULL)//内存分配失败
        return false;
    s->data=e;//用节点s保存数据元素e
    s->next=p->next;//s指向p指向的节点
    p->next=s;//p指向s，在p和p的下一个节点中间插入s
    return true;
}
//定义一个节点类型
typedef struct Node{
    int data;
    struct Node* next;
}Node,*head;

指定节点的前插操作

//前插操作：在p结点之前插入元素e
bool insertpri(Node* p,int e){
    if(p==NULL)//p是否合法
        return false;
    Node *s = (Node*)malloc(sizeof(Node));//分配新空间
    if(s==NULL)//内存分配失败
        return false;
    s->next=p->next;//s指向p指向的节点，即s指向p的下一个节点
    p->next=s;//p指向s
    s->data=p->data;//s保存p保存的值
    p->data=e;//p的值变为要存放的节点，即把p变成新节点
    //相当于本来要在p前面插入一个新节点，但实际上开了一个p节点的副本s节点相当于原p节点，p节点变为插在原p结点前的新节点
    return true;
}

按位序删除（带头结点）

typedef struct Node{
	int data;
    struct Node* next;
}Node,*head;//定义节点类型
bool delete(head &L,int i ,int &e){
    if(i<1)//检测位序合法性
        return false;
    Node*p;//指针p指向当前扫描到的节点
    int j = 0;//当前p指向的是第几个节点
    p=L;//L指向头结点，头结点是第0个节点（不存数据）
    while(p!=NULL&&j<i-1){//循环找到第i-1个节点
        p=p->next;
      	j++;
    }
    if(p==NULL)//i值不合法
        return false;
    if(p->next == NULL)//第i-1个结点之后已无其他节点
        return false;
    Node* q = p->next;//令q指向被删除节点
    e=q->data;//用e返回元素的值
    p->next=q->next;//将*q节点从链中断开
    free(q);//释放节点的存储空间
    return true;//删除成功
}

指定节点的删除

//删除指定节点p（把p变为p后面的一个节点，将原p从链中丢掉）
bool remove(Node* p){
    if(p==NULL)
        return false;
    Node* q=p->next;//q指向p的后继节点//q相当于一个tmp变量
    p->data=p->next->data//p存储原p后继节点的数据，和后继节点交换数据域
        p->next=q->next;//将原p节点从链中断开，p的下一个节点指向q的下一个节点，即p指向p后继节点的后继节点，将p变为自身的后继节点
    free(q);//释放后继节点的存储空间
    return true;
}

封装的好处

2.3.2.2 单链表的查找

按位查找

//按位查找，返回第i个元素（带头结点）
typedef struct Node{
    int data;
    struct Node* next;
}Node,*head;//定义一个节点类型
Node* getnum(head L,int i){
    if(i<0)//判断i是否合法
        return NULL;
    Node* p;//指针p指向当前扫描到的节点
    int j = 0;//当前p指向的是第几个节点
    p = L;//L指向头结点，头结点是第0个节点（不存数据）
    while(p!=NULL && j<i){//循环找到第i个节点
        p=p->next;
        j++;
    }
    return p;
}

• i=0，直接返回头结点

• 当i的值不合法，返回的是NULL

按值查找

typedef struct Node{
    int data;
    struct Node* next;
}Node,*head;
//按值查找，找到数据域==e的节点
Node* find(head L,int e){
    Node* p = L->next;//L是头结点
    //从第一个节点开始查找数据域为e的节点
    while(p!=NULL&&p->data !=e)
        p=p->next;
    return p;//找到后返回该结点指针，否则返回NULL
}

//yxc版
struct Node{
	int val;
	Node*next;
}*head;
Node* find(int x){//要找的值是x，返回值=x的节点
    for(Node *p = head;p;p->next)
        if(p->val==x)
            return p;
}

• 可以找到的情况

• 无法找到的情况，跳出循环，返回NULL

求表的长度

//王道版求表的长度
struct Node{
    int data;
    struct Node *next;
}Node,*head;
int length(head L){
    int len =0;
    Node*p = L;
    while(p->next !=NULL){
        p=p->next;
        len++;
    }
    return len;
}

//yxc版
struct Node{
    int val;
    Node *next;
}*head;
int getlength(){
    int len=0;
    for(Node *p = head;p;p->next)
        len++;
    return len;
}

2.3.2.3 单链表的建立

尾插法建立单链表

typedef struct Node{//定义单链表节点类型
    int data;//每个节点存放一个数据元素
    struct Node *next;//指针指向下一个节点
}Node,*head;
//初始化一个单链表（带头结点）
bool init(head &L){
    L =(Node*) malloc(sizeof(Node));
    if(L==NULL)//内存不足，分配失败
        return false;
    L->next = NULL;
    return true;
}
void test(){
    head L;//声明一个指向单链表的指针
    //初始化一个空表
    init(L);
    
}

/*准备工作
typedef struct Node{
	int val;
    Node* next;
}Node,*head;
//初始化一个单链表（带头结点）
bool init(head &L){
    L = (Node* )malloc(sizeof(Node));//分配一个头结点
    if(L==NULL)//内存不足，分配失败
        	return false;
    L->next = NULL;//头结点之后暂时还没有节点
    return true;
}
void test(){
    head L;//声明一个指向单链表的指针
    init(L);//初始化一个空表
}
*/
//在第i个位置插入元素e（带头结点）
bool insert(head &L,int i ,int e){
    if(i<1)//i不合法
        return false;
    Node* p;//指针p指向当前扫描到的节点
    int j = 0;//当前p指向的是第几个节点
    p = L;//L指向头结点，头结点是第0个节点（不存数据）
    while(p!=NULL && j<i-1){//循环找到第i-1个节点
        p=p->next;
        j++;
    }
    if(p==NULL)//i值不合法
        return false;
    Node *s = (LNode *)malloc(sizeof(Node));//定义一个新节点，此即要插入的节点
    s->val=e;//新插入的节点的值为e
    s->next=p->next;//插入，把s指向头结点的下一个节点
    p->next = s;//s变为头结点的下一个节点，将节点s连到p之后
    return true;//插入成功
}
尾插法建立单链表：
    初始化单链表
    设置变量length记录链表长度
    while循环{
    每次取一个数据元素e
        insert(L,length+1,e)插到尾部;
    length++;
}

/*准备工作
typedef struct Node{
	int val;
    Node* next;
}Node,*head;
//初始化一个单链表（带头结点）
bool init(head &L){
    L = (Node* )malloc(sizeof(Node));//分配一个头结点
    if(L==NULL)//内存不足，分配失败
        	return false;
    L->next = NULL;//头结点之后暂时还没有节点
    return true;
}
void test(){
    head L;//声明一个指向单链表的指针
    init(L);//初始化一个空表
}
*/
//后插法：
head listlist (list &L){//正向建立单链表
    int x;//设为int型
 L=(head)malloc(sizeof(Node));//建立头结点
    Node*s,*r=L;//r为表尾指针
    cin>>x;//输入节点的值
    while(x!=9999){//输入9999表示结束
s=(Node*)malloc(sizeof(Node));
        //s为新加入的节点
        s->data=x;//s保存新加入的节点的数据
        r->next =s;//s变为尾节点，原尾结点指向s
        r=s;//s成为新的尾结点
        cin>>x;//继续输入要加入的值
    }
    //表内数据输入完成
    r->next=NULL;//尾结点指针置空
    return L;//返回头结点
}

头插法建立单链表

/*准备工作
typedef struct Node{
	int val;
    Node* next;
}Node,*head;
//初始化一个单链表（带头结点）
bool init(head &L){
    L = (Node* )malloc(sizeof(Node));//分配一个头结点
    if(L==NULL)//内存不足，分配失败
        	return false;
    L->next = NULL;//头结点之后暂时还没有节点
    return true;
}
void test(){
    head L;//声明一个指向单链表的指针
    init(L);//初始化一个空表
}
*/

head listlist(head &L){//逆向建立单链表
    Node* s;
    int x;
    L=(head)malloc(sizeof(Node));//创立头结点
    L->next=NULL;//初始为空链表
    cin>>x;//输入节点的值
    while(x!=9999){//输入9999表示结束
        s=(Node* )malloc(sizeof(Node));//创建新节点
        s->data=x;//s记录新节点的数值
        s->next=L->next;//s指向原头结点指向的节点
        L->next=s;//将新节点插入表中，L为头指针，s成为新的第一个节点
        cin>>x;
    }
    return L;
}

2.3.3 双链表

单链表 vs 双链表

双链表的初始化（带头结点）

//双链表节点的定义：
typedef struct dnode{
    int data;
    struct dnode *prior,*next;
}dnode,*dlist;
//初始化双链表
bool init(dlist &L){
    L=(dnode*)malloc(sizeof(dnode));//分配一个头结点
    if(L==NULL)//内存不足，分配失败
	return false;
    L->prior=NULL;//头结点的prior永远指向NULL
    L->next = NULL;//头结点之后暂时还没有节点
    return true;
}
void testdlist(){
    //初始化双链表
    dlist L;
    init(L);
}
//判断双链表是否为空
bool empty(dlist L){
    if(L->next == NULL)
        return true;
    else 
        return false;
}

双链表的插入

//在p结点之后插入s节点
bool insert(dnode *p,denode *s)
{
    s->next = p->next;//s指向p的右侧节点，将节点s插入到节点p之后
    p->next->prior=s;//p的右侧节点的左指向s
    s->prior=p;//s的左节点为p
    p->next=s;//p的右节点为s
}

• p节点没有后继节点的情况

//在p结点之后插入s节点
bool insertnext(dnode* p,denode* s){
    if(p==NULL ||s == NULL)//非法参数
	return false;
    s->next=p->next;
    if(p->next !=NULL)//如果p节点有后继节点
        p->next->prior=s;
    s->prior=p;
    p->next=s;
    return true;
}

双链表的删除

//删除p节点的后继节点
bool deletenext(dnode *p){
    if(p==NULL)return false;
    dnode *q=p->next;//找到p的后继节点q
    if(q==NULL)return false;//p没有后继
    p->next=q->next;//p的右节点跳过q
    if(q->next!=NULL)//q节点不是最后一个节点
        q->next->prior=p;//q的下一个点的左节点变为p
    free(q);//释放节点空间
    return true;
}
//删掉整个链表
void destroy(dlist &L){
    //循环释放各个数据节点
    while(L->next !=NULL)
        deletenext(L);
    free(L);//释放头结点
    L=NULL;//头指针指向NULL
}

双链表的遍历

//后向遍历
while(p!=NULL){
    //对p节点做相应处理，如打印
    p=p->next;
}
//前向遍历
while(p!=NULL){
    //对节点p做相应处理
    p=p->prior;
}
//前向遍历（跳过头结点）
while(p->prior!=NULL){
    //对节点p做相应处理
    p=p->prior;
}

2.3.4 循环链表

循环单链表

typedef struct lnode{//定义单链表节点类型
int data;//每个节点存放一个数据元素
struct lnode *next;//指针指向下一个节点
}lnode,*head;
//初始化一个循环单链表
bool init(head &L){
    L=(lnode* )malloc(sizeof(lnode));//分配一个头结点
    if(L==NULL)//内存不足，分配失败
        return false;
    L->next=L;//头结点next指向头结点
    return true;
}
//判断循环单链表是否为空
bool empty(head L){
    if(L->next == L)
        return true;
    else 
        return false;
}
//判断节点p是否为循环单链表的表尾结点
bool istail(head L,lnode *p){
    if(p->next==L)
        return true;
    else 
        return false;
}

循环双链表

typedef struct dnode{
    int data;
    struct dnode *prior,*next;
}dnode,*head;
//初始化空的循环双链表
bool init(head &L){
    L=(dnode*)malloc(sizeof(dnode));//分配一个头结点
    if(L==NULL)//内存不足，分配失败
        return false;
    L->prior=L;//头结点的pior指向头结点
    L->next =L;//头结点的next指向头结点
    return true;
}
void testdlist(){
    //初始化循环双链表
    head L;
    init(L);
}
//判断循环双链表是否为空
bool empty(head L){
    if(L->next ==L)
        return true;
    else 
        return false;
}
//判断节点p是否为循环双链表的表尾结点
bool istail(head L,dnode*p){
    if(p->next ==L)
        return true;
    else 
        return false;
}

双链表的插入

//在p结点之后插入s节点
bool insert(dnode *p,dnode* s){
	s->next = p->next;//将节点s插入到节点p后面
    p->next->prior=s;//p的右节点的左箭头指向s
    s->prior=p;//s的左箭头指向p
    p->next=s;//p的右箭头指向s
}

双链表的删除

//删除p的后继节点q
p->next=q->next;//p指向后继节点的右节点
q->next->prior=p;//p的后继节点的后继节点的左节点变为q
free(q);//释放q节点

2.3.5 静态链表

什么是静态链表

用代码定义一个静态链表

const int maxsize =10;//静态链表的最大长度
struct Node{//静态链表结构类型的定义
	int data;//存储数据元素
	int next;//下一个元素的数组下标
}node[maxsize];
void test(){
   Node a;//数组a作为静态链表
}

//yxc版
// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;//e为节点的值，ne为指向的地址
//因为是从0开始的，所以第k的插入点的下标是k-1
// 初始化
void init()
{
    head = -1;
    idx = 0;
}

// 在链表头插入一个数a，即头插法
void insert(int a)
{
    e[idx] = a, ne[idx] = head, head = idx ++ ;//idx即新插入的点的下标
}

//将x插入到下标是k的点的后面
void add(int k ,int x)
{
    e[idx] = x;
    ne[idx]=ne[k];
    ne[k]=idx++;
    
}

//将下标是k的点后面的点删掉
void remove(int k){
    ne[k]=ne[ne[k]];
}


// 将头结点删除，需要保证头结点存在
void remove()
{
    head = ne[head];
}

//遍历单链表
for(int i = head;i!=-1;i=ne[i])
    	cout<<e[i]<<endl; 

简述基本操作的实现

• 初始化

• 查找（位序的节点）

• 插入位序为i的节点

• 删除某个节点

#define maxsize 10//静态链表的最大长度
typedef struct{//静态链表结构类型的定义
    int data;//存储数据元素
    int next;//下一个元素的数组下标
}slist[maxsize];

//yxc,数组模拟单链表
// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;//e为节点的值，ne为指向的地址
//因为是从0开始的，所以第k的插入点的下标是k-1
// 初始化
void init()
{
    head = -1;
    idx = 0;
}

// 在链表头插入一个数a，即头插法
void insert(int a)
{
    e[idx] = a, ne[idx] = head, head = idx ++ ;//idx即新插入的点的下标
}

//将x插入到下标是k的点的后面
void add(int k ,int x)
{
    e[idx] = x;
    ne[idx]=ne[k];
    ne[k]=idx++;
    
}

//将下标是k的点后面的点删掉
void remove(int k){
    ne[k]=ne[ne[k]];
}


// 将头结点删除，需要保证头结点存在
void remove()
{
    head = ne[head];
}

//遍历单链表
for(int i = head;i!=-1;i=ne[i])
    	cout<<e[i]<<endl; 

2.3.6 顺序表和链表的比较

逻辑结构

存储结构

基本操作

• 初始化（创建）

• 销

• 增删

• 查找

用顺序表or链表

第三章 栈、队列和数组

3.1 栈

3.1.1 栈的基本概念

栈的定义

线性表的基本操作

栈的基本操作

栈的常考题型

3.1.2 栈的顺序存储实现

顺序栈的定义

#define maxsize 10//定义栈中元素的最大个数
typedef struct{
    int data[maxsize]//静态数组存放栈中元素
    int top;//栈顶指针
}sqstack;

//yxc
// tt表示栈顶
int stk[N], tt = 0;//stk表示栈，tt表示栈顶下标

// 向栈顶插入一个数
stk[ ++ tt] = x;

// 从栈顶弹出一个数
tt -- ;

// 栈顶的值
stk[tt];

// 判断栈是否为空，如果 tt > 0，则表示不为空
if (tt > 0) not empty;
else empty;

//栈顶
stk[tt];

初始化操作

#define maxsize 10//定义栈中元素的最大个数
typedef struct{
    int data[maxsize]//静态数组存放栈中元素
    int top;//栈顶指针
}sqstack;
//初始化栈
void init(sqstack &s){
    s.top=-1;//初始化栈顶指针
}
bool ifempty(sqstack s){
    if(s.top==-1)//栈空
        return true;
    else 
        return false;//不空
}

进栈操作

#define maxsize 10//定义栈中元素的最大个数
typedef struct{
	int data[maxsize];//静态数组存放栈中元素
	int top;//栈顶指针
}sqstack;
//新元素入栈
bool push(sqstack &s,int x){
	if(s.top==maxsize-1)//栈满，报错
		return false;
        s.top = s.top+1;//指针先加1
        s.data[s.top]=x;//新元素入栈
        return true;
}

出栈操作

#define maxsize  10//定义栈中元素的最大个数
typedef struct{
    int data[maxsize];//静态数组存放栈中元素
    int top;//栈顶指针
}sqstack;
//出栈操作
bool pop(sqstack &s,int &x){
    if(s.top==-1)//栈空，报错
        return false;
    x=s.data[s.top];//栈顶元素先出栈
    s.top=s.top-1;//指针再-1
    return true;
}

读取栈顶元素操作

#define maxsize  10//定义栈中元素的最大个数
typedef struct{
    int data[maxsize];//静态数组存放栈中元素
    int top;//栈顶指针
}sqstack;
//出栈操作
bool pop(sqstack &s,int &x){
    if(s.top==-1)//栈空，报错
        return false;
    x=s.data[s.top];//栈顶元素先出栈
    s.top=s.top-1;//指针再-1
    return true;
}
//读栈顶元素
bool gettop(sqstack s,int &x){
    if(s.top==-1)//栈空，报错
        return false;
    x=s.data[s.top];//x记录栈顶元素
    return true;
}

另一种方式

#define maxsize 10//定义栈中元素的最大个数
typedef struct{
    int data[maxsize];//静态数组存放栈中元素
    int top;//栈顶指针
}sqstack;
//初始化栈
void init(sqstack &s){
    s.top=0;//初始化栈顶指针
}
//判断栈空
bool empty(sqstack s){
    if(s.top==0)//栈空
        return true;
    else //不空
        return false;
}

共享栈

#define maxsize 10//定义栈中元素的最大个数
typedef struct{
    int data[maxsize];//静态数组存放栈中元素
    int top0;//0号栈栈顶指针
    int top1;//1号栈栈顶指针
}shstack;
//初始化栈
void init(shstack &s){
    s.top0=-1;//初始化栈顶指针
        s.top1=maxsize;
}

3.1.3 栈的链式存储实现

链栈的定义

typedef struct linknode{
    int data;//数据域
    struct linknode *next;//指针域
}*listack;//栈类型定义

3.2 队列

3.2.1 队列的基本概念

队列的定义

队列的基本操作

3.2.2 队列的顺序实现

#define maxsize 10//定义队列中元素的最大个数
typedef struct {
    int data[maxsize];//用静态数组存放队列元素
    int front,rear;//队头指针和队尾指针
}sqqueue;
void testqueue(){
    sqqueue Q;//声明一个队列（顺序存储）
}

//yxc
// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;

// 向队尾插入一个数
q[ ++ tt] = x;

// 从队头弹出一个数
hh ++ ;

// 队头的值
q[hh];

//取出队尾
q[tt];

// 判断队列是否为空，如果 hh <= tt，则表示不为空
if (hh <= tt) not empty;
    else empty;

初始化操作

#define maxsize 10//定义队列中元素的最大个数
typedef struct {
    int data[maxsize];//用静态数组存放队列元素
    int front,rear;//队头指针和队尾指针
}sqqueue;
//初始化队列
void init(sqqueue &Q){
    //初始时，对头、队尾指针指向0
    Q.rear=Q.front=0;
}
//判断队列是否为空
bool empty(sqqueue Q){
    if(Q.rear==Q.front)//队空条件
        return true;
    else return false;
}
void testqueue(){
    sqqueue Q;//声明一个队列（顺序存储）
}

入队操作

#define maxsize 10//定义队列中元素的最大个数
typedef struct {
    int data[maxsize];//用静态数组存放队列元素
    int front,rear;//队头指针和队尾指针
}sqqueue;
//入队
bool inq(sqqueue &Q,int x){
    if(队列已满)
        return false;//队满则报错
    Q.data[Q.rear]=x;//将新元素x插入队尾
    Q.rear=Q.rear+1;//队尾指针后移
    return true;
}

循环队列

循环队列——入队操作

//判断队列是否为空
bool empty(sqq Q){
    if(Q.rear==Q.front)//队空条件
        return true;
    else 
        return false;
}
//入队
bool inq(sqq &Q,int x){
if((Q.rear+1)%maxsize==Q.front))
    return false;//队满则报错
Q.data[Q.rear]=x;//新元素插入队尾
Q.rear=(Q.rear+1)%maxsize;//队尾指针加1取模
	return true;
}

循环队列——出队操作


//出队（删除一个队头元素，并用x返回）
bool dequeue(sqqueue &Q,int &x){
    if(Q.rear==Q.front)
        return false;//队空则报错
    x=Q.data[Q.front];
    Q.front=(Q.front+1)%maxsize;
    return true;
}
//获得队头元素的值，用x返回
bool gethead(sqqueue Q,int &x){
    if(Q.rear==Q.front)
        return false;//队空则报错
    x=Q.data[Q.front];
    return true;
}

方案一：判断队列已满/已空

方案二：判断队列已满/已空

方案三：判断队列已满/已空

其他出题方法

3.2.3 队列的链式实现

typedef struct linknode{//链式队列节点
    int data;
	struct linknode *next;
}linknode;
typedef struct{//链式队列
    linknode *front,*rear;//队列的队头和队尾指针
}linkqueue;

初始化（带头结点）

typedef struct linknode{
	int data;
	struct linknode *next;
}linknode;
typedef struct{
    linknode *front,*rear;
}linkqueue;
//初始化队列（带头节点）
void init(linkqueue &Q){
    //初始时，front、rear都指向头结点
    Q.front=Q.rear=(linknode*)malloc(sizeof(linknode));
    Q.front->next=NULL;
}
void testlinkqueue(){
    linkqueue Q;//声明一个队列
	init(Q);//初始化一个队列
}
//判断队列是否为空
bool empty(linkqueue Q){
    if(Q.front==Q.rear)
        return true;
    else 
        return false;
}

初始化（不带头结点）

//初始化队列（不带头结点）
void init(linkqueue &Q){
    //初始时 front、rear都指向NULL
    Q.front=NULL;
    Q.rear=NULL;
    
}
//判断队列是否为空（不带头结点）
bool empty(linkqueue Q){
    if(Q.front ==NULL)
        return true;
    else 
        return false;
    
}

入队（带头结点）

//新元素入队（带头结点）
void enqueue(linkqueue &Q,int x){
    linknode *s=(linknode *)malloc(sizeof(linknode));//申请一个新的节点
    s->data=x;//把数据x放到这个新节点中
    s->next=NULL;
    Q.rear->next=s;//新节点插入到rear之后
    Q.rear=s;//修改表尾指针
}

入队（不带头结点）

//新元素入队（不带头节点）
void enqueue(linkqueue &Q,int x){
    linknode *s=(linknode *)malloc(sizeof(linknode));//申请一个新节点
    s->data=x;//将数据元素x存入新节点中
    s->next=NULL;
    if(Q.front==NULL){//在空队列中插入第一个元素
        Q.front=s;//修改队头队尾指针
        Q.rear=s;
        
    }
    else{
        Q.rear->=x;//新节点插入到rear接待年之后
        Q.rear=s;//修改rear指针
    }
}

出队（带头结点）

//队头元素出队（不带头节点）
bool dequeue(linkqueue &Q,int &x){
    if(Q.front==Q.rear)//空队
        return false;
    linknode *p=Q.front->next;
    x=p->data;//用变量x返回队头元素
    Q.front->next=p->next;//修改头结点的next指针
    if(Q.rear==p)//此次是最后一个节点出队
        Q.rear=Q.front;//修改rear指针
	free(p);//释放节点空间
    return true;
}

出队（不带头结点）

//队头元素出队（不带头结点）
bool dequeue(linkqueue &Q,int &x){
    if(Q.front==NULL)
        return false;//空队
    linknode *p=Q.front;//p指向此次出队的节点
    x=p->data;//用变量x返回队头元素
    Q.front=p->next;//修改front指针
    if(Q.rear==p){//此次是最后一个节点出队
        Q.front=NULL;//front指向NULL
        Q.rear=NULL//rear指向NULL
        
    }
    free(p);//释放节点空间
    return true;
}

队列满的条件

3.2.4 双端队列

双端队列

考点：判断输出序列合法性

• 若果在输出序列中看到某一个序号的元素，那么在这个元素输出之前，意味着它之前的所有的那些元素，肯定都已经输入到这个队列里边了

栈

输入受限的双端队列

• 下划线是栈中非法但是输入受限的双端队列中合法的输出序列

输出受限的双端队列

3.3 栈和队列的应用

3.3.1 栈在括号匹配中的应用

括号匹配问题

• 当我们遇到左括号的时候，就把它压入栈中，当我们遇到右括号的时候，就把栈顶的那个左括号给弹出，然后检查他们两是否匹配

算法演示

//yxc表达式求值
#include <iostream>
#include <cstring>
#include <stack>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
stack<int> num;
stack<char> op;
void eval(){
    auto b = num.top();num.pop();
    auto a = num.top();num.pop();
    auto c = op.top();op.pop();
    int x ;
    if(c=='-') x = a-b;
    else if (c=='+')x=a+b;
    else if (c=='*') x =a*b;
    else x = a/b;
    num.push(x);
}

int main(){
    string str;
    cin>>str;
    unordered_map<char,int> pr{{'+',1},{'-',1},{'*',2},{'/',2}};
    for(int i = 0;i<str.size();i++){
        auto c = str[i];
        if(isdigit(c)){
            int x = 0,j=i;
            while(j<str.size()&&isdigit(str[j]))x=x*10+str[j++]-'0';
            num.push(x);
            i=j-1;
        }
        else if(c=='(') op.push(c);
        else if(c==')'){
            while(op.size()&&op.top()!='(') eval();
            op.pop();
        }
        else {
            while(op.size()&&op.top()!='('&&pr[op.top()]>=pr[c])eval();
            op.push(c);
        }
    }
    while(op.size())eval();

    cout<<num.top();
    return 0;




}

//算法实现
#define maxsize 10//定义栈中元素的最大个数
typedef struct{
    char data[maxsize];//静态数组存放栈中元素
	int top;//栈顶指针
}sqstack;
//初始化栈
void init(sqstack &S)
    //判断栈是否为空
    bool empty(sqstack S)
    //新元素入栈
    bool push(sqstack &S,char x)
    //栈顶元素出栈，用x返回
    bool pop(sqstack &S,char &x)
  //匹配括号
bool check(char str[],int length){
    sqstack S;
    init(S);//初始化一个栈
    for(int i = 0;i<length;i++){
        if(str[i]=='('||str[i]=='['||str[i]=='{'){
            push(S,str[i]);//扫描到左括号，入栈
        }
        else{
            if(empty(S))//扫描到右括号，且当前栈空
                return false;//匹配失败
        
        char top;
        //如果没扫描到左括号，扫描到右括号且当前栈非空
        pop(S,top);//栈顶元素出栈
  		if(str[i]==')'&&top!='(')
            return false;
        if(str[i]==']'&&top!='[')
            return false;
        if(str[i]=='}'&&top!='{')
            return false;
        }
    }
    return empty(S);//检索完全部括号后，栈空说明匹配成功
}

3.3.2 栈在表达式求值中的应用

熟悉的算术表达式

中缀、后缀、前缀表达式

• 后缀左优先，前缀右优先

中缀表达式转后缀表达式（手算）

• 后缀表达式中的运算符从左到右的先后顺序和中缀表达式当中运算符的生效次序是相同的

中缀表达式转后缀表达式（机算）

• 后缀表达式没有界限符

• 不带括号的情况

• 带括号的情况
  • 当栈顶是左括号的时候，不需要弹出任何元素，直接把当前的运算符压入栈


后缀表达式的计算（手算）

后缀表达式的计算（机算）

• 中缀表达式适合人类运算，后缀表达式适合机器进行运算，因为不用判断运算符的优先级，从左到右直接运算即可

中缀表达式转前缀表达式（手算）

• 按照右优先规则确定的这些运算符的生效顺序，和我们前缀表达式当中各个运算符从右到左出现的次序是相同的

前缀表达式的计算

• 先出栈的是左操作数，后出栈的是右操作数
  • 和后缀表达式的运算刚好相反
    • 后缀表达式中，先出栈的应该是右操作数，后出栈的是左操作数

中缀表达式的计算（用栈实现）

//狗蛋写的
#include <iostream>
#include <cstring>
#include <stack>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
stack<int> num;
stack<char> op;
void eval(){
    auto b = num.top();num.pop();
    auto a = num.top();num.pop();
    auto c = op.top();op.pop();
    int x ;
    if(c=='-') x = a-b;
    else if (c=='+')x=a+b;
    else if (c=='*') x =a*b;
    else x = a/b;
    num.push(x);
}

int main(){
    string str;
    cin>>str;
    unordered_map<char,int> pr{{'+',1},{'-',1},{'*',2},{'/',2}};
    for(int i = 0;i<str.size();i++){
        auto c = str[i];
        if(isdigit(c)){
            int x = 0,j=i;
            while(j<str.size()&&isdigit(str[j]))x=x*10+str[j++]-'0';
            num.push(x);
            i=j-1;
        }
        else if(c=='(') op.push(c);
        else if(c==')'){
            while(op.size()&&op.top()!='(') eval();
            op.pop();
        }
        else {
            while(op.size()&&op.top()!='('&&pr[op.top()]>=pr[c])eval();
            op.push(c);
        }
    }
    while(op.size())eval();

    cout<<num.top();
    return 0;

}

//yxc
#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
#include <unordered_map>

using namespace std;

stack<int> num;
stack<char> op;

void eval()
{
    auto b = num.top(); num.pop();
    auto a = num.top(); num.pop();
    auto c = op.top(); op.pop();
    int x;
    if (c == '+') x = a + b;
    else if (c == '-') x = a - b;
    else if (c == '*') x = a * b;
    else x = a / b;
    num.push(x);
}

int main()
{
    unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
    string str;
    cin >> str;
    for (int i = 0; i < str.size(); i ++ )
    {
        auto c = str[i];
        if (isdigit(c))
        {
            int x = 0, j = i;
            while (j < str.size() && isdigit(str[j]))
                x = x * 10 + str[j ++ ] - '0';
            i = j - 1;
            num.push(x);
        }
        else if (c == '(') op.push(c);
        else if (c == ')')
        {
            while (op.top() != '(') eval();
            op.pop();
        }
        else
        {
            while (op.size() && op.top() != '(' && pr[op.top()] >= pr[c]) eval();
            op.push(c);
        }
    }
    while (op.size()) eval();
    cout << num.top() << endl;
    return 0;
}

• 两者都是从左往右扫描
  • 先弹出的是右操作数，后弹出的是左操作数





3.3.3 栈在递归中的应用

函数调用背后的过程

• 在函数里边修改a的值或者b的值，那么它修改的其实是函数中a和b的值，但是main函数里面的a、b这两个变量其实对应的是内存当中的这两份数据，因此在func1里面修改a和b的值，影响不到main函数里面a和b的值

• 函数执行完之后把它的相关信息弹出栈，释放对应的内存空间

栈在递归中的应用

3.3.4 队列的应用

队列应用——树的层次遍历

• 首先被遍历的是根节点，遍历到1号节点的时候把1号节点的左右孩子塞入队列的队尾

• 遍历完1号节点之后，就可以出队，从队列中删除1号节点，接下来检查新队头节点即2号节点，同样的把2号节点的左右孩子放入队尾
  • 没有孩子的直接出队

//yxc
queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);

while (q.size())
{
    int t = q.front();
    q.pop();

    for (int i = h[t]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true; // 表示点j已经被遍历过
            q.push(j);
        }
    }
}

队列应用——图的广度优先遍历

• 遍历1号节点，检查1号节点相邻的其他节点有没有被遍历过，没被遍历过放到队列的队尾，处理完1号结点之后就可以让他，即1号节点出队

• 接下来处理2号节点，看2号相邻的节点中有没有还没被处理过的节点，把没有处理过的放到队列末尾，然后2号可以出队

队列在操作系统中的应用

3.4 数组和特殊矩阵

一维数组的存储结构

二维数组的存储结构

• 行优先存储

• 列优先存储

普通矩阵的存储

对称矩阵的压缩存储

• 矩阵下标和一维数组下标的映射函数

• 如何访问上三角区

• 万变不离其宗，具体转换只需要看aij对应的是数组中的哪一个元素即可
• 列优先
  • 前面有j-1列，i-j就是该位置前面有多少个元素（按列数），最后加上这个数字本身

三角矩阵的压缩存储

• 按照行优先或者列优先的原则把不是常量的数据都放到一个一维数组里面

• 行优先下三角

• 行优先上三角

三对角矩阵的压缩存储

• j-(i-2)，因为第i行前面有i-2个0

稀疏矩阵的压缩存储

顺序存储

十字链表法

• 绿色数组对应系数矩阵中的各行，橙色数组对应稀疏矩阵的各列，每个非零元素对应一个节点

第四章 串

4.1 串的定义和实现

4.1.1 串的定义和基本操作

串的定义

串vs线性表

串的基本操作

字符集编码（ASCII码）

拓展：乱码问题

4.1.2 串的存储结构

串的顺序存储

//静态数组实现
#define maxlen 255//预定义最大串长为255
typedef struct{
	char ch[maxlen];//每个分量存储一个字符
	int length;
}sstring;
//动态数组实现
typedef strct{
    char *ch;//按串长分配存储区，ch指向串的基地址
    int length;//串的长度
}hstring;
hstring s;
s.ch = (char *)malloc(maxlen * sizeof(char));
s.length =0;

• 方案三的缺点：查询字符串长度的时间复杂度为O(n)
  • 方案二的缺点：字符串长度的范围是8bit即255，比较短
• 方便随机存储，但增删改查不方便

串的链式存储

typedef struct stringnode{
	char ch;//每个节点存1个字符
    struct stringnode *next;
}stringnode, *string;

typedef struct stringnode{
    char ch[4];//每个节点存多个字符
    struct stringnode *next;
}stringnode, *string;

• 便于增删改查，但没有随机存储的特性

基本操作的实现

#typedef maxlen 255//预定义最大串长为255
typedef struct{
    char ch[maxlen];//每个分量存储一个字符
	int length;//串的实际长度
}sstring;
//求子串
bool substring(sstring &sub,sstring s,int pos,int len){
    //字串范围越界
    if(pos+len-1>s.length)
        return false;
    for(int i = pos;i<pos+len;i++)
        sub.ch[i-pos+1]=s.ch[i];
    sub.length =len;
    return true;
}
//比较操作。若S>T，则返回值>0;若S=T，则返回值=0；若S<T，则返回值<0
int strcompare(sstring s,sstring t){
    for(int i = 1;i<=s.length && i<=t.length;i++){
        if(s.ch[i]!=t.ch[i])
            return s.ch[i]-t.ch[i];
}
	//扫描过的所有字符都相同，则长度长的串更大
    return s.length-t.length;
}
//定位操作
int index(sstring s,sstring t){
    itn i=1,n=strlength(s),m=strlength(t);
    sstring sub;//用于暂存字串
    while(i<=n-m+1){
        substring(sub,s,i,m);
        if(strcompare(sub,t)!=0)++i;
        else return i;//返回子串在主串中的位置
    }
    return 0;//S中不存在与T相等的子串
}

4.2 串的模式匹配

4.2.1 朴素模式匹配算法

是什么

朴素模式匹配算法

int index(sstring s,sstring t){
    int i = 1,j=1;
    while(i<=s.length &&j<=t.length){
        if(s.ch[i]==t.ch[j])
            i++,j++;//继续比较后继字符
  		else 
            i=i-j+2,j=1;//指针后退重新开始匹配
    }
    //只有两种情况可能跳出循环：1.i越界，说明遍历了整个主串都没有找到符合条件的子串。2.j越界，说明模式串遍历完毕，在主串中找到了对应的子串
    if(j>t.length)//说明匹配成功
        return i-t.length;
    else //匹配失败
        return 0;
}

//YXC
s[N],p[M];//s是主串，p是模板串

for(int i = 1;i<=n;i++){
//
bool flag = true;

for(int j = 1;j<=m;j++)

if(s[i+j-1]!=p[j]){//因为匹配的时候指向s的也要往后挪动，所以这里的[]内是指s的本轮循环的位置还要往后挪多少位置，最开始的时候是初始位置对比字串，所以挪动的位置为0，此后要-1来保持对准

flag = false;

break;
	}

}
//这里判断的是能否匹配，如果要返回第一次出现的位置，成功后break掉再返回i即可

//完整版
#include <iostream>
#include <cstring>
#include <stdio.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    string a;
    string b;
    getline(cin,a);
    getline(cin,b);
    bool flag=true;
    int N,M;
    N=a.length();
    M=b.length();
    for(int i = 0;i<N;i++){
        flag = true;
        for(int j = 0;j<M;j++){
            if(a[i+j-1]!=b[j]){
               flag = false;
               break;
            }
        }
        if(flag) {
            cout<<i<<endl;
            break;
        }

    }
    if(!flag)cout<<"false"<<endl;
    system("pause");
return 0;


}

4.2.2 KMP算法

yxc笔记

存在五个相等的轴，其中：

• 由于第一段第二段在i-j都相等，所以P①=S①，P②=S②
• 由于J+1匹配失败，P字串向后移动直到再次匹配，此时P③=S②，由于S②=P②，所以P②=P③
• 由于P实际上为字串位移，所以P③=P①
• 综上，存在五段相等的轴
• 因此，只需要求子串P中，P①=P②的最大区域，当该区域越大， P再次匹配往后移动的距离越短

因此，对于字串P：

• 需要预处理出以某个点为终点的后缀与前缀相等，相等的长度最大为多少

  

  Next[i]=j//即从i开始的后缀与从1开始的前缀相等，而且后缀的长度最长

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度 s[]要匹配的长串，p[]比较短的模板串
求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )//扫描p的长度
{
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}

// 匹配O(n)
for (int i = 1, j = 0; i <= n; i ++ )//扫描s的长度
{
    while (j && s[i] != p[j + 1]) //之前没有匹配元素下回溯或者某个元素不匹配
        j = ne[j];//回溯到next数组下标j指向的元素
    if (s[i] == p[j + 1]) j ++ ;//匹配成功，继续往后匹配
    if (j == m)//j=m，说明所有元素都匹配上了，匹配成功
    {
        j = ne[j];//这里是指匹配成功后还有其他要进行的操作
        // 匹配成功后的逻辑
    }
}

//完整
#include<iostream>
using namespace std;
const int N =10010,M=100010;
int n ,m;
char p[N],s[M];
int ne[N];

int main(){
	
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n>>p+1>>m>>s+1;
	//求next数组的过程
	for(int i = 2,j=0;i<=n;i++){
		while(j&&p[i]!=p[j+1]) j = ne[j];
		if(p[i]==p[j+1])j++;
		ne[i] = j;//注意，此处的ne数组已经是优化过的ne数组
	}
	
	
	 
	//kmp匹配过程
	for(int i = 1,j=0;i<=m;i++) //i枚举Si ，j和Si匹配的是P(j+1) ,总往前错一位 
	{
		while(j&&s[i]!=p[j+1])//j没有退回起点，退回起点意味着要重新开始匹配 ;不等意味着那个位置不匹配了 
	    	j = ne[j];//ne[j]是当前j点的最长后缀的长度，j是不匹配后往后移动更新的检验分界点。由于j从0开始，所以当j等于上一个j的ne长度时，相当于j被更新到图示位置 
	    if(s[i]==p[j+1]) j++;//下一个字符终于匹配，继续检验下一个位置的字符是否匹配 
		if(j==n) {
			//匹配成功 
			cout<<i-n<<" ";//输出子串的位置
			j=ne[j];
		}
	}
	
	
} 

kmp匹配过程

求next数组的过程

完整过程

朴素模式匹配算法优化思路

• 找到前缀和后缀相同的子串，然后回溯到前缀的下一个位置

• next指明了当我们在模板串的第几个元素适配的时候，应该把j的值修改为多少

KMP算法

//模式匹配部分
int kmp(sstring s,sstring t,int nex[]){
    int i = 1,j=1;
    while(i<=s.length&&j<=t.length){//没有匹配完的时候
        if(j==0||s.ch[i]==t.ch[j]){//匹配成功或者开始匹配的时候，两者往后移
            ++i;
            ++j;//继续比较后继字符
        }
        else 
            j=next[j];//匹配失败，模板串向右移动
    }
    if(j>t.length)
        return i-t.length;//匹配成功
    else 
        return 0;
}

朴素模式匹配vsKMP算法

求模板串的next数组（手算练习）

next数组的优化

练习：求nextval数组

//求nextval数组
nextval[1]=0;
for(int j = 2;j<=t.length;j++){
    if(t.ch[next[j]]==t.ch[j])
        nextval[j]=nextval[next[j]];
    else
        nextval[j]=next[j];
}

next和nextval数组的个人总结

• next数组采用求匹配失败的元素的左边起子串的前缀后缀相同的下一个位置
• nextval数组j=1的位置无脑写0，然后后面的进行回溯，如果回溯到不一样的就保持不变，一样的就继续回溯

第五章 树与二叉树

5.1 树的基本概念

5.1.1 树的定义和基本术语

树的基本概念

结点、树的属性描述

树vs森林

5.1.2 树的性质

树的常考性质

5.2 二叉树的概念

5.2.1 二叉树的定义和基本术语

二叉树的基本概念

二叉树的五种状态

几个特殊的二叉树

满二叉树

• 除了最下面的叶子节点之外，其他的所有的分支节点都长满了两个分支
• 子结点数要么为2要么为0，不存在度为1的结点
• 这里的取整都是向下取整

二叉排序树

平衡二叉树

5.2.2 二叉树的性质

二叉树的常考性质

• 总度数就是树的分支的总数

5.2.3 二叉树的存储结构

二叉树的顺序存储

#define maxsize 100
struct treenode{
    int value;//结点中的数据元素
    bool isempty;//结点是否为空
};
treenode t[maxsize];
//初始化
for(int i = 0;i<maxsize;i++)
    t[i].isempty = true;

完全二叉树的情况

非完全二叉树的情况

• 对于是否有左右孩子的判断只能用isempty来进行判断
• 存在大量空置单元

二叉树的链式存储

//二叉树的节点（链式存储）
typedef struct bitnode{
	int data;//数据域
	struc bitnode *lkid,*rkid;//左、右孩子指针
}bitnode,*bitree;
//定义一颗空树
bitree root =NULL;
//插入根节点
root = (bitree)malloc(sizeof(bitnode));
root->data={1};
root->lchild =NULL;
root->rchild=NULL;
//插入新节点
bitnode *p=(bitnode *)malloc(sizeof(bitnode));
p->data={2};
p->lchild =NULL;
p->rchild =NULL;
root ->lchild =p;//作为根节点的左孩子

//三叉链表
typedef struct trinode{
    int data;//数据域
    struct trinode *lchild,*rchild,*parent//左孩子，右孩子，父节点
}trinode,*tritree;

5.3 二叉树的遍历和线索二叉树

5.3.1 二叉树的先中后序遍历

二叉树的遍历

先序遍历（代码）

typedef struct binode{
    int data;
    struct binode *lkid,*rkid;
    
}binode,*bitree;
//先序遍历
void pre(bitree T){
    it(T!=NULL){
        visit(T);//访问根节点
        pre(T->lkid);//递归遍历左子树
        pre(T->rkid);//递归遍历右子树
    }
}

中序遍历（代码）

typedef struct binode{
    int data;
    struct binode *lkid,*rkid;
    
}binode,*bitree;
//中序遍历
void inorder(bitree t){
    if(t!=NULL){
        inorder(t->lkid);//递归遍历左子树
        visit(T);//访问根节点
		inorder(t->rkid);//递归遍历右子树
    }
}

后序遍历（代码）

typedef struct binode{
    int data;
    struct binode *lkid,*rkid;
}binode,*bitree;
//后序遍历
void postorder(bitree t){
    if(t!=NULL){
        postorder(t->lkid);//递归遍历左子树
        postorder(t->rkid);//递归遍历右子树
        visit(t);//访问根节点
    }
}

求先序遍历序列

求中序遍历序列

求后序遍历序列

例：求树的深度（应用）

int dep(bitree t){
if(t==NULL){
	return 0;
}
else{
int l = dep(t->lkid);
int r = dep(t->rkid);
//树的深度=max（左子树深度，右子树深度）+1
	return l>r?l+1:r+1;
} 


}

5.3.2 二叉树的层次遍历

二叉树的层序遍历

代码实现

//二叉树的结点（链式存储）
typedef struct node{
    char data;
    struct node *lkid,*rkid;
}node,*tree;
//链式队列结点
typedef struc lnode{
    node *data;
    struct lnode *next;
}lnode;
typedef struct{
    lnode *front,*rear;//队头队尾
}queue;
//层序遍历
void fs(tree t){
    queue Q;
    init(Q);//初始化辅助队列
    tree p;
    enqueue(Q,T);//将根节点入队
	while(!isempty(Q)){//队列不空则循环	
        dequeue(Q,p);//队头结点出队
        visit(p);
        if(p->lkid!=NULL)
            enqueue(Q,p->lkid);//左孩子入队
		if(p->rkid!=NULL)
            enqueue(Q,p->rkid);//右孩子入队
        
    }
}

5.3.3 由遍历序列构造二叉树

由遍历序列构造二叉树

前序+中序遍历序列

例一

例二

后序+中序遍历序列

例

层序+中序遍历序列

例

例2

5.3.4 线索二叉树的概念

中序线索二叉树

线索二叉树的存储结构

//线索二叉树结点
typedef struct node{
    int data;
    struct node *lkid,*rkid;
    int ltag,rtag;//左右线索标志
}node,*tree;

先序线索二叉树

后序线索二叉树

三种线索二叉树的对比

5.3.5 二叉树的线索化

用土办法找到中序前驱

//中序遍历
void fs(tree t){
    if(t!=NULL){
        fs(t->lkid);//递归遍历左子树
        visit(t);//访问根节点
        fs(t->rkid);//递归遍历右子树
    }
}
//访问节点q
void visit(tree *q){
    if(q==p)//当前访问节点刚好是结点p
        final = pre;//找到p的前驱
    else 
        pre=q;//pre指向当前访问的结点
}
//辅助全局变量，用于查找结点p的前驱
node *p;//p指向目标节点
node *pre =NULL;//指向当前访问结点的前驱
node *final=NULL;//用于记录最终结果

中序线索化

//线索二叉树结点
typedef struct node{
    int data;
    struct node *l,*r;
    int lt,rt;//左右线索标志
}node ,*tree;
//全局变量pre，指向当前访问结点的前驱
node *pre=NULL;
//中序遍历二叉树，一边遍历一边线索化
void tread(tree t){
    if(t!=NULL){
        tread(t->l);//中序遍历左子树
        visit(t);//访问根节点
        tread（t->r);//中序遍历右子树
    }
}
void visit(node *q){
    if(q->l==NULL){//左子树为空，建立前驱线索
    	q->l=pre;
        q->lt=1;
    }
    if(pre!=NULL&&pre->r==NULL){//前驱非空，即不是开始的结点，且前驱节点没有右孩子
        pre->r=q;//建立前驱节点的后继线索
		pre->rt=1;
        
    }
    pre=q;
}
//中序线索化二叉树T
void creat(tree t){
    pre =NULL;//因为第一个访问的结点没有前驱，所以pre初始为NULL
    if(t!=NULL){//非空二叉树才能线索化
        tread(t);//中序线索化二叉树
        if(pre->r==NULL)
            pre->rt=1;//处理遍历的最后一个结点
        
    }
}

先序线索化

• 注意，在没有优化的情况下，先序线索化可能出现回溯的情况

//全局变量pre，指向当前访问结点的先驱
node *pre=NULL;
//先序遍历二叉树，一边遍历一遍线索化
void prethread(tree t){
    if(t!=NULL){
        visit(t);//先处理根节点
        	if(t->lt==0)//左孩子不是前驱线索
                pre(t->l);
        pre(t->r);
    }
}
//先序线索化二叉树T
void creat(tree t){
    pre =NULL;//pre初始为NULL
    if(t!=NULL){
        prethread(t);//先序线索化二叉树
			if(pre->r==NULL)
                pre->rt=1;//处理遍历的最后一个结点
    }
}
void visit(node *q){
    if(q->l==NULL){//左子树为空，建立前驱线索
    	q->l=pre;
        q->lt=1;
    }
    if(pre!=NULL&&pre->r==NULL){
        pre->r=q;//建立前驱节点的后继线索
		pre->rt=1;
    }
    pre=q;
}

后续线索化

//全局变量pre，指向当前访问结点的先驱
node *pre=NULL;
//后续遍历二叉树，一边遍历一遍线索化
void post(tree t){
    if(t!=NULL){
        post (t->l);//后序遍历左子树
        post (t->r);//后序遍历右子树
        visit(t);//访问根节点
    }
}
//后续线索化二叉树t
void creat(tree t){
    pre=NULL;//pre初始为NULL
    if(t!=NULL){//非空二叉树才能线索化
    	post(t);//后续线索化二叉树
        if(pre->r==NULL)
            pre->rt=1;//处理遍历的最后一个结点
        
    }
}

5.3.6 在线索二叉树中找前驱后继

中序线索二叉树找中序后继

//找到以P为根的自述中，第一个被中序遍历的结点
node *first(node *p){
    //循环找到最左下结点（不一定是叶节点）
    while(p->lt==0)p=p->l;
    return p;
}
//在中序线索二叉树中找到结点p的后继结点
node *nextnode(node *p){
    //右子树中最左下结点
    if(p->rt==0)return first(p->r);
    else return p->r;//rtag==1直接返回后继线索
}
//对中序线索二叉树进行中序遍历（利用线索实现的非递归算法）
void inorder(node*t){
    	for(node *p=first(t);p!=NULL;p=nextnode(p))
            visit(p);
}

中序线索二叉树找中序前驱

//找到以p为根的子树中，最后一个被中序遍历的结点
node *last(node*p){
    //循环找到最右下结点（不一定是叶节点）
    while(p->rt==0)p=p->r;
    return p;
}
//在中序线索二叉树中找到节点p的前驱节点
node *prenode(node *p){
    //左子树中最右下结点
    if(p->lt==0)return lastnode(p->l);
    else return p->l;//lt==1直接返回前驱线索
}
//对中序线索二叉树进行逆向中序遍历
void rev(node *t){
    for(node *p=last(t);p!=NULL;p=prenode(p))
        visit(p);
}

先序线索二叉树找先序后继

后续线索二叉树找后续前驱

后续线索二叉树找后续后继

5.4 树、森林

5.4.1 树的存储结构

树的逻辑结构

双亲表示法（顺序存储）

#define maxsize 100//树中最多结点数
typedef struct{//树的结点定义
	int data;//数据元素
    int parent;//双亲位置域
}ptnode;
typedef struct{//树的类型定义
    ptnode nodes[maxsize];//双亲表示
	int n;//结点数
    
}ptree;

增

• 新增一个数据元素，储存对应的父节点

删

• 方案一：双亲结点设为-1

• 方案二：把尾部的数据移上来，填充前面的空白

• 删除以后要更改数值，结点数-1

查

孩子表示法（顺序+链式存储）

struct ctnode{
    int kid;//孩子节点在数组中的位置
    struct ctnode *next;//下一个孩子
};
typedef struct{
    int data;
    struct ctnode *first;//第一个孩子
}ctbox;
typedef struct{
    ctbox nodes[maxsize];
    int n,r;//结点数和根的位置
}ctree;

孩子兄弟表示法（链式存储）

//树的存储——孩子兄弟表示法
typedef struct csnode{
    int data;//数据域
    struct csnode *first,*next;//第一个孩子和右兄弟指针
}csnode,*cstree;

森林和二叉树的转换

5.4.2 树和森林的遍历

树的先根遍历

//树的先根遍历
void preorder(node *r){
    if(r!=NULL){
        visit(r);//访问根节点
		while(r还有下一个子树t)
            preorder(t);//先根遍历下一棵子树
    }
}

树的后根遍历

//树的后根遍历
void postorder(node *r){
    if(r!=NULL){
        while(r还有下一个子树t)
            postorder(t);//后根遍历下一棵子树
        visit(r);//访问根节点
    }
}

• 树的先根遍历和树的后根遍历合称树的深度遍历

树的层次遍历(树的宽度遍历)

森林的先序遍历

森林的中序遍历

深度优先遍历yxc

bool st[N];
int dfs(int u)
{
    st[u] = true; // st[u] 表示点u已经被遍历过

    for (int i = h[u]; i != -1; i = ne[i])//遍历点的边
    {
        int j = e[i];//存储当前链表节点对应的图里面的点的编号
        if (!st[j]) dfs(j);//j没有被搜到，继续搜
    }
}

宽度优先遍历yxc

queue<int> q;//初始化
st[1] = true; // 表示1号点已经被遍历过
q.push(1);

while (q.size())//队列不空
{
    int t = q.front();
    q.pop();

    for (int i = h[t]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true; // 表示点j已经被遍历过
            q.push(j);
        }
    }
}

int bfs()
{
	int hh =0,tt=0;//定义队头队尾
    q[0]=1;//q的第一个元素起点
    memset(d,-1,sizeof d);//初始化距离，-1表示没有被遍历过
    d[1]=0;//第一个点遍历
    while(hh<=tt){//队列不空
        int t=q[hh++]//取到队头
            for(int i = h[t];i!=-1;i=e[i])//拓展队头
            {
                int j =e[i];//拓展到队头连接的下一个点
               if(d[j]==-1)//d[j]没有被拓展过
               {
                   d[j]=d[t]+1;
                   q[++tt]=j;
               }
            }
    }
    return 0;
}

5.5 树与二叉树的应用

5.5.1 哈夫曼树

• Huffman树利用的是贪心的算法思想


带权路径长度

哈夫曼树的定义

哈夫曼树的构造

• 每一次从节点集合当中选择两个权值最小的结点，成为左右节点，再让这两个点的权值之和成为新树的根节点的权值
  • 之后选择权值最小的根节点作为左右节点组成新的树，再由这两个结点的权值和作为新的根节点的权值

哈夫曼编码

英文字母频次

5.5.2 并查集

并查集yxc笔记

• 快速处理

  • 将两个集合合并

  • 询问两个元素是否在一个集合当中

  • 近乎O(1)

  • 用树的形式维护所有集合，根节点的编号就是集合的编号，每个节点都存储一个父节点p[x]，当要查找元素属于哪个集合，只要找到根节点的编号即可。

    • 如何判断是否是树根：if(p[x]==x)

    • 如何求x的集合编号:while(p[x]!=x)x=p[x];//只要不是树根就一直往上走，直到走到树根为止

      • 优化：路径压缩

        

    • 如何合并两个集合

      px是x的集合编号,py是y的集合编号。p[x]=y;

      

• 读入操作

  char op[2];

  scanf(“%s”,op) 用字符串不会读入空格和回车

(1)朴素并查集：

    int p[N]; //存储每个点的祖宗节点

    // 返回x的祖宗节点，即所在集合的编号，顺便加上路径优化
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);//当不是祖宗节点的时候，寻找父节点的父节点，递归之后找到祖宗节点并将路径优化
        return p[x];//返回祖宗节点
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);//让a的祖宗节点的父节点等于b的祖宗节点，即将a插入b中

    //判断a和b是不是在同一个集合中
      if(find(a)==find(b)) puts("yes");
		else puts("no"); 

(2)维护size的并查集：

    int p[N], size[N];
    //p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量，只保证根节点的size有意义

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        size[i] = 1;
    }

    // 合并a和b所在的两个集合：
      if(find(a)==find(b))continue;//a和b在一个集合当中
    size[find(b)] += size[find(a)];//把a集合中点的个数加到b集合中
    p[find(a)] = find(b);//将a插入b
    //找到某点所在的集合的点的个数
      cout<<size[find(a)];

(3)维护到祖宗节点距离的并查集：

    int p[N], d[N];
    //p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x)
        {
            int u = find(p[x]);
            d[x] += d[p[x]];
            p[x] = u;
        }
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        d[i] = 0;
    }

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);
    d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量

逻辑结构——集合

并查集的存储结构

并查集的基本操作

并查集的代码实现

#define size 13;
int p[size];//集合元素数组
//初始化并查集
void init(int s[]){
    for(int i = 0;i<size;i++)
        s[i]=-1;//父节点的下标    
}
//find “查”操作，找x所属集合（返回x所属根节点）
int find(int s[],int x){
    while(s[x]>=0)//循环寻找x的根
        x=s[x];
    return x;//根的s[]小于0
}
//union “并”操作，将两个集合合并为一个
void union(int s[],int root1,int root2){
    //要求root1与root2是不同的集合
    if(root1==root2)return ;
    //将根root2连接到另一根root1下面
    s[root2]=root1;
}

时间复杂度分析

并操作的优化

//优化后的并代码
void union(int s[],int root1,int root2){
	if(root1==root2)return ;
	if(s[root2]>s[root1]){//root2结点数更少
		s[root1]+=s[root2];//累加节点总数
		s[root2]=root1;//鸮属合并到大树
	
	}
	else{
		s[root2]+=s[root1];//累加节点总数
		s[root1]=root2;//小树合并到大树
	}
}

5.5.3 并查集的进一步优化

拓展：find操作的优化（压缩路径）

//查操作的优化，先找到根节点，再进行“压缩路径”
int find(int s[],int x){
    int root =x;
    while(s[root]>=0) root=s[root];//循环找到根
    while(x!=root){//压缩路径
        int t=s[x];//t指向x的父节点
        s[x]=root;//x直接挂到根节点下
        x=t;
        
        
    }
    return root;//返回根节点编号
}

并查集的优化

第六章 图

6.1 图的基本概念

6.1.1 图的基本概念

图的定义

无向图、有向图

• 无向图圆括号，有向图尖括号

简单图、多重图

• 多重图即复环图

• 顶点的度、入度、出度

顶点-顶点的关系描述

连通图、强连通图

研究图的局部——子图

连通分量

强连通分量

生成树

• 最后一个结论利用抽屉原理证明

生成森林

边的权、带权图/网

几种特殊形态的图


6.2 图的存储及基本操作

6.2.1邻接矩阵法

图的存储——邻接矩阵法

• 无向图中1表示两点之间有一条边
• 无向图中1表示有一条从A指向B的边

//yxc
g[a][b] 存储边a->b//如果有权重，g[a][b]就是权重，无权重就是布尔值，不能保存重边，只能保留一条，适合存储稠密图，时间复杂度为O(n)

//王道
#define max 100//顶点数目的最大值
typedef struct{
    char vex[max];//顶点表
	int edge[max][max]//邻接矩阵，边表
    int vexnum,arcnum;//图的当前顶点数和边数/弧数
}mgraph;

邻接矩阵法存储带权图（网）

#define max 100//顶点数目的最大值
#define INF=0x3f3f3f3f//定义常量无穷
typedef char vertextype;//顶点的数据类型
typedef int edgetype;//带权图中边上权值的数据类型
typedef struct{
    vertextype vex[max];//顶点
    edgetype edge[max][max];//边的权
    int vexnum,arcnum;//图的当前顶点数和弧数
}mgraph;

邻接矩阵法的性能分析

6.2.2 邻接表法

邻接表法（顺序+链式存储）

//yxc
// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[2N], ne[2N], idx;

// 添加一条边a->b
void add(int a, int b)//插入a的邻边
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++ ;//h[a]是头结点，将a节点开头的第一条边变为当前边，idx移动到下一条边
}

// 初始化
idx = 0;
memset(h, -1, sizeof h);
//邻接表的输入
for(int i = 0;i<m;i++)
{
    int a,b;
    cin>> a >>b;
    add(a,b);
}

//边/弧
typedef struct arcnode{
    int adjvex;//边/弧指向哪个结点
    struct arcnode *next;//指向下一条弧的指针
    //infotype info;//边权值
}
//顶点
typedef struct node{
    vertextype data;//定点信息
    arcnode *first;//第一条边/弧
}node,adjlist[max];
//用邻接表存储的图
typedef struct{
    adjlist vertices;
    int vexnum,arcnum;
}algraph;

6.2.3 十字链表、邻接多重表

• 代码复杂度高，一般不考手写代码

十字链表存储有向图

• 沿着绿色一直往后找各个节点的话，可以找到从当前这个顶点往外发射的边
• 沿着橙色一直往后找各个结点的话，可以找到所有指向当前顶点的弧

十字链表法性能分析

• V表示顶点个数，E表示边的个数

邻接矩阵、邻接表存储无向图

邻接多重表存储无向图

6.2.4 图的基本操作

图的基本操作

判断是否存在边

列出与某个节点邻接的边

• 具体问题具体分析，注意稠密图和稀疏图中V和E的区别

插入顶点

删除顶点x

增加一条边

找到指定顶点的第一个邻接点

找到指定顶点的第一个邻接点接下来的后一个邻接点

设置/获取某条边的权值

6.3 图的遍历

6.3.1 图的广度优先遍历

树vs图

bool visit[max];//访问标记数组
void bfstraverse(graph g){//对图g进行广度优先遍历
    for(i=0;i<g.vexnum;i++)
        visited[i]=false;//访问标记数组初始化
    init(Q);//初始化辅助队列Q
    for(i=0;i<g.vexnum;i++)//从0号顶点开始遍历
        if(!visited[i])//对每个连通分量调用一次BFS
            BFS(G,i);//vi未访问过，从vi开始bfs
    
}
//广度优先遍历
void bfs(graph g,int v){//从顶点v出发，广度优先遍历图G
    visit(v)//访问初始顶点v
        visited[v]=true;//对v做已访问标记
    enqueue(q,v);//顶点v入队列Q
    while(!isempty(q)){
        dequeue(q,v);//顶点v出队列
  for(w=firstneighbor(g,v);w>=0;w=nextneighbor(g,v,w))
     //检测v所有邻接点
            if(!visited[w]){//w为v的尚未访问的邻接顶点
                visit(w);//访问顶点w
                visited[w]true;//对w做已访问标记
                enqueue(q,w);//顶点w入队列
                
            }//if
    }//while
  
}

//yxc
queue<int> q;//初始化
st[1] = true; // 表示1号点已经被遍历过
q.push(1);

while (q.size())//队列不空
{
    int t = q.front();
    q.pop();

    for (int i = h[t]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true; // 表示点j已经被遍历过
            q.push(j);
        }
    }
}
int bfs()
{
	int hh =0,tt=0;//定义队头队尾
    q[0]=1;//q的第一个元素起点
    memset(d,-1,sizeof d);//初始化距离，-1表示没有被遍历过
    d[1]=0;//第一个点遍历
    while(hh<=tt){//队列不空
        int t=q[hh++]//取到队头
            for(int i = h[t];i!=-1;i=e[i])//拓展队头
            {
                int j =e[i];//拓展到队头连接的下一个点
               if(d[j]==-1)//d[j]没有被拓展过
               {
                   d[j]=d[t]+1;
                   q[++tt]=j;
               }
            }
    }
    return 0;
}

广度优先遍历序列

遍历序列的可变性

• 邻接矩阵找到的是递增的次序

算法存在的问题

BFS算法（final版）

bool visit[max];//访问标记数组
void bfstraverse(graph g){//对图g进行广度优先遍历
    for(i=0;i<g.vexnum;i++)
        visited[i]=false;//访问标记数组初始化
    init(Q);//初始化辅助队列Q
    for(i=0;i<g.vexnum;i++)//从0号顶点开始遍历
        if(!visited[i])//对每个连通分量调用一次BFS
            BFS(G,i);//vi未访问过，从vi开始bfs
    
}
//广度优先遍历
void bfs(graph g,int v){//从顶点v出发，广度优先遍历图G
    visit(v)//访问初始顶点v
        visited[v]=true;//对v做已访问标记
    enqueue(q,v);//顶点v入队列Q
    while(!isempty(q)){
        dequeue(q,v);//顶点v出队列
  for(w=firstneighbor(g,v);w>=0;w=nextneighbor(g,v,w))
     //检测v所有邻接点
            if(!visited[w]){//w为v的尚未访问的邻接顶点
                visit(w);//访问顶点w
                visited[w]true;//对w做已访问标记
                enqueue(q,w);//顶点w入队列
                
            }//if
    }//while
  
}

复杂度分析

广度优先生成树

广度优先生成森林

有向图的BFS过程

bool visit[max];//访问标记数组
void bfstraverse(graph g){//对图g进行广度优先遍历
    for(i=0;i<g.vexnum;i++)
        visited[i]=false;//访问标记数组初始化
    init(Q);//初始化辅助队列Q
    for(i=0;i<g.vexnum;i++)//从0号顶点开始遍历
        if(!visited[i])//对每个连通分量调用一次BFS
            BFS(G,i);//vi未访问过，从vi开始bfs
    
}
//广度优先遍历
void bfs(graph g,int v){//从顶点v出发，广度优先遍历图G
    visit(v)//访问初始顶点v
        visited[v]=true;//对v做已访问标记
    enqueue(q,v);//顶点v入队列Q
    while(!isempty(q)){
        dequeue(q,v);//顶点v出队列
  for(w=firstneighbor(g,v);w>=0;w=nextneighbor(g,v,w))
     //检测v所有邻接点
            if(!visited[w]){//w为v的尚未访问的邻接顶点
                visit(w);//访问顶点w
                visited[w]true;//对w做已访问标记
                enqueue(q,w);//顶点w入队列
                
            }//if
    }//while
  
}

6.3.2 图的深度优先遍历

图的优先遍历

//yxc
bool st[N];
int dfs(int u)
{
    st[u] = true; // st[u] 表示点u已经被遍历过

    for (int i = h[u]; i != -1; i = ne[i])//遍历点的边
    {
        int j = e[i];//存储当前链表节点对应的图里面的点的编号
        if (!st[j]) dfs(j);//j没有被搜到，继续搜
    }
}

//王道书
bool visit[max];//访问标记数组
void dfs(graph g,int v){//从顶点v出发，深度优先遍历图G
    visit(v);//访问顶点v
    visited[v]=true;//设已访问标记
    for(w=firstneighbor(g,v);w>=0;w=nextneighbor(g,v,w))
        if(!visited[w]){//w为u的尚未访问的邻接结点
            dfs(g,w);
        }//if
    
}

算法存在的问题

dfs算法（final版）

//王道书
bool visit[max];//访问标记数组
void dfstravers(graph g){//对图g进行深度优先遍历
    for(v=0;v<g.vexnum;++v)
        visited[v]=false;//初始化已访问标记数据
    for(v=0;v<g.vexnum;++v)//本代码中是从v=0开始遍历
        if(!visited[v])
            dfs(g,v);
    
    
}
void dfs(graph g,int v){//从顶点v出发，深度优先遍历图G
    visit(v);//访问顶点v
    visited[v]=true;//设已访问标记
    for(w=firstneighbor(g,v);w>=0;w=nextneighbor(g,v,w))
        if(!visited[w]){//w为u的尚未访问的邻接结点
            dfs(g,w);
        }//if
    
}

复杂度分析

深度优先遍历序列

深度优先生成树

深度优先生成森林

图的遍历与图的连通性

6.4 图的应用

6.4.1 最小生成树

最小生成树（最小代价树）

• 最小生成树没有环，正边和负边都可以用

• 初始阶段考查prim算法和kruskal算法代码的概率不高

prim算法

//yxc
//朴素版prim
//时间复杂度O(n²),n表示点数，m表示边数，稠密图
int n;      // n表示点数
int g[N][N];        // 邻接矩阵，存储所有边
int dist[N];        // 存储其他点到当前最小生成树的距离
bool st[N];     // 存储每个点是否已经在生成树中

//到集合的距离就是一个点连接集合的所有边中最短的那一条
// 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim()
{
    memset(dist, 0x3f, sizeof dist);//初始化最短距离

    int res = 0;
    for (int i = 0; i < n; i ++ )//n次迭代
    {
        int t = -1;//不在集合当中的距离最小点的编号
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        if (i && dist[t] == INF) return INF;

        if (i) res += dist[t];//只要不是第一个点
        st[t] = true;

        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
    }

    return res;
}
//堆优化版prim
//时间复杂度O(mlogn)，稀疏图

kruskal算法

//yxc
//时间复杂度O(mlogn),n表示点数，m表示边数
//将所有边按照权重从小到大排序
//枚举每条边a,b，权重c
//如果a，b不连通，将这条边加入集合中来。
int n, m;       // n是点数，m是边数
int p[N];       // 并查集的父节点数组

struct Edge     // 存储边
{
    int a, b, w;

    bool operator< (const Edge &W)const//重载小于号
    {
        return w < W.w;
    }
}edges[M];

int find(int x)     // 并查集核心操作
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal()
{
    sort(edges, edges + m);//把所有边排序

    for (int i = 1; i <= n; i ++ ) p[i] = i;    // 初始化并查集

    int res = 0, cnt = 0;
    for (int i = 0; i < m; i ++ )//从小到大枚举所有边
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;

        a = find(a), b = find(b);//让a，b分别等于祖宗节点
        if (a != b)     // 如果两个连通块不连通，则将这两个连通块合并
        {
            p[a] = b;//合并两个连通块
            res += w;//存的是最小生成树中所有树边的权重之和
            cnt ++ ;//存的是当前加入了多时少条边
        }
    }

    if (cnt < n - 1) return INF;//图不是联通的
    return res;//输出所有树边的权重之和
}

prim算法 vs kruskal算法

prim算法的实现思想

kruskal算法的实现思想

6.4.2 最短路径问题（bfs算法）

最短路径问题

• 单源最短路径是指从一个源头出发到达其他任意一个顶点

bfs求无权图的单源最短路径

代码实现

//求顶点u到其他顶点的最短路径
void bfs(graph g,int u){
    for(i=0;i<g.vexnum;i++){
        d[i]=INF;//初始化路径长度
        path[i]=-1;//最短路径从哪个顶点过来
    }
    d[u]=0;
    visited[u]=true;
    enqueue(q,u);
    while(!isempty(q)){//bfs算法主过程
        dequeue(q,u);//队头元素u出队
        for(w=firstneighbor(g,u);w>=0;w=nextneighbor(g,u,w))
        if(!visited[w]){//w为u的尚未访问的邻接顶点
            d[w]=d[u]+1;//路径长度加1
            path[w]=u;//最短路径应从u到w
            visited[w]=true;//设已访问标记
            enqueue(q,w);//顶点w入队
            
        }//if
    }//while
}

6.4.3 最短路径问题（dijkstra算法）

yxc笔记

朴素dijkstra算法

思路：
定义距离数组，判断数组，存储结构
初始化距离和存储结构
第一个点的距离定义为0
取出最新点，找出最新点的最短距离
用该最短距离更新
判断长度，得出连不连通

• 时间复杂度是O(n²+m)，n表示点数，m表示边数
• 初始化距离

int g[N][N];  // 存储每条边
int dist[N];  // 存储1号点到每个点的最短距离
bool st[N];   // 存储每个点的最短路是否已经确定

// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);//初始化其他距离
    dist[1] = 0;//初始化第一个点的距离

    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;     // 在还未确定最短路的点中，寻找距离最小的点
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))//当前点还没有确定最短路；没有赋值或者不是最短的
                t = j;//赋值
  // if(t==n)break;//优化可以加上
        // 用t更新其他点的距离
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);
//判断长度，得出最小距离并更新
        st[t] = true;
    }

    if (dist[n] == 0x3f3f3f3f) //不连通
        return -1;
    return dist[n];
}
//输入输出
cin >> n>>m;
memset(g,0x3f,sizeof g);
while(m--){
    int a,b,c;
    cin>>a>>b>>c;
    g[a][b]=min(g[a][b],c);
}
int t =dijkstra()l
    cout<<t;
return 0;

堆优化版的dijkstra算法

• 手写堆
• 优先队列（不支持修改任意一个元素，里面的元素可能是m个，时间复杂度变为mlogm，但由于是稀疏图，所以和mlogn差不多

typedef pair<int, int> PII;

int n;      // 点的数量
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储所有点到1号点的距离
bool st[N];     // 存储每个点的最短距离是否已确定

void add(int a,int b,int c){
    e[idx]=b,w[idx]= c,ne[idx]=h[a],h[a]=idx++;
}
// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;//定义小根堆
    heap.push({0, 1});      // first存储距离，second存储节点编号

    while (heap.size())//堆里面非空
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;//编号；距离

        if (st[ver]) continue;//冗余备份
        st[ver] = true;

        for (int i = h[ver]; 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];
}
int main(){
    cin >> n>>m;
    memset(h,-1,sizeof h);
    while(m--){
        int a,b,c;
        cin >> a >> b>>c;
        add(a,b,c);
    }
    int t = dijkstra();
    cout<<t;
    return 0;
}

BFS算法的局限性

dijkstra算法

dijkstra算法的时间复杂度

用于负权值带权图

6.4.4 最短路径问题（floyd算法）

floyd算法

//yxc
cosnt int INF=1e9;
初始化：
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i == j) d[i][j] = 0;
            else d[i][j] = INF;

// 算法结束后，d[a][b]表示a到b的最短距离
void floyd()
{
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

floyd算法核心代码

//王道
//准备工作，根据图的信息初始化矩阵A和path（如上图）
for(int k = 0;k<n;k++){
    //考虑以vk作为中转点
    for(int i = 0;i<n;i++){
        //遍历整个矩阵，i为行号，j为列号
        for(int j = 0;j<n;j++){
            if(a[i][j]>a[i][k]+a[k][j]){
          					//以vk为中转点的路径更短
                a[i][j]=a[i][k]+a[k][j];//更新最短路径长度
                path[i][j]=k;//中转点
            }
        }
    }
        
}

floyd算法示例

不能解决的问题

6.4.5 有向无环图描述表达式

有向无环图（DAG）

DAG描述表达式

例题

解题方法

6.4.6 拓扑排序

AOV网

yxc拓扑排序笔记

时间复杂度O(n+m)，n表示点数，m表示边数

有向图才有拓扑序列，如果有环没有拓扑序，有向无环图一定有拓扑序列，也被称为拓扑图

入度是指有多少条边指向自己，因此所有入度为0的点都可以作为起点

出度是指有多少条边出去

• 把所有入度为0的点入队
  • 一个有向无环图至少存在一个入度为0的点
  • 有向无环图的拓扑序不一定是唯一的

int n,m;
int h[N],e[N],ne[N],idx;
int d[N],q[N];//d[n]表示入度，q[n]是拓扑序列
void add(int a,int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a]=idx++;
    
}
bool topsort()
{
    int hh = 0, tt = -1;

    // d[i] 存储点i的入度
    for (int i = 1; i <= n; i ++ )
        if (!d[i])
            q[ ++ tt] = i;//数组模拟入队

    while (hh <= tt)//队列不空
    {
        int t = q[hh ++ ];//取出来队头

        for (int i = h[t]; i != -1; i = ne[i])//枚举t的所有出边t->j，删掉t->j
        {
            int j = e[i];//找到出边
           d[j]--;
            if ( d[j] == 0)//前面的所有点都已经排好了
                q[ ++ tt] = j;//j入队
         
        }
    }

    // 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
    return tt == n - 1;
}
//出队的顺序就是拓扑序

拓扑排序

对有回路的图进行拓扑排序

拓扑排序的代码实现

#define size 100//图中顶点数目的最大值
typedef struct arcnode{//边表节点
    int adjvex;//该弧所指向的顶点的位置
    struct arcnode *nextarc;//指向下一条弧的指针
    //infotype info;//网的边权值
}arcnode;
typedef struct vnode{//定点表节点
    vertextype data;//定点信息
    arcnode *firstarc;//指向第一条依附该顶点的弧的指针
}vnode,adjlist[size];
typedef struct{
    adjlist vertices;//邻接表
    int vexnum,arcnum;//图的顶点数和弧数
}graph;//graph是以邻接表存储的图类型
bool topo(graph g){
    init(s);//初始化栈，存储入度为0的顶点
    for(int i = 0;i<g.vexnum;i++)
        if(indegree[i]==0)
            push(s,i);//将所有入度为0的顶点进栈
    int count=0;//计数，记录当前已经输出的顶点数
    while(!isempty(s)){//栈不空，则存在入度为0的顶点
        pop(s,i);//栈顶元素出栈
        print[count++]=i;//输出顶点i
        for(p=g.vertices[i].firstarc;p;p=p->nextarc){
            //将所有i指向的顶点的入度减1，并将入度减为0的顶点压入栈s
            v=p->adjvex;
            if(!(--indegree[v]))
                push(s,v);//入度为0，则入栈
        }
        
    }//while
    if(count<g.vexnum)
        return false;//排序失败，有向图中有回路
    else 
        return true;//拓扑排序成功
}

逆拓扑排序

逆拓扑排序的实现

逆拓扑排序的实现（DFS算法）

void dfstraverse(graph g){//对图g进行深度优先遍历
    for(v=0;v<g.vexnum;++v)
        visited[v]=false;//初始化已访问标记数据
    for(v=0;v<g.vexnum;++v)//本代码中是从v=0开始遍历
        if(!visited[v])
            dfs(g,v);
}
void dfs(graph g,int v){//从顶点v出发，深度优先边路图g
    visited[v]=true;//设已访问标记
  for(w=firstneighbor(g,v);w>=0;w=nextneighbor(g,v,w))
        if(!visited[w]){//w为u的尚未访问的邻接顶点
        dfs(g,w);    
        }//if
    print(v);//输出顶点
}

6.4.7 关键路径

AOE网

关键路径

求关键路径的步骤

求所有事件的最早发生时间

求所有时间的最迟发生时间

求所有活动的最早发生时间

求所有活动的最迟发生时间

求所有活动的时间余量

求得关键活动、关键路径

关键活动、关键路径的特性

第七章 查找

7.1 查找的基本概念

对查找表的常见操作

查找算法的评价指标

7.2 顺序查找和折半查找

7.2.1 顺序查找

顺序查找的算法思想

顺序查找的实现

typedef struct {//查找表的数据结构（顺序表）
	int *ad;//动态数组基址
    int len;//表的长度
}table;
//顺序查找
int search(table st,int key){
    int i;
    for(i = 0;i<st.len&&st.ad[i]!=key;++i);
    //查找成功，则返回元素下标，查找失败，则返回-1
    return i==st.len?-1:i;
}

顺序查找的实现（哨兵）

• 0号位置存关键字

typedef struct{//查找表的数据结构（顺序表）
	int *ad;//动态数组基址
    int len;//表的长度
}table;
//顺序查找
int search(table st,int key){
    st.ad[0]=key;
    int i;
    for(i=st.len;st.ad[i]!=key;--i);//从后往前找
    return i;//查找成功，则返回元素下标；查找失败，则返回0
}

查找效率分析

顺序查找的优化（对有序表）

用查找判定树分析ASL

顺序查找的优化（被查概率不相等）

7.2.2 二分查找

二分查找yxc

二分不用考虑有没有解

整数二分

• 有单调性的题目可以二分，但可以二分不一定有单调性，二分的本质不是单调性
• 二分的本质是性质，使得一部分满足红色性质，一部分满足绿色性质，整个区间可以一分为二，二分可以寻找性质的边界

①红点

• mid=l+r+1>>1;

  if(check(mid)) true ->[mid,r] l = mid;//mid满足红色性质

  ​ false->[l,mid-1] r = mid-1;//mid不满足红色性质，在绿色性质区域

②绿点

• mid = l+r>>1;

  if(check(mid)) true->[l,mid] r = mid;//mid满足绿色性质

  ​ false->[mid+1,r] l = mid+1;//mid满足红色性质，不满足绿色性质

//mid属于绿色区域
bool check(int x) {/* ... */} // 检查x是否满足某种性质
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用，即如果更新方式是r=mid,l=mid+1;
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足绿色性质
        else l = mid + 1;
    }
    return l;
}

//mid属于红色区域
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用,即如果更新方式是l=mid,r=mid-1;
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;//判断mid是否满足红色性质
        else r = mid - 1;
    }
    return l;
}

浮点数二分

注：判断是否满足绿色性质

bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求，比要求的位数多2
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

二分查找的算法思想

二分查找的实现

//王道书版
typedef struct{//查找表的数据结构（顺序表）
    int *ad;//动态数组基址
    int len;//表的长度
    
}table;
//二分查找
int bi(table l,int key){
    int low=0,high=l.len-1,mid;
    while(low<=high){
        mid=(low+high)/2;//取中间位置
        if(l.ad[mid]==key)
            return mid;//查找成功则返回所在位置
        else if(l.ad[mid]>key)
            high=mid-1;//从前半部分继续查找
        else 
            low=mid+1;//从后半部分继续查找
    }
    reuturn -1;//查找失败，返回-1
}

查找效率分析

二分查找判定树的构造

二分查找的查找效率

7.2.3 分块查找

分块查找的算法思想

//索引表
typedef struct{
    int maxvalue;
    int low,high;
}index;
//顺序表存储实际元素
int list[100];


用二分查找索引

查找效率分析（ASL）

动态查找表

7.3 树形查找

7.3.1 二叉排序树

二叉排序树的定义

二叉排序树的查找

//二叉排序树结点
typedef struct bstnode{
    int key;
    struct bstnode *l,*r;
}bstnode,*bstree;
//在二叉排序树中查找值为key的结点
bstnode *bst_search(bstree t,int key){
    
    while(t!=NULL&&key!=t->key){//若树空或等于根节点值，则结束循环
    
    if(key<t->key)t=t->l;//小于，则在左子树上查找
    else t=t->r;//大于，则在右子树上查找
}
    return t;
}
//在二叉排序树中查找值为key的结点（递归实现）
bstnode *bstsearch(bstree t,int key){
    if(t==NULL)
        return NULL;//查找失败
    if(key==t->key)
        return t;//查找成功
    else if(key<t->key)
        return bstsearch(t->l,key);//在左子树中找
	else 
        retun bstsearch(t->r,key);//在右子树中找
}

二叉排序树插入

//在二叉排序树插入关键字为k的新节点（递归实现）
int insert(bstree &t,int k){
    if(t==NULL){//原树为空，新插入节点为根节点
    t=(bstree)malloc(sizeof(bstnode));
    t->key=k;
        t->l=t->r==NULL;
        return 1;//返回1，插入成功
    }
    else if(k==t->key)//树中存在相同关键字的结点，插入失败
        return 0;
    else if(k<t->key)//插入到t的左子树
		return insert(t->l,k);
    else	//插入到t的右子树
        return insert(t->r,k);
 
}

二叉排序树的构造

//在二叉排序树插入关键字为k的新节点（递归实现）
int insert(bstree &t,int k){
    if(t==NULL){//原树为空，新插入节点为根节点
    t=(bstree)malloc(sizeof(bstnode));
    t->key=k;
        t->l=t->r==NULL;
        return 1;//返回1，插入成功
    }
    else if(k==t->key)//树中存在相同关键字的结点，插入失败
        return 0;
    else if(k<t->key)//插入到t的左子树
		return insert(t->l,k);
    else	//插入到t的右子树
        return insert(t->r,k);
 
}
//按照str[]中的关键字序列建立二叉排序树
void creat(bstree &t,int str[],int n){
    t=NULL;//初始时t为空树
    int i = 0;
    while(i<n){//依次将每个关键字插入到二叉排序树中
    	insert(t,str[i]);
        i++;
    }
}

二叉排序树的删除

查找效率分析

7.3.2 平衡二叉树

平衡二叉树的定义

//平衡二叉树结点
typedef struct node{
    int key;//数据域
    int balance;//平衡因子
    struct node *l,*r;
}node,*tree;

平衡二叉树的插入

调整最小不平衡子树

LL


RR

LR

RL

代码思路

汇总

• 思路
  • 从下而上依次算出新节点的各个祖先的平衡因子

例子

练习1

练习2

练习3

查找效率分析

7.3.3 平衡二叉树的删除

平衡二叉树的插入&删除

平衡二叉树的删除

二叉排序树的删除操作

AVL树删除操作——例1

AVL树删除操作——例2

AVL树删除操作——例3

AVL树删除操作——例4

AVL树删除操作——例6

• 二叉排列树中，一个结点的前驱只需要从左孩子出发，一路往右下走到头即可

• 平衡二叉树的结点的后继是右子树一直往左下走

7.3.4 红黑树的定义和性质

为什么要发明红黑树

红黑树大概会怎么考

红黑树的定义

struct node{//红黑树的结点定义
	int key;//关键字的值
    node *parent;//父节点指针
	node *l;//左孩子指针
	node *r;//右孩子指针
    int color;//节点颜色，如：可用0/1表示黑/红，也可使用枚举型enum表示颜色
}；

实例：一棵红黑树

练习：是否符合红黑树要求

补充概念：结点的黑高

与黑高相关的推论

红黑树的性质

红黑树的查找

7.3.5 红黑树的插入

红黑树的插入

• 非根节点的插入只用考虑是否违反“不红红”

例子

7.3.6 红黑树的删除

红黑树的删除操作

7.4 B树和B+树

7.4.1 B树

B树的定义

B树的高度

7.4.2 B树的插入删除

B树的插入

总结

B树的删除

总结

7.4.3 B+树

B+树

B+树的查找

B+树 vs B树

• 1


• 2

本质在于B+树重一个关键字对应一个分支，二B树当中n个关键字会对应n+1个分支

• 3

• 4

• 5

7.5 散列（hash）表

yxc笔记hash

Hash表

• 存储结构

  • 开放寻址法

  • 拉链法

    

• 字符串哈希

• 作用：把一个比较庞大的空间（值域）映射到比较小的空间，映射后的函数叫做哈希函数

  • x %10^5 ∈(0,10^5)
    • 模的数一般要取成质数，所以一般要遍历寻找最小的质数
  • 冲突：两个不一样的数映射成了同一个数，处理冲突的方式可以分为开放寻址法和拉链法

拉链法

(1) 拉链法
    int h[N], e[N], ne[N], idx;//h[N]是槽，e[N]（值）、ne[N]（下一个位置）是链表
//memset(h,-1,sizeof h)把槽先清空
    // 向哈希表中插入一个数
    void insert(int x)
    {
        int k = (x % N + N) % N;//把余数变成正数，k就是x的哈希值，将x插到k槽的单链表中
        e[idx] = x;//存下x的值
        ne[idx] = h[k];
        h[k] = idx ++ ;//链表插入操作
    }

    // 在哈希表中查询某个数是否存在
    bool find(int x)
    {
        int k = (x % N + N) % N;//求出哈希值定位槽位置
        for (int i = h[k]; i != -1; i = ne[i])//遍历单链表
            if (e[i] == x)//判断该槽链表中是否存在x
                return true;

        return false;
    }

//寻找质数
for(int i =  ; ;i++){
bool flag =true;
for(int j = 2;j*j<=i;j++)
	if(i%j==0){
	flag =false ;
	break;
	}
	if(flag)
	{
	cout<<i<<endl
	break;
	}
}

开放寻址法

• 只开一个数组，但是开的长度一般是输入数据的2-3倍

(2) 开放寻址法
    int h[N];
//需要定义一个不在数据范围内的null，如0x3f3f3f3f，一般设置最大值,INT_MAX也还是0x3f3f3f3f

memset(h,0x3f,sizeof h);//初始化哈希表
    //由于x是int类型，一个int四个字节，相当于4个3f，即0x3f3f3f3f

// 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
    int find(int x)
    {
        int t = (x % N + N) % N;//求哈希值，即映射
        while (h[t] != null && h[t] != x)//t位置上面有人，并且位置上的值不等于x
        {
            t ++ ;//看下一个位置
            if (t == N) t = 0;//看完了最后一个位置，需要循环看第一个位置
        }
        return t;//如果x在哈希表中，返回的就是x的下标，如果x不在哈希表中，返回的就是x应该插入的位置
    }

//插入一个数字
h[find(x)]=x;
//判断数字是否在哈希表中
if(h[find(x)])== null cout<<"No";
else cout<<"Yes";

字符串哈希

字符串前缀哈希法

• 先预处理出所有前缀的哈希

  

  把字符串看成是p进制的数字，每一位上的字母就表示p进制上的每一位数字，然后再取模，就可以把字符串映射到从0到Q-1

  

• A-Z不能映射成0，一般从1开始

• 字符串哈希假定不存在冲突，因此不考虑冲突

• 好处是可以利用前缀哈希算出来任意一个子串的哈希值

• 作用：

  快速判断两个字符串是否相同，哈希值相同，两个字符串相同，如果哈希值不同，则两个字符串不同

核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果

typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64
const int P=131 or 13331 //P进制
// 初始化
p[0] = 1;//p的零次方等于1
for (int i = 1; i <= n; i ++ )
{
    h[i] = h[i - 1] * P + str[i];
    p[i] = p[i - 1] * P;//位数对应的数字，类似于024816
}

// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

哈希表

处理冲突的方法——拉链法

拉链法的小优化

哈希查找

• 装填因子越高，说明哈希表装的越满

常见的散列函数

除留取余法

直接定址法

数字分析法

平方取中法

处理冲突的方法——开放定址法

线性探测法

• 查找操作

• 删除操作

• 查找效率分析（ASL）

平方探测法

• 注意

伪随机序列法

处理冲突的方法——再散列法

第八章 排序

8.1 排序的基本概念

排序算法的评价指标

排序算法的分类

8.2 插入排序

8.2.1 插入排序

插入排序

算法实现

//直接插入排序
void insert(int a[],int n){
    int i,j,tmp;
    for(int i = 1;i<n;i++)//将各元素插入已排好序的序列中
        if(a[i]<a[i-1]){//若a[i]小于前驱
            tmp=a[i];//用tmp暂存a[i]
    for(j=i-1;j>=0&&a[j]>tmp;--j)//检查所有前面已排好序的元素
        a[j+1]=a[j]//将所有大于tmp的元素都向后挪位
        a[j+1]=tmp;
        }
    
}

算法实现（带哨兵）

//直接插入排序（带哨兵）
void insert(int a[],int n){
    int i,j;
    for(i=2;i<=n;i++)//依次将a[2]~a[n]插入到前面已排序序列
	if(a[i]<a[i-1]){//若a[i]的值小于前驱，将a[i]插入有序表
    a[0]=a[i];//复制为哨兵,a[0]不存放元素
        for(j = i-1;a[0]<a[j];--j)//从后往前查找待插入位置
            a[j+1]=a[j];//向后挪威
        a[j+1]=a[0];//复制到插入位置
    }
}

算法效率分析

优化——折半插入排序

//折半插入排序
void insert(int a[],int n){
    int i,j,low,high,mid;
    for(i=2;i<=n;i++){//依次将a[2]~a[n]插入前面的已排序序列
    a[0]=a[i];//将a[i]暂存到a[0]
        low =1;high=i-1;//设置折半查找的范围
        while(low<=high){//折半查找（默认递增有序）
        mid=(low+high)>>1;//取中间点
            if(a[mid]>a[0])high=mid-1;//查找左半子表
            else low=mid+1;//查找右半子表
        
        }
        for(j=i-1;j>=high+1;--j)
            a[j+1]=a[j];//统一后移元素，空出插入位置
		a[high+1]=a[0];//插入操作
    }
}

对链表进行插入排序

8.2.2 希尔排序

希尔排序

算法实现

//希尔排序
void sort(int a[],int n){
    int d,i,j;
    //a[0]知识暂存单元，不是哨兵，当j<=0时，插入位置已到
    for(d=n/2;d>=1;d=d/2)//步长变化
        for(i = d+1;i<=n;i++)
            if(a[i]<a[i-d]){//需要将a[i]插入有序增量子表
            a[0]=a[i];//暂存在a[0]
                for(j=i-d;j>0&&a[0]<a[j];j-=d)
                    a[j+d]=a[j];//记录后移，查找插入的位置
                a[j+d]=a[0];//插入
            }//if
}

算法性能分析

8.3 交换排序

8.3.1 冒泡排序

定义

算法实现

//交换
void swap(int &a,int &b){
    int tmp = a;
    a=b;
    b=tmp;
}
//冒泡排序
void sort(int a[],int n){
    for(inti  = 0 ; i<n-1;i++){
        bool flag= false;//表示本次冒泡是否发生交换的标志
        for(int j = n-1;j>i;j--)//一次冒泡过程
            if(a[j-1]>a[j]){//若为逆序
                swap(a[j-1],a[j]);//交换
			flag=true;
                
            }
        if(flag==false)
            return;//本趟遍历后没有发生交换，说明表已经有序
    }
}

算法性能分析

冒泡排序是否适用于链表

8.3.2 快速排序

• 按照408的原题，一次划分只能确定一个元素的最终位置，而一趟排序可能可以确定多个元素的最终位置

yxc版

快速排序——分治 O(nlogn)-O(n²)

• 确定分界点：q[l],q[(l+r)/2],q[r];随机
• 调整区间：第一个区间所有的数都小于等于x，第二个区间所有的数都大于等于x
• 递归处理左右两端

快排非稳定，归并稳定（位置不发生变化）

暴力做法

• a[],b[]

• q[l-r] q[i]<=x x->a[]

  ​ q[i]>=x x->b[]

• a[]->q[] b[]->q[]

void quick_sort(int q[], int l, int r)
{
if (l >= r) return;
int i = l - 1, j = r + 1, x = q[l + 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]);
   }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

快排的定义

• 快排先排序再递归，归并先递归再排序

快排实现代码（教材版过于狗市，仅截图）

算法效率分析

稳定性

8.4 选择排序

8.4.1 简单选择排序

定义

算法实现

//交换
void swap(int &a,int &b){
    int tmp=a;
    a=b;
    b=tmp;
}
//简单选择排序
void sort(int a[],int n){
    for(int i = 0;i<n-1;i++){//一共进行n-1趟
 		int min=i;//记录最小元素位置
        for(int j = i+1;j<n;j++)//在a[i...n-1]中选择最小的元素
            if(a[j]<a[min])min=j;//更新最小元素位置
        if(min!=i)swap(a[i],a[min]);//封装的swap()函数共移动元素3次
    
    }
}

算法性能分析

稳定性

8.4.2 堆排序

yxc笔记

• 能

  • 插入一个数
  • 求集合当中的最小值
  • 删除最小值
  • 删除任意一个元素
  • 修改任意一个元素

• 堆是一颗完全二叉树，除了最后一层节点外，上面的节点都是满的，最后一层从左到右排列

建堆：

//小根堆：每一个点小于等于左右子节点，根节点是整个数据结构中的最小值，用一维数组来存，stl里的堆是优先队列

建堆时间复杂度解释

堆的高度最高是logn层

• heap_swap示意图

// h[N]存储堆中的值, h[1]是堆顶，x的左子节点是2x, 右子节点是2x + 1
// ph[k]存储第k个插入的点在堆中的位置，即下标
// hp[k]存储堆中下标是k的点是第几个插入的
//hp[]和ph[]互为反函数
int h[N], ph[N], hp[N], size;

// 交换两个点，及其映射关系
void heap_swap(int a, int b)
{
    swap(ph[hp[a]],ph[hp[b]]);//hp[a]即下标是a的点是第几个插入的，hp[b]即下标是b的点是第几个插入的，即hp[a]和hp[b]都是ph[k]中的k，因此ph[hp[a]]和ph[hp[b]]就是找a和b在堆中的位置，swap即交换他们之间的位置，即交换下标 。
    swap(hp[a], hp[b]);//因为堆中的位置发生变化，即他们在堆中的下标也发生变化，相应的hp[k]，即存储堆中下标是k的点是第几个插入的对应数字也发生变化，需要重新匹配，即交换k对应的插入次序
    swap(h[a], h[b]);//交换值
}

void down(int u)//往下调整，时间复杂度O(logn)
{
    int t = u;//t代表三个数中最小值的点坐标
    if (u * 2 <= size && h[u * 2] < h[t]) //判断是否存在左节点，判断左节点是否小于该节点
        t = u * 2;//当左节点小于该节点，将t变成左节点
    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t])//判断右节点是否存在；判断右节点是否小于目前的最小点（如果上面成立，最小点已经更新为左节点） 
        t = u * 2 + 1;
    if (u != t)//说明根节点不是最小值，需要进行交换
    {
        heap_swap(u, t);//将t（保存的最小值的坐标）变成根节点，将t变成原根节点。
        down(t);//将原根节点往下沉进行递归处理直到合适的位置
    }
}

void up(int u)//往上调整，每次往上走只需要跟父节点比较，时间复杂度O(logn)
{
    while (u / 2 && h[u] < h[u / 2])
        //存在父节点；父节点比当前节点大，说明该子节点应该向上
    {
        heap_swap(u, u / 2);//交换父子节点，即原子节点已经变成新的父节点
        u >>= 1;//跳转到新的父节点的坐标，继续进行递归操作
    }
}

// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);//由于从下往上递归，在down的时候可以保证每个根节点的左右节点都是完好无损的

//插入一个数
heap[++size]=x;up(size);

//求当前队列的最小值
heap[1];

//删除一个最小值，即删掉堆顶元素:用整个堆的最后一个元素覆盖掉 ，因为是用数组的形式进行存储，删除数组前面的数比较困难，删除最后一个数比较简单 
heap[1]=heap[size];//用最后一个元素覆盖掉堆顶元素
size--;//删除最后一个元素
down(1);//重新排序堆

//删除任意一个元素
heap[k]=heap[size];//用最后一个元素覆盖掉要删除的元素
size--;//删除最后一个元素
down(k);up(k);//只会执行一个

//修改一个元素
heap[k]=x;
down(k);up(k);

堆的定义

堆排序的定义

建立大根堆

建立大根堆（代码）

//建立大根堆
void heap(int a[],int len){
    for(int i = len/2;i>0;i--)//从后往前调整所有非终端节点
        ad(a,i,len);
}
//将以k为根的子树调整为大根堆
void ad(int a[],int k,int len){
    a[0]=a[k];//将a[0]暂存子树的根节点
    for(int i = 2*k;i<=len;i*=2){//沿key较大的子结点向下筛选
        if(i<len&&a[i]<a[i+1])
            i++;//取key较大的子结点的下标
    if(a[0]>=a[i]) break;//筛选结束
    else{
        a[k]=a[i];//将a[i]调整到双亲结点上
        k=i;//修改k值，以便继续向下筛选
    }
}
    a[k]=a[0];//被筛选节点的值放入嘴中位置
}

基于大根堆进行排序

基于大根堆进行排序（代码）

//建立大根堆
void heap(int a[],int len)
//将以k为根的子树调整为大根堆
void ad(int a[],int k,int len)
//堆排序的完整逻辑
void heap(int a[],int len){
    heap(a,len);//初始建堆
    for(int i = len;i>1;i--){//n-1趟的交换和建堆过程
    	swap(a[i],a[1]);//堆顶元素和堆底元素交换
		ad(a,1,i-1);//把剩余的待排序元素整理成堆
    }
}

算法效率分析

稳定性

8.4.3 堆的插入删除

在堆中插入新元素

在堆中删除元素

8.5 归并排序、基数排序和计数排序

8.5.1 归并排序

yxc

归并排序——分治 O(nlogn)

• 确定分界点：mid=(l+r)/2
• 递归排序left,right
• 归并——合二为一O（n）

void merge_sort(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[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];

}

归并排序的定义

2路归并

4路归并

归并排序（手算模拟）

代码实现

算法效率分析

8.5.2 基数排序

• 基本只考手动模拟不考代码

定义

算法效率分析

• r指的是每一个关键字位有可能取多少种取值
• d指的是关键字可以被拆分成几个部分

稳定性

基数排序的应用

8.7 外部排序

8.7.1 外部排序

外存、内存之间的数据交换

外部排序原理

• 每当一个输入缓冲区空了以后，需要立即把与之对应的那个归并段下一块的内容给读入内存，然后才能接着往下归并

时间开销分析

优化：多路归并

优化：减少初始归并段数量

纠正：什么是多路平衡归并

8.7.2 败者树

多路平衡归并带来的问题

败者树的构造

败者树的使用

败者树在多路平衡归并中的应用

败者树的实现思路

8.7.3 置换-选择排序

土办法

置换-选择排序

• 因为13比14更大，所以把14放到归并段1的末尾

• 这个输出文件FO实际上是在磁盘里的

8.7.4 最佳归并树

归并树的神秘性质

构造2路归并的最佳归并树

多路归并的情况

多路归并的最佳归并树

添加虚段的数量