单链表 (singly linked list)循环链表 (circular list)多项式及其相加

《单链表 (singly linked list)循环链表 (circular list)多项式及其相加》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、单链表(SinglyLinkedList)循环链表(CircularList)多项式及其相加双向链表(DoublyLinkedList)稀疏矩阵第三章链表单链表(SinglyLinkedList)特点每个元素(表项)由结点(Node)构成。线性结构结点可以不连续存储表可扩充单链表的存储映像单链表的类定义多个类表达一个概念(单链表)。链表结点(ListNode)类链表(List)类链表游标(Iterator)类定义方式复合方式嵌套方式classList;//复合类定义classListNode{//链表结点类friendclassLis

2、t;//链表类为其友元类private:intdata;//结点数据,整型ListNode*link;//结点指针};classList{//链表类public://链表公共操作………private:ListNode*first,*last;//表头和表尾指针};classList{//链表类定义(嵌套方式)public://链表操作………private:classListNode{//嵌套链表结点类public:intdata;ListNode*link;};ListNode*first,*last;//表头和表尾指针};单链表中的

3、插入与删除插入第一种情况：在第一个结点前插入newnode→link=first;first=newnode；（插入前）（插入后）(插入前)(插入后)第二种情况：在链表中间插入newnode→link=p→link;p→link=newnode；第三种情况：在链表末尾插入newnode→link=p→link;p→link=last=newnode；(插入前)(插入后)intList::Insert(constintx,constinti){//在链表第i个结点处插入新元素xNode*p=first;intk=0;while(p!=N

4、ULL&&k

5、

6、i==0){//插在表前newnode→link=first;if(first==NULL)last=newnode;first=newnode;}else{//插在表中或末尾newnode→

7、link=p→link;if(p→link==NULL)last=newnode;p→link=newnode;}return1;}删除第一种情况:删除表中第一个元素第二种情况:删除表中或表尾元素在单链表中删除含ai的结点intList::Remove(inti){//在链表中删除第i个结点Node*p=first,*q;intk=0;while(p!=NULL&&k

8、n0;}if(i==0){//删除表中第1个结点q=first;//q保存被删结点地址p=first=first→link;//修改first}else{//删除表中或表尾元素q=p→link;p→link=q→link;//重新链接}if(q==last)last=p;//可能修改lastk=q→data;deleteq;//删除qreturnk;}带表头结点的单链表表头结点位于表的最前端，本身不带数据，仅标志表头。设置表头结点的目的是统一空表与非空表的操作，简化链表操作的实现。非空表空表在带表头结点的单链表第一个结点前插入新结点n

9、ewnode→link=p→link;if(p→link==NULL)last=newnode;p→link=newnode;q=p→link;p→link=q→link;deleteq;if(p→link==NULL)last=p;从带表头结点的单链表中删除第一个结点单链表的类模板类模板将类的数据成员和成员函数设计得更完整、更灵活。类模板更易于复用。在单链表的类模板定义中，增加了表头结点。用模板定义的单链表类templateclassList;templateclassListNode{f

10、riendclassList;Typedata;//结点数据ListNode*link;//结点链接指针public:ListNode();//链表结点构造函数ListNode(constType