[数据结构与算法]数据结构与算法

数据结构

数据

定义 :是能输入计算机而且能被计算机处理的各种符号的集合

• 数据是信息得载体
• 是对客观事物符号化得表示
• 是能够被计算机识别、存储和加工

数据元素

• 是数据的基本单位，在计算机程序中通常作为一个整体考虑和处理
• 也称为元素 或记录 结点 或顶点
• 数据元素可以由若干个数据项组成

数据项

• 构成数据元素不可以分割的最小单位 具有独立含义不额、可分割

  三者的关系 数据 > 数据元素 > 数据项

? 列 学生表 > 个人记录 > 学号、姓名

数据对象

• 是性质相同的数据元素的集合 是数据的一个子集

数据元素与数据对象

• 数据元素 组成数据的基本单位
  • 与数据的关系:是集合的 个 体
• 数据对象 性质相同的数据元素的集合
  • 与数据的关系是 ：集合的子集

数据结构

? 定义 ： 是数据元素之间存在一种或多种特定关系的数据元素集合

• 逻辑结构

  定义 ：是数据元素间的关系

  • 集合 各个元素同属一个集合 别无其他关系
  • 线性结构 数据元素之间存在 一对的一的关系 除第一个元素 所有的元素都有前驱 除了最后一个元素 所有元素都有后继 没有前驱元素的的节点我们称为开始元素 没有后继元素的则称这个元素为终端元素
  • 树形结构 树形元素存在一对多的关系
  • 图状结构(网状结构) 存在多对多的元素

• 物理结构 （存储结构）

  定义:逻辑结构在物理内存中的映像

  • 顺序存储 用一组连续存储单元依次存储数据元素 数据元素 之间的逻辑关系由元素的存储位置来表示 c语言中用数组来实现表示
  • 链式存储 用一组任意的存储单元存储数据元素 数据元素之间的逻辑关系用指针来表示
  • 索引存储 在存储元素信息的同时 还建立附加的索引表 索引表中的每项称为索引项 索引项的一般形式是（关键词 地址） 关键字是能唯一标识一个元素的数据项
  • 散列存储 根据元素的关键字可以直接计算出该元素的存储地址 又称哈希存储

• 数据的运算

  运算的定义是针对逻辑结构的 运算的实现是针对存储结构的

数据类型和抽象数据类型

• 数据类型

? 定义 :一组性质相同的值的集合 相当于定义这个值集合上的一组操作总成

• 原子类型 其中的值 不可以再分 如 int byte

• 结构类型 其值可以再分解为若干的成分 的数据类型

• 抽象数据类型

  定义： 指一个数学模型以及定义在此数学模型上的一组操作。它通常是对数据的某种抽象，定义了数据的取值范围及其结构形式，以及对数据操作的集合。

  • 抽象数据类类型 = 数据的逻辑结构 + 抽象的运算
  • 是问题的数学模型中 抽象处来的逻辑数据结构和逻辑数据结构的运算 不考虑实际的的存储结构 和具体实现的算法 通俗语言就是理论阶段没有被实际定义
  • D数据对象 S数据关系 p 基本操作
  • 特征 信息隐蔽 数据封装 使用与实现封离

算法

• 定义： 算法是对特定的问题求解步骤的一种描述 它是指令的有限序列 其中指令解决一个或多个操作
• 特点 ：
  • 有穷性 步骤 和 时间 有穷 程序是无穷的
  • 确定性 每条指令有明确的含义 没有二义性 相同的输入只能得到相同的输出
  • 可行性 算法是可执行的 可以过通过实现基本操作执行有限次数
  • 有输入 零个输入或多个输入 输入 并不是指从外部设备的输入
  • 有输出 一个输入或多个输出
• 算法设计的要求
  • 正确性 ：算法能够正确的解决问题
  • 可读性：易于使人的理解 算法的逻辑必须是清晰的 简单的 和结构化的
  • 健壮性 算法具有很好的容错性 不于合理的数据进行检查 不经常中断
  • 高效性：花费时间少 和尽量低的存储需求

算法时间性能分析

• 事后估算法 程序跑完后用计时来计算
• 事前统计法 与问题规模大小有关

时间复杂度

• 概念 :事前预估 时间开销(Tn)与问题规模n的关系
• 时间复杂度的大小关系

$$O(1)<O({\log }_{2}n)<O(n{\log }_{2}n)<O(n)<O(n^2)<O(n^3)<O(2^n)<O(n!)$$

空间复杂度

概念:算法所需要存储空间 与问题规模的关系

线性结构

线性表

• 定义 ： 线性表是具有相同数据类型的n个的数据元素的一个有限序列
• 特点
  • 有穷性 线性表中的元素个数是有限的
  • 一致性 一个线性表中的所有元素的性质是相同的
  • 序列性 一个线性表中所有元素之间的相对位置是线性的
  • 存在唯一的开始元素和终端元素,除此之外，每个元素只有唯一的前驱元素和 后继元素。
  • 各元素在线性表中的 位置只取决于它们的序号,所以在一个线性表中可以存在两个值相同的元素。
