C语言链表

1.定义结构体

注意Node的定义中的next。

struct film
{
    char title[TSIZE];
    int rating;
};

typedef struct film Item;

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

typedef struct
{
    Node* list;
}List;   //定义List是为了让地址可以顺利传入，以便初始化

2.链表初始化

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

3.确定链表是否为空

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

4.确定链表是否为满

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

5.确定链表项数

unsigned int ListItemCount(const List* plist)
{
    unsigned int count = 0;
    Node* pnode = plist->list;
    while (pnode != NULL)
    {
        ++count;
        pnode = pnode->next;
    }

    return count;
}

6.链表末尾添加项

bool AddItem(Item item, List* plist)
{
    Node* pnew;
    Node* scan = plist->list;

    pnew = (Node*)malloc(sizeof(Node));
    if (pnew == NULL)
        return false;

    CopyToNode(item, pnew);
    pnew->next = NULL;
    if (scan == NULL)
        plist->list = pnew;
    else
    {
        while (scan->next != NULL)
            scan = scan->next;
        scan->next = pnew;
    }

    return true;
}

void CopyToNode(Item item, Node* pnode)
{
    pnode->item = item;
}

7.遍历链表，把函数作用于每一项

void Traverse(const List* plist, void(*pfun)(Item item))
{
    Node* pnode = plist->list;
    while (pnode != NULL)
    {
        (*pfun)(pnode->item);
        pnode = pnode->next;
    }
}


void showmovies(Item item)
{
	printf("名字：%s 级别：%dn", item.title, item.rating);
}

8.释放所有已分配内存

void EmptyTheLlist(List* plist)
{
    Node* psave;

    while (plist->list = NULL)
    {
        psave = plist->list->next;
        free(plist->list);
        plist->list = psave;
    }
}

 该程序缺少在中间插入和删除。

List.h   函数接口

#ifndef LIST_H_
#define LIST_H_

#include 

#define TSIZE 45    //储存电影数目

struct film
{
    char title[TSIZE];
    int rating;
};

typedef struct film Item;

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

typedef struct
{
    Node* list;
}List;



void InitializeList(List* plist);


bool ListIsEmpty(const List* plist);


bool ListIsFull(const List* plist);


unsigned int ListItemCount(const List* plist);


bool AddItem(Item item, List *plist);


void Traverse(const List* plist, void (*pfun)(Item item));


void EmptyTheLlist(List* plist);

#endif

List.cpp   函数实现

#include
#include
#include "list.h"


static void CopyToNode(Item item, Node* pnode);


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


bool ListIsEmpty(const List* plist)
{
    if (plist == NULL)
        return true;
    else
        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->list;
    while (pnode != NULL)
    {
        ++count;
        pnode = pnode->next;
    }

    return count;
}


bool AddItem(Item item, List* plist)
{
    Node* pnew;
    Node* scan = plist->list;

    pnew = (Node*)malloc(sizeof(Node));
    if (pnew == NULL)
        return false;

    CopyToNode(item, pnew);
    pnew->next = NULL;
    if (scan == NULL)
        plist->list = 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->list;
    while (pnode != NULL)
    {
        (*pfun)(pnode->item);
        pnode = pnode->next;
    }
}


void EmptyTheLlist(List* plist)
{
    Node* psave;

    while (plist->list = NULL)
    {
        psave = plist->list->next;
        free(plist->list);
        plist->list = psave;
    }
}

void CopyToNode(Item item, Node* pnode)
{
    pnode->item = item;
}

films.cpp   链表应用

#include
#include
#include
#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, "没有储存可以利用！n");
		exit(1);
	}

	puts("输入电影名:");
	while (s_gets(temp.title, TSIZE) != NULL && temp.title[0] != '')
	{
		puts("输入级别0-10:");
		scanf_s("%d", &temp.rating);
		while (getchar() != 'n')
			continue;
		if (AddItem(temp, &movies) == false)
		{
			fprintf(stderr, "内存分配问题！n");
			break;
		}
		if (ListIsFull(&movies))
		{
			puts("链表已满！");
			break;
		}
		puts("输入下一个电影的名字（回车则停止）:");
	}

	if (ListIsEmpty(&movies))
	{
		printf("无数据！n");
	}
	else
	{
		printf("电影列表:n");
		Traverse(&movies, showmovies);
	}
	printf("有 %d 部电影n", ListItemCount(&movies));

	EmptyTheLlist(&movies);
	printf("退出成功!/n");

	return 0;
}

void showmovies(Item item)
{
	printf("名字：%s 级别：%dn", 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 = '';
		else
			while (getchar() != 'n')
				continue;
	}
	return ret_val;
}

 Lies never hurt anyone, the truth is the sharp knife！

谎言不会伤人，真相才是快刀！