• 好好学习,天天向上~
  • 欢迎欢迎~

C语言面试题详解第16节

c语言 lcc 183℃ 0评论

在程序员求职面试中,有相当一部分时间是用来问答数据结构相关问题的。由于链表是一种经常使用又相对简单的数据结构,所以在面试中经常出现。

另外,虽然在程序开发中常常使用别人写好的库(例如操作链表相关的库),但是C语言是一门注重效率的语言,C程序员只有了解每个库,才能写出消耗资源少,运行效率高的程序。

对于C语言初学者来说,我个人是非常推荐从头实现一遍链表操作的,一来可以作为不错的C语言编程练习项目,再就是可以了解链表这种经典的数据结构。本文打算讨论一下链表,当然了,为了使内容不至于太过空洞,还是以各大公司的面试题为例做介绍的。

单链表

来看看这道日本某著名家电/通信/IT企业面试题:

使用C语言编程实现一个单链表的基本操作(增/查/删/打印)。

先来说说什么是链表。C语言中的链表是基于指针实现的,请看下面这张图:

链表可以像数组一样拥有多个元素。不过,C语言中的数组在运行时就确定创建多少元素,这些元素一次性创建,所以数组的各个元素在内存中紧密排列,是自然连接在一起的,之后数组元素个数不能改变。

C语言中的链表的元素(下文称“节点”)则可以随时创建,也可以随时删除,因此链表中的节点个数可以根据需要动态改变,这也导致各个节点创建的时间差异比较大,难以保证在内存中连续分布,所以需要使用指针连接这些节点。

C语言中的链表一般使用复合数据类型定义,常用的是结构体数据类型。这主要是因为结构体能够较为方便的在链表节点存储数据。试想一下,如果链表使用的 int 数据类型定义,如下:

int* a;
int* b;
int* c;
a = b;
b = c;


这样的确定义了一个链表,实现了各个元素之间的连接,但是这个链表无法存储其他信息,因此没有实际使用价值,应明白C语言程序定义各种数据结构就是为了方便存储数据的。而如果使用结构体定义C语言链表,就很好用了,如下:

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


next 成员负责连接各个元素,data 成员负责存储数据,而且如果想存储更多的数据,也只需往结构体添加新成员。之后若想在链表中建立新节点,使用下面的C语言代码即可:

struct node *node = (struct node *)malloc(sizeof(struct node));

若要删除节点,调用 C语言函数 free(node); 将节点对应的内存释放掉就可以了。下面以 struct node 结构为例,讨论一下链表的基本操作。

建立新节点

链表中各个节点是通过 next 指针连接的,每个节点的 next 指针都指向下一个节点,最后一个节点一般指向 NULL,因为这样可以避免误操作未知内存数据。链表的第一个节点一般称为“头”,为了方便管理,我们再新建一个数据结构,请看下面的C语言代码:

struct header{
    struct node *node;
};

为“头”建立这样的数据类型,还有些别的考虑,可参考我之前的文章:

应明白,建立链表是为了存储数据,前文定义的 struct node 结构适合在链表中存储 int 型数据,假设现在有 int 型数据 val 需要存入链表,可定义

int add_tail(struct header *header, int val);

函数将 val 存在头为 header 的链表尾部,相关C语言代码可如下设计:add_tail() 函数首先应判断 header 的节点是否为空,若为空,说明链表还没有建立,应为其头分配内存,并将 val 存在头节点里,相关C语言代码如下:

int add_tail(struct header *header, int val)
 {
     struct node *tmpnode;

     if(NULL==header->node){
         header->node = (struct node *)malloc(sizeof(struct node));
         if(NULL==header->node){
             printf("malloc header node failed\n");
             return -1;
         }
         header->node->data = val;
         header->node->next = NULL;
     }
...
 }


如果链表已经有头节点,若要增加新节点到链表尾部,则首先应该找到最后一个节点。最后一个节点的特征是 next 指针指向 NULL,因此C语言代码可以如下实现:

tmpnode = header->node;
while(tmpnode->next)
         tmpnode = tmpnode->next;

执行完上面三行C语言代码,tmpnode 就指向链表最后一个节点了,这时只需新建一个节点 new_node,并让 tmpnode->next 指向 new_node,就实现了在链表尾部增加节点,相关C语言代码如下:

struct node *new_node = (struct node *)malloc(sizeof(struct node));
if(NULL == new_node){
       printf("malloc new node failed");
       return -1;
 }
