文章目录
1.1线性表
线性结构的特点: 在数据元素的非空有限集中。
<1>存在惟一的一个被称为“第一个”的数据元素;
<2>存在惟一的一个被称为“最后一个”的数据元素;
<3>除第一个之外,集合中的每个数据元素均只有一个前驱;
<4>除最后一个之外,集合中的每个数据元素均只有一个后继。
线性表:是最常用且最简单的一种数据结构。简言之,一个线性表是n个数据元素的有限序列。
在稍微复杂的线性表中,一个数据元素可以由若干个数据项组成。在这种情况下常把数据元素称为记录,含有大量记录的线性表又称为文件。并且线性表中的数据元素可以是各种各样的但同一线性表中必定具有相特性,即属同一数据对象,相邻数据元素之间存在着序奇偶关系。(连续的)
线性表中元素的个数n(n ≥ 0 \ge0 ≥0)定义为线性表的长度,n=0时称为空表。在非空表中的每个数据元素都有一个确定的位置,如 a 1 a_1 a1是第一个数据元素, a n a_n an是最后一数据元素, a i a_i ai是第i个数据元素,称i为数据元素 a i a_i ai在线性表中的位序。(在线性表中第几个)
线性表是一个相当灵活的数据结构,它的长度可根据需求增长或者缩短,即对线性表的数据元素不仅可以进行访问,还可以进行插入和删除等。
1.2线性表的顺序表示和实现
假设线性表的每个元素需占用l个存储单元,并以所占的第一个单元的存储地址作为数据元素的存储位置(通常称为线性表的起始位置或者基地址)。则线性表中的第i+1个数据元素的存储位置LOC( a i + 1 a_{i+1} ai+1)和第i个数据元素的存储位置LOC( a i a_i ai) 之间满足下列关系:
L O C ( a i + 1 ) = L O C ( a i ) + l L O C ( a i ) = L O C ( a 1 ) + ( i − 1 ) ∗ l LOC(a_{i+1}) = LOC(a_i)+l \\ LOC(a_i) = LOC(a_1)+(i-1)*l LOC(ai+1)=LOC(ai)+lLOC(ai)=LOC(a1)+(i−1)∗l
线性表的这种机内表示称作线性表的顺序存储结构或顺序映像,通常,这种存储结构的线性表称为顺序表(亦可以理解为动态数组,但是是可以插入或者删改的动态数组)。它的特点是,以元素在计算机内”物理位置相邻“来表示线性表中数据元素之间的逻辑关系。
由于线性表的长度可变,且所需最大的存储空间随问题不同而不同,在C语言中可用动态分配的一维数组,