数据的物理结构
数据存储在存储器当中，而存储器相当于内存而言，而光盘，软盘，硬盘等外部存储器的数据组织通常用文件结构来描述。
数据存储的形式有两种：顺序式和链式。、
算法的五个特征：输入，输出，有穷性，确定性和可行性。

特征解释

输入 0个或者多个

输出一个或者多个输出

有穷性不会无限循环

确定性确定性不会有其他含义

可行性每一步都是可行的
算法的设计要求
1、没有语法错误。
2、算法程序对于合法输入能够产生满足要求的输出。
3、算法程序对于非法输入能产生满足规格的说明。
4、算法对于故意刁难的测试输入都有满足要求的输出结果。

特征	解释
输入	0个或者多个
输出	一个或者多个输出
有穷性	不会无限循环
确定性	确定性不会有其他含义
可行性	每一步都是可行的

可读性
需要便于后续的修改阅读

健壮性
输入不合理时，算法能够有相应的处理，而不是产生异常、崩溃或者莫名奇妙的结果。
时间效率高和存储量

1、时间复杂度

关键在于认识：时间=执行次数 T(n)=O(f(n)); 这样就可以用O来记时间复杂度一般情况下，随着输入规模n的增大，T(n)增长最慢的算法为最优算法。常见的时间复杂度O(1),O(n),O(n^2),O(log(n)),O(nlog(n)),O(n^3),O(2^n),O(n!),O(n^n)

2、空间复杂度

关键在于认识：空间=占用内存一般不关注。

3、线性表

判断方法：如果存在多个元素，且每个元素都有唯一的一个前驱和后继，则该数据结构为线性表。头无前驱，尾无后继。对数据的操作：增删改查。

#include<iostream>
using namespace std;
void test(int value)
{
    value = 2;
    cout << value << endl;
}
int main ( )
{
    int x = 1;
    cout << x << endl;
    test ( x );
    cout << x << endl;
}

这里函数修改了元素值，却没有带回来原因是：传递时，test函数里的x是从main中的x复制过来的，所以修改了x的值，但test函数里的x并没有改变。

如果想将参数的结果带回来，需要传入参数的应用“&”。团队中，自己定义的数据结构如果要让人很方便的使用，自己就必须进行函数封装，方便调用。避免出错。

3.1、顺序表

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

#define maxsize 10 // 定义最大容量
typedef struct
{
    elemtype data[maxsize]; // 定义表类型数组
    int length; // 表当前的长度
}SqList; //顺序表的定义类型 （静态分配的方式）


#include <stdio.h>
#define maxsize 10 // 定义最大容量

typedef struct
{
 int data[maxsize]; // 定义表类型数组
 int length; // 表当前的长度   
}sqlist; //顺序表的定义类型 （静态分配的方式）

void Initlist(sqlist &L) // 初始化顺序表
{
    L.length = 0; // 初始长度为0
}

int getelem(sqlist &L, int i) // 获取元素
{
    if(i < 1> || i>L.length)
     return -1;
    return L.data[i - 1];
}
int main()
{
    sqlist L; // 定义顺序表
    Initlist(L);

/*  
    尝试打印“违规”操作，
    必须使用L.length进行限制
    for (int i = 0; i < maxsize; ++i)
    {
        printf("%d lendth : %d\n", L.data[i], L.length);
    } 
*/
//正确方法
    for (int i = 0; i < maxsize; i++)
    {
        int b = getelem(L,i);
        printf ("%d\n",b);
    }
    return 0;
}

这种分配方式的缺点是：大小无法更改。

就只能采用动态分配的方式。

#define InitSize 5 // 定义初始容量
typedef struct
{
    elemtype *data; // 定义表类型数组
    int MaxSize; // 最大容量
    int length; // 表当前的长度
}SqList; //顺序表的定义类型 （动态分配的方式）

用c实现

#include <stdio.h>
#include <malloc.h>
#define Initsize  100 // 初始化数组大小

typedef struct 
{
    int *data; //指示动态分配数组的指针
    int maxsize; // 数组的最大容量
    int length; // 数组的当前长度
}sqlist;

void Initlist (sqlist &L)
{
    // malloc 函数申请一片连续的存储空间
    L.data = (int *)malloc(Initsize * sizeof(int));
    L.maxsize = Initsize;
    L.length = 0;
}
void Increasize (sqlist &L, int inc)
{
    int *newdata; // 新分配的数组
    if(inc <= 0) return ;
    newdata = (int *)malloc((L.maxsize + inc) * sizeof(int));
    for (int i = 0; i < L.length; ++i)
    {
        newdata[ i ] = L.data[ i ];
    }
    L.data+=inc;
    free(L.data);

}
int main ()
{
    sqlist L;
    Initlist (L) 
    //...........往顺序表种随便插入几个元素
    Increasize (L,5);
    return 0;
}

用c++实现


#include <iostream>
using namespace std;

#define InitSize 10

typedef struct {
    int *data;
    int maxsize;
    int length;
}sqlist ;

