個(gè)人中心
退出
劍指offer之C語言實(shí)現(xiàn)鏈表（兩種方式）
1 問題
用C語言實(shí)現(xiàn)鏈表
2 代碼實(shí)現(xiàn)
#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;
}
/*
*創(chuàng)建節(jié)點(diǎn)
*/
struct Node* create_node(int value)
{
struct Node *node = (struct Node*)malloc(sizeof(struct Node));
if (node)
{
node->value = value;
return node;
}
return NULL;
}
/*
*第一種方法插入節(jié)點(diǎn)
*/
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;
}
/*
*第二種方法插入節(jié)點(diǎn)
*/
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;
}
}
/*
*更具這個(gè)值能否能到節(jié)點(diǎn)
*/
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;
}
/*
*第一種方法刪除節(jié)點(diǎn)
*/
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;
}
/*
*第二種方法刪除節(jié)點(diǎn)
*/
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 運(yùn)行結(jié)果
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 總結(jié)
很明顯第二種方式更換簡單好理解，在函數(shù)里面如果我們傳遞指針進(jìn)去，然后想修改這個(gè)指針的話，我們直接給這個(gè)指針賦值來改變這個(gè)指針是不可以的，因?yàn)槭峭r(shí)變量，我們直接可以返回新malloc的指針或者函數(shù)傳遞二級指針作為參數(shù)，在函數(shù)里面修改這個(gè)指針，同時(shí)我們把頭結(jié)點(diǎn)傳遞函數(shù)里面去，我們直接操作head->next = head->next->next;這些都會(huì)有效.
用C語言實(shí)現(xiàn)的話，我們喜歡搞個(gè)頭結(jié)點(diǎn)，然后每個(gè)函數(shù)里面?zhèn)魅腩^結(jié)點(diǎn)，我們函數(shù)里面改變的是head->next的值，但是我們就算移動(dòng)了head節(jié)點(diǎn)，比如head = head->next; 但是實(shí)際上沒有影響，因?yàn)槭橇銜r(shí)變量，最后的head的位置還是沒有動(dòng)
作者：chen.yu
深信服三年半工作經(jīng)驗(yàn)，目前就職游戲廠商，希望能和大家交流和學(xué)習(xí),
微信公眾號：編程入門到禿頭 或掃描下面二維碼
零基礎(chǔ)入門進(jìn)階人工智能(鏈接)
分類導(dǎo)航