正文

C语言数据结构之单向链表详解分析

︶ㄣ米米素材网 メ
米米素材网V管理员 / 阅读
0715

链表可以说是一种最为基础的数据结构了，而单向链表更是基础中的基础。链表是由一组元素以特定的顺序组合或链接在一起的，不同元素之间在逻辑上相邻，但是在物理上并不一定相邻。在维护一组数据集合时，就可以使用链表

链表的概念：链表是一种动态存储分布的数据结构，由若干个同一结构类型的结点依次串连而成。

链表分为单向链表和双向链表。

链表变量一般用指针head表示，用来存放链表首结点的地址。

每个结点由数据部分和下一个结点的地址部分组成，即每个结点都指向下一个结点。最后一个结点称为表尾，其下一个结点的地址部分的值为NULL（表示为空地址）。

特别注意：链表中的各个结点在内存中是可以不连续存放的，具体存放位置由系统分配。

例如：int *ptr ;

因此不可以用ptr++的方式来寻找下一个结点。

使用链表的优点：

不需要事先定义存储空间大小，可以实时动态分配，内存利用效率高；

可以很方便地插入新元素（结点) ，使链表保持排序状态，操作效率高。

下面用课本的例子来讲解：

?
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
/*用链表实现学生成绩信息的管理*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct stud_node{
    int num;
    char name[24];
    int score;
    struct stud_node *next;
};
struct stud_node *Create_Stu_Doc();   /*新建链表*/
struct stud_node *InsertDoc(struct stud_node *head,struct stud_node *stud);   /*插入*/
struct stud_node *DeleteDoc(struct stud_node *head,int num);       /*删除*/
void Print_Stu_Doc(struct stud_node *head);              /*遍历*/
 
int main(void)
{
    struct stud_node *head,*p;
    int choice,num,score;
    char name[20];
    int size = sizeof(struct stud_node);
    
    do{
        printf("1:Create\n 2:Insert\n 3: Delete\n 4:Print\n 0:Exit\n");
        scanf("%d",&choice);
        switch(choice){
            case 1:
                head = Create_Stu_Doc();
                break;
            case 2:
                printf("Input num,name and score:\n");
                scanf("%d %s %d",&num,name,&score);
                p = (struct stud_node *)malloc(size);
                p->num = num;
                strcpy(p->name,name);
                p->score = score;
                head = InsertDoc(head,p);
                break;
            case 3:
                printf("Input num:\n");
                scanf("%d",&num);
                head = DeleteDoc(head,num);
                break;
            case 4:
                Print_Stu_Doc(head);
                break;
            case 0:
                break;
        }
    }
    while(choice != 0);
    
    return 0;
 }
/*新建链表*/
struct stud_node *Create_Stu_Doc(){
    struct stud_node *head,*p;
    int num,score;
    char name[20];
    int size = sizeof(struct stud_node);
    
