• 【408篇】C语言笔记-第十一章（单链表）

    第一节：头插法新建链表

    头插法流程图：

    通过流程图，我们写出代码：

    #include 
#include 

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

// 头插法新建链表
Linklist list_head_insert(Linklist &L){
    LNode *s;
    int x;
    L= (Linklist)malloc(sizeof(LNode)); // 给头结点申请空间
    L->next=NULL; // 头指针的指针域刚开始为NULL
    scanf("%d",&x);
    while (x!=9999){
        s=(LNode*) malloc(sizeof(LNode));  // 给新数据申请一个空间
        s->data=x; // 把读取到的数据给空间中的data成员
        s->next=L->next; // 头指针原先的指针域赋值给新插入的数据指针域
        L->next=s; // 头指针指向新插入的数据指针
        scanf("%d",&x);
    }
    return L;
}

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

int main() {
    Linklist L;  // L仅表示链表头，是结构体指针类型
    list_head_insert(L);  // 输入数组可以为3 4 5 6 7 9999
    print_list(L); // 打印链表
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    F:\Computer\Project\practice\11\11.1-head-insert\cmake-build-debug\11_1_head_insert.exe
1 3 4 5 6 9999
  6  5  4  3  1
进程已结束，退出代码为 0

    • 1
    • 2
    • 3
    • 4

    对于头插法的逻辑，可以用一张图来表示：

    分析：

    1. 头指针的数据域始终为空，位置不动。
    2. 头指针的指针域每次有数据插入时会修改成插入数据的指针，而原来头指针的指针域的值会赋给新插入的数据的指针域，这样就又形成一个链表。
    3. 后插入的数据始终在链表前面。

    第二节：尾插法新建链表

    尾插法流程图：

    说明：尾插法的特点是始终让尾指针指向链表的尾部。

    通过流程图，我们写出代码：

    #include 
#include 

typedef int ElemType;
typedef struct LNode{
    ElemType data;
    struct LNode* next;
}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 print_list(Linklist L){
    L=L->next; // 头结点指向第一个指针
    while (L!=NULL){
        printf("%3d",L->data);
        L=L->next; // 指向下一个指针
    }
}

int main() {
    Linklist L;  // L仅表示链表头，是结构体指针类型
    list_tail_insert(L); // 尾插法，插入的数据可以是2 3 4 5 9999
    print_list(L); // 打印链表
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    F:\Computer\Project\practice\11\11.2-head-insert\cmake-build-debug\11_1_head_insert.exe
2 3 4 5 9999
  2  3  4  5
进程已结束，退出代码为 0

    • 1
    • 2
    • 3
    • 4

    对于尾插法的逻辑，可以用一张图来表示：

    分析：

    1. 头指针的数据域始终为空，位置不动。指针域始终指向第一个数据。
    2. r->next始终指向新的结点，到末尾时指针域赋值为NULL。
    3. 区分r本身和r->next，r->next表示r的指针域，r表示本身。
    4. 后插入的数据始终在链表后面。

    第三节：按位置查找及按值查找

    流程图：

    说明：按位置查找要注意判断查找位置是否合法。

    #include 
#include 

typedef int ElemType;
typedef struct LNode{
    ElemType data;
    struct LNode* next;
}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 && jnext;
        j++;
    }
    return L;
}

// 按值查找
LNode *LocateElem(Linklist L,ElemType e){
    while (L){
        if(L->data==e){
            return L;
        }
        L=L->next;
    }
    return NULL;
}

// 打印链表中每个结点的值
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); // 打印链表
    search=GetElem(L,2);  // 按位置查找
    if(search!=NULL){
        printf("%d\n",search->data);
    }
    search= LocateElem(L,6); // 按值查找
    if(search!=NULL){
        printf("%d\n",search->data);
    }
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    F:\Computer\Project\practice\11\11.3-head-insert\cmake-build-debug\11_1_head_insert.exe
3 4 5 6 7 8 9999
  3  4  5  6  7  8
4
6

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    第四节：往任意位置插入元素

    往任意位置插入元素流程图：

    把新结点插入到第i个位置，关键在于调用GetElem函数，拿到第i-1位置的元素地址。

    #include 
#include 

typedef int ElemType;
typedef struct LNode{
    ElemType data;
    struct LNode* next;
}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 && jnext;
        j++;
    }
    return L;
}

// 新结点插入第i个位置
bool ListFrontInsert(Linklist L,int i,ElemType e){
    Linklist p= GetElem(L,i-1); // 首先查找到第i-1个位置
    if(NULL == p){
        return false;
    }
    Linklist s= (LNode*)malloc(sizeof(LNode));
    s->data=e;
    s->next=p->next;
    p->next=s;
    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); // 打印链表
    ListFrontInsert(L,2,99);
    print_list(L); // 打印链表
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    F:\Computer\Project\practice\11\11.3-head-insert\cmake-build-debug\11_1_head_insert.exe
3 4 5 6 7 9999
  3  4  5  6  7
  3 99  4  5  6  7

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
  • 相关阅读:
    Java练习题——接口和抽象类综合题
    应急响应常用命令（Linux）---读书笔记
    git图形化管理工具
    报错The chromedriver version cannot be discovered以及下载chromedriver.exe和查看其版本的命令
    tiup dm scale-in
    weak的自动置空
    100M跨境电商服务器能同时容纳多少人访问？
    在centos7下docker 制作 java8镜像，上传到阿里云镜像仓库
    基于OSAL 实现UART、LED、ADC等基础示例 4
    spring security 用户授权原理
  • 原文地址：https://blog.csdn.net/weixin_45842494/article/details/128201371