new_node->data = val;
new_node->next = NULL;
tmpnode->next = new_node;

最终,add_tail() 函数的C语言代码如下,请看:

打印链表

链表建立之后,遍历存储在链表中的数据也是简单的,请看C语言代码如下:

void print_list(struct header *header)
{
     struct node *tmpnode = header->node;

     while(tmpnode){
         printf("val: %d\n", tmpnode->data);
         tmpnode = tmpnode->next;
     }
}


print_list() 函数的C语言代码很简单,它从 header 开始,把存在节点中的数据输出,一直到最后一个节点。最后一个节点的 next 指针指向 NULL,此时 while 循环会退出,遍历也就结束了。

查询链表

查询对于链表来说用的比较少,因为链表是链式的数据结构,获取某一节点的数据,只能从 header 逐项遍历,所以链表只适合存储无需随机查询的数据。链表的查询是简单的,只需逐项比对就可以了,相关C语言代码如下,请看:

struct node *query_list(struct header *header, int val)
{
     struct node *tmpnode = header->node;

     while(tmpnode){
         if(val == tmpnode->data)
             return tmpnode;
         tmpnode = tmpnode->next;
     }
     return NULL;
}

删除某个节点

因为链表各个节点是链式连接的,如下图:

若要删除中间的节点,只需要让它之前的节点的 next 指针指向它的下一个节点,并把被删除的节点释放就可以了。相关的C语言代码如下,请看:

     58 int delete_node(struct header *header, int val)
-    59 {
|    60     struct node *pnode, *node;
|    61 
|    62     node = header->node;
|    63 
|-   64     if(val == node->data){
||   65         header->node = node->next;
||   66         free(node);
||   67 
||   68         return 0;
||   69     }
|    70 
|-   71     while(node){
||-  72         if(val == node->data){
|||  73             pnode->next = node->next;
|||  74             free(node);
|||  75 
|||  76             return 0;
|||  77         }
||   78         pnode = node;
||   79         node = node->next;
||   80     }
|    81 
|    82     return -1;
|    83 }


delete_node() 函数会从链表中删除第一个记录数据为 val 的节点,它的逻辑也并不复杂:首先判断要删除的节点是否头节点,如果是头节点,只需要释放之,并将其指向NULL就可以了。其他节点的操作就和上图一样了。

读者可考虑如何修改代码,使 delete_node() 函数从链表中删除所有记录数据为 val 的节点。

删除链表

删除链表其实就是从链表头逐项遍历各个节点,并将之释放的过程。相关C语言代码如下:

void delete_list(struct header *header)
{
     struct node *tmpnode;

     tmpnode = header->node;
     while(tmpnode){
         free(tmpnode);
         header->node = header->node->next;
         tmpnode = header->node;
    }
}

测试

到这里,我们就把单链表的基本操作实现完毕了,现在在 main() 函数里测试这些函数,相关C语言代码如下,请看:

编译上述C语言代码并执行,得到如下结果:

# gcc t.c
# ./a.out 
--- add value ---
val: 1
val: 2
val: 3
val: 7
--- query value ---
val: 3
--- delete value ---
val: 1
val: 2
val: 7
--- delete value ---
val: 2
val: 7
--- delete value ---
val: 2
val: 7
--- query value ---
no such value
--- delete list ---
#

一切与预期一致。

小结

本节通过一道面试题,较为详细的讨论了单链表的基础操作,以及相关的C语言代码实现,可以看出链表其实没有什么神秘的,无非就是通过指针将各个节点连接起来而已。从上文可以看出,有关链表的所有操作,都是通过节点的 next 指针遍历完成的。相信读者看出,单链表只能从 header 逐项往后遍历,有时为了能够更灵活的使用链表,会在 struct node 中增加 struct node * prev; 成员,指向前一个节点,如下图:

这种链表就是所谓的“双向链表”。为了避免误操作未知内存,双向链表的第一个节点的 prev 指针和最后一个节点的 next 指针一般都是指向 NULL 的。不过,有时候也让链表的最后一个节点的 next 指针指向第一个节点,让第一个节点的 prev 指针指向最后一个节点,这样就构成了“环形双向链表”,如下图:

这时,链表就没有“头”的概念了,各个节点的地位都是对等的,从任意一个节点出发都能遍历整个链表。


C语言面试题详解第16节 - 刘冲的博客(https://blog.popkx.com) 原创版权所有,转载请注明出处。
点赞 (1)分享 (0)
发表我的评论
取消评论
表情     9 + 1 = ? (必填)