江小南

V1

2022/12/07阅读:17主题:萌绿

【408篇】C语言笔记-第十二章(单链表的删除&考研真题实战)

第一节:单链表删除操作

删除操作流程图:

通过流程图,我们写出代码:

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;
typedef struct LNode{
    ElemType data;
    struct LNodenext;
}LNode,*Linklist;

// 尾插法新建链表
Linklist list_tail_insert(Linklist &L){
    int x;
    L= (Linklist)malloc(sizeof(LNode)); // 带头结点的链表
    LNode *s,*r=L; // 写成LinkList s,r=L;也可以。r代表链表表尾结点,指向链表尾部
    scanf("%d",&x);
    while (x!=9999){
        s= (LNode*)malloc(sizeof(LNode));
        s->data=x;
        r->next=s;  // 让r指针指向新的尾部
        r=s; // 让r本身指向新的尾部
        scanf("%d",&x);
    }
    r->next=NULL// 尾结点的next指针赋值为NULL
    return L;
}

// 按序号查找结点值
Linklist GetElem(Linklist L,int i){
    int j=0;
    if(i<0){
        return NULL;
    }
    while (L && j<i){
        L=L->next;
        j++;
    }
    return L;
}

// 删除某个位置元素
bool ListDelete(Linklist L,ElemType i){
    Linklist p=GetElem(L,i-1);
    if(NULL==p){
        return false;
    }
    Linklist q;  // 用来存储要删除的节点地址
    q=p->next;
    p->next=q->next; // 断链
    free(q); // 释放空间
    return true;
}

// 打印链表中每个结点的值
void print_list(Linklist L){
    L=L->next; // 头结点指向第一个指针
    while (L!=NULL){
        printf("%3d",L->data);
        L=L->next; // 指向下一个指针
    }
    printf("\n");
}

int main() {
    Linklist L,search;  // L仅表示链表头,是结构体指针类型
    list_tail_insert(L);
    print_list(L); // 打印链表
    ListDelete(L,4);  // 删除第4个位置元素
    print_list(L);
    return 0;
}
F:\Computer\Project\practice\12\12.1-head-insert\cmake-build-debug\11_1_head_insert.exe
1 2 3 4 5 9999
  1  2  3  4  5
  1  2  3  5

进程已结束,退出代码为 0

对于删除元素的逻辑,可以用一张图来表示:

分析

  1. 头指针的数据域始终为空,位置不动。
  2. 删除第i个元素实际上是将原本i元素的next赋值给i-1个位置元素的next。也叫作断链。这样第i-1个元素就和第i+1个元素链接起来,形成链表。
  3. 将要删除的元素地址保存起来,并做释放空间处理。

第二节:考研真题

解读

  1. 空间复杂度为O(1),即不能额外申请空间。
  2. 找到链表的中间结点,前面一半是链表L,将链表的后半部分给一个新的头结点L2,然后将链表L2原地逆置。
  3. 将L和逆置后的L2链表按照L'进行合并。

1. 解题设计

第一阶段:如何找到链表的中间结点

定义两个指针pcur和ppre,让pcur指针每次走两步,ppre指针每次走一步,这样当pcur指针走到最后,那么ppre指针刚好在中间。指针p每次循环走两步,因此每一步都要注意判断是否为NULL。

第二阶段:后一半链表设置为了L2,如何让L2原地逆置

首先我们要判断链表是否为空,如果为空,就返回。如果只有一个结点,也不需要逆置,直接返回。

  1. 链表原地逆置,我们需要使用3个指针,分别为r,s,t,他们分别指向链表的1,2,3的位置,也就是前3个结点。
  2. 让s->next=r,这样2号结点就指向了1号结点,完成了逆置。
  3. 这是,r=s,s=t,t=t->next,通过这个操作,r,s,t分别指向了链表的2,3,4位置结点。在循环执行第2步。当t为NULL时,结束循环。
  4. 循环结束时,t为NULL,这是s是最后一个结点,r是倒数第二个结点,需要再执行一次s->next=r。
  5. 最后需要L2->next->next=NULL;因为原有链表的头结点变成了链表的最后一个结点,最后一个结点的next需要为NULL,这时让L2指向s,因为s是原链表最后一个结点,完成逆置后,就是第一个节点,因此链表头结点L2指向s。

第三阶段:将L和L2链表合并,合并时轮流放入一个结点

我们依然需要3个指针,pcur,p,q,让pcur始终指向新链表尾部,初始化为pcur=L->next。使用p指针始终指向链表L待放入的节点,初始化为p=L->next(因为L的第一个结点就是新链表的第一个结点)。q始终指向L2待放入的节点,初始化为q=L2->next。

