数据结构：线性表走起！

小Bob 小Bob Bob来啦

2020年09月21日 22:10 __ _ _ _ _

文章配图

点击上方「蓝字」关注”程序员Bob”

每天与你不见不散！

文章配图

每日一句，送给最珍贵的你：

我爱，那个和你在一起的自己。

上次对于算法有了一定的了解，这次我们继续学习数据结构，走起！

文章配图

可能大家对于线性表不是太了解（对于刚入门数据结构的来说），那么你们在学习C语言时一定接触过 单链表
，小编在前几月也写过关于几篇单链表的文章，在完整的学习数据结构后就会发现那只不过是小皮毛啦。

在数据结构中，线性表一直是公认最简单的一种结构，比如我们在学校经常遇到的 排队问题
，通常都是按照不同要求来进行排列，这样出意外的情况便会少很多。这样排好队的组织方式，就是我们今天要说的线性表。

一线性表的定义

线性表，从名字上就可以听出来该结构像一条直线且表现出表一样的某种特征，实际上就如把所有单元用一条直线串联起来一样。

线性表：零个或多个数据元素的有限序列。

To：
小编其实并不是特别喜欢定义啥的，毕竟定义它就好像让它失去了活性一样，知识虽然是死的，但它被我们所学习后就不应该再是死的，我们要在生活中常常用到它，而不是用定义牢牢铐住它。

当然这里还是得给大家简单介绍一下定义的内容，首先线性表是一个序列，且是有限的，那就说明它的第一个元素无前驱元素，最后一个元素无后继元素。在计算机中所处理的对象其实都是有限的，并不存在无限的数列，那种无限的数列只存在于数学的概念中。

当然还有一种特殊情况便是当我们的表无一个元素时，我们便称此表为空表。

当此表为非空表时，即此表中每一个数据元素都会有一个确定的位置，通常我们用 a i
表示一个数据元素，比如a1便是第一个数据元素，切记这里和数组下标是不一样的哦！！！

不知大家是否还记得数据结构前面所说过的数据项，平时大家遇到的都是较为简单的线性表，有些复杂的可能就会在一个数据元素中包含若干个数据项啦。

二线性表的抽象数据类型

To： 说到抽象，那可是也苦了小编，想要学好计算机，抽象能力是必不可少的，以至于当小编在看 《深入理解计算机系统》
时，很多关于CPU和计算机内部的一些知识只能靠自己去抽象理解啦，所以大家平时还是得注意培养自己的抽象能力。

在编写程序时大家还是得先自己建立一个线性表，而且在以后工作后我们还得考虑线性表的长期使用，这时我们就得考虑和安排如何 创建和初始化一个线性表。

对此，线性表的抽象数据数据类型定义如下：

ADT 线性表（List）

Data

若线性表的数据对象为{a1,a2…an}，那么每个元素的类型均为Data Type。且数据元素之间的关系是一对一的关系。

Operation

** ** ** InitList(*L)： ** 初始化操作，建立一个空的线性表L。

ListEmpty(L)： 若线性表为空，返回true，否则返回false。

** ** ** ClearList(*L)： ** 将线性表L清空。

** ** ** GetElem(L,i,*e)： ** 将线性表L中的第i个位置元素返回给e。

** ** LocateElem(L,e)： 将线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功；否则。返回0表示失败。

** ** ** ListInsert(*L,i,e)： ** 将线性表L中的第i个位置插入新元素e。

** ** ** ListDelete(*L,i,e)： ** 删除线性表L中第i个位置元素，并用e返回其值。

** ** ListLength(L)： 返回线性表L中的元素个数。

endADT

上述给出的基本操作也是最基本的，对于一些复杂的操作，很多也是一些基本的组合来实现。

比如下面的我们要实现数据元素的插入操作：

//将所有的在线性表Lb中但不在La中的数据元素插入到La中void unionL(List *La,List Lb){int La_len,Lb_len,i;ElemType e;La_len=ListLength(*La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){    GetElem(Lb,i,&e);    if(!LocateElem(*La,e))    ListInsert(La,++La_len,e);    }}

上述程序只是函数的一部分，在上述函数部分中，我们用到了线性表的基本操作：ListLength,GetElem,LocateElem,ListInsert等，可见很多
复杂的操作也只是一些基本操作组合起来的。

未完待续…

文章配图