当前位置：文档之家 › 算法与数据结构第2章 线性表

算法与数据结构第2章 线性表

  • 格式：ppt
  • 大小：664.00 KB
  • 文档页数：132

下载文档原格式

  / 132

合集下载

数据结构第2章作业 线性表(答案)

数据结构第2章作业 线性表(答案)

第2章线性表班级学号__________-姓名一、判断正误（×）1. 链表的每个结点中都恰好包含一个指针。

链表中的结点可含多个指针域，分别存放多个指针。

例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。

（×）2. 链表的物理存储结构具有同链表一样的顺序。

链表的存储结构特点是无序，而链表的示意图有序。

（×）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。

链表的结点不会移动，只是指针内容改变。

（×）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。

（×）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。

正好说反了。

顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜”（×）6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

前一半正确，但后一半说法错误，那是链式存储的优点。

顺序存储方式插入、删除运算效率较低，在表长为n的顺序表中，插入和删除一个数据元素，平均需移动表长一半个数的数据元素。

（×）7. 线性表在物理存储空间中也一定是连续的。

线性表有两种存储方式，顺序存储和链式存储。

后者不要求连续存放。

（×）8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。

线性表有两种存储方式，在顺序存储时，逻辑上相邻的元素在存储的物理位置次序上也相邻。

（×）9. 顺序存储方式只能用于存储线性结构。

顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构，例如完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。

（后一节介绍）（×）10. 线性表的逻辑顺序与存储顺序总是一致的。

理由同7。

链式存储就无需一致。

《数据结构与算法(C++语言版)》第2章 线性表

《数据结构与算法(C++语言版)》第2章 线性表
• 以下是一个使用类LinearList的C++程序，它假定之前的程 序均存储在LinearList.h之中，且异常类定义位于文件 exception.h之中。该示例完成以下操作：创建一个大小为5 的整数线性表L；输出该表的长度（为0）；在第0个元素之 后插入2；在第一个元素之后插入6和8（至此，线性表为2， 6，8）；寻找并输出第一个元素（为2）；输出当前表的长 度（为3）；删除并输出第一个元素。
数据结构与算法 （C++语言版）
第2章 线性表
线性表的类型定义
• 基本概念 • 线性表是由n（n≥0）个类型相同的数据元素组成的有限序 列，通常表示为L=(a1, …, ai–1, ai, ai+1, …, an)。其中，L为线 性表名称，ai为组成该线性表的数据元素，ai–1领先于ai，ai 领先于ai+1，称ai–1是ai的直接前驱元素，ai+1是ai的直接后继 元素。当i=1, 2, …, n–1时，ai有且仅有一个直接后继；当 i=2, 3, …, n时，ai有且仅有一个直接前驱。 • 线性表的长度就是线性表中元素的个数n（n≥0）。当n=0时， 称为空表。在非空表中的每个数据元素都有一个确定的位 置，如a1是第一个数据元素，an是最后一个数据元素，ai是 第i个数据元素。称i为数据元素ai在线性表中的位序。
线性表的类型定义
Prev_Elem(L, cur_e, &pre_e) //返回当前元素的前一个元素值 输入：线性表L。 输出：若cur_e是线性表L的数据元素，且不是第一个，则用 pre_e返回它的直接前驱元 素；否则操作失败，pre_e无定义。 Next_Elem(L, cur_e, &next_e) //返回当前元素的后一个元素值 输入：线性表L。 输出：若cur_e是线性表L的数据元素，且不是最后一个，则用 next_e返回它的直接后继元素；否则操作失败，next_e无定 义。

02331自考数据结构 第二章 线性表

02331自考数据结构 第二章 线性表

return ;
}
if ( L -> length >= ListSize ){
printf (" overflow ");
return ;
}
for ( j - L -> length -1; j >= i -1; j --)
L ->data [ j +1]= L -> data [ j ]; //从最后一个元素开始逐一后移
线性表的基本运算
上述运算仅仅是线性表的基本运算，不是其全部运 算。因为对不同问题的线性表，所需要的运算可能不同。 因此，对于实际问题中涉及其他更为复杂的运算，可用 基本运算的组合来实现。
线性表的基本运算
【例2.1】假设有两个线性表 LA 和 LB 分别表示两个 集合 A 和 B ，现要求一个新集合 A = A∪B 。
线性表的逻辑定义
数据元素“一个接一个的排列”的关系叫做 线性关系，线性关系的特点是“一对一”，在计 算机领域用“线性表”来描述这种关系。另外， 在一个线性表中数据元素的类型是相同的，或者 说线性表是由同一类型的数据元素构成的，如学 生情况信息表是一个线性表，表中数据元素的类 型为学生类型；一个字符串也是一个线性表：表 中数据元素的类型为字符型等等。
,
a2
i
,…,
ai-1
,
a．aii++1．1 , ．…,
an
)
an
线性表n的-1逻辑结an构和存储结构都发…生了相应的变化， 与插入运算相反，插…入是向后移动元素，而删除运算则
是向前移M动AX元-1 素，除非i=n 时直接删除终端元素，不需移
动元素。
删除前
删除后

