数据结构与算法

目录

第一节 基本概念
1.1 数据结构
1.1.1 定义
1.2 算法
1.2.1 定义

第一节 基本概念

1.1 数据结构

1.1.1 定义

数据对象在计算机中的组织方式和与之相关联的一个操作集，以及实现这些操作的最高效的算法

1.2 算法

1.2.1 定义

算法是一个有限指令集，接受一些输入，产生一些输出，并在有限步骤后终止。

1.2.2 算法复杂度

1. 空间复杂度 根据算法写成的程序在执行时占用存储单元的长度。
2. 时间复杂度 根据算法写成的程序在执行时耗费时间的长度

   1.2.3 复杂度的表示法

3. $T(n)=O(f(n))$表示存在常数$C>0$, $n_0 > 0$,使得当$n \ge n_0$时有$T(n) \le C(f(n))$
4. $T(n)=\Omega(g(n))$表示存在常数$C>0$,$ n_0 > 0$,使得当$n \ge n_0$时有$T(n) \ge C(g(n))$
5. $T(n)=\Theta(h(n))$表示同时有$T(n)=O(h(n))$和$T(n)=\Omega(h(n))$

   1.2.4 算法复杂度几个估算方法

6. 若两段算法分别有复杂度$T_1(n)=O(f_1(n))$和$T_2(n)=O(f_2(n))$，那么两段算法串联的复杂度为$T_1(n)+T_2(n)=max(O(f_1(n)),O(f_2(n)))$，嵌套在一起的复杂度为$T_1(n)\times T_2(n)=O(f_1(n)\times f_2(n))$
7. 若$T(n)$是关于$n$的$k$阶多项式，那么$T(n)=\Theta(n^k)$
8. 一个for循环的时间复杂度等于循环次数乘以循环体代码的复杂度
9. 若干层嵌套循环的时间复杂度等于各层循环次数的乘积再乘以循环体代码的复杂度
10. if-else结构的复杂度取决于if条件判断复杂度和两个分支部分的复杂度，总体复杂度取三者中最大

    第二节 线性结构

    2.1 线性表的定义和实现

    2.1.1 线性表的定义

    1. 定义

线性表是由同一类型的数据元素构成的有序序列的线性结构。
线性表中元素的个数称为线性表的长度。
当一个线性表中没有元素（长度为0）时，称为空表。
表的起始位置称为表头，表的结束位置称为表尾。

2.抽象数据类型描述

类型名称：线性表
数据对象集：线性表是$n(n\ge 0)$个元素构成的有序序列$(a_1, a_2,\cdots ,a_n)$，其中$a_1$是表的第一个元素（表头），$a_n$是表的最后一个元素（表尾）；$a_{i+1}$称为$a_i$的直接后继，$a_{i-1}$为$a_i$的直接前驱；直接前驱和直接后继反映了元素之间一对一的邻接逻辑关系。
操作集：对于一个具体的线性表$L\in List$，一个表示位序的整数i，一个元素$X\in ElementType$，线性表的基本操作主要有：
（1）List MakeEmpty()：初始化一个新的空线性表；
（2）ElementType findKth(List L, int i)：根据指定的位序i，返回L中相应的元素$a_i$；
（3）Position Find(List L, ElementType X)：已知X，返回线性表L中与X相同的第一个元素的位置；若不存在则返回错误信息；
（4）bool Insert(List L, ElementType X, int i)：在L的指定位序i前插入一个新元素X；成功则返回true，否则返回false；
（5）bool Delete(List L, int i)：从L中删除指定位序i的元素；成功则返回true，否则返回false；
（6）int Length(List L)：返回线性表L的长度。

2.1.2 线性表的顺序存储实现

1. 线性表结构定义和封装

   typedef int Position;
   // 使用指针来操作线性表，提高效率
   typedef struct LNode * PtrToLNode;
   // 线性表结构包含了存储数据的数组Data和指明表尾位置的Last
   struct LNode {
       ElemenType Data[MAXSIZE];
       Position Last;
   }
   // 将线性表别名定为List
   typedef PtrToLNode List;

2. 初始化

   List MakeEmpty() {
       List L;
       // 为线性表分配空间
       L = (List) malloc(sizeof(struct LNode));
       // 表内无数据，将表尾位置Last设为-1
       L->Last = -1;
       return L;
   }

3. 查找

   #define ERROR -1
   Position find(List L, ElemenType X) {
       Position i = 0;
       // 从0开始遍历数组，查找X相等的项
       while (i <= L->Last && L->Data[i] != X) {
           i++;
       }
       // 没有查到则i = L->Last + 1
       if (i > L->Last) return ERROR;
       return i;
   }

