一、问题引入

图书信息管理系统:
出版社有一些图书数据保存在一个文本文件book.txt 中，为简单起见，在此假设每种图书只包括三部分信息：ISBN (书号）、书名和价格，文件中的部分数据如图2.1 所示。现要求实现一个图书信息管理系统，包括以下6个具体功能。

(1) 查找：根据指定的ISBN 或书名查找相应图书的有关信息， 并返回该图书在表中的位置序号。
(2) 插入：插入一种新的图书信息。
(3) 删除：删除一种图书信息。
(4) 修改：根据指定的ISBN, 修改该图书的价格。
(5) 排序：将图书按照价格由低到高进行排序。
(6) 计数：统计图书表中的图书数量

具体实现：

图书数据由用户输入，功能(5)暂不实现

二、解决过程

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

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

? 运行结果

三、反思总结

顺序表可以随机存取表中任一元素，其存储位置可用一个简单、直观的公式来表示。然而，从另一方面来看，这个特点也造成了这种存储结构的缺点：在做插入或删除操作时，需移动大量元素。另外由于数组有长度相对固定的静态特性， 当表中数据元素个数较多且变化较大时，操作过程相对复杂，必然导致存储空间的浪费。所有这些问题，都可以通过线性表的另一种表示方法-链式存储结构来解决

四、参考引用

数据结构第二版：C语言版【严蔚敏】 第二章 线性表