目录
第1章软件技术概论
1.1软件的定义及分类
1.2软件技术及其发展
1.3章节内容及学习方法
第2章C语言回顾
2.1运行环境
2.2数组与结构
2.2.1数组
2.2.2结构
2.3指针
2.3.1指针的定义及运算
2.3.2数组指针和指针数组
2.3.3结构体指针
2.3.4函数指针与指针函数
2.4递归
2.4.1递归的定义
2.4.2应用递归的问题类型
2.4.3递归与回溯
2.4.4递归与非递归程序的转换
第3章数据结构
3.1数据的逻辑结构与存储结构
3.1.1基本概念
3.1.2数据的逻辑结构
3.1.3数据的存储结构
3.2线性表
3.2.1线性表的顺序存储和操作
3.2.2线性表的链式存储和操作
3.2.3小结
3.2.4栈
3.2.5队列
3.2.6栈和队列的应用
3.3树
3.3.1常用术语
3.3.2二叉树
3.3.3森林、树与二叉树的转换
3.3.4树的应用举例
3.4图
3.4.1常用术语
3.4.2图的存储结构
3.4.3图的应用举例
第4章遍历、查找和排序
4.1算法
4.1.1算法的定义及描述
4.1.2算法设计的要求
4.1.3算法的效率度量
4.2遍历
4.2.1二叉树的遍历
4.2.2图的遍历
4.3查找
4.3.1查找的基本概念
4.3.2顺序查找
4.3.3二分查找
4.3.4分块查找
4.3.5哈希查找
4.4排序
4.4.1排序的基本概念
4.4.2插入排序
4.4.3交换排序
4.4.4选择排序
4.4.5归并排序
4.4.6多关键字排序
4.4.7小结
第5章操作系统
5.1操作系统简介
5.1.1操作系统的功能
5.1.2操作系统的发展历史
5.1.3操作系统的分类
5.2操作系统与计算机硬件
5.2.1处理器
5.2.2内存
5.2.3磁盘
5.2.4I/O设备
5.2.5总线
5.2.6计算机的启动过程
5.3操作系统的相关概念
5.3.1进程
5.3.2地址空间
5.3.3文件
5.3.4输入输出
5.3.5Shell
5.4系统调用
5.5小结
第6章数据库系统
6.1数据库系统概述
6.1.1数据、数据模型与数据库
6.1.2数据库系统
6.2关系数据库
6.2.1关系概念模型
6.2.2关系结构模型
6.3结构化查询语言――SQL
6.3.1SQL概述
6.3.2数据定义
6.3.3数据操纵
6.3.4数据控制
6.4数据库应用系统开发
6.4.1数据库应用系统的结构
6.4.2数据库产品的选择
6.4.3数据库访问标准
第7章计算机网络
7.1计算机网络和因特网
7.1.1计算机网络的定义
7.1.2计算机网络的发展历史
7.1.3因特网的组成
7.1.4计算机网络的性能
7.1.5计算机网络的体系结构
7.2应用层
7.2.1域名系统
7.2.2Web和HTTP
7.2.3文件传输协议
7.2.4因特网中的电子邮件标准
7.3传输层
7.3.1传输层协议概述
7.3.2Internet传输协议UDP
7.3.3Internet传输协议TCP
7.3.4TCP拥塞和流量控制
7.4网络层
7.4.1网络层提供的服务
7.4.2网络协议
7.4.3IPv6
7.4.4因特网的路由选择协议
7.4.5虚拟专用网络
7.5数据链路层
7.5.1数据链路层的基本结构
7.5.2数据链路和帧
7.5.3数据链路控制协议
7.5.4高速以太网
7.6无线网络和移动网络
7.6.1无线传输
7.6.2通信卫星
7.6.3无线局域网
7.6.4移动网络
第8章软件工程
8.1软件工程概述
8.1.1软件危机
8.1.2软件工程的思想
8.2软件的生命周期
8.2.1问题定义及可行性分析
8.2.2需求分析
8.2.3概要设计
8.2.4详细设计
8.2.5编码
8.2.6软件测试
8.2.7软件维护
8.3软件开发方法
8.3.1常用的软件开发方法
8.3.2软件开发方法的选择及评价
8.4计算机辅助软件工程
8.4.1CASE工具的功能
8.4.2常用CASE开发工具
8.4.3CASE工具的使用策略
第9章网络新技术
9.1大数据
9.1.1大数据概述
9.1.2大数据的关键技术
9.1.3大数据的典型应用
9.2云计算
9.2.1云计算概述
9.2.2云计算的关键技术
9.2.3云计算的服务模型和部署模式
9.2.4云计算的典型应用
9.3物联网
9.3.1物联网概述
9.3.2物联网的关键技术
9.3.3物联网的典型应用
9.3.4互联网、物联网、大数据、云计算的关系
参考文献
摘要
第3章
CHAPTER 3
数 据 结 构
数据结构是研究非数值计算程序设计中计算机的操作对象以及它们之间关系和运算的科学。数据结构与数学、计算机硬件和计算机软件等有着密切的关系，数据结构与算法密不可分，是操作系统、编译原理、数据库、情报检索、人工智能等学科的重要基础。
3.1数据的逻辑结构与存储结构
3.1.1基本概念
数据是信息的载体，是描述客观事物的数、字符以及所有能被输入到计算机中并被计算机程序识别和处理的符号的集合，包括数值性数据和非数值性数据。
1. 数据元素、数据项和数据对象
数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可以由若干个数据项组成。数据项是在数据处理时不能再分割的最小单位。数据对象是性质相同的数据元素的集合。数据对象亦称数据元素类。数据元素是数据对象的一个实例。
例如，学生张强的学籍信息集合是数据元素，学生学籍信息表中的每一项，如学号、姓名、性别等各自为一个数据项。特征相同且具有共同数据项的众多学生数据可形成一个学生数据对象student。例如：
student = { 张强，李兵，…… }
任何问题中，数据元素之间都不是孤立的，它们之间存在着某种关系，数据元素之间的关系称为结构。
2. 数据结构
数据结构是互相之间存在关系的数据元素的集合。数据结构将数据按某种逻辑关系组织起来，按一定的存储表示方式把它们存储在计算机存储器中，并在这些数据上定义一个运算的集合。数据结构与数据类型和数据对象不同，它不仅要描述数据类型的数据对象，还要描述数据对象各元素之间的相互关系。
数据结构通常包括逻辑结构和存储结构。逻辑结构用于描述数据之间的逻辑关系，存储结构描述数据如何在计算机内存储。
通常，用计算机解决一个具体问题时，可分为以下步骤。
(1) 从具体问题抽象出一个适当的数学模型。
(2) 设计一个解此数学模型的算法。
(3) 编出程序，进行测试、调试直至得到最终解答。
寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。数值问题可以用诸如方程等描述。而非数值计算问题的数学模型则是用诸如表、树和图之类的数据结构描述。
3. 数据操作
数据操作亦称为数据运算。数据运算是数据结构的一个重要方面，对任何一种数据结构的研究都离不开对该结构上的数据运算及其实现算法的研究。最常用的数据操作有5种： 插入、删除、修改、查找、排序。例如针对线性表常见的基本操作如下。
(1) 线性表初始化。构造一个空的线性表。
(2) 求线性表的长度。返回线性表中所含元素的个数。
(3) 取表元。返回线性表L中的第i个元素的值或地址。
(4) 按值查找。在线性表L中查找值为x的数据元素，其结果返回在L中首次出现的值为x的元素的地址； 若未找到，返回一个特殊值表示查找失败。
(5) 插入操作。在线性表L的第i个位置插入一个值为x的新元素。
(6) 删除操作。删除线性表L中序号为i的数据元素。
基本运算并不是它的全部运算。数据结构的操作定义在逻辑结构层次上，而操作的具体实现建立在存储结构基础上。每个操作的算法只有在存储结构确立之后才能实现。
图3？1描述了数据结构的3个研究内容。
数据结构
逻辑结构线性结构线性表
线
队
非线性结构树
图
存储结构顺序存储
链式存储
数据运算： 检索、排序、插入、删除、修改等
图3？1数据结构的研究内容
3.1.2数据的逻辑结构
数据的逻辑结构反映数据之间的逻辑关系，是对数据之间关系的描述，可以用一个二元组来表示： S=(D，R)。其中D是有限个数据元素构成的集合，R是有限个结点间关系的集合。数据的逻辑结构主要有线性表、树、图等形式。数据的逻辑结构和物理结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。
1. 线性表
线性表是最常用、最简单的一种数据结构，其基本特点是线性表中的数据元素是有序且有限的。线性表中数据元素用结点描述，结点之间是一对一的关系。在线性表里有且仅有一个开始结点和一个终端结点，并且所有结点最多只有一个前驱和一个后继。现实中有很多一对一的线性关系，如英文字母表、一个班中的学生关系(通过学号关联)，图书馆中的书籍(通过图书号关联)。
栈与队列是两种特殊的线性结构。从结构看它们与普通线性表一样，但执行数据操作时它们受特定规则。 栈是定义在线性结构上的抽象数据类型，其操作类似线性表操作，但元素的插入、删除和访问都必须在表的一端进行，其操作如图3？2所示。为形象起见，允许操作端称为栈顶(top)，另一端为栈底(base)，栈的特性为优选后出、后进先出。编程中嵌套函数和递归函数的调用控制、括号匹配问题、运算表达式的计算等均可用栈模拟。
队列是另一种线性表，类似日常生活中排队，队列元素的插入和删除分别在表的两端进行，如图3？3所示。允许插入的一端为队尾(rear)，允许删除的一端为队头(front)。队列的特性为优选先出、后进后出，操作系统中的作业队列和打印任务队列、日常生活中各类排队业务等均可用队列模拟。
图3？2栈示意图
图3？3队列示意图
2. 树
图3？4资源管理器
树及图形结构均为非线性结构。树结构中数据元素之间是一对多的关系。在树中有且仅有一个结点没有前驱，类似于树的根，称为根结点； 其他结点有且仅有一个前驱。它的结构特点具有明显的层次关系。
日常生活及计算机中有很多数据关系是树结构，例如家谱、行政组织机构、人机对弈问题、源程序的语法结构、资源管理器等，如图3？4和图3？5所示。
图3？5对弈问题
3. 图
图结构中数据元素之间是多对多的关系，图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。图结构也称作网状结构。
互联网结构、交通网络图、教学计划编排问题等都可以用图结构描述，如图3？6和图3？7所示。
图3？6教学计划编排问题
图3？7交通网络图
3.1.3数据的存储结构
数据的逻辑结构从逻辑关系上描述数据，是独立于计算机的； 数据的存储结构是逻辑结构在计算机存储器里的实现，是依赖于计算机的。数据的存储结构主要有顺序、链式、索引、散列等4种基本存储结构，并可以根据需要组合成其他更复杂的结构。
1. 顺序存储
顺序存储结构是一种最基本的存储方法，是借助元素在存储器中的相对位置来表示数据元素间的逻辑关系。这种方法主要用于线性的数据结构，它把逻辑上相邻的结点存储在物理上相邻的存储单元里，结点之间的关系由存储单元的邻接关系来体现。在C语言中，通常借助于一维数组表示顺序存储结构。
2. 链式存储
链式结构即在每一个数据元素中增加一个存放另一个元素地址的指针，用该指针来表示数据元素之间的逻辑关系。由此得到的存储表示称为链表，链表既可以表示线性结构，也可以表示非线性结构。
链表中每一个元素称为结点。在C语言中，用结构体类型表示结点，链表由一系列结点组成，结点可以在运行时动态生成。结点所占的存储单元分为两部分： 一部分存放结点本身的信息，称为数据项； 另一部分存放结点的后继结点所对应的存储单元的地址，称为指针项。指针项可以包含一个或多个指针，以指向结点的一个或多个后继。
3. 索引存储
索引存储指除建立存储结点信息外，还建立附加的索引表来标识结点的地址。索引存储结构的优点是检索速度快，缺点是增加了附加的索引表，会占用较多的存储空间。
4. 散列存储
散列存储又称hash存储，是一种将数据元素的存储位置与关键码之间建立确定对应关系的查找技术。
若数据结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数，按这个思想建立的表为散列表。散列技术除了可以用于查找外，还可以用于存储。
同一个逻辑结构可以用不同的存储结构存储，本章主要介绍顺序存储与链式存储。具体选择哪一种需根据数据特点及实际运算的效率来确定。
3.2线性表
线性表是n(n≥0)个具有相同属性的数据元素a1，a2，…，an组成的有限序列，线性表中每一个数据元素均有一个直接前驱和一个直接后继数据元素。当n=0时称为空表，空表不含有任何元素。
3.2.1线性表的顺序存储和操作
1. 线性表的顺序存储
线性表的顺序存储是指在内存中把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里，用这种方法存储的线性表简称顺序表。顺序表中数据元素之间的逻辑关系以元素在计算机内物理位置相邻来表示。
图3？8顺序表的存储地址
由于线性表的所有数据元素属于同一数据类型，所以每个元素在存储器中占用的空间(字节数)相同。因此，要在此结构中查找某一个元素是很方便的，只要知道顺序表首地址和每个数据元素在内存所占字节的大小就可求出第i个数据元素的地址，因此顺序存储结构的线性表可以随机存取其中的任意元素。
假设线性表中有n个元素，每个元素占k个单元，第一个元素的地址loc(a1)称为基地址，第i个元素的地址loc(ai)可以通过如下公式计算： loc(ai)=loc(a1)+(i-1)×k，如图3？8所示。
顺序存储结构在C语言中用一维数组来表示，一维数组的下标等于元素在线性表中的序号减1。 typedef struct
{
ElemType *elem; //线性表占用的数组空间基地址
int length;
int listsize;
int last;
} SeqList;
2. 顺序表的操作
顺序表的操作主要包括线性表的初始化、插入及删除数据、数据的查询及求线性表的长度等。
(1) 数据表的初始化。
初始化即构造一个空的线性表，为顺序表命名及分配空间。
SeqList *init_SeqList()
{
SeqList *L;
L=(SeqList*)malloc(sizeof(SeqList));
L->last=-1;
return L;
}
(2) 插入运算。
插入运算是指在线性表的第i-1个数据元素和第i个数据元素之间插入一个新的数据元素。对于长度可变的线性表，必须按可能达到的优选长度分配空间。
已知线性表(4，9，15，28，30，30，42，51，62)，需在第4个元素之前插入一个元素“21”，则需要将第9个位置到第4个位置的元素依次后移一个位置，然后将“21”插入到第4个位置，如图3？9所示。
图3？9顺序表中插入元素
代码如下：
int Insert_SeqList(SeqList *L,int i,datatype x)
{
int j;
if(L->last==MAXSIZE-1)
{
printf("table is full!"); return(-1);
}
if(i<1||i>(L->last+2))
{
printf("place is wrong!"); return(0);
}
for(j=L->last;j>=i-1;j--)
{
L->data［j+1］=L->data［j］;
}
L->data［i-1］=x;
L->last++;
return(1); }
(3) 删除运算。
线性表的删除运算是将表的第i(1≤i≤n)个元素删除，使长度为n的线性表(e1，…，ei-1，ei，ei+1，…，en)变成长度为n-1的线性表(e1，…，ei-1，ei+1，…，en)。删除第i个元素(1≤i≤n)时需将第i+1至第n(共n-i)个元素依次向前移动一个位置。
例如，线性表(4，9，15，21，28，30，30，42，51，62)删除第5个元素，则需将第6个元素到第10个元素依次向前移动一个位置，如图3？10所示。
图3？10顺序表中删除元素
代码如下：
int Delete_SeqList(SeqList *L,int i)
{
int j;
if(i<1||i>(L->last+1))
{
printf("this element don't exist!");
return(0);
}
for(j=i;j<=L->last;j++)
{
L->data［j-1］=L->data［j］;
}
L->last--;
return(1);
}
在顺序表中插入或删除一个数据元素时，其时间主要耗费在移动数据元素上。对于插入算法而言，设pi为在第i个元素之前插入元素的概率，平均移动次数为
E=∑n+1i=1pi(n-i+1)
假设在任何位置上插入的概率相等，即pi=1/(n+1)，i=1，2，…，n+1，平均移动次数为
E=1n+1
∑n+1i=1(n-i+1)=n2
同理，设Qi为删除第i个元素的概率，并假设在任何位置上删除的概率相等，即Qi=1
，i=1，2，…，n。删除一个元素所需移动元素的平均次数为
E=1n
∑ni=1(n-1)=n-12
由此可得，在顺序表中作插入或删除运算时，平均有一半元素需要移动，时间复杂度为O(n)。(时间复杂度的概念详见4.1.3节)
(4) 顺序表的查找操作。
在线性表中查找关键字为x的元素，并返回其位置。
int Locate_list(int s［］, int n, int x)
{
int i;
for (i=1; i<=n; i++) if (s［i］==x) return(i);
return(0);
}
例3.1从一个有序顺序表中删除重复的元素并返回新的表长，要求空间复杂度为O(1)；
代码如下：
#include
typedef int ElemType;
typedef struct
{
ElemTypedata［100］;
int length;
}SeqList;
int removeSame (SeqList &B)
{
ElemTypee=B.data［0］;
int index=1;
for(int i=1;i {
if(B.data［i］!=e)
{
B.data［index++］=B.data［i］;
e=B.data［i］;
}
}
return index;
}
intmain()
{
SeqList R;
//intA［］={1,2,2,1,3,4,5,4,2,1};
int i;
int A［］={1,2,2,3,3,3,4,4,5,5};
for(i=0;i R.data［i］=A［i］;
R.length=i;
R.length=removeSame (R);
printf("删除前:＼n");
for(i=0;i printf("%2d",A［i］);
printf("＼n");
printf("删除后:＼n");
for(i=0;i printf("%2d",R.data［i］);
printf("＼n");
return 0;
}
显然，线性表的顺序存储具有如下优点。
(1) 方法简单，各种高级语言中都有数组，容易实现。 (2) 不用为表示结点间的逻辑关系而增加额外的存储开销。
(3) 具有按元素序号随机访问的特点。
但线性表的顺序存储也存在以下缺点。
(1) 数据元素优选个数需预先确定，使得高级程序设计语言编译系统需预先分配相应的存储空间，存储空间不便于扩充。
(2) 插入与删除运算的效率很低。为了保持线性表中的数据元素顺序，在插入操作和删除操作时需移动大量数据。对于插入和删除操作频繁的线性表，将导致系统的运行速度难以提高。
3.2.2线性表的链式存储和操作
1. 线性表的链式存储
线性表的链式存储结构又称为线性链表，就是用一组任意的存储单元(可以是不连续的)存储线性表的数据元素，每个存储单元称为结点。每个结点包含两部分内容： 一部分用于存放数据元素值，称为数据域； 另一部分用于存放直接前驱或直接后继结点的地址(指针)，称为指针域。结点的结构示意图如图3？11所示。
图3？11结点的结构示意图
这种链表的每个结点只有一个指针域，故这种链表又称为单链表。由于单链表中每个结点的存储地址是存放在其前趋结点的指针域中，而第一个结点无前趋，因而应设一个头指针H指向第一个结点。同时，由于表中最后一个结点没有直接后继，则指定线性表中最后一个结点的指针域为“空”(null)。用线性链表表示线性表时，数据元素之间的逻辑关系是由结点中的指针指示的，这样对于整个链表的存取必须从头指针开始。图3？12描述了带头结点的单链表。
图3？12带头结点的空单链表和单链表
线性链表的有关术语如下。
(1) 头指针。用于存放线性链表中第一个结点的存储地址。
(2) 空指针。不指向任何结点。
(3) 带头结点的线性链表。在第一个结点前面增加一个附加结点的线性链表，称为带头结点的线性链表。
(4) 单链表。只有一个指针域的线性链表。
C语言中用带指针的结构体类型来描述结点，代码如下：
typedef struct node
{datatype data;
struct node *next;
}LNode,*LinkList;
其中：
LNode: 结构类型名;
data: 用于存放元素的数据信息;
next: 用于存放元素直接后继结点的地址;
该类型结构变量用于表示线性链表中的一个结点。
LNode *p; /* p为指向结点(结构)的指针变量* / LinkList p; /* 同LNode *p;*/
2. 单链表的操作
为了运算方便起见，一般用带头结点的单链表存储线性表。
(1) 单链表的创建。
动态创建单链表有头插、尾插两种方法。头插法是从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。即每次插入的结点都作为链表的第一个结点。尾插法是将新结点插入到当前链表的表尾，使其成为当前链表的尾结点。头插法建立链表算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。
例如，创建函数create_LinkList()，实现头插法创建单链表，链表的头结点head作为返回值。代码如下：
LNode *create_LinkList(void)
{
int data ;
LNode *head, *p;
head= (LNode *) malloc( sizeof(LNode));
head->next=NULL; //创建链表的表头结点head
while (1)
{
scanf("%d", &data) ;
p= (LNode *)malloc(sizeof(LNode));
p？>data=data; //数据域赋值
p？>next=head？>next ; head？>next=p ;
//新创建的结点总是作为第一个结点
}
return(head);
}
创建函数create_LinkList1()，实现尾插法创建单链表函数，链表的头结点head作为返回值。代码如下：
LNode *create_LinkList1(void)
{
int data ;
LNode *head, *p, *q;
head=p=(LNode *)malloc(sizeof(LNode));
p->next=NULL; //创建单链表的表头结点head
while (1)
{
scanf("%d",& data);
q= (LNode *)malloc(sizeof(LNode));
q？>data=data; //数据域赋值
q？>next=p？>next; p？>next=q; p=q ; //新创建的结点总是作为最后一个结点 }
return(head);
}
无论是哪种插入方法，如果要插入建立的单链表的结点是n个，算法的时间复杂度均为O(n)。
(2) 单链表的插入运算。
链表中插入元素只需修改插入元素及其前趋元素的指针即可，操作步骤如图3？13所示。
图3？13线性链表插入元素
创建函数Inset()，实现在第i个结点前插入数据值为x的结点的函数。代码如下：
int Insert (NODE *head， int i， int x)
{
NODE *p， *q;
int j;
if (i<=0) return(0);
p=head;
j=1;
while ((j<=i-1)&&(p!=NULL)) {p=p->link; j++;}
if (p==NULL) return(0);
q=(NODE *)malloc(sizeof(NODE));
q->data=x; q->link=p->link; p->link=q;
return(1);
}
(3) 单链表的删除运算。
链表中删除操作只需修改被删除元素前趋元素指针即可，操作步骤如图3？14所示。
图3？14线性链表删除元素
创建函数Delete()，实现删除指定位置(第i个)元素。代码如下：
int Delete (NODE *head， int i)
{
NODE *p，*q;
int j;
if (i==0) {
p=head; head=head->link;
free(p);
return(1);
}
j=1;p=head;
while ((jlink!=NULL)) p=p->link;
if (p->link==NULL) return (0);
q=p->link; p->link=q->link;
free(q);
return(1);
}
(4) 线性链表的查找运算。
创建函数Locate_LinkList()，实现链表中按元素值查找。代码如下：
Lnode *Locate_LinkList(LinkList L,datatype x)
{
LNode *p=L->next;
while(p!=NULL&&p->data!=x) p=p->next;
return p;
}
3. 循环链表的操作
循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。从循环链表的任意一个结点出发都可以找到链表中的其他结点，使得表处理更加方便灵活。循环链表和单链表的差别仅在于链表中最后一个结点的指针域不为NULL，而是指向头一个结点，成为一个由链指针链接的环，也就是算法中的循环条件不是p或p->next是否为空，而是它们是否等于头指针。循环链表示意图如图3？15所示。
图3？15循环链表示意图
循环链表的操作与单链表相似。
4. 双向链表的操作
若结点中有两个指针域，一个指向直接后继，另一个指向直接前趋，这样的链表称为双向链表，如图3？16所示。双向链表可以克服单链表的单向性缺陷。
图3？16双向链表示意图
双向链表存储结构如下：
struct Double_node
{
int data;
struct Double_node *llink, *rlink;
};
typedef struct Double_node NODE;
对指向双向链表任一结点的指针d，具有关系： d->rlink->llink=d->llink->rlink=d，即当前结点后继的前趋是自身，当前结点前趋的后继也是自身。与单链表的插入和删除操作不同的是，在双向链表中插入和删除必须同时修改两个方向上的指针域的指向。
(1) 双向链表的插入操作。
在数据值为y的结点后，插入数据值为x的结点，如图3？17所示。
图3？17双向链表插入结点示意图
创建函数Insert2()，实现双向链表插入结点操作。代码如下：
int Insert2(NODE *head，int x，int y)
{
NODE *p， *q;
q=head->rlink;
while (q!=head && q->data!=y) q=q->rlink;
if (q==head) return(0);
p=(NODE *)malloc(sizeof(NODE)); p->data=x; p->llink=q; p->rlink=q->rlink;
(q->rlink)->llink=p;
q->rlink=p;
return(1)
}
(2) 双向链表的删除操作。
在双向链表中删除数据值为x的结点，如图3？18所示。
图3？18双向链表删除结点
创建函数Delete2()，实现双向链表删除结点操作。代码如下：
int Delete2 (NODE *head，int x)
{
NODE *q;
q=head->rlink;
while(q!=head && q->data!=x) q=q->rlink;
if(q==head) return(0);
(q->llink)->rlink=q->rlink;
(q->rlink)->llink=q->llink;
free(q);
return(1);
}
3.2.3小结
链表的优缺点恰好与顺序表相反。在实际应用中选取何种存储结构，通常从以下几个方面考虑。
1. 基于空间的考虑
顺序表的存储空间是静态分配的，在程序执行前必须明确规定它的存储规模。若线性表长度n变化较大，则存储规模很难预先正确估计。估计太大将造成空间浪费，估计太小又将使空间溢出机会增多。链表不用事先估计存储规模，是动态分配，只要内存空间尚有空闲，就不会产生溢出，所以当对线性表的长度或存储规模难以估计时，不宜采用顺序存储结构而宜采用动态链表作为存储结构。但链表的存储密度较低，存储密度是指一个结点中数据元素所占的存储单元和整个结点所占的存储单元之比。显然链式存储结构的存储密度是小于1的，顺序表的存储密度等于1。
2. 基于时间的考虑
线性表如果主要做查找，则时间性能为O(1)； 而在链表中按序号访问的时间性能为O(n)。所以，如果经常做的运算是按序号访问数据元素，显然顺序表优于链表。
顺序表中做插入、删除操作时，要平均移动表中一半的元素； 尤其是当每个结点的信息量较大时，移动结点的时间开销就相当可观，不容忽视。在链表中的任何位置上进行插入和删除，都只需要修改指针。对于频繁进行插入和删除的线性表，宜采用链表做存储结构。若表的插入和删除主要发生在表的首尾两端，则宜采用尾指针表示的单循环链表。 3. 基于环境的考虑
顺序表容易实现，任何高级语言中都有数组类型； 链表的操作是基于指针的，其使用受语言环境的。
总之，两种存储结构各有特点，选择哪种结构根据实际使用的主要因素决定。通常较稳定的线性表选择顺序存储结构； 而插/删频繁的动态性较强的线性表宜选择链式存储结构。
3.2.4栈
1. 栈的定义
栈是限定仅在表尾进行插入或删除操作的线性表。表尾称为栈顶，表头称为栈底，不含元素的空表称为空栈。栈按照优选后出的原则存储数据，优选入的数据被压入栈底，最后进入的数据在栈顶，需要读数据的时候从栈顶开始弹出数据，即最后一个数据被第一个读出来。栈的进出操作如图3？19所示。
图3？19进出栈操作
栈的插入和删除操作分别称为进栈和出栈。进栈是将一个数据元素存放在栈顶，出栈是将栈顶元素取出。栈按存储方式可分为两种： 顺序栈和链栈。
例3.2假设有3个元素a，b，c，入栈顺序是a，b，c，则它们的出栈顺序有几种可能？
出栈顺序共有如下几种。
(1) abc顺序进栈则出栈顺序为cba。
(2) a进栈，a出栈，然后b、c进栈，再顺序出栈，则出栈顺序为acb。
(3) a进栈，a出栈； b进栈，b出栈； c进栈，c出栈； 则出栈顺序为abc。
(4) a、b进栈，a、b出栈，然后c进栈，再出栈，则出栈顺序为bac。
(5) a、b进栈，b出栈； c进栈，然后出栈，则出栈顺序为bca。
2. 顺序栈的存储和操作
顺序栈即栈的顺序存储，是利用一组地址连续的存储单元依次存放自栈
