数据结构笔记--导论

系列文章目录：

• 数据结构—导论
• 数据结构—算法基础
• 数据结构—线性表

数据结构的基本知识和导论

数据结构是计算机存储、组织数据的方式，数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。

Nikolaus Wirth 在其著作《Algorithms + Data Structures = Programs》中提出了这个著名的公式，强调了算法和数据结构在计算机科学中的重要性。数据结构的选择和设计对程序的效率、可扩展性和可维护性有着直接的影响。

那么什么是算法？

算法是解决特定问题的一系列步骤或规则，它描述了如何通过一系列计算步骤来解决问题。算法通常具有以下特性：

1. 输入：算法可以接受零个或多个输入，这些输入可以是数据、变量或外部信息。
2. 输出：算法必须产生一个或多个输出，这些输出是算法处理输入后的结果。
3. 确定性：算法的每一步骤都必须是明确的，不能有歧义。每个步骤都必须有明确的操作和结果。
4. 有限性：算法必须包含有限数量的步骤，不能无限循环。
5. 有效性：算法必须能在有限的时间内完成，不能无限期地运行。

算法通常用于解决实际问题，例如排序、搜索、计算、优化等。算法的设计和实现需要考虑时间复杂度和空间复杂度，以优化程序的效率和性能。

说白了就是：数据结构是计算机存储、组织数据的方式，而算法是解决特定问题的一系列步骤或规则，它描述了如何通过一系列计算步骤来解决问题。

本门课程需要学习的内容

1. 数据结构 :

   • 线性表
   • 栈和队列
   • 数组
   • 树和二叉树
   • 图
   • 哈希表

2. 算法 :

   • 排序算法（冒泡排序、选择排序、插入排序、快速排序、归并排序等）
   • 查找算法（顺序查找、二分查找、哈希查找等）
   • 图算法（深度优先搜索、广度优先搜索、最短路径算法等）
   • 动态规划算法

以下是一个简单的数据结构图示，展示了不同类型的数据结构之间的关系：如果看不到，请刷新

这门课基于C语言应该要熟练掌握的内容:

• 函数
• 数组
• 字符串
• 指针
• 内存解析
• 结构体

计算机体系结构

其中，黑色箭头指的是数据流，灰色箭头指的是指令流，黄色箭头指的是控制流。

严格意义上讲，存储器可以分为主存储器和辅助存储器，主存储器就是我们常说的内存，辅助存储器就是我们常说的硬盘。
另外ROM是只读存储器，RAM是随机存储器，RAM中的数据在断电后会被清空，而ROM中的数据在断电后不会清空。

内存条、显卡、各种适配器都有各自的存储地址空间，操作系统会将这些设备的存储地址空间抽象成一个巨大的一维数组空间。

对于内存的每个字节（bits）会分配一个唯一的地址，这个地址就是内存地址，内存地址由地址总线来决定，而内存地址中的每个字节会分配一个唯一的编号（32位或者64位），这个编号就是偏移量。

对于C语言其中int类型占4个字节，char类型占1个字节，float类型占4个字节，double类型占8个字节。地址（16进制）的计算方式为：地址 = 基地址 + 偏移量。

就以数组为例，int arr[10]，arr就是基地址，arr[0]的地址就是arr，arr[1]的地址就是arr + 1，arr[2]的地址就是arr + 2，以此类推。

指针

指针是C语言的重中之重，这里我们复习指针为了是更好的理解数据结构，以及自己编写数据结构。

指针是什么

指针是一个变量，其值为另一个变量的地址，即，指针变量的值就是另一个变量的地址，而该地址中存储的值就是指针变量所指的值。

具体的图例如上图所示，显然地，一个指针即一个新的变量，只不过这个变量存储的是另一个变量的地址，当然，其自身也有自己的地址。

大家可以猜猜这个程序输出什么？

#include<stdio.h>