开启循环,while(NULL!=p&&NULL!=q),首先将pcur->next=q,然后q=q->next和pcur=pcur->next,接着pcur->next=p,然后p=p->next和pcur=pcur->next。直到循环结束。循环结束后,有可能L还剩余一个结点,也可能L2还剩余一个结点,但是只会有一个剩余的节点。判断p不为NULL,把p放入,如果q不为NULL,把q放入即可。

2. 代码实现

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;
typedef struct LNode{
    ElemType data;
    struct LNodenext;
}LNode,*Linklist;

// 尾插法新建链表
Linklist list_tail_insert(Linklist &L){
    int x;
    L= (Linklist)malloc(sizeof(LNode)); // 带头结点的链表
    LNode *s,*r=L; // 写成LinkList s,r=L;也可以。r代表链表表尾结点,指向链表尾部
    scanf("%d",&x);
    while (x!=9999){
        s= (LNode*)malloc(sizeof(LNode));
        s->data=x;
        r->next=s;  // 让r指针指向新的尾部
        r=s; // 让r本身指向新的尾部
        scanf("%d",&x);
    }
    r->next=NULL// 尾结点的next指针赋值为NULL
    return L;
}

// 寻找中间结点并返回第二个链表
void find_middle(Linklist L,Linklist &L2){
    L2=(Linklist) malloc(sizeof(LNode));
    Linklist pcur,ppre;
    pcur=ppre=L->next;  // 初始化双指针均为L的第一个结点
    while (pcur!=NULL){
        pcur=pcur->next;  // pcur走第一步
        if(NULL==pcur){
            break;
        }
        pcur=pcur->next;  // pcur走第二步
        if(NULL==pcur){
            break;
        }
        ppre=ppre->next;  // ppre走一步
    }
    L2->next=ppre->next;
    ppre->next=NULL;
}

// 原地逆转L2
void reverse(Linklist &L2){
    Linklist r,s,t;
    r=s=t=L2->next;
    if(NULL==r){ // 链表为空
        return;
    }
    s=t=t->next;
    if(NULL==t){  // 链表只有一个结点
        return;
    }
    t=t->next;
    while (NULL!=t){
        s->next=r;
        r=s;  // 三个节点依次向后移动
        s=t;
        t=t->next;
    }
    s->next=r;
    L2->next->next=NULL;  // 链表的第一个结点的next要为NULL
    L2->next=s;  // s是头部
}

// 合并链表
void merge(Linklist L,Linklist L2){
    Linklist pcur,p,q;
    pcur=p=L->next;
    q=L2->next;
    p=p->next;
    while (q!=NULL && p!=NULL){
        pcur->next=q; // 链表上给过来一个结点
        q=q->next; // q往后走一步,q在L2上
        pcur=pcur->next; // 新链表往后走一个
        pcur->next=p;   // 链表L2上给过来一个结点
        p=p->next; // q往后走一步,它在L上
        pcur=pcur->next; // 新链表往后走一步
    }
    if(NULL!=q){
        pcur->next=q;
    }
    if(NULL!=p){
        pcur->next=p;
    }
}

// 打印链表中每个结点的值
void print_list(Linklist L){
    L=L->next; // 头结点指向第一个指针
    while (L!=NULL){
        printf("%3d",L->data);
        L=L->next; // 指向下一个指针
    }
    printf("\n");
}

int main() {
    Linklist L,search;  // L仅表示链表头,是结构体指针类型
    list_tail_insert(L);  // 尾插法新建列表
    print_list(L); // 打印链表
    Linklist L2=NULL// 寻找中间结点并返回第二个链表
    find_middle(L,L2);
    printf("---------------------\n");
    print_list(L);
    print_list(L2);
    printf("---------------------\n");
    reverse(L2);   // L2原地逆置
    print_list(L2);
    printf("---------------------\n");
    merge(L,L2);  // 重新合并链表
    free(L2);
    print_list(L);
    return 0;
}
F:\Computer\Project\practice\12\12.2-head-insert\cmake-build-debug\11_1_head_insert.exe
1 2 3 4 5 6 7 8 9 9999
  1  2  3  4  5  6  7  8  9
---------------------
  1  2  3  4  5
  6  7  8  9
---------------------
  9  8  7  6
---------------------
  1  9  2  8  3  7  4  6  5

进程已结束,退出代码为 0

3. 时间复杂度分析

find_middle函数有一个while循环,因为pcur每次移动两个结点,因为循环次数为n/2,忽略首项系数,时间复杂度为O(n)。

reverse函数值遍历了L2链表,遍历长度为n/2,所以时间复杂度为O(n)。

merge函数循环遍历次数也是n/2,因此时间复杂度为O(n)。

三个函数总的运行次数为1.5n,忽略首项系数,因此时间复杂度为O(n)。

分类:

后端

标签:

C++

作者介绍

江小南
V1