一、問題引入
圖書資訊管理系統:
出版社有一些圖書資料保存在一個文本檔案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 <= sq_list_pt->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 < num_of_book; i++)
{
list_insert(&sq_list_t, book_arr[i]);
}
// 遍歷列印所有書籍
printf("列印圖書館所有書籍清單：\n");
list_traverse(sq_list_t);
printf("\n");
// 洗掉
char isbn[20] = {0};
printf("請輸入洗掉書籍的ISBN碼：");
scanf("%20s", isbn);
list_delete(&sq_list_t, isbn);
printf("列印圖書館所有書籍清單：\n");
list_traverse(sq_list_t);
printf("\n");
// 查找
ElemType *p_elem = NULL;
char book_info[300] = {0};
int idx = 0;
printf("請輸入查找資料的ISBN碼：");
scanf("%20s", isbn);
p_elem = element_locate(sq_list_t, isbn, &idx);
if (NULL != p_elem)
{
sprintf(book_info, "{\"name\":\"%s\",\"isbn\":\"%s\",\"price\":%.2f}",
p_elem->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
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/549008.html
標籤：其他