• 常见操作
  • 初始化表
  • 求表的长度
  • 查找第i个元素
  • 按序号查找
  • 指定位置插入
  • 判断是不是空表
  • 删除某个元素

顺序表

定义：指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中

特点：

• 随机访问，即可在O（1）时间内找到第i个元素。
• 存储密度高，每个节点只存储数据元素本身
• 拓展容量不方便（可以用动态分配的方式实现 ）
• 插入、删除操作不方便，需要移动大量元素

操作：

• 结构体

  typedef int dataType;
  //静态分配
  typedef struct {
      dataType data[MAXSIZE];
      //是组的实际长度
      int len;
  } SeqList;
  //动态分配
  typedef struct {
      dataType *data;
      int MaxSize;
      int length
  } SqList;
  

• 初始化

  //动态分配初始化
  void InitList(SqList *list, int initSize) {
      list->MaxSize = initSize;
      //申请MaxSize块 内存每块的大小是dataType大小
      list->data = calloc(list->MaxSize, sizeof(dataType));
      //申请内存失败直接退出
      if (list->data == NULL) exit(1);
      //初始化内存空间
      for (int i = 0; i < list -> MaxSize; i++) {
          list->data[i] = 0;
      }
      list->length = 0;
  }
  //静态分配初始化
  void InitList(SqList *list) {
      list->length = 0;
      for (int i = 0; i < MaxSize; i++) {
          list->data[i] = 0;
      }
  }
  

• 插入数据

  bool ListInsert(SqList *list, int i, dataType e) {
      /**
       * @param list 插入顺序表的的指针变量
       * @param i 插入元素的的位置
       * @param e 插入的元素
       * @return 是不是插入成功
       * */
      if (i < 1 || i > list->length + 1)
          return false;
  
      //如果空间不够就动态增长数组的大小   前提是该数组是动态分配的空间
      if (list->length == list->MaxSize)
          InCreaseSize(list, list->MaxSize);
      //第1个元素 最后一个元素 最后一个元素后面 第i个元素及之后的都后移
      //插入的时候只需要运行到第i次既可以了 
      for (int j = list->length; j >= i; --j) {
          list->data[j] = list->data[j - 1];
      }
      list->data[i - 1] = e; //在第i个元素处存放元素e
      list -> length++;
      return true;
  
  }
  

  最好的时间复杂度 将元素插入到表尾不需要移动元素

  最坏的的时间复杂度 将元素插入到表头需要移动n个元素

  平均情况 (0+ 1+2+3 + 4 +5 +'…+n) / n + 1 = $\frac{n}{2}$

• 动态增长数组大小

  //动态增长数组长度
  void InCreaseSize(SqList * list,int len){
      list -> MaxSize += len;
      list -> data  = realloc(list -> data, list -> MaxSize);
  }
  

• 删除数据

  bool ListDelete(SqList *list, int i, dataType *e) {
      if (i < 1 || i > list -> length) return false; //判断插入的范围是否有效
      /**
       *@param list 顺序表
       * @param e 删除元素所在的位置内容
       * @param i 删除元素的位置
       * */
      *e = list->data[i - 1];
      //把第i个元素前移   
      for (int j = i - 1; j < list->length - 1; ++j) {
          list->data[j] = list->data[ j + 1];
      }
      list->length--;
      return true;
  }
  

  • 时间复杂度
    • 最好的 在表尾一个都不需要删除
    • 最坏 在表头在第一个
    • 平均 (1 + 2 + 3 +…+n-1)/n = (n - 1)/2

• 查找索引

  //按值查找索引
  int Local_SeqList(SeqList al, dataType e) {
      int i;
      for (i = 0; i <= al.len; i++) {
          if (al.data[i] == e) return i + 1;
      }
      return ERROR;
  }
  

  • 时间复杂度 （1 + 2 + 3 + …+n)/n = (n + 1) / 2

• 获取值

  //获取表中的值
  int get_SeqList(SeqList al, dataType i, dataType *j) {
      if (i < 1 || i < al.len + 1) return ERROR;
      return al.data[i - 1];
  }
  

公式

• 插入元素是移 n - i + 1
• 删除元素 n - i

链表

• 链式存储结构
  • 定义:链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息 数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
  • 特点:
    • 存储密度低
    • 数据的插入和删除不需要移动元素 不能随机访问
    • 数据元素之间的逻辑关系通过指针确定

单链表

• 单链表的结构体

typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

• 初始化

//带头节点的初始化
LinkList initList() {
    //生成新的节点作为头节点
    LinkList list = malloc(sizeof(LNode));
    list->next = NULL;
    return list;
}
//不带头节点的初始化
LinkList initList() {
    //生成新的节点作为头节点
    LinkList list = NULL;
    return list;
}

• 头插法创建链表

