C++链表基本操作.doc

C++链表基本操作
我们知道，数组式计算机根据事先定义好的数组类型与长度自动为其分配一连续的存储单元，相同数组的位置和距离都是固定的
链表是一种动态数据结构，他的特点是用一组任意的存储单元（可以是连续的，也可以是不连续的）存放数据元素。链表中每一个元素成为“结点”，每一个结点都是由数据域和指针域组成的，每个结点中的指针域指向下一个结点。Head是“头指针”，表示链表的开始，用来指向第一个结点，而最后一个指针的指针域为NULL(空地址)，表示链表的结束。可以看出链表结构必须利用指针才能实现，即一个结点中必须包含一个指针变量，用来存放下一个结点的地址。实际上，链表中的每个结点可以用若干个数据和若干个指针。结点中只有一个指针的链表称为单链表，这是最简单的链表结构。
struct Node
{
int Data;
Node*next;
};
这里用到了结构体类型。其中，*next是指针域，用来指向该结点的下一个结点；Data是一个整形变量，用来存放结点中的数据。当然，Data可以是任何数据类型，包括结构体类型或类类型。
在此基础上，我们在定义一个链表类list，其中包含链表结点的插入，删除，输出等功能的成员函数。
class list
{
Node*head;
public:
list(){head=NULL;}
void insertlist(int aDate,int bDate);//链表结点的插入
void Deletelist(int aDate);//链表结点的删除
void Outputlist();//链表结点的输出
Node*Gethead(){return head;}
};
2． 链表结点的访问
由于链表中的各个结点是由指针链接在一起的，其存储单元文笔是连续的，因此，对其中任意结点的地址无法向数组一样，用一个简单的公式计算出来，进行随机访问。只能从链表的头指针（即head）开始，用一个指针p先指向第一个结点，然后根据结点p找到下一个结点。以此类推，直至找到所要访问的结点或到最后一个结点（指针为空）为止。
下面我们给出上述链表的输出函数；
void list::outputlist()
{
Node*current=head;
while(current!=NULL)
{
cout<<current->Data<<" ";
current=current->next;
}
cout<<endl;
}
3． 链表结点的插入
如果要在链表中的结点a之前插入结点b，则需要考虑下面几点情况。
（1） 插入前链表是一个空表，这时插入新结点b后。
（2） 若a是链表的第一个结点，则插入后，结点b为第一个结点。
（3）若链表中存在a,且不是第一个结点，则首先要找出a的上一个结点a_k，然后使a_k的指针域指向b，在令b的指针域指向a，即可完成插入。
（4） 如链表中不存在a，则插在最后。先找到链表的最后一个结点a_n，然后使a_n的指针域指向结点b，而b指针的指针为空。
以下是链表类的结点插入函数，显然其也具有建立链表的功能。
void list::insertlist(int aDate,int bDate) //设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作为第一个结点
        {
            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． 链表结点的删除
如果要在链表中删除结点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==aDate) //若a是第一个结点
{
head=p->next;
delete p;
}
else
{
while(p->Data!=aDate&&p->next!=NULL) //a既不是头结点也不是终结点，则查找结点a
{
q=p;
p=p->next;
}
if(p->Data==aDate) //若有结点a
{
q->next=p->next;
delete p;
}
}
}
例题；利用以上三个链表操作成员函数insertlist,deletelist.outputlist,可形成以下的简单链表操作
#include"iostream.h"
struct Node
{
int Data;
Node*next;
};
class list
{
Node*head;
public:
list(){head=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指向结点b
s=(Node*)new(Node); //动态分配一个新结点
s->Data=bData; //设b为此结点
p=head;
if(head==NULL) //若是空表，使b作为第一个结点
{
head=s;
s->next=NULL;
}
else
if(p->Data==aData) //若a是第一个结点
{
s->next=p;
head=s;
}
else
{
while(p->Data!=aData && p->next!=NULL)//查找结点a
{
q=p;
p=p->next;
}
if(p->Data==aData) ///若有结点a
{
q->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;
if(p==NULL) //若是空表
return;
if(p->Data==aData) //若a是第一个结点
{
head=p->next;
delete p;
}
else
{
while(p->Data!=aData&&p->next!=NULL) //查找结点a
{
q=p;
p=p->next;
}
if(p->Data==aData) //若有结点a
{
q->next=p->next;
delete p;
}
}
}
void list::outputlist()
{
Node*current=head;
while(current!=NULL)
{
cout<<current->Data<<" ";
current=current->next;
}
cout<<endl;
}
void main()
{
list A,B;
int Data[10]={25,41,16,98,5,67,9,55,1,121};
A.insertlist(0,Data[0]); //建立链表A首结点
for(int i=1;i<10;i++)
A.insertlist(0,Data[i]); //顺序向后插入
cout<<"\n链表A:";
A.outputlist();
A.deletelist(Data[7]);
cout<<"删除元素Data[7]后";
A.outputlist();
B.insertlist(0,Data[0]); //建立链表B首结点
for(i=0;i<10;i++)
B.insertlist(B.gethead()->Data,Data[i]); //在首结点处顺序向后插入
cout<<"\n链表B:";
B.outputlist();
B.deletelist(67);
cout<<"删除元素67后";
B.outputlist();
}
程序运行结果为
链表A；25，41，16，98，5，67，9，55，1，121
删除元素Data[7]后；
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 <iostream>
#include <iomanip>
using namespace std;
int main()
{
const int n=11;
int i,j,a[n][n];
for(i=1;i<n;i++)
{
a[i][i]=1;
a[i][1]=1;
}
for(i=3;i<n;i++)
{
for(j=2;j<=i-1;j++)
a[i][j]=a[i-1][j-1]+a[i-1][j];
}
for(i=1;i<n;i++)
{
for(j=1;j<=i;j++)
cout<<setw(5)<<a[i][j]<<" ";
cout<<endl;
}
cout<<endl;
return 0;
}
#include <iostream,h>
#include <string.h>
struct Node
{
    int num ;
    Node *next ;
};
Node* Create() //链表创建
{
    int n=0;
    Node *p1,*p2,*head;
    p1=p2=new Node;
    cin>>p1->num;
    head=NULL;
    while (p1->num!=0)
    {
        if (n==1)
        {
            head=p1;
        }
        else
         p2->next=p1;
        p2=p1;
        p1=new Node;
        cin>>p1->num;
        n++;
    }
    p2->next=NULL;

    return head;
}

int ListLength(Node L) //链表的计数
{
Node p=L;
int count=0;
while(p->next)
{
count++;
p=p->next;
}
return count;
}

int Search(Node &L , int value) //链表的查找
{
Node p=L;
int index=0;
while(p)
{
if(p->num== value)
return index;
p=p->next;
index++;
}
return 0;
}

void Print(Node *head) //输出链表
{
    Node* p=head;
    while (p)
    {
        cout<<p->num<<" ";
        p=p->next;
    }
    cout<<endl;

}

void Destruct(Node *head) //清空链表
{
    Node *current = head, *temp = NULL;
while (current)
    {
        temp = current;
        current = current ->next;
        delete temp;
    }
}

Node *ReverseList(Node *head) //链表逆序（循环方法）
{
Node *p,*q,*r;
p=head; //一开始p指向第一个节点
q=p->next; //q指向第二个节点
while (q!=NULL) //如果没到链尾
{ //以第一次循环为例
r=q->next; //r暂时存储第三个节点
q->next=p; //没执行此句前，q->next指向第三个节点
//执行之后，q->next指向第一个节点p
p=q; //之后p指向第二个节点
q=r; //q指向第三个节点
//即...p=>q=>r...变为 ...p<=q<=r...
}
head->next=NULL; //最后原来的链头变为链尾，把它指向NULL。
head=p; //原来的链尾变成链头
return head;
}

Node *ReverseList2(Node *head) //链表逆序（递归方法）

{
    if (!head)
    {
        return NULL;
    }
    Node *temp = ReverseList2 (head->next);
    if (!temp)
    {
        return head;
    }
    head->next->next = head;
    head->next = NULL;
    return temp;
}
递归时,head可以分别用 head ，head1,head2 ...headn-1, headn来表示总共n+1个节点
temp = ReverseList2( head->next ); 此句的递归一直将参数传进来的。
Node* head 递归到 headn 然后判断下列语句：
else if( !headn->next )
{
return headn;
}
将返回值传给temp,此时temp指向链尾 ,由于在此次返回,故此次没有执行最后的else的那部分的语句,返回上一级即是 headn-1 那一级,继续执行
下面的 headn-1->next->next = headn-1;
headn-1->next = NULL; //此两句将最后两个逆序连接,
return temp;
//之后返回temp比上一层的temp即是执行temp = ReverseList2( head->next )赋值,因为递归的口都是在这里的,如果说好理解点也可以将temp来编号
同理
在返回temp后,继续执行
headn-2->next->next = headn-2;
headn-2->next = NULL;
return temp;
.....
一直到 head时 即是原链表的第一个节点,在对其head->next = NULL后,此时以 temp 所指向的节点为链头的逆序链表就形成了.
//已知两个链表head1 和head2 各自有序，请把它们合并成一个链表依然有序。（循环方法）
//(保留所有结点，即便大小相同）
Node *Merge(Node *head1 , Node *head2)
{
    if ( head1 == NULL)
        return head2 ;
    if ( head2 == NULL)
        return head1 ;
    if ( head1->num < =head2->num )
    {
        head = head1 ;
        head1= head1->next;
     }
    else
    {
        head = head2 ;
        head2 = head2->next ;
    }
    Node *temp = head ;
    while ( head1 != NULL && head2 != NULL)
    {
        if ( head1->num <= head2->num )
        {
            temp->next = head1 ;
         head1 = head1->next ;
temp =temp->next;
        }
        else
        {
            temp->next = head2;
          head2 = head2->next ;
temp =temp->next;
        }
    }
    if (head1 == NULL) temp->next = head2;
    if (head2 == NULL) temp->next = head1;
    return head;
}
//已知两个链表head1 和head2 各自有序，请把它们合并成一个链表依然有序。（递归方法）
Node *MergeRecursive(Node *head1 , Node *head2)
{
    if ( head1 == NULL )
        return head2 ;
    if ( head2 == NULL)
        return head1 ;
    Node *head = NULL ;
    if ( head1->num < head2->num )
    {
        head = head1 ;
        head->next = MergeRecursive(head1->next,head2);
    }
    else
    {
        head = head2 ;
        head->next = MergeRecursive(head1,head2->next);
    }
    return head ;
}
从递归函数的定义不难看出，这个函数定义中递归调用时形参发生改变，即是当前节点的下一个节点，每一次递归都按照这个规律逐次遍历两个有序链表的每一个节点，判断大小后使head指向数据域较小的节点，由堆栈空间的思想可知递归到最后指向NULL时才返回两个链表的某一个头节点，而此时head->next=head2，head=head1链表的最后一个节点，该语句就使得这样一个指向关系确立起来。
以上均通过理想的有序链表，即链表1的任何一个数据值都小于链表2来做分析，其他的情况讨论方式类似。
Node* Delete(Node* head , int num) //删除节点
{
    if (head==NULL)
    {
        cout<<"List is Null"<<endl;
        return head;
    }
    Node *p1,*p2;
    p1=head;
    while (p1->num!=num && p1->next)
    {  
        p2=p1;
        p1=p1->next;
    }
    if (p1->num==num)
    {
        if (p1==head)
        {
            head=p1->next;
        }
        else
            p2->next=p1->next;
    }
    else
        cout<<"Do not Find The Num "<<num<<endl;
    return head;}

Node* Insert(Node* head , int num) //插入节点
{
    Node *p0,*p1,*p2;
    p1=head;
    p0=new Node;
    p0->num=num;
    if (head==NULL)
    {
        head=p0;
        p0->next=NULL;
        return head;
    }

    while (p1->num<p0->num && p1->next)
    {
        p2=p1;
        p1=p1->next;
    }
    if (p1->num>=p0->num)
    {if (p1==head)
            head=p0;
        else
         p2->next=p0;
        p0->next=p1;
    }
    else
    {
        p1->next=p0;
        p0->next=NULL;
    }
    return head;
}
void main()
{省略不写}