數據結構之鏈表c語言實現

    準備把原來上學時候寫的數據結構、算法相關的代碼再重新寫一遍，溫習下。首先從鏈表說起，鏈表可能是我們平時用的較多的一種結構，鏈表操作對于刪除、添加的算法時間復雜度為O(1)。

    說到鏈表就不得不提到他的表哥數組，通過下圖來看下一數據和鏈表在內存中的區別（此處所說的內存都是虛擬內存）。

                                         數組在內存中的存放

    注：這里addr + 1 并不是一個字節或者一個字，是一個數據單位的大小。

    由上圖可以看出數組是在內存中連續存放的，這就成在數據刪除或者插入的時候可能要移動很多的數據，其可擴展性也不好。

                                    鏈表在內存中的表示

    上圖中一個數據單元中除了放本單元的數據，還存放了下一個單元的地址，上圖可以簡化一下：

    從上圖可以看出，鏈表中的數據在內存中并不是連續存放的，而是通過index將兩個數據單元關聯起來，這樣可以方便我們在不同的數據單元之間插入數據，例如在數據單元1和數據單元2之間插入數據如下：

                                        數據插入

    鏈表還可以分為單鏈表、雙鏈表、循環鏈表，不過其原理都是大同小異，下面以單鏈表為例練練手，以面向對象的思路進行編程，可能在這里不是太合適，不過訓練對事物進行抽象能力絕對對編程大有好處。

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>

typedef struct list {
	char name[32];
	int age;
	struct list *next;	/* 指向下一個節點 */	
	/* 在頭節點之后插入新節點 */
	void (* insert)(struct list *head, struct list *node);		
	int  (* delete)(struct list *head, struct list *node);	/* 刪除指定的節點 */
	/* 查找是否存在指定節點 */
	struct list *(* find_node)(struct list *head, struct list *node, int *ret);	
	void (* print_list)(struct list *head);	    /* 打印節點內容 */
	void (* destroy_list)(struct list *head);   /* 銷毀整個鏈表 */
}list_t;

struct info {
	char *name;
	int age;
}person[] = {
	{"zhangsan", 18},
	{"lisi", 20},
	{"xiaohong", 30},
	{"end",0},
};

/*
 *fun  : 頭結點之后插入新節點
 *head ：頭結點指針
 *node : 待插入節點指針
 */
void list_insert_node(struct list *head, struct list *node)
{
	if (head == NULL || node == NULL) {
		printf("insert node failed ! \n");
		return;
	} 
	
	node->next = head->next;
	head->next = node;
}

/*
 *fun  : 查找指定的節點是否存在
 *head ：頭結點指針
 *node : 待查找節點指針
 *ret  : 查找成功失敗的標志，0 成功，-1 失敗
 *return : 刪除節點的前一個節點指針
 */
struct list *list_find_node(struct list *head, struct list *node, int *ret)
{
	struct list *tmp;
	
	if (head == NULL || node == NULL) {
		printf("find node failed ! \n");
		*ret = -1;
		return NULL;
	} 
	
	while (head->next) {
		tmp = head->next;
		if ((tmp->age == node->age) && (strcmp(tmp->name, node->name) == 0)){
			return head;
		}
		head = head->next;
	}
	
	*ret = -1;
	return NULL;
}

/*
 *fun  : 刪除指定節點
 *head ：頭結點指針
 *node : 待刪除節點指針
 *return : 0 成功，-1 失敗
 */
int list_del_node(struct list *head, struct list *node)
{
	int ret;
	struct list *pre_del_node;
	struct list *tmp;
	
	if (head == NULL || node == NULL) {
		printf("del node failed ! \n");
		return -1;
	} 
	
	ret = 0;
	pre_del_node = head->find_node(head, node ,&ret);
	if (ret == -1) {
		return ret;
	}
	
	tmp = pre_del_node->next;
	pre_del_node->next = tmp->next;
	free(tmp);	
	
	return 0;
}

/*
 *fun  : 顯示鏈表內容
 *head ：頭結點指針
 */
void print_list(struct list *head)
{
	struct list *tmp;
	
	tmp = head->next;
	
	while (tmp) {
		printf("name = %s, age = %d \n", tmp->name, tmp->age);
		tmp = tmp->next;
	}
}

/*
 *fun  : 刪除成個鏈表
 *head ：頭結點指針
 */
void destroy_list(struct list *head)
{
	struct list *tmp;
	struct list *assit;
	
	assit = head->next;
	while (assit) {
		tmp = assit;
		assit = assit->next;
		free(tmp);
	}
	free(head); /* 釋放頭節點指針 */
}

void init_head(struct list *head)
{
	head->next         = NULL;
	head->insert       = list_insert_node;
	head->delete       = list_del_node;
	head->find_node    = list_find_node;
	head->print_list   = print_list;
	head->destroy_list = destroy_list;
}


int main(int argc, char *argv[])
{
	int i; 
	struct list *head, *tmp;
	
	head = (struct list *)malloc(sizeof(struct list));
	if (head == NULL) {
		printf("no memory \n");
		exit(-1);
	}
	
	init_head(head);
	
	i = 0;
	while (person[i].age) {
		tmp = (struct list *)malloc(sizeof(struct list));
		if (tmp == NULL) {
			/*此處應該釋放掉已經分配的內存，防止內存泄漏，偷懶沒有寫*/
			printf("no memory \n");
			exit(-1);
		}
		strcpy(tmp->name, person[i].name);
		tmp->age = person[i].age;
		tmp->next         = NULL;
		
		head->insert(head, tmp);
		i++;
	}
	
	head->print_list(head);
	head->delete(head, tmp);
	printf("刪除最后插入的節點之后 \n");
	head->print_list(head);
	
	return 0;
}

說明：次例子僅作練習用，真正用到項目中可以找一些開源的，簡潔高效的鏈表代碼，例如我們公司項目中的鏈表就是修改的LINUX內核鏈表來用的，沒有必要重復造輪子，但作為練習還是要敲一下。