一、问题引入
图书信息管理系统:
出版社有一些图书数据保存在一个文本文件book.txt 中,为简单起见,在此假设每种图书只包括三部分信息:ISBN (书号)、书名和价格,文件中的部分数据如图2.1 所示。现要求实现一个图书信息管理系统,包括以下6个具体功能。
(1) 查找:根据指定的ISBN 或书名查找相应图书的有关信息, 并返回该图书在表中的位置序号。
(2) 插入:插入一种新的图书信息。
(3) 删除:删除一种图书信息。
(4) 修改:根据指定的ISBN, 修改该图书的价格。
(5) 排序:将图书按照价格由低到高进行排序。
(6) 计数:统计图书表中的图书数量
具体实现:
图书数据由用户输入,而不直接从文本文件book.txt读取(后续考虑以这种方式载入数据,新增数据通过用户输入)。
二、解决过程2-1 数据格式定义
- 顺序表的定义
#define OK 0#define ERROR -1#define OVERFLOW -2#define MAXSIZE 10000 //顺序表的最大长度typedef struct{char name[50]; // 书名double price; // 单价char isbn[20]; // ISBN码}Book_T;typedef Book_T ElemType;typedef struct{ElemType *base; // 存储空间的基地址int length; // 当前长度}SqList_T; // 顺序表的结构类型为 Sqlist_T
2-2 功能实现
- 顺序表的初始化
int list_init(SqList_T *sq_list_pt){sq_list_pt->base = (ElemType *)malloc(MAXSIZE * sizeof(ElemType));if (sq_list_pt == NULL)exit(OVERFLOW);memset(sq_list_pt->base, 0, MAXSIZE * sizeof(ElemType));sq_list_pt->length = 0;return OK;}
- 顺序表的销毁
void list_destory(SqList_T *sq_list_pt){if (sq_list_pt->base != NULL)free(sq_list_pt->base);sq_list_pt->base = NULL;sq_list_pt->length = 0;}
- 顺序表的查找
ElemType * element_locate(SqList_T sq_list_t, const char *isbn, int *idx){ElemType *p_elem = NULL;*idx = -1;for (int i = 0; i < sq_list_t.length; i++){if (0 == strcmp(sq_list_t.base[i].isbn, isbn)){p_elem = &sq_list_t.base[i];*idx = i+1;break;}}return p_elem;}
- 顺序表的插入
int list_insert(SqList_T *sq_list_pt, ElemType elem){// 判断顺序表是否到达最大长度if (sq_list_pt->length == MAXSIZE)return ERROR;int idx = sq_list_pt->length;sq_list_pt->base[idx] = elem;(sq_list_pt->length)++;return OK;}
- 顺序表的删除
int list_delete(SqList_T *sq_list_pt, const char *isbn){// 判断顺序表是否为空if (sq_list_pt->length == 0)return ERROR;int idx = 0; // idx 从1开始if (element_locate(*sq_list_pt, isbn, &idx) != NULL){for (int i = idx; i length; i++){sq_list_pt->base[i-1] = sq_list_pt->base[i];}}(sq_list_pt->length)--;return OK;}
- 顺序表的遍历
int list_traverse(SqList_T sq_list_t){printf("ISBN " "书名 " "单价 \n");if (sq_list_t.length == 0){printf("图书馆书籍为空\n");return ERROR;}for (int i = 0; i < sq_list_t.length; i++){printf("%-30s%-30s%-30.2f\n", sq_list_t.base[i].isbn, sq_list_t.base[i].name, sq_list_t.base[i].price);}return OK;}
- 顺序表的修改
int list_update(SqList_T *sq_list_pt, const char *isbn, double price){// 判断顺序表是否为空if (sq_list_pt->length == 0)return ERROR;ElemType *p_elem = NULL;int idx = 0; // idx 从1开始p_elem = element_locate(*sq_list_pt, isbn, &idx);if (p_elem == NULL)return ERROR;p_elem->price = price;return OK;}
- 顺序表的排序
int book_price_compare(const void *e1, const *e2){ElemType *elem1 = (ElemType *)e1;ElemType *elem2 = (ElemType *)e2;return (int)(elem1->price - elem2->price);}// 顺序表的排序(根据图书的价格,从低到高排序)int list_sort(SqList_T *sq_list_pt){qsort(sq_list_pt->base, sq_list_pt->length, sizeof(sq_list_pt->base[0]), book_price_compare);return OK;}
2-3 main()
int main(void){int num_of_book = 0;Book_T book_arr[MAXSIZE] = {0};SqList_T sq_list_t = {0};list_init(&sq_list_t);printf("请输入书籍数量:");scanf("%d", &num_of_book);printf("\n");for (int i = 0; i < num_of_book; i++){printf("请输入第%d本的信息\n", i+1);printf("书籍名称:");scanf("%50s", book_arr[i].name);printf("书籍单价:");scanf("%lf", &book_arr[i].price);printf("书籍ISBN:");scanf("%20s", book_arr[i].isbn);printf("\n");}// 插入for (int i = 0; i name, p_elem->isbn, p_elem->price);printf("%s\n", book_info);}printf("\n");// 修改double price = 0;printf("请输入书籍的ISBN码:");scanf("%20s", isbn);printf("请输入书籍现在的价格:");scanf("%lf", &price);if (ERROR == list_update(&sq_list_t, isbn, price)){printf("价格修改失败\n");}printf("打印图书馆所有书籍清单:\n");list_traverse(sq_list_t);printf("\n");// 释放内存空间list_destory(&sq_list_t);return 0;}
? 运行结果
2-4 排序功能(新增)
int main(void){int num_of_book = 0;Book_T book_arr[MAXSIZE] = {0};SqList_T sq_list_t = {0};list_init(&sq_list_t);printf("请输入书籍数量:");scanf("%d", &num_of_book);printf("\n");for (int i = 0; i < num_of_book; i++){printf("请输入第%d本的信息\n", i+1);printf("书籍名称:");scanf("%50s", book_arr[i].name);printf("书籍单价:");scanf("%lf", &book_arr[i].price);printf("书籍ISBN:");scanf("%20s", book_arr[i].isbn);printf("\n");}/* 插入 */for (int i = 0; i < num_of_book; i++){list_insert(&sq_list_t, book_arr[i]);}/* 遍历打印所有书籍 */printf("打印图书馆所有书籍清单:\n");list_traverse(sq_list_t);printf("\n");/* 排序 */list_sort(&sq_list_t);printf("打印图书馆所有书籍清单:\n");list_traverse(sq_list_t);printf("\n");/* 释放内存空间 */list_destory(&sq_list_t);return 0;}
? 运行结果
三、反思总结
顺序表可以随机存取表中任一元素,其存储位置可用一个简单、直观的公式来表示。然而,从另一方面来看,这个特点也造成了这种存储结构的缺点:在做插入或删除操作时,需移动大量元素。另外由于数组有长度相对固定的静态特性, 当表中数据元素个数较多且变化较大时,操作过程相对复杂,必然导致存储空间的浪费。所有这些问题,都可以通过线性表的另一种表示方法-链式存储结构来解决
排序算法qsort()的原型:
void qsort (void* base, size_t num, size_t size, int (*compar)(const void*,const void*));
其中涉及到函数指针的使用。
四、参考引用
数据结构第二版:C语言版【严蔚敏】 第二章 线性表
qsort