《单链表 循环链表多项式及其相加双向链表稀疏矩阵课件》由会员分享，可在线阅读，更多相关《单链表 循环链表多项式及其相加双向链表稀疏矩阵课件（90页珍藏版）》请在金锄头文库上搜索。
1、单链表 循环链表 多项式及其相加 双向链表 稀疏矩阵,第三章 链表,一、单链表,线性表的链式表示,顺序表的优点是可以随机选取表中元素 缺点是插入删除操作复杂。 用指针将互不相连的内存结点串成的 线性表叫线性链表。 结点 node 由一个数据元素域，一个或几个 指针域组成。单链表的结点只有一个指针域。,几个结点，前一个结点的指针，指向后一个结点，就连接成一个线性链表。,线性链表的优点则是插入，删除快捷，缺点是选取复杂。,#include template class Node Node *next; /next 是下一个结点的地址 public: T data; / the data is pu
2、blic Node(const T,1. 结点类的定义,/ constructor. initialize data and / pointer members,template Node:Node(const T ,/ insert a node p after the current one,template void Node:InsertAfter(Node *p) / p points to successor of the current / node, and current node points to p. p-next = next; next = p; ,/ delete
3、 the node following current and return its address,template Node* Node:DeleteAfter(void) / save address of node to be deleted Node* tempPtr = next; / if there isnt a successor, return NULL if (next = NULL) return NULL; / current node points to successor of tempPtr. next = tempPtr-next; / return the
4、pointer to the unlinked node return tempPtr; ,2人工建立一个链表,void main(void) Node*a,*b,*c; a=new Node(a); b=new Node(b); c=new Node(c); Node*head,*p; head=new Node( ); p=head; head-InsertAfter(a); head-InsertAfter(b); head-InsertAfter(c); while(p!=NULL) cout dataNextNode( ); 测试结果：打印 c b a,3. 定义线性链表的一些操作,
5、#include node.h / allocate a node with data member item and pointer nextPtr template Node*GetNode(constT ,enum AppendNewline noNewline, addNewline;,template / print a linked list void PrintList (Node *head, AppendNewline addnl = noNewline ) / currPtr chains through the list, starting at head Node *c
6、urrPtr = head; / print the current nodes data until end of list while(currPtr != NULL) / output newline if addl = addNewline if(addnl = addNewline) cout data data NextNode( ); ,/ find an item in a linked list head; return TRUE and,/ value of previous pointer if found; otherwise return FALSE template
7、 int Find(Node *head, T / failed to locate item ,/ insert item at the front of list,template void InsertFront(Node* ,/ find rear of the list and append item,template void InsertRear(Node* ,/ delete the first node of the list,template void DeleteFront(Node* ,/ delete the first occurrence of key in th
8、e list,template void Delete (Node* ,/ insert item into the ordered list,template void InsertOrder(Node* ,/ delete all the nodes in the linked list,template void ClearList(Node * ,链表插入排序,#include #pragma hdrstop #include node.h #include nodelib.h,template void LinkSort(T a, int n), Node *ordlist = NU
9、LL, *currPtr; int i; for (i=0;i data; currPtr = currPtr-NextNode( ); ClearList(ordlist); ,/ scan the array and print its elements,void PrintArray(int a, int n) for(int i=0;i n;i+) cout ai ; ,/*void main(void), / initialized array with 10 integer values int A10 = 82,65,74,95,60,28,5,3,33,55; LinkSort
10、(A,10); / sort the array cout Sorted array: ; PrintArray(A,10); / print the array cout endl; */ #endif / NODE_LIBRARY,链表的游标类 (Iterator),游标类主要用于单链表的搜索。 游标类的定义原则： Iterator类是List类和ListNode类的友元类。 Iterator对象引用已有的List类对象。 Iterator类有一数据成员current，记录对单链表最近处理到哪一个结点。 Iterator类提供若干测试和搜索操作,表示链表的三个类的模板定义 enum Boo
11、lean 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 private: con
12、st List /当前结点指针public:,ListNode *listfirst; ?,ListIterator ( const List /返回链表当前结点的下一个结点的地址 ,链表的游标类成员函数的实现 template Boolean ListIterator : NotNull ( ) /检查链表中当前元素是否非空 if ( current != NULL ) return True; else return False; ,current,current,情况 1 返回True 情况 2 返回False,template Boolean ListIterator : NextNo
13、tNull ( ) /检查链表中下一元素是否非空 if ( current != NULL ,current,current,情况 1 返回True 情况 2 返回False,template ListNode* ListIterator : First ( ) /返回链表中第一个结点的地址 if ( list.first-link != NULL ) current = list.first-link; return current; else current = NULL; return NULL; ,list.first,current,链表中有表头结点,current,template
14、 ListNode* ListIterator : Next ( ) /返回链表中当前结点的下一个结点的地址 if ( current != NULL ,current,利用游标类 (iterator) 计算元素的和 int sum ( const List ,静态链表结构,静态链表定义,const int MaxSize = 100; /静态链表大小 template class StaticList; template class SListNode friend class StaticList; Type data; /结点数据 int link; /结点链接指针 template c
15、lass StaticList SListNode NodesMaxSize; int newptr; /当前可分配空间首地址 ,将链表空间初始化,template void StaticList : InitList ( ) Nodes0.link = -1; newptr = 1; /当前可分配空间从 1 开始建 /立带表头结点的空链表 for ( int i = 1; i MaxSize-1; i+ ) Nodesi.link = i+1; /构成空闲链接表 NodesMaxSize-1.link = -1; /链表收尾 ,在静态链表中查找具有给定值的结点,template int StaticList : Find ( Type x ) int p = Nodes0.link; /指针 p 指向链表第一个结点 while ( p != -1 ) if ( Nodesp.data != x) p = Nodesp.link; else break; /逐个结点检测查找具有给定值的结点 return p; ,在静态链表的表尾追加一个新结点,template int StaticList : Append ( Type x ) if ( newptr = -
