简介：这份数据结构课程设计报告围绕图书管理信息系统的设计与实现展开，面向通信工程、物联网及计算机相关专业学生，适合作为课程设计参考或期末大作业模板。报告以C语言为实现语言，系统讲解图书采编、编目、查询及借还书等核心业务的完整设计思路，并深入剖析数组、链表、树形结构、Hash表、队列与栈等数据结构在图书信息存储、快速检索和流通管理中的具体应用。压缩包内仅含1个doc文档，约119KB，内容涵盖图书信息数据库设计、以书号为关键字的索引文件构建、书名与作者及出版社的次关键字索引链头文件设计，以及借书人和图书结构体信息定义。文中还给出buy()、SearchByNum()、SearchByName()、borrow()、return()等函数与模块化设计方案，并附有折半查找等关键代码片段。目前已有1381人学习下载，适合需要完整赛题方案、代码框架与排错思路的读者参考借鉴。

1. 图书管理信息系统：从链表到索引，一份能跑起来的课程设计

做过课程设计的人都懂那种感觉：题目发下来一看是“图书管理信息系统”，心里先松一口气——不就是增删改查吗？真动手才发现，图书的借阅记录要按时间排、读者要按学号查、热门书要按借阅次数统计，这些操作背后全是数据结构在撑着。用数组硬扛，插入删除要搬半个表；用链表，查找又得从头遍历到尾。这门课设真正要你交的不是一个能跑的界面，而是一套说得清选型理由、测得出性能差异、扛得住答辩追问的数据结构方案。

这份课程设计报告的核心，是把图书、读者、借阅记录三类实体抽象成合适的存储结构，再用索引把高频查询压到可接受的时间复杂度。它适合正在做数据结构课设的本科生，也适合想回头补一补“链表和索引到底怎么配合”的开发者。下面按“先定结构、再写操作、最后调性能”的顺序，把每一步落到能复现的代码和参数上。

2. 图书管理信息系统的数据结构选型：链表、顺序表还是索引表

2.1 三类实体分别该用什么结构

图书管理信息系统里最容易被忽略的是：不同实体的访问模式完全不同。图书主表以“按 ISBN 精确查”和“按书名模糊查”为主，插入频率低；借阅记录表以“追加新记录”和“按读者查历史”为主，插入频率高；读者表则以“按学号查”为主，规模相对稳定。

我一般这样分配：图书主表用顺序表加哈希索引，因为图书数量可控（几千到几万），顺序存储对缓存友好，哈希索引把 ISBN 查询压到 O(1)；借阅记录用单链表，因为借阅是持续追加的，链表尾插 O(1)，不需要预分配容量；读者表用顺序表加二分查找，学号天然有序，排序一次之后查询稳定在 O(log n)。

注意：不要一上来就全用链表。链表在插入删除上有优势，但随机访问是硬伤，图书查询这种高频操作放在链表上会让整个系统变慢。

2.2 单链表的节点定义与尾插建表

借阅记录用单链表，节点里存读者学号、ISBN、借出日期、归还日期。下面这段 C 代码是尾插建表的标准写法，带尾指针，避免每次插入都从头遍历。

#include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct BorrowNode { char student_id[16]; // 读者学号 char isbn[20]; // 图书 ISBN char borrow_date[12]; // 借出日期 YYYY-MM-DD char return_date[12]; // 归还日期，未还为 "0000-00-00" struct BorrowNode *next; } BorrowNode; typedef struct { BorrowNode *head; BorrowNode *tail; // 尾指针，尾插 O(1) int count; } BorrowList; BorrowList* init_borrow_list(void) { BorrowList *list = (BorrowList*)malloc(sizeof(BorrowList)); list->head = NULL; list->tail = NULL; list->count = 0; return list; } int append_borrow(BorrowList *list, const char *sid, const char *isbn, const char *bdate) { BorrowNode *node = (BorrowNode*)malloc(sizeof(BorrowNode)); if (!node) return -1; strncpy(node->student_id, sid, sizeof(node->student_id) - 1); node->student_id[sizeof(node->student_id) - 1] = '\0'; strncpy(node->isbn, isbn, sizeof(node->isbn) - 1); node->isbn[sizeof(node->isbn) - 1] = '\0'; strncpy(node->borrow_date, bdate, sizeof(node->borrow_date) - 1); node->borrow_date[sizeof(node->borrow_date) - 1] = '\0'; strcpy(node->return_date, "0000-00-00"); node->next = NULL; if (list->tail == NULL) { list->head = node; list->tail = node; } else { list->tail->next = node; list->tail = node; } list->count++; return 0; }