//带头节点
void createList_H(LinkList list, int n) {
    for (int i = 0; i < n; i++) {
        //创建节点 并且给该节点赋值
        LNode *p = malloc(sizeof(LNode));
        printf("请输入第%d个数:", i + 1);
        scanf("%d", &(p->data));
        p->next = list->next;
        list->next = p;
    }
}

//不带头节点的
void createList_H(LinkList *list, int n) {
    for (int i = 0; i < n; i++) {
        //创建节点 并且给该节点赋值
        LNode *p = malloc(sizeof(LNode));
        printf("请输入第%d个数:", i + 1);
        scanf("%d", &(p->data));
        //如果是第一个元素的插入写法
        if (*list == NULL){
            p->next = NULL;
            *list = p;
            continue;
        }
        //让p的下一个位置指向第一个元素
        p->next = *list;
        *list = p;//让list指向新的元素
    }
}

• 尾插法创建链表

void List_TailInsert(LinkList list,int n){
    LNode *r = GetElem(list, getLength(list));
    for (int i = 0; i < n; ++i) {
        //创建新的节点并且赋予值
        LNode *s = malloc(sizeof(LNode));
        printf("请输入第%d个元素:",i + 1);
        scanf("%d",&(s -> data));
        s->next = NULL;

        r->next = s;
        r = s;
    }
}

• 单链表的插入
  • 时间复杂度是O(1)

//单链表的插入 不带头节点
bool ListInsert(LinkList *list, int i, ElemType e) {
    if (i < 1) return false;//判断位置合不合法

    if (i == 1) {
        LNode *s = malloc(sizeof(LNode));
        s->data = e;
        s->next = *list;
        *list = s;
        return true;
    }

    LNode *p = GetElem(*list, i - 1);
    if (p == NULL) return false;
    //创建新新的节点并且赋值
    LNode *s = malloc(sizeof(LNode));
    s->data = e;

    s->next = p->next;
    p->next = s;
    return true;
}
//带头节点
bool ListInsert(LinkList list, int i, ElemType e) {
    if (i < 1) return false;//判断位置合不合法

    LNode *p = GetElem(list, i - 1);
    if (p == NULL) return false;
    //创建新新的节点并且赋值
    LNode *s = malloc(sizeof(LNode));
    s->data = e;

    s->next = p->next;
    p->next = s;
    return true;
}

• 单链表的删除
  • 时间复杂度是O(1)

//带头节点
bool ListDelete(LinkList list, int i, ElemType *e) {
    if (i < 1) return false;
    LNode *p = GetElem(list, i - 1);
    if (p == NULL || p->next == NULL) return false;

    LNode *q = p->next;
    *e = q->data;

    p->next = p->next->next;
    free(q);
    return true;
}
//不带头节点
bool ListDelete(LinkList *list, int i, ElemType *e) {
    if (i < 1) return false;
    if (i == 1) {
        LNode *q = *list;
        *e = q->data;
        *list = q->next;
        free(q);
        return true;
    }
    LNode *p = GetElem(*list, i - 1);
    if (p == NULL || p->next == NULL) return false;

    LNode *q = p->next;
    *e = q->data;

    p->next = p->next->next;
    free(q);
    return true;
}

• 单链表遍历 或求长度
  • 时间复杂度O(n)

//带头节点的
int getLength(LinkList list) {
    int length = 0;
/**   
 * for (LNode *p = list->next; p != NULL;p = p -> next)
 *    length++;  //for循环版本
 * */
    while (list->next) {
        length++;
        list = list->next;
    }
    return length;
}
//不带头节点的
int getLength(LinkList list) {
    int length = 0;
    while (list) {
        length++;
        list = list->next;
    }
    return length;
}

根据i获取元素

LNode *GetElem(LinkList L, int i) {
    if (i < 0) return NULL;
    LNode *p = L;
    for (int j = 1; j <= i && p != NULL; ++j) {
        p = p->next;
    }
    return p;
}
//不带头节点
LNode *GetElem(LinkList L, int i) {
    if (i < 0) return NULL;
    LNode *p = L;
    for (int j = 2; j <= i && p != NULL; ++j) {
        p = p->next;
    }
    return p;
}

单链表的缺点

• 只能从头往后遍历
• 不能对其前驱节点操作

双链表

• 该链表有两个指针 一个指向前前驱一个指向后继

具体实现

• 结构体

typedef struct DNode {
    ElemType data;
    struct DNode *prior, *next;
} DNode, *DLinklist;

• 初始化

DLinklist InitDLinklist() {
    DLinklist L = malloc(sizeof(DLinklist));
    L->prior = NULL;
    L->next = NULL;
    return L;
}

• 插入节点

//在p节点后插入s节点
bool InsertNextDNode(DNode *p, DNode *s) {
    if (p == NULL || s == NULL) return false;

    //先连后断
    s->next = p->next;
    s->prior = p;

    p->next = s;
    //最后一个节点 需要防止是null
    if (s->next != NULL)
        s->next->prior = s;

}

• 删除节点

