《c++链表基本操作资料》由会员分享，可在线阅读，更多相关《c++链表基本操作资料（12页珍藏版）》请在金锄头文库上搜索。
1、C+链表基本操作我们知道，数组式计算机根据事先定义好的数组类型与长度自动为其分配一连续的存储单元，相同数组的位置和距离都是固定的链表是一种动态数据结构，他的特点是用一组任意的存储单元（可以是连续的，也可以是不连续的）存放数据元素。链表中每一个元素成为“结点”，每一个结点都是由数据域和指针域组成的，每个结点中的指针域指向下一个结点。Head是“头指针”，表示链表的开始，用来指向第一个结点，而最后一个指针的指针域为NULL(空地址)，表示链表的结束。可以看出链表结构必须利用指针才能实现，即一个结点中必须包含一个指针变量，用来存放下一个结点的地址。实际上，链表中的每个结点可以用若干个数据和若干个指针
2、。结点中只有一个指针的链表称为单链表，这是最简单的链表结构。struct Nodeint Data;Node*next;这里用到了结构体类型。其中，*next是指针域，用来指向该结点的下一个结点；Data是一个整形变量，用来存放结点中的数据。当然，Data可以是任何数据类型，包括结构体类型或类类型。在此基础上，我们在定义一个链表类list，其中包含链表结点的插入，删除，输出等功能的成员函数。class listNode*head;public:list()head=NULL;void insertlist(int aDate,int bDate);/链表结点的插入void Deletelist
3、(int aDate);/链表结点的删除void Outputlist();/链表结点的输出Node*Gethead()return head;2 链表结点的访问由于链表中的各个结点是由指针链接在一起的，其存储单元文笔是连续的，因此，对其中任意结点的地址无法向数组一样，用一个简单的公式计算出来，进行随机访问。只能从链表的头指针（即head）开始，用一个指针p先指向第一个结点，然后根据结点p找到下一个结点。以此类推，直至找到所要访问的结点或到最后一个结点（指针为空）为止。下面我们给出上述链表的输出函数；void list:outputlist()Node*current=head;while(c
4、urrent!=NULL)coutDatanext;coutData=bDate; /设b为此结点p=head; if(head=NULL) /若是空表，使b作为第一个结点 head=s; s-next=NULL; else if(p-Data=aDate) /若a是第一个结点 s-next=p; head=s; else while(p-Data!=aDate&p-next!=NULL)/查找结点a q=p; p=p-next; if(p-Data=aDate) /若有结点a q-next=s; s-next=p; else /若没有结点a； p-next=s; s-next=NULL; 4
5、 链表结点的删除如果要在链表中删除结点a并释放被删除的结点所占的存储空间，则需要考虑下列几种情况。（1） 若要删除的结点a是第一个结点，则把head指向a的下一个结点。（2）若要删除的结点a存在于链表中，但不是第一个结点，则应使a得上一个结点a_k-1的指针域指向a的下一个结点a_k+1。（3） 空表或要删除的结点a不存在，则不做任何改变。void list:deletelist(int aDate) /设aDate是要删除的结点a中的数据成员Node*p,*q; /p用于指向结点a,q用于指向结a的前一个结点p=head;if(p=NULL) /若是空表return;if(p-Data=aD
6、ate) /若a是第一个结点head=p-next;delete p;elsewhile(p-Data!=aDate&p-next!=NULL) /a既不是头结点也不是终结点，则查找结点aq=p;p=p-next;if(p-Data=aDate) /若有结点aq-next=p-next;delete p;例题；利用以上三个链表操作成员函数insertlist,deletelist.outputlist,可形成以下的简单链表操作#includeiostream.hstruct Nodeint Data;Node*next;class listNode*head;public:list()head
7、=NULL;void insertlist(int aData,int bData);void deletelist(int aData);void outputlist();Node*gethead()return head;void list:insertlist(int aData,int bData) /设aData是结点a中的数据，bData是结点b中的数据Node*p,*q,*s; /p指向结点a，q指向结点a_k，s指向结点bs=(Node*)new(Node); /动态分配一个新结点s-Data=bData; /设b为此结点p=head;if(head=NULL) /若是空表，
8、使b作为第一个结点head=s;s-next=NULL;elseif(p-Data=aData) /若a是第一个结点s-next=p;head=s;elsewhile(p-Data!=aData & p-next!=NULL)/查找结点aq=p;p=p-next;if(p-Data=aData) /若有结点aq-next=s;s-next=p;else /若没有结点a；p-next=s;s-next=NULL;void list:deletelist(int aData) /设aData是要删除的结点a中的数据成员Node*p,*q; /p用于指向结点a,q用于指向结a的前一个结点p=head
9、;if(p=NULL) /若是空表return;if(p-Data=aData) /若a是第一个结点head=p-next;delete p;elsewhile(p-Data!=aData&p-next!=NULL) /查找结点aq=p;p=p-next;if(p-Data=aData) /若有结点aq-next=p-next;delete p;void list:outputlist()Node*current=head;while(current!=NULL)coutDatanext;coutendl;void main()list A,B;int Data10=25,41,16,98,5
10、,67,9,55,1,121;A.insertlist(0,Data0); /建立链表A首结点for(int i=1;i10;i+)A.insertlist(0,Datai); /顺序向后插入coutn链表A:;A.outputlist();A.deletelist(Data7);cout删除元素Data7后;A.outputlist();B.insertlist(0,Data0); /建立链表B首结点for(i=0;iData,Datai); /在首结点处顺序向后插入coutn链表B:;B.outputlist();B.deletelist(67);cout删除元素67后;B.outputlist();程序运行结果为链表A；25，41，16，98，5，67，9，55，1，121删除元素Data7后；25，41，16，98，5，67，9，1，121链表B；121，1，55，9，67，5，98，16，41，25，删除元素67后；121，1，55，9，5，98，16，41，25，下面是杨辉三角的代码：#include #include using namespace std;int main()const int n=11;int i,j,ann;for(i=1;in;i+)aii
