【练习】c++删除链表倒数第K个结点和插入排序算法将单链表递增排序

青旅半醒 2023-01-13 06:18 65阅读 0赞

## 删除单链表倒数第K个结点 ##

运行结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 1]  
代码：

struct node { 
        int data;
        node* next;
    
    };
    //删除链表的倒数第k个结点
    bool delet(node*& L, int k) { 
        node* p, * q, * t;
        p = L;
        int i = 0;
        while (i < k) { 
            i++;
            p = p->next;
        }
        if (p == NULL)return false;
        q = L;
        while (p->next != NULL) { 
            p = p->next;
            q = q->next;
        }
        t = q->next;
        q->next = t->next;
        delete t;
        return true;
    }
    
    int main()
    { 
        srand(0);
        node* m = new node;
    
        m->data = rand() % 5;
        //cout << m->data;
        node* n = new node;
        n->data = rand() % 7;
        m->next = n;
    
        node* nn = new node;
    
        nn->data = rand() % 8;
        n->next = nn;
        node* jj = new node;
        jj->data = 100;
        jj->next = NULL;
        nn->next = jj;
        node* copy_m = m;
        cout << "第一个链表：";
        while (copy_m) { 
            cout << copy_m->data<<",";
            copy_m = copy_m->next;
        }
        delet(m, 2);
       copy_m = m;
        cout << "\n删除结点后链表：";
        while (copy_m) { 
            cout << copy_m->data<<",";
            copy_m = copy_m->next;
        }
    
    
    
    }

## 直接插入将单链表递增排序 ##

结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 2]

//直接插入排序
    void sort(node*& L) { 
        node* p = L->next->next;
      
        node* q;
        L->next->next = NULL;//构建只含一个数据结点的有序表
        node* pre = L;
        while (p != NULL) { 
            pre = L;//注意每次最外面的while中都要初始化pre
            q = p->next;//q保存当前p结点的后继结点
            while (pre->next != NULL && pre->next->data < p->data)
                pre = pre->next;
            p->next = pre->next;//当pre->next->data>p->data 在pre后面插入p结点 因为p的数据更小 按递增排序
            pre->next = p;
            p = q;//p指向原来的后继结点
        }
    }
    int main()
    { 
        srand(0);
        node* begin=new node;
        begin->next = NULL;
        node* m = new node;
    
        m->data = rand() % 15;
        //cout << m->data;
          m->next= begin->next;
          begin->next = m;
        node* n = new node;
        n->data = rand() % 7;
      n->next= begin->next;
      begin->next = n;
        node* nn = new node;
    
        nn->data = rand() % 20;
        nn->next = begin->next;
        begin->next = nn;
        node* jj = new node;
        jj->data = 10;
        jj->next = begin->next;
        begin->next = jj;
        node* copy_m = begin;
        cout << "第一个链表：";
        while (copy_m->next) { 
         
            cout << copy_m->next->data<<",";
            copy_m = copy_m->next;
        }
      sort(begin);
       copy_m = begin;
        cout << "\n排序结点后链表：";
        while (copy_m->next) { 
     
            cout << copy_m->next->data<<",";
            copy_m = copy_m->next;
        }
    
    
    
    }

注意，这里在自己初始化链表的时候发现：  
只有写成

while (copy_m->next) { 
     
            cout << copy_m->next->data<<",";
            copy_m = copy_m->next;
        }

时才能正确输出排序后的结果，  
如果写成

while (copy_m) { 
      copy_m = copy_m->next;
            cout << copy_m->data<<",";
           
        }

是无法得到排序后结果的。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70]: /images/20221022/597575c9bc414ccf9666e55b611b0c61.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 1]: /images/20221022/41dff0b3f3be498c91fbc1764c531581.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 2]: /images/20221022/8a9e1326f73d4203b5bc2c2a8d0530ec.png