一、什么是数据结构很多同学第一次听到“数据结构”时会觉得它很抽象、很难入门。其实理解数据结构只需要抓住一句话数据结构就是研究“数据元素”与“数据元素”之间关系的学问。既然是一门“关系学”那么它研究的核心问题主要有三个这些数据之间是什么样的关系逻辑结构怎么把具有逻辑关系的数据真正存储到计算机中存储结构基于这样的关系如何对数据进行增加、删除、修改、查找等操作算法换句话说数据结构并不神秘它解决的是一个非常实际的问题当数据规模变大、数据之间关系变复杂时如何有组织、高效率地处理和存储这些数据。二、我们该怎么学习数据结构学习数据结构建议不要一开始就死记背代码而是按下面的顺序逐步推进先理解数据结构的特点它要解决什么问题、数据之间是什么关系。弄清楚数据的操作增加、删除、修改、查找、遍历、销毁等基本操作有哪些。重视指针链表这类链式结构离不开指针理解指针是理解链式存储的关键。动手写代码实现听懂不代表学会能自己写出可运行代码才算真正掌握。此外强烈建议大家养成一个学习习惯画图。链表就画出一个个结点用箭头标出next的指向。树就画成层次结构分清父结点和子结点。图就画出顶点和边观察多对多的关系。画图能把抽象的逻辑关系变得直观清晰是学习数据结构最高效的方法之一。三、前置知识C 语言基础数据结构课程通常使用 C 语言进行讲解因此需要先具备一定的 C 语言基础。学习阶段需要掌握的内容语法基础变量、数据类型、运算符、流程控制、函数等基本语法编程思维能用程序语言描述问题求解步骤并逐步实现处理少量数据使用普通变量处理单个或几个数据处理批量数据使用数组、结构体存储和处理同一类型的一组数据当数据规模继续增大、数据之间的关系不再是简单的“排成一列”时就需要更系统的手段来组织数据这就是数据结构出现的意义。四、为什么数据结构是优秀程序员的基本功一名优秀的程序员往往需要具备两项核心能力一门编程语言用来和计算机沟通、实现程序逻辑。数据结构与算法用来设计合理的数据组织方式和高效的解决思路。可以这样理解两者之间的关系好的程序设计 合适的算法 合适的数据结构。数据结构负责“怎么存”算法负责“怎么算”。两者相辅相成共同决定一个程序是否高效、稳定、易于维护。五、数据结构中的基本术语学习数据结构时几个基本术语必须先弄清楚术语含义数据是描述客观事物的符号是计算机能够操作的对象数据项组成数据元素的、有一定意义的最小单位数据元素数据的基本单位一个数据元素可以由若干个数据项组成数据对象性质相同的数据元素的集合是数据的子集在具体实践中例如一个学生信息表一个完整的“学生记录”就是数据元素是一个具有一定意义的基本单位。姓名、学号、成绩等就是组成学生记录的数据项。所有性质相同的学生记录构成数据对象也就是“学生”这种类型的数据集合。而“学生”、“课程”、“图书”等所有客观事物符号的总和就是更广义的数据。一句话总结数据结构就是研究“数据元素”与“数据元素”之间关系的学科。六、数据的逻辑结构逻辑结构反映的是数据元素之间逻辑上的对应关系它不关心数据在计算机里怎么存只关心数据之间“是什么关系”。常见的逻辑结构有四种1. 集合结构元素与元素之间同属一类除了“属于同一个集合”外没有其他关系。2. 线性结构元素与元素之间是一对一的关系可以理解为排成一条线例如0 - 1 - 2 - 3。在线性关系中除了起始元素和终了元素外每个元素都有自己的前驱结点和后继结点。3. 树形结构元素与元素之间是一对多的关系具有明显的层次性。例如班级管理中班主任下面可以管理班长、副班长、学习委员、纪委等多个角色班主任 ├── 班长 ├── 副班长 ├── 学委 ├── 纪委 └── 委4. 图形结构元素与元素之间是多对多的关系。最常见的应用场景就是地图软件城市与城市之间可以通过多条道路相互连通呈现复杂的网状关系。小结逻辑结构对应关系典型例子集合无对应关系同属一个集合的元素线性一对一数组、链表、队列、栈树形一对多文件目录、组织架构图形多对多地图导航、社交网络七、数据的存储结构逻辑结构描述的是“数据之间什么关系”但程序中的数据最终还是要存储到计算机内存中。存储结构回答的问题是怎么把具有逻辑关系的数据在内存中有效地存储下来常见的存储结构主要有四种1. 顺序存储结构使用连续的内存空间存放数据最典型的就是数组。2. 链式存储结构数据元素可以存放在不同位置通过指针把它们“串”起来最典型的就是链表。3. 索引结构类似看书时的目录额外维护一个索引表通过索引快速定位数据。4. 散列哈希结构通过哈希函数建立“值”与“存储位置”之间的映射关系值 -- 哈希函数 -- 存储位置八、顺序存储与链式存储的对比以存储一组具有线性逻辑关系的整数数据为例int sno[10] {0,1,2,3,4,5,6,7,8,9}; // 学号1. 顺序存储数组优点支持随机访问访问元素非常方便。缺点增加、删除元素比较麻烦通常需要整体移动数据。2. 链式存储链表优点增加、删除元素方便只需要修改指针指向。缺点访问某个元素需要从头遍历不支持随机访问。3. 数组增删操作的代价例如在原有数组基础上增加一个学号int sno[10] {0,1,2,3,4,5,6,7,8,9}; // 原数组 int sno1[11] {0,1,2,3,4,5,6,7,8,9,10}; // 增加一个学号思路如下新创建一个多一个元素的数组。将原数组中的数据拷贝过来再新增一个数值。释放原有空间。删除一个学号后后面的元素通常需要向前移动int sno1[10] {0,1,2,3,4,6,7,8,9};可以看到同一个逻辑关系的数据可以采用不同的存储结构不同的存储结构其处理思路算法也不相同。因此选择什么样的算法取决于我们要处理的是“逻辑结构 存储结构”综合后的实际数据。九、算法概述数据结构离不开算法。算法是对解决特定问题求解步骤的描述在计算机中表现为指令的有限序列每一条指令表示一个或多个操作。简单说算法就是解决问题的步骤。1. 算法的五个特征输入算法有零个或多个输入。输出算法至少有一个输出。有穷性算法在执行有限步骤后会结束不会无限循环。确定性每一步都有确定的含义不会产生歧义。可行性每一步都可以通过有限次基本运算完成。2. 好算法应具备的特点正确性能够得到正确的结果。可读性代码逻辑清晰便于阅读和理解。健壮性鲁棒性对非法输入能够妥善处理而不是直接崩溃。时间效率和存储量低即尽量低的时间复杂度和空间复杂度。简单理解时间复杂度关注的是执行时间随数据规模增长的速度空间复杂度关注的是占用的内存空间。好的算法应该在保证正确的前提下尽量做到又快又省。十、线性表顺序存储线性表是一对一的数据结构也是最常用、最基础的结构之一。它可以用顺序存储实现也可以用链式存储实现。使用数组顺序表存储线性表在各个语言中都非常常见C 语言int a[10];CvectorJavaArrayListPythonlist顺序表的基础操作包括创建增加删除修改查找销毁以 C 语言为例创建并使用动态数组int a[10]; // 静态数组 int *p malloc(sizeof(int) * 10); // 动态数组 insertArray(...); // 插入数据 deleteArray(...); // 删除数据 modifyArray(...); // 先找到再修改 findArray(...); // 查找 // 销毁释放堆区空间 free(p);顺序表的特点是便于随机访问、增删相对麻烦适合数据量稳定、读多改少的场景。十一、线性表链式存储链表链表是使用链式方式实现的线性结构。链表的每一个结点通常包含两部分数据域存放真正的数据。指针域存放下一个结点的地址。带头链表中几个重要概念头结点链表最前面的辅助结点数据域通常不关心。首结点第一个有效数据结点。尾结点最后一个有效数据结点其指针域为NULL。空链表只有头结点且头结点指针域为NULL。链表的基础操作与顺序表一致创建、增、删、查、改、销毁。十二、链表代码实现详解1. 创建空链表创建链表时先创建一个头结点并且让头结点的指针域指向NULL。struct node *linklist_create(void) { // 创建一个头结点 struct node *head malloc(sizeof(struct node)); // 头结点数据域不关心 head-next NULL; return head; }2. 头插法头插法指的是每次新结点都插入到头结点的后面。插入后新结点成为新的首结点。void linklist_insert_head(node_t *phead, data_t data) { // 1. 创建新结点 node_t *pNew malloc(sizeof(node_t)); // 2. 把 data 数据放到新结点数据域中 pNew-data data; // 3. 连接结点 pNew-next phead-next; phead-next pNew; }3. 判断链表是否为空int is_empty(node_t *phead) { return phead-next NULL; }4. 遍历打印链表void linklist_print(node_t *phead) { // 1. 有效性验证可能传入 NULL if (phead NULL) return; // 2. 空链表提示 if (is_empty(phead)) { printf(链表为空\n); return; } node_t *p phead-next; while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); }5. 尾插法尾插法指的是每次新结点都插入到尾结点的后面。需要先找到当前尾结点再将新结点连接上去。void linklist_insert_tail(node_t *phead, data_t data) { // 1. 创建新结点 node_t *pNew malloc(sizeof(node_t)); // 2. 把 data 数据放到新结点数据域中 pNew-data data; pNew-next NULL; // 3. 找到尾结点 node_t *p phead; while (p-next ! NULL) { p p-next; } p-next pNew; }6. 查找结点查找操作用于按关键字定位结点如果找到就返回该结点地址否则返回NULL。node_t *linklist_find_key(node_t *phead, data_t key) { if (phead NULL) return NULL; node_t *p phead-next; while (p ! NULL) { // 假设按数据域查找实际可以按学号等关键字比较 if (p-data key) return p; p p-next; } return NULL; }7. 修改结点修改操作通常是先查找目标结点再更新其数据域。int linklist_update(node_t *phead, data_t old_data, data_t new_data) { node_t *p linklist_find_key(phead, old_data); if (p NULL) return -1; // 未找到目标结点 p-data new_data; return 0; // 修改成功 }8. 删除结点删除操作既可以从链表两端删除也可以按关键字删除指定结点。8.1 头删头删每次删除首结点也就是头结点后面的第一个有效结点。int linklist_delete_head(node_t *phead) { if (phead NULL || is_empty(phead)) return -1; node_t *p phead-next; // 待删除的首结点 phead-next p-next; // 让头结点指向下一个结点 free(p); return 0; }8.2 尾删尾删每次删除尾结点。需要先找到倒数第二个结点再释放最后一个结点。int linklist_delete_tail(node_t *phead) { if (phead NULL || is_empty(phead)) return -1; node_t *p phead; while (p-next-next ! NULL) { p p-next; } free(p-next); p-next NULL; return 0; }8.3 按关键字删除指定结点int linklist_delete_key(node_t *phead, data_t key) { if (phead NULL || is_empty(phead)) return -1; node_t *p phead; while (p-next ! NULL) { if (p-next-data key) { node_t *tmp p-next; p-next tmp-next; free(tmp); return 0; } p p-next; } return -1; // 未找到目标结点 }9. 销毁链表链表使用完毕后需要逐个释放结点避免造成内存泄漏。void linklist_destroy(node_t *phead) { if (phead NULL) return; node_t *p phead; node_t *tmp NULL; while (p ! NULL) { tmp p; p p-next; free(tmp); } }10. 实践用链表实现学生管理系统基于上面掌握的链表操作可以扩展出一个简单的学生管理系统核心功能包括录入学生信息向链表尾部插入学生结点。打印学生信息遍历链表并输出。新增学生信息在头部或尾部插入新结点。删除学生信息按学号等关键字查找并删除。统计学生人数遍历链表并计数。实际项目中可以把data_t定义为包含学号、姓名、成绩的结构体typedef struct { int sno; // 学号 char name[20]; // 姓名 float score; // 成绩 } data_t; typedef struct node { data_t data; struct node *next; } node_t;此时比较和打印操作需要根据结构体字段调整。例如按p-data.sno比较学号按p-data.name打印姓名。掌握了链表的基本操作框架后只要替换数据域类型和对应比较逻辑就能快速扩展出学生管理系统、图书管理系统等应用。