int  initlist(sqlist &L)
{
    L.data = new int[InitSize];
    if(L.data == NULL)
    {
        return -1;
    }
    L.maxsize = InitSize;
    L.length = 0;
    return 0;
}
int addlist ( sqlist &L , int x )
{
    if ( L.length >= L.maxsize )
    {
        int* newdata = new int[ L.maxsize + x ];
        for ( int i = 0 ; i < L.length ; i++ )
        {
            newdata[ i ] = L.data[ i ];
        }
        delete [] L.data;
        L.data = newdata;
        L.maxsize += x;
    }
    return 0;
}
void adddate ( sqlist& L , int i )
{
    if(L.length >= L.maxsize)
    {
        return ;
    }
    L.data[L.length] = i;
    L.length++;
}
int getelement ( sqlist& L , int i )
{
    if ( i < 1 || i > L.length )
    {
        return -1;
    }
    return L.data[i - 1];
}
int main()
{
    sqlist L;
    initlist ( L );
    for (int i = 0 ; i < 10 ; i++)
    {
        adddate ( L , i);
    }
    addlist ( L , 1 ); //表增加一个空位
    adddate ( L , 10 );
    int k = -1;
    for (int i = 0 ; i < L.length ; i++)
    {
        k = getelement ( L , i + 1 );
        cout << k  << endl;
    }

    //表释放删除
    //·····
    while(1);
}

顺序表的特点 1、随机访问，时间复杂度为O(1),即通过下标直接访问，效率高。 2、存储密度高，每个节点只存储数据元素。 3、扩展容量不方便（采用动态分配方式实现，时间复杂度较高）。 4、插入、删除操作不方便，需要移动大量的元素。

3-1-2、顺序表的插入

顺序表的插入：

#define Maxsize 10 // 定义顺序表的最大容量
typedef struct {
    elemtype data[Maxsize]; // 存储空间
    int length; // 表当前的长度
}SqList;

void Initlist(SqList &L)
{
    sql.length = 0;
}

