无头结点单向链表实现代码,C代码库,德仔网

代码语言
代码分类
【C】无头结点单向链表实现
作者:丁小莫 / 发布于2015/8/3/ 1259
Linux平台下编写，测试函数main.c为一个简单的学生信息的插入、删除等操作。

	
	slist.h

	/* 无头结点单向链表 */
	
	#ifndef __SLIST_H__
	#define __SLIST_H__
	
	#include <stdio.h>
	#include <stdlib.h>
	#include <string.h>
	
	typedef int (*cmp_t)(const void *, const void *);
	typedef void (*pfunc_t)(const void *, int);
	
	/* 结点类型 */
	typedef struct node node_t;
	struct node{
	 void *data;
	 node_t *next;
	};
	
	/* 链表类型 */
	typedef struct list list_t;
	struct list{
	 node_t *head;
	 int size;
	 int len;
	};
	
	/* 创建链表 */
	list_t *list_create(int size);
	/* 链表尾部插入数据 */
	int list_append(list_t *handler, void *data);
	/* 链表首部插入数据 */
	int list_prepend(list_t *handler, void *data);
	/* 按照索引插入数据 */
	int list_insertby_index(list_t *handler, void *data, int index);
	/* 有序插入数据 */
	int list_insertby_sort(list_t *handler, void *data, cmp_t func);
	
	/* 根据索引返回数据 */
	void *list_by_index(list_t *handler, int index);
	/* 对链表数据进行排序 */
	void list_sort(list_t *handler, cmp_t func);
	
	/* 按照索引删除数据 */
	int list_delby_index(list_t *handler, int index, pfunc_t pfunc);
	/* 按照关键字删除数据 */
	int list_delby_key(list_t *handler, void *key, cmp_t func, pfunc_t pfunc);
	
	/* 按照关键字查找一个数据 */
	void *list_findoneby_key(list_t *handler, void *key, cmp_t func);
	/* 按照关键字查找所有数据 */
	list_t *list_findallby_key(list_t *handler, void *key, cmp_t func);
	/* 按照索引查找数据 */
	void *list_findby_index(list_t *handler, int index);
	/* 查找中间数据 */
	void *list_find_mid(list_t *handler);
	
	/* 链表逆序 */
	void list_reverse(list_t *handler);
	
	/* 保存链表到文件中 */
	int list_saveto_file(list_t *handler);
	/* 加载文件到链表中 */
	list_t *list_loadfrom_file(void);
	
	/* 遍历链表 */
	void list_travel(list_t *handler, pfunc_t pfunc);
	/* 销毁链表 */
	void list_destroy(list_t *handler, pfunc_t pfunc);
	
	#endif

	

	

	

	slist.c

	/* 无头结点单向链表 */
	
	#include "slist.h"
	
	/* 创建结点 */
	static node_t *node_create(void *data, int size)
	{
	 node_t *new_node = NULL;
	
	 new_node = malloc(sizeof(node_t));
	 if (NULL == new_node)
	 return NULL;
	 new_node->data = malloc(size);
	 if (NULL == new_node->data) {
	 free(new_node);
	 new_node = NULL;
	 return NULL;
	 }
	 memcpy(new_node->data, data, size);
	 new_node->next = NULL;
	
	 return new_node;
	}
	
	/* 创建链表 */
	list_t *list_create(int size)
	{
	 list_t *new = NULL;
	
	 new = malloc(sizeof(list_t));
	 if (NULL == new)
	 return NULL;
	 new->head = NULL;
	 new->size = size;
	 new->len = 0;
	
	 return new;
	}
	
	/* 链表尾部插入数据 */
	int list_append(list_t *handler, void *data)
	{
	 node_t *new_node = NULL;
	 node_t *tmp = NULL;
	
	 new_node = node_create(data, handler->size);
	 if (NULL == new_node)
	 return -1;
	#if 1
	 if (NULL == handler->head)
	 handler->head = new_node;
	 else {
	 for (tmp = handler->head; tmp->next != NULL; tmp = tmp->next)
	 ;
	 tmp->next = new_node;
	 }
	#endif
	#if 0
	 //此做法错误，仅对临时变量tmp进行了赋值
	 for (tmp = handler->head; tmp != NULL; tmp = tmp->next)
	 ;
	 tmp = new_node;
	#endif
	 handler->len++;
	
	 return 0;
	}
	
	/* 链表首部插入数据 */
	int list_prepend(list_t *handler, void *data)
	{
	 node_t *new_node = NULL;
	
	 new_node = node_create(data, handler->size);
	 if (NULL == new_node)
	 return -1;
	 if (handler->head) //若头指针不为空，则替换头指针所指向的结点
	 new_node->next = handler->head;
	 handler->head = new_node;
	 handler->len ++;
	
	 return 0;
	}
	
	/* 按照索引插入数据 */
	int list_insertby_index(list_t *handler, void *data, int index)
	{
	 int i;
	 node_t *new_node = NULL;
	 node_t *tmp = NULL;
	
	 if (index < 0 || index > handler->len)
	 return -1;
	
	 if (index == 0) {
	 list_prepend(handler, data);
	 return 0;
	 }
	
	 new_node = node_create(data, handler->size);
	 if (NULL == new_node)
	 return -1;
	 i = 0;
	 for (tmp = handler->head; tmp != NULL; tmp = tmp->next) {
	 if (++i == index) {
	 new_node->next = tmp->next;
	 tmp->next = new_node;
	 handler->len ++;
	 return 0;
	 }
	 }
	}
	/* 有序插入数据 */
	int list_insertby_sort(list_t *handler, void *data, cmp_t func)
	{
	 int i = 0;
	 node_t *new_node = NULL;
	 node_t *tmp = NULL;
	
	 new_node = node_create(data, handler->size);
	 if (NULL == new_node)
	 return -1;
	
	 for (tmp = handler->head; tmp != NULL; tmp = tmp->next) {
	 if (func(tmp->data, data) > 0)
	 break;
	 i++;
	 }
	 list_insertby_index(handler, data, i);
	
	 return 0;
	}
	
	/* 根据索引返回数据 */
	void *list_by_index(list_t *handler, int index)
	{
	 int i = 0;
	 node_t *tmp = NULL;
	
	 if (index < 0 || index > handler->len)
	 return NULL;
	 for (tmp = handler->head; tmp != NULL; tmp = tmp->next) {
	 if (index == i++)
	 return tmp->data;
	 }
	 return NULL;
	}
	
	/* 交换结点数据 */
	static void list_swap_data(char *data1, char *data2, int size)
	{
	 int i;
	
	 for (i = 0; i < size; i++) {
	 data1[i] ^= data2[i];
	 data2[i] ^= data1[i];
	 data1[i] ^= data2[i];
	 }
	}
	
	/* 对链表数据进行冒泡排序 */
	void list_sort(list_t *handler, cmp_t func)
	{
	 int i, j;
	 void *data1;
	 void *data2;
	
	 for (i = 0; i < handler->len; i++) {
	 for (j = 0; j < handler->len - i -1; j++) {
	 data1 = list_by_index(handler, j);
	 data2 = list_by_index(handler, j + 1);
	 if (func(data1, data2) > 0)
	 list_swap_data(data1, data2, handler->size);
	 }
	 }
	}
	
	/* 按照索引删除数据 */
	int list_delby_index(list_t *handler, int index, pfunc_t pfunc)
	{
	 node_t *tmp = NULL;
	 node_t *prev = NULL;
	 int i = 0;
	
	 if (index < 0 || index >= handler->len)
	 return -1;
	
	 if (0 == index) {
	 tmp = handler->head;
	 handler->head = handler->head->next;
	 } else {
	 for (tmp = handler->head; tmp != NULL; tmp = tmp->next) {
	 if (index == i++) {
	 prev->next = tmp->next;
	 break;
	 }
	 prev = tmp; //记录上一个
	 }
	 }
	 if (pfunc)
	 pfunc(tmp->data, 0);
	 free(tmp->data);
	 free(tmp);
	 handler->len --;
	 return 0;
	}
	/* 按照关键字删除数据 */
	int list_delby_key(list_t *handler, void *key, cmp_t func, pfunc_t pfunc)
	{
	 int i = 0;
	 void *data;
	
	 for (i = 0; i < handler->len; i++) {
	 data = list_by_index(handler, i);
	 if (func(data, key) == 0) {
	 list_delby_index(handler, i, pfunc); //删除数据过程中handler->len一直在变化
	 i--;
	 }
	 }
	 return 0;
	}
	
	/* 按照关键字查找一个数据 */
	void *list_findoneby_key(list_t *handler, void *key, cmp_t func)
	{
	 int i = 0;
	 void *data = NULL;
	
	 for (i = 0; i < handler->len; i++) {
	 data = list_by_index(handler, i);
	 if (0 == func(data, key))
	 return data;
	 }
	 return NULL;
	}
	
	/* 按照关键字查找所有数据 */
	list_t *list_findallby_key(list_t *handler, void *key, cmp_t func)
	{
	 int i = 0;
	 void *data = NULL;
	 list_t *new_list = NULL;
	
	 new_list = list_create(handler->size);
	 if (NULL == new_list)
	 return NULL;
	 for (i = 0; i < handler->len; i++) {
	 data = list_by_index(handler, i);
	 if (0 == func(data, key))
	 list_append(new_list, data);
	 }
	 return new_list;
	}
	
	/* 按照索引查找数据 */
	void *list_findby_index(list_t *handler, int index)
	{
	 return list_by_index(handler, index);
	}
	
	/* 查找中间数据 */
	void *list_find_mid(list_t *handler)
	{
	 node_t *mid = NULL;
	 node_t *tmp = NULL;
	
	 mid = handler->head;
	 tmp = handler->head;
	
	 while (tmp != NULL && tmp->next != NULL) {
	 mid = mid->next;
	 tmp = tmp->next->next;
	 }
	 return mid->data;
	}
	
	/* 链表逆置 */
	void list_reverse(list_t *handler)
	{
	 node_t *prev; //原链表上一个
	 node_t *tmp; //当前
	 node_t *next; //原链表下一个
	
	 prev = NULL;
	 tmp = handler->head;
	 next = tmp->next;
	
	 /* 将指针反转 */
	 while (next) {
	 tmp->next = prev;
	 prev = tmp;
	 tmp = next;
	 next = tmp->next;
	 }
	 tmp->next = prev;
	 handler->head = tmp;
	}
	
	/* 保存链表到文件中 */
	static char file_head[] = "LIST";
	int list_saveto_file(list_t *handler)
	{
	 node_t *tmp = NULL;
	 FILE *fp = NULL;
	
	 fp = fopen("list.db", "w");
	 if (NULL == fp) {
	 perror("fopen");
	 return -1;
	 }
	
	 fwrite(file_head, sizeof(file_head), 1, fp);
	 fwrite(&handler->size, sizeof(int), 1, fp);
	 fwrite(&handler->len, sizeof(int), 1, fp);
	 for (tmp = handler->head; tmp != NULL; tmp = tmp->next)
	 fwrite(tmp->data, handler->size, 1, fp);
	
	 fclose(fp);
	 return 0;
	}
	
	/* 加载文件到链表中 */
	list_t *list_loadfrom_file(void)
	{
	 list_t *handler = NULL;
	 char buf[20] = {};
	 int size;
	 int len;
	 int i;
	 void *data = NULL;
	 FILE *fp = NULL;
	
	 fp = fopen("list.db", "r");
	 if (NULL == fp) {
	 perror("fopen");
	 return NULL;
	 }
	
	 fread(buf, sizeof(file_head), 1, fp);
	 if (strncmp(buf, file_head, 4)) {
	 fclose(fp);
	 return NULL;
	 }
	
	 fread(&size, sizeof(int), 1, fp);
	 fread(&len, sizeof(int), 1, fp);
	 handler = list_create(size);
	 if (NULL == handler) {
	 fclose(fp);
	 return NULL;
	 }
	 data = malloc(size);
	 if (NULL == data) {
	 fclose(fp);
	 return NULL;
	 }
	 for (i = 0; i < len; i++) {
	 fread(data, size, 1, fp);
	 list_append(handler, data);
	 }
	
	 fclose(fp);
	 return handler;
	}
	
	/* 遍历链表 */
	void list_travel(list_t *handler, pfunc_t pfunc)
	{
	 node_t *tmp = NULL;
	 int index;
	
	 index = 0;
	 for (tmp = handler->head; tmp != NULL; tmp = tmp->next)
	 pfunc(tmp->data, index++);
	}
	/* 销毁链表 */
	void list_destroy(list_t *handler, pfunc_t pfunc)
	{
	 node_t *tmp = NULL;
	 node_t *save = NULL;
	
	 for (tmp = handler->head; tmp != NULL; tmp = save) {
	 save = tmp->next;
	 if (pfunc)
	 pfunc(tmp->data, 0);
	 free(tmp->data);
	 free(tmp);
	 tmp = NULL;
	 }
	 free(handler);
	}

	

	

	

	main.c

	#include <stdio.h>
	#include <stdlib.h>
	#include <string.h>
	#include "slist.h"
	
	#define NAME_MAX 20
	#define get_buf(fmt, buf, size) \
	 do { \
	 printf(fmt); \
	 fgets(buf, size, stdin); \
	 buf[strlen(buf) - 1] = '\0'; \
	 } while (0)
	
	typedef struct stu {
	 char name[NAME_MAX];
	 int age;
	}stu_t;
	/* 打印学生信息（回调函数） */
	void print_stu(const void *data, int index)
	{
	 const stu_t *stu = NULL;
	
	 stu = data;
	 if(stu)
	 printf("[%d]name:%10s age:%d\n", index, stu->name, stu->age);
	}
	
	/* 比较函数（回调）*/
	int cmp_int(const void *src, const void *dst)
	{
	 const stu_t *data1 = src;
	 const stu_t *data2 = dst;
	
	 return data1->age - data2->age;
	}
	
	/* 比较函数2(回调）*/
	int cmp_by_int(const void *data, const void *key)
	{
	 const stu_t *data1 = data;
	 const int *data2 = key;
	
	 return data1->age - *data2;
	}
	
	int get_stu(stu_t *stu)
	{
	 get_buf("Input name:", stu->name, NAME_MAX);
	 if (0 == strcmp(stu->name, "exit"))
	 return -1;
	 stu->age = random() % 10 + 20;
	 return 0;
	}
	
	int main(void)
	{
	 list_t *handler = NULL;
	 stu_t stu;
	
	 srandom(getpid());
	 handler = list_create(sizeof(stu_t));
	 if (NULL == handler)
	 return -1;
	 while (-1 != get_stu(&stu))
	 list_append(handler, &stu);
	 //list_prepend(handler, &stu);
	 //list_insertby_sort(handler, &stu, cmp_int);
	
	 list_travel(handler, print_stu);
	#if 1
	 /* 链表保存至文件 */
	 list_saveto_file(handler);
	#endif
	
	 list_destroy(handler, NULL);
	 return 0;
	}
	
	
	#if 0
	 /* 测试按照索引插入 */
	 list_travel(handler, print_stu);
	 int index;
	 while (1) {
	 if(-1 == get_stu(&stu))
	 break;
	 printf("input index:");
	 scanf("%d", &index);
	 getchar();
	 list_insertby_index(handler, &stu, index);
	 list_travel(handler, print_stu);
	 }
	#endif
	#if 0
	 /* 根据索引返回数据 */
	 int index;
	 while (1) {
	 printf("input index:");
	 scanf("%d", &index);
	 getchar();
	 print_stu(list_by_index(handler, index), 0);
	 }
	#endif
	#if 0
	 /* 测试冒泡排序 */
	 list_sort(handler, cmp_int);
	 puts("*************************");
	 list_travel(handler, print_stu);
	#endif
	#if 0
	 /* 根据索引删除数据 */
	 while (1) {
	 int index;
	 printf("input index:");
	 scanf("%d", &index);
	 getchar();
	 puts("************************");
	 list_delby_index(handler, index, print_stu);
	 puts("************************");
	 list_travel(handler, print_stu);
	 }
	#endif
	#if 0
	 /* 根据关键字删除数据 */
	 while (1) {
	 int key;
	 printf("input key:");
	 scanf("%d", &key);
	 getchar();
	 puts("************************");
	 list_delby_key(handler, &key, cmp_by_int, print_stu);
	 puts("************************");
	 list_travel(handler, print_stu);
	 }
	#endif
	#if 0
	 /* 根据关键字查找一个数据 */
	 while (1) {
	 int key;
	 printf("input key:");
	 scanf("%d", &key);
	 getchar();
	 puts("************************");
	 print_stu(list_findoneby_key(handler, &key, cmp_by_int), 0);
	 }
	#endif
	#if 0
	 /* 根据关键字查找所有数据 */
	 while (1) {
	 int key;
	 list_t *new_list = NULL;
	 printf("input key:");
	 scanf("%d", &key);
	 getchar();
	 puts("************************");
	 new_list = list_findallby_key(handler, &key, cmp_by_int);
	 list_travel(new_list, print_stu);
	 list_destroy(new_list, NULL);
	 }
	#endif
	#if 0
	 /* 根据索引查找数据 */
	 int index;
	 while (1) {
	 printf("input index:");
	 scanf("%d", &index);
	 getchar();
	 print_stu(list_findby_index(handler, index), 0);
	 }
	#endif
	#if 0
	 /* 查找中间数据 */
	 puts("********************");
	 print_stu(list_find_mid(handler), 0);
	#endif
	#if 0
	 /* 链表逆置 */
	 puts("********************");
	 list_reverse(handler);
	 list_travel(handler, print_stu);
	#endif
试试其它关键字
　单向链表　
同语言下
可能有用的
丁小莫贡献的其它代码(1)
.无头结点单向链表实现