1、第2章 线 性 表 第第2章章 线性表线性表 2.1 线性表的概念及运算线性表的概念及运算 2.2 线性表的顺序存储线性表的顺序存储 2.3 线性表的链式存储线性表的链式存储 第2章 线 性 表 2.1 线性表的概念及运算线性表的概念及运算2.1.1 线性表的逻辑结构线性表的逻辑结构 第2章 线 性 表 线性表的定义： 线性表是由n (n0)个类型相同的数据元素a1, a2, ， an组成的有限序列，表中相邻数据元素之间存在着序偶关系。 （1）对于非空的线性表（a1, a2, ，ai-1, ai, ai+1, , an）， ai-1 领先于ai，称ai-1 是ai的直接前驱，而称ai是 ai-
2、1的直接后继。 （2）除了第一个元素a1外，每个元素ai有且仅有一个被称为其直接前驱的结点ai-1；除了最后一个元素an外，每个元素ai有且仅有一个被称为其直接后继的结点ai+1。 （3）线性表中元素的个数n被定义为线性表的长度，n=0时称为空表。 第2章 线 性 表 2.1.2 线性表的抽象数据类型定义线性表的抽象数据类型定义 ADT LinearList 数据元素数据元素： D=ai| aiD, i=1, 2, ，n, n0 ， D为某一数 据对象 关系关系： | ai, ai+1D，i=1, 2, , n-1 基本操作：基本操作： （1） InitList（L） 操作前提： L为未初始化
3、线性表。 操作结果： 将L初始化为空表。 第2章 线 性 表 （2） DestroyList(L)操作前提： 线性表L已存在。 操作结果： 将L销毁。 （3） ClearList(L)操作前提： 线性表L已存在 。 操作结果： 将表L置为空表。 （4） EmptyList（L）操作前提： 线性表L已存在。 操作结果： 如果L为空表则返回真， 否则返回假。 第2章 线 性 表 （5） ListLength（L） 操作前提： 线性表L已存在。 操作结果： 如果L为空表则返回0， 否则返回表中的元素个数。 （6） Locate(L, e) 操作前提： 表L已存在， e为合法元素值。 操作结果： 如果
4、L中存在元素e， 则将“当前指针”指向元素e所在位置并返回真， 否则返回假。 （7） GetData(L, i) 操作前提： 表L存在， 且i值合法， 即1iListLength（L）。 操作结果： 返回线性表L中第i个元素的值。 第2章 线 性 表 （8） InsList(L, i, e) 操 作 前 提 ： 表 L 已 存 在 ， e 为 合 法 元 素 值 且1iListLength(L)+1。 操作结果：在L中第i个位置插入新的数据元素e，L的长度加1。 （9） DelList(L, i, *e) 操作前提： 表L已存在且非空， 1iListLength(L)。 操作结果： 删除L的第
5、i个数据元素， 并用e返回其值， L的长度减1。 ADT LinearList 第2章 线 性 表 2.2 线性表的顺序存储线性表的顺序存储2.2.1 线性表的顺序存储结构线性表的顺序存储结构 线性表的顺序存储是指用一组地址连续的用一组地址连续的存储单元依次依次存储线性表中的各个元素，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中。 采用顺序存储结构的线性表通常称为顺序表顺序表。 顺序表的存储结构能够映射元素的逻辑结构。第2章 线 性 表 顺序表存储示意图 内存空间状态a1a2aianloc(a1)(n1)kloc(a1)(i1)kloc(a1)loc(a1)k存储地址逻辑地
6、址12in空闲第2章 线 性 表 顺序存储结构可以借助于一维数组来表示，一维数组的下标与元素在线性表中的序号相对应。线性表的顺序存储结构可用C语言定义如下： define MAXSIZE m /* m代表线性表可能达到的最大长度*/typedef struct ElemType elemMAXSIZE； /* 线性表占用的数组空间 */ int last； /* 记录线性表中最后一个元素在数组elem中 的位置（下标值）， 空表置为-1 */ SeqList； 第2章 线 性 表 2.2.2 线性表顺序存储结构上的基本运算线性表顺序存储结构上的基本运算 1. 查找操作查找操作 （1）按序号查找
7、）按序号查找GetData(L, i): 要求查找线性表L中第i个数据元素，其结果是L.elemi-1或L-elemi-1。 （2）按内容查找）按内容查找Locate(L, e): 要求查找线性表L中与给定值e相等的数据元素，其结果是：若在表L中找到与e相等的元素，则返回该元素在表中的序号；若找不到， 则返回一个“空序号”， 如-1。 第2章 线 性 表 按内容查找运算可采用顺序查找法实现：从第一个元素开始，依次将表中元素与给定元素 e 相比较， (1)若存在相等的元素，则表示查找成功，结果返回该元素在表中的序号序号； (2)若表中的所有元素都与给定元素 e 不相等，则表示查找失败，结果返回“
8、-1”。第2章 线 性 表 顺序表按内容查找算法描述：顺序表按内容查找算法描述： int Locate(SeqList L， ElemType e) i=0 ; while (i=L.last)&(L.elemi! =e) ) i+; if (ilast+1， i 的合法取值范围是 1iL-last+2 */ int k ; /* 首先判断插入位置是否合法首先判断插入位置是否合法 */ if ( (iL-last+2) ) printf(插入位置i值不合法)； return(ERROR); 【算法【算法2.2 线性表的插入运算线性表的插入运算】 第2章 线 性 表 /* 判断顺序表是否还有空间
9、可用来进行元素的插入判断顺序表是否还有空间可用来进行元素的插入 */if ( L-last=maxsize-1 ) printf (表已满无法插入)； return (ERROR); /* 为插入元素移动位置，注意数组下标与元素序号的对应关系为插入元素移动位置，注意数组下标与元素序号的对应关系 */for ( k=L-last ; k=i-1 ; k- ) L-elemk+1=L-elemk; L-elemi-1=e; L-last +; return (OK); 【算法【算法2.2 线性表的插入运算线性表的插入运算】 第2章 线 性 表 说明：说明：（1）当在表尾插入元素时，给定的插入元素的
10、位置i= L-last+2，算法中为插入元素移动位置的循环中语句L-elemk+1=L-elemk将不会执行，因为循环的终值大于初值，此时不需要移动元素， 可直接在表尾插入新元素e。 （2）当在表首插入元素时，给定的插入元素位置i= 1时， 为插入元素移动位置的语句L-elemk+1=L-elemk需执行n次，即将表中已存在的n个元素依次后移一个位置才能将e插入。结论：结论：语句L-elemk+1=L-elemk的语句频度与插入位 置i 有关。 第2章 线 性 表 3. 删除操作删除操作DelList（L，i，*e） 线性表的删除运算是指将表的第i(1in)个元素删除， 使长度为n的线性表(e
11、1，, ei-1，ei，ei+1，en)变成长度为n-1的线性表(e1，, ei-1， ei+1，en)。 顺序表进行删除操作时， 首先将原表中第i个位置的元素的值放入指针e所指向的单元作备份，然后将原表中位置i+1 ， n-1 ，n上的结点， 依次前移到位置i，n-2，n-1上，同时表的长度减1。 第2章 线 性 表 顺序表中删除元素顺序表中删除元素 例：已知线性表L=(4, 9, 15, 21, 28, 30, 30, 42, 51, 62)，删除位置 i = 5， 则需将第6个元素到第10个元素依次向前移动一个位置，如下图所示。第2章 线 性 表 顺序表删除算法描述：顺序表删除算法描述：
12、 int DelList ( SeqList *L , int i , ElemType *e )/* i的合法取值范围为1 i L . Last +1 */ int k ; /* 首先判断删除位置是否合法首先判断删除位置是否合法 */ if ( ( i L - last +1 ) ) printf (删除位置不合法！)； return ( ERROR ) ; 【算法【算法2.3 线性表的删除运算线性表的删除运算】 第2章 线 性 表 *e = L - elemi-1; for ( k = i ; i last ; k+ ) L - elemk-1= L - elemk; L - last -
13、 ; return ( OK ) ; 【算法【算法2.3 线性表的删除运算线性表的删除运算】 第2章 线 性 表 说明说明：（1）当删除顺序表的表尾元素时，给定的删除位置i = L - last + 1，算法中为删除元素移动位置的循环语句L - elemk-1= L - elemk将不会执行，因为循环变量的初值大于终值，此时不需要移动元素，仅将表长度减1即可。（2）当删除表首元素时，给定的删除元素位置i= 1， 算法中为删除元素移动位置的语句L - elemk-1=L-elemk需执行n-1次，即需要将表中除表首元素外的n-1个元素依次前移一个位置才能实现删除表首元素的操作。结论：结论：删除算
14、法中移位语句L-elemk-1= L-elemk的语句 频度也与删除位置i有关。 第2章 线 性 表 顺序表插入删除元素算法分析：顺序表插入删除元素算法分析：插入：插入：设 Pi 为在第i个元素之前插入元素的概率，假设在任何位置插入元素的概率相等，即 Pi =1/(n+1), i=1, 2, ，n+1。设Eins为在长度为n的表中插入一元素所需移动元素的平均次数： nkniniiinsnkninninPE1111211) 1(11) 1(删除：删除：设Qi为删除第i个元素的概率，假设在任何位置上删除元素的概率相等， 即Q i=1/n , i=1, 2, ，n。在长度为n的表中删除一个元素所需移
15、动元素的平均次数Edel为 ：1011211)(1)(nkniniidelnkninninQE第2章 线 性 表 总结：总结：顺序表的优点顺序表的优点： (1)无需为表示结点间的逻辑关系而增加额外的存储空间。(2)可方便地随机存取表中的任一元素。 缺点：缺点： (1)插入或删除运算不方便，平均需要移动一半元素。(2) 需占用连续的存储空间，要预先对表的长度进行估计，容易造成空间浪费或者数据溢出。 综上，顺序表适用于表的长度变化不大，且插入删除元素操作综上，顺序表适用于表的长度变化不大，且插入删除元素操作经常在表尾进行的线性表的存储。经常在表尾进行的线性表的存储。第2章 线 性 表 2.3 线性
16、表的链式存储线性表的链式存储 2.3.1 单链表单链表 单链表结点包括两个域：数据域数据域用来存储结点的值；指针域指针域用来存储数据元素的直接后继的地址（或位置），通过每个结点的指针域将线性表的n个结点按其逻辑顺序链接在一起。由于链表的每个结点只有一个指针域，故将这种链表又称为单链单链表表。单链表的结点结构单链表的结点结构 datanext数据域指针域第2章 线 性 表 由于单链表中每个结点的存储地址（位置）是存放在其前驱结点的指针域中的，由其前驱结点来指示，而第一个结点无前驱，因而应设一个头指针个头指针H指向第一个结点。同时，由于表中最后一个结点没有直接后继，则应该指定线性表中最后一个结点的
17、指针域为“空”（NULL）。 对于整个单链表的存取必须从头指针开始，头指针必须是已知的， 沿着每个结点的后继指针域可以依次找到线性表中原来逻辑上相邻的所有结点，从而实现了线性表的链式存储。第2章 线 性 表 例：下图所示为线性表（A, B, C, D, E, F, G, H）的单链表存储结构，整个链表的存取需从头指针开始进行，依次顺着每个结点的指针域找到线性表的各个元素。 ABCDEFGHH第2章 线 性 表 (a) 带头结点的空单链表HHa1a2an(b) 带头结点的单链表第2章 线 性 表 单链表的存储结构描述如下： typedef struct Node / * 结点类型定义 * / E
18、lemType data； struct Node *next； Node, *LinkList；假设有语句：LinkList L，则表示定义一个结构指针L，即单链表的头指针，它指向表中第一个结点。若L=NULL，则表示单链表为一个空表，其长度为0。若不是空表，则可以通过头指针，找到要访问的所有结点的数据信息。对于带头结点的单链表L，p = L - next指向表中的第一个结点a1，即p-data=a1，而p-next-data=a2。 其余依此类推。 第2章 线 性 表 2.3.2 单链表上的基本运算单链表上的基本运算 1. 建立单链表（头插法建表和尾插法建表）建立单链表（头插法建表和尾插法
19、建表）1）头插法建表头插法建立单链表图示头插法建立单链表图示 执行的语句组为:snextLnext；Lnexts；L(a) 建空表c1ss 指向新申请的结点sdatac1(b) 申请新结点并赋值Lci 1s(c) 插入第一个结点Lc2c1cic1s(d) 插入第i个元素第2章 线 性 表 用头插法建立单链表的算法： Linklist CreateFromHead ( ) LinkList L ; Node *s ; char c ; int flag = 1 ; /* 设置一个标志变量设置一个标志变量flag，初值为，初值为1，当输入，当输入“$” 时，将时，将flag置为置为0，建表结束，建
20、表结束 */ /* 为头结点分配存储空间为头结点分配存储空间*/ L = ( Linklist ) malloc ( sizeof ( Node ) ) ; L - next = NULL ; 【算法【算法2.5 用头插法建立单链表用头插法建立单链表】 第2章 线 性 表 While ( flag ) c = getchar () ; if ( c ! =$) /* 为读入的字符分配存储空间为读入的字符分配存储空间 */ s = ( Node* ) malloc ( sizeof ( Node ) ) ; s - data = c ; s - next = L - next ; L - nex
21、t = s ; else flag = 0 ; return L ; 【算法【算法2.5 用头插法建立单链表用头插法建立单链表】 第2章 线 性 表 2） 尾插法建表 尾插法建表图示尾插法建表图示 rs；r 始终指向单链表的表尾L(a) 建空表c1ss 指向新申请的结点空间sdatac1(b) 申请新结点并赋值Lc1s(c) 插入第一个结点Lc2c1rrr nexts；(d) 插入第二个结点sr第2章 线 性 表 Linklist CreateFromTail ( ) LinkList L ; Node *r , *s ; int flag = 1 ; L = ( Node * ) mallo
22、c ( sizeof ( Node ) ) ; /* 为头结点分配存储空间为头结点分配存储空间 */ L - next = NULL ; r = L ; /* r指针始终指向链表的当前表尾，指针始终指向链表的当前表尾， 以便于做尾插入，其以便于做尾插入，其 初值指向头结点初值指向头结点 */ 用尾插法建立单链表的算法： 【算法【算法2.6 尾插法建表尾插法建表】 第2章 线 性 表 while ( flag ) c = getchar ( ); if ( c ! = $) s = ( Node* ) malloc ( sizeof ( Node ) ) ; s - data = c ; r -
23、 next = s ; r = s ； else flag = 0 ; r - next = NULL ; /* 将最后一个结点的next链域置为空， 表示建表结束 */ return L ; 【算法【算法2.6 尾插法建表尾插法建表】 第2章 线 性 表 2. 查找查找（按序号查找和按值查找按序号查找和按值查找） 1） 按序号查找 算法描述：算法描述：设带头结点的单链表的长度为 n，要查找表中第 i 个结点，则需要从单链表的头指针 L 出发，从头结点的链域（L-next）开始顺着链域扫描，用指针 p 指向当前扫描到的结点（初值指向头结点），用 j 做计数器，累计当前扫描过的结点数（初值为0）
24、， 当j = i 时， 指针 p 所指的结点就是要找的第 i 个结点。 第2章 线 性 表 Node * Get ( LinkList L , int i )/* 在带头结点的单链表 L 中查找第 i 个结点， 若找到(1in)， 则返回该结点的存储位置（地址指针），否则返回NULL */ int j ； Node *p ； p = L ； j = 0 ； /* 从头结点开始扫描 */ while ( p - next ! = NULL & j next ； /* 扫描下一结点 */ j +； /* 已扫描结点计数器 */ if（ i = j ） return p ； /* 找到了第i个结点
25、*/ else return NULL ； /* 找不到， i0 或 i n */【算法【算法2.7 在单链表在单链表L中查找第中查找第i个结点个结点】 第2章 线 性 表 2) 按值查找 算法描述：按值查找是指在单链表中查找是否存在结点元素值等于给定元素 e 的结点，若有的话， 则返回首次找到的其值为 e 的结点的存储位置（地址），否则返回NULL。查找过程从单链表的头指针指向的头结点出发，顺着链域逐个将结点的值和给定值 e 作比较。 第2章 线 性 表 Node *Locate ( LinkList L, ElemType e) /* 在带头结点的单链表 L 中查找其结点值等于e 的结点，
26、 若找到则返回该结点的位置指针 p ；否则返回NULL */ Node *p ; p = L - next ; /* 从表中第一个结点比较 */ while ( p ! = NULL ) if ( p - data！= e ) p = p - next ; else break ; /* 找到结点e， 退出循环 */ return p ; 【算法【算法2.8 在单链表在单链表L中查找值等于中查找值等于e的结点的结点】 第2章 线 性 表 3. 单链表插入操作单链表插入操作 算法描述算法描述：要在带头结点的单链表L中第 i 个位置插入一个数据元素 e ，首先需要在单链表中找到第 i - 1 个结
27、点并用指针pre指示，然后申请一个新的结点并由指针 s 指示，其数据域的值为e，并修改第i-1个结点的指针使其指向s，然后使s结点的指针域指向原第i个结点。第2章 线 性 表 在单链表第在单链表第 i 个结点前插入一个结点个结点前插入一个结点La1ai 1aianpre(a) 寻找第i1 个结点es(b) 申请新的结点La1ai 1aianprees 与ai连链:snextprenextai-1与ai断链,插入e:prenexts；(c) 插入第2章 线 性 表 int InsList ( LinkList L , int i , ElemType e ) Node *pre , *s ; i
28、nt k ; /* 在第在第 i 个元素之前插入，个元素之前插入， 则需要先找到第则需要先找到第 i -1 个数据元素的存储位置个数据元素的存储位置, 用指针用指针pre指示指示 */ pre = L ; k = 0 ; while( pre != NULL & k next ; k = k + 1 ; 【算法【算法2.9 单链表插入操作单链表插入操作】 第2章 线 性 表 if ( k ! = i 1 ) /* 即即while循环是因为循环是因为 pre = NULL 或或 i data = e ; s - next = pre - next ; pre - next = s ; retur
29、n OK ; 【算法【算法2.9 单链表插入操作单链表插入操作】 第2章 线 性 表 4 单链表删除操作单链表删除操作 算法描述算法描述：要删除带头结点的单链表L中第 i 个位置的一个数据元素 ，首先需要沿着单链表的链域找到第 i - 1 个结点并用指针 p 指示，通过指针 p 可以找到待删除的结点（p - next ）及其后继结点（p - next - next），然后修改第 i 1 个结点的指针域使其指向第 i + 1 个结点，然后用 free 函数释放第 i 个结点的结点空间即可。第2章 线 性 表 单链表的删除过程单链表的删除过程 La1ai 1aianp(a) 寻找第i1 个结点由p
30、 指向它La1ai 1aianpai 1rrpnext;pnextpnextnext;free(r);(b) 删除并释放第i结点第2章 线 性 表 int DelList ( LinkList L , int i , ElemType *e ) Node * p , *r ; int k ; p = L ; k = 0 ; /* 寻找被删除结点 i 的前驱结点 i 1 使 p 指向它 */ while ( p - next != NULL & k next ; k = k + 1 ; 【算法【算法2.10 单链表删除操作单链表删除操作】 第2章 线 性 表 if ( k ! = i 1 ) /
31、* 即while循环是因为 p - next = NULL或 i next ; p - next = p - next - next ; free ( r ) ; return OK ; 【算法【算法2.10 单链表删除操作单链表删除操作】 第2章 线 性 表 说明说明：删除算法中的循环条件（p - next ! = NULL & k i - 1）与前插算法中的循环条件（ p ! = NULL & k next = NULL ）。 int ListLength ( LinkList L ) Node *p ; p = L - next ; j = 0 ; /* 用来存放单链表的长度 */ wh
32、ile ( p != NULL ) p = p - next ; j + ; return j ; 【算法【算法2.11 求单链表的长度求单链表的长度】 第2章 线 性 表 例例: 如果以单链表表示集合，假设集合A用单链表LA表示， 集合B用单链表LB表示，设计算法求两个集合的差，即A-B。 算法描述：集合的差A-B中包含所有属于集合A而不属于集合B的元素，对于集合A中的每个元素e，在集合B的链表LB中进行查找，若存在与e相同的元素，则从LA中将其删除。 第2章 线 性 表 void Difference ( LinkList LA , LinkList LB )Node *pre , *p
33、, *q , *r ; pre = LA ; p = LA - next ; /* p 指向指向LA表中的某一结点，表中的某一结点， 而而pre始终指始终指 向向 p 的前驱的前驱 */ while ( p ! = NULL ) q = LB - next ; /* 依次扫描依次扫描LB中的结点，中的结点， 看是否有与看是否有与LA中中p指向结点的值相同的结点指向结点的值相同的结点 */ while ( q ! = NULL & q - data ! = p - data ) q = q - next ; if ( q != NULL ) 【算法【算法2.12 用单链表求两个集合的差集用单链表
34、求两个集合的差集】 第2章 线 性 表 r = p ; pre - next = p - next ; p = p - next ; free ( r ) ; else pre = p ; p = p - next ; 【算法【算法2.12 用单链表求两个集合的差集用单链表求两个集合的差集】 第2章 线 性 表 2.3.3 循环链表循环链表 循环链表是单链表的另一种形式，它是一个首尾相接的链表。将单链表最后一个结点的指针域由NULL改为指向头结点或线性表中的第一个结点，就得到了单链形式的循环链表，称为循环单链表。 在循环单链表中，表中所有结点都被链在一个环上，为了使某些操作实现起来方便，在循环
35、单链表中也可设置一个头结点。 这样，空循环链表仅由一个自成循环的头结点表示。 第2章 线 性 表 La1ai 1aianL(a) 带头结点的空循环链表(b) 带头结点的循环单链表的一般形式a1ai 1aianrearrear*(rearnext)*(c) 采用尾指针的循环单链表的一般形式第2章 线 性 表 例：例：有两个带头结点的循环单链表LA、LB，编写一个算法，将两个循环单链表合并为一个循环单链表，其头指针为LA。 算法描述：算法描述：先找到两个链表的尾，并分别用指针p、q指向它们，然后将第一个链表的尾与第二个表的第一个结点链接起来，并修改第二个表的尾 q，使它的链域指向第一个表的头结点。
36、 第2章 线 性 表 LinkList merge ( LinkList LA , LinkList LB ) Node *p , *q ; p = LA ; q = LB ; while ( p - next ! = LA ) p = p - next ; while ( q - next! = LB ) q = q - next ; /* 修改表修改表LA的尾指针，的尾指针， 使之指向表使之指向表LB 中的第一个结点中的第一个结点 */ p - next = LB - next ; /* 修改表修改表LB 的尾指针，的尾指针， 使之指向表使之指向表LA 的头结点的头结点 */ q - ne
37、xt = LA ; free ( LB ) ; return ( LA ) ; 【算法【算法2.13 循环单链表的合并算法循环单链表的合并算法】 第2章 线 性 表 上例中要找到采用头指针指示的带头结点的单循环链表的表尾仍然需要像普通单链表一样遍历所有结点，此操作的时间复杂度为线性阶O(n)。 但是若在建立单循环链表时采用尾指针表示，则无需遍历就可以方便的找到该链表的首结点和尾结点，其时间复杂度是常量阶O(1)。 实际应用中应该视具体情况来决定到底采用头指针还是尾指针指示单循环链表。第2章 线 性 表 2.3.4 双向链表双向链表 在单链表的每个结点中增加一个指向其前驱的指针域 prior，形
38、成的链表中有两条方向不同的链，分别指向结点的前驱结点和后继结点，称之为双向链表双向链表(Double Linked List)。priordatanext前驱指针域数据域后继指针域第2章 线 性 表 La1a2a3L(a) 空的双向循环链表(b) 非空的双向循环链表 若再对双向链表的头结点的前驱指针域和尾结点的后继指针域进行修改，则可以进一步定义一种新的链表双向循环链表。第2章 线 性 表 由于在双向链表中既有前向链又有后向链，寻找任一个结点的直接前驱结点与直接后继结点变得非常方便。设指针p指向双链表中某一结点，则有下式成立： p-prior-next = p = p-next-prior 双
39、链表的结构定义如下： typedef struct DNode ElemType data ； struct DNode *prior ， *next ； DNode , *DoubleList ； 第2章 线 性 表 2.3.5 顺序表和链表的比较顺序表和链表的比较 1. 基于空间的考虑基于空间的考虑 链表中的每个结点，除了数据域外，还要额外设置指针域，从存储密度（结点数据结点数据本身所占的存储量和整个结点结构整个结点结构所占的存储量之比）来讲，是不经济的。 例如：设线性表中结点的数据为整数，指针所占空间和整型量相同。若不考虑顺序表中的备用结点空间，则顺序表的存储空间利用率为100%，而单链
40、表的存储空间利用率为50%。 结论：当线性表的长度变化不大，结论：当线性表的长度变化不大， 易于事先确定其大小时，易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构。为了节约存储空间，宜采用顺序表作为存储结构。 第2章 线 性 表 2. 基于时间的考虑基于时间的考虑 顺序表是利用向量实现的，对表中任一结点都可以直接存取，而链表中的结点，需要顺着指针域才能找到。 因此，若线性表的操作主要是进行查找，很少做插入和删除因此，若线性表的操作主要是进行查找，很少做插入和删除时，宜采用顺序表做存储结构。时，宜采用顺序表做存储结构。 在链表中的任何位置上进行插入和删除，只需要修改指针。而在顺序表中进行插入和删除，平均要移动表中近一半的结点。 因此，对于需要频繁进行插入和删除的线性表，因此，对于需要频繁进行插入和删除的线性表， 宜采用链宜采用链表做存储结构。若表表做存储结构。若表的插入和删除主要发生在表的首尾两端，的插入和删除主要发生在表的首尾两端， 则宜采用尾指针表示的单循环链表。则宜采用尾指针表示的单循环链表。