bool ListInsert(SqList &L, int i, int e)
{
    if (L.length == Maxsize) return false; // 顺序表已满，不能插入
    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()
{
    SqList L;
    Initlist(L);
    //...............往顺序表种随便插入几个元素
    bool ret = ListInsert(L, 1, 10); // 在第一个元素之前插入一个值为10的元素
    if(ret == true)
        return 0;
    else
        return -1; 
}

顺序表要求插入的时候不能跳跃。

时间复杂度情况最好情况：插入位置在表尾，时间复杂度为O(1)

最坏情况：插入位置在表头，时间复杂度为O(n)

平均情况：插入位置在表中间，时间复杂度为O(n)

顺序表的删除

bool ListDelete(SqList &L, int i, int &e)
{
    if (L.length == 0) return false; // 顺序表为空，不能删除
    if (i < 1 || i > L.length) return false; // 位置参数错误
    e = L.data[i - 1];
    for (int j = i; j <= L.length - 1; ++j) // 删除元素后，将后面的元素全部前移
        L.data[j - 1] = L.data[j];
    L.length--; // 删除一个元素，表长度减1
    return true;
}

int main()
{
    SqList L;
    Initlist(L);
    //...............往顺序表种随便插入几个元素
    int e=-1;
    if(ListDelete(L, 1, e) == true)
    {
        cout << "删除的元素为："<<e;
        return 0;
    }
    else
    {
        return -1;
    }

}

函数的传参，需要确定是否需要将参数返回。不传函数地址或这不取地址，择会重新在内存中复制一份数据。取地址决定着数据是复制一份还是延用一份。

3-1-3、顺序表的查找

顺序表的按位查找 getElem(SqList L, int i) // 按位查找操作。获取表L中第i个元素的值。

静态：

#define Maxsize 10 // 定义顺序表的最大容量
typedef struct {
    Elemtype data[Maxsize]; // 存储空间
    int length; // 表当前的长度
}SqList;

Elemtype getElem(SqList L, int i) // 按位查找操作。获取表L中第i个元素的值。
{
    return L.data[i - 1];
}

动态：

#define InitSize 10 // 定义顺序表的最大容量
typedef struct {
    Elemtype *data; // 存储空间
    int maxsize; // 顺序表的最大容量
    int length; // 表当前的长度
}SqList;

Elemtype getElem(SqList L, int i) // 按位查找操作。获取表L中第i个元素的值。
{
    if (i < 1 || i > L.length)
    {
        return -1; // 位置参数错误，返回-1
    }
    return L.data[i - 1];
    //return *(L.data + i - 1);
}

对于malloc得到的内存空间。可以采用数组的方式来进行访问。访问方法和访问普通数组一样。时间复杂度为O(1)。顺序表随机存取。

顺序表按照值查找： LocateElem(SqList L, Elemtype e) // 按值查找操作。获取表L中第1个值为e的元素位置。

#define InitSize 10 // 定义顺序表的最大容量
typedef struct {
    Elemtype *data; // 存储空间
    int maxsize; // 顺序表的最大容量
    int length; // 表当前的长度
}SqList;

int LocateElem(SqList L, Elemtype e) // 按值查找操作。获取表L中第1个值为e的元素位置。
{
    for (int i = 0; i < L.length; ++i)
        if (L.data[i] == e)
         return i + 1; // 返回该元素在顺序表中的位置
    return 0; // 没有找到
}

基本数据类型：int float double char 都可以用==进行比较。

时间复杂度：最坏情况：O(n) 最好情况：O(1) 平均情况：O(n)

3-2、链表

3-2-1、单链表的定义

顺序表采用顺序储存，单链表采用链式储存。

typedef struct Node { //节点
    Elemtype data; //数据域
    struct Node *next; //指针域
}  Node,*LinkList;

Node * GetElem(LinkList L, int i)
{
    int j = 1;
    Node *p = L->next;
    if (i < 1) return NULL;
    if (i == 1) return L;
    while (p && j < i)
    {
        p = p->next;
        ++j;
    }
    return p; // 返回第i个节点
}
Node *Linklist; // 定义链表,强调链表
Linklist p; // 定义p，强调节点

强调这是一个单链表 Linklist
强调这是一个节点 Node *

不带头节点的单链表初始化方法:


typedef struct Node {
    Elemtype data;
    struct Node *next;
}Node, *LinkList;

bool InitList(LinkList &L) //取地址是因为需要返回一个链表
{
    L = NULL;
    return true;
}

void main()
{
    LinkList L ;
    InitList(L); // 初始化链表
}

//判断单链表是否为空
bool ListEmpty(LinkList L)
{
    return (L == NULL); // 链表为空，返回true
}

带头节点的单链表初始化方法:

typedef struct Node {
    Elemtype data;
    struct Node *next;
}Node, *LinkList;

bool InitList(LinkList &L) //取地址是因为需要返回一个链表
{
    L = (Node *)malloc(sizeof(Node)); // 初始化头节点
    if (!L) return false;
    L->next = NULL;
    return true;
}

void main()
{
    LinkList L;
    InitList(L); // 初始化链表
}

//判断单链表是否为空
bool ListEmpty(LinkList L)
{
    return (L->next == NULL); // 链表为空，返回true
    // 链表为空，返回true
}

链表不带头节点，操作比较麻烦。

3-2-2、单链表的插入和删除

带头节点（按位序插入）

不带头节点（按位序插入）
指定的结点后插入操作

与后面插入操作相比

指定节点的前插操作 - 1

bool InsertElem(LinkList L, Node *p,ElemTyep e) //前插操作：在节点p的前面插入值为e的节点 ，L位表头指针
然后遍历插入。
时间复杂度：O(1)

指定节点的前插操作 - 2 (节点没办法跑路。但是数据可以跑路)

bool InsertPriorNode(Lnode *p, Elemtype e) // 前插操作：在节点p的前面插入值为e的节点
{
    if(p == NULL)
    {
        return false; // 参数错误，返回false
    }
    Node *s = (Node *)malloc(sizeof(Node)); // 生成新节点
    if (!s) 
    {
         return false; // 内存分配失败，返回false
    }
    s-next = p->next; // 插入节点
    p->next = s; // 将新节点连接到p的后面
    s->data = p->data; // 讲p的数据赋值给s
    p->data = e; // 将p的数据赋值给e
    return true; // 插入成功，返回true
}

时间复杂度：O(1)

直接传节点方式--原理和带跑数据一样

bool InsertPriorNode(Lnode *p, Node *s) // 前插操作：在节点p的前面插入值为e的节点
{
    if(p == NULL || s == NULL)
    {
        return false; // 参数错误，返回false
    }
    s->next = p->next; // 插入节点
    p->next = s; // 将新节点连接到p的后面
    Elemtype temp = s->data; // 保存数据
    s->data = p->data; // 将p的数据赋值给s
    p->data = temp; // 将s的数据赋值给p
    return true; // 插入成功，返回true

按位序删除（带头节点）

typedef struct Node {
    Elemtype data;
    struct Node *next;
}Node, *LinkList;
bool ListDelete(LinkList &L, int i,Elemtype &e) // 按位序删除操作,
{
    if( i < 1 )
    {
        return false; // 参数错误，返回false
    }
    Node *p ;// 定义p，指向链表的第i-1个结点
    int j = 0; //当前p的位序
    p = L; // 指向头节点
    while(p! = NULL && j < i-1) // 找到第i-1个结点
    {
        p = p->next; // 指针后移
        ++j;
    }
    if(p ==NULL)
        return false; // 参数错误，返回false
    if(p->next == NULL) //第i-1个结点为尾节点，返回false
        return false; // 参数错误，返回false
   Node *q = p->next; // 定义q，指向第i个结点
   e = q->data; // 将第i个结点的数据赋值给e
   p->next = q->next; // 删除第i个结点
   free(q); // 释放第i个结点
   return true; // 删除成功，返回true
}

第二个办法，和带着数据跑插入一样这次是往要删除的后一个节点的数据赋值到前一个节点，然后删除后一个节点，这样数据就跑到前一个节点了。

bool ListDelete(node *p) // 按位序删除操作,
{
    if(p == NULL || p->next == NULL) //第i-1个结点为尾节点,只能从表头开始遍历
    {
        return false; // 参数错误，返回false
    }
    Node *q = p->next; // 定义q，指向第i个结点
    p->data = q->data; // 将第i个结点的数据赋值给e
    p->next = q->next; // 删除第i个结点
    free(q); // 释放第i个结点
    return true; // 删除成功，返回true
}

3-2-3、单链表的查找

1、按位查找


/// 按位查找操作,返回第i个结点的数据（带头节点）
Node *GetElem(LinkList L, int i) // 按位序查找操作
{
    if(i < 0)
    {
        return NULL; // 参数错误，返回NULL
    }
    Node *p; //指针p指向当前扫描到的节点
    int j=0; //当前p指向第几个节点
    p=L; // 指向头节点
    while(p != NULL && j < i) // 找到第i个结点
    {
        p = p->next; // 指针后移
        ++j;
    }
    
    return p; // 返回第i个结点
}

平均时间复杂度：O(n)

2、按值查找

/// 按值查找操作,返回值为e的结点（带头节点）
Node *LocateElem(LinkList L, Elemtype e) // 按值查找操作
{
    Node *p; // 定义指针p，指向当前扫描到的节点
    p=L->next; // 指向头节点
    while(p != NULL && p->data != e) // 链表不为空
    {
        p = p->next; // 指针后移
    }
    return p; // 返回值为e的结点
}

3-2-4、单链表的建立

3-2-4-1、尾插法

方法：创立一个头节点。设置一个指针，永远指向尾节点。

bool InsertNewElem(Node *p, Elemtype e) // 尾插操作
{
    if(p == NULL)
    {
        return false; // 参数错误，返回false
    }
    Node *s = (Node *)malloc(sizeof(Node)); // 生成新节点
    s->data = e; // 将e赋值给新节点
    s->next = p->next; // 将新节点连接到p的后面
    p->next = s; // 将新节点连接到p的后面
    return true; // 插入成功，返回true
}

尾插法建立单链表：初始化链表设置变量Length记录链表长度 while 循环{ 每次取一个数据e LIstInsert(L, Length++, e);插入尾部 length++ }

3-2-4-2、头插法

方法：对头节点进行后插操作。(元素逆序)

//
Linklist List_Headinsert(LinkList &L) //逆向建立单链表
{
    LNode *s;
    int x;
    L = (Node *)malloc(sizeof(Node)); // 生成头节点
    L->next = NULL; // 头节点无前驱
    while(scanf("%d", &x) != EOF) // 输入数据
    {
        s = (Node *)malloc(sizeof(Node)); // 生成新节点
        s->data = x; // 将x赋值给新节点
        s->next = L->next; // 将新节点连接到L的后面
        L->next = s; // 将新节点连接到L的后面

    }
    return L; // 返回头节点

}

3-2-5、双链表

typedef struct DNode {
    Elemtype data;
    struct DNode *prior, *next; // 前驱和后继指针
}DNode, *DLinkList;
//注意 DNode *L和DLinkList L等价,只是强调的东西不同

bool InitList_DL(DLinkList &L) // 初始化操作
{
    L = (DNode *)malloc(sizeof(DNode)); // 生成头节点
    if(!L)
        return false; // 内存分配失败，返回false
    L->prior = NULL; // 头节点永远指向NULL
    L->next = NULL; // 头节点后暂时没有节点
    return true; // 初始化成功，返回true
}
//判断双连边表是否为空（带头节点）
bool Empty_DL(DLinkList L) // 判断操作
{
    if(L->next == NULL) // 链表为空，返回true
        return true; // 链表为空，返回true
        return false; // 链表不为空，返回false
}
void main()
{
    DLinkList L; //不带星强调链表,带星强调节点
    InitList_DL(L); //初始化链表


}

3-2-5-1、双链表的插入

bool ListInsert_DL(DNode *p, DNode *s) // 在p节点后插入s节点
{
    if(p == NULL || s == NULL)  // 参数错误，返回false
        return false;

    s->next = p->next; // 将s节点连接到p的后面
    if(p->next != NULL) //p不为尾节点
        p->next->prior = s; //将s节点连接到p的后面

    s->prior = p; // 将p节点赋值给s的前驱
    p->next = s; // 将p节点赋值给s的前驱

    return true; // 插入成功，返回true

}


有点绕，看图理解

3-2-5-2、双链表的删除


bool Delete_DL(DNode *p) // 删除p节点后的q节点
{
    if(p == NULL) // 参数错误，返回false
        return false;
    DNode *q = p->next; // 定义指针q指向p的后继
    if(q == NULL) // p为尾节点，返回false
        return false;
    p->next = q->next; // 将q节点连接到p的后面
    if(q->next != NULL) // q不为尾节点
        q->next->prior = p; // 将p节点连接到q的后面
    free(q); // 释放节点
    return true; // 删除成功，返回true

}

双链表销毁

void DestroyList_DL(DLinkList &L) // 销毁操作
{
    DNode *p, *q;
    p = L->next; // 定义指针p指向头节点
    while(p != NULL) // 链表不为空
    {
        q = p->next; // 定义指针q指向p的后继
        free(p); // 释放节点
        p = q; // 指针后移
    }
    L->next = NULL; // 头节点后暂时没有节点
}

3-2-5-3、双链表的遍历

//向后遍历
    while(p != NULL) // 链表不为空
    {
        p = p->next; // 指针后移
    }

//向前遍历
    while(p != NULL) // 链表不为空
    {
        p = p->prior; // 指针后移
    }
    //向前遍历（跳过带头节点）
    while(p->prior != NULL) // 链表不为空
    {
        p = p->prior; // 指针后移; 
    }

3-2-6、循环链表

循环链表有两种，循环单链表和循环双链表。循环单链表常用操作尾部节点的next指向头节点

判断空

bool Empty_CL(LinkList L) // 判断操作
{
    if(L->next == L) // 链表为空，返回true
        return true; // 链表为空，返回true
    return false; // 链表不为空，返回false
}

判断是不是表尾节点


bool Last_CL(LinkList L, LinkList p) // 判断操作
{
    if(p->next == L) // p是尾节点，返回true
        return true; // p是尾节点，返回true
    return false; // p不是尾节点，返回false
}

循环双链表操作

初始化

bool InitList_CL(LinkList &L) // 初始化操作
{

    L = (Node *)malloc(sizeof(Node)); // 生成头节点
    if(!L)
        return false; // 内存分配失败，返回false
    L->next = L; // 尾节点指向自己
    L->prior = L; // 前驱节点指向自己
    return true; // 初始化成功，返回true
}

判断空

bool Empty_CL(LinkList L) // 判断操作
{
    if(L->next == L) // 链表为空，返回true
        return true; // 链表为空，返回true
    return false; // 链表不为空，返回false
}

插入

bool ListInsert_CL(Dnode *p, Dnode *s) // 在p节点后插入s节点
{
    if(p == NULL || s == NULL)  // 参数错误，返回false
        return false;
    s->next = p->next; // 将s节点连接到p的后面
    p->next->prior = s; //将s节点连接到p的后面
    s->prior = p; // 将p节点赋值给s的前驱
    p->next = s; // 将p节点赋值给s的前驱
    return true; // 插入成功，返回true
}

删除

bool Delete_CL(Dnode *p) // 删除p节点后的q节点
{
    if(p == NULL) // 参数错误，返回false
        return false;
    Dnode *q = p->next; // 定义指针q指向p的后继
    p->next = q->next; // 将q节点连接到p的后面
    q->next->prior = p; // 将p节点连接到q的后面
    free(q); // 释放节点
    return true; // 删除成功，返回true
}

3-2-7、静态链表


#define MAXSIZE 100
typedef int Status; // 状态码
typedef int SElemType; // 存储元素类型

// 静态链表结构体
typedef struct
{
    SElemType data; // 数据域
    int cur; // 当前位置标志
}SLinkList[MAXSIZE];

4、栈

栈:只允许在一端进行插入和删除操作的线性表，后进先出LIFO(Last In First Out) 术语：栈顶top和栈底base，空栈：top == base 基本操作： 1、初始化：分配栈空间 2、销毁：释放栈空间 3、入栈：将元素压入栈顶 4、出栈：将元素从栈顶弹出 5、读栈顶：读栈顶元素 6、判空：判断栈是否为空

4-1、顺序栈

代码中声明结构体，或者变量，就是开辟内存空间

#define MAXSIZE 100
typedef struct
{
    SElemType data[MAXSIZE]; // 存储空间
    int top; // 栈顶指针
}SqStack;

初始化

void InitStack_Sq(SqStack &S) // 初始化操作
{
    S.top = -1; // 栈顶指针置-1
}

判空

bool Empty_Sq(SqStack S) // 判断操作
{
    if(S.top == -1) // 栈为空，返回true
        return true; // 栈为空，返回true
    return false; // 栈不为空，返回false
}

判满

bool Full_Sq(SqStack S) // 判断操作
{
    if(S.top == MAXSIZE - 1) // 栈满，返回true
        return true; // 栈满，返回true
    return false; // 栈不满，返回false
}

入栈

bool Push_Sq(SqStack &S, SElemType e) // 入栈操作
{
    if(S.top == MAXSIZE - 1) // 栈已满，返回false
        return false; // 栈已满，返回false
    S.data[++S.top] = e; // 栈顶指针后移，将元素压入栈顶
    return true; // 入栈成功，返回true
}

出栈

bool Pop_Sq(SqStack &S, SElemType &e) // 出栈操作
{
    if(S.top == -1) // 栈为空，返回false
        return false; // 栈为空，返回false
    e = S.data[S.top--]; // 栈顶指针前移，将元素弹出
    return true; // 出栈成功，返回true
}

读栈顶

bool GetTop_Sq(SqStack S, SElemType &e) // 读栈顶操作
{
    if(S.top == -1) // 栈为空，返回false
        return false; // 栈为空，返回false
    e = S.data[S.top]; // 将栈顶元素赋值给e
    return true; // 读栈顶成功，返回true
}

4-1-1、共享栈

typedef struct
{
    SElemType data[MAXSIZE]; // 存储空间
    int top0;
    int top1; // 队头和队尾指针
}SqQueue;

初始化

void InitStack_Sq(SqQueue &Q) // 初始化操作
{
    Q.top0 = -1; 
    Q.top1 = MAXSIZE; 
}

内存增长方向相反

4-2、链栈

使用链表的一段进行插入，或者删除操作，实现栈操作。

5、队列

5-1、顺序队列

队列：只允许在一端进行插入，在另一端删除的线性表，先进先出FIFO(First In First Out) 术语：队头head和队尾tail，空队列：head == tail 基本操作： 1、初始化：分配栈空间 2、销毁：释放栈空间 3、入队：将元素压入队尾 4、出队：将元素从队首弹出 5、读队首：读队首元素 6、判空：判断栈是否为空

#define MAXSIZE 100
typedef struct
{
    SElemType data[MAXSIZE]; // 存储空间
    int front; // 队首指针
    int rear; // 队尾指针
}SqQueue;

判空

bool Empty_Sq(SqQueue Q) // 判断操作
{
    if(Q.front == Q.rear) // 队为空，返回true
        return true; // 队为空，返回true
    return false; // 队不为空，返回false
}

入队

bool EnQueue_Sq(SqQueue &Q, SElemType e) // 入队操作
{
    if((Q.rear + 1) % MAXSIZE == Q.front) // 队已满，返回false，运用中，会浪费一个存储空间
        return false; // 队已满，返回false
    Q.data[Q.rear] = e; // 将元素压入队尾
    Q.rear = (Q.rear + 1) % MAXSIZE; // 队尾指针后移,相当于一个循环队列
    return true; // 入队成功，返回true
}

利用取余运算，实现循环队列。逻辑上实现闭环

出队

bool DeQueue_Sq(SqQueue &Q, SElemType &e) // 出队操作
{
    if(Q.front == Q.rear) // 队为空，返回false,和入队的条件不同，要注意区分
        return false; // 队为空，返回false
    e = Q.data[Q.front]; // 将队首元素赋值给e
    Q.front = (Q.front + 1) % MAXSIZE; // 队首指针后移,相当于一个循环队列
    return true; // 出队成功，返回true
}

另一种判断队空的方法

#define MAXSIZE 100
typedef struct
{
    SElemType data[MAXSIZE]; // 存储空间
    int front; // 队首指针
    int rear; // 队尾指针
    int flag; // 标志位,最后一次是入队还是出队
}SqQueue;

5-2、链队列

使用链表的一段进行插入，或者删除操作，实现栈操作。回顾之前的链表，要标记一个链表，只需要保存链表的头指针就可以了。遍历，查询等，这个指针不要动。使用另一个指针，来遍历链表。

带头结点

tyepdef struct QNode
{
    SElemType data;
    struct QNode *next;
}QNode, *QueuePtr;

typedef struct
{
    QNode *front; // 队首指针
    QNode *rear; // 队尾指针
}LinkQueue;
/* 初始化 */
bool InitQueue(LinkQueue *Q)
{
    Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));
    if(!Q->front) // 分配失败，返回false
        return false; // 分配失败，返回false
    Q->front->next = NULL; // 队空，队首指针指向NULL
    return true; // 初始化成功，返回true
}
/* 判断空 */
bool IsEmpty()
{
    if(Q->front == Q->rear) // 队空，返回true
        return true; // 队空，返回true
    return false; // 队不空，返回false
}
/* 新元素入队 */
void EnQueue(LinkQueue *Q, SElemType e)
{
    QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
    if(!s) // 分配失败，返回false
        return; // 分配失败，返回false
    s->data = e; // 赋值
    s->next = NULL; // 队尾指针指向NULL
    Q->rear->next = s; // 队尾指针指向新节点
    Q->rear = s; // 队尾指针指向新节点
    return; // 入队成功，返回true
}
/* 带头节点的链队首元素出队 */
bool DeQueue(LinkQueue *Q, SElemType &e)
{
    if(Q->front == Q->rear) // 只有一个元素，
        return false; // 头节点，返回false
    QueuePtr *p = Q->front->next; // 队首指针
    e = p->data; // 队首元素赋值给e
    Q->front->next = p->next; // 队首指针指向下一个节点
    if(Q->rear == p) // 只有一个元素，队尾指针指向NULL
        Q->rear = Q->front; // 只有一个元素，队尾指针指向NULL
    free(p); // 释放节点
    return true; // 出队成功，返回true
        


}
void main()
{
    LinkQueue Q;
    InitQueue(&Q); // 初始化操作
}

