单链表循环链表多项式及其相加双向链表稀疏矩阵

《单链表循环链表多项式及其相加双向链表稀疏矩阵》由会员分享，可在线阅读，更多相关《单链表循环链表多项式及其相加双向链表稀疏矩阵（90页珍藏版）》请在装配图网上搜索。

1、 一、单链表一、单链表 线性表的链式表示线性表的链式表示顺序表的优点是可以随机选取表中元素缺点是插入删除操作复杂。用指针将互不相连的内存结点串成的线性表叫线性链表线性链表。结点结点 node 由一个数据元素域，一个或几个指针域组成。单链表的结点只有一个指针域。 几个结点，前一个结点的指针几个结点，前一个结点的指针，指向后一个结点，就连接成，指向后一个结点，就连接成一个线性链表。一个线性链表。线性链表的优点则是插入，删除快捷，缺点是选取复杂。 #include stdlib.h#include template class Node Node *next; /next 是下一个结点的地址 pub

2、lic: T data; / the data is public NodeNode(const (const T T& & itemitem, , NodeNode * * ptrnext= ptrnext=NULLNULL);); / list modification methods void InsertAfter(Node *p); Node * DeleteAfter(void); / obtain the address of the next node Node *NextNode(void) const;1. 结点类的定义结点类的定义 / constructor. initi

3、alize data and / constructor. initialize data and / pointer members/ pointer memberstemplate class template NodeNode :NodeNode(const (const T T& & itemitem, , Node Node * * ptrnextptrnext) : ) : datadata( (itemitem), ), nextnext( (ptrnextptrnext) )） / return value of private member next/ return valu

4、e of private member nexttemplate class template NodeNode * * NodeNode :NextNodeNextNode(void) const(void) const return return nextnext; ; / insert a node p after the current one/ insert a node p after the current onetemplate class template void void NodeNode :InsertAfterInsertAfter( (NodeNode * *p)p

5、) / p points to successor of the current / p points to successor of the current / node, and current node points to p. / node, and current node points to p. p p-nextnext = = nextnext; ; nextnext = = p p; ; / delete the node following current and return its address/ delete the node following current a

6、nd return its addresstemplate class template NodeNode* * NodeNode :DeleteAfterDeleteAfter(void)(void) / save address of node to be deleted/ save address of node to be deleted NodeNode * * tempPtrtempPtr = = nextnext; ; / if there isnt a successor, return NULL/ if there isnt a successor, return NULL

7、if ( if (nextnext = = NULLNULL) ) return return NULLNULL; ; / current node points to successor of / current node points to successor of tempPtr.tempPtr. nextnext = = tempPtrtempPtr-nextnext; ; / return the pointer to the unlinked node/ return the pointer to the unlinked node return return tempPtrtem

8、pPtr; ; 2人工建立一个链表人工建立一个链表void main(void) Node*a,*b,*c; a=new Node(a); b = n e w N o d e ( b ) ; c = n e w Node(c); Node*head,*p; head=new Node( ); p=head; head-InsertAfter(a); head-InsertAfter(b); head-InsertAfter(c); while(p!=NULL) cout dataNextNode( ); l测试结果：打印 c b a 3. 定义线性链表的一些操作定义线性链表的一些操作#incl

9、ude node.h/ allocate a node with data member item and pointer nextPtrtemplate Node*GetNode(constT&item,Node*nextPtr = NULL) Node *newNode; / allocate memory while passing item and NextPtr to / constructor. terminate program if allocation fails newNode = new Node(item, nextPtr); if (newNode = NULL) c

10、err Memory allocation failure! endl; exit(1); return newNode; enum AppendNewline noNewline, addNewline;template / print a linked listvoid PrintList (Node *head, A p p e n d N e w l i n e a d d n l = noNewline ) / currPtr chains through the list, starting at head Node *currPtr = head; / print the cur

11、rent nodes data until end of list while(currPtr != NULL) / output newline if addl = addNewline if(addnl = addNewline) cout data endl; else cout data NextNode( ); / find an item in a linked list head; return TRUE and/ value of previous pointer if found; otherwise return FALSEtemplate int Find(Node *h

12、ead, T& item, Node* &prevPtr) Node *currPtr = head; / begin traversal at first node prevPtr = NULL; / cycle through the list until end of list while(currPtr != NULL) if (currPtr-data = item) item = currPtr-data; return 1; prevPtr = currPtr; currPtr = currPtr-NextNode( ); return 0; / failed to locate

