數(shù)據(jù)結(jié)構(gòu)之鏈表c語言實現(xiàn)

    準(zhǔn)備把原來上學(xué)時候?qū)懙臄?shù)據(jù)結(jié)構(gòu)、算法相關(guān)的代碼再重新寫一遍，溫習(xí)下。首先從鏈表說起，鏈表可能是我們平時用的較多的一種結(jié)構(gòu)，鏈表操作對于刪除、添加的算法時間復(fù)雜度為O(1)。

    說到鏈表就不得不提到他的表哥數(shù)組，通過下圖來看下一數(shù)據(jù)和鏈表在內(nèi)存中的區(qū)別（此處所說的內(nèi)存都是虛擬內(nèi)存）。

                                         數(shù)組在內(nèi)存中的存放

    注：這里addr + 1 并不是一個字節(jié)或者一個字，是一個數(shù)據(jù)單位的大小。

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

                                    鏈表在內(nèi)存中的表示

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

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

                                        數(shù)據(jù)插入

    鏈表還可以分為單鏈表、雙鏈表、循環(huán)鏈表，不過其原理都是大同小異，下面以單鏈表為例練練手，以面向?qū)ο蟮乃悸愤M(jìn)行編程，可能在這里不是太合適，不過訓(xùn)練對事物進(jìn)行抽象能力絕對對編程大有好處。

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

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

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

/*
 *fun  : 頭結(jié)點之后插入新節(jié)點
 *head ：頭結(jié)點指針
 *node : 待插入節(jié)點指針
 */
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  : 查找指定的節(jié)點是否存在
 *head ：頭結(jié)點指針
 *node : 待查找節(jié)點指針
 *ret  : 查找成功失敗的標(biāo)志，0 成功，-1 失敗
 *return : 刪除節(jié)點的前一個節(jié)點指針
 */
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  : 刪除指定節(jié)點
 *head ：頭結(jié)點指針
 *node : 待刪除節(jié)點指針
 *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  : 顯示鏈表內(nèi)容
 *head ：頭結(jié)點指針
 */
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 ：頭結(jié)點指針
 */
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); /* 釋放頭節(jié)點指針 */
}

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) {
			/*此處應(yīng)該釋放掉已經(jīng)分配的內(nèi)存，防止內(nèi)存泄漏，偷懶沒有寫*/
			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("刪除最后插入的節(jié)點之后 \n");
	head->print_list(head);
	
	return 0;
}

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