不带头节点

/* 初始化 */
void InitQueue(LinkQueue *Q)
{
    Q->front = NULL; // 队空，队首指针指向NULL
    Q->rear = NULL; // 队尾指针指向NULL
}
/* 判空*/
bool IsEmpty(LinkQueue Q)
{
    if(Q.front == NULL) // 队空，返回true
        return true; // 队空，返回true
    return false; // 队不空，返回false

}

/* 入队  */
void EnQueue(LinkQueue *Q, QElemType e)
{
    QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
    if(!s) // 分配失败，返回false
        return; // 分配失败，返回false
    s->data = e; // 赋值
    s->next = NULL; // 队尾指针指向NULL
    if(Q->front == NULL) // 队空，队首指针指向新节点
    {

        Q->front = s;
        Q->rear = s; // 队尾指针指向新节点
    }
    else // 队不空，队尾指针指向新节点
    {
        Q->rear->next = s;
        Q->rear = s; // 队尾指针指向新节点
    }
        return; // 入队成功，返回true
}

/* 出队操作 */
bbool DeQueue(LinkQueue *Q, QElemType &e)
{
    if(Q->front == NULL) // 队空，返回false
        return false; // 队空，返回false
    QueuePtr p = Q->front; // 队首指针
    e = p->data; // 队首元素赋值给e
    Q->front = p->next; // 队首指针指向下一个节点
    if(Q->rear == p) // 只有一个元素，队尾指针指向NULL
    {
        Q->rear = NULL; // 只有一个元素，队尾指针指向NULL
        Q->front = NULL; // 只有一个元素，队首指针指向NULL
    }
    
    free(p); // 释放节点
    return true; // 出队成功，返回true
}

