[数据结构与算法]c 链表模拟

链表头文件 list.h

#ifndef LIST_H_
#define LIST_H_

#include <stdbool.h>

#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;

/**
* 操作： 初始化一个链表
* 前置条件： 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);

/**
* 操作： 把函数作用于链表的每一项
* 前置条件： pfun指向一个函数，该函数接受一个Item类型的参数，且无返回值， plist指向一个已经初始化的链表
* 后置条件： 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;
}

bool ListIsEmpty(const List* plist)
{
	if (*plist == NULL) {
		return true;
	}
	return false;
}

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;
}

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;
	
	// 如果列表为空， 把pnew放在列表的开头
	if (scan == NULL) {
		*plist = pnew;
	}
	else {
		// 找到链表的末尾
		while (scan->next != NULL) {
			scan = scan->next;
		}
		scan->next = pnew;
	}

	return true;
}

void Traverse(const List* plist, void(*pfun)(Item item))
{
	Node* pnode = *plist;

	while (pnode != NULL) {
		// 把函数应用于链表中的项
		(*pfun)(pnode->item);
		pnode = pnode->next;
	}
}

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

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

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

int main(void)
{
	List movies;
	Item temp;

	InitializeList(&movies);

	if (ListIsFull(&movies)) {
		fprintf(stderr, "No memory available! \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_s("%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.\n");
	}
	else {
		printf("Here is the movies list: \n");
		Traverse(&movies, showmovies);
	}

	printf("You entered %d movies.\n", ListItemCount(&movies));

	EmptyTheList(&movies);
	printf("Done!\n");

	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;
	char* find;

	ret_val = fgets(st, n, stdin);
	if (ret_val) {
		find = strchr(st, '\n');
		if (find) {
			*find = '\0';
		}


		else {
			while (getchar() != '\n') {
				continue;
			}
		}
	}
	return ret_val;
}

来自《c primer plus》