第二章线性表

1、 考纲要求考纲要求 1. 1. 线性表的定义和基本操作线性表的定义和基本操作2. 2. 顺序存储结构（顺序表）顺序存储结构（顺序表）3. 3. 链式存储结构（链表）链式存储结构（链表）4. 4. 线性表的应用线性表的应用1 1、有穷性有穷性：由有限个元素组成，元素个数：由有限个元素组成，元素个数nn表长度，表长度，n=0n=0空表。空表。 设线性表为设线性表为 (a(a1 1，a a2 2, . . . , . . . ，a ai i，. . . . . . ，a an n), ), 称称 i i 为为 a ai i在线性表中的位序。在线性表中的位序。2 2、有序性有序性：线性表元素之间存在序

2、偶关系，：线性表元素之间存在序偶关系，1in1inextq-next ; ; p-nextp-next = = q-next;q-next; B Bp p = = q-nextq-next ; ; q-nextq-next = = p;p; C Cp p = = q-nextq-next ; ; q-nextq-next = = p-next;p-next; D Dq-nextq-next = = q-next-next;q-next-next; q-nextq-next = = q;q;（7）设计算法将值为设计算法将值为x x的节点插入到值为的节点插入到值为k k的节点之前，若没有的节点之前

3、，若没有找到值为找到值为k k的结点，即插到链表的表尾；判断单链表是否递增有的结点，即插到链表的表尾；判断单链表是否递增有序；实现单链表的就地逆置运算。序；实现单链表的就地逆置运算。（基于单链表遍历操作的运算）（基于单链表遍历操作的运算）（8)8) 复制一个单链表。复制一个单链表。（基于单链表创建操作的运算）（基于单链表创建操作的运算）（9 9）在有序单链表中插入数据域为）在有序单链表中插入数据域为x x的结点，插入后单链表仍然的结点，插入后单链表仍然是有序的；设单链表是非递减的有序序列，设计算法删除链表中是有序的；设单链表是非递减的有序序列，设计算法删除链表中值相同的多余结点；值相同的多余结

4、点；（有序单链表的操作运算）（有序单链表的操作运算）（1010）设单链表）设单链表A,BA,B，设计的算法判定，设计的算法判定B B是否为是否为A A的子序列；设两的子序列；设两个递增的单链表个递增的单链表A,BA,B，设计算法将他们合并成一个有序链表。，设计算法将他们合并成一个有序链表。（多链表操作）（多链表操作）（1111）采用程序设计语言描述算法（使用采用程序设计语言描述算法（使用C C、C+C+或或JAVAJAVA语言实现，关键之处请给出简要注释。语言实现，关键之处请给出简要注释。datalink1 1、循环链表的存储方式循环链表的存储方式: :将单链表终端节点的指针域由空指针改将单链

5、表终端节点的指针域由空指针改为指向头结点，使整个链表构成一个环，该链表称为循环链表为指向头结点，使整个链表构成一个环，该链表称为循环链表。2 2、循环链表上基本操作的实现循环链表上基本操作的实现：循环链表上基本操作与单链表：循环链表上基本操作与单链表类似，只不过将循环条件改为：类似，只不过将循环条件改为：p-next!=hp-next!=h。3 3、从表中任意一个位置出发都可以遍历整个循环链表。从表中任意一个位置出发都可以遍历整个循环链表。4 4、例题例题：（1 1）非空的单循环链表）非空的单循环链表L L的尾结点的尾结点p p满足（满足（ ）。）。A.p-next=NULL; B.p=NUL

6、L C.p-next=L D. p=LA.p-next=NULL; B.p=NULL C.p-next=L D. p=L（2 2）若要在）若要在O(1)O(1)时间内实现两个循环单链表的首尾相接，则两时间内实现两个循环单链表的首尾相接，则两个循环单链表应各设一个指针，分别指向（个循环单链表应各设一个指针，分别指向（ ）。）。A.A.各自的头结点各自的头结点 B.B.各自的表尾结点各自的表尾结点C.C.各自的第一个元素结点各自的第一个元素结点 D.D.一个表的头结点，一个表的尾结点一个表的头结点，一个表的尾结点（3 3）设有两个长度为）设有两个长度为n n的单链表，以的单链表，以h1h1为头指针

7、的是链表是非循为头指针的是链表是非循环的，以环的，以h2h2为尾指针的链表是循环的，则（为尾指针的链表是循环的，则（ ）。）。A.A.两个链表删除第一个结点的操作，时间复杂度均为两个链表删除第一个结点的操作，时间复杂度均为O(1)O(1)B.B.两个链表表尾插入一个结点的操作，时间复杂度均为两个链表表尾插入一个结点的操作，时间复杂度均为O(n)O(n)C.C.循环链表要比非循环链表占有更多的空间循环链表要比非循环链表占有更多的空间D.D.非循环链表要比循环链表占有更多的空间非循环链表要比循环链表占有更多的空间1 1、双向链表的存储方式双向链表的存储方式: :在单链表的结点中增加一个指向其前驱在

8、单链表的结点中增加一个指向其前驱的指针域，就形成了双向链表的指针域，就形成了双向链表。通常我们使用带头结点的双向循。通常我们使用带头结点的双向循环链表。环链表。2 2、双向链表存储结构定义双向链表存储结构定义：每个结点，：每个结点，除存储除存储所对应数据元素所对应数据元素信息外，还需存储其直接后继信息外，还需存储其直接后继和前趋和前趋的信息的信息。typedef struct DNode ElemType data; struct LNode *next,*prior; DNode ，*DLinkList;3、从表中任意一个位置出发都可以遍历整个表。从表中任意一个位置出发都可以遍历整个表。4

9、4、双向链表上基本操作的实现双向链表上基本操作的实现：a.a.插入操作插入操作b.b.删除操作删除操作5 5、例题例题：（1 1）与单链表相比，双向链表的优点是（）与单链表相比，双向链表的优点是（ ）。）。A.A.可以进行随机访问可以进行随机访问 B.B.数据插入和删除操作更简单数据插入和删除操作更简单C.C.节约存储空间节约存储空间 D.D.访问前后结点更加灵活访问前后结点更加灵活（2 2）带头结点的双向循环链表）带头结点的双向循环链表L L为空的条件（为空的条件（ ）。）。A.L-next-prior=NULLA.L-next-prior=NULL B.L-next=LB.L-next=L

10、C.L-prior=L D.BC.L-prior=L D.B和和C C都对都对（3）设设p p结点是带表头结点双向循环链表的表中结点结点是带表头结点双向循环链表的表中结点, ,在在p p结点后结点后插入插入s s结点语句序列中正确的是结点语句序列中正确的是( )( )A. s-next=p-nextA. s-next=p-next；p-next-prior=sp-next-prior=s； p-next=sp-next=s；s-prior=ps-prior=p；B. p-next=sB. p-next=s；s-next=p-nexts-next=p-next； p-next-prior=sp-next-prior=s；s-next=ps-next=p；C. p-next=sC. p-next=s；p-next-prior=sp-next-prior=s； s-next=p-nexts