c语言之————有头循环双链表实现队列存储_用双向链表作为队列的存储形式c语言

1、链表

dlist.h

/*
 *dlist.h
 *描述：
 *		有头循环双表
 *Data:
 *		2014-07-21
 */
 
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
struct node_info
{
	struct node_info *prev;
	struct node_info *next;
	char par[];  			/*0长数组，不占空间*/
};
 
struct list_info
{
	struct node_info head;
	/*
	 * 头插
	 */
	void (*add)(struct list_info *,size_t data_size,const void *data_entry);
	/*
	 * 尾插
	 */
	void (*add_tail)(struct list_info *,size_t data_size,const void *data_entry);
	/*
	 * 得到第一个数据
	 */
	void (*get)(struct list_info *,size_t data_size,void *data_entry);
	/*
	 * 获得最后一个数据
	 */
	void (*get_tail)(struct list_info *,size_t data_size, void *data_entry);
	/*
	 * 删除节点
	 */
	void (*del)(struct list_info *,struct node_info *);
	/*
	 * 判断节点是否为空
	 */
	int (*isempty)(struct list_info *);
};
 
void list_init(struct list_info*);
void list_destroy(struct list_info*);
 
#define PAR(node,type) ((type*)node->par)
 
#define list_for_each(info, cur) \
	for (cur = (info)->head.next; \
		(cur) != &(info)->head; \
		cur = (cur)->next)
 
#define list_for_each_safe(info, cur, tmp) \
	for (cur = (info)->head.next, tmp = (cur)->next; \
		(cur) != &(info)->head; \
		cur = tmp, tmp = (tmp)->next)

dlist.c

/*
 *dlist.c
 *
 */
 
#include "dlist.h"
 
static void list_add(struct list_info *info,size_t data_size,const void *data_entry)
{
	struct node_info *new_node = (struct node_info *)malloc(sizeof(struct node_info) + data_size);
 
	memcpy(new_node->par,data_entry,data_size);
 
	new_node->prev = &info->head;
	new_node->next = info->head.next;
	info->head.next = new_node;
	new_node->next->prev = new_node;//info->head.next->prev = new_node;
}
 
static void list_add_tail(struct list_info *info,size_t data_size,const void *data_entry)
{
	struct node_info *new_node = (struct node_info *)malloc(sizeof(struct node_info) + data_size);
 
	memcpy(new_node->par,data_entry,data_size);
 
	new_node->prev = info->head.prev;
	new_node->next = &info->head;
	info->head.prev->next = new_node;
	info->head.prev = new_node;		//new_node->prev->next = new_node;
}
 
static void list_get(struct list_info *info,size_t data_size,void *data_entry)
{
	memcpy(data_entry, info->head.next->par, data_size);
}
 
static void list_get_tail(struct list_info *info,size_t data_size,void *data_entry)
{
	memcpy(data_entry, info->head.prev->par, data_size);
}
 
static void list_del(struct list_info *info,struct node_info *node)
{
	node->prev->next = node->next;
	node->next->prev = node->prev;
 
	node->next = node;
	node->prev = node;
 
	free(node);
}
 
static int list_isempty(struct list_info *info)
{
//	return info->head.prev  == &info->head;
	return info->head.next == &info->head;
}
 
void list_init(struct list_info *info)
{
	info->head.prev = &info->head;
	info->head.next = &info->head;
	info->add = list_add;
	info->add_tail = list_add_tail;
	info->get = list_get;
	info->get_tail = list_get_tail;
	info->del = list_del;
	info->isempty = list_isempty;
}
 
void list_destroy(struct list_info *info)
{
	struct node_info *cur = NULL;
	struct node_info *tmp = NULL;
	list_for_each_safe(info, cur, tmp)
	{
		info->del(info, cur);
	}
}

2、队列

queue.h

/*
 * queue.h
 *队列原理是先进的先出
 */
 
#pragma once
 
#include "dlist.h"
 
struct queue_info
{
	struct list_info list;
	/*
	 * 入列
	 */
	void (*push)(struct queue_info *,size_t data_size,const void *data_entry);
 
	/*
	 * 出列
	 */
	int (*pop)(struct queue_info *,size_t data_size,void *data_entry);
 
	/*
	 * 队头
	 */
	int (*top)(struct queue_info *,size_t data_size,void *data_entry);
 
	/*
	 * 判断队列是否为空
	 */
	int (*isempty)(struct queue_info *);
};
 
struct queue_info *queue_init(struct queue_info *);
void queue_destroy(struct queue_info *);

queue.c

/*
 * queue.c
 *
 */
 
#include "queue.h"
 
 
static void queue_push(struct queue_info *info,size_t data_size,const void *data_entry)
{
	info->list.add_tail(&info->list,data_size,data_entry);
}
 
static int queue_top(struct queue_info *info,size_t data_size,void *data_entry)
{
	/*
	 * 如果队列为空，
	 */
	if(info->isempty(info))
	{
		return -1;
	}
	else
	{
		info->list.get(&info->list,data_size,data_entry);
		return 0;
	}
}
 
static int queue_pop(struct queue_info *info,size_t data_size,void *data_entry)
{
	/*
	 * 假如队列头不存在
	 */
	if(info->top(info,data_size,data_entry))
	{
		return -1;
	}
	else
	{
		info->list.del(&info->list,info->list.head.next);
		return 0;
	}
}
 
static int queue_isempty(struct queue_info *info)
{
	return info->list.isempty(&info->list);
}
 
struct queue_info *queue_init(struct queue_info *info)
{
	list_init(&info->list);
	info->push = queue_push;
	info->top = queue_top;
	info->pop = queue_pop;
	info->isempty = queue_isempty;
 
	return info;
}
 
void queue_destroy(struct queue_info *info)
{
	list_destroy(&info->list);
}

3、测试代码

test.c

/*
 * test.c
 *
 */
 
#include "queue.h"
 
struct data_info
{
	const char*name;
	size_t age;
};
 
int main()
{
	struct queue_info  queue;
	struct data_info s[] = {
			{"jack",20},
			[1] = {
					.name = "marry",
					.age = 22
			},
			[2] = {"peter",21}
			};
 
	queue_init(&queue);
 
	size_t i = 0;
	for(i = 0; i < sizeof(s)/sizeof(struct data_info);i ++)
	{
		queue.push(&queue,sizeof(struct data_info),s + i);
	}
 
	if(queue.isempty(&queue))
	{
		printf("queue is empty!\n");
	}
	else
	{
		printf("queue is not empty!\n");
	}
 
	struct data_info tmp;
	if(queue.top(&queue,sizeof(struct data_info),&tmp))
		printf("no top data!\n");
	else
	{
		printf("Top data is : name %s , age is %d \n",tmp.name,tmp.age);
	}
 
	queue_destroy(&queue);
 
	printf("After destroy stack ... \n");
	if(queue.isempty(&queue))
	{
		printf("queue is empty!\n");
	}
	else
	{
		printf("queue is not empty!\n");
	}
 
	return 0;
}

4、Makefile

all:test
 
test:test.o dlist.o queue.o
	gcc -o $@ $^
	
test.o:test.c
	gcc -c test.c
	
dlist.o:dlist.c
	gcc -c dlist.c
	
queue.o:queue.c
	gcc -c queue.c	
	
clean:
	rm *.o test

5、测试结果

queue is not empty!
Top data is : name jack , age is 20 
After destroy stack ... 
queue is empty!