int main()
{
    int a;
    int *p;
    a=10;p=&a;

    printf("%d\n",a); 
    printf("%d\n",*(&a)); 
}

指针的运算

指针可以进行以下运算：

• 取地址运算符：&，用于获取变量的地址。例如，int a = 10; int *p = &a;，其中p的值为变量a的地址。
• 解引用运算符：*，用于获取指针指向的变量的值。例如，int a = 10; int *p = &a; int b = *p;，其中b的值为变量a的值。
• 指针运算：指针可以进行加减运算，表示指针指向的地址的偏移量。例如，int a[10]; int *p = a; int *q = p + 2;，其中q的值为p的值加上2个int类型数据的字节大小。
• 指针比较：指针可以进行比较运算，表示指针指向的地址的大小关系。例如，int a[10]; int *p = a; int *q = a + 2; if (p < q) { ... }，其中if语句的条件为true，表示p指向的地址小于q指向的地址。
• 指针赋值：指针可以赋值为另一个指针的值，表示指针指向的地址相同。例如，int a[10]; int *p = a; int *q = p;，其中q的值为p的值，表示q和p指向的地址相同。
• 指针类型转换：指针可以进行类型转换，表示指针指向的数据类型不同。例如，int a = 10; int *p = &a; char *q = (char *)p;，其中q的值为p的值，表示q指向的数据类型为char。

指针与数组

指针和数组在C语言中有着密切的联系，指针可以用来访问和操作数组中的元素。

#include <stdio.h>

int main()
{
    int arr[5] = {1, 2, 3, 4, 5};
    int *p = arr;
    for (int i=0; i<sizeof(arr)/sizeof(arr[0]); i++)
    {
        printf("%d ", *(p + i));
    }
    return 0;
}

思考一下，为什么对于p指针加上i可以对应到下一个元素？这和我们之前说的一个int类型变量占用4个字节，那么指针p起初指向的地址（假如是：00000000005FFE8C）加上i（假如i=1），那么指针p指向的地址就是：00000000005FFE8D，而00000000005FFE8D这个地址存储的值还是指向arr[0]。而对于arr[1]的地址应该是00000000005FFE90，为什么这个循环到i=1的时候，能输出arr[1]的值呢？

这里是答案

实际上，给指针加上一个整数，加上的是这个整数和指针数据类型对应的字节数，也就是说，p指向的是int类型的数据，那么p+1就是p指向的地址加上sizeof(int)，也就是p指向的地址加上4个字节，所以p+1指向的就是arr[1]。
比如这个，p+1就是p+1*4。

下面我们来看看C/C++中各种数据类型所占的字节数

有符号数	无符号数	32位	64位
char	unsigned char	1	1
short	unsigned short	2	2
int	unsigned int	4	4
long	unsigned long	8	16
long long	unsigned long long	8	16
float		4	4
double		8	8

这个表格的数据要有印象，对于估算一个程序的时间复杂度和空间复杂度很有帮助。

指针与函数

指针可以用于函数参数和返回值，使得函数能够修改传入的参数，或者返回一个指向动态分配内存的指针。

#include <stdio.h>
#include <stdlib.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int main() {
    int x = 5, y = 10;
    printf("Before swap: x = %d, y = %d\n", x, y);
    swap(&x, &y); // 传入x和y的地址
    printf("After swap: x = %d, y = %d\n", x, y);
    return 0;
}

以上是一个非常简单的例子，在我们今后的学习中，我们会看到更多关于指针与函数的例子。比如以下利用指针实现一个简单的链表：

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

Node* createNode(int data) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