bool DeleteNextDNode(DNode * p) {
    if (p == NULL) return false;
    DNode *q = p -> next;
    //删除节点的后一个
    if (q == NULL) return false; //没有后继
    
    p -> next = q->next;
    if (q->next != NULL )//判断q是不是最后一个节点
        q->next->prior = p;
    free(q);
    return true;
}

循环链表

• 定义:链表的最后一个节点指向了头节点的链表

具体实现

• 初始化

LinkList InitList() {
    LinkList list = malloc(sizeof(LinkList));
    list->next = list;
    return list;
}

• 是不是为空

bool isTail(LinkList list, LNode *p) {
    if (list->next == list)
        return true;
    else
        return false;
}

• 是不是最后一个节点

bool Empty(LinkList list) {
    if (list->next == list)
        return true;
    else
        return false;
}

静态链表

• 定义 ：借助数组来描述线性表的链式存储结构
• 特点
  • 静态链表以next= =-1作为其结束的标志
  • 静态链表的插入、删除操作与动态链表的相同，只需要修改指针,而不需要移动元素
• 缺点:不能随机存取，只能从头结点开始依次往后查找;容量固定不可变

顺序表和链表的比较

循序表

• 优点
  • 方法简单，各种高级语言中都有数组，容易实现。
  • 不用为表示节点间的逻辑关系而增加额外的存储开销。
  • 顺序表具有按元素序号随机访问的特点。
• 缺点
  • 在顺序表中做插入、删除操作时，平均移动表中的一半元素，因此n较大的顺序表效率低。
  • 静态分配，程序执行之前必须明确规定存储规模预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出

链表

• 优点
  • 插入、删除运算方便
• 缺点
  • 要占用额外的存储空间存储元素之间的关系，存储密度降低。存储密度是指一个节点中数据元素所占的存储单元和整个节点所占的存储单元之比。
  • 链表不是一种随机存储结构，不能随机存取元素

栈和队列

栈

基本概念

• 定义：只允许在一端进行插入或删除操作的线性表 先进后出
• 特点 :先进后出 (LIFO)
• 结构
  • 线性表允许进行插入删除的那一端
  • 固定的，不允许进行插入和删除的另一端
• 卡特兰数
  • 不同元素进栈 出栈排列的个数为 $\frac{1}{n+1}{C}_{2n}^n$

顺序栈的实现

• 结构体

typedef struct {
    ElemType data[MaxSize];
    int top;
} SqStack;

• 初始化

void InitStack(SqStack *stack) {
    stack->top = 0;
    //初始化等于零 或 -1  两种方式 判断栈满 和栈空 不一样
}

• 出栈

bool Pop(SqStack *stack,ElemType *x){
    //栈空  出栈失败
    if (isEmpty(*stack)) return false;

    stack->top--;
    *x = stack -> data[stack -> top];
    return true;
}

• 进栈

bool Push(SqStack *stack, ElemType x) {
    //栈空报错
    if (stack -> top ==  MaxSize) return false;

    stack->data[stack->top] = x;
    stack->top++;
    return true;
}

• 从栈顶取值

bool getTop(SqStack stack,ElemType * x){
    if (isEmpty(stack)) return false;
    *x = stack.data[--stack.top];
    return true;
}

共享栈

• 结构体

typedef struct {
    ElemType data[MaxSize];
    int top0;
    int top1
}ShStack;

• 初始

void InitStack(ShStack *s) {
    s->top0 = -1; //预计还没到达的位置
    s -> top1 = MaxSize;
}

• 是不是满栈

bool isFUll(ShStack s){
    return s.top0 + 1 == s.top1;
}

链栈

• 定义 用链式存储的方式实现栈
• 结构体

typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LiStack;

• 具体操作

//初始化栈  不带头节点
LiStack InitStack() {
    LiStack stack = NULL;
    return stack;
}
bool InsertNextNode(LNode **p, ElemType e) {
    //创建一个新节点赋值
    LNode *s = malloc(sizeof(LNode));
    s->data = e;
    //将节点的值往后
    s->next =  *p;
    *p  = s;
    return true;
}
bool getTop(LiStack stack, ElemType *x) {
    if (isEmpty(stack)) return false;
    *x = stack->data;
    return true;
}
bool Push(LiStack *stack, ElemType x) {
    if (*stack == NULL) {
       LNode * s = malloc(sizeof(LNode));
       s->data = x;
       s->next = NULL;
       *stack = s;
       return true;
    }
    return InsertNextNode(stack, x);
}
bool Pop(LiStack *stack, ElemType *x) {
    //栈空  出栈失败
    if (isEmpty(*stack)) return false;
    LNode *p = *stack;
    *x = p->data;
    if (p->next != NULL)
        *stack = p->next;
    free(p);
    return true;
}
typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LiStack;

队列

• 定义:只能在表的一端进行插入，而在表的另一端删除
• 特点 先进先出 FIFO
• 结构
  • 队头 front 准许删除的一端
  • 队尾 rear 准许插入的一端

循环队列

• 结构体

typedef struct {
    ElemType data[MaxSize];
    int front;
    int rear;
} SqQueue;