13、 item / insert item at the front of listtemplate void InsertFront(Node* & head, T item) / allocate new node so it points to original list head / update the list head head = GetNode(item,head); / find rear of the list and append itemtemplate void InsertRear(Node* & head, const T& item) Node *newNode,

14、 *currPtr = head; if (currPtr = NULL) / if list is empty, insert item at the front InsertFront(head,item); else / find the node whose pointer is NULL while(currPtr-NextNode( ) != NULL) currPtr = currPtr-NextNode( ); / allocate node and insert at rear (after currPtr) newNode = GetNode(item); currPtr-

15、InsertAfter(newNode); / delete the first node of the listtemplate void DeleteFront(Node* & head) / save the address of node to be deleted Node *p = head; / make sure list is not empty if (head != NULL) / move head to second node and delete original head = head-NextNode( ); delete p; / delete the fir

16、st occurrence of key in the listtemplate void Delete (Node* & head, T key) Node *currPtr = head, *prevPtr = NULL; if (currPtr = NULL) return; while (currPtr != NULL & currPtr-data != key) prevPtr = currPtr; currPtr = currPtr-NextNode( ); if (currPtr != NULL) if(prevPtr = NULL) head = head-NextNode()

17、; else prevPtr-DeleteAfter(); delete currPtr; / insert item into the ordered listtemplate void InsertOrder(Node* & head, T item) Node *currPtr, *prevPtr, *newNode; prevPtr = NULL; currPtr = head; while (currPtr != NULL) if (item data) break; prevPtr = currPtr; currPtr = currPtr-NextNode( ); if (prev

18、Ptr = NULL) InsertFront(head,item); else newNode = GetNode(item); prevPtr-InsertAfter(newNode); / delete all the nodes in the linked listtemplate void ClearList(Node * &head) Node *currPtr, *nextPtr; currPtr = head; while(currPtr != NULL) nextPtr = currPtr-NextNode( ); delete currPtr; currPtr = next

19、Ptr; head = NULL; 链表插入排序链表插入排序#include #pragma hdrstop#include node.h#include nodelib.h template void LinkSort(T a, int n) Node *ordlist = NULL, *currPtr; int i; for (i=0;i data; currPtr = currPtr-NextNode( ); ClearList(ordlist); / scan the array and print its elementsvoid PrintArray(int a, int n) f

