第 2 章 线性表（线性表的动态分配顺序存储结构实现）

1. 背景说明

线性表(linear Iist)是最常用且最简单的一种数据结构。简言之，一个线性表是 n 个数据元素的有限序列。

至于每个数据元素的具体含义，在不同的情况下各不相同，它可以是一个数或一个符号，也可以是一页书，甚至其他更复杂的信息。

2. 示例代码

1) status.h

/* DataStructure 预定义常量和类型头文件 */

#ifndef STATUS_H
#define STATUS_H

/* 函数结果状态码 */
#define TRUE 					1			/* 返回值为真 */
#define FALSE 					0			/* 返回值为假 */
#define RET_OK 					0			/* 返回值正确 */
#define INFEASIABLE    		   	2			/* 返回值未知 */
#define ERR_MEMORY     		   	3			/* 访问内存错 */
#define ERR_NULL_PTR   			4			/* 空指针错误 */
#define ERR_MEMORY_ALLOCATE		5			/* 内存分配错 */
#define ERR_NULL_STACK			6			/* 栈元素为空 */
#define ERR_PARA				7			/* 函数参数错 */
#define ERR_OPEN_FILE			8			/* 打开文件错 */
#define ERR_NULL_QUEUE			9			/* 队列为空错 */
#define ERR_FULL_QUEUE			10			/* 队列为满错 */
typedef int Status;							/* Status 是函数的类型,其值是函数结果状态代码，如 RET_OK 等 */
typedef int Bollean;						/* Boolean 是布尔类型,其值是 TRUE 或 FALSE */

#endif // !STATUS_H

2) dynSqList.h

/* 线性表的动态分配顺序存储结构头文件 */

#ifndef DYNSQLIST_H
#define DYNSQLIST_H

#include "status.h"

#define LIST_INIT_SIZE 10 			/* 线性表存储空间的初始分配量 */
#define LISTINCREMENT 2 			/* 线性表存储空间的分配增量 */

typedef int ElemType;

typedef struct {
	ElemType *elem;					/* 存储空间基址 */
	int length;						/* 当前长度 */
	int listSize;					/* 当前分配的存储容量(以 sizeof(ElemType) 为单位) */
} SqList;

/* 算法 2.3, 操作结果：构造一个空的顺序线性表 */
Status InitList(SqList *L);

/* 初始条件：顺序线性表 L 已存在。操作结果：销毁顺序线性表 L */
Status DestroyList(SqList *L);

/* 初始条件：顺序线性表 L 已存在。操作结果：将 L 重置为空表 */
Status ClearList(SqList *L);

/* 初始条件：顺序线性表 L 已存在。操作结果：若 L 为空表，则返回 TRUE，否则返回 FALSE */
Bollean ListEmpty(SqList L);

/* 初始条件：顺序线性表 L 已存在。操作结果：返回 L 中数据元素个数 */
int ListLength(SqList L);

/* 初始条件：顺序线性表 L 已存在，1 ≤ i ≤ ListLength(L)
   操作结果：用 e 返回 L 中第 i 个数据元素的值 */
Status GetElem(SqList L, int i, ElemType *e);

/* 算法 2.6, 初始条件：顺序线性表 L 已存在，compare() 是数据元素判定函数(满足为 1,否则为 0)
   操作结果：返回 L 中第 1 个与 e 满足关系 compare() 的数据元素的位序
   若这样的数据元素不存在，则返回值为 0 */
int LocateElem(SqList L, ElemType e, Status(*compare)(ElemType, ElemType));

/* 初始条件：顺序线性表 L 已存在
   操作结果：若 cur_e 是 L 的数据元素，且不是第一个，则用 pre_e 返回它的前驱
   否则操作失败，pre_e 无定义 */
Status PriorElem(SqList L, ElemType cur_e, ElemType *pre_e);

/* 初始条件：顺序线性表 L 已存在
   操作结果：若 cur_e 是 L 的数据元素，且不是最后一个，则用 next_e 返回它的后继
   否则操作失败，next_e 无定义 */
