数据结构之链表(c语言版)

Byadmin

Published2025-12-05 15:26:39

链表是线性表，链表的特点就是可以动态增减元素。种类有单向链表、双向链表，循环链表。

一、单链表

单链表的储存思想使用指针表示节点之间的逻辑关系，它的储存单元可以连续也可以不连续，每个储存单元需要储存信息和储存与后继节点的地址信息，储存单元又称之为节点。单链表由头指针唯一确定，整个单链表的操作必须由头指针开始。

链表的单位是一个一个节点，每个节点分为数据域和指针域，数据域存放数据，指针域存放指向下一个节点的指针（没有指针的语言存放的是对下一个节点的引用）。

头节点通常不放数据（也可以存放数据），尾节点指针域为空（循环链表不为空）。

单链表示意图：

c语言实现单链表1.0

还是1.0版本和2.0版本哈，2.0是后来增加的，更加健壮！

#include

//定义节点

typedef struct list

{ int data;

struct list *next;

/* data */

}Node;

//节点初始化

Node *create_node(){

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

//节点

p->next=NULL;

return p;

}

//建立链表,尾部增加

Node *link_list(int d[],int size){

Node *head=create_node();

Node *tail=head; //尾节点，此时尾节点就是头节点

for(int i=0;i

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

p->data=d[i];

p->next=NULL;

tail->next=p;

tail=p;//p变为尾节点

}

return head;

}

//追加

int append(Node *head,int e){

Node *p=create_node();

p->data=e;

Node *s=head;

while(s->next!=NULL){

s=s->next;

}

s->next=p;

return 1;

}

//长度

int Len(Node *head){

Node *p=head;

int count=0;

for(;p!=NULL;count++){

p=p->next;

}

return count;

}

//插入

int Insert(Node *head,int i,int e){

if(i<1){

printf("插入错误，程序终止");

exit(0);

}

if(i>=Len(head)+1){

//此时为追加

append(head,e);

return 1;

}

int n=1;

Node *p=head;

for(;n

p=p->next;

}

Node *s=create_node();

s->data=e;

s->next=p->next;

p->next=s;

return 1;

}

//删除

int Delete(Node *head ,int i){

if(i<1||i>Len(head)){

printf("删除非法，程序终止");

exit(0);

}

Node *f=head;//前指针

Node *b;//后指针

for(int n=1;n

f=f->next;

b=(f->next)->next;

}

Node *s=f->next;//此为被销毁的节点

f->next=b;

free(s);//释放内存

return 1;

}

//查找

int Query(Node *head ,int i){

if(i<1||i>Len(head)){

printf("查找非法，程序终止");

exit(0);

}

Node *p=head;//工作指针

for(int n=1;n

p=p->next;

}

int e=p->data;//查询的元素

return e;

}

//修改

int Update(Node *head ,int i,int e){

if(i<1||i>Len(head)){

printf("修改非法，程序终止");

exit(0);

}

Node *p=head;//工作指针

for(int n=1;n

p=p->next;

}

p->data=e;

return 1;

}

//判空

int is_Empty(Node *head){

if(head->next==NULL){

return 1;

}

return 0;

}

//遍历链表