5-3、双端队列

有多种形式，双端队列：只允许从两端插入、两端删除的线性表。输入受限的双端队列：只允许一端插入，两端的删除操作。输出受限的双端队列：只允许一端删除，两端的插入操作。

6、栈在括号匹配中的应用

IDE：可视化编程环境

#define MAXSIZE 100
typedef struct
{
    SElemType data[MAXSIZE]; // 存储空间
    int top; // 栈顶指针
}SqStack;
bool bracketCheck(char str[],int length)
{
    SqStack S;
    InitStack(&S);//初始化栈
    for(int i=0;i<length;i++)
    {
        if(str[i] == '(' || str[i] == '[' || str[i] == '{')
            Push(&S,str[i]); // 入栈
        else if(str[i] == ')')
        {
            if(S.top == -1) // 栈空，返回false
                return false; // 
        }
        char topElem = pop(&S); // 获取栈顶元素
        if(str[i] == ')' && topElem != '(') // 栈顶元素不匹配，返回false
            return false; // 
        if(str[i] == ']' && topElem != '[') // 栈顶元素不匹配，返回false
            return false; // 
        if(str[i] == '}' && topElem != '{') // 栈顶元素不匹配，返回false
            return false; // 
    }
    if(S.top != -1) // 栈不空，返回false
        return false; // 

    return true; // 括号匹配，返回true
}

