数据结构复习要点

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

一、绪论

1、数据结构的三要素

数据的逻辑结构（面向问题）、数据的存储结构（面向计算机），以及数据的操作。

什么是数据结构呢？数据结构是一门研究非数值计算的程序设计问题中，计算机处理的对象及其相互间的关系和操作等的学科。目前在我国，“数据结构”不仅成为计算机专业的核心课程之一，而且也是其他非计算机专业的重要选修课。“数据结构”在计算机科学领域内是综合性较强的专业基础课程。这门课程的研究不仅涉及计算机硬件（特别是编译理论、存储设备和访问方法等）的范畴，还与计算机软件研究有更为紧密的联系，无论是编译程序还是操作系统，都涉及数据单元在存储器中的分配问题。

数据（data)

是对客观事物的符号表示，在计算机科学中指所有能输入到计算机并被其程序处理的符号总称。

数据元素（data element)

是数据的基本单位，通常在计算机程序中作为一个整体进行考虑和操作。

数据对象（data object）

是由性质相同的数据元素组成的集合，它是数据的一个子集。

数据结构（data structure)

是指存在一种或多种特定关系的数据元素的集合。

数据元素之间的这种关联称为结构。根据数据元素间关系的不同特点，通常有以下4类基本结构：1）集合：结构中的数据元素之间除了“同属一个集合”的关系外，没有其他关系；2）线性结构：结构中的数据元素之间存在一对一的关系；3）树形结构：结构中的数据元素之间存在一对多的关系；4）图状结构或网状结构：结构中的数据元素之间存在多对多的关系。

数据结构的形式定义为：数据结构是一个二元组 Data Structure = (D,S)，其中：D是数据元素的有限集，S是在D上的关系的有限集。换句话说，它是从操作对象抽象出来的数学模型。“关系”描述了数据元素之间的逻辑关联，因此又称为数据的逻辑结构。

在计算机中表示信息的基本单位是一个二进制数位，称作位（bit）。我们可以用若干个位组合成一个位串来表示一个数据元素或结点。当数据元素由多个数据项组成时，位串中对应于各个数据项的子位串成为数据域。

数据元素之间的关系在计算机中有两种不同的表示方法：顺序映射和非顺序映射，并由此形成了两种存储结构：顺序存储结构和链式存储结构。顺序映射的特点是通过元素在存储器中的相对位置来表达数据元素间的逻辑关联。非顺序映射则是利用指针指示元素的存储地址来表现数据元素间的逻辑关系，不直接反映这种逻辑关联，而是将数据放置于无固定联系的单元中。

如果我们把C语言视为一个执行C指令和处理C数据类型的虚拟处理器，那么书中讨论的存储结构就是数据结构在这一虚拟环境中的体现，可以称之为虚拟存储结构。

数据类型（data type)

是与数据结构紧密相关的概念，最早出现在高级编程语言中，用以描述操作对象的特性。根据“值”的不同特点，高级编程语言中的数据类型可划分为两类：一类是非结构化的原子类型，其值无法再分；例如C语言的基本类型（整型、实型、字符型和枚举型），指针类型及空类型。另一类是结构化类型，其值由多个部分按某种方式组合而成，因此可以分解，并且这些部分本身既可以是非结构化的，也可以是结构化的。

抽象数据类型（Abstract Data Type,简称ADT）

是指一个数学模型以及定义在该模型上的一系列操作。如前所述，抽象数据类型的定义包括一个值域和在此值域上定义的操作集合。根据其值的不同特点，可以细分为以下3种类型：1）原子类型（atomic data type)，这类变量的值不可再分。通常情况下已有的内置数据类型足以满足需求，但在某些时候也需要定义新的原子数据类型；2）固定聚合类型（fixed-aggregate data type)，该类型的变量由确定数量的部分按某种方式组合而成；3）可变聚合类型（variable-aggregate data type)，与固定聚合类型相比，其值的组成部分的数量不固定。

显然，后两种类型可以统称为结构化类型。与数据类型的形式定义相对应，抽象数据类型可以用三元组 (D,S,P) 表示，其中 D 是数据对象，S 是在 D 上的关系集，P 则是对 D 的基本操作集。书中采用以下格式来定义抽象数据类型：

ADT 抽象数据类型名{
     数据对象：<数据对象的定义>
     数据关系：<数据关系的定义>
     基本操作：<基本操作的定义>
}ADT 抽象数据类型名

其中，数据对象和关系的描述使用伪代码，基本操作的定义格式如下：