void printList(Node *head) {
    Node *current = head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

int main() {
    Node *head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    printList(head);
    return 0;
}

指针与结构体

指针可以用于指向结构体，使得可以通过指针访问结构体中的成员变量。

#include <stdio.h>

typedef struct {
    int x;
    int y;
} Point;

struct Point *createPoint(int x, int y) {
    struct Point *p = (struct Point *)malloc(sizeof(struct Point));  // 这里使用了堆内存，我们后面会讲
    // 如果不用堆内存实现，我们可以这么写：
    // struct Point p;
    // p.x = x;
    // p.y = y;
    // return &p;
    // 但是这样写的话，p是一个局部变量，当函数结束时，p就会被销毁，所以我们需要使用堆内存来保存p，这样即使函数结束，p也不会被销毁。
    p->x = x;
    p->y = y;
    return p;
}


int main() {
    struct Point *p = createPoint(1, 2);
    printf("Point: (%d, %d)\n", p->x, p->y);
    free(p); // 释放堆内存
    return 0;
}

上面的例子中，我们使用了一个createPoint的结构体函数，读取两个参数，然后返回一个指向结构体的指针，然后我们使用->运算符来访问结构体中的成员变量。
如果要继续创建新的Point，那么我们可以这样：

struct Point *p1 = createPoint(1, 2);
struct Point *p2 = createPoint(3, 4);

这时肯定又有小伙伴要问了，那如果我要创建很多个Point怎么办呢？

我们可以创建个数组来存储每个Point对应的地址，然后通过这个地址来访问每个Point的成员变量。那么恭喜你，你已经学会了链表的基本概念。

查看答案

//这里我们先创建个数组来存储每个Point对应的地址
Point *points[10]
//然后我们就可以通过这个地址来访问每个Point的成员变量
points[0] = createPoint(1, 2);
points[1] = createPoint(3, 4);
//...

指针与动态内存分配

C语言程序编译后，会在内存中分配一块区域，用于存储程序运行时的数据。这块区域分为栈区、堆区、全局区、常量区等。

1. 🧮 栈区（Stack）

   • 存储局部变量、函数参数、返回地址等。
   • 由编译器自动分配和释放，遵循后进先出（LIFO）原则。
   • 空间较小，速度快。
   • ⚠️ 注意：不要返回栈区局部变量的地址，否则会产生“野指针”问题。

2. 🧠 堆区（Heap）

   • 用于存储动态分配的内存。
   • 使用如 malloc()、calloc()、realloc() 分配，需要用 free() 显式释放。
   • 空间较大，但分配/释放较慢。
   • 由程序员管理，易发生内存泄漏。

3. 🌍 全局/静态区（Data Segment）

   • 包含全局变量和 static 修饰的静态变量。
   • 程序运行整个生命周期中都存在。
   • 编译时分配，程序结束时由系统自动释放。

4. 📜 常量区（Text/ROData Segment）

   • 用于存储只读数据，如字符串常量、const 修饰的全局常量。
   • 这些内容可能被编译器优化为存储在只读段，不能被修改（修改可能导致段错误 Segmentation Fault）。

然后根据上面的分区，我们可以有三种形式的内存分配方式：

分配方式	分配时间	生命周期	示例
静态分配	编译时	程序整个运行期间	全局变量、静态变量
栈分配	函数调用时	当前函数调用期间	局部变量、函数参数
堆分配	程序运行时	手动释放或程序结束	使用 malloc / free 分配和释放内存

🔍 小细节提醒：

1. 栈空间较小（一般几 MB），堆空间较大（取决于系统）。
2. 常量区有时和代码区在一个 segment（比如 Linux 下 .rodata）。
3. const 修饰的局部变量仍然分配在栈上，不在常量区；但 const 修饰的全局变量可能会被优化到常量区。

使用案例

#include <stdio.h>
#include <stdlib.h>

int main() {
    int *p = (int *)malloc(sizeof(int)); // 分配一个 int 大小的内存空间
    if (p == NULL) {
        printf("Memory allocation failed\n");
        return 1;
    }
    *p = 10; // 将 10 存入分配的内存空间
    printf("Value: %d\n", *p); // 输出 10
    free(p); // 释放分配的内存空间
    return 0;
}