Status NextElem(SqList L, ElemType cur_e, ElemType *next_e);

/* 算法 2.4，初始条件：顺序线性表 L 已存在，1 ≤ i ≤ ListLength(L) + 1
   操作结果：在 L 中第 i 个位置之前插入新的数据元素 e，L 的长度加 1 */
Status ListInsert(SqList *L, int i, ElemType e);

/* 算法 2.5，初始条件：顺序线性表 L 已存在，1 ≤ i ≤ ListLength(L)
   操作结果：删除 L 的第 i 个数据元素，并用 e 返回其值，L 的长度减 1 */
Status ListDelete(SqList *L, int i, ElemType *e);

/* 初始条件：顺序线性表 L 已存在
   操作结果：依次对 L 的每个数据元素调用函数 vi()。一旦 vi() 失败，则操作失败
   vi() 的形参加 '&'，表明可通过调用 vi() 改变元素的值 */
Status ListTraverse(SqList L, void(*vi)(ElemType*));

#endif // !DYNSQLIST_H

3) dynSqList.c

#include "dynSqList.h"
#include <stdlib.h>
#include <stdio.h>

/* 算法 2.3, 操作结果：构造一个空的顺序线性表 */
Status InitList(SqList *L)
{
	(*L).elem = (ElemType*)malloc(sizeof(ElemType) * LIST_INIT_SIZE);
	if (!(*L).elem) {
		printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ERR_MEMORY_ALLOCATE);
		return ERR_MEMORY_ALLOCATE;
	}

	(*L).length = 0;
	(*L).listSize = LIST_INIT_SIZE;

	return RET_OK;
}

/* 初始条件：顺序线性表 L 已存在。操作结果：销毁顺序线性表 L */
Status DestroyList(SqList *L)
{
	free((*L).elem);
	(*L).length = 0;
	(*L).listSize = 0;

	return RET_OK;
}

/* 初始条件：顺序线性表 L 已存在。操作结果：将 L 重置为空表 */
Status ClearList(SqList *L)
{
	(*L).length = 0;

	return RET_OK;
}

/* 初始条件：顺序线性表 L 已存在。操作结果：若 L 为空表，则返回 TRUE，否则返回 FALSE */
Bollean ListEmpty(SqList L)
{
	return (L.length == 0) ? TRUE : FALSE;
}

/* 初始条件：顺序线性表 L 已存在。操作结果：返回 L 中数据元素个数 */
int ListLength(SqList L)
{
	return L.length;
}

/* 初始条件：顺序线性表 L 已存在，1 ≤ i ≤ ListLength(L)
   操作结果：用 e 返回 L 中第 i 个数据元素的值 */
Status GetElem(SqList L, int i, ElemType *e)
{
	if (i < 1 || i > L.length) {
		printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ERR_PARA);
		return ERR_PARA;
	}

	*e = *(L.elem + i - 1);

	return RET_OK;
}

/* 算法 2.6, 初始条件：顺序线性表 L 已存在，compare() 是数据元素判定函数(满足为 1,否则为 0)
   操作结果：返回 L 中第 1 个与 e 满足关系 compare() 的数据元素的位序
   若这样的数据元素不存在，则返回值为 0 */
int LocateElem(SqList L, ElemType e, Status(*compare)(ElemType, ElemType))
{
	ElemType *p = L.elem;
	int i = 1;
	while (i <= L.length && !compare(*p++, e)) {
		++i;
	}

	return (i <= L.length) ? i : 0;
}

/* 初始条件：顺序线性表 L 已存在
   操作结果：若 cur_e 是 L 的数据元素，且不是第一个，则用 pre_e 返回它的前驱
   否则操作失败，pre_e 无定义 */
Status PriorElem(SqList L, ElemType cur_e, ElemType *pre_e)
{
	ElemType *p = L.elem + 1;
	int i = 2;
	while (i++ <= L.length && *p++ != cur_e);
	if (i > L.length) {
		return INFEASIABLE;
	}
	
	*pre_e = *(--p);

	return RET_OK;
}