逻辑说明：append_borrow不遍历链表，直接通过tail指针在尾部接上新节点，时间复杂度 O(1)。参数sid、isbn、bdate都是外部传入的字符串，函数内部用strncpy拷贝并手动补\0，防止源字符串超长导致越界。return_date初始化为"0000-00-00"表示未归还，后续归还操作再改写这个字段。

2.3 按学号查借阅记录：链表遍历的边界处理

链表查询只能从头遍历，但遍历本身有几个容易翻车的地方：空链表、查到尾节点、学号字段没补\0导致strcmp越界。下面这个函数把三种情况都兜住了。

BorrowNode* find_by_student(BorrowList *list, const char *sid) { if (list == NULL || list->head == NULL) return NULL; BorrowNode *cur = list->head; while (cur != NULL) { if (strncmp(cur->student_id, sid, sizeof(cur->student_id)) == 0) { return cur; } cur = cur->next; } return NULL; }

逻辑说明：先判空链表，再进入循环。比较用strncmp并限定长度，避免student_id未正确终止时读到相邻内存。返回第一个匹配节点，如果要查该读者的全部借阅记录，把return改成打印后继续cur = cur->next即可。参数sid由调用方保证是合法学号字符串。

3. 用索引把图书查询从 O(n) 压到 O(1)：哈希表与 MySQL 索引的配合

3.1 内存哈希索引的构建

图书主表用顺序表存，同时建一张哈希表做 ISBN 到数组下标的映射。哈希函数用经典的 BKDR，冲突用链地址法。这样按 ISBN 查书从 O(n) 降到平均 O(1)。

#define HASH_SIZE 10007 // 取质数，减少冲突 typedef struct HashEntry { char isbn[20]; int index; // 对应图书数组下标 struct HashEntry *next; } HashEntry; typedef struct { HashEntry *buckets[HASH_SIZE]; } HashIndex; unsigned int bkdr_hash(const char *str) { unsigned int seed = 131; unsigned int hash = 0; while (*str) { hash = hash * seed + (*str++); } return hash % HASH_SIZE; } void hash_insert(HashIndex *idx, const char *isbn, int book_index) { unsigned int h = bkdr_hash(isbn); HashEntry *entry = (HashEntry*)malloc(sizeof(HashEntry)); strncpy(entry->isbn, isbn, sizeof(entry->isbn) - 1); entry->isbn[sizeof(entry->isbn) - 1] = '\0'; entry->index = book_index; entry->next = idx->buckets[h]; idx->buckets[h] = entry; } int hash_lookup(HashIndex *idx, const char *isbn) { unsigned int h = bkdr_hash(isbn); HashEntry *cur = idx->buckets[h]; while (cur != NULL) { if (strcmp(cur->isbn, isbn) == 0) return cur->index; cur = cur->next; } return -1; // 未找到 }

逻辑说明：HASH_SIZE取 10007 这个质数，是为了让 BKDR 哈希的分布更均匀，减少冲突链长度。hash_insert用头插法，插入 O(1)。hash_lookup返回图书数组下标，-1 表示未找到。参数book_index是图书在顺序表中的位置，由调用方在插入图书后传入。

3.2 落库时用 MySQL 索引兜底

课程设计通常还要把数据落到 MySQL。内存哈希表解决运行时查询，数据库索引解决持久化和复杂条件查询。图书表的 ISBN 建唯一索引，借阅记录表的学号和 ISBN 建复合索引。