7、队列在括号匹配中的应用

表达式：由操作数、运算符和界限符组成的序列。

8、栈在递归中的应用

函数调用的特点：最后调用的函数最先返回。也就符合栈的先进后出特点。函数调用时，需要用栈来保存现场信息。

调用返回地址
函数参数
局部变量

9、队列应用

在操作系统中，进程调度算法：先来先服务、短作业优先、时间片轮转。在树中，先序遍历、中序遍历、后序遍历。也是用队列来实现的。

10、特殊矩阵的压缩存储

一维数组存储结构：线性储存。
二维数组存储结构：行优先存储、列优先存储。都是线性。知道行号和列号，能直接得出地址。

矩阵：使用数组存储特殊矩阵： 1、对称矩阵：对角线元素相同。策略：只存储对角线元素+下三角元素。按行优先存储或者列优先存储。

2、三角矩阵：上三角元素和下三角元素都为0。

3、对角矩阵：主对角线元素为1，其他元素为0。同样用一维数组存储。

4、稀疏矩阵：元素个数远小于n*m。两种方法存储：顺序存储三元组、链式存储十字链表。

11、串

串：就是字符串，由0个或多个字符组成的有限序列。串名：字符串的名称，是串的首地址。串的长度：串中字符的个数。空串：长度为0的串，空格也算字符。有空格不算空串。子串：串中任意个连续的字符组成的串。子串在主串中出现的位置：子串第一个字符在主串中的位置。存储时以线性的方式存储。主要操作：假设有串T="",S="iphone 11 pro Max",W = "pro" StrAssign(T,s)：将串s赋值给串T。 StrEmpty(T)：判断串T是否为空串。 StrLength(T)：求串T的长度。 StrCopy(T,S)：将串S复制给串T。 ClearSring(T)：清空串T。 DestoryString(T)：销毁串T。 Concat(T,S1,S2)：将串S1和S2连接起来，生成新串T。 SubString(&Sub,S,i,j)：求子串Sub，其值等于主串S中从第i个字符开始的子串。 Indext(S,T)：返回串S中与串T相等的第一个子串的起始位置。否则返回0。 StrCompare(S,T)：比较串S和串T的大小关系，逐个字符比较，直到出现大小关系为止。以ASCCII码值大小比较。每个字符的ASCCII码值大小关系。