• 初始化

void InitQueue(SqQueue *queue) {
    queue->rear = 0;//指向即将入队的元素的位置队尾
    queue->front = 0;//指向即将出队的位置队头
}

• 是否为空

//判断队列是否为空
bool queueEmpty(SqQueue queue) {
    if (queue.rear == queue.front)
        return true;
    else
        return false;
}

• 队队列是不是满的

bool isFull(SqQueue queue) {
    //queue.rear == MaxSize; 静态队列
    return (queue.rear + 1) % MaxSize;//循环队列 但是有一个空间放不进
}

• 获取长度

int getLength(SqQueue queue) {
    return (queue.rear + MaxSize - queue.front) %MaxSize;
}

• 入队

bool enQueue(SqQueue *queue, ElemType x) {
    if (isFull(*queue))
        return false;
    queue->data[queue->rear] = x;
    queue->rear = (queue->rear + 1) % MaxSize;
    return true;

}

• 出队

//出队
bool DeQueue(SqQueue *queue, ElemType *x) {
    if (queueEmpty(*queue)) return false;
    *x = queue->data[queue->front];

    queue->front = (queue->front + 1) % MaxSize;
    return true;
}

链队

队列用链表方式实现

具体实现

typedef struct {
    LNode *front, *rear;
} LinkQueue;

LinkQueue *InitQueue() {
    LNode *head = malloc(sizeof(LNode));//创建头节点
    //创建队链并且将队头和队尾指针都指向头结点
    LinkQueue *linkQueue = malloc(sizeof(LinkQueue));
    //linkQueue->front = linkQueue->rear = NULL;
    linkQueue->front = linkQueue->rear = head;
    //front 队头 rear 队尾
    return linkQueue;
}

//入队 队尾插入元素
void enQueue(LinkQueue *linkQueue, ElemType x) {
//  创建新的元素并且赋值
    LNode *s = malloc(sizeof(LNode));
    s->data = x;
    s->next = NULL;
    //让rear指针指向把新元素   rear指针指向最后
    linkQueue->rear->next = s;
    linkQueue->rear = s;
}
//出队 删除队头元素
bool deQueue(LinkQueue *linkQueue, ElemType *x) {
    LNode *p = linkQueue->front->next;
    if (p == NULL) return false;//队列为空 出队失败
    *x = p->data;
//    让头指针执行头指针指向的洗一个节点
    linkQueue->front = p->next;
    free(p);
    return true;
}

bool isEmpty(LinkQueue linkQueue) {
    //不带头节点 linkQueue.front == NULL
    return linkQueue.front->next == NULL;
}

双端队列

• 定义:准许从两端插入两端删除的线性表
• 输入受限的双端队列 :只准许从一端插入 两端删除的的线性表
• 输出受限的双端队列:只准许从两端插入一端删除的线性表

队列和 应用

栈的应用

• 括号的匹配

  bool bracketCheck(char str[], int length) {
      LiStack *stack = InitStack();
      for (int i = 0; i < length; i++) {
          if (str[i] == '(' || str[i] == "{" || str[i] == "["){
              Push(stack,str[i]);
          }else {
              if (isEmpty(stack)) return false;
              char topElem;
              Pop(stack,&topElem);
              if (str[i] == ")" && topElem != '(')
                  return false;
              if (str[i] == "]" && topElem != ']')
                  return false;
              if (str[i] == "}" && topElem != '{')
                  return false;
          }
      }
      return isEmpty(stack);
  }
  

• 后缀表达式 逆波兰表达式

  • 定义:运算符在两个操作数的后边
  • 手动转换方法
    • 确定运算的优先级
    • 然后将运算符的优先级移动到数字后面
    • 将数字和数字后面的操作符看作一个整体 回到2 重复
  • 用栈实现后缀的计算机实现
    • 从左到右 遇到数字压入栈
    • 遇到操作符 就从栈弹出两个数 计算后并压入
    • 最后栈中所剩余的就是结果
  • 将中缀转换成后缀 机算
    • 遇到操作数就加入后缀表达式
    • 遇到左括号就直接入栈( 遇到右括号)就将所有的操作符加入后缀表达式
    • 遇到运算符 栈顶的运算符大于或等于现在的运算符就弹出栈加入后缀表达式 并将现在压入栈中 栈空直接
  • 中缀转后缀并计算
    • 准备两个栈 一个是放数字的栈 一个放运算符的栈
    • 扫描到数字就压入 数栈
    • 每当从操作符号栈中弹出一个就从数字栈中弹出两个并计算 再压回数字栈

• 前缀表达式 波兰表达式

  • 定义:运算符在两个数的前面

• 递归

队列的应用

• 打印机 FCFAS 先来先服务
• 树的层次遍历
• 图的广度遍历

数组，字符串 和广义表

数组

