C语言 算法与数据结构 五种双向链表的实现方法

第一种

llist.h

#ifndef __LLIST_H__
#define __LLIST_H__

#define LLIST_FORWARD 1
#define LLIST_BACKWARD 2

typedef void llist_op(void *);
typedef int llist_cmp(const void *,const void *);

struct llist_node_st
{
void *data;
struct llist_node_st *prev,*next;
};

typedef struct
{
int size;
struct llist_node_st head;
}LLIST;

LLIST *llist_create(int size);

int llist_insert(LLIST *, const void *data, int mode);

void *llist_find(LLIST *,const void *key,llist_cmp *cmp);

int llist_delete(LLIST *,const void *key,llist_cmp *cmp );

int llist_fetch(LLIST *,const void *key,llist_cmp *cmp, void *data );

void llist_travel(LLIST *,llist_op *op);

void llist_destroy(LLIST *);




#endif

llist.c

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

#include "llist.h"

LLIST *llist_create(int size)
{
	LLIST *ptr;

	ptr = malloc(sizeof(*ptr));
	if(ptr == NULL)
		return NULL;

	ptr->size = size;
	ptr->head.data = NULL;
	ptr->head.prev = ptr->head.next = &ptr->head;

	return ptr;
}

int llist_insert(LLIST *ptr, const void *data, int mode)
{

	struct llist_node_st *newnode;

	newnode = malloc(sizeof(*newnode));
	if(newnode == NULL)
		return -1;
	newnode->data = malloc(ptr->size);
	if(newnode->data == NULL)
	{
		free(newnode);
		return -2;
	}
	memcpy(newnode->data, data, ptr->size);

	if(mode == LLIST_FORWARD)
	{
		newnode->prev = &ptr->head;
		newnode->next = ptr->head.next;
	}
	else
	{
		if(mode == LLIST_BACKWARD)
		{
			newnode->next = &ptr->head;
			newnode->prev = ptr->head.prev;
		}
		else
			return -3;
	}
	newnode->prev->next = newnode;
	newnode->next->prev = newnode;	
	
	return 0;	
}

static struct llist_node_st *find_(LLIST *ptr,const void *key,llist_cmp *cmp)
{
	struct llist_node_st *cur;

    for(cur = ptr->head.next ;  cur != &ptr->head  ; cur = cur->next)
		if(cmp(cur->data,key) == 0)
			break;
	
	return cur;
}


void *llist_find(LLIST *ptr,const void *key,llist_cmp *cmp)
{
	return find_(ptr,key,cmp)->data;
}


int llist_delete(LLIST *ptr,const void *key,llist_cmp *cmp )
{
	struct llist_node_st *node;

	node = find_(ptr,key,cmp);
	if(node == &ptr->head)
		return -1;

	node->next->prev = node->prev;
	node->prev->next = node->next;

	free(node->data);
	free(node);
	return 0;
}

int llist_fetch(LLIST *ptr,const void *key,llist_cmp *cmp ,void *data)
{
	struct llist_node_st *node;

	node = find_(ptr,key,cmp);
	if(node == &ptr->head)
		return -1;

	node->next->prev = node->prev;
	node->prev->next = node->next;

	memcpy(data,node->data,ptr->size);
	free(node->data);
	free(node);
	return 0;
}


void llist_travel(LLIST *ptr,llist_op *op)//print_s
{
	struct llist_node_st *cur;

	for(cur = ptr->head.next ;  cur != &ptr->head  ; cur = cur->next)
		op(cur->data);
}

void llist_destroy(LLIST *ptr)
{
	struct llist_node_st *cur,*next;

	for(cur = ptr->head.next ;  cur != &ptr->head  ; cur = next)
	{
		next = cur->next;
		free(cur->data);
		free(cur);
	}
	free(ptr);
}

main.c

#include 
#include 
#include 

#include "llist.h"

#define NAMESIZE    32

struct score
{
	int id;
	char name[NAMESIZE];
	int math;
};

