算法思想有很多，业界公认的常用算法思想有8种，分别是枚举、递推、递归、分治、贪心、试探法、动态迭代和模拟。当然8种只是一个大概的划分，是一个“仁者见仁、智者见智”的问题。

其实这些算法都是用来处理数据的，这些被处理的数据必须按照一定的规则进行组织。当这些数据之间存在一种或多种特定关系时，通常将这些关系称为结构。在C语言数据之间一般存在如下3种基本结构。

• ① 线性结构：数据元素间是一对一关系。
• ② 树形结构：数据元素间是一对多关系。
• ③ 网状结构：数据元素间是多对多关系。

今天小编将分享第一种线性结构。

线性表详解

线性表中各个数据元素之间是一对一的关系，除了第一个和最后一个数据元素外，其他数据元素都是首尾相接的。因为线性表的逻辑结构简单，便于实现和操作，所以该数据结构在实际应用中被广泛采用。在本节中，将详细讲解线性表的基本知识。

1.1.1　线性表的特性

线性表是一种最基本、最简单、最常用的数据结构。在实际应用中，线性表都是以栈、队列、字符串、数组等特殊线性表的形式来使用的。因为这些特殊线性表都具有自己的特性，所以掌握这些特殊线性表的特性，对于数据运算的可靠性和提高操作效率是至关重要的。

线性表是一个线性结构，它是一个含有n>=0个节点的有限序列。在节点中，有且仅有一个开始节点没有前驱并有一个后继节点，有且仅有一个终端节点没有后继并有一个前驱节点，其他的节点都有且仅有一个前驱和一个后继节点。通常可以把一个线性表表示成一个线性序列：k1，k2，…，kn，其中k1是开始节点，kn是终端节点。

1．线性结构的特征

在编程领域中，线性结构具有如下两个基本特征。

① 集合中必存在唯一的“第一元素”和唯一的“最后元素”。

② 除最后元素之外，均有唯一的后继；除第一元素之外，均有唯一的前驱。

由n(n>=0)个数据元素（节点）a1，a2，…，an组成的有限序列，数据元素的个数n定义为表的长度。当n=0时称为空表，通常将非空的线性表(n>0)记作：（a1，a2，…，an）。数据元素ai(1<=i<=n)没有特殊含义，不必去“剖根问底”地研究它，它只是一个抽象的符号，其具体含义在不同的情况下可以不同。

2．线性表的基本操作过程

线性表虽然只是一对一的关系，但是其操作功能非常强大，具备了很多操作技能。线性表的基本操作如下。

① 用Setnull（L）：置空表。

② 用Length（L）：求表长度和表中各元素个数。

③ Get（L，i）：获取表中第i个元素（1<=i<=n）。

④ Prior（L，i）：获取i的前趋元素。

⑤ Next（L，i）：获取i的后继元素。

⑥ Locate（L，x）：返回指定元素在表中的位置。

⑦ Insert（L，i，x）：插入新元素。

⑧ Delete（L，x）：删除已存在元素。

⑨ Empty（L）：判断表是否为空。

3．线性表的结构特点

线性表具有如下结构特点。

① 均匀性：虽然不同数据表的数据元素是各种各样的，但同一线性表的各数据元素必须有相同的类型和长度。

② 有序性：各数据元素在线性表中的位置只取决于它们的序。数据元素之前的相对位置是线性的，即存在唯一的“第一个”和“最后一个”数据元素，除了第一个和最后一个外，其他元素前面只有一个数据元素直接前趋，后面只有一个直接后继。

1.1.2　顺序表操作

在现实应用中，有两种实现线性表数据元素存储功能的方法，分别是顺序存储结构和链式存储结构。顺序表操作是最简单的操作线性表的方法，此方式的主要操作功能有以下几种。

（1）计算顺序表的长度

数组的最小索引是0，顺序表的长度就是数组中最后一个元素的索引last加1。使用C语言计算顺序表长度的算法实现如下所示。

public int GetLength() {return last+1; }

（2）清空操作

清空操作是指清除顺序表中的数据元素，最终目的是使顺序表为空，此时last等于−1。使用C语言清空顺序表的算法实现如下所示。

public void Clear() {last = -1; }

（3）判断线性表是否为空

当顺序表的last为−1时表示顺序表为空，此时会返回true，否则返回false表示不为空。使用C语言判断线性表是否为空的算法实现如下所示。

public bool IsEmpty() {if (last == -1) {return true; }else {return false; } }

（4）判断顺序表是否为满

当顺序表为满时last值等于maxsize−1，此时会返回true，如果不为满则返回false。使用C语言判断顺序表是否为满的算法实现如下所示。

public bool IsFull() {if (last == maxsize - 1) {return true; }else {return false; } }

（5）附加操作

在顺序表没有满的情况下进行附加操作，在表的末端添加一个新元素，然后使顺序表的last加1。附加操作的算法实现如下所示。

public void Append(T item) {if(IsFull()) { Console.WriteLine("List is full"); return; }data[++last] = item; }

（6）插入操作