基本操作名(参数表）
    初始条件：<初始条件描述>
    操作结果：<操作结果描述>

例1-6 抽象数据类型三元组的定义：

1. 形式化定义

   三元组 Triple = (D1, D2, D3, R)
   D1, D2, D3：三个元素的数据类型（可以相同或不同）
   R：元素间的关系和操作集合

2. ADT 规范表示

   ADT Triple {
       数据对象：
           D = {e1, e2, e3 | e1∈D1, e2∈D2, e3∈D3}
       
       数据关系：
           R = {<e1, e2, e3>}
       
       基本操作：
           // 构造操作
           InitTriple(&T, v1, v2, v3)
               初始条件：无
               操作结果：构造三元组 T，元素分别为 v1, v2, v3
           
           // 访问操作
           GetFirst(T)
               初始条件：三元组 T 已存在
               操作结果：返回第一个元素
           
           GetSecond(T)
               初始条件：三元组 T 已存在
               操作结果：返回第二个元素
           
           GetThird(T)
               初始条件：三元组 T 已存在
               操作结果：返回第三个元素
           
           // 修改操作
           SetFirst(&T, value)
               初始条件：三元组 T 已存在
               操作结果：将第一个元素设置为 value
           
           SetSecond(&T, value)
               初始条件：三元组 T 已存在
               操作结果：将第二个元素设置为 value
           
           SetThird(&T, value)
               初始条件：三元组 T 已存在
               操作结果：将第三个元素设置为 value
           
           // 其他操作
           IsEqual(T1, T2)
               初始条件：三元组 T1, T2 已存在
               操作结果：判断两个三元组是否相等
   }

3. 编程语言中的实现示例 C++ 模板实现：

   template<typename T1, typename T2, typename T3>
   class Triple {
   private:
       T1 first;
       T2 second;
       T3 third;
   
   public:
       Triple(T1 f, T2 s, T3 t) : first(f), second(s), third(t) {}
       
       T1 getFirst() const { return first; }
       T2 getSecond() const { return second; }
       T3 getThird() const { return third; }
       
       void setFirst(T1 value) { first = value; }
       void setSecond(T2 value) { second = value; }
       void setThird(T3 value) { third = value; }
       
       bool operator==(const Triple& other) const {
           return first == other.first && 
                  second == other.second && 
                  third == other.third;
       }
   };

Python 实现：

from typing import Generic, TypeVar, Any

T1 = TypeVar('T1')
T2 = TypeVar('T2')
T3 = TypeVar('T3')

class Triple(Generic[T1, T2, T3]):
    def __init__(self, first: T1, second: T2, third: T3):
        self._first = first
        self._second = second
        self._third = third
    
    def get_first(self) -> T1:
        return self._first
    
    def get_second(self) -> T2:
        return self._second
    
    def get_third(self) -> T3:
        return self._third
    
    def set_first(self, value: T1) -> None:
        self._first = value
    
    def set_second(self, value: T2) -> None:
        self._second = value
    
    def set_third(self, value: T3) -> None:
        self._third = value
    
    def __eq__(self, other: Any) -> bool:
        if not isinstance(other, Triple):
            return False
        return (self._first == other._first and 
                self._second == other._second and 
                self._third == other._third)

多元数据类型（polymorphic data type)

是指其值的成分不确定的数据类型。从抽象数据类型的视角看，具有相同的数学抽象特征，因此称为多态数据类型。

在高级编程语言的虚拟层面上讨论抽象数据类型的表示和实现，并且讨论的数据结构及其算法主要是面向读者，故采用介于伪代码和C语言之间的类C语言作为描述工具。

1. 预定义常量和类型：

这一步的目标是定义该 ADT 所依赖的基础类型和状态值，使其独立于任何具体的编程语言。

// 预定义常量
// （三元组通常没有特定的状态常量，这里以操作返回值状态为例）
#define OK 1      // 操作成功
#define ERROR 0   // 操作失败
#define TRUE 1
#define FALSE 0

// 预定义元素类型
// 为了通用性，我们将三个元素的数据类型定义为可配置的
typedef ElemType1; // 第一个元素的类型，例如 int, char, string 等
typedef ElemType2; // 第二个元素的类型
typedef ElemType3; // 第三个元素的类型

// 函数状态返回值类型
typedef int Status;

2. 数据对象

数据对象：
    D = { e1, e2, e3 | e1 ∈ ElemType1, e2 ∈ ElemType2, e3 ∈ ElemType3 }

3. 数据关系

数据关系：
    R = { <e1, e2, e3> } 
    // 表示三个元素之间存在一个有序的、固定的组合关系

4. 基本操作

基本操作：

    // === 构造/销毁操作 ===
    InitTriple(&T, v1, v2, v3)
        操作结果：用给定的值 v1, v2, v3 构造一个三元组 T。
        
    DestroyTriple(&T)
        初始条件：三元组 T 已存在。
        操作结果：销毁三元组 T，释放其占用的资源。

    // === 取值操作 ===
    GetFirst(T, &e1)
        初始条件：三元组 T 已存在。
        操作结果：用 e1 返回 T 的第一个元素。
        
    GetSecond(T, &e2)
        初始条件：三元组 T 已存在。
        操作结果：用 e2 返回 T 的第二个元素。
        
    GetThird(T, &e3)
        初始条件：三元组 T 已存在。
        操作结果：用 e3 返回 T 的第三个元素。

    // === 赋值操作 ===
    SetFirst(&T, e1)
        初始条件：三元组 T 已存在。
        操作结果：将 T 的第一个元素修改为 e1。
        
    SetSecond(&T, e2)
        初始条件：三元组 T 已存在。
        操作结果：将 T 的第二个元素修改为 e2。
        
    SetThird(&T, e3)
        初始条件：三元组 T 已存在。
        操作结果：将 T 的第三个元素修改为 e3。

    // === 判断与比较操作 ===
    IsEqual(T1, T2)
        初始条件：三元组 T1 和 T2 已存在。
        操作结果：若 T1 和 T2 的三个元素分别相等，则返回 TRUE，否则返回 FALSE。

    CopyTriple(T_src, &T_dest)
        初始条件：三元组 T_src 已存在。
        操作结果：由三元组 T_dest 生成一个与 T_src 完全相同的三元组。

} ADT Triple

