7- 常用的三种线性数据结构

教学内容： 第1章：C语言语法基础第2章：C程序设计基础第3章：利用数组处理同类型的批量数据第4章：利用函数实现模块化程序设计第5章：灵活使用指针第6章：结构体、共用体、枚举类型及其应用第7章：常用的三种线性数据结构第8章：利用文件进行数据管理第9章：嵌入式技术基础实践方法C语言程序设计7.1线性数据结构概述7.2线性表*7.3栈*7.4队列【学习内容】

第7章常用的三种线性数据结构【学习目标】

1.理解线性数据结构的概念和存储方法；2.理解数组处理数据的优缺点；3.掌握链表的定义及操作方法；*4.掌握栈的定义、存储方法及对应的操作方法；*5.掌握队列的定义、存储方法及对应的操作方法；*6.了解链表、栈和队列在嵌入式软件中的应用。7.1线性数据结构概述

线性数据结构：结构中的数据元素之间存在“一对一”的线性逻辑关系，即数据元素存在着依次排列的先后次序关系，且只有一个起始数据元素和一个终止数据元素。数据元素也称为节点。常用的线性数据结构：线性表、栈和队列等。

线性表（LinearList）：1~100之间的自然数序列、26个字符组成的英文字母表、一个班级的学生信息表等。

栈（Stack）：盘子、作业叠放时，先放的在底部，后放的在顶部；取出时，先取顶部的，才能取下面的——后进先出（LIFO）的线性表。

队列（Queue）：排队购票时，先来先购先走，后来后购后走——先进先出（FIFO）的线性表。线性数据结构的两种存储方法：顺序存储、链式存储。

顺序存储：逻辑上相邻的数据元素对应的物理存储位置也相邻，可用数组来实现。

链式存储：逻辑上相邻的数据元素对应的物理存储位置可以不相邻，可用指针来实现。7.2.1线性表的定义

线性表是由n（n≥0）个性质相同的数据元素组成的有限序列，记作：（a1，a2，…，ai-1，ai，ai+1，…，an）。除了首元素a1外，其他每个元素都有一个直接前趋（ai直接前趋为ai-1）；除了尾元素an外，其他每个元素都有一个直接后继（ai直接后继为ai+1）。7.2线性表

采用顺序存储结构的线性表称为顺序表，常用数组实现顺序表。数组占用一片连续的存储空间。优点：可用下标随机访问任一数组元素。

（2）当待处理的数据个数不确定时，很难确定合适的数组长度。

缺点：

（1）对数组元素的插入或删除操作不方便，效率低。

链式存储的线性表——链表，可以弥补数组存在的以上缺陷。7.2.2单向链表的定义7.2线性表

一个单向链表由头指针（head）和若干个节点组成。每个节点由数据域（存放本节点的实际数据）和指针域（存放下一个节点的地址）两部分组成。

头指针用于存放第1个节点的地址，指向第1个节点，因此可通过头指针找到第1个节点，然后再通过第1个节点找到第2个节点，依次类推，直到找到最后一个节点（其指针域为空，不指向任何节点）。

若不关心每个节点的实际地址，而只注重各节点的逻辑关系，则可简化为：7.2线性表

可以设计一个结构体类型来描述单向链表节点的结构：链表主要有建立、输出、查找、插入、删除等操作。

为了便于操作，常在链表中增加一个头节点（不存放数据）。带头节点的单向链表包括1个头节点（0号节点）和3个数据节点（1～3号节点）。7.2.2单向链表的定义7.2线性表

7.2.3单向链表的基本操作1、链表的建立

建立链表：从无到有，一个一个地开辟节点和输入各节点的数据，并建立起前后相链接的关系。

“尾插法”建立单向链表的过程：

头节点的指针域始终指向第1个数据节点，新增节点链接到原链表的尾部。

插入字符c的详细过程：c

需要设定3个指针：头指针head、尾节点指针e、新增节点指针p7.2线性表

ruturn(head);7.2.3单向链表的基本操作1、链表的建立7.2线性表

建立链表后，可将链表中各节点的数据依次输出。

//函数参数：链表的头指针head7.2.3单向链表的基本操作2、链表的输出7.2线性表

在链表中，不能像数组那样直接通过序号访问到节点，而必须从链表的头节点开始，逐个节点进行搜索，直到搜索到指定序号节点为止。如果指定的节点序号非法（序号小于0或序号大于数据节点数），则查找失败，需要返回NULL。

下图所示的链表，包含1个头节点（0号节点）和4个数据节点（1号～4号节点）。7.2.3单向链表的基本操作3、链表的查找——按序号查找7.2线性表

从链表的第1个节点开始，逐个节点进行搜索，直到搜索到指定节点值为止。在搜索过程中，如果找到指定节点，则返回指定节点的地址；当扫描到最后一个节点，仍找不到指定节点值时，则返回NULL。7.2.3单向链表的基本操作3、链表的查找——按值查找7.2线性表

在第3个位置（第2个位置后）上插入给定节点值x的运算过程：按序号查找2号节点：7.