int id_cmp(const void *data,const void *key)
{
	const struct score *d = data;
	const int *id = key;
	return d->id - *id;
}
int name_cmp(const void *data,const void *key)
{
	const struct score *d = data;
	const char *name = key;
	return strcmp(d->name ,name);
}


void print_s(void *data)
{
	struct score *d = data;
	printf("%d %s %d\n",d->id,d->name,d->math);
}

int main()
{
	LLIST *handler;
	struct score tmp;
	int i;

	handler = llist_create(sizeof(struct score));
	if(handler == NULL)
	{
		printf("llist_create() error.\n");
		exit(1);
	}

	for(i = 0 ;i < 6; i++)
	{
		tmp.id = i;
		snprintf(tmp.name,NAMESIZE,"Stu%d",i);
		tmp.math = 100-i;

		llist_insert(handler,&tmp,LLIST_BACKWARD);
	}

	llist_travel(handler, print_s);
	printf("\n");

	int id = 1;
	char *name = "stu2";
	int math = 100;
	void *retp;

//	llist_delete(handler,&id,id_cmp);

	if(llist_fetch(handler,&id,id_cmp,&tmp) == 0)
		print_s(&tmp);
	printf("\n");	
	llist_travel(handler, print_s);


/*
//	retp = llist_find(handler,&id,id_cmp);
	retp = llist_find(handler,name,name_cmp);
	if(retp == NULL)
		printf("Can not find!\n");
	else
		print_s(retp);
*/
	llist_destroy(handler);
	exit(0);
}

第二种   数据可变长

llist.h

#ifndef __LLIST_H__
#define __LLIST_H__

#define LLIST_FORWARD	1
#define LLIST_BACKWARD	2

typedef void llist_op(void *);
typedef int llist_cmp(const void *,const void *);

struct llist_node_st
{
	struct llist_node_st *prev,*next;
	char data[1];
};

typedef struct
{
	int size;
	struct llist_node_st head;
}LLIST;

LLIST *llist_create(int size);

int llist_insert(LLIST *, const void *data, int mode);

void *llist_find(LLIST *,const void *key,llist_cmp *cmp);

int llist_delete(LLIST *,const void *key,llist_cmp *cmp );

int llist_fetch(LLIST *,const void *key,llist_cmp *cmp, void *data );

void llist_travel(LLIST *,llist_op *op);

void llist_destroy(LLIST *);



#endif

llist.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "llist.h"

LLIST *llist_create(int size)
{
	LLIST *ptr;

	ptr = malloc(sizeof(*ptr));
	if(ptr == NULL)
		return NULL;

	ptr->size = size;
	ptr->head.prev = ptr->head.next = &ptr->head;

	return ptr;
}

int llist_insert(LLIST *ptr, const void *data, int mode)
{

	struct llist_node_st *newnode;

	newnode = malloc(sizeof(*newnode)+ptr->size);
	if(newnode == NULL)
		return -1;
	memcpy(newnode->data, data, ptr->size);

	if(mode == LLIST_FORWARD)
	{
		newnode->prev = &ptr->head;
		newnode->next = ptr->head.next;
	}
	else
	{
		if(mode == LLIST_BACKWARD)
		{
			newnode->next = &ptr->head;
			newnode->prev = ptr->head.prev;
		}
		else
			return -3;
	}
	newnode->prev->next = newnode;
	newnode->next->prev = newnode;	
	
	return 0;	
}

static struct llist_node_st *find_(LLIST *ptr,const void *key,llist_cmp *cmp)
{
	struct llist_node_st *cur;

    for(cur = ptr->head.next ;  cur != &ptr->head  ; cur = cur->next)
		if(cmp(cur->data,key) == 0)
			break;
	
	return cur;
}


void *llist_find(LLIST *ptr,const void *key,llist_cmp *cmp)
{
	struct llist_node_st *node;
	node = find_(ptr,key,cmp);
	if(node == &ptr->head)
		return NULL;
	return node->data;
}


int llist_delete(LLIST *ptr,const void *key,llist_cmp *cmp )
{
	struct llist_node_st *node;

	node = find_(ptr,key,cmp);
	if(node == &ptr->head)
		return -1;

	node->next->prev = node->prev;
	node->prev->next = node->next;

	free(node);
	return 0;
}