/* 初始条件：顺序线性表 L 已存在
   操作结果：若 cur_e 是 L 的数据元素，且不是最后一个，则用 next_e 返回它的后继
   否则操作失败，next_e 无定义 */
Status NextElem(SqList L, ElemType cur_e, ElemType *next_e)
{
	ElemType *p = L.elem;
	int i = 1;
	while (i < L.length && *p != cur_e) {
		++i;
		++p;
	}

	if (i == L.length) {
		return INFEASIABLE;
	}

	*next_e = *(++p);

	return RET_OK;
}

/* 算法 2.4，初始条件：顺序线性表 L 已存在，1 ≤ i ≤ ListLength(L) + 1
   操作结果：在 L 中第 i 个位置之前插入新的数据元素 e，L 的长度加 1 */
Status ListInsert(SqList *L, int i, ElemType e)
{
	if (i < 1 || i > (*L).length + 1) {
		printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ERR_PARA);
		return ERR_PARA;
	}

	if ((*L).length == (*L).listSize) {
		ElemType* newBase = (ElemType*)realloc((*L).elem, (unsigned long long)((*L).listSize + LISTINCREMENT) * sizeof(ElemType));
		if (!newBase) {
			printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ERR_MEMORY_ALLOCATE);
			return ERR_MEMORY_ALLOCATE;
		}

		(*L).elem = newBase;
		(*L).listSize += LISTINCREMENT;
	}

	ElemType *q = (*L).elem + i - 1;
	for (ElemType* p = (*L).elem + (*L).length - 1; p >= q; --p) {
		*(p + 1) = *p;
	}

	*q = e;
	++(*L).length;

	return RET_OK;
}

/* 算法 2.5，初始条件：顺序线性表 L 已存在，1 ≤ i ≤ ListLength(L)
   操作结果：删除 L 的第 i 个数据元素，并用 e 返回其值，L 的长度减 1 */
Status ListDelete(SqList *L, int i, ElemType *e)
{
	if (i < 1 || (*L).length) {
		printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ERR_PARA);
		return ERR_PARA;
	}

	ElemType *p = (*L).elem + i - 1;
	*e = *p;
	ElemType* q = (*L).elem + (*L).length - 1;
	for (++p; p <= q; ++p) {
		*(p - 1) = *p;
	}

	--(*L).length;

	return RET_OK;
}

/* 初始条件：顺序线性表 L 已存在
   操作结果：依次对 L 的每个数据元素调用函数 vi()。一旦 vi() 失败，则操作失败
   vi() 的形参加 '&'，表明可通过调用 vi() 改变元素的值 */
Status ListTraverse(SqList L, void(*vi)(ElemType*))
{
	ElemType *p = L.elem;
	for (int i = 1; i <= L.length; ++i) {
		vi(p++);
	}

	return RET_OK;
}

4) algorithm.h

/* 算法实现头文件 */

#ifndef ALGORITHM_H
#define ALGORITHM_H

#include "auxiliary.h"

/* 算法 2.1，将所有在线性表 Lb 中但不在 La 中的数据元素插入到 La 中 */
void Union(SqList *La, SqList Lb);

/* 算法 2.2，已知线性表 La 和 Lb 中的数据元素按值非递减排列
   归并 La 和 Lb 得到新的线性表 Lc, Lc 的数据元素也按值非递减排列 */
void MergeList(SqList La, SqList Lb, SqList *Lc);

/* 算法 2.7，已知顺序线性表 La 和 Lb 的元素按值非递减排列
   归并 La 和 Lb 得到新的顺序线性表 Lc, Lc 的元素也按值非递减排列 */
void MergeList2(SqList La, SqList Lb, SqList *Lc);

/* 另一种合并线性表的方法（根据算法 2.7 下的要求修改算法 2.7） */
void MergeList3(SqList La, SqList Lb, SqList *Lc);

#endif // !ALGORITHM_H

5) algorithm.c

/* 算法实现源文件 */

#include "algorithm.h"
#include <stdio.h>
#include <stdlib.h>

