剑指offer之C语言实现链表(两种方式)
【摘要】 1 问题
用C语言实现链表
2 代码实现
#include <stdio.h>#include <stdlib.h> #define true 0#define false -1 typedef struct Node{ int value; struct Node *next;} List; /*...
1 问题
用C语言实现链表
2 代码实现
-
#include <stdio.h>
-
#include <stdlib.h>
-
-
#define true 0
-
#define false -1
-
-
typedef struct Node
-
{
-
int value;
-
struct Node *next;
-
} List;
-
-
/**
-
*初始化链表
-
*/
-
struct Node* init_list()
-
{
-
struct Node *head = (struct Node*)malloc(sizeof(struct Node));
-
if (head)
-
{
-
head->next = NULL;
-
return head;
-
}
-
return NULL;
-
}
-
-
/*
-
*创建节点
-
*/
-
struct Node* create_node(int value)
-
{
-
struct Node *node = (struct Node*)malloc(sizeof(struct Node));
-
if (node)
-
{
-
node->value = value;
-
return node;
-
}
-
return NULL;
-
}
-
-
/*
-
*第一种方法插入节点
-
*/
-
int insert_list(struct Node **head, List* node)
-
{
-
if (*head == NULL || node == NULL)
-
{
-
printf("head or node is NULL");
-
return false;
-
}
-
node->next = *head;
-
*head = node;
-
return true;
-
}
-
-
/*
-
*第二种方法插入节点
-
*/
-
int insert_list1(struct Node *head, List* node)
-
{
-
if (head == NULL || node == NULL)
-
{
-
printf("head or node is NULL");
-
return false;
-
}
-
node->next = head->next;
-
head->next = node;
-
return true;
-
}
-
-
/*
-
*第一种方法打印
-
*/
-
void print_list(List *head)
-
{
-
if (head == NULL)
-
{
-
printf("head is NULL\n");
-
return;
-
}
-
while (head->next != NULL)
-
{
-
printf("value is %d\n", head->value);
-
head = head->next;
-
}
-
}
-
-
/*
-
*第二种方法打印
-
*/
-
void print_list1(List *head)
-
{
-
if (head == NULL)
-
{
-
-
printf("head is NULL\n");
-
return;
-
}
-
struct Node *p = head->next;
-
while (p != NULL)
-
{
-
printf("value is %d\n", p->value);
-
p = p->next;
-
}
-
-
-
}
-
-
/*
-
*更具这个值能否能到节点
-
*/
-
struct Node* get_node(List *head, int value)
-
{
-
-
if (head == NULL)
-
return NULL;
-
struct Node *p = head;
-
while (p != NULL)
-
{
-
if (p->value == value)
-
{
-
return p;
-
}
-
p = p->next;
-
}
-
return NULL;
-
}
-
-
/*
-
*第一种方法删除节点
-
*/
-
int delete_node(struct Node **head, struct Node *node)
-
{
-
if (*head == NULL)
-
return false;
-
if ((*head) == node)
-
{
-
*head = (*head)->next;
-
return true;
-
}
-
struct Node *p = *head;
-
while ((*head)->next != NULL)
-
{
-
if ((*head)->next == node)
-
{
-
(*head)->next =(*head)->next->next;
-
*head = p;
-
return true;
-
}
-
*head = (*head)->next;
-
}
-
*head = p;
-
return false;
-
}
-
-
/*
-
*第二种方法删除节点
-
*/
-
int delete_node1(struct Node *head, struct Node *node)
-
{
-
if (head == NULL)
-
return false;
-
while (head->next != NULL)
-
{
-
if (head->next == node)
-
{
-
head->next = head->next->next;
-
return true;
-
}
-
head = head->next;
-
}
-
return false;
-
}
-
-
/*
-
*释放链表
-
*/
-
int free_list(List *head)
-
{
-
if (head == NULL)
-
return false;
-
struct Node *p = NULL;
-
while(head != NULL)
-
{
-
p = head;
-
head = head->next;
-
free(p);
-
}
-
return true;
-
}
-
-
int main()
-
{
-
struct Node* head = NULL;
-
struct Node* node1 = NULL, *node2 = NULL, *node3 = NULL;
-
struct Node* node4 = NULL, *node5 = NULL, *node6 = NULL;
-
head = init_list();
-
if (!head)
-
{
-
printf("init head fail\n");
-
}
-
node1 = create_node(5);
-
node2 = create_node(4);
-
node3 = create_node(3);
-
node4 = create_node(2);
-
node5 = create_node(1);
-
node6 = create_node(3);
-
-
insert_list1(head, node1);
-
insert_list1(head, node2);
-
insert_list1(head, node3);
-
insert_list1(head, node4);
-
insert_list1(head, node5);
-
insert_list1(head, node6);
-
print_list1(head);
-
printf("first print_list---------------\n");
-
delete_node1(head, node1);
-
print_list1(head);
-
printf("second print_list--------------\n");
-
free_list(head);
-
head = NULL;
-
-
head = init_list();
-
if (!head)
-
{
-
printf("init head fail\n");
-
}
-
node1 = create_node(5);
-
node2 = create_node(4);
-
node3 = create_node(3);
-
node4 = create_node(2);
-
node5 = create_node(1);
-
node6 = create_node(3);
-
-
insert_list(&head, node1);
-
insert_list(&head, node2);
-
insert_list(&head, node3);
-
insert_list(&head, node4);
-
insert_list(&head, node5);
-
insert_list(&head, node6);
-
print_list(head);
-
printf("third print_list---------------\n");
-
delete_node(&head, node4);
-
print_list(head);
-
printf("four print_list---------------\n");
-
struct Node *result = get_node(head, 4);
-
if (result)
-
{
-
printf("list contain node and the value of node is %d\n", result->value);
-
}
-
else
-
{
-
printf("list do not contain the node\n");
-
}
-
free_list(head);
-
head = NULL;
-
return 0;
-
}
3 运行结果
-
value is 3
-
value is 1
-
value is 2
-
value is 3
-
value is 4
-
value is 5
-
first print_list---------------
-
value is 3
-
value is 1
-
value is 2
-
value is 3
-
value is 4
-
second print_list--------------
-
value is 3
-
value is 1
-
value is 2
-
value is 3
-
value is 4
-
value is 5
-
third print_list---------------
-
value is 3
-
value is 1
-
value is 3
-
value is 4
-
value is 5
-
four print_list---------------
-
list contain node and the value of node is 4
4 总结
很明显第二种方式更换简单好理解,在函数里面如果我们传递指针进去,然后想修改这个指针的话,我们直接给这个指针赋值来改变这个指针是不可以的,因为是停时变量,我们直接可以返回新malloc的指针或者函数传递二级指针作为参数,在函数里面修改这个指针,同时我们把头结点传递函数里面去,我们直接操作head->next = head->next->next;这些都会有效.
用C语言实现的话,我们喜欢搞个头结点,然后每个函数里面传入头结点,我们函数里面改变的是head->next的值,但是我们就算移动了head节点,比如head = head->next; 但是实际上没有影响,因为是零时变量,最后的head的位置还是没有动
文章来源: chenyu.blog.csdn.net,作者:chen.yu,版权归原作者所有,如需转载,请联系作者。
原文链接:chenyu.blog.csdn.net/article/details/86515602
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)