//函数结果状态代码
#define TRUE    1
#define FALSE   0
#define OK      1
#define ERROR   0
#define INFEASIBLE  -1
#define OVERFLOW    -2
// Status是函数的类型，其值是函数结果状态代码
type  int Status；

（2）数据结构的表示（存储结构）用类型定义（typedef）描述。数据元素类型约定为ElemType，由用户在使用该数据类型时自行定义。

（3）基本操作的算法都用以下形式的函数描述：

抽象数据类型 Triple 的基本操作算法描述

函数描述格式：

函数类型 函数名(参数列表) {
 //算法说明
  语句序列
}//函数名

4. 构造与销毁操作

// 构造三元组
Status InitTriple(Triple &T, ElemType1 v1, ElemType2 v2, ElemType3 v3)
    操作：为三元组T分配内存，并分别用v1, v2, v3初始化三个分量
    返回：成功返回OK，失败返回ERROR

// 销毁三元组  
Status DestroyTriple(Triple &T)
    初始条件：三元组T已存在
    操作：释放三元组T占用的内存空间
    返回：成功返回OK，失败返回ERROR

5. 取值操作

// 获取第一个元素
Status GetFirst(Triple T, ElemType1 &e1)
    初始条件：三元组T已存在
    操作：用e1返回T的第一个元素值
    返回：成功返回OK，失败返回ERROR

// 获取第二个元素
Status GetSecond(Triple T, ElemType2 &e2)
    初始条件：三元组T已存在
    操作：用e2返回T的第二个元素值
    返回：成功返回OK，失败返回ERROR

// 获取第三个元素
Status GetThird(Triple T, ElemType3 &e3)
    初始条件：三元组T已存在
    操作：用e3返回T的第三个元素值
    返回：成功返回OK，失败返回ERROR

6. 判断与比较操作

// 判断两个三元组是否相等
Status IsEqual(Triple T1, Triple T2)
    初始条件：三元组T1和T2均已存在
    操作：比较T1和T2的三个对应元素是否分别相等
    返回：若全部相等返回TRUE，否则返回FALSE

// 复制三元组
Status CopyTriple(Triple T_src, Triple &T_dest)
    初始条件：三元组T_src已存在
    操作：创建一个与T_src完全相同的三元组T_dest
    返回：成功返回OK，失败返回ERROR

// 判断三元组是否为空
Status IsEmpty(Triple T)
    初始条件：三元组T已存在
    操作：检查三元组T是否包含有效数据
    返回：若为空返回TRUE，否则返回FALSE

7. 遍历操作

// 遍历三元组（对每个元素执行指定操作）
Status TraverseTriple(Triple T, Status (*visit)(ElemType1, ElemType2, ElemType3))
    初始条件：三元组T已存在，visit是对元素操作的应用函数
    操作：依次对T的三个元素调用函数visit
    返回：visit成功返回OK，否则返回ERROR

使用示例

// 创建三元组
Triple T;
InitTriple(T, 10, "hello", 3.14);

// 获取和修改元素
ElemType1 first;
GetFirst(T, first);      // first = 10
SetSecond(T, "world");   // 修改第二个元素为"world"

// 比较三元组
Triple T2;
InitTriple(T2, 10, "world", 3.14);
if (IsEqual(T, T2)) {
    // 执行相等时的操作
}

// 遍历三元组
TraverseTriple(T, PrintElements);  // 假设PrintElements是打印函数

这种描述方式清晰地定义了每个操作的：

• 函数接口（返回值类型、函数名、参数列表）
• 前置条件（初始条件）
• 功能说明（操作）
• 后置条件（返回结果）

（4）赋值语句有：

简单赋值 变量名=表达式；
串联赋值 变量名1=变量名2=...=变量名k=表达式；
成组赋值 （变量名1，...,变量名k)=(表达式1，...,表达式2）；
         结构名=结构名；
         结构名=（值1，...，值k);
         变量名[]=表达式；
        变量名[起始下标..终止下标]=变量名[起始下标...终止下标];
交换赋值 变量名  变量名；
条件赋值 变量名 = 条件表达式?表达式T：表达式F；

（5）选择语句有

条件语句1 if（表达式）语句；
条件语句2 if（表达式）语句；
               else语句：
开头语句1 switch（表达式）{
    case 值1:语句序列1；break；
    ...
    case值n：语句序列n；break;
    default:语句序列n+1;
}
开关语句2 switch{
       case 条件1：语句序列1；break；
       ...
       case条件n:语句序列n;break;
       default;语句序列n+1；
}

（6）循环语句有：

