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

《单链表 循环链表多项式及其相加双向链表稀疏矩阵.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、单链表循环链表多项式及其相加双向链表稀疏矩阵第三章链表单链表(SinglyLinkedList)特点每个元素(表项)由结点(Node)构成。线性结构结点可以连续，可以不连续存储结点的逻辑顺序与物理顺序可以不一致表可扩充datalinka0a1a2a3a4first单链表的存储映像free(a)可利用存储空间a0a2a1a3freefirst(b)经过一段运行后的单链表结构单链表的类定义多个类表达一个概念(单链表)。链表结点(ListNode)类链表(List)类链表游标(Iterator)类

2、定义方式复合方式嵌套方式继承方式classList;//链表类定义（复合方式）classListNode{//链表结点类friendclassList;//链表类为其友元类private:intdata;//结点数据,整型ListNode*link;//结点指针};classList{//链表类private:ListNode*first,*last;//表头指针};classList{//链表类定义(嵌套方式)private:classListNode{//嵌套链表结点类public:intd

3、ata;ListNode*link;};ListNode*first,*last;//表头指针public://链表操作………};链表类和链表结点类定义(继承方式)classListNode{//链表结点类protected:intdata;ListNode*link;};classList:publicclassListNode{//链表类,继承链表结点类的数据和操作private:ListNode*first,*last;//表头指针};单链表中的插入与删除插入第一种情况：在第一个结点前插入

4、newnode->link=first;first=newnode;（插入前）（插入后）firstnewnodenewnodefirst(插入前)(插入后)第二种情况：在链表中间插入newnode->link=p->link;p->link=newnode；newnodepnewnodep第三种情况：在链表末尾插入newnode->link=p->link;p->link=newnode；(插入前)(插入后)newnodenewnodeppintList::Insert(intx,inti)

5、{//在链表第i个结点处插入新元素xListNode*p=first;for(k=0;klink;if(p==NULL&&first!=NULL){cout<<“无效的插入位置!”;return0;}ListNode*newnode=//创建新结点newListNode(x,NULL);if(first==NULL

6、

7、i==0){//插在表前newnode->link=first;if(first==N

8、ULL)last=newnode;first=newnode;}else{//插在表中或末尾newnode->link=p->link;if(p->link==NULL)last=newnode;p->link=newnode;}return1;}删除第一种情况:删除表中第一个元素第二种情况:删除表中或表尾元素在单链表中删除含ai的结点ai-1ai-1aiaiai+1ai+1pq删除前删除后intList::Remove(inti){//在链表中删除第i个结点ListNode*p,*q;

9、if(i==0)//删除表中第1个结点{q=first;p=first=first->link;}else{p=first;intk=0;//找第i-1个结点while(p!=NULL&&klink;k++;}if(p==NULL

10、

11、p->link==NULL){cout<<“无效的删除位置!”;return0;}else{//删除表中或表尾元素q=p->link;//重新链接p->link=q->link;}if(q==last)last=p;//可能修改lastTy

12、pex=q->data;deleteq;//删除qreturnx;//返回第i个结点的值}带表头结点的单链表表头结点位于表的最前端，本身不带数据，仅标志表头。设置表头结点的目的是统一空表与非空表的操作，简化链表操作的实现。非空表空表0ana1firstfirst0在带表头结点的单链表第一个结点前插入新结点newnode->link=p->link;if(p->link==NULL)last=newnode;p->link=newnode;firstnewnodefirstnewnode插入fir