20、or(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(A,10); / sort the array cout Sorted array: ; PrintArray(A,10); / print the array cout endl;*/ #endif / NODE_LIBRARY 链表的游标类链表的游标类 (Iterator)(Iterator)n游标类主要用于单链表的搜

21、索。游标类主要用于单链表的搜索。n游标类的定义原则：游标类的定义原则：u IteratorIterator类是类是ListList类和类和ListNodeListNode类的友元类。类的友元类。u IteratorIterator对象引用已有的对象引用已有的ListList类对象。类对象。u IteratorIterator类有一数据成员类有一数据成员currentcurrent，记录对单链表最，记录对单链表最近处理到哪一个结点。近处理到哪一个结点。u IteratorIterator类提供若干测试和搜索操作类提供若干测试和搜索操作 enum Boolean False, True ;temp

22、late 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: const List & list; /引用已有链表 ListNod

23、e *current; /当前结点指针public: ListNode *listfirst; ? ListIterator ( const List & l ) : list ( l ), current ( l.first ) /构造函数: 引用链表 ListNode * Firster ( ) current = list.first; return current; /当前指针置于表头, 返回表头结点地址 Boolean NotNull ( ); /检查当前指针空否 Boolean NextNotNull ( ); /检查链表中下一结点是否非空 ListNode *First ( );

24、 /返回第一个结点的地址 ListNode *Next ( ); /返回链表当前结点的下一个结点的地址 template Boolean ListIterator : NotNull ( ) /检查链表中当前元素是否非空 if ( current != NULL ) return True; else return False;currentcurrent情况情况 1 返回返回True 情况情况 2 返回返回False template Boolean ListIterator : NextNotNull ( ) /检查链表中下一元素是否非空 if ( current != NULL & cu

25、rrent-link != NULL ) return True; else return False; currentcurrent情况情况 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.firstcurrent链表中有表头链表中有表头结点结点

26、 currenttemplate ListNode* ListIterator : Next ( ) /返回链表中当前结点的下一个结点的地址 if ( current != NULL & current-link != NULL ) current = current-link; return current; else current = NULL; return NULL; current int sum ( const List &L ) ListIterator li (L); /定义游标对象, current 指向 li.first if (li. First( ) =NULL) r

27、eturn 0; /链表为空时返回0 int retval =current-data; /第一个元素 while ( li.nextNotNull ( ) ) /链表未扫描完 retval += li.Next( )-data; /累加 return retval; const int MaxSize = 100; /静态链表大小template class StaticList;template class SListNode friend class StaticList; Type data; /结点数据 int link; /结点链接指针template class StaticLi

28、st 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

29、.link; /指针 p 指向链表第一个结点 while ( p != -1 ) if ( Nodesp.data != x) p = Nodesp.link; else break; /逐个结点检测查找具有给定值的结点 return p; template int StaticList : Append ( Type x ) if ( newptr = -1 ) return 0; /追加失败 int q = newptr; /分配结点 newptr = Nodesnewptr.link; Nodesq.data = x; Nodesq.link = -1; int p = 0; /查找表尾

30、 while ( Nodesp.link != -1 ) p = Nodesp.link; Nodesp.link = q; /追加 return 1; template int StaticList : Locate ( int i ) if ( i 0 ) return -1; /参数不合理 if ( i = 0 ) return 0; int j = 0, p = Nodes0.link; while ( p != -1 & j i ) p = Nodesp.link; j+; /循链查找第 i 号结点 return p; template int StaticList : Insert

31、 ( int i, Type x ) int p = Locate ( i-1 ); if ( p = -1 ) return 0; /找不到结点 int q = newptr; /分配结点 newptr = Nodesnewptr.link; Nodesq.data = x; Nodesq.link = Nodesp.link; /链入 Nodesp.link = q; return 1; template int StaticList : Remove ( int i ) int p = Locate ( i-1 ); if ( p = -1 ) return 0; /找不到结点 int

32、q = Nodesp.link; /第 i 号结点 Nodesp.link = Nodesq.link; Nodesq.link = newptr; /释放 newptr = q; return 1; a0a1a2an-1firstan-1firsta1a0first( (空表空表) )( (非空表非空表) ) template class CircList;template class CircListNode friend class CircList ;public: CircListNode ( Type d = 0, CircListNode *next = NULL ) : dat

33、a ( d ), link ( next ) /构造函数private: Type data; /结点数据 CircListNode *link; /链接指针 template class CircList private: CircListNode *first, *current, *last; /链表的表头指针、当前指针和表尾指针public: CircList ( Type value ); CircList ( ); int Length ( ) const; Boolean IsEmpty ( ) return first-link = first; Boolean Find (

34、const Type & value ); Type getData ( ) const; void Firster ( ) current = first; Boolean First ( ); Boolean Next ( ); Boolean Prior ( ); void Insert ( const Type & value ); void Remove ( ); 搜索成功搜索成功搜索不成功搜索不成功firstfirst3131484815155757搜索搜索15 搜索搜索25 current current currentcurrent current current curren

35、tcurrent template CircListNode * CircList : Find ( Type value ) /在链表中从头搜索其数据值为value的结点 current = first-link; /检测指针 current 指示第一个结点 while ( current != first & current-data != value ) current = current-link; return current; #include #include “CircList.h”Template void CircList : Josephus ( int n, int m

36、 ) First ( ); for ( int i = 0; i n-1; i+ ) /执行执行n- -1次次 for ( int j = 0; j m-1; j+ ) Next ( ); cout “出列的人是出列的人是” getData ( ) endl; /数数m- -1个人个人 Remove ( ); /删去删去 void main ( ) CircList clist; int n, m; cout n m; for ( int i = 1; i = n; i+ ) clist.insert (i); /形成约瑟夫环 clist.Josephus (n, m); /解决约瑟夫问题 i