/* 算法 2.1，将所有在线性表 Lb 中但不在 La 中的数据元素插入到 La 中 */
void Union(SqList *La, SqList Lb)
{
	int laLength = ListLength(*La);
	int lbLength = ListLength(Lb);
	ElemType e;
	for (int i = 1; i <= lbLength; ++i) {
		if (GetElem(Lb, i, &e) == RET_OK) {
			if (!LocateElem(*La, e, Equal)) {
				ListInsert(La, ++laLength, e);
			}
		}
	}
}

/* 算法 2.2，已知线性表 La 和 Lb 中的数据元素按值非递减排列
   归并 La 和 Lb 得到新的线性表 Lc, Lc 的数据元素也按值非递减排列 */
void MergeList(SqList La, SqList Lb, SqList *Lc)
{
	int ret = InitList(Lc);
	if (ret != RET_OK) {
		printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ret);
		return;
	}

	int laLength = ListLength(La);
	int lbLength = ListLength(Lb);
	InitList(Lc);
	int i = 1, j = 1, k = 0;
	ElemType ai, bj;
	while (i <= laLength && j <= lbLength) {
		(void)GetElem(La, i, &ai);
		(void)GetElem(Lb, j, &bj);
		if (ai <= bj) {
			(void)ListInsert(Lc, ++k, ai);
			++i;
		}
		else {
			(void)ListInsert(Lc, ++k, bj);
			++j;
		}
	}

	while (i <= laLength) {
		(void)GetElem(La, i++, &ai);
		(void)ListInsert(Lc, ++k, ai);
	}

	while (j <= lbLength) {
		(void)GetElem(Lb, j++, &bj);
		(void)ListInsert(Lc, ++k, bj);
	}
}

/* 算法 2.7，已知顺序线性表 La 和 Lb 的元素按值非递减排列
   归并 La 和 Lb 得到新的顺序线性表 Lc, Lc 的元素也按值非递减排列 */
void MergeList2(SqList La, SqList Lb, SqList *Lc)
{
	(*Lc).listSize = (*Lc).length = La.length + Lb.length;
	ElemType *pc = (*Lc).elem = (ElemType*)malloc((*Lc).listSize * sizeof(ElemType));
	if (!(*Lc).elem) {
		printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ERR_MEMORY_ALLOCATE);
		return;
	}

	ElemType *pa = La.elem;
	ElemType *pb = Lb.elem;
	ElemType *pa_last = La.elem + La.length - 1;
	ElemType *pb_last = Lb.elem + Lb.length - 1;
	while (pa <= pa_last && pb <= pb_last) {
		if (*pa <= *pb) {
			*pc++ = *pa++;
		}
		else {
			*pc++ = *pb++;
		}
	}

	while (pa <= pa_last) {
		*pc++ = *pa++;
	}

	while (pb <= pb_last) {
		*pc++ = *pb++;
	}
}

/* 另一种合并线性表的方法（根据算法 2.7 下的要求修改算法 2.7） */
void MergeList3(SqList La, SqList Lb, SqList *Lc)
{
	(*Lc).listSize = La.length + Lb.length;
	ElemType *pc = (*Lc).elem = (ElemType*)malloc((*Lc).listSize * sizeof(ElemType));
	if (!(*Lc).elem) {
		printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ERR_MEMORY_ALLOCATE);
		return;
	}

	ElemType *pa = La.elem;
	ElemType *pb = Lb.elem;
	ElemType *pa_last = La.elem + La.length - 1;
	ElemType *pb_last = Lb.elem + Lb.length - 1;
	while (pa <= pa_last && pb <= pb_last) {
		switch (Comp(*pa, *pb)) {
			case  0: pb++;
			case -1: *pc++ = *pa++;
					 break;
			case  1: *pc++ = *pb++;
		}
	}

	while (pa <= pa_last) {
		*pc++ = *pa++;
	}

	while (pb <= pb_last) {
		*pc++ = *pb++;
	}

	(*Lc).length = pc - (*Lc).elem;
}

6) auxiliary.h

/* 辅助函数头文件 */

#ifndef AUXILIARY_H
#define AUXILIARY_H

