C语言实现单链表-02版

时间:2023-10-31 17:17:58

我们在C语言实现单链表-01版中实现的链表非常简单;

但是它对于理解单链表是非常有帮助的,至少我就是这样认为的;

简单的不能再简单的东西没那么实用,所以我们接下来要大规模的修改啦;

Problem

1,要是数据很多怎么办,100000个节点,这个main函数得写多长啊。。。

2,这个连接的方式也太土啦吧!万一某个节点忘记连接下一个怎么办。。。

3,要是我想知道这个节点到底有多长,难道每次都要从头到尾数一遍嘛。。。

4,要是我想在尾部添加一个节点,是不是爬也要爬到尾部去啊。。。

这个是简单版中提出的问题,接下来就解决它们;

Solution

首先,定义我们的数据域,它既然是一个人,那么就把身高和体重放到人身上吧;

typedef struct person_ {
int hight;
int weight;
}Person;

再继续定义我们的节点;

typedef struct node_ {
Person * data;
struct node_ * next;
}Node;

好啦!接下来我们希望有一个函数帮我们把节点连接起来,并且把数据域(人得身高体重)填入;

Node * create_node(void *data)
{
Node * tmp = (Node*)malloc(sizeof(Node));
if(tmp) {
tmp->data = data;
tmp->next = NULL;
}
return tmp;
}

它的意图很明显,只要给我一个人的身高和体重我就返回一个节点给你;

我们到这里可以先测试一下自己的程序看看有什么问题没,然后再继续;

int main(void)
{
Person a = { , };
Node * A = create_node(&a); Person b = { , };
Node * B = create_node(&b); Person c = { , };
Node * C = create_node(&c); A->next = B;
B->next = C; Node * we=NULL;
we = A; while(we != NULL) {
printf("%d--%d\n",we->data->hight,we->data->weight);
we = we->next;
}
return ;
}

看看结果:

C语言实现单链表-02版

似乎比前一个版本有所进步;

但是可以怎么说,链表的内脏我们写进去啦!但是它的肠子还露在外边,恶心吧:);

如果不能,理解的话,你请看在main函数中那些恶心的步骤任然在。。。;

好吧!解决它;

typedef struct link_list_ {
Node * head;
Node * tail;
int size;
}Link_List;

为了更好的管理我们的链表,我们需要知道它的头和尾还有它到底有多长;

因此,上面的结构体应该是暂时可以这么写的;

好吧!有了结构体,接下来就是初始化它啦!它就像其他int,char类型一样使用前一样需要初始化;

(就像哪个婴儿都喜欢喝奶一样哈)

Link_List * init_list(void)
{
Link_List * lst = (Link_List*)malloc(sizeof(Link_List));
lst->head = lst->tail = NULL;
lst->size = ;
return lst;
}

初始化后,我们需要给它添加一些节点啦;

这里链表的管理的方式很简单,它只记住链表的头和尾还有长度,不关心你在里面存入什么数据;

(就好比,学校的宿舍管理员,它只知道拿着宿舍大门的钥匙,才不管你在宿舍里怎么睡觉---其实有些管得很严呢:);

好啦!我们需要一个插入节点的函数(让我们的肠子跟随内脏一起进去吧,不要再继续恶心啦

我们的插入数据函数如下:

void insert(Link_List *lst,void *data)
{
Node * new_node = create_node(data);
if(lst->size == ) {
lst->tail = new_node; //tip:01
} new_node->next=lst->head;
lst->head = new_node;
lst->size++;
}

然后可以测试我们的代码啦!

int main(void)
{
Link_List * root = init_list(); Person a = { , };
Person b = { , };
Person c = { , }; insert(root,&a);
insert(root,&b);
insert(root,&c); Node * we=NULL;
we = root->head; while(we != NULL) {
printf("%d--%d\n",we->data->hight,we->data->weight);
we = we->next;
}
return ;
}

看看结果:

C语言实现单链表-02版

注意看,我们的输出次序与前面的次序不一样啦!

怎么回事呢?思考一下会;

这个问题先不告诉大家,接下来看看我们的链表是不是管理正常;

首先,看看这个链表现在到底它到底有多长呢;

{
Link_List * root = init_list(); Person a = { , };
Person b = { , };
Person c = { , }; insert(root,&a);
insert(root,&b);
insert(root,&c); Node * we=NULL;
we = root->head; while(we != NULL) {
printf("%d--%d\n",we->data->hight,we->data->weight);
we = we->next;
}
printf("The size of the link-list is : %d\n",root->size);
return ;
}

看看结果:

C语言实现单链表-02版

再看看,尾部和头部节点,是不是都能很轻松的告诉我们呢;

   printf("The size of the link-list is : %d\n",root->size);
printf("The head guy is %d--%d\n",root->head->data->hight,root->head->data->weight);
printf("The last guy is %d--%d\n",root->tail->data->hight,root->tail->data->weight);
return ;

好啦!再看结果:

C语言实现单链表-02版

好啦!结果正如我们期待的;

观察发现,我们的最后两句是root->head->data->hight等等,非常长,这里给大家介绍一种简单的写法;

#define GO_H(RT,HW) (RT->head->data->HW)    //GO_H:go head; RT:Root; HW: Hight,Weight
#define GO_T(RT,HW) (RT->tail->data->HW) //GO_T:go tail; RT :Root; HW: Hight,Weight

然后我们的代码就可以这样写啦!

    printf("The head guy is %d--%d\n",GO_H(root,hight),GO_H(root,weight));
printf("The last guy is %d--%d\n",GO_T(root,hight),GO_T(root,weight));

好啦!基本上完成啦!

所有代码如下:

#include <stdio.h>
#include <stdlib.h> #define GO_H(RT,HW) (RT->head->data->HW) //GO_H:go head; RT:Root; HW: Hight,Weight
#define GO_T(RT,HW) (RT->tail->data->HW) //GO_T:go tail; RT :Root; HW: Hight,Weight typedef struct person_ {
int hight;
int weight;
}Person; typedef struct node_ {
Person * data;
struct node_ * next;
}Node; typedef struct link_list_ {
Node * head;
Node * tail;
int size;
}Link_List; Node * create_node(void *data)
{
Node * tmp = (Node*)malloc(sizeof(Node));
if(tmp) {
tmp->data = data;
tmp->next = NULL;
}
return tmp;
} Link_List * init_list(void)
{
Link_List * lst = (Link_List*)malloc(sizeof(Link_List));
lst->head = lst->tail= NULL;
lst->size = ;
return lst;
}
void insert(Link_List *lst,void *data)
{
Node * new_node = create_node(data);
if(lst->size == ) {
lst->tail = new_node; //tip:01
} new_node->next=lst->head;
lst->head = new_node;
lst->size++;
}
int main(void)
{
Link_List * root = init_list(); Person a = { , };
Person b = { , };
Person c = { , }; insert(root,&a);
insert(root,&b);
insert(root,&c); Node * we=NULL;
we = root->head; while(we != NULL) {
printf("%d--%d\n",we->data->hight,we->data->weight);
we = we->next;
}
printf("The size of the link-list is : %d\n",root->size);
printf("The head guy is %d--%d\n",GO_H(root,hight),GO_H(root,weight));
printf("The last guy is %d--%d\n",GO_T(root,hight),GO_T(root,weight));
return ;
}

但是我不得不告诉你,它还有很多缺陷;

我们下次再讨论;