单链表基本操作总结

绝地灬酷狼 2022-08-02 00:16 339阅读 0赞

**链表基本概念：**  
**链表：**线性表的链式存储。  
**数据域：**存储数据信息。即数据。  
**指针域：**存放下一节点的位置信息。即该指针指向下一节点。

**单链表：每一个节点node：一个数据域 + 一个指针域。**  
**头节点：**  
1、数据域可以存放线性表长度等公共信息。  
2、指针域，指向第一个节点（数据域）的位置。  
3、**头结点不一定是链表的必须元素。**不过有了头结点，对第一个元素节点前插入和删除元素，就和其它节点一致了。  
4、头结点是为了操作的同一和方便设立的，其数据域一般无意义，也可存放链表长度。  
**头指针：**指向第一个结点的指针。  
**最后一个节点：**数据域存放数据；指针域为空，即NULL。  
**若线性表为空，则头节点的指针域为空。**  
// **循环链表：**将单链表中的**终端节点的指针由空指针改为指向头结点**，就使整个单链表形成一个环，这种头尾相接的单链表简称循环链表。  
// **双向链表：**是在单链表的每个节点中，**再设置一个指向其前驱节点的指针域**。

单链表基本操作有：创建、输出、测长、插入、删除、逆置、排序等。

**单链表结构定义代码：**

typedef struct Node{
        int data;
        struct Node *next;
    }ListNode;

**创建单链表操作：**

/**创建链表*/
    ListNode * Create_list(int n)     // 注意这里函数返回值为一个指向Node的指针，n表示几个节点
    {
        int elem,i;
        i = 1;
        ListNode *head, *current, *temp;   /*current：代表一个当前节点，它的下一节点是你正要创建的；temp：代表你正要创建的节点。*/
        head = new ListNode;
        head->next = NULL;
        head->data = n;
        current = head;
    
        while(i <= n)   /*尾插法：即新节点放在尾部*/
        {
            cout << "please input elem: " << endl;
            cin >> elem;
    
            temp = new ListNode;
            temp->data = elem;
            temp->next = NULL;
            current->next = temp;
            current = temp;
            i++;
        }
    
        return head;
    }

**输出操作：**

/**输出链表*/
    int Output_list(ListNode *head)
    {
        ListNode *p;
        p = head->next;
        if(p == NULL)
        {
            cout << "The List is NULL" << endl;
            return 0;
        }
        do{
            cout << p->data << ' ';
            p = p->next;
        }while(p != NULL);           // 这里需要加“；”
    
        cout << endl;
    
        return 0;
    }

**测一个链表的节点数，即长度：**

/**测长度*/
    int Length_test(ListNode *head)
    {
        ListNode *p;
        int i = 0;
        p = head->next;
    
        while(p != NULL)
        {
            i++;
            p = p->next;
        }
        cout << "The length of list is " << i << endl;
        return 0;
    }

**插入节点操作：**

/**在第i个节点后插入一个节点，elem：表示你要插入的数据*/
    ListNode * Insert_node(ListNode *head,int elem,int i)
    {
        int j = 0;
        ListNode *p,*temp;
        temp = head->next;
        /*错误写法
        while(NULL != temp) 在找到 j 后没有跳出循环
        {
            j++;
            if(j <= i)
                temp = temp->next;
        }
        */
        while(NULL != temp)
        {
            j++;
            if(j >= i)   /**指针停在第i个节点之前*/
                break;
            temp = temp->next;
        }
        if(temp == NULL)
        {
            cout << "There is no i" << endl;
            return head;
        }
        p = new ListNode;
        p->data = elem;
        p->next = temp->next;
        temp->next = p;
    
        head->data = head->data + 1;   /**插入一个结点，头结点数据保存的链表长加一*/
    
        return head;
    }

**删除操作：**

