C++数据结构之单链表

zhangxiafll

2012-02-02

关注关注

线性表包含数据域和指针域其中，data存储数据本身的值，next存储后继元素的地址下面的图表示的是一个数据节点

C++数据结构之单链表

单链表的结构示意图（包括空的单链表）：

C++数据结构之单链表

单链表的节点类:

　template<classT>  


classNode  


{  



public:  




T data;//数据  




Node<T> *next;//next指针  



Node()  


{  



this->next=NULL;//构造空的节点  



}  



Node(T data,Node<T> *next=NULL)//构造一个节点  



{  



this->data=data;  




this->next=next;  



}  


};

单链表类声明如下：

#include<iostream>  



#include "Node.h"//单链表节点类  



template<classT>  



classSinglyLinkedList //单链表类  



{  



public:  




Node<T> *head;//单链表的头指针。  




SinglyLinkedList();//构造空的单链表。  




SinglyLinkedList(T value[], intn);//构造由指定的数组提供的单链表  




~SinglyLinkedList();//析构  




boolisEmpty();//判断是否为空。  




intlength();//获取长度  




Node<T>* getNode(inti);//返回第i(i>=0)个节点指针  




T get(inti);//返回第i个元素  




boolset(inti,T x);//设置第i个元素为x  




template<classT> friend std::ostream& operator<<(std::ostream& out,SinglyLinkedList<T> &list);  




Node<T>* insert(inti,T x);//插入第I个节点并返回第i个节点的指针  




boolremove(inti,T& old);//删除第i个元素，将删除的元素存放到old  




voidclear();//清空单链表  




voidconcat(SinglyLinkedList<T> &list);//将List链接在当前单链表之后  



};

单链表部分如构造空的链表对象，析构，判断为空的实现，没有要讲的算法，实现如下：

template<classT>  



SinglyLinkedList<T>::SinglyLinkedList()//构造空的单链表  



{  



this->head=NULL;  



　}  


template<classT>  



SinglyLinkedList<T>::~SinglyLinkedList()//析构  



{  


clear();  


}  


template<classT>  



boolSinglyLinkedList<T>::isEmpty()//判断链表是否为空  



{  


returnthis->head==NULL;  


}

单链表的遍历操作，遍历单链表是指从第一个节点开始访问，沿着节点的Next可依次访问单链表中的各个节点，并且各个节点只被访问一次。实现的单链表遍历的基本算法如下：

intj=0;  


Node<T> *p=head;  



while(p!=NULL&&j<i)  



{  


j++;  


p=p->next;  


}

单链表的length(),get(),set(),clear()和输出等操作都基于以上算法。

template<classT>  


intSinglyLinkedList<T>::length()  


{  


　inti=0;  



Node<T> *p=head;//创建一个用于遍的变量  




while(p!=NULL)  



{  


i++;  


std::cout<<p->data;  


p=p->next;  


}  


　returni;  


}  


template<classT>  


Node<T>* SinglyLinkedList<T>::getNode(inti)  


{  



if(i<0)  



returnNULL;  


intj=0;  


Node<T> *p=head;  



while(p!=NULL&&j<i)  



{  


j++;  


p=p->next;  


}  


returnp;  


}  


template<classT>  



T SinglyLinkedList<T>::get(inti)  



{  


Node<T> *p=getNode(i);  



if(p!=NULL)  



returnp->data;  


T d;  


returnd;  



//throw "单链表为空或者参数指定的元素不存在";  



}  


template<classT>  



boolSinglyLinkedList<T>::set(inti,T x)  



{  


Node<T> *p=getNode(i);  



if(p!=NULL)  



{  


p->data=x;  


returntrue;  


}  


returnfalse;  


}  


template<classT>  



std::ostream& operator<<(std::ostream& out,SinglyLinkedList<T> &list)  



{  


Node<T> *p=list.head;  



out<<"(";  




while(p!=NULL)  



{  



out<<p->data;  



p=p->next;  



if(p!=NULL)  




out<<",";  



}  



out<<") ";  



returnout;  


}  


template<classT>  


voidSinglyLinkedList<T>::clear()  


{  


Node<T> *p=head;  



while(p!=NULL)  



{  


Node<T> *q=p;  


p=p->next;  


delete q;  


}  


head=NULL;  


　}

