C++链表基本操作.doc

《C++链表基本操作.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、.C++链表基本操作我们知道，数组式计算机根据事先定义好的数组类型与长度自动为其分配一连续的存储单元，相同数组的位置和距离都是固定的链表是一种动态数据结构，他的特点是用一组任意的存储单元（可以是连续的，也可以是不连续的）存放数据元素。链表中每一个元素成为“结点”，每一个结点都是由数据域和指针域组成的，每个结点中的指针域指向下一个结点。Head是“头指针”，表示链表的开始，用来指向第一个结点，而最后一个指针的指针域为NULL(空地址)，表示链表的结束。可以看出链表结构必须利用指针才能实现，即一个结点中必须包含一个指针变量，用来存放下一个结点的地址。实际上，链表中的每个结点可以用

2、若干个数据和若干个指针。结点中只有一个指针的链表称为单链表，这是最简单的链表结构。structNode{intData;Node*next;};这里用到了结构体类型。其中，*next是指针域，用来指向该结点的下一个结点；Data是一个整形变量，用来存放结点中的数据。当然，Data可以是任何数据类型，包括结构体类型或类类型。在此基础上，我们在定义一个链表类list，其中包含链表结点的插入，删除，输出等功能的成员函数。classlist{Node*head;public:list(){head=NULL;}voidinsertlist(intaDate,intbDate);//链

3、表结点的插入voidDeletelist(intaDate);//链表结点的删除voidOutputlist();//链表结点的输出Node*Gethead(){returnhead;}};2．链表结点的访问由于链表中的各个结点是由指针链接在一起的，其存储单元文笔是连续的，因此，对其中任意结点的地址无法向数组一样，用一个简单的公式计算出来，进行随机访问。只能从链表的头指针（即head）开始，用一个指针p先指向第一个结点，然后根据结点p找到下一个结点。以此类推，直至找到所要访问的结点或到最后一个结点（指针为空）为止。下面我们给出上述链表的输出函数；voidlist::outpu

4、tlist(){Node*current=head;while(current!=NULL){cout<Data<<"";current=current->next;}cout<

5、到链表的最后一个结点a_n，然后使a_n的指针域指向结点b，而b指针的指针为空。以下是链表类的结点插入函数，显然其也具有建立链表的功能。voidlist::insertlist(intaDate,intbDate)//设aDate是结点a中的数据，bDate是结点b中的数据{      Node*p,*q,*s;//p指向结点a，q指向结点a_k，s指向结点b      s=(Node*)new(Node);//动态分配一个新结点      s->Data=bDate;//设b为此结点        p=head;     if(head==NULL)//若是空表，使b作为第

6、一个结点       {           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     

7、              {                           q=p;                            p=p->next;                    }                  if(p->Data==aDate)///若有结点a                   {                         q->next=s;                          s->next=p;