int llist_fetch(LLIST *ptr,const void *key,llist_cmp *cmp ,void *data)
{
	struct llist_node_st *node;

	node = find_(ptr,key,cmp);
	if(node == &ptr->head)
		return -1;

	node->next->prev = node->prev;
	node->prev->next = node->next;

	memcpy(data,node->data,ptr->size);
	free(node);
	return 0;
}


void llist_travel(LLIST *ptr,llist_op *op)//print_s
{
	struct llist_node_st *cur;

	for(cur = ptr->head.next ;  cur != &ptr->head  ; cur = cur->next)
		op(cur->data);
}

void llist_destroy(LLIST *ptr)
{
	struct llist_node_st *cur,*next;

	for(cur = ptr->head.next ;  cur != &ptr->head  ; cur = next)
	{
		next = cur->next;
		free(cur);
	}
	free(ptr);
}

 

main.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "llist.h"

#define NAMESIZE    32

struct score
{
	int id;
	char name[NAMESIZE];
	int math;
};

int id_cmp(const void *data,const void *key)
{
	const struct score *d = data;
	const int *id = key;
	return d->id - *id;
}
int name_cmp(const void *data,const void *key)
{
	const struct score *d = data;
	const char *name = key;
	return strcmp(d->name ,name);
}


void print_s(void *data)
{
	struct score *d = data;
	printf("%d %s %d\n",d->id,d->name,d->math);
}

int main()
{
	LLIST *handler;
	struct score tmp;
	int i;

	handler = llist_create(sizeof(struct score));
	if(handler == NULL)
	{
		printf("llist_create() error.\n");
		exit(1);
	}

	for(i = 0 ;i < 6; i++)
	{
		tmp.id = i;
		snprintf(tmp.name,NAMESIZE,"Stu%d",i);
		tmp.math = 100-i;

		llist_insert(handler,&tmp,LLIST_BACKWARD);
	}

	llist_travel(handler, print_s);
	printf("\n");

	int id = 1;
	char *name = "stu2";
	int math = 100;
	void *retp;

//	llist_delete(handler,&id,id_cmp);

	if(llist_fetch(handler,&id,id_cmp,&tmp) == 0)
		print_s(&tmp);
	printf("\n");	
	llist_travel(handler, print_s);


/*
//	retp = llist_find(handler,&id,id_cmp);
	retp = llist_find(handler,name,name_cmp);
	if(retp == NULL)
		printf("Can not find!\n");
	else
		print_s(retp);
*/
	llist_destroy(handler);
	exit(0);
}

 

第三种  最常用 封装隐藏struct

llist.h

#ifndef __LLIST_H__
#define __LLIST_H__


typedef void LLIST;

#define LLIST_FORWARD	1
#define LLIST_BACKWARD	2

typedef void llist_op(void *);
typedef int llist_cmp(const void *,const void *);

LLIST *llist_create(int size);

int llist_insert(LLIST *, const void *data, int mode);

void *llist_find(LLIST *,const void *key,llist_cmp *cmp);

int llist_delete(LLIST *,const void *key,llist_cmp *cmp );

int llist_fetch(LLIST *,const void *key,llist_cmp *cmp, void *data );

void llist_travel(LLIST *,llist_op *op);

void llist_destroy(LLIST *);



#endif

llist.c

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

#include "llist.h"
#include "llist.h"

struct llist_node_st
{
	struct llist_node_st *prev,*next;
	char data[1];
};

struct llist_head_st
{
	int size;
	struct llist_node_st head;
};

LLIST *llist_create(int size)
{
	struct llist_head_st *ptr;

	ptr = malloc(sizeof(*ptr));
	if(ptr == NULL)
		return NULL;

	ptr->size = size;
	ptr->head.prev = ptr->head.next = &ptr->head;

	return ptr;
}

