剑指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;
      /**
       *初始化链表
       */
      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