数据结构自学记录(四):循环链表

2023-11-05 08:33| 来源: 网络整理| 查看: 265

循环链表是另一种形式的链式存储结构形式:

循环单链表:将表中尾节点的指针域改为指向表头节点,整个链表形成一个环。由此从表中任一节点出发均可找到链表中其他节点。节点类型与普通单链表节点类型相同.循环双链表:...形成两个环。节点类型与普通双链表节点类型相同.

循环单链表图示:

与非循环单链表比较：1:链表中没有空的指针域. 2:p如果为尾结点,则p->next == L;

循环双链表图示:

与非循环双链表比较：1:链表中没有空的指针域. 2:p如果为尾结点,则p->next == L;3:L->prior就可以直接找到尾结点.

习题

【例2-8】某线性表最常用的操作是在尾元素之后插入一个元素和删除第一个元素，故采用存储方式最节省运算时间。

A.单链表

B.仅有头结点指针的循环单链表

C.双链表

D.仅有尾结点指针的循环单链表

【例2-9】如果对含有n（n>1）个元素的线性表的运算只有4种，即删除第一个元素、删除尾元素、在第一个元素前面插入新元素、在尾元素的后面插入新元素，则最好使用。

A.只有尾结点指针没有头结点的循环单链表

B.只有尾结点指针没有头结点的非循环双链表

C.只有首结点指针没有尾结点指针的循环双链表

D.既有头指针也有尾指针的循环单链表

[算法设计]

要求:设计判断带头节点的循环双链表L（含两个以上的节点）是否对称相等的算法。

算法思路:1.p从左向右扫描L，q从右向左扫描L 2.若对应数据节点的data域不相等，则退出循环 3.否则继续比较，直到p与q相等或p的下一个节点为*q为止。注意数据结点为奇数和偶数的情况.

算法代码:

int isEuqal(ptrDLinkList L) { int same = 1; ptrDLinkList p = L->next; ptrDLinkList q = L->prior; while(same == 1) { if(p->data != q->data) same = 0; else if(q == p || p == q->prior) //表示所有的结点已经遍历完成 break; else { q = q->prior; p = p->next; } } return same; }

【本文地址】

公司简介

联系我们