字符集

英文和控制符：ASCCII码值。一个字符占1个字节。
中英文：Unicode码值。一个字符占3个字节。基于同一种码值，不同编码方式，有uft-8、utf-16、utf-32。

11-1、串的存储结构

下面11-2采用第四种方法。

顺序存储

#define MAXSIZE 100
typedef struct
{
    char data[MAXSIZE]; // 存储空间
    int length; // 串的长度
}SqString;

顺序存储、堆区

#define MAXSIZE 100
typedef struct Node
{
    char *ch; // 存储空间
    int length; // 串的长度
}LinkNode, *LinkString;

Hstring S;
S.data = (char *)malloc(sizeof(char) * MAXSIZE); // 分配空间
S.length = 0;

链式存储

tyoedef struct StringNode
{
    char ch[i];//每个节点存储i个字符，提高内存利用率。内存密度。
    struct StringNode *next;
}StringNode, *LinkString;

11-2、顺序串的功能实现

Substring(&sub,S,i,j)：求子串Sub，其值等于主串S中从第i个字符开始,长度为j的子串。假设S.ch = "yanggguanchao" S.length = 14

#define MAXSIZE 100 // 串的长度
typedef struct
{
    char ch[MAXSIZE]; // 存储空间
    int length; // 串的长度
}String;

bool Substring(String &sub,String S,int i,int j)
{
    /*这里的主串从1开始 , 0用来保存长度*/
    if(i+j - 1 > S.length) // 越界，返回
        return false; // 
    for(int k = i; k <= i+j; k++)
        Sub.ch[k-i +1] = S.ch[k]; 
    sub.length = j; // 
    return true; // 

}

比较串S和串T的大小关系,若S>T，逐个字符比较，直到出现大小关系为止。以ASCCII码值大小比较。

int StrCompare(String S,String T)
{
    for(int i = 0; i < S.length && i < T.length; i++)
    {
        if(S.ch[i] != T.ch[i]) // 比较字符ASCCII码值大小
            return = S.ch[i] - T.ch[i]; // 
    }
    return S.length - T.length; // 
}

找子串在主串中出现的位置

int Index(String S,String T)
{
    int i = 0;
    int n = StringLength(S);
    int m = StringLength(T);
    while(i <= n - m + 1){
        Substring(Sub,S,i,m); 
        if(StrCompare(Sub,T) != 0)
            i++;
        else 
            return i; // 返回位置
    }
    return 0; //S中没有T串
}

11-3、串的模式匹配

朴素模式暴力匹配算法子串：一定或者没有在主串中模式串：找到的不一定是你想要的

上一节的子串匹配算法，在主串中找子串。即使一个朴素模式匹配算法。

通过数组下标，进行匹配。主串指针在头处，模式串指针

int Index(String S,String T)
{
    int i = 0;
    int j = 0;
    while(i <= S.length - T.length)
    {
        ++j;
        ++i;
    }
    else
    {
        i=i-j+2;//这里字符位置是从1开始，所以要减2，串结构，下标0舍弃
        j = 1；
    }
    if(j > T.length)
        return i - T.length; // 返回位置
    else
        return 0; // S中没有T串
}

11-4、KMP算法

是对朴素模式匹配算法的改进。主串指针不返回，模式串指针返回扫描过的位置放到数组中。当发生某一位不匹配，模式串指针返回该位置

求next数组

//求模式串T的next数组
void getNext(String T,int next[])
{
    int i = 1;
    int j = 0;
    next[1] = 0;
    while(i < T.length)
    {
        if(j == 0 || T.ch[i] == T.ch[j])
        {
            ++i;
            ++j;
            //若pi = pj，则next[i+1] = next[j+1]
            next[i] = j; // 
        }
        else
            j = next[j]; // 
    }
}

int Index_KMP(String S,String T)
{
    int i = 1;
    int j = 1;
    get_next(T,next); // 求next数组
    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; // S中没有T串
}

12、树

根节点：开始节点。叶子节点：没有子节点的节点。边：连接节点。分支节点：有子节点的节点。空树：没有节点的树。

非空树：