数据结构课后习题第2章

数据结构课后习题第2章

2. 指针 P 指向不带头结点的线性链表 L 的首元素的条件是（ ）。
A.P= =L
C.P-﹥next==L
B.L-﹥Next==P
D.P-﹥next==NULL
3. 指针 p 指向带头结点的单循环链表 L 的首元素的条件是（ ）。
A.P= =L
C.P-﹥next==L
B.L-﹥Next==P
D.P-﹥next==NULL
网络工程 2011 级 1 班、计算机科学与技术 2011 级 2 班《算法与数据结构》课后习题（第 2 章）
2011 级 计科 (网工)
题号
得分
一
【课后习题】第 2 章 线性表
班 学号：
一、判断题（如果正确，在题号前打“”，否则打“”。每题 2 分，共 10 分)
二
( ) 1. 线性表若采用顺序存储表示时所有结点之间的存储单元地址必须连续。 ( ) 2. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 ( ) 3. 如果某个数据结构的每一个元素都是最多只有一个直接前驱，则必为线性结构。 ( ) 4. 线性表的逻辑顺序与物理顺序总是一致的。 ( ) 5. 线性表的长度是指它所占存储空间的大小。
二、填空题（每空 1.5 分，共 21 分)
1. 从逻辑结构看，线性表是典型的
2. 在一个长度为 n 的向量中在第 i（1≤i≤n+1）个元素之前插入一个元素时，需向后移动
个元素，算法的时间复杂度为
3. 在一个长度为 n 的向量中删除第 i（1≤i≤n）个元素时，需向前移动
算法的时间复杂度为
。
。
4. 若长度为 n 的线性表采用链式存储结构，在其第 i 个结点前插入一个新的元素的算法的

《数据结构》习题及答案：第2章 线性表(第1次更新2012-3)

《数据结构》习题及答案：第2章 线性表(第1次更新2012-3)

第2章线性表一、选择题1.表长为N 的顺序表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（），删除一个元素需要移动的元素个数为（）。

【＊＊，★】A. (N-1)/2B. NC. N+1D. N-1E. N/2F. (N+1)/2G. (N-2)/22.线性表是具有N 个（）的有限序列。

【＊】A、表元素B、字符C、数据元素D、数据项E、信息3.“线性表的逻辑顺序和物理顺序总是一致的。

”这个结论是（）。

【＊】A、正确的B、错误的C、不一定，与具体结构有关。

4.线性表采用链式存储结构时，要求内存中可用存储单元的地址（）。

【＊，★】A、必须是连续的B、部分地址必须是连续的C、一定是不连续的D、连续或不连续都可以。

5.带头结点的单链表为空的判定条件是（）。

【＊】A、head==NULLB、head->next==NULLC、head->next==headD、head!=NULL6.不带头结点的单链表head 为空的判定条件是（）。

【＊】A、head==NULLB、head->next==NULLC、head->next==headD、head!=NULL7.非空的循环单链表head 的尾结点P 满足（）。

（注:带头结点）【＊】A、P->NEXT=NULLB、p=NULLC、p->next==headD、p==head8.在一个具有n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）。

【＊，★】A、O(1)B、O(n)C、O(n2)D、O(nlog2n)9.在一个单链表中，若删除P 所指结点的后继结点，则执行（）。

【＊，★】A、p->next=p->next->nextB、p=p->next;p->next=p->next->nextC、p->next=p->next;D、p=p->next->next;10.在一个单链表中，若在Ｐ所指结点之后插入Ｓ所指结点，则执行（）。

数据结构线性表课后答案

数据结构线性表课后答案

第2章线性表1．选择题（1）顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。

A．110 B．108 C．100 D．120答案：B解释：顺序表中的数据连续存储，所以第5个元素的地址为：100+2*4=108。