void display(Node *head){

Node *p=head->next;//头节点没有数据

printf("此时有%d个节点\n",Len(head));

for(;p!=NULL;p=p->next){

printf("The data is %d\n",p->data);

}

//销毁链表

void Destory(Node *head){

for(Node *p=head;head!=NULL;){

head=head->next;

free(p);

p=head;

}

printf("链表已经销毁\n");

exit(0);

}

这里把大部分功能都用函数表达了，有些功能用属性似乎更加简便，不过无伤大雅。

在主函数中测试一下功能：

int main(){

int a[5]={2,1,5,11,6};

int size=sizeof(a)/sizeof(int);

printf("创建链表\n ");

Node *p=link_list(a,size);

display(p);

append(p,18);

display(p);

Insert(p,2,37);

Insert(p,4,23);

Insert(p,14,37);

display(p);

Delete(p,2);

display(p);

int i=9;

int e=Query(p,i);

printf("查询的是第%d个元素，值为%d\n",i,e);

Update(p,i,10);

printf("修改了%d号元素,现在值为%d\n",i,Query(p,i));

Destory(p);

}

测试结果：

创建链表

此时有6个节点

The data is 2

The data is 1

The data is 5

The data is 11

The data is 6

此时有7个节点

The data is 2

The data is 1

The data is 5

The data is 11

The data is 6

The data is 18

此时有10个节点

The data is 2

The data is 37

The data is 1

The data is 23

The data is 5

The data is 11

The data is 6

The data is 18

The data is 37

此时有9个节点

The data is 2

The data is 1

The data is 23

The data is 5

The data is 11

The data is 6

The data is 18

The data is 37

查询的是第9个元素，值为37

修改了9号元素,现在值为10

链表已经销毁

c语言实现单链表2.0

从全局静态变量来表示头节点和节点数量，此时代码逻辑简单多了。

增删改查功能都没有实现，可以自行摸索。

#include

//定义节点

typedef struct list

{ int data;

struct list *next;

/* data */

}Node;

static int count=0;//节点数量，代替了Len函数中的逻辑

static Node *head=NULL;//头节点

//节点初始化

Node *create_node(){

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

//节点

p->next=NULL;

return p;

}

//建立链表,尾部增加

Node *link_list(int d[],int size){

head=create_node();

Node *tail=head; //尾节点，此时尾节点就是头节点

for(int i=0;i

Node *p=create_node();

p->data=d[i];

p->next=NULL;

tail->next=p;

tail=p;//p变为尾节点

printf("链表增加元素%d\n",d[i]);

}

count=size+1;//头节点也算

printf("链表创建成功\n");

return head;

}

//长度

int Len(){

//原先的代码去掉，直接由count代替

return count;

}

//判空

int is_Empty(){

if(count==0){

return 1;

}

return 0;

}

//遍历链表

void display(){

printf("此时有%d个节点\n",count);

Node *p=head->next;

// for(;p!=NULL;p=p->next){

// printf("The data is %d\n",p->data);

// }

for(int i=1;i

printf("The data is %d\n",p->data);

p=p->next;

}

int main(){

int a[5]={2,1,5,11,6};

int size=sizeof(a)/sizeof(int);

printf("创建链表\n ");

Node *p=link_list(a,size);

display();

}

二、单向循环链表

循环链表有单向的也有双向的，其实就是尾节点的指针域指向了头节点，成为循环结构。这样从任意位置都可以遍历所有。

在单链表1.0的基础上稍作修改，一个单向循环链表就完成了。在指针的指向方面稍作修改就可以完成，部分方法就没有提供了，可以自行摸索。

单循环链表1.0

#include

//定义节点

typedef struct list

{ int data;

struct list *next;

/* data */

}Node;

//节点初始化

Node *create_node(){

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

//节点

p->next=NULL;

return p;

}

//建立链表,尾部增加

Node *link_list(int d[],int size){

Node *head=create_node();

Node *tail=head; //尾节点，此时尾节点就是头节点

for(int i=0;i

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

p->data=d[i];

p->next=head;//指向头节点

tail->next=p;

tail=p;//p变为尾节点

}

return head;

}

//长度

int Len(Node *head){

Node *p=head;

if(p==NULL){

return 0;

}

p=head->next;

Node *s=head;

int count=1;

for(;p!=s&&p!=NULL;count++){

p=p->next;

}

return count;

}

//判空

int is_Empty(Node *head){

if(head->next==NULL){

return 1;

}

return 0;

}

//遍历链表

void display(Node *head){

Node *p=head->next;//头节点没有数据

Node *s=head;//标记指针

printf("此时有%d个节点\n",Len(head));

for(;p!=s;p=p->next){

printf("The data is %d\n",p->data);

}

在主函数中测试一下：

int main(){

int a[5]={2,1,5,11,6};

int size=sizeof(a)/sizeof(int);

printf("创建链表\n ");

Node *p=link_list(a,size);

display(p);//遍历循环链表

Node * s=(p->next)->next;//指向其他节点的指针

display(s);//其他节点遍历

}

结果如下，可以看到不是预期的结果，某个数据。。。是1995024，这是个啥，这是头节点的data,自动分配的。

创建链表

此时有6个节点

The data is 2

The data is 1

The data is 5

The data is 11

The data is 6

此时有6个节点

The data is 5

The data is 11

The data is 6

The data is 1995024

The data is 2

这肯定不行啊，说好的头节点不放数据的，所以我们遇到头节点得跳到下一级。1.0版本的可以自己实现一下！

我们搞个2.0版本的。

单循环链表2.0

#include

//定义节点

typedef struct list

{ int data;

struct list *next;

/* data */

}Node;

static Node *head=NULL;

static int count=0;

//节点初始化

Node *create_node(){

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

//节点

p->next=NULL;

return p;

}

//建立链表,尾部增加

Node *link_list(int d[],int size){

head=create_node();

Node *tail=head; //尾节点，此时尾节点就是头节点

for(int i=0;i

Node *p=create_node();

p->data=d[i];

p->next=head;//指向头节点

tail->next=p;

tail=p;//p变为尾节点

}

count+=size+1;//节点数量

return head;

}

//查询

int query(int i){

is_error(i);

Node *p=head;

for(int n=1;n

p=p->next;

}

return p->data;

}

//是否非法

int is_error(int i){

if(is_Empty()){

printf("NULL,非法\n");

return 1;

}

if(i<1||i>count){

printf("查询超长，非法\n");

return 2;

}

return 0;

}

//长度

int Len(){

return count;

}

//判空

int is_Empty(){

if(count==0){

return 1;

}

return 0;

}

//遍历链表

void display(Node *p){

printf("此时有%d个节点\n",count);

for(int i=1;i

if(p==head){ //判断是否是头指针

p=p->next;

}

printf("The data is %d\n",p->data);

p=p->next;

}

主函数中测试一下：

int main(){

int a[5]={2,1,5,11,6};

int size=sizeof(a)/sizeof(int);

printf("创建链表\n ");

Node *p=link_list(a,size);

display(p);//遍历循环链表

p=p->next->next;//偏移

display(p);//其他节点遍历

}

创建链表

此时有6个节点

The data is 2

The data is 1

The data is 5

The data is 11

The data is 6

此时有6个节点

The data is 1

The data is 5

The data is 11

The data is 6

The data is 2

此时结果应该是正确的！

三、双向链表

双向链表即有两个指向的链表，通常指指向前节点和后继节点的链表。这样也是从任何部位都能遍历全部元素，

且查找元素时，可以向前查找或者向后查找，不必完全遍历全链表。

双向链表示意图：

c语言实现双链表

在单链表2.0的基础上研究双链表。

先创建一个双向链表。

#include

//定义节点

typedef struct list

{ int data;

struct list *next;//双指针

struct list *prev;

/* data */

}Node;

static int count=0;//节点数量

static Node *head=NULL;//头节点

//节点初始化

Node *create_node(){

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

//节点

p->next=NULL;

p->prev=NULL;

return p;

}

//尾节点

Node *get_tail(){

Node *tail=head;

for(int i=1;i

tail=tail->next;

}

return tail;

}

//建立链表,尾部增加

Node *link_list(int d[],int size){

head=create_node();//头节点初始化

Node *tail=head; //尾节点，此时尾节点就是头节点

for(int i=0;i

Node *p=create_node();

p->data=d[i];

tail->next=p;

p->prev=tail;

tail=p;//p变为尾节点

}

count=size+1;

return head; //返回头节点

}

//长度

int Len(){

return count;

}

//判空

int is_Empty(){

if(count==0){

return 1;

}

return 0;

}

//遍历链表，从头节点开始

void display(){

printf("此时有%d个节点\n",count);

Node *p=head->next;

for(;p!=NULL;p=p->next){

printf("The data is %d\n",p->data);

}

//查找元素

Node* query(int i){

if(error(i)){

return NULL;

}

Node *p;

if(i<=(int)(count/2)){//从头结点开始查找

p=head;

for(int n=1;n

p=p->next;

}

return p;

}else //从尾节点向前查找

{

p=get_tail();

for(int n=0;n

p=p->prev;

}

return p;

}

return NULL;

}

//得到节点

Node *get_node(int i){

Node *p=head;

if(i==count){

return get_tail();

}

if(error(i)){

return NULL;

}

for(int s=1;s

p=p->next;

}

return p;

}

//判断传入参数是否非法

int error(int i){

if(is_Empty()){

printf("链表NULL,非法\n");

return 1;

}

if(i<1||i>count){

printf("查询超长，非法\n");

return 2;

}

return 0;

}

测试一下：

int main(){

int a[5]={2,1,5,11,6};

int size=sizeof(a)/sizeof(int);

printf("创建链表\n ");

Node *p=link_list(a,size);

display();

printf("查询的元素是%d\n",query(5)->data);

printf("查询的元素是%d\n",query(2)->data);

}

此时可以查询。

创建链表

此时有6个节点

The data is 2

The data is 1

The data is 5

The data is 11

The data is 6

查询的元素是11

查询的元素是2

再加入删除、更新、插入函数。

//插入

void insert(int i,int e){

Node *s =query(i);

Node *p=create_node();

p->data=e;

p->next=s;

p->prev=s->prev;

(s->prev)->next=p;

s->prev=p;

count++;

}

//删除

void delete(int i){

Node *s=query(i);

Node *p,*n;

//修改指针指向

p=s->prev;

n=s->next;

p->next=n;

n->prev=p;

free(s); //销毁节点

count--;//数量减少

}

//更新

void update(int i,int e){

Node *p=query(i);

p->data=e;

}

再次测试：

int main(){

int a[5]={2,1,5,11,6};

int size=sizeof(a)/sizeof(int);

printf("创建链表\n ");

Node *p=link_list(a,size);

display();

printf("查询的元素是%d\n",query(5)->data);

printf("查询的元素是%d\n",query(2)->data);

update(2,8);

display();

delete(2);

display();

insert(2,8);

display();

}

如下所示：

创建链表

此时有6个节点

The data is 2

The data is 1

The data is 5

The data is 11

The data is 6

查询的元素是11

查询的元素是2

此时有6个节点

The data is 8

The data is 1

The data is 5

The data is 11

The data is 6

此时有5个节点

The data is 1

The data is 5

The data is 11

The data is 6

此时有6个节点

The data is 8

The data is 1

The data is 5

The data is 11

The data is 6

四、双向循环链表

双向循环链表的用处比较广泛、不过就是双向链表的基础上进行了循环。构造难度不大，可以参考单链表循环实现。

数据结构与算法学习目录