链表的常用算法c++

绝地灬酷狼 2022-11-29 12:30 149阅读 0赞

> 结点定义：struct node  
> 创建无序链表：Create()  
> 遍历链表：Print() Search()  
> 删除结点：Delete\_one\_node()  
> 释放链表：Delete\_chain()  
> 插入一个结点：Insert()  
> 创建有序链表：Create\_sort()

#include <iostream>
    #include<iomanip>
    using namespace std;
    
    /*不带头节点*/
    
    //定义链表结点结构
    struct node{
        
        int data;
        node *next;
    };
    
    //动态创建无序链表,函数返回值为链表的首指针;程序运行时，依次输入链表中各结点的数据，以输入'-1'表示结束。
    node * Create(){
        
        node *p1, *p2 = NULL, *head;//p1指向新开辟的结点，p2指向建立过程中的链表尾结点，head指向链表首结点
        int a;
        head = NULL;//初始时，设置head为空指针
    
        cout << "正在创建一条无序链表...\n";
        cout << "请输入一个正整数，以-1结束：";
        cin >> a;//输入第一个数据
    
        while(a != -1){
        
            p1 = new node;//动态申请一个新结点 <指针变量> = new <数据类型> 程序结束前必须通过delete释放
            p1->data = a;//给新结点数据域赋值
    
            if(head == NULL)//只有第一次加入结点时本条件成立
                head = p2 = p1;//加入首结点
            else{
        
                p2->next = p1;//连入中间结点
                p2 = p1;
            }
    
             cout << "请输入一个正整数，以-1结束：";
             cin >> a;//输入下一个数据
    
        }
    
        if(head != NULL){
        //如建立的不是空链表，则需要进行尾结点处理
    
            p2->next = NULL;
        }
    
        return head;//返回链表首指针
    }
    
    
    //遍历链表：输出链表中各结点数据值
    
    void Print(const node *head){
        //常量指针，即指向常量的指针，目的是保护指针所指向的结点值不被改变
        const node *p;//p是指向常量的指针
    
        p = head;
        cout << "链表中各节点数据为：";
    
        while(p != NULL){
        
            cout << setw(4) << p->data;
    
            p = p->next;
        }
        cout << endl;
    
    
    }
    
    //遍历链表：在链表中顺序查找某结点的值，如果存在则返回该结点的指针，否则返回空指针
    
    const node * Search(const node *head, int x){
        //函数的返回值依然是指向常量的指针，目的是在调用Search()的主函数中保护查找到的节点
        const node *p;//p是指向常量的指针
    
        p = head;
        while(p != NULL){
        
    
            if(p->data == x)
               return p;//若找到，则返回该节点的指针
            p = p->next;
        }
        return NULL;//若找不到，则返回空指针
    }
    
    
    //删除结点：删除链表中结点的data为num的结点，为简单起见，若有多个，则只删除第一个
    /*算法整体思路：首先查找待删除的结点（由p1指向），若找到则删除它，若未找到则无需删除：
    1）若待删除的结点是首结点，此时需要重新设置首指针 2）若待删除的结点是其他结点，则不需要修改首指针*/
    node *Delete_one_node(node *head, int num){
        
        node *p1, *p2 = NULL;//指针p1向下一结点方向(尾结点方向）依次查找待删除的结点，p2始终指向p1的前一个结点
    
        if(head == NULL){
        //判断链表是否为空
    
            cout << "链表为空，无结点可删除!\n";
            return NULL;
        }
    
        p1 = head;
        while(p1->data != num && p1->next != NULL){
        //循环查找待删除结点,未找到且链表未遍历完，则继续循环
    
            p2 = p1;//p2记住p1
            p1 = p1->next;//p1指向后一个结点，p2指向的结点在p1指向的结点之前
    
        }
    
        if(p1->data == num){
        //找到了待删结点，由p1指向
    
            if(p1 == head)//找到的是首结点
                head = p1->next;//重新设置head的指向
            else//找到的不是首结点
                p2 = p1->next;//不管是中间结点还是尾结点，都只需要将p2的next指针绕过p1结点指向p1的下一个结点即可
    
            delete p1;//无论找到的结点是否为首结点，结点本身的空间是要释放的
            cout << "删除了一个结点！\n";
    
        }
        else//未找到待删除结点
            cout << num << " 链表上没有找到待删除的结点！\n";
    
        return head;
    
    }
    
    //插入一个结点（对于升序链表）,插入结点时，若原链表是空链表，则构造一个具有一个结点的链表，首结点指向该结点即可
    //若原链表是非空的：1）插入在原链表首结点之前 2）插入在链表中间 3）插入在链表尾结点之后
    node *Insert(node *head, node *p){
        
        node *p1, *p2 = NULL;//p2为p1的前一个结点,p1代表当前在处理的结点
    
        if(head == NULL){
        //原链表为空链表
    
            head = p;
            p->next = NULL;
    
            return head;
        }
    
        p1 = head;
    
        while((p->data) > (p1->data) && p1->next != NULL){
        //寻找待插入节点的位置，直到找到或链表已经遍历完
    
            p2 = p1;//p2记住p1
            p1 = p1->next;//p1指向后一个结点，p2指向的结点在p1指向的结点之前
    
        }
    
        if((p->data) <= (p1->data)){
        //插入在p1之前
    
            p->next = p1;//但p1有可能是首结点，所以需要进一步判断
    
            if(head == p1) head = p;//插在链表首部
    
            else p2->next = p;//插在链表中间
        }
        else{
        //插在链表末尾
    
            p1->next = p;
            p->next = NULL;
    
        }
    
        return head;
    
    }
    
    //创建有序链表，基于Insert()方法->升序:
    //循环输入数值，建立一个新结点，其数据域的值就是输入的数值，调用插入结点函数Insert()，
    //将该新结点插入到链表中，使链表始终保持升序
    node *Create_sort(){
        
        node *p, *head = NULL;
        int a;
        cout << "正在创建建一条有序链表...\n";
        cout << "请输入一个整数，以-1结束：";
        cin >> a;//输入第一个结点的值
    
        while(a != -1){
        //当输入-1时结束创建过程
                
            p = new node;//创建一个新结点，p指向它
            p->data = a;
            head = Insert(head, p);//将p结点插入head链表，保持升序
            cout << "请输入一个整数，以-1结束：";
            cin >> a;//输入下一结点的值
    
        }
        return head;//返回升序链表首指针
    }
    
    
    //释放链表：释放链表所有结点的空间
    void Delete_chain(node * head){
        
        node *p;
        while(head){
        //等价于 head ！= NULL
            p = head;
            head = head->next;
            delete p;//delete <指针变量> ：释放一个由<指针变量>指向的变量的空间
    
        }
    
        cout << "释放了链表" << endl;
    
    }
    
    
    
    int main()//测试以上所有函数
    {
        
        node * head;
        int num;
        head = Create();
        Print(head);
    
        cout << "请输入待删除结点上的整数：";
        cin >> num;
        head = Delete_one_node(head, num);//此函数返回node类型的指针，即头结点的指针
        Print(head);
    
        cout << "请输入要查找的整数：";
        cin >> num;
        if(Search(head, num) != NULL)
            cout << num << " 在链表中\n";
        else
            cout << num << " 不在链表中\n";
        Delete_chain(head);//一定要在测试函数末尾释放链表，否则后果不可预测
    
        head = Create_sort();//创建有序链表
        Print(head);
        Delete_chain(head);//一定要在测试函数末尾释放链表，否则后果不可预测
    
        return 0;
    }