4. 插入

   bool Insert(List L, ElementType X, int i) {
       // 检查数组是否已经填满
       if (L->Last == MAXSIZE - 1) {
           printf("data is full");
           return false;
       }
       
       // 检查位序i是否合法，在1（表头）到L->Last + 2（表尾后一项）之间
       if (i < 1 || i > L->Last + 2) {
           printf("invalid position");
           return false;
       }
       
       // 从表尾开始，将每一项向后移动一位
       for (int j = L->Last; j >= i - 1; j--) {
           L->Data[j + 1] = L->Data[j];
       }
       
       // 将第i位值设为X
       L->Data[i - 1] = X;
       // 修改表长
       L->Last++;
       return true;
   }

5. 删除

   bool Delete(List L, int i) {
       // 检查位序i是否合法，在1（表头）到L->Last + 1（表尾）之间
       if (i < 1 || i > L->Last + 1) {
           printf("invalid position");
           return false;
       }
       // 从第i + 1位开始，将每一项向前移动一位
       for (int j = i; j <= L->Last; j++) {
           L->Data[j - 1] = L->Data[j];
       }
       // 修改表长
       L->Last--;
       return true;
   }

   2.1.3 线性表的链式存储实现

6. 线性表结构的定义和封装

   typedef struct LNode * PtrToLNode;
   struct LNode {
       ElementType Data;
       PtrToLNode Next;
   }
   typedef PtrToLNode Position;
   typedef PtrToLNode List;

7. 求表长

   int Length(List L) {
       Position p;
       int size = 0;
       p = L;
       while(p) {
           p = p->Next;
           size++;
       }
       return size;
   }

8. 查找

   #define ERROR -1
   
   ElementType FindKth(List L, int K) {
       Position = p;
       // 从第一位开始查找
       int cnt = 1;
       p = L;
       // 依次遍历，直到表尾或者第K位
       while (p && (cnt < K)) {
           p = p->Next;
       }
       // 如果当前位序为K，说明位数合法，返回p的数据，否则返回错误码
       if (p && (cnt == K)) {
           return p->Data;
       } else {
           return ERROR;
       }
   }
   
   Position Find(List L, ElementType X) {
       Position p;
       p = L;
       // 从头开始查找数据与给出相符的
       while (p && p->Data != X) {
           p = p->Next;
       }
       // 数据不存在，p指向队尾的Next，即NULL，返回错误码
       if (p) {
           return p;
       } else {
           return ERROR;
       }
   }

9. 插入

   #defile ERROR NULL
   List Insert(List L, ElementType X, int i) {
       Position tmp, pre;
       tmp = (Position) malloc(sizeof(struct LNode));
       tmp->Data = X;
       if (i == 1) {
           // 表头插入元素
           tmp->Next = L;
           // 将新节点作为表头返回
           return tmp;
       } else {
           int cnt = 1;
           pre = L;
           // 查找原第i - 1位（待插入位置前一位）的元素
           while(pre && (cnt < i - 1)) {
               pre = pre->Next;
               cnt++;
           }
           // 如果没有找到该元素或者位序异常，释放空间，返回错误码
           if (pre == NULL || cnt != i - 1) {
               printf("position error");
               free(tmp);
               return ERROR;
           } else {
               tmp->Next = pre->Next;
               pre->Next = tmp;
               return L;
           }
       }
   }

10. 删除

    bool Delete(List L, int i) {
        Position tmp, pre;
        int cnt = 0;
        pre = L;
        while (pre && cnt < i - 1) {
            pre = pre->Next;
            cnt++:
        }
        
        if (pre == NULL || cnt != i - 1 || pre->Next == NULL) {
            printf("invalid position");
            return false;
        } else {
            tmp = pre->Next;
            pre->Next = tmp->Next;
            free(tmp);
            return true;
        }
    }

2.2 堆栈

2.2.1 堆栈的定义

1. 定义

堆栈是具有一定约束的线性表，插入和删除都需要从端点进行，这一端点称之为栈顶。

2. 堆栈抽象数据描述

类型名称：堆栈；
数据对象集：一个有0个或多个元素的有穷线性表；
操作集：对一个具体的长度为正整数MaxSize的堆栈$S\in Stack$，记堆栈中任一元素$X\in ElementType$，堆栈的主要操作有：
（1）Stack CreateStack(int MaxSize)：生成空堆栈，其最大长度为MaxSize；
（2）bool isFull(Stack S)：判断堆栈S是否已满；
（3）bool Push(Stack S, ElementType X)：将元素X压入栈。堆栈已满返回false；否则将元素插入到堆栈S的栈顶处并返回true；
（4）bool IsEmpty(Stack S)：判断堆栈S是否为空；
（5）ElementType Pop(Stack S)：删除并返回栈顶元素。
数据结构与算法
=====