int llist_insert(LLIST *p, const void *data, int mode)
{
	struct llist_head_st *ptr = p;
	struct llist_node_st *newnode;

	newnode = malloc(sizeof(*newnode)+ptr->size);
	if(newnode == NULL)
		return -1;
	memcpy(newnode->data, data, ptr->size);

	if(mode == LLIST_FORWARD)
	{
		newnode->prev = &ptr->head;
		newnode->next = ptr->head.next;
	}
	else
	{
		if(mode == LLIST_BACKWARD)
		{
			newnode->next = &ptr->head;
			newnode->prev = ptr->head.prev;
		}
		else
			return -3;
	}
	newnode->prev->next = newnode;
	newnode->next->prev = newnode;	
	
	return 0;	
}

static struct llist_node_st *find_(struct llist_head_st *ptr,const void *key,llist_cmp *cmp)
{
	struct llist_node_st *cur;

    for(cur = ptr->head.next ;  cur != &ptr->head  ; cur = cur->next)
		if(cmp(cur->data,key) == 0)
			break;
	
	return cur;
}


void *llist_find(LLIST *p,const void *key,llist_cmp *cmp)
{
	struct llist_head_st *ptr = p;
	struct llist_node_st *node;
	node = find_(ptr,key,cmp);
	if(node == &ptr->head)
		return NULL;
	return node->data;
}


int llist_delete(LLIST *p,const void *key,llist_cmp *cmp )
{
	struct llist_node_st *node;
	struct llist_head_st *ptr = p;

	node = find_(ptr,key,cmp);
	if(node == &ptr->head)
		return -1;

	node->next->prev = node->prev;
	node->prev->next = node->next;

	free(node);
	return 0;
}

int llist_fetch(LLIST *p,const void *key,llist_cmp *cmp ,void *data)
{
	struct llist_head_st *ptr = p;
	struct llist_node_st *node;

	node = find_(ptr,key,cmp);
	if(node == &ptr->head)
		return -1;

	node->next->prev = node->prev;
	node->prev->next = node->next;

	memcpy(data,node->data,ptr->size);
	free(node);
	return 0;
}


void llist_travel(LLIST *p,llist_op *op)//print_s
{
	struct llist_head_st *ptr = p;
	struct llist_node_st *cur;

	for(cur = ptr->head.next ;  cur != &ptr->head  ; cur = cur->next)
		op(cur->data);
}

void llist_destroy(LLIST *p)
{
	struct llist_head_st *ptr = p;
	struct llist_node_st *cur,*next;

	for(cur = ptr->head.next ;  cur != &ptr->head  ; cur = next)
	{
		next = cur->next;
		free(cur);
	}
	free(ptr);
}

main.c

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

#include "llist.h"

#define NAMESIZE    32

struct score
{
	int id;
	char name[NAMESIZE];
	int math;
};

int id_cmp(const void *data,const void *key)
{
	const struct score *d = data;
	const int *id = key;
	return d->id - *id;
}
int name_cmp(const void *data,const void *key)
{
	const struct score *d = data;
	const char *name = key;
	return strcmp(d->name ,name);
}


void print_s(void *data)
{
	struct score *d = data;
	printf("%d %s %d\n",d->id,d->name,d->math);
}

int main()
{
	LLIST *handler;
	struct score tmp;
	int i;

	handler = llist_create(sizeof(struct score));
	if(handler == NULL)
	{
		printf("llist_create() error.\n");
		exit(1);
	}

	for(i = 0 ;i < 6; i++)
	{
		tmp.id = i;
		snprintf(tmp.name,NAMESIZE,"Stu%d",i);
		tmp.math = 100-i;

		llist_insert(handler,&tmp,LLIST_BACKWARD);
	}

	llist_travel(handler, print_s);
	printf("\n");

	int id = 1;
	char *name = "stu2";
	int math = 100;
	void *retp;

//	llist_delete(handler,&id,id_cmp);

	if(llist_fetch(handler,&id,id_cmp,&tmp) == 0)
		print_s(&tmp);
	printf("\n");	
	llist_travel(handler, print_s);


/*
//	retp = llist_find(handler,&id,id_cmp);
	retp = llist_find(handler,name,name_cmp);
	if(retp == NULL)
		printf("Can not find!\n");
	else
		print_s(retp);
*/
	llist_destroy(handler);
	exit(0);
}

 

