本文共 3228 字，大约阅读时间需要 10 分钟。

C语言链表实现实例

在学习C语言的时候，链表是一种非常基础而实用的数据结构。通过一个简单的电影存储系统，来理解链表的实现原理。

链表的概念

链表是一种由节点组成的数据结构，每个节点包含数据部分和指向下一个节点的指针。这样的结构具有灵活性和扩展性，特别适合动态内存分配场景。

实现链表

首先，我们需要定义链表的节点结构。每个节点包含一个数据项和一个指向下一个节点的指针。在本例中，节点存储电影的标题和评分。

typedef struct {
    char title[TSIZE];
    int rating;
} Item;
typedef struct node {
    Item item;
    struct node* next;
} Node;
typedef Node* List;

链表操作

链表的实现通常包括初始化、检查是否为空或满、添加新项、遍历以及清空等基本操作。这些操作需要通过函数实现。

初始化链表

链表的初始化需要分配内存并将头节点设置为空。

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

检查链表状态

检查链表是否为空或是否已满需要遍历链表。

bool ListIsEmpty(const List* plist) {
    return *plist == NULL;
}
bool ListIsFull(const List* plist) {
    Node* pt = malloc(sizeof(Node));
    if (pt == NULL) {
        free(pt);
        return true;
    }
    free(pt);
    return false;
}

添加新项

添加新项需要分配内存，复制数据并连接到链表的适当位置。

bool AddItem(Item item, List* plist) {
    Node* pnew = malloc(sizeof(Node));
    if (pnew == NULL) {
        return false;
    }
    pnew->item = item;
    pnew->next = NULL;
    if (*plist == NULL) {
        *plist = pnew;
    } else {
        Node* scan = *plist;
        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 = NULL;
    while (*plist != NULL) {
        psave = (*plist)->next;
        free(*plist);
        *plist = psave;
    }
}

实际应用中，链表的具体实现需要根据需求进行调整。以下是链表操作的完整示例代码：

#include 
   
    
#include 
    
     
#include "headfile.h"
void showmovies(Item item);
char* s_gets(char* st, int n);
int main() {
    List movies = NULL;
    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_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.");
    } else {
        printf("Here is the movie list:\n");
        Traverse(&movies, showmovies);
    }
    printf("You have entered %d movies.\n", ListItemCount(&movies));
    EmptyTheList(&movies);
    printf("Bye!\n");
    return 0;
}
void showmovies(Item item) {
    printf("Movies: %s Rating: %d\n", item.title, item.rating);
}
char* s_gets(char* st, int n) {
    char* val, *find;
    val = fgets(st, n, stdin);
    if (val) {
        find = strchr(st, '\n');
        if (find) {
            *find = '\0';
        } else {
            while (getchar() != '\n') {
                continue;
            }
        }
    }
    return val;
}