CREATE TABLE book ( id INT PRIMARY KEY AUTO_INCREMENT, isbn VARCHAR(20) NOT NULL, title VARCHAR(128) NOT NULL, author VARCHAR(64), total_copies INT DEFAULT 1, available_copies INT DEFAULT 1, UNIQUE KEY uk_isbn (isbn) ) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4; CREATE TABLE borrow_record ( id INT PRIMARY KEY AUTO_INCREMENT, student_id VARCHAR(16) NOT NULL, isbn VARCHAR(20) NOT NULL, borrow_date DATE NOT NULL, return_date DATE DEFAULT NULL, KEY idx_student_borrow (student_id, borrow_date), KEY idx_isbn (isbn) ) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

逻辑说明：uk_isbn唯一索引保证同一 ISBN 不重复插入，同时让WHERE isbn = ?走索引。idx_student_borrow是复合索引，遵循最左前缀原则，WHERE student_id = ?和WHERE student_id = ? AND borrow_date > ?都能命中。idx_isbn单独建，用于统计某本书的借阅次数。

提示：复合索引的字段顺序按区分度从高到低排。学号区分度远高于借出日期，所以student_id放前面。反过来建索引，WHERE student_id = ?就用不上。

3.3 索引维护的时机与代价

索引不是越多越好。每建一个索引，插入和更新都要多写一棵 B+ 树。借阅记录表插入频繁，索引控制在两个以内。图书表更新少，可以多建。内存哈希索引在图书信息变更时要同步更新，否则会出现“数据库改了、内存还是旧值”的玄学 bug。

我一般把哈希索引的更新封装在图书增删改的统一入口里，任何修改图书的操作都先改数据库，成功后再更新哈希表。如果数据库写失败，哈希表不动，保证两边一致。

4. 借阅与归还的链表操作：插入、删除、遍历的完整实现

4.1 归还操作：在链表中定位并改写节点

归还不需要删除节点，只需要把对应借阅记录的return_date从"0000-00-00"改成实际日期。定位逻辑是按学号和 ISBN 双条件查找。

