Ch2.3线性表 -链式存储 - 作业答案.pptVIP

说明： 第一个生成的结点是开始结点，将开始结点插入到空表中，是在当前链表的第一个位置上插入，该位置上的插入操作和链表中其它位置上的插入操作处理是不一样的，原因是开始结点的位置是存放在头指针（指针变量）中，而其余结点的位置是在其前趋结点的指针域中。算法中的第一个if语句就是用来对第一个位置上的插入操作做特殊处理。 算法中的第二个if语句的作用是为了分别处理空表和非空表两种不同的情况，若读入的第一个字符就是结束标志符，则链表head是空表，尾指针r亦为空，结点*r不存在；否则链表head非空，最后一个尾结点*r是终端结点，应将其指针域置空。 例题:设单链表的长度为n，要查找表中第i个结点，仅当1≦i≦n时，i的值是合法的。但有时需要找头结点的位置，故我们将头结点看做是第0 个结点，其算法如下： 四、删除运算 删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点a i-1的指针域next中，所以我们必须首先找到a i-1的存储位置p。然后令p–next指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间，将其归还给“存储池”。此过程为： ⑴若线性表需频繁查找却很少进行插入和删除操作，或其操作和元素在表中的位置密切相关时，宜采用顺序表作为存储结构；若线性表需频繁插入和删除时，则宜采用单链表做存储结构。 ⑵当线性表中元素个数变化较大或者未知时，最好使用单链表实现；而如果用户事先知道线性表的大致长度，使用顺序表的空间效率会更高。 由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或p—next是否为空，而是判断它们是否等于某一指定指针，如头指什或尾指针等。 typedef struct dlistnode{ datatype data; struc dlistnode *prior，*next; }dlistnode; typedef dlistnode * dlinklist; dlinklist head; 设指针p指向某一结点，则双向链表结构的对称性可用下式描述： (p—prior)—next=p=(p—next)—prior 即结点*p的存储位置既存放在其前趋结点*(p—prior)的直接后继指针域中，也存放 在它的后继结点*(p—next)的直接前趋指针域中。 课堂练习 4. 线性表采用链接存储时，其地址（ ）。 A 必须是连续的 B 部分地址必须是连续的 C 一定是不连续的 D 连续与否均可以 【解答】D 5. 链表不具有的特点是（ ）。 A 可随机访问任一元素 B 插入、删除不需要移动元素 C 不必事先估计存储空间 D 所需空间与线性表长度成正比 【解答】A 课堂练习 6.若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用（ ）存储方法最节省时间。 A 单链表 B 带头指针的单循环链表 C 双链表 D 带尾指针的单循环链表 【解答】D 7.使用双链表存储线性表，其优点是可以（ ）。 A 提高查找速度 B 更方便数据的插入和删除 C 节约存储空间 D 很快回收存储空间 【解答】B 课堂练习 8.在一个单链表中，已知q所指结点是p所指结点的直接前驱，若在q和p之间插入s所指结点，则执行（ ）操作。 A s-next=p-next; p-next=s; B q-next=s; s-next=p; C p-next=s-next; s-next=p; D p-next=s; s-next=q; 【解答】B 课堂练习 9.在由尾指针rear指示的单循环链表中，在表尾插入一个结点s的操作序列是（ ）；删除开始结点的操作序列为（ ）。 【解答】s-next =rear-next; rear-next =s; rear =s。 q=rear-next-next; rear-next-next=q-next; delete q。 课堂练习 10 在循环双链表的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-n