目录

第一节 基本概念
1.1 数据结构
1.1.1 定义
1.2 算法
1.2.1 定义

第一节 基本概念

1.1 数据结构

1.1.1 定义

数据对象在计算机中的组织方式和与之相关联的一个操作集，以及实现这些操作的最高效的算法

1.2 算法

1.2.1 定义

算法是一个有限指令集，接受一些输入，产生一些输出，并在有限步骤后终止。

1.2.2 算法复杂度

1. 空间复杂度 根据算法写成的程序在执行时占用存储单元的长度。
2. 时间复杂度 根据算法写成的程序在执行时耗费时间的长度

   1.2.3 复杂度的表示法

3. $T(n)=O(f(n))$表示存在常数$C>0$, $n_0 > 0$,使得当$n \ge n_0$时有$T(n) \le C(f(n))$
4. $T(n)=\Omega(g(n))$表示存在常数$C>0$,$ n_0 > 0$,使得当$n \ge n_0$时有$T(n) \ge C(g(n))$
5. $T(n)=\Theta(h(n))$表示同时有$T(n)=O(h(n))$和$T(n)=\Omega(h(n))$

   1.2.4 算法复杂度几个估算方法

6. 若两段算法分别有复杂度$T_1(n)=O(f_1(n))$和$T_2(n)=O(f_2(n))$，那么两段算法串联的复杂度为$T_1(n)+T_2(n)=max(O(f_1(n)),O(f_2(n)))$，嵌套在一起的复杂度为$T_1(n)\times T_2(n)=O(f_1(n)\times f_2(n))$
7. 若$T(n)$是关于$n$的$k$阶多项式，那么$T(n)=\Theta(n^k)$
8. 一个for循环的时间复杂度等于循环次数乘以循环体代码的复杂度
9. 若干层嵌套循环的时间复杂度等于各层循环次数的乘积再乘以循环体代码的复杂度
10. if-else结构的复杂度取决于if条件判断复杂度和两个分支部分的复杂度，总体复杂度取三者中最大

    第二节 线性结构

    2.1 线性表的定义和实现

    2.1.1 线性表的定义

    1. 定义

线性表是由同一类型的数据元素构成的有序序列的线性结构。
线性表中元素的个数称为线性表的长度。
当一个线性表中没有元素（长度为0）时，称为空表。
表的起始位置称为表头，表的结束位置称为表尾。

2.抽象数据类型描述

类型名称：线性表
数据对象集：线性表是$n(n\ge 0)$个元素构成的有序序列$(a_1, a_2,\cdots ,a_n)$，其中$a_1$是表的第一个元素（表头），$a_n$是表的最后一个元素（表尾）；$a_{i+1}$称为$a_i$的直接后继，$a_{i-1}$为$a_i$的直接前驱；直接前驱和直接后继反映了元素之间一对一的邻接逻辑关系。
操作集：对于一个具体的线性表$L\in List$，一个表示位序的整数i，一个元素$X\in ElementType$，线性表的基本操作主要有：
（1）List MakeEmpty()：初始化一个新的空线性表；
（2）ElementType findKth(List L, int i)：根据指定的位序i，返回L中相应的元素$a_i$；
（3）Position Find(List L, ElementType X)：已知X，返回线性表L中与X相同的第一个元素的位置；若不存在则返回错误信息；
（4）bool Insert(List L, ElementType X, int i)：在L的指定位序i前插入一个新元素X；成功则返回true，否则返回false；
（5）bool Delete(List L, int i)：从L中删除指定位序i的元素；成功则返回true，否则返回false；
（6）int Length(List L)：返回线性表L的长度。

2.1.2 线性表的顺序存储实现

1. 线性表结构定义和封装

   typedef int Position;
   // 使用指针来操作线性表，提高效率
   typedef struct LNode * PtrToLNode;
   // 线性表结构包含了存储数据的数组Data和指明表尾位置的Last
   struct LNode {
       ElemenType Data[MAXSIZE];
       Position Last;
   }
   // 将线性表别名定为List
   typedef PtrToLNode List;

2. 初始化

   List MakeEmpty() {
       List L;
       // 为线性表分配空间
       L = (List) malloc(sizeof(struct LNode));
       // 表内无数据，将表尾位置Last设为-1
       L->Last = -1;
       return L;
   }

3. 查找

   #define ERROR -1
   Position find(List L, ElemenType X) {
       Position i = 0;
       // 从0开始遍历数组，查找X相等的项
       while (i <= L->Last && L->Data[i] != X) {
           i++;
       }
       // 没有查到则i = L->Last + 1
       if (i > L->Last) return ERROR;
       return i;
   }

