鸟语天空

抽象数据类型(ADT)——链表

作者：追风剑情 发布于：2020-4-21 11:23 分类：C

示例：通过链表储存用户输入的影片信息

list.h

//#pragma once
//防止多次包含头文件
#ifndef LIST_H_
#define LIST_H_
#include <stdbool.h> /* C99特性 */

/* 特定程序的声明 */

#define TSIZE 45 /* 储存电影名的数组大小 */
struct film
{
	char title[TSIZE];
	int rating;
};

/* 一般类型定义 */
typedef struct film Item;

typedef struct node
{
	Item item;
	struct node * next;
} Node;

typedef Node * List;

/* List的另一种定义 */
/*
typedef struct list
{
	Node * head; //指向链表头的指针
	Node * end;  //指向链表尾的指针
	int size;	 //链表中的项数
} List;
*/

/* 函数原型 */

/* 操作：		初始化一个链表		*/
/* 前提条件：	plist指向一个链表	*/
/* 后置条件:	链表初始化为空		*/
void InitializeList(List * plist);

/* 操作：		确定链表是否为空，plist指向一个已初始化的链表		*/
/* 后置条件:	如果链表为空，该函数返回true；否则返回false			*/
bool ListIsEmpty(const List * plist);

/* 操作：		确定链表是否已满，plist指向一个已初始化的链表		*/
/* 后置条件:	如果链表已满，该函数返回true；否则返回false			*/
bool ListIsFull(const List * plist);

/* 操作：		确定链表中的项数，plist指向一个已初始化的链表		*/
/* 后置条件:	该函数返回链表中的基数								*/
unsigned int ListItemCount(const List * plist);

/* 操作：		在链表的末尾添加项												*/
/* 前提条件：	item是一个待添加至链表的项，plist指向一个已初始化的链表			*/
/* 后置条件:	如果可以，该函数在链表末尾添加一个项，且返回true，否则返回false	*/
bool AddItem(Item item, List * plist);

/* 操作：		把函数作用于链表中的每一项									*/
/*				plist指向一个已初始化的链表									*/		
/*				pfun指向一个函数，该函数接受一个Item类型的参数，且无返回值	*/
/* 后置条件:	pfun指向的函数作用于链表中的每一项一次						*/
void Traverse(const List * plist, void(*pfun)(Item item));

/* 操作：		释放已分配的内存（如果有的话）						*/
/*				plist指向一个已初始化的链表							*/
void EmptyTheList(List * plist);

#endif

list.c

#include <stdio.h>
#include <stdlib.h>
#include "list.h"

/* 局部函数原型 */
static void CopyToNode(Item item, Node * pnode);

void InitializeList(List * plist)
{
	*plist = NULL;
}

/* 如果链表为空，返回true */
bool ListIsEmpty(const List * plist)
{
	if (*plist == NULL)
		return true;
	return false;
}

/* 如果链表已满, 返回true */
bool ListIsFull(const List * plist)
{
	Node * pt;
	bool full;

	pt = (Node *)malloc(sizeof(Node));
	if (pt == NULL) //分配内存失败
		full = true;
	else
		full = false;
	free(pt);
	return full;
}

/* 返回节点的数量 */
unsigned int ListItemCount(const List * plist)
{
	unsigned int count = 0;
	Node * pnode = *plist; /* 设置链表的开始 */

	while (pnode != NULL)
	{
		++count;
		pnode = pnode->next; /* 设置下一个节点 */
	}
	return count;
}

/* 创建储存项的节点，并将其添加至由plist指向的链表末尾(较慢的实现) */
bool AddItem(Item item, List * plist)
{
	Node * pnew;
	Node * scan = *plist;
	pnew = (Node *)malloc(sizeof(Node));
	if (pnew == NULL) //分配内存失败
		return false;
	CopyToNode(item, pnew);
	pnew->next = NULL;
	if (scan == NULL) //如果链表为空
		*plist = pnew;
	else
	{
		while (scan->next != NULL)
			scan = scan->next; //找到链表的末尾
		scan->next = pnew; //把pnew添加到链表的末尾
	}
	return true;
}

/* 访问每个节点并执行pfun指向的函数 */
void Traverse(const List * plist, void(*pfun)(Item item))
{
	Node * pnode = *plist; /* 设置链表的开始 */
	while (pnode != NULL)
	{
		(*pfun)(pnode->item); /* 把函数应用于链表中的项 */
		pnode = pnode->next;
	}
}

/* 释放由malloc()分配的内存 */
/* 释放链表指针为NULL */
void EmptyTheList(List * plist)
{
	Node * psave;
	while (*plist != NULL)
	{
		psave = (*plist)->next;
		free(*plist);
		*plist = psave;
	}
}

/* 局部函数 */
/* 把一个项拷贝到节点中 */
static void CopyToNode(Item item, Node * pnode)
{
	pnode->item = item;
}

Main.c

#define _CRT_SECURE_NO_WARNINGS
//可以用#ifndef指令，防止多次包含一个文件
#include <stdio.h>
//提供malloc()原型
#include <stdlib.h>
//提供strcpy()原型
#include <string.h>
//提供CHAR_BIT的定义，CHAR_BIT表示每字节的位数
#include <limits.h>
//C99定义了bool、true、false
//如果编译器不支持bool,可以用枚举替代enum bool {false, true};
#include <stdbool.h>
#include "list.h"

void showmovies(Item item);
char* s_gets(char* st, int n);

int main(int argc, char* argv[])
{
	List movies;
	Item temp;

	/* 初始化 */
	InitializeList(&movies);
	if (ListIsFull(&movies))
	{
		fprintf(stderr, "No memory available! Bye!\n");
		exit(1);
	}

	/* 获取用户输入并储存 */
	puts("Enter first movie title:");
	while (s_gets(temp.title, TSIZE) != NULL &&
		temp.title[0] != '\0')
	{
		puts("Enter your rating<0-10>:");
		scanf("%d", &temp.rating);
		while (getchar() != '\n')
			continue;
		if (AddItem(temp, &movies) == false)
		{
			fprintf(stderr, "Problem allocating memory\n");
			break;
		}
		if (ListIsFull(&movies))
		{
			puts("The list is now full.");
			break;
		}
		puts("Enter next movie title (empty line to stop):");
	}

	/* 显示 */
	if (ListIsEmpty(&movies))
		printf("No data entered.");
	else
	{
		printf("Here is the movie list:\n");
		Traverse(&movies, showmovies);
	}
	printf("You entered %d movies.\n", ListItemCount(&movies));
	
	/* 清理 */
	EmptyTheList(&movies);
	printf("Bye!\n");

	system("pause");
	return 0;
}

void showmovies(Item item)
{
	printf("Movie: %s Rating: %d\n", item.title, item.rating);
}

// 自己实现读取函数
char* s_gets(char* st, int n)
{
	char* ret_val;
	int i = 0;
	ret_val = fgets(st, n, stdin);
	if (ret_val) //即，ret_val != NULL
	{
		while (st[i] != '\n' && st[i] != '\0')
			i++;
		if (st[i] == '\n')
			st[i] = '\0';
		else
			while (getchar() != '\n')
				continue;
	}
	return ret_val;
}

运行测试

标签: C语言