数据结构核心：从基础概念到链表实现，程序员的必备内功

一、程序设计的本质：数据结构与算法的完美结合

程序 = 数据结构 + 算法——这是计算机科学中最为经典的公式之一。

数据结构：数据的组织方式

数据结构决定了数据在计算机中的存储和组织形式。好的数据结构能够让程序更高效地处理数据，就像图书馆需要科学的图书分类系统一样。

算法：处理数据的方法

算法是解决特定问题的一系列操作步骤，它告诉计算机如何有效地处理数据。同一组数据，不同的算法处理效率可能有天壤之别。

二、程序效率的两大衡量指标

时间复杂度：时间效率的量化

时间复杂度描述了数据量增长与程序运行时间增长的关系。常见的时间复杂度从小到大排序：

• O(1)：常数时间，理想状态

• O(log n)：对数时间，二分查找等算法

• O(n)：线性时间，简单遍历

• O(n log n)：快速排序、归并排序

• O(n²)：冒泡排序、选择排序

• O(2ⁿ)：指数时间，某些递归算法

空间复杂度：空间效率的衡量

空间复杂度关注数据量增长与程序所需存储空间的关系。在现代开发中，我们经常需要在时间和空间之间做出权衡。

三、数据结构的两个维度：逻辑与存储

逻辑结构：数据元素间的抽象关系

• 线性结构：一对一关系，如数组、链表、栈、队列

• 树形结构：一对多关系，如二叉树、B树

• 图形结构：多对多关系，如社交网络图

存储结构：数据在内存中的实际存放方式

1. 顺序存储（数组实现）

// 顺序表头文件定义
typedef int DataType;
extern DataType *CreateSeqlist(int len);

优点：

• 随机访问效率高（O(1)时间复杂度）

• 内存连续，缓存友好

缺点：

• 插入删除需要移动大量元素

• 大小固定，扩展成本高

2. 链式存储（链表实现）

// 单向链表节点定义
typedef struct node {
DataType Data;
struct node *pNext;
} node_t;

优点：

• 动态分配内存，灵活扩展

• 插入删除效率高（O(1)时间复杂度）

缺点：

• 随机访问效率低（O(n)时间复杂度）

• 额外指针空间开销

3. 索引存储与散列存储

• 索引存储：建立索引表提高查询效率

• 散列存储：通过哈希函数直接定位数据位置

四、链表：灵活的动态数据结构

链表的核心优势

链表的动态性使其在处理不确定数据量时具有天然优势。与数组不同，链表不需要预先分配固定大小的内存空间。

单向链表的操作函数

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

Node_t *CreateEmptyLinkList(void)
{
Node_t *pNewNode = NULL;

pNewNode = malloc(sizeof(Node_t));
if (NULL == pNewNode)
{
perror("fail to malloc");
return NULL;
}

pNewNode->pNext = NULL;

return pNewNode;
}

int InsertHeadNode(Node_t *pHead, DataType TmpData)
{
Node_t *pNewNode = NULL;

pNewNode = malloc(sizeof(Node_t));
if (NULL == pNewNode)
{
perror("fail to malloc");
return -1;
}

pNewNode->Data = TmpData;
pNewNode->pNext = pHead->pNext;
pHead->pNext = pNewNode;

return 0;
}

int ShowLinkList(Node_t *pHead)
{
Node_t *pTmpNode = NULL;

pTmpNode = pHead->pNext;
while (pTmpNode != NULL)
{
printf("%d ", pTmpNode->Data);
pTmpNode = pTmpNode->pNext;
}
printf("\\n");

return 0;
}

int DeleteLinkNode(Node_t *pHead, DataType TmpData)
{
int cnt = 0;
Node_t *pPreNode = NULL;
Node_t *pTmpNode = NULL;

pPreNode = pHead;
pTmpNode = pHead->pNext;

while (pTmpNode != NULL)
{
if (pTmpNode->Data == TmpData)
{
pPreNode->pNext = pTmpNode->pNext;
free(pTmpNode);
pTmpNode = pPreNode->pNext;
cnt++;
}
else
{
pTmpNode = pTmpNode->pNext;
pPreNode = pPreNode->pNext;
}
}

return cnt;
}

链表的变体形式