数据结构 - 链表_C

在存储和一大波数的时候，我们通常使用的是数组，但有时候数组显得不够灵活，比如以下示例：

有一串已经从小到大排好序的数2 3 5 8 9 10 18 26 32。

现在需要往这串数字中插入一个6，使得新的序列仍然符号从小到大的排列。

我们如果使用数组来时间这一 *** 作就需要将8和8后面的数全部依次往后挪一维。

这样 *** 作显然很耽误时间，如果使用链表就会快很多。

如何实现链表呢？在C语言中可以使用动态指针和动态分配内存函数malloc来实现。

指针？天啊！如果你在学习C语言的时候没有搞懂指针，或者还不知道指针是啥，不要紧，我们现在可以回顾一下指针。

如果你已经对malloc了如指掌了的话则可以跳过下面这一小段，

先看这两句：

int a;
int *p;

第一行我们很熟悉了，就是定义一个整型变量a。

第二行就是在p前面多方了一个*号，这就表示了定义了一个整型指针变量p。

即定义了一个指针，只需要在前面加一个 *即可。

接下来，指针有什么作用呢？答案是：存储一个地址。

准确的说是存储一个内存空间的地址，比如说整型变量a的地址。

严格的说这里的指针p也只能存储一个存放整数的内存空间的地址，因为在定义的时候已经限制了这一点。

当然你可以也定义一个只能存储一个存放浮点数的内存空间的地址，比如：

double *p;

简单的说，指针就是用来存储地址的。

你可能要问：不就是存储地址吗，地址不都是一样吗，为什么还要区分不同类型的指针呢，不要着急，后面会解释。

接下来需要解决的一个问题：整型指针如果才能存储整型变量a的地址呢？很简单，如下：

p=&a;s

这个&符号很熟悉吧，就是经常在scanf函数中使用的&，这叫取地址符。

这样整型指针p就获得了整型变量a的地址，我们可以形象的形如整型指针p指向了整型变量a的地址。

p指向了a有什么用呢？用处就是我们可以用指针来 *** 作变量a了，比如我们可以通过 *** 作指针变量p来输出变量a的值：

#include 

int main()
{
    int a = 10;
    int *p;
    p = &a;
    printf("%d\n", *p);
    
    return 0;
}

这里printf语句里面的*叫做间接访问运算符，作用就是取得指针p所指向的内存中的值。

在C语言中 *有3个用途，分别是：

乘号，用作乘法运算。
声明一个指针变量，在定义指针变量时使用。

间接访问运算符，取得指针所指向的内存中的值。

malloc的作用就是从内存中申请分配指定字节大小的内存空间。

上面的代码就需要申请4个字节，可以使用sizeof(int)获取int类型占用的直接数，如下：

malloc(sizeof(int));

现在已经成功的从内存空间申请了4个字节的空间来准备存放一个整数，可是如何来对这个空间进行 *** 作呢？这时候就需要一个指针来指向这个空间，即存储这个空间的首地址：

int *p;
p = (int *)malloc(sizeof(int));

需要注意，malloc函数的返回值类型为void* 类型。

void *表示为确定的指针类型。

在C语言和C++中，void *类型可以转置转换为任何其他类型的指针。

上面代码中我们将其强制转化为整型指针，以便计算机知道这里是4个字节作为一个整体来存放整数。

有个问题，为什么要秋分不同类型的指针。

因为指针变量存储的是一个内存空间的首地址，但是这个内存空间占用了多少字节，用来存储声明类型的数，则是由指针的类型来标明，这样系统才知道应该如何区多少个连续内存作为一个数据。

OK，现在可以对刚刚通过指针p申请的4个字节的空间进行 *** 作了，例如我们在这个空间中存入10

#include 

int main()
{
    int *p;
    p = (int *)malloc(sizeof(int));
    
    *p = 10;
    printf("%d", *p);
}

可能你会问，为什么要用这么复杂的方法来存储数据呢？因为之前的方法，我们必须预先正确的知道所需的变量的个数，也就是说我们必须定义出所有的变量。

比如我们定义了100个整型变量，那么程序只能存储100个整数，如果现在的实际情况是根据需要存储101个，那么就必须要要修改程序。

如果有一天你的软件已经发布或者已经交付使用，却发现要存储1000个数才行，那么就不得不再修改程序，重新编译程序，发布一个新的版本来代替原来的。

而有了malloc函数我们可以在程序运行的过程中根据实际需要来动态的申请内存空间。

接下来就是介绍新的链表实现方式——数组模拟链表。

首先，我们要知道链表中的每一个节点都是如何存储的，每一个节点都是由两个部分组成。

一部分用来存储具体的数值，用一个整型变量即可，还有一部分用来存储下一个节点的地址，可以用指针来实现(也称为后继指针)。

struct node {
    int data;
    struct node *next;
};

