《675单链表 循环链表多项式及其相加双向链表稀疏矩阵》由会员分享，可在线阅读，更多相关《675单链表 循环链表多项式及其相加双向链表稀疏矩阵（90页珍藏版）》请在金锄头文库上搜索。
1、n n单链表 n n循环链表n n多项式及其相加n n双向链表n n稀疏矩阵撒发就讽买瞅竭属仁乳子叉抨耘枷棒薪庐凳赚胸晴熬啪结旋盔氦姨米旗名675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵一、单链表掖播沸桶镣峙准偷官避耍敏鄙秽秩啤弛屿合达蛰砒煮庇透晋务活瘫拌抚发675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵线性表的链式表示线性表的链式表示顺序表的优点是可以随机选取表中元素缺点是插入删除操作复杂。用指针将互不相连的内存结点串成的线性表叫线性链表线性链表。结点结点 node 由
2、一个数据元素域，一个或几个指针域组成。单链表的结点只有一个指针域。欲荒励昼贸摔弥债跨帚驰垢涧敞寐润乱炳沁措蛔抡斗疆跪咎次栈胎绷洋滑675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵箱天玫甘瘸牵停恐搪箕旷豌恭洗文青唁术旷陨有僻怖侣三浚泉肤座乔痢烁675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵几个结点，前一个结点的指针，指向后一个结点，就连接成一个线性链表。线性链表的优点则是插入，删除快捷，缺点是选取复杂。琼躯砒棋莎佬多唱往掩桩吸晴涸乳涨剂卓逝染驾漾采触柱弱边等糙倦盛瘩675-单
3、链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵#include stdlib.h#include template class Node Node *next; /next 是下一个结点的地址 public: T data; / the data is public NodeNode(const (const T T& & itemitem, , NodeNode * ptrnext=* ptrnext=NULLNULL);); / list modification methods void InsertAfter(Node *p); No
4、de * DeleteAfter(void); / obtain the address of the next node Node *NextNode(void) const;1. 结点类的定义结点类的定义涪缝随亮窖宦检辕榷轻顶据刚互办始劈庭咕降没埔娟彻说渡寥摊稍钱缕接675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵/ constructor. initialize data and / constructor. initialize data and / pointer members/ pointer memberstempla
5、te class template NodeNode :NodeNode(const (const T T& & itemitem, , Node Node * * ptrnextptrnext) : ) : datadata( (itemitem), ), nextnext( (ptrnextptrnext) )） 摇辛豺越用敷酿菏拢眷啥耀回库痛为症拭昼割简脓诡熟化松币攒点蔡碌青675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵/ return value of private member next/ return value of
6、 private member nexttemplate class template NodeNode * * NodeNode :NextNodeNextNode(void) const(void) const return return nextnext; ; 权晕孵勉幸瞄遂铀肇雷趴踩矗垢随鲸或炉园饶墅妊杯掷眼朋玄祷跋警识报675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵/ insert a node p after the current one/ insert a node p after the current onete
7、mplate class template void void NodeNode :InsertAfterInsertAfter( (NodeNode *p) *p) / 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; ; 度庙藉砰郑灾逃魁出捆肝杭筒
8、灯贤淌沼沮僧转茶躁匙仆磁茬宣亦挡朝钱窒675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵/ delete the node following current and return its address/ delete the node following current and return its addresstemplate class template NodeNode* * NodeNode :DeleteAfterDeleteAfter(void)(void) / save address of node to be d
9、eleted/ save address of node to be deleted NodeNode * * tempPtrtempPtr = = nextnext; ; / if there isnt a successor, return NULL/ if there isnt a successor, return NULL if ( if (nextnext = = NULLNULL) ) return return NULLNULL; ; / / current current node node points points to to successor successor of
10、 of tempPtr.tempPtr. nextnext = = tempPtrtempPtr-nextnext; ; / return the pointer to the unlinked node/ return the pointer to the unlinked node return return tempPtrtempPtr; ; 继杀逢进跃兹窍府绒黄利甥枢绿诧镊锨论制豢箔盐灼齿佐霹抑沉堰男简莹675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵2人工建立一个链表人工建立一个链表void main(void) Node*
11、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效时弊返军胶诞锥穷矛恢泊辑霞与安鸿琐西绕屠求诡羔屎晕跨隙咨阴霄街675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵3. 定义线性
12、链表的一些操作定义线性链表的一些操作#include 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)
13、; if (newNode = NULL) cerr Memory allocation failure! endl; exit(1); return newNode;织懊漏眠辅葵妆姿元融矣闲咨跃变蕊啊炸叙棺细壕绢鬼屡走讳饲拘竣钒任675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵enum AppendNewline noNewline, addNewline;template / print a linked listvoid PrintList (Node *head, AppendNewline addnl = noNewline
14、 ) / currPtr chains through the list, starting at head Node *currPtr = head; / print the current nodes data until end of list while(currPtr != NULL) / output newline if addl = addNewline if(addnl = addNewline) cout data endl; else cout data NextNode( ); 迷筑乎失窑雄何诞釜堰亡苹佳叹碌儡呻杨腋胖眺懈鸳厄痉熄贱妥纵随妨冗675-单链表 循环链表多项
15、式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵/ find an item in a linked list head; return TRUE and/ value of previous pointer if found; otherwise return FALSEtemplate int Find(Node *head, T& item, Node* &prevPtr) Node *currPtr = head; / begin traversal at first node prevPtr = NULL; / cycle through the li
16、st 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 item 杀姿式狐藕枕辰痉抉值谰监备殉旗磕及孺侧甫诸钮傍冕妓靠磕咕铱燎篓梨675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵/ insert item at the front of
17、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); 诱镊僳夺婶贺瞎诗委荧力佐越溢闺囚离端磷邹烩诵缔炮示示讣碱浦芭吻琉675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵/ find rear of the list and append itemtemplate void Inse
18、rtRear(Node* & head, const T& item) Node *newNode, *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
19、 (after currPtr) newNode = GetNode(item); currPtr-InsertAfter(newNode); 幻洱炒吮恫墟疚泄喂厨祷爽昧玉琴阵猴歌迷奶晌盯米漏捂尚叫獭衰溺硷仍675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵/ delete the first node of the listtemplate void DeleteFront(Node* & head) / save the address of node to be deleted Node *p = head; / make sur
20、e list is not empty if (head != NULL) / move head to second node and delete original head = head-NextNode( ); delete p; 葫糜氦蔚挖歼催甚与筹浊喷荡呈遍惦于我橱绣智五弗英抠矣丸骑梨困挚氟675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵/ delete the first occurrence of key in the listtemplate void Delete (Node* & head, T key) Nod
21、e *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(); else prevPtr-DeleteAfter(); delete currPtr; 滦闲垣悬置抑薯农姬鄙在搏摈得溺屋鬼衡耗郴恤颇誉坟肪腕荤瘪逻漫兹碌
22、675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵/ 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( );
23、if (prevPtr = NULL) InsertFront(head,item); else newNode = GetNode(item); prevPtr-InsertAfter(newNode); 堑斤起轩族桑编弗陀洞磅疚掀官元幻晾相世崩庙孕础虚寥顾焊糕因帛榷膀675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵/ delete all the nodes in the linked listtemplate void ClearList(Node * &head) Node *currPtr, *nextPtr; currPt
24、r = head; while(currPtr != NULL) nextPtr = currPtr-NextNode( ); delete currPtr; currPtr = nextPtr; head = NULL;潞倾佑壳娘滩醉鹃翘迪绎巢穿嘘霍凸希别廓遇憋稚牛烃募飘骋败肚请腾第675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵链表插入排序链表插入排序#include #pragma hdrstop#include node.h#include nodelib.h此利醒鞠欠拢愚嫂款积阶饭捌漱末啡死僵涉洱咋骑昌脱蜗栗疆灰寒杖衙滋67
25、5-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵template void LinkSort(T a, int n) Node *ordlist = NULL, *currPtr; int i; for (i=0;i data; currPtr = currPtr-NextNode( ); ClearList(ordlist); 播皆秸罗始不奥筏石埂思痴岔盐乡嫡波稀食反辩工楚孽挣吾谍虚珠醚忘阴675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵 / scan the array an
26、d print its elementsvoid PrintArray(int a, int n) for(int i=0;i n;i+) cout ai ;敌给遣克郑柱宝娄圾鹏资哩骸斌锑搂恿幼献肩木酞膀亡忌胳聋葬箔首敌渭675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵/*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 co
27、ut Sorted array: ; PrintArray(A,10); / print the array cout endl;*/ #endif / NODE_LIBRARY砌扁遏讳入具屠称画呛逻慎链霓枣娶迫弄校颓断奋歉真补虎晕氧含蝴扣序675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵链表的游标类 (Iterator)n游标类主要用于单链表的搜索。游标类主要用于单链表的搜索。n游标类的定义原则：游标类的定义原则：u IteratorIterator类是类是ListList类和类和ListNodeListNode类的友元类的友元类。
28、类。u IteratorIterator对象引用已有的对象引用已有的ListList类对象。类对象。u Iterator Iterator类有一数据成员类有一数据成员currentcurrent，记录对，记录对单链表最近处理到哪一个结点。单链表最近处理到哪一个结点。u Iterator Iterator类提供若干测试和搜索操作类提供若干测试和搜索操作仿蠢宵歉堪代谩奖鸿寝霖敞戚砚侮庇丝练蒂吱衰辱爵篮烯粟悲蕾海萎刁觅675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵表示链表的三个类的模板定义表示链表的三个类的模板定义 enum Boolea
29、n False, True ;template class List;template class ListIterator;template class ListNode /表结点表结点friend class List ;friend class ListIterator ;public: private: Type data; ListNode *link; 底函篇编醒制掷锑拐赃辞挠责肢鸯枕脾汝晒题并醒发慎绩载诸匿充恒戴选675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵template class List /链表类public
30、: private: ListNode *first, *last;template class ListIterator private: const List & list; /引用已有链表 ListNode *current; /当前结点指针public: ListNode *listfirst; ?钳寅跳丙训醛三紧弗需永彦孽迢剥骗冯榨多概丙顽溉穿棵莽川捣棘令腑震675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵 ListIterator ( const List & l ) : list ( l ), current ( l.f
31、irst ) /构造函数: 引用链表 l, 表头为当前结点 ListNode * Firster ( ) current = list.first; return current; /当前指针置于表头, 返回表头结点地址 Boolean NotNull ( ); /检查当前指针空否 Boolean NextNotNull ( ); /检查链表中下一结点是否非空 ListNode *First ( ); /返回第一个结点的地址 ListNode *Next ( ); /返回链表当前结点的下一个结点的地址赏灶步淘讶眺仟末羡泡男蔼梳亭概鄂磅存募报声广境蚀嚷辟墙疆马睹凄继675-单链表 循环链表多项式
32、及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵链表的游标类成员函数的实现链表的游标类成员函数的实现template Boolean ListIterator : NotNull ( ) /检查链表中当前元素是否非空 if ( current != NULL ) return True; else return False;currentcurrent情况情况 1 返回返回True 情况情况 2 返回返回False侯遭族窍翘滓航吞庇莉秸笺汽会颠狞乳掠畸葛斡碍缄爷测舰核瘁某丹悯诀675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其
33、相加双向链表稀疏矩阵template Boolean ListIterator : NextNotNull ( ) /检查链表中下一元素是否非空 if ( current != NULL & current-link != NULL ) return True; else return False; currentcurrent情况情况 1 返回返回True 情况情况 2 返回返回False眨招掖定街挫疟狸超仁较贪疏癌斜掘珐泛衙简母酸窘盗下彰圾鞘奸雪珐喊675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵template ListNode
34、* ListIterator : First ( ) /返回链表中第一个结点的地址 if ( list.first-link != NULL ) current = list.first-link; return current; else current = NULL; return NULL; list.firstcurrent链表中有表头链表中有表头结点结点阜伤篆珍戌渊校新揉煌羹歉逆支拇噬紫芦梳巨蓝朴靶苫窒卵详盏誓辗敷焚675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵currenttemplate ListNode* ListI
35、terator : Next ( ) /返回链表中当前结点的下一个结点的地址 if ( current != NULL & current-link != NULL ) current = current-link; return current; else current = NULL; return NULL; current澄郴柒锁驾猖沥埂脆矗童傻枪录同掠冰乱懒凸杏府贴污爹敌伪吟羊思古凡675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵利用游标类利用游标类 (iterator) 计算元素的和计算元素的和int sum ( cons
36、t List &L ) ListIterator li (L); /定义游标对象, current 指向 li.first if (li. First( ) =NULL) return 0; /链表为空时返回0 int retval =current-data; /第一个元素 while ( li.nextNotNull ( ) ) /链表未扫描完 retval += li.Next( )-data; /累加 return retval;兑窒卿氰诛复中棉蔑奠作务秤苏噬比舰殖坠鄙久气洲挚茎衅古反潍坤埃匆675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双
37、向链表稀疏矩阵静态链表结构静态链表结构须淫偶说袖鳞里由敲汾绍氟需硫隐览海窗希熄咀且种削庚罗严硬撒搓鸯卷675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵静态链表定义静态链表定义const int MaxSize = 100; /静态链表大小template class StaticList;template class SListNode friend class StaticList; Type data; /结点数据 int link; /结点链接指针template class StaticList SListNode Nodes
38、MaxSize; int newptr; /当前可分配空间首地址吉九体稍仟工鞭肮盅鼠喷瞄跌企浴拐戈葛钙竿谨虫柜尔择锌滴恢蓉宏疯勺675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵将链表空间初始化将链表空间初始化template void StaticList : InitList ( ) Nodes0.link = -1; newptr = 1; /当前可分配空间从 1 开始建 /立带表头结点的空链表 for ( int i = 1; i MaxSize-1; i+ ) Nodesi.link = i+1; /构成空闲链接表 Nodes
39、MaxSize-1.link = -1; /链表收尾裔懈怜沧疾炮淑呕县枝扶厘妮冠瞪蛔幌诱滨溺卸苞诌玉昌渍献窥憨戊允馏675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵在静态链表中查找具有给定值的结点在静态链表中查找具有给定值的结点template int StaticList : Find ( Type x ) int p = Nodes0.link; /指针 p 指向链表第一个结点 while ( p != -1 ) if ( Nodesp.data != x) p = Nodesp.link; else break; /逐个结点检测
40、查找具有给定值的结点 return p;愈奖饮刽驳蝴犹巷湍漂零镶带基典崖檄病戒砖瞳淖饺察槛苍踊敛遁铲式吐675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵在静态链表的表尾追加一个新结点在静态链表的表尾追加一个新结点template int StaticList : Append ( Type x ) if ( newptr = -1 ) return 0; /追加失败 int q = newptr; /分配结点 newptr = Nodesnewptr.link; Nodesq.data = x; Nodesq.link = -1; i
41、nt p = 0; /查找表尾 while ( Nodesp.link != -1 ) p = Nodesp.link; Nodesp.link = q; /追加 return 1; 眶惰块模克揽返踞酉啥驶卵唆厌圣辽景肥杭涝溃渡椰佐幻脖诵霜擂残皂玖675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵在静态链表中查找在静态链表中查找第第 i 个个结点结点template int StaticList : Locate ( int i ) if ( i 0 ) return -1; /参数不合理 if ( i = 0 ) return 0;
42、int j = 0, p = Nodes0.link; while ( p != -1 & j i ) p = Nodesp.link; j+; /循链查找第 i 号结点 return p; 剥证镑霖敞休丹手怎兰追悟茅百个荣薯莉耳悦胀池摔帜淄龋捆鹃供气语颈675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵在静态链表在静态链表第第 i 个个结点处插入一个新结点结点处插入一个新结点template int StaticList : Insert ( int i, Type x ) int p = Locate ( i-1 ); if ( p
43、 = -1 ) return 0; /找不到结点 int q = newptr; /分配结点 newptr = Nodesnewptr.link; Nodesq.data = x; Nodesq.link = Nodesp.link; /链入 Nodesp.link = q; return 1;麓准呻历驻狙栋妒摧蠕毁焚螺扫傀陋厨迪策统侈泵损颧垣懈罐荫懊瑶犊毗675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵在静态链表中释放在静态链表中释放第第 i 个个结点结点template int StaticList : Remove ( int
44、i ) int p = Locate ( i-1 ); if ( p = -1 ) return 0; /找不到结点 int q = Nodesp.link; /第 i 号结点 Nodesp.link = Nodesq.link; Nodesq.link = newptr; /释放 newptr = q; return 1;呛蓝边刻匀奢骑在闭都反沂埠冕戌伴触先聊备塘巾狈急露众豆忻奎疯封莎675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵二、循环链表二、循环链表 (Circular List)n n循环链表是单链表的变形。循环链表是单链表
45、的变形。n n循环链表的最后一个结点的循环链表的最后一个结点的 link 指针不为指针不为 NULL，而是指向了表的前端。，而是指向了表的前端。n n为简化操作，在循环链表中往往加入表头为简化操作，在循环链表中往往加入表头结点。结点。n n循环链表的特点是：循环链表的特点是：只要知道表中某一结只要知道表中某一结点的地址，就可搜寻到所有其他结点的地点的地址，就可搜寻到所有其他结点的地址。址。狂叛蔽忿啮骑姚理志棺锨锐谷彼坊菠滩辣剃迭苯垂她睦泼像娄君亨慧洛碌675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵n n循环链表的示例循环链表的示例n
46、 n带表头结点的循环链表带表头结点的循环链表 a0a1a2an-1firstan-1firsta1a0first( (空表空表) )( (非空表非空表) )延脆煞床犯盼剂陡葬灶拇戚猩裕男木阳蜡绎司嘿蚀聂琐膜涕衍疼治掖绩酸675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵template class CircList;template class CircListNode friend class CircList ;public: CircListNode ( Type d = 0, CircListNode *next = NULL
47、) : data ( d ), link ( next ) /构造函数private: Type data; /结点数据 CircListNode *link; /链接指针 循环链表类的定义循环链表类的定义投扇浴卡渍契琶带微耐乡么鹅纺滋装札录构淄邵戏差迟诀戮拼育蜕含孝葱675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵template class CircList private: CircListNode *first, *current, *last; /链表的表头指针、当前指针和表尾指针public: CircList ( Typ
48、e value ); CircList ( ); int Length ( ) const; Boolean IsEmpty ( ) return first-link = first; Boolean Find ( const Type & value ); 绕滓宇宋雹寻址道特唉编茹澄彭膀僳藕蛇岩逃果辉垮把击蓝驻瞒虾虑或冒675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵 Type getData ( ) const; void Firster ( ) current = first; Boolean First ( ); Boole
49、an Next ( ); Boolean Prior ( ); void Insert ( const Type & value ); void Remove ( );酱赦峭贸油楔喀铰陇末滤晌袖幼布耗矛副尘皂来揭古佩斋辗脚梭钳郁洒地675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵搜索成功搜索成功搜索不成功搜索不成功循环链表的搜索算法循环链表的搜索算法firstfirst3131484815155757搜索搜索15 搜索搜索25 current current currentcurrent current current current
50、current甘呛寻函淬矢椽喝樊声剑豹谅区溃感茬茧细娱鸯摧淌挝晕颂怀共老椅屏桐675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵循环链表的搜索算法循环链表的搜索算法template CircListNode * CircList : Find ( Type value ) /在链表中从头搜索其数据值为value的结点 current = first-link; /检测指针 current 指示第一个结点 while ( current != first & current-data != value ) current = curren
51、t-link; return current; 帽仿咸腮跪秤云魁谦谤界蛤默拷咳废并涤呵耸溢盖淬虎打犹茧捂志燕尘棚675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵用循环链表求解约瑟夫问题用循环链表求解约瑟夫问题n n约瑟夫问题的提法约瑟夫问题的提法 n 个人围成一个圆圈，首先第个人围成一个圆圈，首先第 1 个人个人从从 1 开始一个人一个人顺时针报数开始一个人一个人顺时针报数, 报到第报到第 m 个人，令其出列。然后再个人，令其出列。然后再从下一从下一 个人开始，从个人开始，从 1 顺时针报数，顺时针报数，报到第报到第 m 个人，再令其
52、出列，个人，再令其出列，如此下去如此下去, 直到圆圈中只剩一个人为直到圆圈中只剩一个人为止。此人即为优胜者。止。此人即为优胜者。寿卖桂捅雷匙澎戊涯酚逆坊呵蛆脾驹改托古魏典辨瘫樊匹砚怠鉴啦绅弘绕675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵例如例如 n = 8 m = 3赣景补剖洒快耸譬甘垦愤来岔偿西傲摧谋校臣门炒刃裹扔身扩冈窗掣堆蒜675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵约瑟夫问题的解法约瑟夫问题的解法#include #include “CircList.h”Te
53、mplate void CircList : Josephus ( int n, int m ) 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 ( ); /删去删去 豫衰耘槐京彪谴侵偏炼怀闸傈曹诊迭膛贾胁捕核戮踩主且师乘楞瘁声捷寡675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵void m
54、ain ( ) CircList clist; int n, m; cout n m; for ( int i = 1; i = n; i+ ) clist.insert (i); /形成约瑟夫环 clist.Josephus (n, m); /解决约瑟夫问题枝巢樱闻贝诸蛙政篆睬锭痈重卢偏于根尽疥霸渭绑秘姿蛙殖穷爵讹附戚养675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵三、多项式三、多项式 (Polynomial)n nn 阶多项式阶多项式 Pn(x) 有有 n+1 项项。u 系数系数 c0, c1, c2, , cnu 指数指数 0
55、, 1, 2, , n。按升幂排列。按升幂排列悸入葫蚀囱审并闻三亏夺迸翘严其赚搂骗妆缝宙敞肺旬差俗乎诬降疙嘲善675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵n n在多项式的链表表示中每个结点三个在多项式的链表表示中每个结点三个数据成员：数据成员：n n优点是：优点是：uu 多项式的项数可以动态地增长，多项式的项数可以动态地增长，不存在存储溢出问题。不存在存储溢出问题。uu 插入、删除方便，不移动元素。插入、删除方便，不移动元素。多项式的链表表示多项式的链表表示coef exp link Data Term乓俐萝郎献秩鳃釜摄伶鼻艺槛需
56、酌天脆呸诧松凉相至澳蔼杜王粳署擞演缕675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵多项式多项式(polynomial)类的链表定义类的链表定义struct Term /多项式结点定义 float coef; /系数 int exp; /指数 Term ( float c, int e ) coef = c; exp = e; ; class Polynomial /多项式类的定义 List poly; /构造函数 friend Polynomial & operator + ( Polynomial &); /加法;赢鉴空膘薄奸瘸塞
57、匀误缚炒忌状董顷信享癌咨材句琴奶瑰扇又氛搏赛祈婶675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵多项式链表的相加多项式链表的相加AH = 1 - 3x6 + 7x12BH = - x4 + 3x6 - 9x10 + 8x14AH.firstBH.first CH.first 1 01 0-1 4-1 4-3 63 6-9 10-9 107 127 128 148 14烙侄离枕两叙致摄杂灼帽臃阜亡垄庸屯讥苫菜巷渍瘟倾明雹讯扛涉鞍玻缴675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩
58、阵两个多项式的相加算法两个多项式的相加算法n n扫描两个多项式，若都未检测完：扫描两个多项式，若都未检测完：uu 若当前被检测项指数若当前被检测项指数相等相等，系数，系数相加。若未变成相加。若未变成 0，则将结果加，则将结果加到结果多项式。到结果多项式。uu 若当前被检测项指数若当前被检测项指数不等不等，将指，将指数小者加到结果多项式。数小者加到结果多项式。n n若一个多项式已检测完，将另一个若一个多项式已检测完，将另一个多项式剩余部分复制到结果多项式。多项式剩余部分复制到结果多项式。勒聪藏草糜蛇方抿嗓涝煮料拨栗呼胯迷烦公术哑偶擎怖函蘑入乱帝馈繁控675-单链表 循环链表多项式及其相加双向链表
59、稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵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 = bh.poly.first-link; /多项式检测指针 delete p; /删去b
60、h的表头结点凋遁醇捎垦讨江永哀瑟九垛尺糙宿踢谤舵魄耕宁醛初服台撰偶哥涛剖梗焰675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵 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.c
61、oef ) link; delete p; /相加为零, 该项不要 else /相加不为零, 加入ch链 pa-data = a; pc-link = pa;肖破庄县厌悄围瘸莽于寿典糖报谊臀掉互疥罢记厚甜宗衣职捣吵燥酥碘苔675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵 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
62、 = pa-link; 诈贵险忆笨挤交绑琅感炎仅些敌词磊说在全揖姆错震榆须剁玫姑涂测懒荣675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵 if ( pa-link ) pc-link = pa; else pc-link = pb; /剩余部分链入ch链 return this; 遭偏厩航聂渍掠做秆私秽刺仔壹北园尚远昏呵鸟官篙缘浆悯式挤签碉讫毫675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵四、双向链表四、双向链表 (Doubly Linked List)n n双向链表是指在
63、前驱和后继方向都能双向链表是指在前驱和后继方向都能游历游历(遍历遍历)的线性链表。的线性链表。n n双向链表每个结点结构：双向链表每个结点结构： n n双向链表通常采用带表头结点的循环双向链表通常采用带表头结点的循环链表形式。链表形式。前驱方向前驱方向 后继方向后继方向lLink data rLink纂蛀社仕夯仙裂估奢主恕目粪纱汕矣酋扰所秦陇擅聂效央个绷升杰晰刺叙675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵n n结点指向结点指向p = p-lLink-rLink = p-rLink-lLink非空表非空表 空表空表p-lLinkp
64、-rLinkplLinkrLinkfirstfirst练延玉梳裁罗经屑易撅根墓管播盾摸鸽蘸补二狄疫引瘸盐骋待上妥还馅娜675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵双向循环链表类的定义双向循环链表类的定义template class DblList;template class DblNode friend class DblList;private: Type data; /数据 DblNode * lLink, * rLink; /指针public: DblNode (Type value=0, DblNode * left,
65、DblNode * right ) : data (value), lLink (left), rLink (right) 油磷酚冠烂肃绸抗瘪糕批佣邓盼嘱费笆掀扭凹雇存畸荔筏郭宽银堑羚足尚675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵 DblNode ( Type value ) : data (value), lLink (NULL), rLink (NULL) DblNode * getLeftLink ( ) return llink; /取得左链指针值 DblNode * getRightLink ( ) return rl
66、ink; /取得右链指针值 Type getData ( ) return data; void setLeftLink ( DblNode*Left ) llink = Left; /修改左链指针值 void setRightLink ( DblNode*Right ) rlink = Right; /修改左链指针值 繁瘦猖烃吟璃询詹边圾矢闯起锌裙枷掩偏婚写挤惩眷呈环叹落养餐捕放控675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵 void setData ( Type value ) data = value; ;template
67、class DblList private: DblNode * first, * current;public: DblLIst (); /构造函数 DblList ( ); /析构函数 int Length ( ) const; /计算长度 int IsEmpty ( ) /判链表空否 return first-rlink = first; 鳃苟秋雍药壬遁需蚊泵琵鲍宪鳖俗傍蚁仪岂咽臼旅雌锨山骂剑避原聋惜萍675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵 int Find ( const Type& target ); void F
68、irster ( ) current = first; /当前指针置于表头结点。 int First ( ) ;/当前指针置于第一个结点 int Next ( );/当前指针置于后继结点 int Prior ( );/当前指针置于前驱结点 void Insert ( const Type& value );/插入一个包含有值value的新结点 void Remove ( );/删除当前结点;侧寝锨铬馁矮胚酌逸放床穷炼蒙吏始爷簧蝎确粗兼谤彻单串硬肤崇钢躁密675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵template DblList
69、: DblList () /构造函数: 建立双向循环链表的表头结点 first = current = new DblNode (); if (first = NULL ) cerr rLink = first-lLink = first; /表头结点的链指针指向自己珍鼓菊擎谤挥羽行捣幻窝类智溅豫伎赤霞虽幼履代愚案浙拎毛疑颊利秆腰675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵template int DblList : Length ( ) const /计算带表头结点的双向循环链表的长度 DblNode * p = first-r
70、Link; int count = 0; while ( p != first ) p = p-rLink; count+; return count; 塞脸毖星句悠克暇扩创容妖新篆鉴菌女靳胳干英介柑彬烯片寇君此酷培慈675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵搜索成功搜索成功搜索不成功搜索不成功双向循环链表的搜索算法双向循环链表的搜索算法firstfirst3131484815155757搜索搜索15 搜索搜索25 菌腋叼促俞钾姬厦极径痉砌狭需列拥增拦入往柞广奸圣盛可俭爆岿玛绷纺675-单链表 循环链表多项式及其相加双向链表稀疏
71、矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵template int DblList :Find ( const Type& target ) /在双向循环链表中搜索含target的结点, 若/找到, 则返回1, 同时current指针指向该结点, /否则函数返回0。 current = first-rLink; while ( current != first & current-data != target ) current = current-rLink; if ( current != first ) return 1; else return 0;些似恃窝救股梆洽髓城
72、堤豫一疫禁暂勿远澈刊厚蝉邵丛绞彻洪估奋拍施非675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵双向循环链表的插入算法双向循环链表的插入算法 (非空表非空表)firstfirst314815后插入后插入25currentcurrent31482515newnode-lLink = current;newnode-rLink = current-rLink;current-rLink = newnode;current = current-rLink;current-rLink-lLink = current;馁石彰涨盔痘馈婪毒剪逸俊戎碧獭
73、冒瘦浚蛀三尼泳赛詹妇噶渭膨皋坡继嗣675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵双向循环链表的插入算法双向循环链表的插入算法 (空表空表)first后插入后插入25currentcurrent25newnode-lLink = current;newnode-rLink = current-rLink; ( = first )current-rLink = newnode;current = current-rLink;current-rLink-lLink = current; ( first -lLink = current )
74、 first笼辱扰撼肆颈围寇神骨席滥匆薪拦圣紫榆颈穷保扇彰串瑚烫富腔嵌狮屈仙675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵template void DblList :Insert ( const Type & value ) if ( first-rlink = first ) /空表情形 current = first-rLink = new DblNode ( value, first, first ); else /非空表情形 current-rLink = new DblNode ( value, current, cur
75、rent-rLink ); current = current-rLink; current-rLink-lLink = current;司贩疯和蝗胯狞伶肋蔽懦唁召杯南功勾挖敷中矢缝皂钨削树战酉锰回汰蛛675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵删除删除48双向循环链表的删除算法双向循环链表的删除算法firstfirst非空表非空表314815current3115currentcurrent-rLink-lLink = current-lLink; current-lLink-rLink = current-rLink;毒沤癸圃
76、桃屑埃鞋咽举芽爹几村敲弦黄韶惶均粳盖觅锰杀秃温竹坟坐填至675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵删除删除31双向循环链表的删除算法双向循环链表的删除算法firstfirst31currentcurrentcurrent-rLink-lLink = current-lLink; current-lLink-rLink = current-rLink;图鬃慷涯城广翠落无称妊矽陵库媚褂雕什闰城侥访锤吞倒甫椭偷纽汾循逾675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵templ
77、ate void DblList : Remove ( ) if ( current != first ) DblNode *temp = current; /被删结点 current = current-rLink; /当前指针进到下一结点 current-lLink = temp-lLink; /将被删结点从链中摘下 temp-lLink-rLink = current; delete temp; /删去 枫乒被傣青卜寂巡兵频侗献此稍送频孟非送鲤毒莽南援埂契七拧渣蒂烧斧675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵templat
78、e int DblList : First ( ) if ( !IsEmpty ( ) ) current = first-rLink; return 1; current = first; return 0;其他双向循环链表的公共操作其他双向循环链表的公共操作答皖溉弥腻拆隋驰葡监脏暑植你巾肛衬诌唯枕宁匡肉疾匝杯乖干辐尧躁光675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵template int DblList : Next ( ) if ( current-rLink = first ) /最后结点 current = first
79、-rLink; return 0; current = current-rLink; return 1;template int DblList : Prior ( ) if ( current-lLink = first ) /第一个结点 current = first -lLink; return 0; current = current-lLink; return 1;耐尉稳彝菩饿伙腹揖蓄惟皆队妙各渝吾浆铡廖勺擎炯德腾顿制杖荡档榨很675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵五、稀疏矩阵五、稀疏矩阵n n在矩阵操作在矩阵操作
80、(+、-、*、/)时矩阵非零时矩阵非零元素会发生动态变化，用稀疏矩阵的元素会发生动态变化，用稀疏矩阵的链接表示可适应这种情况。链接表示可适应这种情况。n n稀疏矩阵的链接表示采用正交链表：稀疏矩阵的链接表示采用正交链表：行链表与列链表十字交叉。行链表与列链表十字交叉。n n行链表与列链表都是带表头结点的循行链表与列链表都是带表头结点的循环链表。用表头结点表征是第几行，环链表。用表头结点表征是第几行，第几列。第几列。仁蒂莫捡涌烦内扼楷促渭蚊析租掖咆践跌队奄唤梯告砸焙秧者揖碎奄醋纵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵稀疏矩阵的
81、结点稀疏矩阵的结点headdownnextright(a) 表头结点表头结点 (b) 非零元素结点非零元素结点rightvaluedownrowcolaijFalseij(c) 建立建立aij结点结点 head馅诱梅恬谎继谦盯资速挎兽稠古烁娩激屹伊彪泣湃厩妥阮容优激侄眠拙叮675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵稀疏矩阵的正交链表表示的示例稀疏矩阵的正交链表表示的示例柏翟怪掇栗逼贩贿尺向署养皖绍夷系醒胯翰饯竖过仅唁枕抢呕颈未星砸膝675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链
82、表稀疏矩阵稀疏矩阵的链表表示的类定义稀疏矩阵的链表表示的类定义enum Boolean False, True ;struct Triple int row, col; float value; ;class Matrix;class MatrixNode /矩阵结点定义friend class Matrix;friend istream &operator ( istream &, Matrix & ); /矩阵输入重载函数private: MatrixNode *down, *right;/列/行链指针 Boolean head; /结点类型搭轻岩眶芥糕瑞穷左胎咸视档哀诀串侗有蒋悠棱绊赤砌
83、叁俐戌狠顶炮趴那675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵 Union Triple triple; MatrixNode *next; /矩阵元素结点(False)或链头结点(True) MatrixNode ( Boolean, Triple* ); /结点构造函数MatrixNode:MatrixNode ( Boolean b, Triple *t ) /矩阵结点构造函数 head = b; /结点类型 if ( b ) right = next = this; else triple = *t;圈攀蜘蔑苯扫买绿施履矛记
84、苑净群药焚发惮昭秘昭床芳迁帐噎韵铜佩痛归675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵typedef MatrixNode *MatrixNodePtr;/一个指针数组, 用于建立稀疏矩阵class Matrix friend istream& operator ( istream &, Matrix & ); /矩阵输入矩阵输入public: Matrix ( ); /析构函数析构函数private: MatrixNode *headnode; /稀疏矩阵的表头稀疏矩阵的表头;劣择噬皆碟遇讽诲拨艘忌攻蒜箕堑匣颈匙豢券颓祸哈鉴央枢你
85、隆捡饵独征675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵用正交链表表示的稀疏矩阵的建立用正交链表表示的稀疏矩阵的建立istream & operator ( istream & is, Matrix & matrix ) 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 Ma
86、trixNode ( False, &s ); if ( !p ) /零矩阵时 matrix.headnode-right = matrix.headnode; 顿拧豌骆劣霄稻厢柯峨奴芜台蝗递扒旅屋戮番靳过栽引参请矾喀洋贿沥请675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵 return is; MatrixNodePtr *H = new MatrixNodePtr ( p ); /建立表头指针数组, 指向各链表的表头 for ( int i = 0; i p; i+ ) Hi = new MatrixNode ( True, 0
87、); int CurrentRow = 0; MatrixNode *last = H0; /当前行最后结点 for ( i = 0; i t.row t.col t.value; /输入非零元素的三元组拍麻漂恭钉纶议桶讣具贝菇邹现耙司剿略畅丽挂森涕阀惮镰索途弹象具避675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵 if ( t.row CurrentRow ) /如果行号大于当前行,闭合当前行 last-right = HCurrentRow; CurrentRow = t.row; last = HCurrentRow; last
88、 = last-right = /链入当前行 new MatrixNode ( False, &t ); Ht.col-next = Ht.col-next-down = last; /链入列链表 last-right = HCurrentRow; /闭合最后一行江喝疾超邮姥签鹊腻刘痴缮坍砾荚曝摸现拈嘻笨憾玫庭普聚汞齐妙贪袭欣675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵 /闭合各列链表 for ( i = 0; i next-down = Hi; /链接所有表头结点 for ( i = 0; i next =Hi+1; Hp-1-
89、next = matrix.headnode; matrix.headnode-right = H0; delete H; return is;语弊激替滞溢黄瘴烂跨辐纠窿册必孵镍竭矾脱役疏混莫臃吻桅尔勉稻症四675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵稀疏矩阵的删除稀疏矩阵的删除n n为执行稀疏矩阵的删除，需要使用可利为执行稀疏矩阵的删除，需要使用可利用空间表来管理回收的空间。用空间表来管理回收的空间。n n可利用空间表是单链表结构，只允许在可利用空间表是单链表结构，只允许在表头插入或删除，其表头指针为表头插入或删除，其表头指针为
90、av。n n使用可利用空间表，可以高效地回收循使用可利用空间表，可以高效地回收循环链表。环链表。n n如果需要建立新的稀疏矩阵，还可以从如果需要建立新的稀疏矩阵，还可以从可利用空间表中分配结点。可利用空间表中分配结点。机孤埠脊润诱贺陛命享验邓夏吠吧棚栈美飘避障象顿唆氏小贵叛嘘青筹钩675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵用正交链表表示的稀疏矩阵的删除用正交链表表示的稀疏矩阵的删除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;溅三淬陈寨勇赘槐思弦扔圈嘻拈坡弄关偏走宵捞钵装旁钠诅变请抡汞肪现675-单链表 循环链表多项式及其相加双向链表稀疏矩阵675-单链表 循环链表多项式及其相加双向链表稀疏矩阵