#include "status.h"
#include "dynSqList.h"

/* 判断两个元素是否相等 */
Status Equal(ElemType e1, ElemType e2);

/* 打印元素 */
void Print(ElemType *e);

/* 比较元素大小 */
int Comp(ElemType e1, ElemType e2);

/* 判断元素之间是否存在平方关系 */
Status compSquare(ElemType e1, ElemType e2);

/* 使元素值加倍 */
void doubleElem(ElemType *e);

#endif // !AUXILIARY_H

7) auxiliary.c

/* 辅助函数实现源文件 */

#include "auxiliary.h"
#include <stdio.h>

/* 判断两个元素是否相等 */
Status Equal(ElemType e1, ElemType e2)
{
	return (e1 == e2) ? TRUE : FALSE;
}

/* 打印元素 */
void Print(ElemType *e)
{
	printf("%d ", *e);
}

/* 比较元素大小 */
int Comp(ElemType e1, ElemType e2)
{
	return (e1 == e2) ? 0 : ((e1 < e2) ? -1 : 1);
}

/* 判断元素之间是否存在平方关系 */
Status compSquare(ElemType e1, ElemType e2)
{
	return (e1 == e2 * e2) ? TRUE : FALSE;
}

/* 使元素值加倍 */
void doubleElem(ElemType *e)
{
	*e *= 2;
}

8) main.c

/* 入口程序源文件 */

#include "algorithm.h"
#include <stdio.h>

int main(void)
{
	/* 算法 2.1 测试 */
	SqList La;
	int ret = InitList(&La);
	if (ret != RET_OK) {
		printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ret);
		return ret;
	}

	for (int i = 0; i < 5; ++i) {
		ret = ListInsert(&La, i + 1, i + 1);
		if (ret != RET_OK) {
			printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ret);
			return ret;
		}
	}

	printf("La: ");
	ret = ListTraverse(La, Print);
	if (ret != RET_OK) {
		printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ret);
		return ret;
	}

	printf("\n");

	SqList Lb;
	ret = InitList(&Lb);
	if (ret != RET_OK) {
		printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ret);
		return ret;
	}

	for (int i = 1; i <= 5; ++i) {
		ret = ListInsert(&Lb, i, 2 * i);
		if (ret != RET_OK) {
			printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ret);
			return ret;
		}
	}

	printf("Lb: ");
	ret = ListTraverse(Lb, Print);
	if (ret != RET_OK) {
		printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ret);
		return ret;
	}

	printf("\n");

	Union(&La, Lb);										/* 或 MergeList3(La, Lb, &Ld) */
	printf("La: ");
	ret = ListTraverse(La, Print);
	if (ret != RET_OK) {
		printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ret);
		return ret;
	}

	printf("\n");

	/* 算法 2.2 、2.3 测试 */
	SqList Lc;
	MergeList(La, Lb, &Lc);								/* 或 MergeList2(La, Lb, &Lc) */
	printf("Lc: ");
	ret = ListTraverse(Lc, Print);
	if (ret != RET_OK) {
		printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ret);
		return ret;
	}

	printf("\n");

	/* 基本操作测试 */
	
	/* 求第一个满足条件是 2 的平方的数的位置 */
	int index = LocateElem(Lc, 2, compSquare);
	printf("index = %d\n", index);

	/* 依次对元素加倍并遍历元素 */
	ret = ListTraverse(Lc, doubleElem);
	if (ret != RET_OK) {
		printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ret);
		return ret;
	}

	printf("Lc: ");
	ret = ListTraverse(Lc, Print);
	if (ret != RET_OK) {
		printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ret);
		return ret;
	}

	printf("\n");
	
	/* 销毁线性表 */
	ret = DestroyList(&La);
	if (ret != RET_OK) {
		printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ret);
		return ret;
	}

	ret = DestroyList(&Lb);
	if (ret != RET_OK) {
		printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ret);
		return ret;
	}

	ret = DestroyList(&Lc);
	if (ret != RET_OK) {
		printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ret);
	}

	return ret;
}

3. 输出示例