4. 插入

   bool Insert(List L, ElementType X, int i) {
       // 检查数组是否已经填满
       if (L->Last == MAXSIZE - 1) {
           printf("data is full");
           return false;
       }
       
       // 检查位序i是否合法，在1（表头）到L->Last + 2（表尾后一项）之间
       if (i < 1 || i > L->Last + 2) {
           printf("invalid position");
           return false;
       }
       
       // 从表尾开始，将每一项向后移动一位
       for (int j = L->Last; j >= i - 1; j--) {
           L->Data[j + 1] = L->Data[j];
       }
       
       // 将第i位值设为X
       L->Data[i - 1] = X;
       // 修改表长
       L->Last++;
       return true;
   }

5. 删除

   bool Delete(List L, int i) {
       // 检查位序i是否合法，在1（表头）到L->Last + 1（表尾）之间
       if (i < 1 || i > L->Last + 1) {
           printf("invalid position");
           return false;
       }
       // 从第i + 1位开始，将每一项向前移动一位
       for (int j = i; j <= L->Last; j++) {
           L->Data[j - 1] = L->Data[j];
       }
       // 修改表长
       L->Last--;
       return true;
   }

   2.1.3 线性表的链式存储实现

6. 线性表结构的定义和封装

   typedef struct LNode * PtrToLNode;
   struct LNode {
       ElementType Data;
       PtrToLNode Next;
   }
   typedef PtrToLNode Position;
   typedef PtrToLNode List;

7. 求表长

   int Length(List L) {
       Position p;
       int size = 0;
       p = L;
       while(p) {
           p = p->Next;
           size++;
       }
       return size;
   }

8. 查找

   #define ERROR -1
   
   ElementType FindKth(List L, int K) {
       Position = p;
       // 从第一位开始查找
       int cnt = 1;
       p = L;
       // 依次遍历，直到表尾或者第K位
       while (p && (cnt < K)) {
           p = p->Next;
       }
       // 如果当前位序为K，说明位数合法，返回p的数据，否则返回错误码
       if (p && (cnt == K)) {
           return p->Data;
       } else {
           return ERROR;
       }
   }
   
   Position Find(List L, ElementType X) {
       Position p;
       p = L;
       // 从头开始查找数据与给出相符的
       while (p && p->Data != X) {
           p = p->Next;
       }
       // 数据不存在，p指向队尾的Next，即NULL，返回错误码
       if (p) {
           return p;
       } else {
           return ERROR;
       }
   }

9. 插入

   #defile ERROR NULL
   List Insert(List L, ElementType X, int i) {
       Position tmp, pre;
       tmp = (Position) malloc(sizeof(struct LNode));
       tmp->Data = X;
       if (i == 1) {
           // 表头插入元素
           tmp->Next = L;
           // 将新节点作为表头返回
           return tmp;
       } else {
           int cnt = 1;
           pre = L;
           // 查找原第i - 1位（待插入位置前一位）的元素
           while(pre && (cnt < i - 1)) {
               pre = pre->Next;
               cnt++;
           }
           // 如果没有找到该元素或者位序异常，释放空间，返回错误码
           if (pre == NULL || cnt != i - 1) {
               printf("position error");
               free(tmp);
               return ERROR;
           } else {
               tmp->Next = pre->Next;
               pre->Next = tmp;
               return L;
           }
       }
   }

10. 删除

    bool Delete(List L, int i) {
        Position tmp, pre;
        int cnt = 0;
        pre = L;
        while (pre && cnt < i - 1) {
            pre = pre->Next;
            cnt++:
        }
        
        if (pre == NULL || cnt != i - 1 || pre->Next == NULL) {
            printf("invalid position");
            return false;
        } else {
            tmp = pre->Next;
            pre->Next = tmp->Next;
            free(tmp);
            return true;
        }
    }

2.2 堆栈

2.2.1 堆栈的定义

1. 定义

堆栈是具有一定约束的线性表，插入和删除都需要从端点进行，这一端点称之为栈顶。

2. 堆栈抽象数据描述

类型名称：堆栈；
数据对象集：一个有0个或多个元素的有穷线性表；
操作集：对一个具体的长度为正整数MaxSize的堆栈$S\in Stack$，记堆栈中任一元素$X\in ElementType$，堆栈的主要操作有：
（1）Stack CreateStack(int MaxSize)：生成空堆栈，其最大长度为MaxSize；
（2）bool isFull(Stack S)：判断堆栈S是否已满；
（3）bool Push(Stack S, ElementType X)：将元素X压入栈。堆栈已满返回false；否则将元素插入到堆栈S的栈顶处并返回true；
（4）bool IsEmpty(Stack S)：判断堆栈S是否为空；
（5）ElementType Pop(Stack S)：删除并返回栈顶元素。