在顺序表中插入数据的方法非常简单，只需要在顺序表的第i个位置插入一个值为item的新元素即可。插入新元素后，会使原来长度为n的表（a1，a2，…，a(i−1)，ai，a(i+1)，…，an）的长度变为（n+1），也就是变为（a1，a2，…，a(i−1)，item，ai，a(i+1)，…，an）。i的取值范围为1<=i<=n+1，当i为n+1时，表示在顺序表的末尾插入数据元素。

在顺序表插入一个新数据元素的基本步骤如下。

① 判断顺序表的状态，判断是否已满和插入的位置是否正确，当表满或插入的位置不正确时不能插入。

② 当表未满直插入的位置正确时，将an～ai依次向后移动，为新的数据元素空出位置。在算法中用循环来实现。

③ 将新的数据元素插入到空出的第i个位置上。

④ 修改last值以修改表长，使其仍指向顺序表的最后一个数据元素。

顺序表插入数据示意图如图3-1所示。

图1-1　顺序表插入数据示意图

使用C语言在顺序表中实现插入操作的算法代码如下所示。

public void Insert(T item, int i) { //判断顺序表是否已满if (IsFull()) {  Console.WriteLine("Listisfull"); return;}//判断插入的位置是否正确//i小于1表示在第1个位置之前插入//i大于last+2表示在最后一个元素后面的第2个位置插入if(i<1||i>last+2){ Console.WriteLine("Positioniserror!"); return;}//在顺序表的表尾插入数据元素if(i==last+2){ data[i-1]=item;}else//在表的其他位置插入数据元素{//元素移动for(intj=last;j>=i-1;--j){ data[j+1]=data[j];}//将新的数据元素插入到第i个位置上data[i-1]=item;}//修改表长++last;}

在上述代码中，位置变量i的初始值是1而不是0。

（7）删除操作

可以删除顺序表中的第i个数据元素，删除后使原来长度为n的表(a1，a2，…,ai−1，ai，ai−1，…，an)变为长度为（n−1）的表，即(a1，a2，…，ai-1，ai+1，…，an)。i的取值范围为1<=i<=n。当i为n时，表示删除顺序表末尾的数据元素。

在顺序表中删除一个数据元素的基本流程如下。

① 判断顺序表是否为空，判断删除的位置是否正确，当为空或删除的位置不正确时不能删除；

② 如果表为空和删除的位置正确，则将ai+1～an依次向前移动，在算法中用循环来实现移动功能；

③ 修改last值以修改表长，使它仍指向顺序表的最后一个数据元素。

图1-2展示了在一个顺序表中删除一个元素的前后变化过程。图3-2中的表原来长度是8，如果删除第5个元素E，在删除后为了满足顺序表的先后关系，必须将第6～8个元素（下标位5～7）向前移动一位。

图1-2　顺序表中删除一个元素

使用C语言在顺序表中删除数据元素的基本算法实现如下所示。

publicTDelete(inti){ T tmp = default(T); //判断表是否为空if (IsEmpty()) { Console.WriteLine("List is empty"); return tmp; } //判断删除的位置是否正确 // i小于1表示删除第1个位置之前的元素 // i大于last+1表示删除最后一个元素后面的第1个位置的元素if (i < 1 || i > last+1) { Console.WriteLine("Position is error!"); return tmp; } //删除的是最后一个元素if (i == last+1) { tmp = data[last--]; return tmp; }  else //删除的不是最后一个元素 { //元素移动 tmp = data[i-1]; for (int j = i; j <= last; ++j) { data[j] = data[j + 1]; } } //修改表长 --last;return tmp; }

（8）获取表元

通过获取表元运算可以返回顺序表中第i个数据元素的值，i的取值范围是1<=i<=last+1。因为表中数据是随机存取的，所以当i的取值正确时，获取表元运算的时间复杂度为O(1)。使用C语言实现获取表元运算的算法实现如下所示。

public T GetElem(int i) {if (IsEmpty()|| (i<1) || (i>last+1)) {Console.WriteLine("List is empty or Position is error!");return default(T); }return data[i-1]; }

（9）按值进行查找

所谓按值查找，是指在顺序表中查找满足给定值的数据元素。它就像住址的门牌号一样，这个值必须具体到XX单元XX室，否则会查找不到。按值查找就像Word中的搜索功能一样，可以在繁多的文字中找到需要查找的内容。在顺序表中找到一个值的基本流程如下所示。

① 从第一个元素起依次与给定值进行比较，如果找到，则返回在顺序表中首次出现与给定值相等的数据元素的序号，称为查找成功。

② 如果没有找到，在顺序表中没有与给定值匹配的数据元素，返回一个特殊值表示查找失败。

使用C语言实现按值查找运算的算法实现如下所示。

publicintLocate(Tvalue){//顺序表为空if(IsEmpty()){Console.WriteLine("listisEmpty");return-1;}inti=0;//循环处理顺序表for(i=0;i<=last;++i){//顺序表中存在与给定值相等的元素if(value.Equals(data[i])){ break;}}//顺序表中不存在与给定值相等的元素if(i>last){  return-1;}returni;}

END

喜欢的读者请转发到朋友圈

本文摘自《算法学习与应用从入门到精通》