    head = NULL;
    printf("Input num,name and score:\n");
    scanf("%d %s %d",&num,name,&score);
    while(num != 0){
        p=(struct stud_node *)malloc(size);
        p->num = num;
        strcpy(p->name,name);
        p->score = score;
        head = InsertDoc(head,p);    /*调用插入函数*/
        scanf("%d %s %d",&num,name,&score);
    }
    return head;
}
/*插入操作*/
struct stud_node *InsertDoc(struct stud_node *head,struct stud_node *stud){
    struct stud_node *ptr,*ptr1,*ptr2;
    ptr2 = head;
    ptr = stud;             /*ptr指向待插入的新的学生记录结点*/
    /*原链表为空链表时的插入*/
    if(head == NULL){
        head = ptr;
        head->next = NULL;
    }else{
        while((ptr->num > ptr2->num)&&(ptr2->next != NULL)){
            ptr1 = ptr2;
            ptr2 = ptr2->next;         /*ptr1,ptr2各往后移一个结点*/
        }                            
        if(ptr->num <= ptr2->num){     /*在ptr1与ptr2之间插入新结点*/
            if(head == ptr2){
            head=ptr;
        }
        else{
            ptr1->next = ptr;
            ptr->next = ptr2;
        }
        }
        else{                        
            ptr2->next = ptr;          /*新插入结点成为尾结点*/
            ptr->next =NULL;
        }
    }
    return head;
}
/*删除操作*/
struct stud_node *DeleteDoc(struct stud_node *head,int num){
    struct stud_node *ptr1,*ptr2;
    /*要被删除结点为表头结点*/
    while(head != NULL && head->num==num){
        ptr2=head;
        head=head->next;
        free(ptr2);
    }
    if(head==NULL){
        return NULL;   
    }         /*链表为空*/
    /*要被删除结点为非表头结点*/
    ptr1=head;
    ptr2=head->next;      /*从表头的下一个结点搜索所有符合删除要求的结点*/
    while(ptr2 != NULL){
        if(ptr2->num == num)/*ptr2所指结点符合删除要求*/{
            ptr1->next=ptr2->next;
            free(ptr2);
        }
        else{
            ptr1 = ptr2;         /*ptr1后移一个结点*/
            ptr2 = ptr1->next;        /*ptr2指向ptr1的后一个结点*/
        }
    }
    return head;
}
/*遍历操作*/
void Print_Stu_Doc(struct stud_node *head){
    struct stud_node *ptr;
      if(head==NULL){
        printf("\nNo Records\n");
        return;
      }
      printf("\nThe Students'Records Are:\n");
      printf("Num\t Name\t Score\t");
      for(ptr=head;ptr!=NULL;ptr=ptr->next){
        printf("%d\t%s\t%d\n",ptr->num,ptr->name,ptr->score);
      }
}

申请大小为 struct stud_node 结构的动态内存空间，新申请到的空间要被强制类型转换成

struct stud_node 型的指针，并保存到指针变量p中，如下：

struct stud_node*p；

p = ( struct stud_node *)malloc(sizeof( struct stud_node ));

链表的建立：

上面程序中链表结点是按照学生学号排序的，若向根据数据输入的顺序来建立链表，如下：

?
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
/*按输入顺序建立单向链表*/
struct stud_node *Create_Stu_Doc(){
    int num,score;
    char name[20];
    int size = sizeof(struct stud_node);
    struct stud_node *head,*tail,*p;
    head=tail=NULL;
    printf("Input num,name and score:\n");
    scanf("%d %s %d",&num,name,&score);
    while(num!=0){
        p=(struct stud_node *)malloc(size);
        p->num = num;
        strcpy(p->name,name);
        p->score = score;
        p->next = NULL;
        if(head == NULL){
            head = p;
        }else{
            tail->next=p;       /*把原来链表的尾结点的next域指向该新增的结点*/
            tail=p;
        }
        scanf("%d %s %d",&num,name,&score);
    }
    return head;
}

由于按数据输入建立链表时，新增加的结点会加在链表末尾，所以该新增结点的 next 域应置成 NULL ： p->next = NULL.

链表的遍历：

为了逐个显示链表每个结点的数据，程序要不断从链表中读取结点内容，显然需要用到循环。

在for语句中将ptr的初值置为表头head，当ptr不为NULL时循环继续，否则循环结束。不可以用ptr++来寻找下一个结点。

链表的插入：

插入原则：先连后断。

首先找到正确位置，然后插入新的结点。寻找正确位置是一个循环的过程：从链表head开始，把要插入的结点stud的num分量值与链表中结点的num分量值逐一比较，直到出现要插入结点的值比第 i 结点的num分量值大，比第 i+1结点的分量值小。所以先与第 i+1 结点相连。再将 i 结点 与 i+1结点断开，并让 i 结点与 stud 结点相连。

链表的删除：

删除原则：先接后删。

若被删除结点是表头则 head=head->next ;

其他内容省略。

到此这篇关于C语言数据结构之单向链表详解分析的文章就介绍到这了,更多相关C语言 单向链表内容请搜索米米素材网以前的文章或继续浏览下面的相关文章希望大家以后多多支持米米素材网！

原文链接：https://blog.csdn.net/m0_61897853/article/details/121096419