链表和数组是两种最基本的数据结构，都属于线性表，常常放在一起作比较，主要区别在于数组要求逻辑顺序和内存上物理顺序一致，而链表没有要求。逻辑顺序和物理顺序一致指的是，如果逻辑顺序是1，2，3，4，5，那么在物理内存中，2也要放在1点后面。
链表的基本单元是结点，结点分为两个部分，数据域和指针域。顾名思义，数据域负责存储数据，而指针域则是指向其他结点。
结点
链表有很多形式，单链表、双链表、循环链表。其中最简单的是单链表，一个结点只存放一个指针，指向另一个结点。而双链表则是有两个指针，分别指向前一个结点和后一个结点。
灵魂画手-单链表
链表和数组相比的主要优点在于数据的插入和删除，时间复杂度都是 ，而随机访问的时间复杂度则是
.
灵魂画手-删除
灵魂画手-插入
了解了基本知识后，应该如何用C语言写一个链表呢？我将根据自己的学习过程分为三个层次来介绍，
第一阶段: 只用指针和结构体
在「C语言程序设计(第四版)」中，作者给了一个示例，帮助初学者理解结构体和指针。下面的代码我学习该部分内容后，按照自己的理解写的。
#include <stdio.h>
//singlyLinkedList_v1.c
typedef struct listNode ListNode;
typedef struct listNode{
char c;
ListNode *next;
} ListNode;
int main(int argc, char *argv[])
{
//char *seq = "GAGATGCGATGACCTGATC";
ListNode n1, n2, n3, n4;
//create linked list
n1.c = 'A';
n2.c = 'T';
n3.c = 'C';
n4.c = 'G';
n1.next = &n2;
n2.next = &n3;
n3.next = &n4;
// parse the linked list
ListNode *header = &n1;
for( ; header->next != NULL; header=header->next){
printf("%c ->", header->c);
}
printf("%c\n",header->c);
// delete the node2
n1.next = n1.next->next;
header = &n1;
for( ; header->next != NULL; header=header->next){
printf("%c ->", header->c);
}
printf("%c\n",header->c);
// add node5 between n1 and n3
ListNode n5;
n5.c = 'A';
n5.next = n1.next;
n1.next = &n5;
header = &n1;
for( ; header->next != NULL; header=header->next){
printf("%c ->", header->c);
}
printf("%c\n",header->c);
return 0;
}
我用typedef ... 新类型 定义了链表的节点 ListNode, 之后便可以在主函数中声明该数据类型。
然后我用n1.next = &n2这类方式，将各个结点通过指针进行连接，&是地址运算符，返回变量所在的内存位置。
删除节点采用的是n1.next = n1.next->next的方式，当然也可以是n1.next = *(n1.next).next。但不可以是n1.next=n1.next.next。 原因是n1.next是一个指针，需要先用*获取指针的具体内容后，才能用.引用结构体的成员。但是由于运算符.优先度高于*, 所以要用到()。 而用->的就可以少打几个符号。
插入结点也很好了解，先用ListNode n5创建了一个新的结点，之后n5.next = n1.next;让新结点指向前一个结点所指向的结点，最后n1.next = &n5让前一个结点指向新的结点。 顺序不可调换，不然就会导致指针丢失。
第二阶段: 用函数抽象化重复操作
上一部分的代码仅适用演示，实际过程中我们需要将一些重复的操作抽象成函数。例如，在表头插入的一个结点。
先来一个错误示范，症状是while部分无法打印出链表内容，
void insert_head(List *list, int value)
{
ListNode *node = calloc(1, sizeof(ListNode));
node->value = value;
if (list->head = NULL){
list->head = node;
} else{
node->next = list->head;
list->head = node;
}
}
int main(int argc, char *argv[])
{
char *seq = "GAGATGCGATGACCTGATC";
List *seqList = create_list();
// initialization
int i = 0;
for (i = 0; seq[i] != '\0'; i++){
insert_head(seqList, seq[i]);
}
// print
printf("The node is linked list is \n");
ListNode *head = seqList->head;
while (head->next != NULL){
printf("%d ->", head->value);
head = head->next;
}
return 0;
}
经过我不断的调试，最后才发现是list->head = NULL写错了，将逻辑判断符号错写成赋值符号。除去这个问题，其他部分都是可行的，继续用灵魂画图来描述一下逻辑。
空表
非空表
所有代码如下。代码实现了如下功能:
-
create_list: 创建新的链表, 返回一个指向链表的指针 -
is_empty: 判断链表是否为空表，返回逻辑值 -
find_by_value: 根据值查找结点，返回指向结点的指针 -
delete_by_value: 根据值删除结点 -
insert_head: 在头部插入结点 -
insert_value: 在给定节点后插入新结点
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
//singlyLinkedList_v2.c
typedef struct listNode ListNode;
struct listNode {
int value;
ListNode *next;
};
typedef struct list{
ListNode *head;
} List;
List* create_list()
{
return calloc(1,sizeof(List));
}
bool is_empty(List *list)
{
if (list->head == NULL){
return true;
}else{
return false;
}
}
void insert_value(List *list, ListNode *pos, int value)
{
ListNode *node = calloc(1, sizeof(ListNode));
node->value = value;
if (is_empty(list)){
list->head = node;
}else{
node->next = pos->next;
pos->next = node;
}
}
void insert_head(List *list, int value)
{
ListNode *node = calloc(1, sizeof(ListNode));
node->value = value;
if ( is_empty(list) ){
list->head = node;
} else{
node->next = list->head;
list->head = node;
}
}
ListNode *find_previous(List *list, ListNode *node)
{
if (is_empty(list))
return ;
ListNode *p = list->head;
while ( p->next != NULL){
if (p->next == node){
return p;
} else{
p = p->next;
}
}
return ;
}
ListNode *find_by_value(List *list, int value)
{
int flag = 0;
ListNode *p = list->head;
if (is_empty(list))
return;
while ( p->next != NULL){
if (p->value == value){
flag = 1 ;
break;
} else{
p = p->next;
}
}
if (flag = 1){
return p;
} else{
printf("%c is not in the list\n", value);
return;
}
}
void delete_by_value(List *list, int value)
{
if (is_empty(list))
return;
// find the node to delete
ListNode *pos = find_by_value(list, value);
// find the previous node
ListNode *prev = find_previous(list, pos);
// delete the node
prev->next = prev->next->next;
}
void print_list(List *list)
{
ListNode *head = list->head;
while (head->next != NULL){
printf("%c->", head->value);
head = head->next;
}
printf("%c\n", head->value);
}
int main(int argc, char *argv[])
{
char *seq = "GAGATGCGATGACCTGATC";
List *seqList = create_list();
// initialization
int i = 0;
for (i = 0; seq[i] != '\0'; i++){
insert_head(seqList, seq[i]);
}
print_list(seqList);
// test find position
char target = 'G';
ListNode *pos = find_by_value(seqList, target);
printf("Finding %c\n", target);
// test insert
insert_value(seqList, pos, 'P');
printf("Insert at %c\n", target);
print_list(seqList);
// test find the previous
ListNode *prev_node = find_previous(seqList, pos);
printf("Thre previous value before %c is %c\n", target, prev_node->value);
// test delete
delete_by_value(seqList, target);
printf("delete %c\n", target);
print_list(seqList);
return 0;
}
代码中所使用的指针，远超过我之前(毕竟之前从没有这样子搞).
第三阶段: 项目化
to be continued.
写在最后
当我用C语言实现了数据结构中的单链表一瞬间，我才认为自己摆脱了hello world!这个阶段，才感觉自己入门了C语言。为什么要这样子说呢？
第一：编写链表代码特别考验对指针的使用，而指针一直被认为是C语言的精髓，有人说，没学过指针就等于学过C。
第二：在写链表的时候，我才将结构体，函数，类型定义，指针共同的使用，而不是孤立看待他们。
网友评论