单链表链表的游标类静态链表 循环链表多项式及其相加双向链

单链表链表的游标类静态链表循环链表多项式及其相加双向链表稀疏矩阵单链表(SinglyLinkedList)特点每个元素(表项)由结点(Node)构成。线性结构。结点之间可以连续，可以不连续存储;结点的逻辑顺序与物理顺序可以不一致;表可扩充。datalinka0a1a2a3a4Λfirst单链表的存储映像free(a)可利用存储空间a0a2a1a3freefirst(b)经过一段运行后的单链表结构单链表的类定义多个类表达一个概念(单链表)。链表结点(ListNode)类；链表(List)类。定义方式：复合方式；嵌套方式；继承方式。classList;//链表类定义（复合方式）classListNode{//链表结点类friendclassList;//链表类为其友元类private:intdata;//结点数据,整型ListNode*link;//结点指针};classList{//链表类private:ListNode*first,*current;//表头指针};classList{//链表类定义(嵌套方式)private:classListNode{//嵌套链表结点类public:intdata;ListNode*link;};ListNode*first,*current;//表头指针public://链表操作………};链表类和链表结点类定义(继承方式)classListNode{//链表结点类protected:intdata;ListNode*link;};classList:publicclassListNode{//链表类,继承链表结点类的数据和操作private:ListNode*first,*current;//表头指针};在复合方式中，链表结点类中声明链表类是它的友元类，这样可以“奉献”它的私有成员给链表类。这种方式灵活。在嵌套方式中，链表结点类是链表类的私有成员，这样限制了链表结点类的应用范围。在继承方式中，链表类声明为链表结点类的派生类，这在实现上是可行的。但在逻辑上是有问题的，如三角形is多边形（继承关系）链表is链表结点（显然概念有误）单链表中的插入与删除插入第一种情况：在链表最前端插入newnode-link=first;first=newnode;（插入前）（插入后）firstnewnodenewnodefirst(插入前)(插入后)第二种情况：在链表中间插入newnode-link=current-link;current-link=newnode；newnodecurrentnewnodecurrent第三种情况：在链表末尾插入newnode-link=current-link;current-link=newnode；(插入前)(插入后)newnodenewnodecurrentcurrentintList::Insert(intx,inti){//在链表第i(≥0)号结点处插入新元素xListNode*p=current;current=first;for(k=0;ki-1;k++)//找第i-1号结点if(current==NULL)break;elsecurrent=current-link;if(current==NULL&&first!=NULL){cout“无效的插入位置!\n”;current=p;return0;}ListNode*newnode=//创建新结点newListNode(x,NULL);if(first==NULL||i==0){//插在表前newnode-link=first;first=current=newnode;}else{//插在表中或末尾newnode-link=current-link;current=current-link=newnode;}return1;}删除第一种情况:删除表中第一个元素第二种情况:删除表中或表尾元素在单链表中删除含ai的结点ai-1ai-1aiaiai+1ai+1pq删除前删除后intList::Remove(Type&x,inti){//在链表中删除第i号结点,通过x返回其值ListNode*p,*q;if(i==0)//删除表中第0号结点{q=first;current=first=first-link;}else{p=current;current=first;intk=0;//找第i-1号结点while(current!=NULL&&ki-1){current=current-link;k++;}if(current==NULL||current-link==NULL){cout“无效的删除位置!\n”;current=p;return0;}else{//删除表中或表尾元素q=current-link;//重新链接current=current-link=q-link;}}x=q-data;deleteq;//删除qreturn1;}带表头结点的单链表表头结点位于表的最前端，本身不带数据，仅标志表头。设置表头结点的目的是统一空表与非空表的操作，简化链表操作的实现。非空表空表0an-1a0firstfirst0在带表头结点的单链表最前端插入新结点newnode-link=p-link;p-link=newnode;firstnewnodefirstnewnode插入firstnewnode0firstnewnode0插入ppppq=p-link;p-link=q-link;deleteq;从带表头结点的单链表中删除最前端的结点(非空表）(空表）firstfirstfirst0first0pqpq单链表的模板类类模板将类的数据成员和成员函数设计得更完整、更灵活。类模板更易于复用。在单链表的类模板定义中，增加了表头结点。用模板定义的单链表类templateclassTypeclassList;templateclassTypeclassListNode{friendclassListType;Typedata;//结点数据ListNodeType*link;//结点链接指针public:ListNode():link(NULL){}//构造函数ListNode(Typeitem):data(item),link(NULL){}ListNode(Typeitem,ListNodeType*next):data(item),link(next){}//以item和next建立一个新结点ListNodeType*getLink(){returnlink;}//取得结点的下一结点地址TypegetData(){returndata;}//取得结点中的数据voidsetLink(ListNodeType*next){link=next;}//修改结点的link指针voidsetData(Typevalue){data=value;}//修改结点的data值};templateclassTypeclassList{//链表类private:ListNodeType*first,*current;//链表的表头指针和当前元素指针public:List(Typevalue){current=first=newListNodeType(value);}List(ListType&RL);//复制构造函数~List(){MakeEmpty();deletefirst;}//析构函数voidMakeEmpty();//将链表置为空表intLength()const;//计算链表的长度ListNodeType*Find(Typevalue);//搜索含数据value的元素并成为当前元素ListNodeType*Locate(inti);//搜索第i号元素的地址并置为当前元素intGetData(Type&value);//取出表中当前元素的值intInsert(Typevalue);//将value插在表中当前元素后intRemove(Type&value);//将链表当前元素删去,填补者为当前元素ListNodeType*Firster(){current=first;returnfirst;}//当前指针置于表头,返回表头结点地址ListNodeType*First(){current=first-link;returncurrent;}//第一个结点为当前结点ListNodeType*Next();//下一个结点为当前结点intNotNull(){returncurrent!=NULL;}intNextNotNull(){returncurrent!=NULL&¤t-link!=NULL;}};templateclassTypevoidListType::MakeEmpty(){//删去链表中除表头结点外的所有其他结点ListNodeType*q;while(first-link!=NULL){q=first-link;first-link=q-link;//将表头结点后第一号结点从链中摘下deleteq;//释放它}current=first;//当前指针置于表头结点}链表类部分操作的实现firstqfirstfirstqqfirsta0a1a1a2a2a2currenttemplateclassTypeintListType::Length()const{//求单链表的长度ListNodeType*p=first-link;//检测指针p指示第一号结点intcount=0;while(p!=NULL){//逐个结点检测p=p-link;count++;}returncount;}firstpa0a1a2c=0firstpa0a1a2c=1firstpa0a1a2c=2firstpa0a1a2c=3templateclassTypeListNodeType*ListType::Find(Typevalue){//在链表中从头搜索其数据值为value的结点current=first-link;//当前指针current指示第一号结点while(current!=NULL)if(current-data==value)break;elsecurrent=current-link;returncurrent;}//搜索失败时current=NULLtemplateclassTypeListNodeType*ListType::Locate(inti){//定位函数：返回表中第i号元素的地址,//i=0为寻找表头结点的地址if(i0)returnNULL;//i值不合理current=first;intk=0;while(current!=NULL&&ki){current=current-link;k++;}//找第i号结点returncurrent;//返回第i号结点地址或NULL}//定位失败时current=NULLtemplateclassTypeintListType::GetData(Type&value){//取出链表中当前元素的值if(current==NULL||current==first)return0;else{value=current-data;return1;}}templateclassTypeintListType::Insert(Typevalue){//将新元素value插入在链表中当前结点后if(current==NULL)return0;ListNodeType*newnode=//创建结点newListNodeType(value);newnode-l