单链表的插入操作，单链表不像顺序表，对与表的插入和删除很简单：

空表插入/头插入

Node<T> *q=NULL;  



if(head==NULL||i<0)//头插入(单链表为空或者)  



{  


q=newNode<T>(x,head);  


head=q;  


}  


中间插入/尾插入  


p->next=newNode<T>(x,p->next);  


单链表insert()以及参数构造函数：  


　template<classT>  


Node<T>* SinglyLinkedList<T>::insert(inti,T x)  


{  


Node<T> *q=NULL;  



if(head==NULL||i<0)//头插入(单链表为空或者)  



{  


q=newNode<T>(x,head);  


head=q;  


}  



else 



{  


intj=0;  


Node<T> *p=head;  



while(p->next!=NULL&&j<i-1)  



{  


j++;  


p=p->next;  


}  


q=newNode<T>(x,p->next);  


　p->next=q;  


}  


returnq;  


}  


　template<classT>  


SinglyLinkedList<T>::SinglyLinkedList(T table[],intn)  


{  


head=NULL;  



if(n>0)  



{  



head=newNode<T>(table[0]);//创建节点  




　Node<T> *rear=head;//创建一个指向头节点的指针  



inti=1;  



　while(i<n)  



{  


rear->next=newNode<T>(table[i++]);  


rear=rear->next;  


}  


}  


}

　单链表的删除操作也分两类：

头删除

Node<T> *q=head;  


head=head->next;  


delete q;

中间/尾删除

Node<T> *q=p->next;  



if(q!=NULL)//判断删除节点  



{  



p->next=q->next;//让删除节点的前驱Next指针下一节点  




delete q;//删除该节点  



}

单链表的删除函数remove（）实现：

template<classT>  


boolSinglyLinkedList<T>::remove(inti,T &old)  


{  



if(i<0||head==NULL)  



{  


Node<T> *q=head;  


old=q->data;  


head=head->next;  


delete q;  


　}  



else 



{  



Node<T> *p=getNode(i-1);//获取删除节点的前驱  




　if(p!=NULL&&p->next!=NULL)//判断删除节点和删除节点是否为空  



{  



Node<T> *q=p->next;//新建一个节点指针，将删除接点复制过去  



old=q->data;  



p->next=q->next;//让删除节点的前驱Next指针下一节点  




delete q;//删除该节点  



　returntrue;  


}  


　}  


returnfalse;  


}  


单链表的链接函数：concat()  


template<classT>  


voidSinglyLinkedList<T>::concat(SinglyLinkedList<T> &list)  


{  



if(this->head==NULL)  



{  



this->head=list->head;  



}  



else 



{  


Node<T> *p=head;  



while(p->next!=NULL)  



{  


p=p->next;  


}  


p=list->head;  


}  



list->head=NULL;//设置单链表为空，否则运行出错  



}

以上对C++单链表的分析添加一个学生结构和一个测试函数：

Student.h  


structStudent  


{  



charnumber[10]; //学号  




charname[20]; //姓名  




doublescore; //得分  




friend std::ostream& operator<<(std::ostream& out,Student &stu)  



{  



out<<"学号："<<stu.number<<"姓名："<<stu.name<<"得分："<<stu.score;  



returnout;  


}  


};  


主函数：  


#include<iostream>  



#include "SinglyLinkedList.h" 




#include "Student.h" 



void_TestToSinglyLinkedList()  


{  



Student data[]={{"090313018","Silvester",45.4},{"090313018","捐赠",45.4},{"090313018","版主",45.6}};  



SinglyLinkedList<Student> m(data,3);  


Student t;  



std::cout<<(m.isEmpty()?"不为空！":"该链表为空！")<<std::endl;  




std::cout<<"长度："<<m.length()<<std::endl;  




std::cout<<"移除2个学生"<<m.remove(1,t)<<std::endl;  




std::cout<<"t:"<<t<<std::endl;  




std::cout<<"2个学生信息"<<m.getNode(1)<<std::endl;  




Student s={"415646","fdsfs",453.1};  




std::cout<<m.get(1)<<m.set(1,s)<<m.insert(5,s)<<std::endl;  



}  


voidmain()  


　{  


_TestToSinglyLinkedList();  



system("pause");  



}

C++数据结构之单链表