（2）在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（）。

A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B．在第i个结点后插入一个新结点（1≤i≤n）C．删除第i个结点（1≤i≤n）D．将n个结点从小到大排序答案：A解释：在顺序表中插入一个结点的时间复杂度都是O(n2)，排序的时间复杂度为O(n2)或O(nlog2n)。

顺序表是一种随机存取结构，访问第i个结点和求第i个结点的直接前驱都可以直接通过数组的下标直接定位，时间复杂度是O(1)。

（3）向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。

A．8 B．63.5 C．63 D．7答案：B解释：平均要移动的元素个数为：n/2。

（4）链接存储的存储结构所占存储空间（）。

A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B．只有一部分，存放结点值C．只有一部分，存储表示结点间关系的指针D．分两部分，一部分存放结点值，另一部分存放结点所占单元数答案：A（5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。

A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续或不连续都可以答案：D（6）线性表Ｌ在（）情况下适用于使用链式结构实现。

A．需经常修改Ｌ中的结点值Ｂ．需不断对Ｌ进行删除插入C．Ｌ中含有大量的结点Ｄ．Ｌ中结点结构复杂答案：B解释：链表最大的优点在于插入和删除时不需要移动数据，直接修改指针即可。

（7）单链表的存储密度（）。

A．大于1 B．等于1 C．小于1 D．不能确定答案：C解释：存储密度是指一个结点数据本身所占的存储空间和整个结点所占的存储空间之比，假设单链表一个结点本身所占的空间为D，指针域所占的空间为N，则存储密度为：D/(D+N)，一定小于1。

北京林业大学《数据结构与算法》课件PPT 第2章 线性表


线性表P = (p0,p1,p2,…,pn)
P(x) = 10 + 5x - 4x2 + 3x3 + 2x4
指数 （下标i）
0
1
2
3
系数p[i] 10
5
-4
3
数组表示
（每一项的指数i隐含 在其系数pi的序号中）
4
2
北京林业大学信息学院
Rn(x) = Pn(x) + Qm(x)
线性表R = (p0 + q0,p1 + q1,p2 + q2,…,pm + qm,pm+1,…,pn)
数，即表长
例1 分析26 个英文字母组成的英文表
（ A, B, C, D, …… , Z） 数据元素都是字母; 元素间关系是线性 例2 分析学生情况登记表
学号
041810205 041810260 041810284 041810360
：
姓名
于春梅 何仕鹏 王爽 王亚武
：
性别
女 男 女 男 ：
年龄
下标i 0
1
2
系数 b[i]
8
22 -9
指数 1
7
8
线性表P =((p1, e1), (p2, e2),…,(pm, em))
创建一个新数组c 分别从头遍历比较a和b的每一项
✓指数相同，对应系数相加，若其和不为零，则在c中增加一个新项 ✓指数不相同，则将指数较小的项复制到c中 一北个京多林项业大式学已信遍息历学完院毕时，将另一个剩余项依次复制到c中即可
线性表
北京林业大学信息学院
第2章 线性表
教学目标
1. 了解线性结构的特点 2.掌握顺序表的定义、查找、插入和删除 3.掌握链表的定义、创建、查找、插入和删除 4.能够从时间和空间复杂度的角度比较两种存储结

《数据结构及其应用》笔记含答案 第二章_线性表

第2章线性表一、填空题1、线性结构反映结点间的逻辑关系是一对一的。

2、线性结构的特点：1）只有一个首结点和尾结点2）除首尾结点外，其他结点只有一个直接前驱和一个直接后继3、线性表的顺序表示又称为顺序存储结构。

4、结点只有一个指针域的链表，称为单链表。

5、首尾相接的链表称为循环链表。

6、线性表的链式表示又称为非顺序映像。

7、指向链表中第一个结点的指针称为头指针。

8、链表中存储第一个数据元素的结点称为首元结点。

二、判断题1、线性表的逻辑顺序与存储顺序总是一致的。

（╳）2、顺序存储的线性表可以按序号随机存取。

（√）3、顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。

（╳）4、线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。

（√）5、在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。

（╳）6、在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。

（√）7、线性表的链式存储结构优于顺序存储结构。

（╳）8、在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。

（√）9、线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。

（√）10、在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。

（╳）11、线性表的特点是每个元素都有一个前驱和一个后继。

（╳）三、单项选择题1、顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（B）。

