数据结构

1.1 数据结构

是描述和量化客观事物和信息等的符号，在计算机领域是指所有能输入计算机并能被计算机系统和程序识别、存储、加工和处理的符号的总称。

数据

是数据的基本单位，在计算机程序中通常把数据元素作为一个整体来存储和处理。数据元素可以只是单个的数据项，也可以由多个数据项复合组成。

数据元素

是数据不可分割的最小单位。

数据项

是数据的一个子集，是性质相同的数据的集合。

数据对象（data object）

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据元素间的关系称为结构

数据结构（data structure）

集合：结构中的数据除了“同属于一个集合”的关系外，不存在其他关系。

线性结构：结构中的数据元素的位置之间存在一对一的关系

树形结构：结构中的元素之间存在一对多的关系。

图状结构：结构中的数据元素存在多对多的关系。图状结构又称网状结构。

数据的逻辑结构是指数据元素间的逻辑关系，也就是数据元素间抽象关系的描述。它与数据在计算机的存储器中存储的方式无关，独立于计算机存在。根据数据间的不同特性，通常有四类基本结构。

.数据的逻辑结

是指数据的逻辑结构在计算机中的表示。它包含两方面的含义。其一是如何在计算机中存储数据元素。其二是如何体现数据元素之间的逻辑关系。即数据的存储结构包括数据元素的表示和关系的表示。数据的存储结构可分为顺序存储、链式存储、索引存储和散列存储结构

数据的存储结构

是对数据施加的操作

.数据的运算

1.2 数据结构的基本术语和概念

算法语言、算法、数据结构和程序设计技术。

程序设计的要素

在合法输入下，一个算法必须在执行有穷步之后结束，而其中每一个步骤都能在有限时间内完成。

1.有穷性

算法中每一个步骤、每一条指令都有确切的含义，对符合算法要求的任何输入数据都能正确执行。而对于相同的输入只能得出相同的输出。

2.确定性

算法中描述的操作都可以通过已经实现的基本操作执行有限次来实现。

3.可行性

算法要有处理的对象，也就是数据。根据需要某些数据可以在执行时输入，并通过变量接受它们。有些数据可能已被嵌入算法中，或通过赋值方法使变量获得数据。

4.算法有零个或多个输入

输出是一组与输入量有着某种特定关系的量，是算法执行后的结果。

5.算法有一个或多个输出

解决特定问题的方法。

算法

一般情况下，算法基本操作重复执行的次数是问题规模n的某个函数f(n)。而算法的时间复杂度简单说来是指算法中某种基本操作执行次数的数量级。通常用T(n)=O(f(n))表示，其中O表示f(n)的数量级。例1.1 用C语言求两个n阶矩阵的乘积的算法for(i=1;i<=n;i++)  for(j=1;j<=n;j++)  {     c[i][j]=0;    for(k=1;k<=n;k++)     c[i][j]= c[i][j]+a[i][k]*b[k][j];  }上述算法问题的规模为n，基本操作乘法的执行次数f(n)≈n*n*n，所以T(n)=O(n3)。

算法的时间复杂度是评估算法的重要标准之一，它能较好地体现算法本身的时间效率，而与具体实现算法的计算机软件、硬件无关。

时间复杂度

类似于算法的时间复杂度，空间复杂度作为算法所需存储空间的量度，记作S(n)= O(f(n))其中n为问题的规模，算法所需存储空间是问题规模n的函数f(n)。空间复杂度对于“算法设计与分析”的研究也是必要的，但它的重要性远不如时间复杂度，本课程不做重点讨论。但程序设计人员在设计算法时始终要有“时、空”这一概念，要尽量避免存储空间的浪费。

空间复杂度

1.3 算法和算法分析

一、绪论

线性表（linear_list）是属于同一个数据对象的数据元素的有限序列。线性表中数据元素的个数称为线性表的长度，长度为0的线性表称为空表。

1.线性表的定义

若将线性表记为（a1， a2，…ai-1，ai，…an），其中（i=1，2，3，…，n）是属于某个数据对象的元素，由线性表的定义，若线性表至少包含2个元素，则线性表中的数据元素之间存在以下关系：1．表中存在称作“第一个”的元素，例如上表中的a1，存在称作“最后一个”的数据元素，例如上表中的an。2．表中第一个元素a1前面没有元素和它相邻，称它没有直接前驱，它后面有且只有一个元素a2与它相邻，称它有且只有一个直接后继。而表中“最后一个”元素an有且只有一个直接前驱an-1，没有直接后继。3．除“第一个”元素和“最后一个”元素外，其他每个元素均有且只有一个直接前驱和一个直接后继。

线性表的逻辑结构是指线性表中数据元素之间的逻辑（抽象）关系

2.线性表的逻辑结构

1．存取。存取表中第i个数据元素ai(1≤i≤n)。

2．插入。在表中第i个数据元素前插入一个新的数据元素，也就是使新插入的数据元素成为新表中的第i个数据元素(1≤i≤n+1)。

3．删除。删除表中第i个元素(1≤i≤n)。

4．查找。在线性表中查找满足某种条件的数据元素。

5．求表长。求线性表中的元素个数。

对线性表的其他操作还有将两个线性表按照某种要求合并；在可能的条件下将表中数据元素按一定规则排序等。

3.线性表的基本操作

2.1 线性表的定义和逻辑结构

顺序表：线性表的顺序存储是指用一组地址连续的存储单元依次存放线性表的数据元素，这种存储形式的线性表称为顺序表。在顺序表中用内存中地址的线性关系表示线性表中数据元素之间的关系。

顺序表的特点：逻辑结构中相邻的结点在存储结构中也相邻，可以随机访问。

