第0章 C语言：Python的底层视角
Python是一门高级语言，它隐藏了内存管理的细节，让我们能够专注于解决问题本身。然而，理解底层机制对于深入掌握数据结构至关重要。本章将通过C语言来揭示Python隐藏的细节，帮助读者理解内存地址、指针以及链表的真正实现方式。
0.1 为什么需要C语言
Python中的列表和字典等数据结构使用起来非常方便，但它们是如何在内存中存储的？当我们创建一个列表并追加元素时，底层发生了什么？要回答这些问题，我们需要了解内存地址和指针的概念。
C语言直接暴露了这些底层概念，让我们能够精确控制内存的使用方式。通过学习C语言的指针，我们可以更好地理解：
- 变量在内存中是如何存储的
- 链表节点之间是如何连接的
- 为什么链表的插入删除比数组快
- Python中的引用本质上是什么
0.2 内存地址与变量
计算机内存由大量存储单元组成，每个存储单元都有唯一的编号，称为地址。当我们声明一个变量时，计算机会在内存中分配空间存储这个变量的值。
Memory Address
/* 0-1 查看变量的内存地址 */
#include <stdio.h>
int main() {
int a = 10;
int b = 20;
int c = 30;
printf("变量a: 值=%d, 地址=%p\n", a, (void*)&a);
printf("变量b: 值=%d, 地址=%p\n", b, (void*)&b);
printf("变量c: 值=%d, 地址=%p\n", c, (void*)&c);
return 0;
}
运行这段程序，你会看到每个变量都有一个不同的地址。在大多数系统中，int类型占4个字节，相邻变量的地址通常相差4。地址用十六进制表示，如0x7fff5fbff8ac。
取地址运算符&可以获取任何变量的地址。这与Python中的id()函数类似：
# Python中查看对象的"地址"
a = 10
b = 20
print(f"a的id: {id(a)}")
print(f"b的id: {id(b)}")
Python的id()返回的是对象的标识符，在CPython实现中就是对象的内存地址。
不同类型的变量占用不同大小的内存空间：
/* 0-2 不同类型变量的大小 */
#include <stdio.h>
int main() {
printf("char: %zu 字节\n", sizeof(char));
printf("short: %zu 字节\n", sizeof(short));
printf("int: %zu 字节\n", sizeof(int));
printf("long: %zu 字节\n", sizeof(long));
printf("float: %zu 字节\n", sizeof(float));
printf("double: %zu 字节\n", sizeof(double));
return 0;
}
在64位系统上，输出通常是：char 1字节，short 2字节，int 4字节，long 8字节，float 4字节，double 8字节。
0.3 指针的概念
指针是存储内存地址的变量。通过指针，我们可以间接访问和修改其他变量的值。这是理解链表等数据结构的关键。
Pointer Basics
/* 0-3 指针的基本使用 */
#include <stdio.h>
int main() {
int num = 42;
int *ptr = # /* ptr存储num的地址 */
printf("num的值: %d\n", num);
printf("num的地址: %p\n", (void*)&num);
printf("ptr的值(存储的地址): %p\n", (void*)ptr);
printf("ptr指向的值: %d\n", *ptr);
/* 通过指针修改值 */
*ptr = 100;
printf("\n通过指针修改后:\n");
printf("num的值: %d\n", num);
return0;
}
这段代码展示了指针的两个核心操作：
- 取地址 (
&)：获取变量的内存地址 - 解引用 (
*)：通过指针访问其指向的值
声明指针时，类型决定了通过该指针访问内存时解释数据的方式：
int *iptr; /* 指向int的指针 */
char *cptr; /* 指向char的指针 */
double *dptr; /* 指向double的指针 */
Python中的变量赋值实际上就是引用的传递，类似于C语言的指针：
# Python引用示例
a = [1, 2, 3]
b = a # b和a指向同一个列表对象
b.append(4)
print(a) # [1, 2, 3, 4] - a也被修改了
在C语言中，这相当于两个指针指向同一块内存。
0.4 指针与数组
数组是一块连续的内存空间。数组名在大多数情况下会"退化"为指向首元素的指针。
Pointer and Array
/* 0-4 指针与数组的关系 */
#include <stdio.h>
int main() {
int arr[5] = {10, 20, 30, 40, 50};
int *ptr = arr; /* ptr指向arr[0] */
printf("数组元素访问:\n");
for (int i = 0; i < 5; i++) {
printf(" arr[%d] = %d, *(ptr + %d) = %d\n",
i, arr[i], i, *(ptr + i));
}
printf("\n指针运算:\n");
printf(" arr的地址: %p\n", (void*)arr);
printf(" arr+1的地址: %p (增加了%d字节)\n",
(void*)(arr + 1), (int)((char*)(arr + 1) - (char*)arr));
return0;
}
arr[i]和*(arr + i)完全等价。指针加1不是地址加1，而是加上sizeof(类型)的字节数。int指针加1，地址增加4字节。
这与Python列表的重要区别是：C数组在内存中连续存储，而Python列表存储的是对象的引用，元素本身可能分散在内存各处。
/* 0-5 指针遍历数组 */
#include <stdio.h>
void print_with_pointer(int *arr, int size) {
printf("使用指针遍历: ");
for (int i = 0; i < size; i++) {
printf("%d ", *arr); /* 解引用 */
arr++; /* 移动到下一个元素 */
}
printf("\n");
}
int main() {
int arr[5] = {1, 2, 3, 4, 5};
print_with_pointer(arr, 5);
return0;
}
0.5 动态内存分配
C语言中，我们可以使用malloc在运行时动态分配内存。这在创建链表等数据结构时非常重要。
/* 0-6 动态内存分配 */
#include <stdio.h>
#include <stdlib.h>
int main() {
/* 分配存储5个int的空间 */
int *arr = (int*)malloc(5 * sizeof(int));
if (arr == NULL) {
printf("内存分配失败\n");
return1;
}
/* 使用动态数组 */
for (int i = 0; i < 5; i++) {
arr[i] = i * 10;
}
printf("动态数组内容: ");
for (int i = 0; i < 5; i++) {
printf("%d ", arr[i]);
}
printf("\n");
/* 扩展数组 */
arr = (int*)realloc(arr, 10 * sizeof(int));
for (int i = 5; i < 10; i++) {
arr[i] = i * 10;
}
printf("扩展后内容: ");
for (int i = 0; i < 10; i++) {
printf("%d ", arr[i]);
}
printf("\n");
/* 释放内存 */
free(arr);
return0;
}
malloc分配的内存位于堆区，需要手动用free释放。忘记释放会导致内存泄漏。Python通过垃圾回收机制自动管理内存，不需要手动释放。
0.6 链表节点结构
链表是理解指针应用的绝佳例子。每个链表节点包含数据和指向下一个节点的指针。与数组不同，链表节点在内存中不必连续存储。
Linked List Node
/* 0-7 链表节点的定义 */
#include <stdio.h>
#include <stdlib.h>
/* 链表节点结构 */
typedefstruct Node {
int data; /* 数据域 */
struct Node *next;/* 指针域，指向下一个节点 */
} Node;
/* 创建新节点 */
Node* create_node(int data) {
Node *new_node = (Node*)malloc(sizeof(Node));
if (new_node == NULL) {
printf("内存分配失败\n");
returnNULL;
}
new_node->data = data;
new_node->next = NULL;
return new_node;
}
int main() {
/* 创建三个节点 */
Node *n1 = create_node(10);
Node *n2 = create_node(20);
Node *n3 = create_node(30);
/* 连接节点 */
n1->next = n2;
n2->next = n3;
/* n3->next 已经是 NULL */
/* 遍历链表 */
Node *current = n1;
printf("链表内容: ");
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
/* 打印节点信息 */
printf("\n节点详细信息:\n");
printf("节点1: 地址=%p, 数据=%d, next=%p\n",
(void*)n1, n1->data, (void*)n1->next);
printf("节点2: 地址=%p, 数据=%d, next=%p\n",
(void*)n2, n2->data, (void*)n2->next);
printf("节点3: 地址=%p, 数据=%d, next=%p\n",
(void*)n3, n3->data, (void*)n3->next);
/* 释放内存 */
free(n1);
free(n2);
free(n3);
return0;
}
链表节点通过next指针连接。n1->next = n2使n1指向n2。这种连接方式让节点可以分散在内存任何位置，不同于数组必须连续存储。
0.7 单向链表的完整实现
现在我们实现一个完整的单向链表，包括创建、插入、删除和遍历等操作。
Singly Linked List
/* 0-8 单向链表完整实现 */
#include <stdio.h>
#include <stdlib.h>
typedefstruct Node {
int data;
struct Node *next;
} Node;
/* 创建新节点 */
Node* create_node(int data) {
Node *node = (Node*)malloc(sizeof(Node));
node->data = data;
node->next = NULL;
return node;
}
/* 在链表头部插入 */
void insert_front(Node **head, int data) {
Node *new_node = create_node(data);
new_node->next = *head;
*head = new_node;
}
/* 在链表尾部插入 */
void insert_back(Node **head, int data) {
Node *new_node = create_node(data);
if (*head == NULL) {
*head = new_node;
return;
}
Node *current = *head;
while (current->next != NULL) {
current = current->next;
}
current->next = new_node;
}
/* 在指定位置插入 */
void insert_at(Node **head, int position, int data) {
if (position < 0) return;
if (position == 0) {
insert_front(head, data);
return;
}
Node *current = *head;
for (int i = 0; i < position - 1 && current != NULL; i++) {
current = current->next;
}
if (current == NULL) return;
Node *new_node = create_node(data);
new_node->next = current->next;
current->next = new_node;
}
/* 删除指定值的节点 */
void delete_node(Node **head, int data) {
if (*head == NULL) return;
Node *current = *head;
Node *prev = NULL;
while (current != NULL && current->data != data) {
prev = current;
current = current->next;
}
if (current == NULL) return; /* 未找到 */
if (prev == NULL) {
*head = current->next;
} else {
prev->next = current->next;
}
free(current);
}
/* 查找节点 */
Node* search(Node *head, int data) {
while (head != NULL) {
if (head->data == data) {
return head;
}
head = head->next;
}
returnNULL;
}
/* 打印链表 */
void print_list(Node *head) {
printf("链表: ");
while (head != NULL) {
printf("%d -> ", head->data);
head = head->next;
}
printf("NULL\n");
}
/* 获取链表长度 */
int get_length(Node *head) {
int count = 0;
while (head != NULL) {
count++;
head = head->next;
}
return count;
}
/* 释放整个链表 */
void free_list(Node *head) {
Node *temp;
while (head != NULL) {
temp = head;
head = head->next;
free(temp);
}
}
int main() {
Node *head = NULL;
printf("=== 构建链表 ===\n");
insert_back(&head, 10);
insert_back(&head, 20);
insert_back(&head, 30);
insert_front(&head, 5);
print_list(head);
printf("长度: %d\n", get_length(head));
printf("\n=== 在位置2插入15 ===\n");
insert_at(&head, 2, 15);
print_list(head);
printf("\n=== 删除值为20的节点 ===\n");
delete_node(&head, 20);
print_list(head);
printf("\n=== 查找节点 ===\n");
Node *found = search(head, 15);
if (found != NULL) {
printf("找到节点，值=%d，地址=%p\n", found->data, (void*)found);
}
free_list(head);
return0;
}
链表操作的核心是正确维护next指针：
- 头部插入：新节点的
next指向原头节点，然后更新头指针 - 尾部插入：遍历到最后一个节点，将其
next指向新节点 - 中间插入：找到前驱节点，新节点的
next指向前驱的next，前驱的next指向新节点 - 删除节点：找到前驱节点，将其
next跳过被删除节点
0.8 双向链表
单向链表只能从头到尾遍历。双向链表的每个节点有两个指针，分别指向前驱和后继，可以双向遍历。
Doubly Linked List
/* 0-9 双向链表实现 */
#include <stdio.h>
#include <stdlib.h>
typedefstruct DNode {
int data;
struct DNode *prev;/* 指向前驱节点 */
struct DNode *next;/* 指向后继节点 */
} DNode;
/* 创建新节点 */
DNode* create_dnode(int data) {
DNode *node = (DNode*)malloc(sizeof(DNode));
node->data = data;
node->prev = NULL;
node->next = NULL;
return node;
}
/* 头部插入 */
void dlist_insert_front(DNode **head, int data) {
DNode *new_node = create_dnode(data);
if (*head != NULL) {
new_node->next = *head;
(*head)->prev = new_node;
}
*head = new_node;
}
/* 尾部插入 */
void dlist_insert_back(DNode **head, int data) {
DNode *new_node = create_dnode(data);
if (*head == NULL) {
*head = new_node;
return;
}
DNode *current = *head;
while (current->next != NULL) {
current = current->next;
}
current->next = new_node;
new_node->prev = current;
}
/* 正向遍历 */
void dlist_print_forward(DNode *head) {
printf("正向: ");
while (head != NULL) {
printf("%d <-> ", head->data);
head = head->next;
}
printf("NULL\n");
}
/* 反向遍历 */
void dlist_print_backward(DNode *head) {
if (head == NULL) {
printf("反向: NULL\n");
return;
}
/* 找到末尾 */
while (head->next != NULL) {
head = head->next;
}
printf("反向: ");
while (head != NULL) {
printf("%d <-> ", head->data);
head = head->prev;
}
printf("NULL\n");
}
/* 删除节点 */
void dlist_delete(DNode **head, int data) {
if (*head == NULL) return;
DNode *current = *head;
while (current != NULL && current->data != data) {
current = current->next;
}
if (current == NULL) return;
/* 更新前驱节点的next */
if (current->prev != NULL) {
current->prev->next = current->next;
} else {
*head = current->next;
}
/* 更新后继节点的prev */
if (current->next != NULL) {
current->next->prev = current->prev;
}
free(current);
}
/* 释放链表 */
void dlist_free(DNode *head) {
while (head != NULL) {
DNode *temp = head;
head = head->next;
free(temp);
}
}
int main() {
DNode *head = NULL;
printf("=== 构建双向链表 ===\n");
dlist_insert_back(&head, 10);
dlist_insert_back(&head, 20);
dlist_insert_back(&head, 30);
dlist_insert_front(&head, 5);
dlist_print_forward(head);
dlist_print_backward(head);
printf("\n=== 删除值为20的节点 ===\n");
dlist_delete(&head, 20);
dlist_print_forward(head);
dlist_print_backward(head);
dlist_free(head);
return0;
}
双向链表的优势：
- 双向遍历：可以从任意节点向前或向后遍历
- 删除更简单：不需要找前驱节点，因为每个节点都有
prev指针 - 更灵活：可以从尾部开始操作
缺点是每个节点需要额外的空间存储prev指针，插入操作需要维护更多的指针。
0.9 Python与C的对比
| 特性 | C语言 | Python |
|---|---|---|
| 变量 | 存储具体值 | 存储对象引用 |
| 内存地址 | 直接可见（指针） | 通过id()间接查看 |
| 内存管理 | 手动malloc/free | 自动垃圾回收 |
| 空指针 | NULL，访问会崩溃 | None，安全处理 |
| 链表实现 | 需要自己实现 | 使用list或自定义类 |
| 性能 | 编译后直接运行 | 解释执行，较慢 |
Python中实现链表：
# Python链表实现
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def insert_front(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def print_list(self):
current = self.head
while current:
print(current.data, end=' -> ')
current = current.next
print('None')
# 使用
ll = LinkedList()
ll.insert_front(10)
ll.insert_front(20)
ll.print_list() # 20 -> 10 -> None
Python的实现更加简洁，但底层的内存管理和指针操作被隐藏了。通过学习C语言实现，我们能够理解Python链表在底层是如何工作的。
0.10 小结
本章通过C语言揭示了数据结构的底层实现：
- 内存地址：每个变量在内存中都有唯一地址，通过
&运算符获取 - 指针：存储地址的变量，通过
*解引用访问指向的值 - 单向链表：节点通过
next指针连接，适合单向遍历 - 双向链表：节点有
prev和next两个指针，可以双向遍历
理解这些概念后，再回到Python，你会发现列表、字典等数据结构的设计变得更加清晰。Python隐藏了复杂性，但底层仍然是内存地址、指针和链表这些基本概念在工作。
有了这些基础，接下来我们将学习Python中的各种数据结构与算法，不需要再关心底层的内存管理细节，但会知道它们在幕后是如何工作的。
预览时标签不可点