/**删除第i个结点*/
    ListNode * Delete_node(ListNode *head,int i)
    {
        int j = 0;
        ListNode *temp,*pre_temp;
        temp = head->next;
    
        while(NULL != temp)
        {
            j++;
            if(j >= i)
                break;
            pre_temp = temp; /**保存之前节点*/
            temp = temp->next;
        }
        if(temp == NULL)
        {
            cout << "There is no i" << endl;
            return head;
        }
        pre_temp->next = temp->next;
        /**这里不能写成temp = temp->next; 因为下面有 delete temp;会将后面的节点删掉*/
    
        delete temp;
    
        head->data -= 1;   /**删掉一个结点，头结点数据保存的链表长减一*/
    
        return head;
    }

**逆置操作：**

/**单链表逆置，将头结点后的节点一个个断开，使用头插法插入在头结点后*/
    ListNode * Reverse_list(ListNode *head)
    {
        if(NULL == head)
            return head;
        if(NULL == head->next)
            return head;
        if(NULL == head->next->next)
            return head;
        /**要实现逆置，除了头结点外，至少需要2个数据节点*/
    
        ListNode *curr, *temp;
        curr = head->next;    /**curr用来保存断开后的那一串*/
        head->next = NULL;    /**头结点与后面结点断开*/
    
        while(NULL != curr)
        {
            temp = curr->next;         /**temp起临时代替curr的作用*/
            curr->next = head->next;   /**头插法*/
            head->next = curr;
            curr = temp;               /**temp将功能还给curr*/
        }
        return head;
    }

**单链表排序（使用冒泡排序法）：此排序算法，仅交换了数据，没有交换结点**

void Swap_data(int &a,int &b)   /**这里必须要加引用符，不然交换没效果*/
    {
        int temp;
        temp = a;
        a = b;
        b = temp;
    }
    ListNode * Sort_list(ListNode *head)
    {
        int i,len;
        ListNode *p;
        len = head->data;
        p = head->next;
        if(NULL == p)
            cout << "list is null" << endl;
        for(i = 1; i <= len; i++)
        {
            while(NULL != p->next)
            {
                if(p->data > p->next->data)
                    Swap_data(p->data,p->next->data);
                p = p->next;
            }
            p = head->next;
        }
        return head;
    }

**一个特别的函数：用于找出单链表中间节点，在不知道节点总数的情况下**

/**不知节点总数，只遍历一次就可以求出中间结点*/
    /**这个函数有问题，只能对节点为奇数的求解，节点为偶数时，会出现p->next->next无意义的情况，使程序发生错误*/
    /*原理是：找两个指针，一个每次走一步，另一个每次走两步，当走两步的指针到结尾时，走一步的指针刚好走到中间结点处*/
    void Search_mid(ListNode *head)
    {
        ListNode *p_1,*q_2;
        ListNode *mid;
        p_1 = head->next;
        q_2 = head->next;
        while(NULL != q_2->next)
        {
            p_1 = p_1->next;
            q_2 = q_2->next->next;
            mid = p_1;
        }
        cout << "中间值为: " << mid->data << endl;
    }

**测试主函数：**

int main()
    {
        ListNode *p;
        int a=3;
        int b = 4;
        p = Create_list(5);
        cout << "The list is:" << endl;
        Output_list(p);
        Length_test(p);
    
        p = Insert_node(p,6,5);
        cout << "插入节点后:" << endl;
        Output_list(p);
        cout << "New length: " << p->data << endl;
    
        p = Delete_node(p,3);
        cout << "删除节点后:" << endl;
        Output_list(p);
    
        p = Reverse_list(p);
        cout << "逆置后:" << endl;
        Output_list(p);
    
        p = Sort_list(p);
        cout << "排序后（从小到大）:" << endl;
        Output_list(p);
    
        cout << "原ab: " << a << b << endl;
        Swap_data(a,b);
        cout << "交换后: " << a << b << endl;
    
        Search_mid(p);
    
        return 0;
    }

/*点滴积累，我的一小步O(∩\_∩)O~*/