雅乐网

本程序托管在开源中国http://git.oschina.net/cryt/c_adt

该程序包含list.h头文件，包含结构体以及函数的声明， list.c文件，包含具体函数的实现，demo.c为演示程序。

本链表数据结构如下：

list结构体 表示整体的一个链表

listnode是结点定义

而listnode中的指针pelem指向的是元素的具体内容。

Pelem声明为void *类型。这可以使得链表可以是不同的类型。也就是说，可以在同一个程序中使用不同类型的多个链表。

本程序中链表设置了头结点和尾结点，这给许多操作带来方便。头结点和尾结点并不包含数据。链表初始化的时候，头结点指向尾结点，尾结点指向头结点。头结点的后继是首节点，尾结点的前驱是末节点。头结点和尾结点只是为了方便操作，它们存在于链表的整体定义中，地址保持不变。

 list.h

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

#define BOOL int
#define TRUE 1
#define FALSE 0

//链表结点结构 存储一个结点
typedef struct listnode{
	void * pelem;	//抽象的数据域 可以指向任何类型
	struct listnode * pre;	//指向上一个结点
	struct listnode * next;	//指向下一个结点
} listnode;
//链表结构 储存整个链表
typedef struct list{
	int elemsize;	//链表结点指向的数据域的大小
	int listsize;	//链表中元素的个数
	struct listnode header;	//头结点
	struct listnode trailer;	//尾结点
} list;

list * list_init(int elemsize);	//初始化链表
BOOL getpos_invalid(list * pL, int i);	//判断取值元素的位置是否符合要求
BOOL list_exist(list * pL);	//判断链表是否存在
BOOL list_empty(list * pL);	//判断链表是否为空 若不存在则不为空
BOOL getpos_invalid(list * pL, int i);	//判断元素位置是否合法
BOOL putpos_invalid(list * pL, int i);	//判断要插入的位置是否合法 尾指针算一个
BOOL list_getelem(list * pL, int i, void * pe);	//取第几个元素放到pe指向的结构
listnode * list_getp(list * pL, int i);	//根据位置返回该位置的结点指针，可能是尾指针
BOOL list_insert(list * pL, listnode * p, void * pe);	//在某结点位置前插入结点 可能是尾结点之前
BOOL list_travel(list * pL, void visit());	//遍历链表 执行visit操作
BOOL list_clear(list * pL);	//清空链表
BOOL list_destroy(list ** pL);	//销毁链表
BOOL list_remove(list * pL, listnode * pnode, void *p);	//删除一个元素
int list_length(list * pL);	//判断列表长度
int list_locateelem(list * pL, void * pe, BOOL compare());
BOOL list_priorelem(list * pL, void * pe, void * pre_e);
BOOL list_nextelem(list * pL, void * pe, void * next_e);
BOOL equal(void * a, void * b);

BOOL savelist(list * pL);
BOOL loadlist(list ** pL);

 list.c