• 定义 是由n个相同类型的数据元素构成的有限序列
• 特点：数组一旦被定义，其维数和维界不可以改变
• 地址计算
  • 一维数组地址计算 a[i] = LOC + i * sizeof(ElemType)
  • 行优先 b[i] [j] = Loc + (i * N + J) * sizeof(ElemType)
  • 列优先 b[i] [j] = = LOC + ( j*M+ i ) * sizeof(ElemType)
• 特殊矩阵
  • 对称矩阵
    • 定义 若 n 阶方阵中任意一个元素 ai,j都有 ai,j = aj,i 则该矩阵为对称矩阵
    • 压缩存储策略 只存储主对角线+下三角区
    • 数组的大小 $\frac{n(1+n)}{2}$
    • 行优先的原则 [1+2+···+(i-1)] + j = $\frac{i(i?1)}{2}+J$ 个元素 ai,j = aj,i
    • 列优先的原则 [n + n -1 + … n - (j -1) + 1] + i - j = $\frac{(j?1)(2n?j+2)}{2}$ + i - j
  • 三对角矩阵
    • 定义 当|i -j| > 1 a_ij=0
    • 按行优先 元素个数3n -2 a_ij是3(i-1) -1 + j-i + 2 个元素
  • 稀疏矩阵
    • 非零元素远远少于矩阵元素的个数
    • 压缩存储策略： 顺序存储——三元组 <行，列，值>
    • 压缩存储策略二： 链式存储——十字链表法

字符串

? 定义：串，即字符串（String）是由零个或多个字符组成的有限序列。一般记为 S = ‘a1a2······an’ （n ≥0） n = 0 空串

? 串的存储结构

//静态数组
typedef struct {
    char ch[MaxSize];
    int length;
} SString;
//动态数组
typedef struct {
    char *ch;
    int length;
} HString;
//通过链表
typedef struct StringNode {
    char ch; //char ch[MaxSize]
    struct StringNode *next;
} StringNode, *String;

基本操作

• 求子串

//求子串
bool SubString(HString *sub, HString s, int pos, int len) {
    /**
     *@param sub 子串
     * @param s  主串
     * @param pos 开始的位置
     * @param len 截取的长度
     * */
    //字串的范围越界
    if (pos + len - 1 > s.length) return false;
    int j = 0;
    for (int i = pos; i < pos + len; ++i) {
//        i - pos + 1
        sub->ch[j++] = s.ch[i];
    }
    sub->length = len;
    return true;
}

• 比较

int StrCompare(HString s1, HString s2) {
//  从零开始所以小于实际长度
    for (int i = 0; i < s1.length && i < s2.length; ++i) {
        if (s2.ch[i] != s1.ch[i])
            return s1.ch[i] - s2.ch[i];
    }
    //如果所有的字符串都相等就比长度
    return s1.length - s2.length;
}

• Kmp算法、

int Index_KMP(SString s, SString t, int next[]) {
    int i = 0, j = 0;
    while (i < s.length && j < t.length) {
        if (j == -1|| s.ch[i] == t.ch[i]){
            //如果数字相等就开始往后走
            i++;
            j++;
        }else {
            j = next[j];
        }
    }
    //第j个相等的时候 j是等于j+1
    if (j == t.length) return i - t.length;
    else return 0;
}
//求nextvalue  
//从第二个元素开始 如果当前的字符等于回到位置的字符 那么nextvalue[j]  = nextvalue(next[j])的值

• 暴力求子串

int Index(SString s, SString t) {
    /**
     * @param s 主串
     * @param t 子串
     * */
    int i = 0, j = 0; //i主串的指针 j字串的指针
    while (i < s.length && j < t.length) {
        if (s.ch[i] == t.ch[i]) {
            //如果数字相等就开始往后走
            i++;
            j++;
        } else {
            //因为i和j走了相同步  i - j 直接回到没有匹配的前一个位置  +2 直接到下一个匹配的位置 
            i = i - j  + 2;
            j = 0;
        }
    }
    //j走到了最后一个
    if (j == t.length) return i - t.length;
    else return 0;
}

广义表

• 线性表的推广 递归的定义 广义表的元素可以是子表 子表又可以是子表
• GetHead 取表头 取出第一个元素 可以是单原子也可以是一个子表
• GetTail 取表尾 取出除表头元素的之外的由其余元素构成的表

非线性结构

树结构

树

定义 :树是n >= 个节点的有限结合 每颗子树的根节点有且仅有一个直接前驱,但是可以又若干个直接后继

基本术语

• 节点 包含数据元素的值和指向其他节点的分支指针
• 叶子节点 :终端节点 度为零的节点
• 节点的度:节点的子树的棵数
• 树的度:各个节点的度的最大值
• 森林 森林是m >=0 棵互不相交的树的集合

常用的性质

• 节点数 = 总度数 + 1
• 
• 度为m的数第i层最多有$m^{i?1}$ 个节点
• 高度为h的的m叉树 用等比数列求和 a1 - an + 1 / 1 - q
• 高度为h的m叉树至少有h个节点
• 高度为h 度为m的树至少有h +m - 1个节点
• 最小高度 节点数大于前一层总节点 小于h层的总节点

存储方式

