本章的基本内容是:线性表的逻辑结构定义和各种存储结构的描述方法;在线性表的两类存储结构(即顺序表和链表)上如何实现基本操作。
线性表是一种比较简单的数据结构,它是n个节点的有限序列。线性表常用的存储方式有两种:顺序存储结构和链式存储结构。
在线性表的顺序存储结构中,是利用节点的存储位置来反映节点的逻辑关系,节点的逻辑次序与存储空间中的物理次序一致,因而只要确定了线性表中起始节点的存储位置,即可方便地计算出任一节点的存储位置,所以可以实现节点的随机访问。在顺序表中只需存放节点自身的信息,因此,存储密度大、空间利用率高。但在顺序表中,节点的插入、删除运算可能需要移动许多其他节点的位置,一些长度变化较大的线性表必须按照最大需要的空间分配存储空间,这些都是线性表顺序存储结构的缺点。
而在线性表的链式存储结构中,节点之间的逻辑次序与存储空间中的物理次序不一定相同,是通过给节点附加一个指针域来表示节点之间的逻辑关系。所以,不需要预先按最大的需要分配存储空间。同时,链表的插入、删除运算只需修改指针域,而不需要移动其他节点。这是线性表链式存储结构的优点。它的缺点在于,每个节点中的指针域需要额外占用存储空间,因此,它的存储密度较小。另外,链式存储结构是一种非随机存储结构,查找任一节点都要从头指针开始,沿指针域一个一个地搜索,增加了某些算法的时间代价。
将单链表加以改进可得到循环链表和双向链表。在循环链表中,所有的节点构成了一个环,所以从任一节点开始都可以扫描此线性表中的每个节点。双向链表既有指向直接后继的指针,又有指向直接前趋的指针,从而便于查找节点的前趋。
线性表的运算主要有查找、插入和删除,应熟练掌握线性表在不同存储方式下各种运算的实现方法。
1.选择题
(1)线性结构中的一个节点代表一个 。
A.数据元素 B.数据项
C.数据 D.数据结构
(2)线性表L=(a1, a2,…,ai,…,an),下列说法正确的是 。
A.每个元素都有一个直接前驱和一个直接后继
B.线性表中至少要有一个元素
C.表中诸元素的排列顺序必须是由小到大或由大到小的
D.除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和一个直接后继
(3)顺序表是线性表的 。
A.链式存储结构 B.顺序存储结构
C.索引存储结构 D.散列存储结构
(4)对于顺序表,以下说法错误的是 。
A.顺序表是用一维数组实现的线性表,数组的下标可以看成是元素的绝对地址
B.顺序表的所有存储节点按相应数据元素间的逻辑关系决定的次序依次排列
C.顺序表的特点是:逻辑结构中相邻的节点在存储结构中仍相邻
D.顺序表的特点是:逻辑上相邻的元素存储在物理位置也相邻的单元中
(5)对顺序表上的插入、删除算法的时间复杂度分析来说,通常以 为标准操作。
A.条件判断 B.节点移动
C.算术表达式 D.赋值语句
(6)对于顺序表的优缺点,以下说法错误的是 。
A.无需为表示节点间的逻辑关系而增加额外的存储空间
B.可以方便地随机存取表中的任何一个节点
C.插入和删除操作较方便
D.由于顺序表要求占用连续的空间,存储分配只能预先进行(静态分配)
(7)在含有n个节点的顺序存储的线性表中,在任一节点前插入一个节点所需移动节点的平均次数为 。
A.n B.n/2
C.(n-1)/2 D.(n+1)/2
(8)在含有n个节点的顺序存储的线性表中,删除一个节点所需移动节点的平均次数为 。
A.n B.n/2
C.(n-1)/2 D.(n+1)/2
(9)带头节点的单链表head为空的条件是 。
A.head=NULL B.head->next=NULL
C.head->next=head D.head!=NULL
(10)在单循环链表head的尾节点*p满足 。
A.p->next=NULL B.p=NULL
C.p->next=head D.p=head
(11)在双循环链表的*p节点之后插入*s 节点的操作是 。
A.p->next=s; s->prior=p; p->next->prior=s; s->next=p->next;
B.p->next=s; p->next->prior=s; s->prior=p; s->next=p->next;
C.s->prior=p; s->next=p->next;p->next:=s; p->next=prior=s;
D.s->prior=p; s>next=p>next; p>next->prior=s;p->next=s;
(12)在一个单链表中,已知*q 节点是*p节点的前驱节点,若在*q和*p之间插入节点*s,则执行 。
A.s->next=p->next;p->next=s;
B.p->next=s->next;s->next=p;
C.q->next=s; s->next=p;
D.p->next=s; s->next=q;
(13)在一个单链表中,若*p节点不是最后节点,在*p之后插入节点*s,则执行 。
A.s->next=p; p->next=s;
B.s->next=p->next; p->next=s;
C.s->next=p ->next;p=s;
D.p->next=s; s->next=p;
(14)若某线性表中最常用的操作是取第i个元素和找第i个元素的前驱元素,则采用
存储方式最节省时间。
A.顺序表 B.单链表
C.双链表 D.单循环链表
(15)设rear是指向非空带头节点的单循环链表的尾指针,则删除表头节点的操作可表示为 。
A.p=rear; rear=rear->next;free(p);
B.rearr=rear->next;free(rear);
C.rear=rear->next->next;free(rear);
D.p=rear->next->next; rear->next->next=p->next;free(p);
(16)在一个单链表中,若删除*p节点的后继节点,则执行 。
A.q=p->next;p->next=q->next;free(q);
B.p=q->next;p->next=p->next->next;free(p);
C.p->next=p->next; free(p->next);
D.p=p->next->next;free(p->next);
(17)设指针p指向双链表的某一节点,则双链表结构的对称性可用 式来刻画。
A.p->prior->next->==p->next->next
B.p->prior->prior->==p->next->prior
C.p->prior->next->==p->next->prior
D.p->next->next->==p->prior->prior
(18)在循环链表中,将头指针改设为尾指针rear后,其头节点和尾节点的存储位置分别是 。
A.rear和rear->next->next B.rear->next和rear
C.rear->next->next和rear D.rear和rear->next
(19)循环链表的主要优点是 。
A.不再需要头指针了
B.已知某个节点的位置后,容易找到它的直接前驱
C.在进行插入、删除操作时,能更好地保证链表不断开
D.从表中任一节点出发都能扫描到整个链表
(20)在线性表的下列存储结构中,读取元素花费时间最少的是 。
A.单链表 B.双链表
C.循环链表 D.顺序表
2.填空题
(1)在一个长度为n的线性表中的第i个元素(1≤i≤n)之前插入一个元素时,需向后移动 元素。
(2)在一个长度为n的线性表中删除第i个元素(1≤i≤n)时,需要向前移动
个元素。
(3)在双向链表中,每个节点有两个指针域,一个指向 ,另一个指向 。
(4)一个单链表中,在p所指节点之前插入s所指节点,可执行如下操作:
s->next = ;
p->next = s;
t = p->data;
p->data = ;
s->data = ;
(5)在一个单链表中,删除p所指节点时,应执行以下操作:
q = p->next;
p->data = p->next->data;
p->next = ;
free (q);
(6)带头节点的单链表head为空的条件是 。
(7)在一个单链表中,p所指节点之后插入s所指节点,应执行s->next =
和p->next = 的操作。
(8)非空的循环单链表head的尾节点(由p所指向),满足 。
3.问答题
(1)叙述线性表的定义及线性结构的基本特征。
(2)叙述线性表两种存储结构各自的优缺点。
(3)试比较分析单链表与双链表有何优缺点。
(4)试问下列程序段中执行完while循环后this指针的位置在什么地方?
①struct node *head,*this;
this=head;
while(this->next !=NULL)
this=this->next;
②struct node *head,*this;
this=head;
while(this!= NULL)
this=this->next;
4.上机操作题
(1)设计一个算法,将x插入到一个有序(从小到大排序)线性表(顺序存储结构)的适当位置上,并保持线性表的有序性。
(2)设计一个算法,从顺序表中删除自第i个元素开始的k个元素。
(3)设计一个算法,将顺序表中所有值为x的元素替换成y。
(4)有一个循环链表A,如图2-72所示。
图2-72 循环链表A示意图
试编写程序实现将ptr的节点插入到循环链表A中。
(5)有两个循环链表如图2-73所示。
图2-73 循环链表示意图
这两个链表有两个链表首A和B,试编写将A和B相连的程序。