《清华大学数据结构03_linklist》由会员分享，可在线阅读，更多相关《清华大学数据结构03_linklist（87页珍藏版）》请在金锄头文库上搜索。
1、n n单链表单链表 ( (Singly Linked ListSingly Linked List) )n n循环链表循环链表 ( (Circular ListCircular List) )n n多项式及其相加多项式及其相加n n双向链表双向链表 ( (Doubly Linked ListDoubly Linked List) )n n稀疏矩阵稀疏矩阵n n小结小结单链表单链表 ( (Singly Linked ListSingly Linked List) )n n特点特点uu每个元素每个元素( (表项表项) )由结点由结点( (NodeNode) )构成。构成。uu 线性结构线性结构uu
2、 结点可以不连续存储结点可以不连续存储uu 表可扩充表可扩充单链表的存储映像单链表的存储映像单链表的类定义单链表的类定义n n多个类表达一个概念多个类表达一个概念( (单链表单链表) )。uu 链表结点链表结点( (ListNodeListNode) )类类uu 链表链表( (ListList) )类类uu 链表游标链表游标( (IteratorIterator) )类类n n定义方式定义方式uu 复合方式复合方式uu 嵌套方式嵌套方式class List; /复合类定义class ListNode /链表结点类friend class List; /链表类为其友元类private:int d
3、ata; /结点数据, 整型整型ListNode *link; /结点指针;class List /链表类public:/链表公共操作private:ListNode *first, *last; /表头和表尾指针;class List /链表类定义(嵌套方式) public:/链表操作 private:class ListNode /嵌套链表结点类public:int data;ListNode *link;ListNode *first, *last; /表头和表尾指针 ;单链表中的插入与删除单链表中的插入与删除n n插入插入uu第一种情况：在第一个结点前插入第一种情况：在第一个结点前插入
4、newnodelink = first ; first = newnode；（插入前）（插入前） （插入后）（插入后）firstnewnodenewnode first( (插入前插入前) () (插入后插入后) )uu 第二种情况：在链表中间插入第二种情况：在链表中间插入newnodelink = plink;plink = newnode；newnode pnewnodepuu第三种情况：在链表末尾插入第三种情况：在链表末尾插入newnodelink = plink;plink = last = newnode；( (插入前插入前) () (插入后插入后) )newnodenewnodel
5、astplastpint List:Insert ( const int x, const int i ) /在链表第 i 个结点处插入新元素 xListNode *p = first; int k = 0;while ( p != NULL template class ListNode friend class List;Type data; /结点数据 ListNode *link; /结点链接指针 public:ListNode ( ); /链表结点构造函数ListNode ( const TypeListNode *NextNode ( ) return link; /给出当前结点的
6、下一结点地址ListNode *GetNode ( const Type/创建数据为item，指针为next的新结点void InsertAfter ( ListNode *p );/在当前结点后插入结点pListNode *RemoveAfter ( );/摘下当前结点的下一结点 ;template class List ListNode *first, *last; public:List ( const Type /构造函数List ( ); /析构函数void MakeEmpty ( ); /链表置空int Length ( ) const; /求链表长度ListNode *Find
7、( Type value );ListNode *Find ( int i );int Insert ( Type value, int i );Type *Remove ( int i );Type *Get ( int i ); ; template ListNode : ListNode ( ) : link (NULL) template ListNode: ListNode( const Type link = p; 链表结点部分操作的实现链表结点部分操作的实现template ListNode *ListNode:GetNode ( const Typenewnode link =
8、 next;return newnode; template ListNode *ListNode:RemoveAfter ( ) /摘下当前结点的下一结点ListNode *tempptr = link;if ( link = NULL ) return NULL;/没有下一结点则返回空指针link = tempptrlink; /重新链接return tempptr; /返回下一结点地址 template List : List ( ) /析构函数 ( (链表的公共操作链表的公共操作) )MakeEmpty ( ); delete first;/链表置空，再删去表头结点 template
9、void List : MakeEmpty ( ) /删去链表中除表头结点外的所有其他结点ListNode *q;while ( firstlink != NULL ) q = firstlink; firstlink = qlink;/将表头结点后第一个结点从链中摘下delete q; /释放它 last = first; /修改表尾指针 template int List:Length ( ) const /求单链表的长度ListNode *p = firstlink;/检测指针p指示第一个结点int count = 0; while ( p != NULL ) /逐个结点检测p = pl
10、ink; count+;return count; template ListNode*List : Find ( Type value ) /在链表中从头搜索其数据值为value的结点 ListNode *p = firstlink;/检测指针 p 指示第一个结点while ( p != NULL return p; / p 在搜索成功时返回找到的结点地址/ p 在搜索不成功时返回空值 template ListNode *List : Find ( int i ) /在链表中从头搜索第 i 个结点，不计头结点if ( i *p = firstlink; int j = 0;while (
11、p != NULL / p 指向链表第 i-1个结点if ( p = NULL ) return 0;ListNode *newnode = /创建结点GetNode ( value, plink );if ( plink = NULL ) last = newnode;plink = newnode; /重新链接return 1; template Type *List:Remove ( int i ) /从链表中删去第 i i 个结点ListNode *p = Find (i-1), *q;if ( p = NULL | plink = NULL )return NULL;q = plin
12、k; plink = qlink; /重新链接Type value = new Type ( qdata );if ( q = last ) last = p;delete q;return template Type *List:Get ( int i ) /提取第 i i 个结点的数据ListNode *p = Find ( i );/ p 指向链表第 i i 个结点if ( p = NULL | p = first )return NULL;else return 链表的游标类链表的游标类 ( (IteratorIterator) )n n游标类主要用于单链表的搜索。游标类主要用于单链表
13、的搜索。n n游标类的定义原则：游标类的定义原则：uu IteratorIterator类是类是ListList类和类和ListNodeListNode类的友类的友 元类。元类。uu IteratorIterator对象引用已有的对象引用已有的ListList类对象类对象 。uu IteratorIterator类有一数据成员类有一数据成员currentcurrent，记记 录对单链表最近处理到哪一个结点。录对单链表最近处理到哪一个结点。uu IteratorIterator类提供若干测试和搜索操作类提供若干测试和搜索操作表示链表的三个类的模板定义表示链表的三个类的模板定义enum Boole
14、an False, True ; template class List; template class ListIterator;template class ListNode /表结点 friend class List ; friend class ListIterator ; public: private:Type data;ListNode *link; ; template class List /链表类 public: private:ListNode *first, *last; ;template class ListIterator public:ListIterator ( const List /检查链表中当前指针是否非空Boolean NextNotNull ( );/检查链表中下一结点是否非空ListNode *First ( );/返回链表表头指针ListNode *Next ( ); /返回链表当前结点的下一个结点的地址 private:const List /引用已有链表ListNode *current
