第二章线性表2.ppt

{引用型操作} Status ListEmpty ( LinkList L ); //判表空 int ListLength( LinkList L ); //求表长 Status Prior( LinkList L ); //改变当前指针指向其前驱 Status Next ( LinkList L ); //改变当前指针指向其后继 ElemType GetCurElem ( LinkList L ); //返回当前指针所指数据元素 O(1) O(1) O(n) O(1) O(1) Status LocatePos( LinkList L, int i ); //改变当前指针指向第i个结点 Status LocateElem (LinkList L, ElemType e, Status (*compare)(ElemType, ElemType)); //若存在与e 满足函数compare( )判定关系的 //元素，则移动当前指针指向第1个满足条件的 //元素，并返回OK; 否则返回ERROR Status ListTraverse(LinkList L, Status(*visit)() ); //依次对L的每个元素调用函数visit() O(n) O(n) O(n) {加工型操作} Status ClearList ( LinkList L ); //重置 L 为空表 Status SetCurElem(LinkList L, ElemType e ); //更新当前指针所指数据元素 Status Append ( LinkList L, Link s ); //在表尾结点之后链接一串结点 Status InsAfter ( LinkList L, Elemtype e ); //将元素 e 插入在当前指针之后 Status DelAfter ( LinkList L, ElemType e ); //删除当前指针之后的结点 O(1) O(n) O(1) O(1) O(1) 五、其它形式的链表 最后一个结点的指针域的指针又指回第一个结点的链表。 1. 循环链表 和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”，即 P-next= =L a1 a2 … ... an p L 2. 双向链表 链表中的结点有两个指针域，其一指向直接后继，另一指向直接前趋。 b c a typedef struct DuLNode { ElemType data; // 数据域 struct DuLNode *prior; // 指向前驱的指针域 struct DuLNode *next; // 指向后继的指针域 } DuLNode, *DuLinkList; 用C语言可描述如下： prior data next 3.双向循环链表 空表 非空表 a1 a2 … ... an d 结构特性：d-next-prior=d- prior - next=d 双向链表的操作特点： 有些操作如：ListLength、GetElem、和LocateElem等仅需涉及一个方向的指针，所以和单链表相同。 “插入”和“删除”时需要同时修改两个方向上的指针。 ai-1 ai e s-next = p-next; p-next = s; s-next-prior = s; s-prior = p; p s ai-1 ai 插入 Status ListInsert_DuL(DuLinkList L, int i, ElemType e) {