for语句 for（赋初值表达式序列；条件；修改表达式序列）语句；
while语句 while（条件）语句；
do-while语句 do{
             语句序列;
            }while(条件）；

（7）结束语句有：

函数结束语句   return表达式；
              return；
case结束语句   break;
异常结束语句   exit(异常代码）;

(8)输入和输出语句有：

输入语句  scanf([格式串]，变量1，...,变量n);
输出语句  printf([格式串],表达式1，...，表达式n);
通常省略格式串

（9）注释

单行注释 // 文字序列

（10）基本函数有：

求最大值   max(表达式1,...,表达式n)
求最小值   min(表达式1,...,表达式n)
求绝对值   abs(表达式)
求不足整数值  floor(表达式）
求进位整数值  ceil(表达式）
判定文件结束  eof(文件变量）或eof
判定行结束   eoln(文件变量）或eoln

（11）逻辑运算约定

与运算&&：对于A&&B,当A的值为0时，不再对B求值。
或运算||：对于A||B，当A的值为非0时，不再对B求值。

例1-7 抽象数据类型Triplet的表示和实现

4. 预定义常量和类型

/* ------------ 预定义常量和类型 ------------ */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

typedef int Status;        // 函数状态返回值类型
typedef int ElemType;      // 元素类型，可根据需要修改

5. Triplet 类型的存储表示

/* ------------ Triplet 类型的存储表示 ------------ */
typedef ElemType *Triplet; // 由三个ElemType元素组成的数组类型

6. 基本操作的函数实现

/* ------------ 基本操作的算法实现 ------------ */

/* 操作结果：构造三元组T，依次置T的三个元素为v1，v2和v3。 */
Status InitTriplet(Triplet *T, ElemType v1, ElemType v2, ElemType v3) {
    *T = (ElemType *)malloc(3 * sizeof(ElemType));
    if (!*T) {
        exit(OVERFLOW); // 存储分配失败
    }
    (*T)[0] = v1;
    (*T)[1] = v2;
    (*T)[2] = v3;
    return OK;
}

/* 操作结果：销毁三元组T。 */
Status DestroyTriplet(Triplet *T) {
    free(*T);
    *T = NULL;
    return OK;
}

/* 初始条件：三元组T已存在，1≤i≤3。 */
/* 操作结果：用e返回T的第i个元素的值。 */
Status Get(Triplet T, int i, ElemType *e) {
    if (i < 1 || i > 3) {
        return ERROR; // i值不合法
    }
    *e = T[i - 1]; // 将第i个元素的值赋给e
    return OK;
}

/* 初始条件：三元组T已存在，1≤i≤3。 */
/* 操作结果：改变T的第i个元素的值为e。 */
Status Put(Triplet *T, int i, ElemType e) {
    if (i < 1 || i > 3) {
        return ERROR; // i值不合法
    }
    (*T)[i - 1] = e; // 将第i个元素的值改为e
    return OK;
}

/* 初始条件：三元组T已存在。 */
/* 操作结果：如果T的三个元素按升序排列，则返回1，否则返回0。 */
Status IsAscending(Triplet T) {
    return (T[0] <= T[1]) && (T[1] <= T[2]);
}

/* 初始条件：三元组T已存在。 */
/* 操作结果：如果T的三个元素按降序排列，则返回1，否则返回0。 */
Status IsDescending(Triplet T) {
    return (T[0] >= T[1]) && (T[1] >= T[2]);
}

/* 初始条件：三元组T已存在。 */
/* 操作结果：用e返回T的三个元素中最大值。 */
Status Max(Triplet T, ElemType *e) {
    *e = (T[0] >= T[1]) ? 
         ((T[0] >= T[2]) ? T[0] : T[2]) : 
         ((T[1] >= T[2]) ? T[1] : T[2]);
    return OK;
}

/* 初始条件：三元组T已存在。 */
/* 操作结果：用e返回T的三个元素中最小值。 */
Status Min(Triplet T, ElemType *e) {
    *e = (T[0] <= T[1]) ? 
         ((T[0] <= T[2]) ? T[0] : T[2]) : 
         ((T[1] <= T[2]) ? T[1] : T[2]);
    return OK;
}

7. 主函数测试示例

/* ------------ 主函数测试 ------------ */
#include <stdio.h>

void printTriplet(Triplet T, const char *name) {
    printf("%s = (%d, %d, %d)\n", name, T[0], T[1], T[2]);
}

int main() {
    Triplet T;
    ElemType e;
    
    // 测试初始化
    printf("=== 测试初始化三元组 ===\n");
    InitTriplet(&T, 10, 20, 30);
    printTriplet(T, "T");
    
    // 测试Get操作
    printf("\n=== 测试Get操作 ===\n");
    Get(T, 2, &e);
    printf("第二个元素的值为：%d\n", e);
    
    // 测试Put操作
    printf("\n=== 测试Put操作 ===\n");
    Put(&T, 2, 25);
    Get(T, 2, &e);
    printf("修改后第二个元素的值为：%d\n", e);
    printTriplet(T, "T");
    
    // 测试判断函数
    printf("\n=== 测试判断函数 ===\n");
    printf("是否升序排列：%s\n", IsAscending(T) ? "是" : "否");
    printf("是否降序排列：%s\n", IsDescending(T) ? "是" : "否");
    
    // 测试最大最小值
    printf("\n=== 测试最大最小值 ===\n");
    Max(T, &e);
    printf("最大值：%d\n", e);
    Min(T, &e);
    printf("最小值：%d\n", e);
    
    // 测试销毁
    printf("\n=== 测试销毁 ===\n");
    DestroyTriplet(&T);
    printf("三元组已销毁\n");
    
    return 0;
}

8. 预期输出结果

=== 测试初始化三元组 ===
T = (10, 20, 30)

=== 测试Get操作 ===
第二个元素的值为：20

=== 测试Put操作 ===
修改后第二个元素的值为：25
T = (10, 25, 30)

=== 测试判断函数 ===
是否升序排列：是
是否降序排列：否

=== 测试最大最小值 ===
最大值：30
最小值：10

=== 测试销毁 ===
三元组已销毁

2、算法概念及评价

1. 五个特性：有穷性、确定性、可行性、输入、输出

算法（algorithm)是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。此外，一个算法还具有下列5个重要特性：

1. 有穷性 一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成。
2. 确定性 算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。并且，在任何条件下，算法是唯一的一条执行路径，即对于相同的输入只能得到相同的输出。
3. 可行性 一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。
4. 输入 一个算法有多个或零个的输入，这些输入取自于某个特定的对象的集合。
5. 输出 一个算法有一个或多个的输出，这些输出是同输入有着某些特定关系的量。
2. 评价标准：正确性、可读性、健壮性、效率与低存储需求。
6. 正确性 算法应当满足具体问题的要求。通常一个大型问题的需求，要以特定的规格说明方式给出。
7. 可读性 算法主要是为了人的阅读和交流，其次才是机器执行。
8. 健壮性 当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生不可理解地输出结果。
9. 效率与低存储需求 通俗地说，效率指的是算法执行的时间。

3）效率的度量：时间复杂度和空间复杂度

• 事后统计的方法
• 事前分析估算的方法 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n), 算法的时间量度记作 T（n)=O(f(n)) 它表示随问题规模n的增大，算法执行时间的增长率相同，称作算法的渐进时间复杂度，简称 时间复杂度。

被称做问题的基本操作的原操作应是其重复执行次数和算法的执行时间成正比的原操作，多数情况下它是最深层循环内的语句中的原操作，它的执行次数和包含它的语句的频度相同。

类似于算法的时间复杂度，本书以 空间复杂度 作为算法所需存储空间的量度，记作 S（n)=O（f(n))

3、算法与程序的区别

	算法	程序
本质	一个有效方法的精确指令序列，是解决问题的一种思想。它基于特定的计算模型（如图灵机）。	算法的一种具体实现，是使用某种编程语言编写的、能在计算机上执行的代码集合。
形式	独立于实现。通常用伪代码、流程图或自然语言描述。其核心是控制结构（顺序、选择、循环）和基本操作的集合。	依赖于语言。由特定编程语言的语法元素（如关键字、数据类型、运算符）和语法规则构成。
状态	通常是静态的、无状态的。它描述的是步骤本身，不包含运行时的数据。	是动态的、有状态的。程序在执行时拥有状态，即其变量在内存中的当前值集合。
存在性	一个逻辑实体。即使没有被编写成代码，算法作为一种思路也是存在的。	一个物理实体。以源代码或可执行文件的形式存在。
正确性

关注功能性准确性，即对于所有合法的输入，在有限的步骤内是否能产生预期的结果。可通过数学方法（如循环不变式、断言）证明。

除了功能正确性外，还重视稳定性、效率（例如时间/空间复杂度在具体环境下的表现）和容错能力。

评判标准

主要评估其时间复杂度和空间复杂度。

除效率之外，还评估其可读性、可维护性、可移植性、模块化程度等软件工程指标。

1. 算法必须是有限的，程序不一定具备有限性（例如操作系统、Web服务器图形用户界面应用）；
2. 算法的有限性：一个算法在执行有限步之后必须终止，并且每一步都需在有限时间内完成。这是算法的基本特征之一（另外四个为：输入、输出、确定性、可行性）。
3. 程序不一定具备有限性：程序是特定编程语言下的实现，它作为一个在计算机上运行的实体，其生命周期不一定符合“有限性”。

因此，“有限性”是算法作为数学和逻辑抽象的必要条件，但不是程序作为执行实体的必需条件。算法是对问题解决步骤的规范描述，而程序则是特定编程语言下的具体实现。

算法是计算过程的抽象概括，定义了“做什么”以及“如何做”的逻辑步骤，其正确性与效率分析独立于任何具体的编程语言和计算机系统。程序则是在特定冯·诺依曼体系结构计算机上的实例化，必须处理具体的数据类型、内存管理、I/O接口等实现细节，是将静态的算法思想转化为动态、可执行的进程的载体。

算法是程序的灵魂，程序则是算法的表现形式。

2. 程序中的指令必须为机器可执行，而算法中的指令则无此限制；
3. 算法指令的抽象性：算法是一个思维框架，是对解决问题的方法与步骤的逻辑概括。其核心在于准确表达计算过程的逻辑，而不关注由谁来执行。
4. 程序指令的具体性：程序是算法的具体实现，是在真实计算系统（通常是冯·诺依曼体系结构的计算机）上运行的实际代码。

算法的指令为抽象的逻辑步骤，其正确性依赖于计算模型的公理系统；而程序的指令为具体的、基于特定计算环境的机器操作，其可执行性是存在的前提条件。

3. 算法是对特定问题求解步骤的一种描述，而程序则是算法在计算机上的具体实现（一个算法若用程序设计语言来描述，就成为一个程序）；
4. 算法必须正确无误，而程序可能是错误的；
5. 数据结构 + 算法 = 程序。这一观点由瑞士计算机科学家尼克劳斯·维尔特在其1976年出版的经典著作《算法+数据结构=程序》中提出。

数据组织是关键
算法与数据结构的紧密联系
算法设计依赖于数据结构
数据结构的选择取决于算法。
算法：定义了程序的逻辑和控制流程。
数据结构：定义了信息的表示和存储模型
程序 = 算法 + 数据结构 + [设计模式 + 架构 + 语言范式 + ...]

特征

	算法	程序
本质	对解决问题步骤的描述（蓝图）	算法在计算机上的具体实现（建筑）
存在性	抽象的逻辑实体	具体的物理实体（代码文件）
有限性	必须满足（逻辑步骤有限）	不一定满足（可以是无限循环的服务）
指令	抽象，无执行限制	具体，必须为机器可执行
依赖性	独立于语言与机器	依赖于特定的语言、系统与硬件

数据结构的相关概念

1. 数据结构包括数据的逻辑结构和存储结构，是相互之间存在一种或多种特定关系的数据元素集合。
2. 数据元素是组成数据的基本单元。
3. 数据项是数据不可分割的最小单位。
4. 抽象数据类型是指一个数学模型及定义在该模型上的一组操作。
5. 数据的四种逻辑结构（集合、线性、树形、图形或网状）。这是一种逐步推进的关系：
   集合 → 线性 → 树形 → 图状。
   集合是关系最弱的结构。
   线性结构是树形结构的特例（每个节点只有一个子节点的树即为线性表）。
   树形结构是图状结构的特例（一种无环、连通的“有向图”）。
6. 数据的四种存储结构（顺序、链式、索引、散列）；

存储结构	核心机制	优点	缺点	典型应用
顺序存储	物理位置相邻	随机存取、存储密度高	预分配、插入删除慢	数组、矩阵
链式存储	附加指针	动态灵活、插入删除快	不可随机存取、存储密度低	链表、树、图
索引存储	建立索引表	检索速度快	需额外空间、需维护索引	数据库索引、文件系统
散列存储	哈希函数直接计算	存取速度极快(O(1))	存在冲突、不支持顺序访问	哈希表、字典、缓存

不论是顺序存储结构还是链式存储结构，都要存储数据元素本身和数据元素之间的关系。

5. 数据逻辑结构与存储结构的区别和联系

区别：数据的逻辑结构是指数据元素间的逻辑关系，独立于计算机；数据的存储结构是指数据结构在计算机中的表示形式，依赖于计算机语言。

联系：一种逻辑结构可以用多种存储结构来存储；一种存储结构可以用来存多种逻辑结构。

分析问题 → 抽象出数据的逻辑结构 → 根据操作需求选择最合适的存储结构 → 在存储结构上实现算法 → 解决问题

二、线性表

1. 线性表的定义：从数据对象、元素间的关系、基本操作三个方面进行阐述。

方面	核心阐述
数据对象	由 n 个类型相同的数据元素构成的有限序列。
元素关系	一对一的线性关系，除首尾外，每个元素有且仅有一个直接前驱和一个直接后继。
基本操作	ADT 抽象数据类型名{ 数据对象：<数据对象的定义> 数据关系：<数据关系的定义> 基本操作：<基本操作的定义> }ADT 抽象数据类型名

定义了结构的生命周期（启动、销毁）、数据管理（增加、删除、修改）和数据查询（检索、遍历）等一系列操作。

2、线性表的两种存储形式及其优劣点

特性维度	顺序存储结构（顺序表）	链式存储结构（链表）
基本原理	使用一段地址连续的存储单元（如数组）依次存放元素。	利用一组任意的存储单元（结点）存放元素。结点包含数据区和指针区。
元素关系表示	通过元素的物理位置（下标）相邻来隐含表达逻辑关系。	通过显式的链接（链） 来表达元素间的逻辑关联。
空间分配	静态或动态分配，但均需预先申请一块连续的存储区域。	动态分配，在需要时动态申请单个结点的空间，无需预先分配整个表所需空间。
随机访问	支持，高效。	不支持，低效。
通过下标可直接计算出地址，时间复杂度为 O(1)。		必须从表头开始顺序遍历，平均时间复杂度为 O(n)。
插入/删除操作	平均需要移动大量元素，时间复杂度为 O(n)。	只需修改指针，无需移动元素，已知位置后时间复杂度为 O(1)。
?		在表头操作：移动n个元素。 (但查找操作位置本身需要 O(n)) ? 在表尾操作：移动0个元素。 ? 平均：移动 n/2 个元素。
存储密度	存储密度 = 1（高）	存储密度 < 1（低）
	只存放数据元素本身，无额外开销。	每个结点除了数据区，还需要额外的指针区来储存地址。
内存结构	连续的内存块。	分散的内存块，通过指针链接。
结构开销	需要预分配固定大小的空间，可能造成空间浪费（分配过多）或溢出（分配不足）。	每个元素都有指针的结构开销，但总体空间是按需申请的。
容量管理	扩容操作（如C++的vector）通常代价高昂，需要分配新数组并复制所有元素。	容量理论上只受系统内存总量限制，扩容灵活。
缓存友好性	高。由于内存连续，缓存 locality 好，访问效率高。	低。内存分散，缓存命中率低。
代表实现	数组、C++ STL中的 vector、Java中的 ArrayList。	单链表、双链表、循环链表、C++ STL中的 list、Java中的 LinkedList。
核心权衡		顺序表用 “静态空间” 和 “移动元素” 的代价，换来了 “随机访问” 的高效；链表则用 “额外指针空间” 和 “遍历查找” 的代价，换来了 “动态增长” 和 “插入删除” 的灵活。

1）线性表的顺序存储是指在内存中用地址连续的一块存储区域对线性表中的各元素按其逻辑次序依次存放，以这种形式存储的线性表称为顺序表。

2）线性表的链式存储结构是用一组任意的存储单元储存自身的信息外还需保存直接前趋或后继元素的存储位置。因此，链式存储结构的线性表其元素之间的逻辑关联是通过节点的指针区来表达的。

3）顺序存储的优势：方法简单、使用数组实现容易；无需为表示节点间的逻辑关系而增加额外开销；具有按元素序号随机访问的特点。

顺序存储的不足：进行插入、删除操作时，平均需移动表中一半的元素，效率较低；需预先分配足够大的存储空间，若估计过大，则会导致空间浪费，预估过小又会造成溢出。

4）链表的优点和缺点恰好与顺序表相反。

3. 与线性表两种存储形式相关的信息

链表类型	结构特点	优点	缺点
单链表	结点只有一个指针区 next，指向直接后继。	结构简单，空间开销小。	无法逆向访问，查找前驱困难。
双链表	结点有两个指针区：prior（指向前趋）和 next（指向后继）。	可以双向遍历，插入、删除操作更灵活（可直接获取前趋节点）。	空间开销更大（每个结点多一个指针），操作稍复杂。
循环单链表	在单链表基础上，最后一个结点的 next 指针指向头结点（或第一个结点）。	从任意结点出发都可访问全表。	操作时需注意防止死循环。
循环双链表	在双链表基础上，头结点的 prior 指向尾结点，尾结点的 next 指向头结点。	双向循环，功能最全面，操作最方便。	结构最复杂，空间开销最大。
静态链表	使用数组来描述链表！数组的每个元素是一个结构体，包含 data 和 cur（游标，相当于 next，存储下一个元素的下标）。	在不支持指针的高级语言（如早期Basic）中实现链表功能；允许固定空间内的动态分配。	需要预分配固定大小的数组；失去顺序存储随机访问的特点；需自己管理空闲空间。

1）线性表中逻辑相邻的两个元素其存放位置不一定相邻；

2）线性表链式结构表示不一定优于顺序存储；

3）链式存储方式以指针表示结点间逻辑关系：一个需频繁进行插入，删除操作的线性表应采用链式存储结构；

4）线性表元素个数稳定，很少进行插入和删除操作应采用顺序存储结构；

5）若线性表最常用的操作是存取第i个元素及前趋元素的值，则采用顺序存储方式最节省运算时间。

6）在顺序存储形式，链式存储形式上删除元素的平均时间复杂度。

操作	顺序表	链表（单链表）
插入 ListInsert(&L, i, e)	1. 合法性检查（i是否有效）。 2. 空间检查（是否已满）。	1. 合法性检查（i是否有效）。 2. 空间检查（是否已满）。

2. 查找前驱：定位第 i-1 个节点（即插入位置的前继节点 p）。

3. 移动元素：将第 i 个至第 n 个元素整体后移一个位置。

3. 创建新节点 s，其数据域设置为 e。

4. 放入新元素：在位置 i 插入 e。

4. 修改指针：

5. 表长增加1。

s->next = p->next;

时间复杂度：O(n)，主要成本在于移动元素。

p->next = s;

时间复杂度：O(1)（已知前继节点位置），但查找前继节点本身为 O(n)。

删除 ListDelete(&L, i, &e)

1. 合法性检查（i 是否有效，表是否为空）。

1. 合法性验证。

2. 取出被删元素：e = L.data[i-1]。

2. 查找前驱：定位第 i-1 个节点 p。

3. 移动元素：将第 i+1 个至第 n 个元素整体前移一个位置。

3. 定位待删节点：q = p->next;

4. 表长减少1。

4. 修改指针：p->next = q->next;

时间复杂度：O(n)，主要成本在于移动元素。

5. 取出/释放：e = q->data; 然后释放节点 q。

时间复杂度：O(1)（已知前继节点位置），但查找前继节点本身为 O(n)。

4.线性表的建立、插入、删除、输出

顺序表的类型定义、插入、删除、单链表的创建（头插法、尾插法）、插入（后插基本操作）、删除、输出历来都是重点。

如删除顺序表中某元素需移动多少个元素，在顺序表中插入一个元素需移动多少个元素等。

场景

推荐存储结构

理由

需要频繁按索引随机访问（如 get(i)， set(i, e)）

顺序表

其随机访问时间复杂度为 O(1)，链表则为 O(n)。

需要频繁在头部/中部进行插入/删除

链表

链表插入/删除的时间复杂度为 O(1)（忽略查找），而顺序表需 O(n) 移动元素。

已知最大规模，且操作多集中在尾部（如栈）

顺序表

顺序表尾插/尾删亦是 O(1)，且存储密度高，缓存友好。

长度变化剧烈，或无法预估大小

链表

链表可真正实现按需分配，避免顺序表扩容带来的性能抖动。

实现复杂数据结构的基础（如树、图的邻接表）

链表

其动态和递归特性非常适合表示非线性结构。

内存紧张，追求极致存储效率

顺序表

存储密度为1，没有指针的额外开销。

例1：设有一带头节点的数据域为整型数据的单链表 h，给出单链表节点类型定义，并设计算法输出单链表中的所有元素。

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

void PrintList(LinkList h) {
    // h 是带头结点的单链表的头指针
    if (h == NULL) {
        printf("链表不存在！\n");
        return;
    }
    
    LNode *p = h->next; // p 指向第一个数据节点
    if (p == NULL) {
        printf("链表为空！\n");
        return;
    }
    
    printf("单链表中的元素为：");
    while (p != NULL) {
        printf("%d ", p->data); // 输出当前节点的数据
        p = p->next;           // p 移向下一个节点
    }
    printf("\n");
}

例2：设有一带头节点的数据域为整型数据的单链表 H，给出单链表结点类型定义并设计算法统计单链表中元素 x 的个数。

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

// 定义单链表节点类型
typedef struct LNode {
    int data;           // 数据域，存储整型数据
    struct LNode *next; // 指针域，指向下一个节点
} LNode, *LinkList;

int CountX(LinkList H, int x) {
    // H 是带头结点的单链表的头指针
    // x 是要统计的目标元素
    if (H == NULL) {
        printf("链表不存在！\n");
        return 0;
    }
    
    LNode *p = H->next; // p 指向第一个数据节点
    int count = 0;      // 初始化计数器
    
    while (p != NULL) {
        if (p->data == x) {
            count++;    // 找到目标元素，计数器加1
        }
        p = p->next;    // 移动到下一个节点
    }
    
    return count;       // 返回统计结果
}

算法分析

时间复杂度: O(n)，其中 n 为链表长度。需要遍历所有节点一次。

空间复杂度: O(1)，仅使用了固定数量的临时变量（

p

和

count

）。

5. 单链表结点的作用：简化运算。

三、栈和队列

1. 栈和队列的概念、特点

维度	栈	队列
基本概念	一种只能在一端（栈顶）进行插入和删除操作的线性表。	一种允许在一端（队尾）插入，在另一端（队头）删除的线性表。
逻辑结构	线性结构	线性结构
数据关系	元素之间具有一对一的线性关系。	元素之间具有一对一的线性关系。
操作规则	后进先出或先进后出。	先进先出。
类似于一摞盘子，你只能取最上面的那个。类似于现实生活中的排队，先来的人先接受服务。
插入操作名称	入栈、压栈	入队、进队
插入操作位置	栈顶	队尾
删除操作名称	出栈、弹栈	出队、离队
删除操作位置	栈顶	队头
访问操作	只能访问栈顶元素。	只能访问队头和队尾元素（有些实现仅允许访问队头）。
核心操作	Push(S, e): 入栈 Pop(S, &e): 出栈 GetTop(S, &e): 取栈顶	EnQueue(Q, e): 入队 DeQueue(Q, &e): 出队 GetHead(Q, &e): 取队头
存储结构	1. 顺序栈（基于数组） 2. 链栈（基于链表）	1. 顺序队列（基于数组） 2. 链队列（基于链表） 3. 循环队列（顺序队列的优化）
典型应用	1. 函数调用栈（保存现场、返回地址） 2. 表达式求值（中缀转后缀） 3. 括号匹配 4. 深度优先搜索 5. 撤销机制	1. 操作系统作业调度（如打印机任务队列） 2. 消息队列 3. 广度优先搜索 4. 多线程间的数据缓冲

1) 栈和队列是特殊的线性表；

2) 栈和队列的存储方式：既可以是顺序存储，又可以是链式存储；

3) 同一栈内各元素的类型必须一致；

4) 栈是限定仅能在表尾一端进行插入、删除操作的线性表；

5) 队列是限定仅能在表头进行删除、表尾进行插入的线性表；

6) 栈的特点是后进先出，队列的特点是先进先出；

若将1，2，3按先后次序入栈，出栈顺序不可能为3，1，2。

7）在进行进栈操作时，应首先检查栈是否已满；在进行退栈操作时，应先判断栈是否为空。当栈中有n个元素，在尝试进栈时出现溢出，则说明该栈的最大容量为n。

2. 顺序栈、链栈、循环队列、链队列

1）循环队列解决的问题：虚假溢出

2）循环队列判断空和满的条件：在少用一个存储单元的基础上进行

front == rear时队空；
（rear+1)%maxsize==front 时队满

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：数据结构 Structure Aggregate OverFlow Elements

相关内容：数据结构要点复习