• 双亲表示法

  typedef struct {
      ElemType data;
      int parent;
  }PTNode;
  
  typedef struct {
      PTNode nodes[MaxSize];
      int n
  }PTree;
  

• 孩子表示法

  //数组加链表 数组中的值表示所有的节点 数组中的next表示对应的孩子的节点
  typedef struct TreeNode {
      ElemType data;
      struct TreeNode *next;
  }TreeNode;
  
  typedef struct{
      ElemType data;
      TreeNode * firstChild;
  }ParentNode;
  
  typedef struct {
      ParentNode nodes[MaxSize];
      int n,r;
  };
  

• 孩子兄弟表示法

  typedef struct  CSNode{
      ElemType data;
      struct CSNode *firstChild,*nextSibling;
  }CSNode,*CSTree;
  

哈夫曼树

• 定义 在带又nge带权叶节点的二叉树中 其中带权路径长度(wpl)最小的二叉树称为哈夫曼树

• 构造

  • 每次从选取节点权值最小的合成一个新树
  • 新树的节点权值是两个新节点的之和
  • 重复 只剩一棵树截至

• 哈夫曼树的叶子节点是n 但是每次两个合并需要一个新的节点 所以哈弗曼树 需要合并n - 1 次 总共有2n - 1 个节点

• 哈弗曼的编码是左零右一的方式

• 关键代码

   //构造哈夫曼树
      //第一层是构造的次数 第二层找出两个最小并且没有父节点的
      for (int i = 0; i < n - 1; ++i) {
          int w1 = MaxWeigh, w2 = MaxWeigh, index1, index2;
          for (int j = 0; j < n + i; ++j) {
              //如果第一个小 放入 14 6 98 99
              if (HuffmanNode[j].parent == -1 && HuffmanNode[j].weight < w1) {
                  //防止前面出现的第二小值 
                  index2 = index1;
                  w2 = w1; //把第二小值赋值
                  index1 = j;
                  w1 = HuffmanNode[j].weight;
              } else if (HuffmanNode[j].parent == -1 && HuffmanNode[j].weight < w2) {
                  index2 = j;
                  w2 = HuffmanNode[j].weight;
              }
          }
          //合并两颗二叉树
          HuffmanNode[index1].parent = n + i;
          HuffmanNode[index2].parent = n + i;
          
          HuffmanNode[n + i].weight = w1 + w2;
          HuffmanNode[n + i].lchild = index1;
          HuffmanNode[n+i].rchild = index2;
      }
  

并查集

定义:并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。

• 具体实现

  //初始化
  void init(int S[]) {
      for (int i = 0; i < MaxSize; ++i) {
          S[i] = 0;
      }
  }
  //查找集合  从该节点出发
  int Find(int s[], int x) {
      int root = x;
  //  找到根节点
      while (s[root] >= 0) root = s[root];
  //  压缩路径
      while (x != root) {
  //      记录好以前的双亲节点
          int t = s[x];
          s[x] = root;
          x = t;
      }
      return root;
  }
  
  /**
   * 合并集合
   * */
  void Union(int s[], int root1, int root2) {
  
      if (root2 > root1) {
          s[root1] += s[root2];
          s[root2] = root1;
      } else {
          s[root2] += s[root1];
          s[root1] = root2;
      }
  }
  

• 优化原理

  • find 查优化 将所有所有的路径上所有节点挂到根节点
  • union 并的优化 将小树 和到大树节点下

二叉树

定义 :二叉树是n>= 0 个节点的有限结合: 每个节点最多只能有两颗子树 左右子树不能颠倒 (二叉树是有序树)

基本术语

• 满二叉树 一颗高度为h 且含有$2^h?1$ 个节点的二叉树 只有最后一层有 叶子节点 不存在度为1的节点
• 完全二叉树 有且仅当 其每一个节点都与高度h的完全二叉树 的中的编号为 1 ~ n的节点–对应 成为完全二叉树 只有最后两层可能有叶子节点 最多只有一个度为1的节点

常用的性质

• 叶子节点 比分支节点多一个 n0 = n2 + 1 n = n0 + n1 + n2 n = n1 + 2n2 + 1
• 完全二叉树 有2k 个节点 则n1 = 1, n0 = k ,n2 = k -1 满二叉树 是奇数个节点

具体实现