上面代码中，定义了一个node的结构体类型是，这个结构体类型有两个成员，第一个结构体成员是data，用来存储具体的数值，第二个成员是一个指针，用来存储下一个节点的地址，因为下一个节点的类型也是struct node，所以这个指针的类型也必须是struct node *类型的指针。

如何建立链表呢？首先我们需要一个头指针head指向链表的最开始。

当链表还没有建立的时候头指针head为空。

struct node *head;
head = NULL;

现在创建一个节点，并用临时指针p指向这个节点。

struct node *p;
p = (struct node *)malloc1(sizeof(struct node));

接下来就是设置新创建的这个节点的左半部分和右半部分。

scanf("%d", &a);
p->data = a;
p->next = NULL;

上面使用了一个符号->，这个符号叫做结构体指针运算符，也是用来访问结构体内部成员的。

因为此处p是一个指针，所以不能使用.号来访问内部成员，而要使用->。

下面设置头指针并设置新创建的节点的*next指向空。

头指针的作用就是方便以后从头到尾的遍历整个链表。

if (head == NULL) {
    head = p; // 如果这是第一个创建的几点，则将头指针指向这个节点
} else {
    q->next = p; // 如果不是第一个创建的节点，则将上一个节点的后继指针指向当前节点
}

完整代码如下：

#include 

struct node
{
    int data;
    struct node *next;
}

int main()
{
    struct node *head, *p, *q, *t;
    int i, n, a;
    scanf("%d", &n);
    head = NULL;
    
    for (i = 1; i <= n; i++) {
        scanf("%d", &a);
        
        p = (struct node *)malloc(sizeof(struct node));
        p->data = a;
        p->next = NULL;
        
        if (head == NULL) {
            head = p;
        } else {
            q->next = p;
        }
        
        q = p;
    }
    
    t = head;
    while (t ！= NULL) {
        printf("%d ", t->data);
        t = t->next;
    }
    
    return 0;
}

上面这段代码没有释放动态申请的内存空间，虽然没有错误，但是这样是不安全的代码，会造成内存泄漏，后面会对free释放命令进行说明，也可以先行去了解。

接下来的 *** 作就是往链表里面插入一个6。

首先，需要一个临时变量从链表的头部开始遍历。

t = head;

等到指针t的下一个节点的值比6大的时候，将6查到中间。

即t->next->data大于6的时候进行插入，代码如下：

scanf("%d", &a);
while (t != NULL) {
    if (t->next == NULL || t->next->data > a) {
        p = (struct node *)malloc(sizeof(struct node));
        
        p->next = a;
        p->next = t->next; // 新增节点的后继指针指向当前节点的后继指针所指向的节点
        t->next = p; // 当前节点的后继指针指向新增节点
        break;
    }
    t = t->next; // 继续下一个节点
}

完整代码如下：

#include 
#include 

// 这里创建一个结构体用来表示链表的节点类型
struct node {
    int data;
    struct node *next;
};

int main()
{
    struct node *head, *p, *q, *t;
    int i, n, a, b;
    scanf("%d", &n);
    head = NULL; // 头指针为空
    
    for (i = 1; i <= n; i++) { // 循环读入n个数
        scanf("%d", &a);
        // 动态申请一个空间，用来存储一个节点，并用临时指针来指向这个节点
        p = (struct node *)malloc(sizeof(struct node));
        p->data = a; // 将数据存储当当前节点中
        p->next = NULL; // 设置当前节点的后继指针为空
        
        if (head == NULL) {
            head = p; // 如果是第一个创建的节点，则头指针指向这个节点
        } else {
            q->next = p; // 如果不是第一个创建的节点，则将上一个节点的后继指针指向当前节点
        }
        
        q = p; // 指针q也指向当前节点
    }
    
    scanf("%d", &b); // 读入待插入数
    t = head; // 从链表头部开始遍历
    while (t != NULL) { // 没有到达链表尾部
    	if (t->next == NULL || t->next->data > b) {
            // 如果当前节点是最后一个节点或者下一个节点的值大于待插入数的时候插入到链表中
        	p = (struct node *)malloc(sizeof(struct node));
        	// 动态申请一个内存空间来存储新增的节点
        	p->data = b;
        	p->next = t->next; // 新增节点的后继指针指向当前节点的后继指针所指向的节点
        	t->next = p; // 当前节点的后继指针指向新增节点
        	break;
   		}
    	t = t->next; // 继续下一个节点
	}
    
    // 输出链表中的所有数
    t = head;
    while (t != NULL) {
        printf("%d ", t->data);
        t = t->next;
    }
    
    return 0;
}

欢迎分享，转载请注明来源：内存溢出

原文地址: https://outofmemory.cn/langs/562371.html

数据结构 - 链表

发表评论

评论列表（0条）