//初始化链表
list * list_init(int elemsize)
{
	list * pL;

	if((pL = (list *)malloc(sizeof(list))) == NULL)
		exit(-1);
	pL->elemsize = elemsize;
	pL->listsize = 0;
	pL->header.pelem = NULL;
	pL->header.next = &(pL->trailer);
	pL->header.pre = NULL;
	pL->trailer.pelem = NULL;
	pL->trailer.pre = &(pL->header);
	pL->trailer.next = NULL;

	return pL;
}
//清空链表 链表不存在时 返回错误
BOOL list_clear(list * pL)
{
	listnode * p, *q;
	int i;
	if (list_exist(pL) == FALSE)
		return FALSE;
	if (pL->listsize == 0)
		return TRUE;
	p = pL->header.next;
	i = 1;
	while (i <= pL->listsize)
	{
		free(p->pelem);
		q = p;
		p = p->next;
		free(q);
		i++;
	}
	pL->header.next = &pL->trailer;
	pL->trailer.pre = &pL->header;
	pL->listsize = 0;

	return TRUE;
}
//销毁链表 若本来就不存在 返回成功
BOOL list_destroy(list ** pL)
{
	if (list_exist(*pL) == FALSE)
		return TRUE;
	if (list_clear(*pL) == FALSE)
		return FALSE;
	free(*pL);
	*pL = NULL;
	
	return TRUE;
}
//判断列表是否存在
BOOL list_exist(list * pL)
{
	return (pL == NULL) ? FALSE : TRUE;
}
//判断链表是否为空
BOOL list_empty(list * pL)
{
	if (list_exist(pL) == FALSE)
		return FALSE;
	if (pL->listsize == 0)
		return TRUE;
	return FALSE;
}
//判断位置是否在合理区间 1到元素总数
BOOL getpos_invalid(list * pL, int i)
{
	if (list_exist(pL) == FALSE)
		return FALSE;
	if (i < 1 || i > pL->listsize)
		return FALSE;
	else
		return TRUE;
}
//判断位置是否合理 1到总数+1  尾指针
BOOL putpos_invalid(list * pL, int i)
{
	if (list_exist(pL) == FALSE)
		return FALSE;
	if (i < 1 || i > pL->listsize + 1)
		return FALSE;
	else
		return TRUE;
}
//根据位置返回该位置结点指针 可能是尾指针
listnode * list_getp(list * pL, int i)
{
	int j;
	listnode * p;	//可能指向尾指针
	if (putpos_invalid(pL, i) == FALSE)
		return NULL;
	j = 1;
	p = pL->header.next;
	while (j < i)
	{
		p = p->next;
		j++;
	}
	
	return p;
}
//根据位置把该位置的元素复制到pe指向的内存
BOOL list_getelem(list * pL, int i, void * pe)
{
	int j;
	listnode * p;
	if (getpos_invalid(pL, i) == FALSE)
		return FALSE;
	j = 1;
	p = pL->header.next;
	while (j < i)
	{
		p = p->next;
		j++;
	}
	memcpy(pe, p->pelem, pL->elemsize);
	return TRUE;
}
//插入元素 插入在p结点之前 p可能是尾指针
BOOL list_insert(list * pL, listnode * p, void * pe)
{
	listnode * pnode;

	if((pnode = (listnode *)malloc(sizeof(listnode))) == NULL)
		exit(-1);
	pnode->pelem = malloc(pL->elemsize);
	memcpy(pnode->pelem, pe, pL->elemsize);

	p->pre->next = pnode;
	pnode->pre = p->pre;
	pnode->next = p;
	p->pre = pnode;

	pL->listsize++;
	
	return TRUE;
}
//遍历对元素进行visit()操作
BOOL list_travel(list * pL, void visit())
{
	listnode * p;
	int i;
	if (list_exist(pL) == FALSE)
	{
		printf("链表不存在!");
		return FALSE;
	}
	if (list_empty(pL) == TRUE)
	{
		printf("是空表!");
		return FALSE;
	}
	i = 1;
	p = pL->header.next;
	while (i <= pL->listsize)
	{
		printf("第%d个:\t", i);
		visit(p->pelem);
		p = p->next;
		i++;
	}
	return TRUE;
}
//保存到文件
BOOL savelist(list * pL)
{
	FILE  * out;
	listnode * p;
	int i;
	if (list_exist(pL) == FALSE)
		return FALSE;
	if ((out = fopen("list.dat", "wb")) == NULL)
		return FALSE;
	fwrite(&pL->listsize, sizeof(pL->listsize), 1, out);
	fwrite(&pL->elemsize, sizeof(pL->elemsize), 1, out);
	p = pL->header.next;
	i = 1;
	while (i <= pL->listsize)
	{
		fwrite(p->pelem, pL->elemsize, 1, out);
		p = p->next;
		i++;
	}
	fclose(out);
	return TRUE;
}
//从文件加载
BOOL loadlist(list ** pL)
{
	FILE * in;
	listnode * p, * q;
	int i;
	if (list_destroy(pL) == FALSE)
		return FALSE;
	if ((in = fopen("list.dat", "rb")) == NULL)
		return FALSE;
	if (((*pL) = (list *)malloc(sizeof(list))) == NULL)
		exit(-1);

	fread(&(*pL)->listsize, sizeof((*pL)->listsize), 1, in);
	fread(&(*pL)->elemsize, sizeof((*pL)->elemsize), 1, in);
	(*pL)->header.pelem = NULL;
	(*pL)->header.next = &((*pL)->trailer);
	(*pL)->header.pre = NULL;
	(*pL)->trailer.pelem = NULL;
	(*pL)->trailer.pre = &((*pL)->header);
	(*pL)->trailer.next = NULL;

	
	i = 1;
	q = &((*pL)->header);
	while (i <= (*pL)->listsize)
	{
		if((p = (listnode *)malloc(sizeof(listnode))) == NULL)
			exit(-1);
		p->pelem = malloc((*pL)->elemsize);
		fread(p->pelem, (*pL)->elemsize, 1, in);
		q->next = p;
		p->pre = q;
		q = p;
		i++;
	}
	q->next = &(*pL)->trailer;
	(*pL)->trailer.pre = q;

	return TRUE;
}
//删除单个元素 根据元素内容*pnode找到该节点 并将删除的元素放到p
BOOL list_remove(list * pL, listnode * pnode, void *p)
{
	if (list_exist(pL) == FALSE || list_empty(pL) == TRUE)
		return FALSE;
	pnode->pre->next = pnode->next;
	pnode->next->pre = pnode->pre;
	memcpy(p, pnode->pelem, pL->elemsize);
	free(pnode);
	pL->listsize--;

	return TRUE;
}
//返回列表有效元素个数
int list_length(list * pL)
{
	if (list_exist(pL) == TRUE)
		return pL->listsize;
	else
		return -1;
}
//根据规则查找列表中第一个满足要求的元素 放到pe中
int list_locateelem(list * pL, void * pe, BOOL compare())
{
	listnode * p;
	int i;
	p = pL->header.next;
	i = 1;
	while (i <= pL->listsize)
	{
		if (compare(p->pelem, pe) == TRUE)
			return i;
		p = p->next;
		i++;
	}
	return 0;	
}
//求前驱元素 
BOOL list_priorelem(list * pL, void * pe, void * pre_e)
{
	int i;
	if (list_exist(pL) == FALSE || list_empty(pL) == TRUE)
		return FALSE;
	if((i = list_locateelem(pL, pe, &equal)) == 0 || i == 1)
		return FALSE;
	if (list_getelem(pL, i-1, pre_e) == TRUE)
		return TRUE;
	else
		return FALSE;
}
//求后继元素
BOOL list_nextelem(list * pL, void * pe, void * next_e)
{
	int i;
	if (list_exist(pL) == FALSE || list_empty(pL) == TRUE)
		return FALSE;
	if((i = list_locateelem(pL, pe, &equal)) == 0 || i == pL->listsize)
		return FALSE;
	if (list_getelem(pL, i+1, next_e) == TRUE)
		return TRUE;
	else
		return FALSE;
}

 demo.c

