前言
链表不同于顺序表，顺序表是以数组为存储基础的数据结构，它在内存中表现为一块连续的内存空间；而链表不需要，它通过一个指针来连接各个分散的结点，形成了一个链状的结构，每个结点存放一个元素，以及一个指向下一个结点的指针，通过这样一个一个相连，最后形成了链表。
链表分为带头结点的链表和不带头结点的链表，戴头结点的链表就是会有一个头结点指向后续的整个链表，但是头结点不存放数据。本篇博客构建一个带头节点的链表。
构建单个节点的结构体
首先构建一个结构体表示链表的单个节点；其中包含该节点储存的数据，和下一个节点的指针。
typedef int E;
struct ListNode
{
E element;
struct ListNode * next;
};
typedef struct ListNode * Node;
typedef关键字为int类型定义了一个新的别名E。
定义了一个名为ListNode的结构体。这个结构体表示单链表中的一个节点。
编写初始化函数
初始化链表的时候，由于只有一个头节点，所以我们让该节点指向的下一个地址为NULL。
void initList(Node node)
{
node->next = NULL;
}
初始化一个链表的头节点，使其next指针指向NULL，以表示这是一个空链表或者该节点是链表的最后一个节点。
实现链表的插入
链表的插入大概分为三个步骤
- 首先找到需要插入的地方
- 将需要插入的节点指向前驱节点的下一个节点
- 将前驱节点指向需要插入的节点
int insertList(Node node,E element,int index)
{
if (index < 1) return 0;
while (--index)
{
node = node->next;
if (node == NULL) return 0;
}
Node new_node = malloc(sizeof (struct ListNode));
new_node->element = element;
new_node->next = node->next;
node->next = new_node;
return 1;
}
函数在成功插入后返回 1，表示插入成功。
这样就编写完链表的插入操作了，现在来测试一下；
编写一个打印链表元素的函数：
void printList(Node head){
while (head->next) {
head = head->next;
printf("%d ", head->element);
}
}
在主函数中初始化链表 并执行测试函数：
int main()
{
struct ListNode head;
initList(&head);
for (int i = 1; i <= 3; ++i) {
insertList(&head, i * 10, i);
}
printList(&head); // 10 20 30
return 0;
}
数据成功打印。
实现删除链表节点的功能
删除节点主要分三步：
- 找到需要删除的节点
- 将该节点的上一个节点指向需要删除节点的下一个节点
- 释放需要删除的节点的内存空间
int deleteList(Node node,int index)
{
if (index < 1) return 0;
while (--index) {
node = node->next;
if(node == NULL) return 0;
}
Node tmp = node->next; // 存储待删除节点的地址
node->next = node->next->next;
free(tmp); // 释放地址
return 1;
}
获取对应位置上的元素
getList函数则用于获取链表中指定索引处的元素地址。
E * getList(Node node,int index)
{
if (index < 1) return NULL;
do {
node = node->next;
if (node == NULL) return NULL;
} while (--index);
return &(node->element);
}
查找对应元素的位置
findList的目的是在一个链表中查找一个特定的元素element，并返回该元素在链表中的位置（假设从1开始计数）。
int findList(Node node, E element)
{
int i = 1;
node = node->next;
while (node)
{
if (node->element == element) return i;
node = node->next;
i++;
}
return -1;
}
求链表的长度
int sizeList(Node node)
{
int i = 0;
while(node->next)
{
node = node->next;
i++;
}
return i;
}
全部代码
#include <stdio.h>
#include <stdlib.h>
/*
* 链表
*/
typedef int E;
struct ListNode
{
E element;
struct ListNode * next;
};
typedef struct ListNode * Node;
void initList(Node node)
{
node->next = NULL;
}
int insertList(Node node,E element,int index)
{
if (index < 1) return 0;
while (--index)
{
node = node->next;
if (node == NULL) return 0;
}
Node new_node = malloc(sizeof (struct ListNode));
new_node->element = element;
new_node->next = node->next;
node->next = new_node;
return 1;
}
int deleteList(Node node,int index)
{
if (index < 1) return 0;
while (--index) {
node = node->next;
if(node == NULL) return 0;
}
Node tmp = node->next; // 存储待删除节点的地址
node->next = node->next->next;
free(tmp); // 释放地址
return 1;
}
E * getList(Node node,int index)
{
if (index < 1) return NULL;
do {
node = node->next;
if (node == NULL) return NULL;
} while (--index);
return &(node->element);
}
int findList(Node node, E element)
{
int i = 1;
node = node->next;
while (node)
{
if (node->element == element) return i;
node = node->next;
i++;
}
return -1;
}
int sizeList(Node node)
{
int i = 0;
while(node->next)
{
node = node->next;
i++;
}
return i;
}
void printList(Node head){
while (head->next) {
head = head->next;
printf("%d ", head->element);
}
}
int main()
{
struct ListNode head;
initList(&head);
for (int i = 1; i <= 3; ++i) {
insertList(&head, i * 10, i);
}
printList(&head);
return 0;
}