typedef char ElemType;
#define MaxSize 100
typedef struct TreeNode{
  ElemType  value;
  bool isEmpty;
}TreeNode;
TreeNode t[MaxSize]; 
//中序遍历
void InOrder(BiTree tree) {
  if (tree == NULL) return;
  InOrder(tree->lchild);
  visit(tree);
  printf("先序遍历生成的顺序:");
  InOrder(tree->rchild);
}
//后续遍历
void postOrder(BiTree tree) {
  if (tree == NULL) return;
  postOrder(tree->lchild);
  postOrder(tree->rchild);
  visit(tree);

}
//前序遍历
void preOrder(BiTree tree) {
  if (tree == NULL) return;
  visit(tree);
  preOrder(tree->lchild);
  preOrder(tree->rchild);
}
/*
*用一个栈来存储节点 
* p指针指向下一个需要访问的节点  
* 如果该节点为空就直接弹出栈取它的其他节点
* 后续遍历用栈实现需要设置标志位是第几次入栈
* */
void InOrderTraverse(BiTree tree) {
  LiStack stack = NULL;
  BiTNode *p = tree;
  while (true) {
      if (p != NULL) {
          //进去栈之后会立即访问左子树 左子树没有立即拿出右子树
          visit(p);
          push(&stack, p);
          p = p->lchild;
      } else {
          if (stack == NULL) break;
          BiTNode *temp = pop(&stack);
          p = temp->rchild;
      }
  }
}
//建立一个树
void createTree(BiTree *tree) {
  //按先序建立一个树
  char ch;
  //从输入数据构建节点
  printf("请输入节点的值:");
  scanf("%c", &ch);
  getchar();
  if (ch == '#') {
      *tree = NULL;
      return;
  }
  BiTNode *node = malloc(sizeof(BiTNode));
  node->data = ch;
  node->lchild = node->rchild = NULL;
  //让当前节点的地址等于构建的节点
  *tree = node;

  BiTree t = *tree;
  createTree(&(t->lchild));
  createTree(&(t->rchild));
}
//层次遍历
void LeaveOrder(BiTree *tree) {
  LinkQueue queue = malloc(sizeof(Queue));
  queue -> front = NULL;
  queue ->rear = NULL;
  
  if (tree != NULL) enQueue(queue, tree);

  while (!queueEmpty(queue)) {
      BiTNode *node = Dequeue(queue);
      if (node->lchild)
          enQueue(queue, node->lchild);
      if (node->rchild)
          enQueue(queue, node->rchild);
  }
}
//计算深度
int Depths(BiTree tree) {
  if (tree == NULL) return 0;
  int m = Depths(tree->lchild);//01
  int n = Depths(tree->rchild);//01
  if (m > n) return m + 1;  //加1 是加上根这一个节点
  else return n + 1;//1
}

图结构

• 图的定义和基本术语

  • 图的定义 :
    • 图是由顶点的有穷非空集合和顶点之间边的集合组成，表示为G（V,E），其中G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
    • 图G由顶点集和边集E组成 记为G=(V,E)
  • 简单图
    • 不存在重复的边
    • 不存在顶点到自身的边
  • 多重图
    • 图G中某两个结点之间的边数多于一条
    • 又准许自己和自己连接
  • 顶点的度
    • 无向图 ：顶点V的度是指依附于该顶点的边的条数
    • 有向图 ： 入度 + 出度
  • 路径 ：从顶点A -> B之间的一条路径是指顶点的序列
  • 回路: 第一个顶点和最后一个顶大相同的路径称为回路或环
  • 简单路径:在路径序列中，顶点不重复出现
  • 简单回路:除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路
  • 路径的长度:路径上边的数目

  getchar();
  if (ch == ‘#’) {
  *tree = NULL;
  return;
  }
  BiTNode *node = malloc(sizeof(BiTNode));
  node->data = ch;
  node->lchild = node->rchild = NULL;
  //让当前节点的地址等于构建的节点
  *tree = node;

  BiTree t = *tree;
  createTree(&(t->lchild));
  createTree(&(t->rchild));
  }
  //层次遍历
  void LeaveOrder(BiTree *tree) {
  LinkQueue queue = malloc(sizeof(Queue));
  queue -> front = NULL;
  queue ->rear = NULL;

  if (tree != NULL) enQueue(queue, tree);

  while (!queueEmpty(queue)) {
  BiTNode *node = Dequeue(queue);
  if (node->lchild)
  enQueue(queue, node->lchild);
  if (node->rchild)
  enQueue(queue, node->rchild);
  }
  }
  //计算深度
  int Depths(BiTree tree) {
  if (tree == NULL) return 0;
  int m = Depths(tree->lchild);//01
  int n = Depths(tree->rchild);//01
  if (m > n) return m + 1; //加1 是加上根这一个节点
  else return n + 1;//1
  }

图结构

• 图的定义和基本术语

  • 图的定义 :
    • 图是由顶点的有穷非空集合和顶点之间边的集合组成，表示为G（V,E），其中G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
    • 图G由顶点集和边集E组成 记为G=(V,E)
  • 简单图
    • 不存在重复的边
    • 不存在顶点到自身的边
  • 多重图
    • 图G中某两个结点之间的边数多于一条
    • 又准许自己和自己连接
  • 顶点的度
    • 无向图 ：顶点V的度是指依附于该顶点的边的条数
    • 有向图 ： 入度 + 出度
  • 路径 ：从顶点A -> B之间的一条路径是指顶点的序列
  • 回路: 第一个顶点和最后一个顶大相同的路径称为回路或环
  • 简单路径:在路径序列中，顶点不重复出现
  • 简单回路:除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路
  • 路径的长度:路径上边的数目