C++单链表的创建与操作

清疚 2022-05-29 09:38 198阅读 0赞

链表是一种动态数据结构，他的特点是用一组任意的存储单元（可以是连续的，也可以是不连续的）存放数据元素。  
链表中每一个元素成为“结点”，每一个结点都是由数据域和指针域组成的，每个结点中的指针域指向下一个结点。Head是“头指针”，表示链表的开始，用来指向第一个结点，而最后一个指针的指针域为NULL(空地址)，表示链表的结束。  
可以看出链表结构必须利用指针才能实现，即一个结点中必须包含一个指针变量，用来存放下一个结点的地址。  
结点中只有一个next指针的链表称为单链表，这是最简单的链表结构。  
首先定义一个结构体，用于表示链表的结点。

struct node{
        int data;
        node *next;
    };

然后建立一个单链表的类。

node* list::Create()
    {
        node *p,*s;
        int x=0,cycle=1;
        while (cin>>x)
        {
            s = new node;
            s->data = x;
            if (NULL == head)
            {
                head = s;
            }
            else
            {
                p->next = s;
            }
            p = s;
        }
        p->next=NULL;
        if(NULL!=head)
            cout<<"创建成功！"<<endl;
        else
            cout<<"没有数据输入！"<<endl;
        return head;
    }

用以输出元素

void list::Output()
    {
        cout<<"\n==========输出刚才的数据=============\n"<<endl;
        node *p = head;
        while(p != NULL){
            cout<<p->data<<endl;
            p=p->next;
        }
    }

计算该链表的长度

int list::Length()
    {
        int cnt = 0;
        node *p = head;
        while(p != NULL){
            p=p->next;
            ++cnt;
        }
        return cnt;
    }

删除某个元素时，如果是head结点时，

void list::Delete(const int aDate)
    {
        node *p = head,*s;
        while (aDate!=p->data&&p->next!=NULL)
        {
            s=p;// 直到找出相等的结点跳出循环 s存储前一个结点，p存储当前结点
            p=p->next;
        }
        if (aDate == p->data)
        {
            if (p == head)
            {
                head = p->next;
            }
            else
            {
                s->next = p->next;
            }
            delete p;
        }
        else
        {
            cout<<"没有找到这个数据！"<<endl;
        }
    }

未完待续。。。。