1. 顺序存储结构的概念

在程序设计语言中，一维数组在内存中占用的存储空间就是一组连续的存储区域，因此可以利用一维数组来存储线性表，其存储结构与线性表的逻辑结构完全一致。

数组是计算机内存中一组类型相同、连续存储的变量，每一个变量称为数组元素，按地址由小到大的顺序每个数组元素都有一个确定的下标。C语言中，在说明数组的同时就为数组开辟了相应的存储空间。

2. 利用数组存储处理线性表

指针：任意一个内存变量，都有唯一确定的地址，称这个地址为该变量的指针，它是一个常量。

指针变量：是一种特殊的变量，它和普通变量一样占用一定的内存空间，与普通变量的不同之处在于，指针变量中存放的不是普通数据，而是另外一个变量的地址（指针）。

3. 利用指针处理线性表

指针变量在说明时要指明它的数据类型，其类型就是它将要指向的变量的类型。就C语言而言，只要把数组的首地址赋给具有相同数据类型的指针变量，就可以利用该指针访问到数组中任意一个数组元素，因而也就可以利用指针处理线性表。由于数组名是地址常量，不能对它进行赋值，而指针变量可以进行一系列运算并能被赋值，另外利用指针变量结合C语言的相关函数可以动态分配存储空间，所以，采用指针处理线性表比数组更方便、更灵活。

2.2线性表的顺序存储结构 

算法要点：从an开始逐次将an，an-1，…ai向后平移一个存储位置，然后将x存入到a[i]中。

1.顺序表的插入操作

2.顺序表的删除操作

在顺序存储结构的线性表中插入或删除一个数据元素，平均需要移动表中一半元素，因而上述两个算法的时间复杂度为O(n)，当n很大时，顺序存储结构下的线性表的插入、删除操作效率是很低的。

线性表长度为n，问题规划n，基本操作为“移动”对于插入操作（共有n+1种情况）插入位置 移动次数i=n+10i=1 n其他情况n-i+1等概率平均移动次数=n/2，时间复杂度为O(n)

3.插入、删除操作的时间复杂度分析

2.3 顺序表的操作

链表：用链式存储结构存储的线性表

（1）用一组任意的存储单元来存储线性表的数据元素，不要求逻辑上相邻的两个数据元素物理上也相邻，这组存储单元可以是连续的，也可以是不连续的。

（2）线性表中任意一个数据元素以结点的形式进行存储。结点包括两部分信息，其一为数据域，存储数据元素。其二为指针域，用以存储相邻结点的存储地址。指针域可以只有一个，用它来存储的直接后继结点的存储地址。也可以有两个，其中一个指针域存放的直接后继的存储地址，另一个指针域存放的直接前驱的存储地址。

n个结点链接成一个链表，即为线性表的链式存储结构。采用链式存储结构的线性表称为链表（Linked List）。

（3）指针域中存储的信息称作指针或链。

（4）链表是通过“链”建立起数据元素之间的逻辑关系，因此插入、删除操作不需要移动数据元素，不能随机存取。

链表的特点

2.4 线性表的链式存储结构

由单向链表的结构可知，只要已知头指针，就可以由前到后逐次访问到链表中任意一个结点。具体做法是由头指针出发，可以访问到第一个结点，由第一个结点的指针域可以访问到第二个结点，…，一般地，由第i个结点的指针域可以访问到第i+1个结点

与线性表（a1，a2，…，an）相应的单向链表由n个结点链接而成。每个数据元素对应链表中一个结点，数据元素ai相应的结点在单向链表中称为结点ai。结点ai中的数据域存储数据元素ai，指针域用于存放ai的直接后继元素ai+1相应结点的存储地址。链表中第一个结点的存储位置称为头指针，程序中通常用一个指针变量存储头指针。本章命名该指针变量为head。最后一个数据元素an没有直接后继，所以链表中最后一个结点的指针域存放的是空指针（NULL）

1.单向链表的表示

在C语言中，可以用“结构变量”存储结点的信息，用“结构指针变量”存储头指针

2.单向链表的存储结构

在某些情况下，为了操作方便，在线性链表的第一个结点前增加一个附加结点，称它为头结点。头结点的数据域可以不存储任何信息，或者只是存储一些非线性表的数据元素的附加信息。而头结点指针域用以存储第一个结点的指针（地址）

3.静态法建立链表

算法要点：程序中有3个结构指针变量，其中指针变量head存放头结点的地址，指针变量p用以在动态开辟新结点的存储单元时，存放新的结点的地址，我们称它为“生成指针”。指针q始终指向当前链表的尾结点。当p所指向的新结点被链入表尾后，由q来替代p指向表尾结点，目的是可以通过q访问尾结点，我们称它为“接应指针”。具体步骤为：用p开辟新结点，并由p指向新结点，把p链入表尾，用q指向尾结点，由p继续生成新结点。

（1）尾插法

用p开辟新结点，利用指针q把p所指向的新结点插入当前链表的头结点之后，作为第一个结点，再由p继续生成新结点。（使用指针变量q是为了与后面的插入算法一致，而就本例可以不设q，而利用head就可以完成q的功能）

（2）头插法

建立单向链表的算法是一个动态过程，即从“空表”开始，依次生成各元素的结点，并逐次插入到链表中。根据插入位置的不同，建立链表的方法可以分为尾插法和头插法。尾插法是逐次生成的新结点总是作为当前链表的尾结点插入，头插法是逐次生成的新结点总是作为当前链表的第一个结点插入，算法2-3、算法2-4分别是用尾插法和头插法建立单向链表的算法。

4.动态法建立链表

5.单向链表的插入操作

2.5 单向链表的存储结构和操作

线性表

数据结构