int return_book(BorrowList *list, const char *sid, const char *isbn, const char *rdate) { if (list == NULL || list->head == NULL) return -1; BorrowNode *cur = list->head; while (cur != NULL) { if (strcmp(cur->student_id, sid) == 0 && strcmp(cur->isbn, isbn) == 0 && strcmp(cur->return_date, "0000-00-00") == 0) { strncpy(cur->return_date, rdate, sizeof(cur->return_date) - 1); cur->return_date[sizeof(cur->return_date) - 1] = '\0'; return 0; } cur = cur->next; } return -1; // 未找到未归还记录 }

逻辑说明：三个条件同时满足才算命中——学号对、ISBN 对、且当前未归还。这样避免同一读者多次借同一本书时改错记录。参数rdate是归还日期字符串，格式YYYY-MM-DD。返回 0 表示成功，-1 表示没有找到可归还的记录。

4.2 删除历史记录：单链表删除的指针操作

课程设计里常要求“清理某读者已归还的全部记录”。单链表删除要维护前驱指针，头节点删除要单独处理。

int purge_returned(BorrowList *list, const char *sid) { if (list == NULL) return -1; BorrowNode *cur = list->head; BorrowNode *prev = NULL; int removed = 0; while (cur != NULL) { int match = (strcmp(cur->student_id, sid) == 0 && strcmp(cur->return_date, "0000-00-00") != 0); if (match) { BorrowNode *victim = cur; if (prev == NULL) { list->head = cur->next; cur = list->head; } else { prev->next = cur->next; cur = cur->next; } if (victim == list->tail) { list->tail = prev; } free(victim); list->count--; removed++; } else { prev = cur; cur = cur->next; } } return removed; }

逻辑说明：prev始终指向cur的前驱。删除头节点时更新head，删除尾节点时更新tail，中间节点改prev->next。free之后不能再访问victim的字段。返回删除条数，方便调用方确认。参数sid是目标读者学号，函数只删该读者已归还的记录，未归还的保留。

4.3 遍历统计：热门图书排行

按借阅次数给图书排序，需要遍历借阅链表并累加每本书的计数。用一个辅助数组存 ISBN 和计数，遍历完再排序。

#define MAX_BOOKS 4096 typedef struct { char isbn[20]; int count; } BookStat; int compare_stat(const void *a, const void *b) { return ((BookStat*)b)->count - ((BookStat*)a)->count; } int top_books(BorrowList *list, BookStat *out, int max_out) { BookStat stats[MAX_BOOKS]; int n = 0; BorrowNode *cur = list->head; while (cur != NULL) { int found = -1; for (int i = 0; i < n; i++) { if (strcmp(stats[i].isbn, cur->isbn) == 0) { found = i; break; } } if (found >= 0) { stats[found].count++; } else if (n < MAX_BOOKS) { strncpy(stats[n].isbn, cur->isbn, sizeof(stats[n].isbn) - 1); stats[n].isbn[sizeof(stats[n].isbn) - 1] = '\0'; stats[n].count = 1; n++; } cur = cur->next; } qsort(stats, n, sizeof(BookStat), compare_stat); int out_n = (n < max_out) ? n : max_out; for (int i = 0; i < out_n; i++) { out[i] = stats[i]; } return out_n; }

逻辑说明：内层线性查找在图书种类多时偏慢，但课程设计规模下可接受。qsort的compare_stat返回b->count - a->count实现降序。max_out控制输出条数，避免调用方缓冲区溢出。参数out由调用方分配，至少能放max_out个BookStat。

5. 课程设计避坑：链表和索引最容易翻车的 5 个地方

5.1 链表遍历时 free 之后继续访问

现象：程序在清理记录后随机崩溃，或者打印出乱码。原因：free(victim)之后没有及时把cur指向下一个节点，或者继续读victim->next。解决：删除节点前先把next存到临时变量，free之后用临时变量推进。上面purge_returned里cur = cur->next在free之前执行，就是这个道理。

5.2 哈希索引和数据库不同步

现象：数据库里图书信息改了，按 ISBN 查还是旧数据。原因：更新只写了 MySQL，忘了更新内存哈希表，或者更新顺序反了。解决：所有写操作走同一个入口函数，先写数据库，事务提交成功后再更新哈希索引。如果数据库写失败，哈希表不动。

5.3 复合索引字段顺序建反

现象：WHERE student_id = ?查询不走索引，全表扫描。原因：复合索引建成了(borrow_date, student_id)，最左前缀匹配不上。解决：用EXPLAIN看key字段，确认命中预期索引。字段顺序按区分度从高到低排，学号在前，日期在后。

5.4 字符串字段没补 \0 导致 strcmp 越界

现象：两个明显不同的学号被判为相等，或者查询结果莫名其妙。原因：strncpy拷贝时源字符串长度等于目标缓冲区大小，没有补\0，后续strcmp读到缓冲区外的内存。解决：每次strncpy后手动把最后一个字节置\0，或者用snprintf替代。

5.5 尾指针在删除尾节点后没更新

现象：继续尾插时新节点接在了已释放的内存上，程序崩溃。原因：删除的恰好是尾节点，tail还指向被free的节点。解决：删除时判断victim == list->tail，是则把tail更新为prev。如果删的是唯一节点，head和tail都要置NULL。

6. 让课设报告加分：用 gprof 量化链表与索引的性能差异

答辩时老师最爱问“你为什么用链表不用数组”。光说理论不够，跑一组数据最有说服力。用gprof对同一批操作分别测链表和顺序表的耗时，把数据写进报告的性能分析章节。

编译时加-pg选项：

gcc -pg -O2 -o libsys main.c borrow_list.c hash_index.c ./libsys gprof ./libsys gmon.out > profile.txt

profile.txt里看flat profile的% time和calls。我一般构造 10 万条借阅记录，分别测“尾插 10 万次”和“按学号查 1 万次”。链表尾插因为带尾指针，和顺序表差距不大；但按学号查，顺序表加二分是 O(log n)，链表是 O(n)，1 万次查询的耗时差距能到两个数量级。把这两组数字做成表格放进报告，比写十行“链表插入快、数组查询快”管用得多。

注意：具体数字随机器和编译选项变化，报告里写清测试环境和编译参数，别直接抄这组数。

还有一个容易被忽略的加分点：在报告里画一张“查询耗时随数据量增长”的曲线。链表是直线上升，哈希索引基本水平，二分查找是对数缓升。三条线放一起，选型理由一目了然。我当年课设就是靠这张图把性能分析章节撑起来的，老师追问时直接指着图讲，比背概念踏实。

希望帮到你。

本文还有配套的精品资源，点击获取