第四种    函数指针传参

llist.h

#ifndef __LLIST_H__
#define __LLIST_H__

#define LLIST_FORWARD	1
#define LLIST_BACKWARD	2

typedef void llist_op(void *);
typedef int llist_cmp(const void *,const void *);

struct llist_node_st
{
	struct llist_node_st *prev,*next;
	char data[1];
};

typedef struct llist_head_st
{
	int size;
	struct llist_node_st head;
	int (*insert)(struct llist_head_st *, const void *data, int mode);
	void *(*find)(struct llist_head_st *,const void *key,llist_cmp *cmp);
	int (*delete)(struct llist_head_st *,const void *key,llist_cmp *cmp );
	int (*fetch)(struct llist_head_st *,const void *key,llist_cmp *cmp, void *data );
	void (*travel)(struct llist_head_st *,llist_op *op);
}LLIST;

LLIST *llist_create(int size);
void llist_destroy(LLIST *);



#endif

llist.c

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

#include "llist.h"

int llist_insert(LLIST *, const void *data, int mode);
void *llist_find(LLIST *,const void *key,llist_cmp *cmp);
int llist_delete(LLIST *,const void *key,llist_cmp *cmp );
int llist_fetch(LLIST *,const void *key,llist_cmp *cmp, void *data );
void llist_travel(LLIST *,llist_op *op);

LLIST *llist_create(int size)
{
	LLIST *ptr;

	ptr = malloc(sizeof(*ptr));
	if(ptr == NULL)
		return NULL;

	ptr->size = size;
	ptr->head.prev = ptr->head.next = &ptr->head;
	ptr->insert = llist_insert;
	ptr->delete = llist_delete;
	ptr->fetch = llist_fetch;
	ptr->find = llist_find;
	ptr->travel = llist_travel;

	return ptr;
}

int llist_insert(LLIST *ptr, const void *data, int mode)
{

	struct llist_node_st *newnode;

	newnode = malloc(sizeof(*newnode)+ptr->size);
	if(newnode == NULL)
		return -1;
	memcpy(newnode->data, data, ptr->size);

	if(mode == LLIST_FORWARD)
	{
		newnode->prev = &ptr->head;
		newnode->next = ptr->head.next;
	}
	else
	{
		if(mode == LLIST_BACKWARD)
		{
			newnode->next = &ptr->head;
			newnode->prev = ptr->head.prev;
		}
		else
			return -3;
	}
	newnode->prev->next = newnode;
	newnode->next->prev = newnode;	
	
	return 0;	
}

static struct llist_node_st *find_(LLIST *ptr,const void *key,llist_cmp *cmp)
{
	struct llist_node_st *cur;

    for(cur = ptr->head.next ;  cur != &ptr->head  ; cur = cur->next)
		if(cmp(cur->data,key) == 0)
			break;
	
	return cur;
}


void *llist_find(LLIST *ptr,const void *key,llist_cmp *cmp)
{
	struct llist_node_st *node;
	node = find_(ptr,key,cmp);
	if(node == &ptr->head)
		return NULL;
	return node->data;
}


int llist_delete(LLIST *ptr,const void *key,llist_cmp *cmp )
{
	struct llist_node_st *node;

	node = find_(ptr,key,cmp);
	if(node == &ptr->head)
		return -1;

	node->next->prev = node->prev;
	node->prev->next = node->next;

	free(node);
	return 0;
}

int llist_fetch(LLIST *ptr,const void *key,llist_cmp *cmp ,void *data)
{
	struct llist_node_st *node;

	node = find_(ptr,key,cmp);
	if(node == &ptr->head)
		return -1;

	node->next->prev = node->prev;
	node->prev->next = node->next;

	memcpy(data,node->data,ptr->size);
	free(node);
	return 0;
}


void llist_travel(LLIST *ptr,llist_op *op)//print_s
{
	struct llist_node_st *cur;

	for(cur = ptr->head.next ;  cur != &ptr->head  ; cur = cur->next)
		op(cur->data);
}