A．110 B．108 C．100 D．120解释：顺序表中的数据连续存储，所以第5个元素的地址为：100+2*4=108。

2、在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（A）。

A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B．在第i个结点后插入一个新结点（1≤i≤n）C．删除第i个结点（1≤i≤n）D．将n个结点从小到大排序解释：在顺序表中插入一个结点的时间复杂度都是O(n2)，排序的时间复杂度为O(n2)或O(nlog2n)。

第二章线性表答案

第⼆章线性表答案第2章线性表⼀选择题1．下述哪⼀条是顺序存储结构的优点？（ A ）A．存储密度⼤ B．插⼊运算⽅便 C．删除运算⽅便 D．可⽅便地⽤于各种逻辑结构的存储表⽰2．下⾯关于线性表的叙述中，错误的是哪⼀个？（ B ）A．线性表采⽤顺序存储，必须占⽤⼀⽚连续的存储单元。

B．线性表采⽤顺序存储，便于进⾏插⼊和删除操作。

C．线性表采⽤链接存储，不必占⽤⼀⽚连续的存储单元。

D．线性表采⽤链接存储，便于插⼊和删除操作。

3．线性表是具有n个（ C ）的有限序列（n>0）。

A．表元素 B．字符 C．数据元素 D．数据项 E．信息项4．若某线性表最常⽤的操作是存取任⼀指定序号的元素和在最后进⾏插⼊和删除运算，则利⽤（ A ）存储⽅式最节省时间。

A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表5．某线性表中最常⽤的操作是在最后⼀个元素之后插⼊⼀个元素和删除第⼀个元素，则采⽤（ D ）存储⽅式最节省运算时间。

A．单链表 B．仅有头指针的单循环链表 C．双链表D．仅有尾指针的单循环链表6．设⼀个链表最常⽤的操作是在末尾插⼊结点和删除尾结点，则选⽤( D )最节省时间。

A. 单链表B.单循环链表C. 带尾指针的单循环链表D.带头结点的双循环链表7．若某表最常⽤的操作是在最后⼀个结点之后插⼊⼀个结点或删除最后⼀个结点。

则采⽤（ D ）存储⽅式最节省运算时间。

A．单链表 B．双链表 C．单循环链表 D．带头结点的双循环链表8. 静态链表中指针表⽰的是（ BC ）.A．内存地址 B．数组下标 C．下⼀元素地址D．左、右孩⼦地址9. 链表不具有的特点是（ C ）A．插⼊、删除不需要移动元素 B．可随机访问任⼀元素C．不必事先估计存储空间 D．所需空间与线性长度成正⽐10. 下⾯的叙述不正确的是（ BC ）A．线性表在链式存储时，查找第i个元素的时间同i的值成正⽐表4s→供选择的答案：A.连续B.单向链接C.双向链接D.不连接E.循环链接F.树状G.⽹状H.随机I.顺序J.顺序循环12.(1) 静态链表既有顺序存储的优点，⼜有动态链表的优点。

数据结构第二章线性表1答案

数据结构第二章线性表1答案第二部分线性表一、选择题1．关于顺序存储的叙述中,哪一条是不正确的( B )A.存储密度大B.逻辑上相邻的结点物理上不必邻接C.可以通过计算直接确定第i个结点的位置D.插入、删除操作不方便2．长度为n的单链表连接在长度为m的单链表后的算法的时间复杂度为( C )A O(n)B O(1)C O(m)D O(m+n)3．在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是：( A )A 访问第i个结点（1<=i<=n）和求第i个结点的直接前趋（2<=i<=n）B 在第i个结点（1<=i<=n）后插入一个新结点C 删除第i个结点（1<=i<=n）D 将n个结点从小到大排序4．一个向量第一个元素的存储地址是100 ，每个元素的长度为2 ，则第5 个元素的地址是：( B )（A ）110 （ B ）108 （C ）100 （D ）1205．已知一个顺序存储的线性表，设每个结点需要占m个存储单元，若第一个结点的地址为da，则第i个结点的地址为：( A ) A）da+(i-1)*m B) da+i*m C) da-i*m D) da+(i+1)*m6．在具有n个结点的单链表中，实现（A ）的操作，其算法的时间复杂度为O(n)。

A）遍历链表和求链表的第i个结点B）在地址为p的结点之后插入一个结点C）删除开始结点D）删除地址为p的结点的后继结点7．链表是一种采用（B ）存储结构存储的线性表。

