数据结构之c++版本单链表基本操作

偏执的太偏执、 2023-10-18 17:16 7阅读 0赞

**单链表的建立（以下均为附加头结点的单链表的操作）需要两个基本类；一：结点类（Linknode），二：链表类（List）  
下面是建立链表的结点类和链表类基本写法：**

#include <iostream>
    #include <stdio.h>
    #include<algorithm>
    using namespace std;
    class List; //前视定义,否则友元无法定义
    class LinkNode
    {
        
     friend  List; //链表结点类的定义
     private:
       LinkNode *link;
       int data;
     public:
       LinkNode (LinkNode *ptr = NULL)    {
        link=ptr;}
       LinkNode(const int & item, LinkNode *ptr = NULL){
          data=item;link=ptr;}
       ~LinkNode(){
        };
    };
    class List
    {
        
    private:
        LinkNode *first;
        int length;
    public:
        List();
        void inputFront();
        void inputRear();
        void output();
        void Insert(int i)；
        int Remove(int i,int x);
        void Sort(List A);
    };

给出构造函数List()

List::List()
    {
        
        first = new LinkNode;
        first->link = NULL;
    }

在给出前插法和后插法两种输入数据的方法之前先把输出函数output()完成如下

void List::output()
    {
        
        LinkNode *p = first->link;
        while(p!=NULL)
        {
        
            cout<<p->data<<endl;
            p = p->link;
        }
    }

**1.前插法建立单链表**

void List::inputFront()
    {
        
        int m;
        cin>>m;
        for(int i=0;i<m;i++)
        {
        
            int x;
            cin>>x;
            LinkNode *p = new LinkNode(x);
            p->link = first->link;
            first->link = p;
        }
    }

main函数如下

int main()
    {
        
        List A;
        A.inputFront();
        A.output();
        return 0;
    }

输出结果如下：  
![可知][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODIxOTYz_size_16_color_FFFFFF_t_70]可知输入五个元素 1 2 3 4 5 最后倒序输出了

**2.后插法建立单链表**

void List::inputRear()
    {
        
        int m;
        cin>>m;
        length = m;
        for(int i=0;i<m;i++)
        {
        
            int x;
            cin>>x;
            LinkNode *p = new LinkNode(x);
            LinkNode *temp = first;
            while(temp->link!=NULL)
            {
        
                temp = temp->link;
            }
            temp->link = p;
            p->link = NULL;
        }
    }

main函数调用inputRear() 并且output 输出结果如下  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODIxOTYz_size_16_color_FFFFFF_t_70 1]  
当输出5个数为1 2 3 4 5时，顺次输出。

**3.指定位置插入一个结点**  
如果我们需要在第i个位置插入一个结点的话那么操作如下

void List::Insert(int i)
    {
        
        int x;
        cin>>x;
        LinkNode *p = first;
        for(int j=0;j<i-1;j++)
        {
        
            p = p->link;
        }
        LinkNode *newNode = new LinkNode(x);
        newNode->link = p->link;
        p->link = newNode;
        length++;
    }

在测试中测试在第二个位置插入一个数字 main函数如下

int main()
    {
        
        List A;
       // A.inputFront();
        A.inputRear();
        A.output();
        cout<<"-------------------------"<<endl;
        A.Insert(2);
        A.output();
        return 0;
    }

测试结果如下  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODIxOTYz_size_16_color_FFFFFF_t_70 2]  
**4.删除链表中第i个元素**  
具体操作如下

int List::Remove(int i,int x)
    {
        
        LinkNode *current = first;
        for(int j=0;j<i-1;j++)
        {
        
            current = current->link;
        }
        LinkNode *del = current->link;
        current->link = del->link;
        x = del->data;
        delete del;
        length--;
        return x;
    }

main函数如下

int main()
    {
        
        List A;
       // A.inputFront();
        A.inputRear();
        A.output();
        cout<<"-------------------------"<<endl;
        A.Insert(2);
        cout<<"插入第二个数以后的结果是："<<endl;
        A.output();
        int x;
        cout<<"删除操作↓"<<endl;
        cout<<"删除的第四个数是："<<A.Remove(4,x)<<endl;
        cout<<"删除第四个数以后的结果是："<<endl;
        A.output();
        return 0;
    }

结果如下  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODIxOTYz_size_16_color_FFFFFF_t_70 3]  
**5.排序操作**  
以从小到大排序为例  
代码如下

void List::Sort(List A)
    {
        
        LinkNode *Front = NULL;
        LinkNode *Rear = NULL;
        Front = first->link;
        while(Front!=Rear)
        {
        
            while(Front->link!=Rear)
            {
        
                if(Front->data>Front->link->data)
                {
        
                    int tmp = Front->data;
                    Front->data = Front->link->data;
                    Front->link->data = tmp;
                }
                Front = Front->link;
            }
            Rear = Front;
            Front = first->link;
        }
    }

main函数中只需要调用A.Sort(A);即可。  
**6.连接**

void List::append(List A,List B)
    {
        
        LinkNode *p = A.first;
        LinkNode *q = B.first;
        while(p->link!=NULL)
        {
        
            p = p->link;
        }
        p->link = q->link;
    }

**7.删除链表中重复元素**

void List::Union(List A)
    {
        
        LinkNode *p,*q;
        p = first;
        q = p->link;
        while(q)
        {
        
            if(p->data != q->data)
            {
        
                p = q;
                q = q->link;
            }
            else
            {
        
                p->link = q->link;
                free(q);
                q = p->link;
            }
        }
    }

**8.并集可由6和7实现**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODIxOTYz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190418140015424.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODIxOTYz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODIxOTYz_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2019041814081160.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODIxOTYz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODIxOTYz_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20190418142950883.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODIxOTYz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODIxOTYz_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20190418144913565.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODIxOTYz,size_16,color_FFFFFF,t_70