1 什么是线性表
线性表的定义:由零个或多个数据元素组成的有限序列
- 首先它是一个序列,也就是说元素之间是有先来后到之分。
- 若元素存在多个,则第一个元素无前驱,而最后一个元素无后继,其他元素都有且只有一个前驱和后继。
- 线性表强调是有限的,事实上无论计算机发展到多强大,他所能处理的元素都是有限的。
线性表的形式化定义:
引申问题:
(1)请问公司的组织架构是否属于线性关系?
分析:一般公司的总经理管理几个总监,每个总监管理几个经理,每个经理都有各自的下属和员工。那这样的组织架构当然不是线性关系了,事实上后面你就会知道,这是一个树状结构。注意线性关系的条件是如果存在多个元素,则”第一个元素无前驱,而最后一个元素无后继,其他元素都有且只有一个前驱和后继。“
(2)那么班里同学之间的友谊是否属于线性关系?
当然也不是了,因为每个人都会跟许多同学建立纯纯的友谊关系。
(3)一个班级的点名册,是不是线性表?
这个当然是的。我们看下表:
学号 | 姓名 | 性别 | 职位 |
---|---|---|---|
1 | 景禹 | 男 | 班长 |
2 | 哒哒 | 女 | 副班长 |
3 | 花花 | 女 | 音乐课代表 |
4 | 素素 | 女 | 美术课代表 |
5 | 明明 | 男 | 小组长 |
2 线性表分类
2.1 抽象数据类型
线性表是存储操作数据的,那么就涉及到数据类型,所以在看分类之前我们先了解一个概念:抽象数据类型。
数据类型: 是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。
例如很多编程语言的整型,浮点型,字符型这些指的就是数据类型,在计算机中,内存也不是无限大的,你要计算1+1=2这样的整型数字的加减乘除运算,显然不需要开辟很大的内存空间。而如果要计算1.23456789+2.987654321这样带大量小数的,就需要开辟比较大的空间才能存放的下。于是,计算机的研究者们就考虑,要对数据类型进行分类,分出多种数据类型来适应各种不同的计算条件差异。例如在C语言中,按照取值的不同,数据类型可以分为两类:
- 原子类型:不可以再分解的基本类型,例如整型、浮点型、字符型等等。
- 结构类型:由若干个类型组合而成,是可以再分解的,例如整型数组是由若干整型数据组成的。
抽象:是指抽取出事物具有的普遍性的本质。他要求抽出问题的特征而忽略非本质的细节,是对具体事物的一个概括。抽象是一种思考问题的方式,它隐藏了繁杂的细节。
抽象数据类型(Abstract Data Type,ADT) 是指一个数据模型及定义在该模型上的一组操作,就相当于高级语言当中类的概念。
抽象数据类型的定义仅取决于它的一组逻辑特性,而与其在计算机内部如何表示和实现无关。比如1+1=2这样的一个操作,在不同CPU的处理上可能不一样,但由于其定义的数学特性相同,所以在计算机编程者看来,它们都是相同的。
“抽象” 的意义在于数据类型的数学抽象特性。而且,抽象数据类型不仅仅指那些已经定义并实现的数据类型,还可以是计算机编程者在设计软件程序时自己定义的数据类型(比如Java中的类等)。
描述抽象数据类型的标准格式:
ADT 抽象数据类型 Data 数据元素之间逻辑关系的定义 Operation 操作 endADT
线性表的抽象数据类型:所谓抽象数据类型就是把数据类型和相关操作捆绑在一起。
线性表的抽象数据类型定义:
ADT 线性表(List) Data 线性表的数据对象集合为{$a_1$,$a_2$,...,$a_n$},每个元素的类型均为DataType。其中,除第一个元素$a_1$外,每个元素有且只有一个直接前驱元素,除了最后一个元素$a_n$外,每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。 Operation InitList(*L):初始化操作,建立一个空的线性表L. ListEmpty(L):判断线性表是否为空表,若线性表为空表,返回true,否则返回false ClearList(*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
实现两个线性表A、B的并集操作,即要使得集合A = A U B
- 其实仔细思考一下,我们只需要循环遍历集合B中的每一个元素,判断当前元素是否在A中存在,若不存在,则插入A中即可。
-
综合分析,我们需要运用几个基本的操作组合即可:
-
ListLength(L);
-
GetElem(L,i,*e);
-
LocateElem(L,e);
-
ListInsert(*L,i,e);
-
参考代码实现:
//union.c 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); } } }
2.2 分类
看完抽象数据类型,我们就来看看线性表的分类,如下图:
线性表有两种物理存储结构:顺序存储结构和链式存储结构。
2.3 顺序存储结构
线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素。
物理上的存储方式事实上就是在内存中找个初始地址,然后通过占位的形式,把一定的内存空间给占了,然后把相同数据类型的数据元素依次放在这块空地中。
线性表的顺序存储结构的结构代码:
#define MAXSIZE 20 typedef int ElemType; typedef struct { ElemType data[MAXSIZE]; int length; } SqList;
顺序存储结构封装需要的三个属性:
- 存储空间的起始位置,数组data,她的存储位置就是线性表存储空间的起始位置(电影院某个厅所在位置)。
- 线性表的最大存储容量:数组的长度MAXSIZE(电影院某个厅内的座位总数)
- 线性表的当前长度:length。(电影院某个厅当前看电影的人数)
数组的长度和线性表的当前长度需要区分一下:数组长度是存放线性表的存储空间的总长度,一般初始化后不变。而线性表的当前长度是线性表中元素的个数,是会变化的。
习惯上数组是从0开始的计算方法:
假设ElemType占用的是c个存储单元(字节),那么线性表中第i+1个数据元素和第i个数据元素的存储位置的关系是(LOC表示获得存储位置的函数):
地址计算方法:对于第 i 个数据元素的存储位置可以由推算得出:
根据上面的公式,我们就可以随时计算出线性表中任意位置的地址,不管他是的第一个还是最后一个,都是相同的时间。那么它的存储时间醒醒当然就是O(1),我们通常称为随机存储结构。
2.3.1 获取一个元素
//getElem.c #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef int Status; Status GetElem(SqList L, int i, ElemType *e) { if( L.length==0 || i<1 || i>L.length ) { return ERROR; } *e = L.data[i-1]; return OK; }
2.3.2 插入一个元素
- 如果插入位置不合理,抛出异常;
- 如果线性表长度大于等于数组长度,则抛出异常或动态增加数组容量。
- 从最后一个元素开始向前表里到第i个位置,分别将他们都向后移动一个位置。
- 将要插入元素填入位置 i 处;
- 线性表长度加1
Status ListInsert(SqList *L, int i, ElemType e) { int k; if( L->length == MAXSIZE ) { return ERROR; } if ( i<1 || i>L->Length+1) { return ERROR; } if( i <= L->Length ) { for( k=L->Length-1; k >= i-1; k-- ){ L->data[k+1] = L->data[k]; } } L->data[i-1] = e; L->Length++; return OK; }
2.3.3 删除一个元素
- 如果删除位置不合理,抛出异常
- 取出删除元素
- 从删除元素位置开始遍历到最后一个元素位置,分别将它们都向前移动一个位置;
- 表长减一
Status ListDelete(SqList *L, int i, ElemType *e) { int k; if( L->length == 0){ return ERROR; } if( i < 1 || i > L->length){ return ERROR; } *e = L->data[i-1]; //e用于保存第i个位置的值,并返回 if( i < L->Length){ for( k=i; k < L->length; k++){ L->data[k-1]=L->data[k]; } } L->length--; return OK; }
2.3.4 顺序存储结构小结
对于插入或者删除:
最好的情况:插入和删除操作刚好要求在最后一个位置操作,因为不需要移动任何元素,所以此时的时间复杂度为O(1)
最坏的情况: 如果插入和删除的位置是第一个元素,那就意味着要移动所有的元素向后或者向前,所以这个时间复杂度为O(n)
平均情况: 取中值
线性表顺序存储结构的优缺点:
- 线性表的顺序存储结构,在读数据时,不管是哪个位置,时间复杂度都是O(1),而在插入或删除时,时间复杂度都是O(n).
- 也就是说,顺序存储结构适合元素个数比较稳定,不经常插入和删除元素,而更多的操作是存取数据的应用。
- 优点:
- 无需为表中元素之间的逻辑关系而增加额外的存储空间。
- 可以快速存取表中任意位置的元素
- 缺点:
- 插入和删除操作需要移动大量元素。
- 当线性表长度变化较大时,难以确定存储空间的容量。
- 容易造成存储空间的 "碎片",浪费存储空间。因为线性表申请内存空间是一整块一整块申请的,那么中间就会造成很多的 ”碎片空间“,而无法使用。
这里简单说一下内存碎片哈:
- 外部碎片指的是那些还没有被分配出去(不属于任何进程),但由于太小了无法分配给申请空内存空间的新进程的内存空闲区域。外部碎片处于任何已分配区域或者页面外部的空闲存储块。这些存储块的总和可以满足当前申请的长度要求,但是由于他们的地址不连续或其他原因,使得系统无法满足当前申请。
-
内部碎片就是已经被分配出去(能明确指出属于哪个进程)却不能被利用的内存空间;内部碎片是处于区域内部或者页面内部的存储块,占有这些区域或页面的进程并不适用这个存储块。而在进行占有这块存储块时,系统无法利用它,直到进程释放它,或者进行结束时,系统才有可能利用这个存储空间。
3 小结
好了,本节我们主要了解一下线性表是什么,有哪些分类以及看了一下顺序存储的优缺点,由于链式存储的变种有很多,我们下节一一讲哈,有理解不对的地方欢迎指正哈。
标签:存储,线性表,元素,数据类型,抽象数据类型,数据结构,顺序存储 From: https://www.cnblogs.com/kukuxjx/p/17365542.html