37、n0iinn2210nxc xc xcxcc(x)PPn(x) 。u u coef exp link Data Term struct Term /多项式结点定义 float coef; /系数 int exp; /指数 Term ( float c, int e ) coef = c; exp = e; ; class Polynomial /多项式类的定义 List poly; /构造函数 friend Polynomial & operator + ( Polynomial &); /加法; AH = 1 - 3x6 + 7x12BH = - x4 + 3x6 - 9x10 + 8x14

38、AH.firstBH.first CH.first 1 01 0-1 4-1 4-3 63 6-9 10-9 107 127 128 148 14 friend Polynomial& operator + ( Polynomial& bh ) /两个带头结点的按升幂排列的多项式相加，/返回结果多项式链表的表头指针，结果不/另外占用存储, 覆盖ah和bh链表 ListNode *pa, *pb, *pc, *p; Term a, b; pc = poly.first; /结果存放指针 p = bh.poly.first; pa = poly.first-link; /多项式检测指针 pb =

39、bh.poly.first-link; /多项式检测指针 delete p; /删去bh的表头结点 while ( pa != NULL & pb != NULL ) a = pa-data; b = pb-data; switch ( compare ( a.exp, b.exp ) ) case = :/pa-exp = pb-exp a.coef = a.coef + b.coef;/系数相加 p = pb; pb = pb-link; delete p;/删去原pb所指结点 if ( abs(a.coef ) link; delete p; /相加为零, 该项不要 else /相加不为

40、零, 加入ch链 pa-data = a; pc-link = pa; pc = pa; pa = pa-link; break; case : /pa-exp pb-exp pc-link = pb; pc = pb; pb = pb-link; break; case exp exp pc-link = pa; pc = pa; pa = pa-link; if ( pa-link ) pc-link = pa; else pc-link = pb; /剩余部分链入ch链 return this; p-lLinkp-rLinkplLinkrLinkfirstfirst template c

41、lass DblList;template class DblNode friend class DblList;private: Type data; /数据 DblNode * lLink, * rLink; /指针public: DblNode (Type value=0, DblNode * left, DblNode * right ) : data (value), lLink (left), rLink (right) DblNode ( Type value ) : data (value), lLink (NULL), rLink (NULL) DblNode * getLe

42、ftLink ( ) return llink; /取得左链指针值 DblNode * getRightLink ( ) return rlink; /取得右链指针值 Type getData ( ) return data; void setLeftLink ( DblNode*Left ) llink = Left; /修改左链指针值 void setRightLink ( DblNode*Right ) rlink = Right; /修改左链指针值 void setData ( Type value ) data = value; ;template class DblList pri

43、vate: DblNode * first, * current;public: DblLIst (); /构造函数 DblList ( ); /析构函数 int Length ( ) const; /计算长度 int IsEmpty ( ) /判链表空否 return first-rlink = first; int Find ( const Type& target ); void Firster ( ) current = first; /当前指针置于表头结点。 int First ( ) ; /当前指针置于第一个结点 int Next ( ); /当前指针置于后继结点 int Prio

44、r ( ); /当前指针置于前驱结点 void Insert ( const Type& value );/插入一个包含有值value的新结点 void Remove ( );/删除当前结点; template DblList : DblList () /构造函数: 建立双向循环链表的表头结点 first = current = new DblNode (); if (first = NULL ) cerr rLink = first-lLink = first; /表头结点的链指针指向自己 template int DblList : Length ( ) const /计算带表头结点的双向

45、循环链表的长度 DblNode * p = first-rLink; int count = 0; while ( p != first ) p = p-rLink; count+; return count; 搜索成功搜索成功搜索不成功搜索不成功firstfirst3131484815155757搜索搜索15 搜索搜索25 template int DblList :Find ( const Type& target ) /在双向循环链表中搜索含target的结点, 若/找到, 则返回1, 同时current指针指向该结点, /否则函数返回0。 current = first-rLink;

46、while ( current != first & current-data != target ) current = current-rLink; if ( current != first ) return 1; else return 0; firstfirst31481525currentcurrent31482515newnode-lLink = current;newnode-rLink = current-rLink;current-rLink = newnode;current = current-rLink;current-rLink-lLink = current; f

47、irst25currentcurrent25newnode-lLink = current;newnode-rLink = current-rLink; ( = first )current-rLink = newnode;current = current-rLink;current-rLink-lLink = current; ( first -lLink = current ) first template void DblList :Insert ( const Type & value ) if ( first-rlink = first ) /空表情形 current = firs

48、t-rLink = new DblNode ( value, first, first ); else /非空表情形 current-rLink = new DblNode ( value, current, current-rLink ); current = current-rLink; current-rLink-lLink = current; firstfirst314815current3115currentcurrent-rLink-lLink = current-lLink; current-lLink-rLink = current-rLink; firstfirst31cu

49、rrentcurrentcurrent-rLink-lLink = current-lLink; current-lLink-rLink = current-rLink; template void DblList : Remove ( ) if ( current != first ) DblNode *temp = current; /被删结点 current = current-rLink; /当前指针进到下一结点 current-lLink = temp-lLink; /将被删结点从链中摘下 temp-lLink-rLink = current; delete temp; /删去 te

50、mplate int DblList : First ( ) if ( !IsEmpty ( ) ) current = first-rLink; return 1; current = first; return 0; template int DblList : Next ( ) if ( current-rLink = first ) /最后结点 current = first -rLink; return 0; current = current-rLink; return 1;template int DblList : Prior ( ) if ( current-lLink =

51、first ) /第一个结点 current = first -lLink; return 0; current = current-lLink; return 1; headdownnextright(a) 表头结点表头结点 (b) 非零元素结点非零元素结点rightvaluedownrowcolaijFalseij(c) 建立建立aij结点结点 head enum Boolean False, True ;struct Triple int row, col; float value; ;class Matrix;class MatrixNode /矩阵结点定义friend class M

52、atrix;friend istream &operator ( istream &, Matrix & ); /矩阵输入重载函数private: MatrixNode *down, *right;/列/行链指针 Boolean head; /结点类型 Union Triple triple; MatrixNode *next; /矩阵元素结点(False)或链头结点(True) MatrixNode ( Boolean, Triple* ); /结点构造函数MatrixNode:MatrixNode ( Boolean b, Triple *t ) /矩阵结点构造函数 head = b; /

53、结点类型 if ( b ) right = next = this; else triple = *t; typedef MatrixNode *MatrixNodePtr;/一个指针数组, 用于建立稀疏矩阵class Matrix friend istream& operator ( istream &, Matrix & ); /矩阵输入矩阵输入public: Matrix ( ); /析构函数析构函数private: MatrixNode *headnode; /稀疏矩阵的表稀疏矩阵的表头头; istream & operator ( istream & is, Matrix & mat

54、rix ) Triple s; int p; is s.row s.col s.value; /输入矩阵的行数, 列数和非零元素个数 if ( s.row s.col ) p = s.row; else p = s.col; /取行、列数大者 matrix.headnode = /整个矩阵表头结整个矩阵表头结点点 new MatrixNode ( False, &s ); if ( !p ) /零矩阵时 matrix.headnode-right = matrix.headnode; return is; MatrixNodePtr *H = new MatrixNodePtr ( p );

55、/建立表头指针数组, 指向各链表的表头 for ( int i = 0; i p; i+ ) Hi = new MatrixNode ( True, 0 ); int CurrentRow = 0; MatrixNode *last = H0; /当前行最后结点 for ( i = 0; i t.row t.col t.value; /输入非零元素的三元组 if ( t.row CurrentRow ) /如果行号大于当前行,闭合当前行 last-right = HCurrentRow; CurrentRow = t.row; last = HCurrentRow; last = last-r

56、ight = /链入当前行 new MatrixNode ( False, &t ); Ht.col-next = Ht.col-next-down = last; /链入列链表 last-right = HCurrentRow; /闭合最后一行 /闭合各列链表 for ( i = 0; i next-down = Hi; /链接所有表头结点 for ( i = 0; i next =Hi+1; Hp-1-next = matrix.headnode; matrix.headnode-right = H0; delete H; return is; Matrix : Matrix ( ) if ( headnode = NULL ) return; MatrixNode *x = headnode-right, *y; headnode-right = av; av = headnode; while ( x != headnode ) y = x-right; x-right = av; av = y; x = x-next; headnode = NULL;