void llist_destroy(LLIST *ptr)
{
	struct llist_node_st *cur,*next;

	for(cur = ptr->head.next ;  cur != &ptr->head  ; cur = next)
	{
		next = cur->next;
		free(cur);
	}
	free(ptr);
}

main.c

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

#include "llist.h"

#define NAMESIZE    32

struct score
{
	int id;
	char name[NAMESIZE];
	int math;
};

int id_cmp(const void *data,const void *key)
{
	const struct score *d = data;
	const int *id = key;
	return d->id - *id;
}
int name_cmp(const void *data,const void *key)
{
	const struct score *d = data;
	const char *name = key;
	return strcmp(d->name ,name);
}


void print_s(void *data)
{
	struct score *d = data;
	printf("%d %s %d\n",d->id,d->name,d->math);
}

int main()
{
	LLIST *handler;
	struct score tmp;
	int i;

	handler = llist_create(sizeof(struct score));
	if(handler == NULL)
	{
		printf("llist_create() error.\n");
		exit(1);
	}

	for(i = 0 ;i < 6; i++)
	{
		tmp.id = i;
		snprintf(tmp.name,NAMESIZE,"Stu%d",i);
		tmp.math = 100-i;

		handler->insert(handler,&tmp,LLIST_BACKWARD);
	}

	handler->travel(handler, print_s);
	printf("\n");

	int id = 1;
	char *name = "stu2";
	int math = 100;
	void *retp;

//	llist_delete(handler,&id,id_cmp);

	if(handler->fetch(handler,&id,id_cmp,&tmp) == 0)
		print_s(&tmp);
	printf("\n");	
	handler->travel(handler, print_s);


/*
//	retp = llist_find(handler,&id,id_cmp);
	retp = llist_find(handler,name,name_cmp);
	if(retp == NULL)
		printf("Can not find!\n");
	else
		print_s(retp);
*/
	llist_destroy(handler);
	exit(0);
}

 

第五种   大佬级别  LINUX内核链表代码 kernel

llist.h

#ifndef __LIST_H__
#define __LIST_H__

struct list_head
{
	struct list_head *prev,*next;
};

#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \
	struct list_head name = LIST_HEAD_INIT(name)


static inline void __list_add(struct list_head *new,
		struct list_head *prev,
		struct list_head *next)
{
	next->prev = new;
	new->next = next;
	new->prev = prev;
	prev->next = new;
}

static inline void list_add(struct list_head *new, struct list_head *head)
{
	__list_add(new, head, head->next);
}

static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
	__list_add(new, head->prev, head);
}


#define list_for_each(pos, head) \
	for (pos = (head)->next; pos != (head); pos = pos->next)


/*
* list_entry - get the struct for this entry
* @ptr:    the &struct list_head pointer.
* @type:   the type of the struct this is embedded in.
* @member: the name of the list_head within the struct.
*/

#define offsetof(TYPE, MEMBER)  ((size_t)&((TYPE *)0)->MEMBER)

#define container_of(ptr, type, member) ({          \
		const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
		(type *)( (char *)__mptr - offsetof(type,member) );})

#define list_entry(ptr, type, member) \
	container_of(ptr, type, member)

#endif

 

main.c

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

#include "list.h"

#define NAMESIZE    32
struct score
{
	int id;
	char name[NAMESIZE];
	int math;
	struct list_head node;
};

void print_s(void *data)
{
	struct score *d = data;
	printf("%d %s %d\n",d->id,d->name,d->math);
}

int main()
{
	struct score *tmp;
	struct list_head  *cur;
	int i;

	LIST_HEAD(head);

	for(i = 0 ;i < 6; i++)
	{
		tmp = malloc(sizeof(*tmp));
		/*if error*/

		tmp->id = i;
		snprintf(tmp->name,NAMESIZE,"Stu%d",i);
		tmp->math = 100-i;

		list_add_tail(&tmp->node ,&head);
	}


	list_for_each(cur, &head)
	{
		tmp = list_entry(cur, struct score, node);
		print_s(tmp);
	}

	exit(0);
}

 

© 版权声明
THE END
喜欢就支持一下吧
点赞12 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片

    暂无评论内容