其他类型的链表主要内容 静态链表 循环链表 双向链表

静态链表结构 利用数组定义，运算 过程中存储空间大小不变 分配节点： j = avil; avil = A[avil].link; 释放节点： A[i].link = avil; avil = i;

Linked Lists: Cursor Implementation Problem: Inserting or Deleting use new and delete to obtain and release a piece of space dynamic management If operations of getting or returning are frequently, it may indicate more time required Two resolving way: Cursor Implementation of linked lists using static memory Initially We allocate many nodes to linked into spare lists

Linked Lists: Cursor Implementation Global array of structures Address: Array index 1 2 3 4 5 6 7 8 9 10 #define SpaceSize 1000 typedef struct Node{ ElementType data; int next; }Node,CursorSpace[Spacesize];

Linked Lists: Cursor Implementation header free list head 1 2 3 4 5 6 7 8 9 10 Simulation of malloc and free Equivalent for malloc and free in cursor space array: Freelist: cells that are not in any lists Use cell 0 as a header of freelist A value of 0 for next is equivalent to NULL

Linked Lists: Cursor Implementation CursorAlloc to simulate malloc() 1 2 3 4 5 6 7 8 9 10 freelist 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 freelist 2 header 1 3 4 5 6 7 8 9 10

Linked Lists: Cursor Implementation int CursorAlloc(void) { //allocate a cell from freelist int p; p = CursorSpace[0].next; CursorSpace[0].next = CursorSpace[p].next; return p; } //end of CursorAlloc

Linked Lists: Cursor Implementation CursorFree to simulate Free() 1 2 3 4 5 6 7 8 9 10 freelist 8 header 2 c 3 b 4 e 5 g 6 f 7 d 1 9 10 1 2 3 4 5 6 7 8 9 10 freelist 4 header 2 c 3 b 5 e 8 g 6 f 7 d 1 9 10

Linked Lists: Cursor Implementation void CursorFree(int p) { //release a cell to freelist CursorSpace[p].next = CursorSpace[0].next; CursorSpace[0].next = p; } //end of CursorFree

Linked Lists: Cursor Implementation Check if the node is tail node CursorSpace[r].next != first Insert after p Status Insert(elementType e, int p) { int Tmpcell; Tmpcell = CursorAlloc(); if(Tmpcell == 0) return ERROR; CursorSpace[Tmpcell].data = e; CursorSpace[Tmpcell].next = CursorSpace[p].next; CursorSpace[p].next = Tmpcell; return OK; }

循环链表 (Circular List) 循环链表是单链表的变形。 循环链表最后一个结点的 link 指针不 为 0 (NULL)，而是指向了表的前端。 为简化操作，在循环链表中往往加入表头结点。 循环链表的特点是：只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址。

循环链表的示例 带表头结点的循环链表

循环链表类的定义 template <class Type> class CircList; template <class Type> class CircListNode { friend class CircList; public: CircListNode ( Type d = 0, CircListNode<Type> *next = NULL ) : data ( d ), link ( next ) { } //构造函数 private: Type data; CircListNode<Type> *link; }

template <class Type> class CircList { public: CircList ( Type value ); ~CircList ( ); int Length ( ) const; Boolean IsEmpty ( ) { return first→link == first; } Boolean Find ( const Type & value ); Type getData ( ) const; void Firster ( ) { current = first; } Boolean First ( ); Boolean Next ( );

插入 Boolean Prior ( ); void Insert ( const Type & value ); void Remove ( ); private: CircListNode<Type> *first, *current, *last; }; 插入

Variations of Circular Linked Lists construct an empty Circular linked list List ( const Type & value ) { last =first = new ListNode<Type>( value ); } CircList ( const Type & value ) { last =first = new CircListNode<Type>( value ); first->link = first; }

Linked Lists: Searching in a CLL template <class Type> CircListNode<Type>*List <Type>::Find ( Type value ) { //在链表中从头搜索其数据值为value的结点 CircListNode<Type> *p = first→link; //检测指针 p 指示第一个结点 while ( p != first && p→data != value ) p = p→link; return (p!=first)?p:NULL; // p 在搜索成功时返回找到的结点地址 // p 在搜索不成功时返回空值 }

双向链表 (Doubly Linked List) 双向链表是指在前驱和后继方向都能游历(遍历)的线性链表。 双向链表每个结点结构： 前驱方向   后继方向 双向链表通常采用带表头结点的循环链表形式。

结点指向 p == p→lLink→rLink == p→rLink→lLink 非空表 空表 结点指向 p == p→lLink→rLink == p→rLink→lLink

双向循环链表类的定义 template <class Type> class DblList; template <class Type> class DblNode { friend class DblList<Type>; private: Type data; //数据 DblNode<Type> *lLink, *rLink; //指针 DblNode ( Type value, //构造函数 DblNode<Type> *left, DblNode<Type> *right ) : data (value), lLink (left), rLink (right) { }

DblNode ( Type value ) : data (value), lLink (NULL), rLink (NULL) { } }; template <class Type> class DblList { public: DblLIst ( Type uniqueVal ); ~DblList ( ); int Length ( ) const; int IsEmpty ( ) { return first→rlink == first; } int Find ( const Type & target ); Type getData ( ) const;

void Firster ( ) { current = first; } int First ( ); int Next ( ); int Prior ( ); int operator ! ( ) { return current != NULL; } void Insert ( const Type & value ); void Remove ( ); private: DblNode<Type> *first, *current; };

双向循环链表的搜索算法 搜索成功 搜索不成功

template <class Type> int DblList<Type>:: Find ( const Type & target ) { //在双向循环链表中搜索含target的结点， //搜索成功返回1，否则返回0。 DblNode<Type> *p = first→rLink; while ( p != first && p→data != target ) p = p→rLink; //循链搜索 if ( p != first ) { current = p; return 1; } return 0; }

双向循环链表的插入算法 1、p→lLink = current; 2、p→rLink =current→rLink; 3、current→rLink = p; 4、current = current→rLink; 5、current→rLink→lLink = current; 3 2 5 非空表插入 空表插入 1 4

template <class Type> void DblList<Type>:: Insert ( const Type & value ) { if ( current == NULL ) //空表情形 current = first→rLink = new DblNode ( value, first, first ); else { //非空表情形 current→rLink =new DblNode ( value, current, current→rLink ); current = current→rLink; } current→rLink→lLink = current;

双向循环链表的删除算法 1、current→rLink→lLink = current→lLink; 2、current→lLink→rLink = current→rLink; 2 1

template <class Type> void DblList<Type>::Remove ( ) { if ( current != NULL ) { DblNode *temp = current; //被删结点 current = current→rLink; //下一结点 current→lLink = temp→lLink; //从链中摘下 temp→lLink→rLink = current; delete temp; //删去 if ( current == first ) if ( IsEmpty ( ) ) current = NULL; else current = current→rLink; }

其他双向循环链表的公共操作 template <class Type> DblList<Type>::DblList ( Type uniqueVal ) { //双向循环链表的构造函数, 创建表头结点 first = new DblNode<Type> ( uniqueVal ); first→rLink = first→lLink = first; current = NULL; }

template <class Type> int DblList<Type>::Length ( ) const { //求双向循环链表的长度(不计表头结点) DblNode<Type> * p = first→rLink; int count = 0; while ( p != first ) { p = p→rLink; count++; } return count; }

template <class Type> int DblList<Type>::First ( ) { if ( !IsEmpty ( ) ) //跳过表头结点的第一个 { current = first→rLink; return 1; } current = NULL; return 0; } int DblList<Type>::Next ( ) { if ( current→rLink == first ) { current = NULL; return 0; } current = current→rLink; return 1;

template <class Type> int DblList<Type>::Prior ( ) { if ( current→lLink == first ) { current = NULL; return 0; } current = current→lLink; return 1; }