有节点的树。有且只有一个根节点。
没有后继的节点称之为“叶子节点”
有后继的节点称之为“分支节点”

树：由n（n>=0）个节点组成的有限集合。n=0时，称为空树。任意一个非空树m，有且仅有一个根节点。任何一个节点都有仅且只有一个父节点。

树形结构应用

文件系统
国家省市县区镇村

有序树：从逻辑上看，树中结点的各个子树从左到右是有次序的，不能互换。无序树：从逻辑上看，树中结点的各个子树从左到右是无次序的，可以互换。

12-1、二叉树

定义二叉树：每个节点最多有两个子树的树结构。
二叉树的性质 1、二叉树的深度为k，则最多有2^k-1个结点。 2、左右树不能互换。有序树。

几种特殊的二叉树：

平衡二叉树：左右子树的高度差不超过1。效率很高

12-2、二叉树的存储结构

顺序存储结构：用一维数组存储二叉树。（能快速访问，但是会浪费存储空间）链式存储结构：用指针域存储二叉树。

//链式存储结构
typedef struct {
    int data; /* 数据域 */
    BiTNode *lchild, *rchild; /* 左右孩子指针 */
}BiTNode, *BiTree;

int main()
{
    //创建二叉树
    BiTree root;
    root = (BiTNode *)malloc(sizeof(BiTNode)); // 申请节点空间

    //初始化二叉树
    root->data = 1;
    root->lchild = NULL;
    root->rchild = NULL;

    //创建左子树
    BiTNode *left = (BiTNode *)malloc(sizeof(BiTNode)); // 申请节点空间
    left->data = 2;
    left->lchild = NULL;
    left->rchild = NULL;
    root->lchild = left; // 链接左子树

}

在实际过程中，如果二叉树查找父节点很费时间，可以设置一个指针域，指向父节点。

struct BiTNode
｛
    ElemType data;
    结构体指针 left;
    结构体指针 right;
    结构体指针 parent;
}

12-3、二叉树的遍历

先序遍历： 1、若二叉树为空，则返回空操作； 2、若二叉树非空：（1）访问根节点；（2）先序遍历左子树；（3）先序遍历右子树。

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

//先序遍历
void PreOrder(BiTree T)
{
    if(T != NULL)
    {
        visit(T); // 访问节点
        PreOrder(T->lchild); // 遍历左子树
        PreOrder(T->rchild); // 遍历右子树
    }
}

中序遍历： 1、若二叉树为空，则返回空操作； 2、若二叉树非空：（1）中序遍历左子树；（2）访问根节点；（3）中序遍历右子树。

void InOrder(BiTree T)
{
    if(T != NULL)
    {
        InOrder(T->lchild); // 遍历左子树
        visit(T); // 访问节点
        InOrder(T->rchild); // 遍历右子树
    }
}

后序遍历： 1、若二叉树为空，则返回空操作； 2、若二叉树非空：（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根节点。

viod PostOrder(BiTree T)
{
    if(T != NULL)
    {
        PostOrder(T->lchild); // 遍历左子树
        PostOrder(T->rchild); // 遍历右子树
        visit(T); // 访问节点
    }
}

12-4、二叉树的层序遍历

算法描述 1、创建一个队列Q，并将根节点入队； 2、根节点入队后 3、若队列非空，则队头元素出队，访问该节点；并判断该节点的左右孩子是否为空，若非空，则将该节点入队； 4、循环3，直到队列为空。

#include <stdio.h>
void LevelOrder(BiTree T)
{
    LinkQueue Q;//创建队列
    InitQueue(&Q);//初始化队列
    BiTree p;
    EnQueue(&Q, T); //根节点入队
    while(!QueueEmpty(Q))
    {
        DeQueue(&Q, &p); //队头元素出队
        visit(p); //访问该节点
        if(p->lchild != NULL)
            EnQueue(&Q, p->lchild); //左孩子入队
        if(p->rchild != NULL)
            EnQueue(&Q, p->rchild); //右孩子入队

    }
    return;
}

12-5、根据几种遍历序列重建二叉树

中序遍历序列和其他三种方式任意结合一种，都可以唯一确定一棵二叉树。但是不用中序遍历，其他两种结合无法确定一棵二叉树。

12-6、线索二叉树

普通二叉树找前驱后继比较麻烦。

// 创建线索二叉树
typede struct BiTNode{
    ElemType data;
    struct BiTNode *lchild, *rchild;
    int ltag, rtag; // 左右标志

}BiTNode, *BiTree;

12-7、二叉树线索化，对visit函数进行实现

线索化先要对二叉树进行一次完整遍历。

中序线索化完整代码如下：

先序线索化代码：

后续线索化代码：

12-8、二叉树中序找后继和前驱

12-9、树的存储

二叉树的顺序存储，使用数组存储，至于链式存储在上面已经讲过了。

其他树：二叉树也可以以用这个方法存储。

孩子表示法：顺序+链式存储:

兄弟孩子表示法：链式存储:

树和二叉树的转化：

森林转化成二叉树：

12-10、树的遍历

树的先根遍历，实现后达到树和二叉树的转化:

树的后续遍历，实现二叉树和树的转化:

树的层序遍历：

12-11、哈夫曼树

节点的权：节点上数据所表示的某种信息量。节点的带权路径长度：从根节点到该节点的路径长度与该节点上数据的乘积。哈夫曼树：带权路径长度最小的二叉树。也称为最优二叉树。

应用：哈夫曼编码。（可变长度编码）一般的ascii码是定长编码，一个字节8位。哈夫曼编码：将字符按照出现频率从高到低排序，然后两两合并，合并后字符频率和合并前字符频率之和就是合并后字符频率。