#include "list.h"
#include "list.c"

#define ElemType student
typedef struct {
	char name[20];
	int age;
} student;

void display(void *stu);
void menu(void);
void inputstu(student * p);	//输入学生信息
void inputindex(int *);	//输入位置信息


int main(void){
	list * pL;
	student * pe;
	listnode * pnode;
	student pre_e, next_e;
	int op;
	int i;
	op = 0;
	pL = NULL;
	if ((pe = (student *)malloc(sizeof(student))) == NULL)
		exit(-1);
	do{
		 system("cls");
		 menu();
		 printf("          Please input your option[0-12]:");
		 scanf("%d",&op);
		 switch(op){
			 case 0: break;
			 case 1: //初始化列表
				 if (list_exist(pL) == TRUE || list_empty(pL) == FALSE)
					 list_destroy(&pL);
				 if ((pL = list_init(sizeof(student))) != NULL)
				 {
					 printf("初始化成功!");
					  getchar();getchar();
				 }
				 else
				 {
					 printf("初始化失败!");
					  getchar();getchar();
				 }			 break;
			 case 2: //插入元素
				 inputindex(&i);
				 inputstu(pe);

				 if ((pnode = (list_getp(pL, i))) == NULL)
				 {
					 printf("位置不对或者链表不存在!");
					 getchar();getchar();
					 break;
				 }
				 if (list_insert(pL, pnode, pe) == TRUE)
					 printf("插入成功!");
				 else
					 printf("插入失败!");
				 getchar();getchar();
							 break;
			 case 3: //销毁列表
				 if(list_destroy(&pL) == TRUE)
					 printf("销毁成功!");
				getchar();getchar();
				break;
			 case 4: //清空列表
				 if(list_clear(pL) == TRUE)
				 {
					 printf("清空成功!");
					getchar();getchar();
				 }
				 else
				 {
					printf("列表不存在!");
				 	getchar();getchar();
				 }
				break;
		/*	 case 5: //删除区间
				 printf("请输入区间");
				 scanf("%d %d", &lo, &hi);
				 if(list_delete(pL, lo, hi) == FALSE)
				 {
					 printf("删除失败");
					getchar();getchar();
				 }
				 else
				{
					 printf("删除成功!");
					getchar();getchar();
				 }
				 break;*/
			 case 6: //删除某元素
				inputindex(&i);
				if (getpos_invalid(pL, i) == FALSE)
				{
					printf("位置不合法或列表不存在");
					getchar();getchar();
					break;
				}
				if ((pnode = list_getp(pL, i)) == NULL)
				{
					printf("删除失败!");
					getchar();getchar();
					break;
				}
				if(list_remove(pL, pnode, pe) == TRUE)
				{
					printf("第%d个元素", i);
					display(pe);
					printf("删除成功");
					getchar();getchar();
				}
				else
				{
					printf("删除失败!");
					getchar();getchar();
				}
							 
							 break;
			 case 7: //判断列表是否存在
				 if (list_exist(pL) == TRUE)
				 {
					 printf("列表存在!");
					 getchar();getchar();
				 }
				 else
				 {
					 printf("列表不存在!");
					 getchar();getchar();
				 }
				break;
			 case 8: //判断列表是否为空
				 if (list_exist(pL) == FALSE)
				 {
					 printf("列表不存在!");
					getchar();getchar();
					break;
				 }
				if (list_empty(pL) == TRUE)
				 {
					 printf("列表为空!");
					 getchar();getchar();
				 }
				 else
				 {
					 printf("列表不为空!");
					 getchar();getchar();
				 }
				 break;
			 case 9: //遍历元素
				 list_travel(pL, &display);
							 getchar();getchar();
							 break;
			 case 10: //求列表长度
				 if (list_exist(pL) == FALSE)
				 {
					 printf("列表不存在!");
					getchar();getchar();
					break;
				 }
				 printf("列表长度是%d", list_length(pL));
					getchar();getchar();
				break;
			 case 11: //按位置查找元素
				 inputindex(&i);
				if (getpos_invalid(pL, i) == FALSE)
				{
					printf("位置不合法或列表不存在");
					getchar();getchar();
					break;
				}
				if ((pnode = list_getp(pL, i)) == NULL)
				{
					printf("失败!");
					getchar();getchar();
					break;
				}
				display(pnode->pelem);
				getchar();getchar();
				break;
			 case 12: //按元素查找位置
				 inputstu(pe);
				 if ((i = list_locateelem(pL, (void *)pe, &equal)) == 0)
				 {
					 printf("查找失败!");
					getchar(); getchar();
				 }
				 else
				 {
					 printf("是第%d个元素", i);
					 getchar(); getchar();
				 }
								 break;
			 case 13: //求前驱元素
				 inputstu(pe);
				 if(list_priorelem(pL, pe, &pre_e) == TRUE)
				 {
					 display(pe);
					 printf("的前驱元素是");
					 display(&pre_e);
					getchar(); getchar();
				 }
				 else
				 {
					 printf("查找前驱元素失败!");
					 getchar(); getchar();
				 }
								 break; 
			 case 14: //求后继元素
				 	inputstu(pe);
				 if(list_nextelem(pL, pe, &next_e) == TRUE)
				 {
					 display(pe);
					 printf("的后继元素是");
					 display(&next_e);
					getchar(); getchar();
				 }
				 else
				 {
					 printf("查找后继元素失败!");
					 getchar(); getchar();
				 }
								 break;
			 case 15: //保存到文件
				 if(savelist(pL) == TRUE)
				 {
					 printf("保存成功!");
					 getchar(); getchar();
				 }
				 else
				 {
					 printf("保存失败!");
					 getchar(); getchar();
				 }
				break;
			 case 16: //从文件加载
				  if(loadlist(&pL) == TRUE)
				  {
					 printf("加载成功!");
					 getchar(); getchar();
				  }
				  else
				  {
					 printf("加载失败!");
					 getchar(); getchar();
				  }
				 break;							
			 default: ;
		 }
	}while(op);
	printf("\n--------------------Welcome again!--------------------\n");
	getchar();getchar();

	return 0;
}