（A ）顺序（B ）链式（ C ）星式（D ）网状8．线性表若采用链式存储结构时，要求内存中可用存储单元的地址：（D ）（A ）必须是连续的（ B ）部分地址必须是连续的（C ）一定是不连续的（ D ）连续或不连续都可以9．线性表Ｌ在（B ）情况下适用于使用链式结构实现。

（Ａ）需经常修改Ｌ中的结点值（Ｂ）需不断对Ｌ进行删除插入（Ｃ）Ｌ中含有大量的结点（Ｄ）Ｌ中结点结构复杂10．在长度为n 的顺序表的第i (1≤i≤n+1) 个位置上插入一个元素，元素的移动次数为( A )A.n-i+1B.n-iC.iD.i-111．线性表是（A）。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

利用已有基本运算求解问题 例2.1 假设有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示,即线性表中的数据元素即为集合中的成员。编写一 个算法求一个新的集合C=A∪B,即将两个集合的并集放在线 性表LC中。 解题思路: LC LA LC LB中不在LA中的元素
void unionList(List LA,List LB,List &LC)
该运算返回L中第 i(1≤i≤ListLength(L))个元素的值,存放在e中。
e=L->data[i-1];
return 1; } 本算法的时间复杂度为O(1)。
(7) 按元素值查找LocateElem(L,e) 该运算顺序查找第1个值域与e相等的元素的位序。若这样的元 素不存在,则返回值为0。 int LocateElem(SqList *L, ElemType e) { int i=0; while (i<L->length && L->data[i]!=e) i++; if (i>=L->length) else } return i+1; return 0;
{ int lena,lenb,lenc,i; ElemType e; InitList(LC); lena=ListLength(LA); for (i=1;i<=lena;i++) //求线性表的长度
//将LA的所有元素插入到Lc中
{ GetElem(LA,i,e); ListInsert(LC,i,e);
0
返回到 sq Main：
？？？
main：
引用的作用 main() { SqList *sq; InitList(sq); op(sq);
sq
？？？
L 调用 InitList
} void InitList (SqList *&L) //用引用 { L=(SqList *) malloc (sizeof(SqList))； L->length=0； }
当n=0时,表示线性表是一个空表,即表中不包含任何元 素。设序列中第i(i表示逻辑位序)个元素为ai(1≤i≤n)。
线性表的一般表示为: (a1,a2,…ai,ai+1,…,an)
逻辑结构
其中 a1 为第一个元素 , 又称做表头元素 ,a2 为第二个 元素,an为最后一个元素,又称做表尾元素。 例如,在线性表 (1,4,3,2,8,10) 中,1为表头元素,10为表尾元素。
a0
逻辑位序 1
…
ai-1
i
ai
i+1
…
an-1
n
…
…
MaxSize
例如：ListInsert_Sq(L, 5, 66) i--; /*将顺序表位序转化为data下标*/ for (j=L->length;j>i;j--) L->data[j]=L->data[j-1]; /*将data[i]及后面元素后移一个位臵*/ L->data[i]=e;
本算法中基本运算为 while 循环中的 i++ 语句 , 故时间复杂 度为: O(L->length)或O(n)
(8) 插入数据元素ListInsert(L,i,e) 该运算在顺序表L的第i个位臵(1≤i≤ListLength(L)+1) 上插入新的元素e。 思路：如果i值不正确,则显示相应错误信息；否则将 顺序表原来第 i 个元素及以后元素均后移一个位臵 , 腾出 一个空位臵插入新元素,顺序表长度增1。
2.2.1 线性表的顺序存储—顺序表
线性表的顺序存储结构就是:把线性表中的所有元素 按照其逻辑顺序依次存储到从计算机存储器中指定存储 位臵开始的一块连续的存储空间中。 这样,线性表中第一个元素的存储位臵就是指定的存 储位臵,第i+1个元素(1≤i≤n-1)的存储位臵紧接在第i个元 素的存储位臵的后面。 线性表 逻辑结构 顺序表 存储结构
对于第1章的逻辑结构City，假定每个元素占用30个 存储单元，数据从100号单元开始由低地址向高地址方向 存储，对应的顺序表如下：
地址
100
城市名
Beijing Shanghai
区号
010 021
说明
首都 直辖市
130
160 190
Wuhan
Xian Nanjing
027
029 025
湖北省省会
存储地址 LOC(A) LOC(A)+sizeof(ElemType) LOC(A)+(i-1)*sizeof(ElemType) LOC(A)+(n-1)*sizeof(ElemType) LOC(A)+(MaxSize-1)*sizeof(ElemType)
顺序表示意图
在定义一个线性表的顺序存储类型时 , 需要定义一个数组 来存储线线表中的所有元素和定义一个整型变量来存储线性 表的长度。 假定数组用 data[MaxSize] 表示 , 长度整型变量用 length 表 示 , 并采用结构体类型表示 , 则元素类型为通用类型标识符 ElemType的线性表的顺序存储类型可描述如下:
陕西省省会 江苏省省会
210
2.2.2 顺序表基本运算的实现
一旦采用顺序表存储结构,我们就可以用C/C++语言实 现线性表的各种基本运算。为了方便,假设ElemType为 char类型,使用如下自定义类型语句: typedef char ElemType;
1. 建立顺序表
其方法是将给定的含有n个元素的数组的每个元素依次放 入到顺序表中，并将n赋给顺序表的长度成员。算法如下：
int ListInsert(SqList *&L,int i,ElemType e) { int j; if (i<1 || i>L->length+1) return 0; i--; //将顺序表逻辑位序转化为data下标即物理位序 for (j=L->length;j>i;j--) //将data[i]及后面元素后移 L->data[j]=L->data[j-1]; L->data[i]=e; L->length++; //顺序表长度增1 return 1; }
2.1.2 线性表的运算
线性表的基本运算如下:
(1) 初始化线性表InitList(&L):构造一个空的线性表L。 (2) 销毁线性表DestroyList(&L):释放线性表L占用的内存空 间。
(3) 判线性表是否为空表ListEmpty(L):若L为空表,则返回 真,否则返回假。 (4) 求线性表的长度ListLength(L):返回L中元素个数。 (5) 输出线性表DispList(L):当线性表L不为空时,顺序显示 L中各结点的值域。 (6) 求 线 性 表 L 中 指 定 位 臵 的 某 个 数 据 元 素 GetElem(L,i,&e): 用 e 返回 L 中第 i(1≤i≤ListLength(L)) 个元素 的值。
}
lenB=ListLength(LB);
lenc=0;
for (i=1;i<=lenb;i++) { GetElem(LB,i,e); //取LB中第i个数据元素赋给e if (!LocateElem(LA,e))
ListInsert(LC,++lenc,e);
//LA中不存在和e相同者,则插入到LC中 }
Байду номын сангаас区别
假定线性表的元素类型为ElemType,则每个元素所占用 存储空间大小(即字节数)为sizeof(ElemType),整个线性表所占 用存储空间的大小为: n*sizeof(ElemType) 其中,n表示线性表的长度。
下标位置 0 1 ┇ i-1 ┇ n-1 ┇ MaxSize-1
线性表存储空间 a1 a2 ┇ ai ┇ an ┇ ┇
0
返回到 sq main：
(2) 销毁线性表DestroyList(L) 该运算的结果是释放线性表L占用的内存空间。 void DestroyList(SqList *&L) {
free(L);
} 本算法的时间复杂度为O(1)。
思考题：这里采用顺序指针，而不是直接给定顺 序表。两者有什么区别？ 如果直接采用顺序表： void InitList(SqList &L) { L.length=0; }
第2章 线性表
2.1 线性表的基本概念 2.2 线性表的顺序存储 2.3 线性表的链式存储 2.4 线性表的应用 2.5 有序表 本章小结
2.1 线性表的基本概念
2.1.1 线性表的定义 2.1.2 线性表的运算
2.1.1 线性表的定义
线性表是具有相同特性的数据元素的一个有限序列。 该序列中所含元素的个数叫做线性表的长度,用n表 示,n≥0。
typedef struct { ElemType data[MaxSize]; int length; } SqList; //顺序表类型
其中,data成员存放元素,length成员存放线性表的实际长度。
说明：由于C/C++中数组的下标从0开始，线性表的第i 个元素ai存放顺序表的第i-1位臵上。为了清楚，将ai在逻辑 序列中的位臵称为逻辑位序，在顺序表中的位臵称为物理位 序。
}
体现结构化编程的思想。
由 于 LocateElem(LA,e) 运 算 的 时 间 复 杂 度 为 O(ListLength(LA)),所以本算法的时间复杂度为: O(ListLength(LA)*ListLength(LB))。
2.2 线性表的顺序存储