void display(void *stu)
{
	printf("姓名:%s\t年龄%d\n", ((student *)stu)->name, ((student *)stu)->age);
}

void menu(void){
	printf("\n\n");
	printf("      Menu for Linear Table On Sequence Structure \n");
	printf("------------------------------------------------------\n");
	printf("\t修改类\t\t\t查找类\n");
	printf("\t1. 初始化列表\t\t7. 判断列表是否存在\n");
	printf("\t2. 插入元素\t\t8. 判断列表是否为空\n");
	printf("\t3. 销毁列表\t\t9. 遍历列表元素\n");
	printf("\t4. 清空列表\t\t10. 列表长度\n");
	printf("\t5. 删除区间\t\t11. 按位置查找元素\n");
	printf("\t6. 删除某元素\t\t12. 按元素查找位置\n");
	printf("\t\t\t\t13. 求某元素前驱元素\n");
	printf("\t\t\t\t14. 求某元素后继元素\n");
	printf("\t文件类");
	printf("\n\t15. Savelist\t\t16. Loadlist\n");
	printf("    	  0. Exit\n");
	printf("------------------------------------------------------\n");
	
}

void inputstu(student * p)
{
	printf("请输入学生姓名:");
	scanf("%s", p->name);
	printf("请输入年龄:");
	scanf("%d", &p->age);
	
}
void inputindex(int * i)
{
	printf("请输入位置:");
	scanf("%d", i);
}

//判断两个元素是否相等
BOOL equal(void * a, void * b)
{
	student * p1 , * p2;
	p1 = a;
	p2 = b;
	if ((strcmp(p1->name, p2->name) == 0) && p1->age == p2->age)
		return TRUE;
	else
		return FALSE;
}