C语言实现顺序表

 用C语言实现了部分顺序表的基本数据操作

#pragma once
#include <stdlib.h>
#include <stdio.h>
typedef int Rank; // 秩
typedef int Status; // 函数结果状态返回值
typedef int ElemType; // 元素类型

#define TRUE 1
#define FALSE 0
#define OK 1 // 成功
#define ERROR 0 // 错误
#define INFEASIBLE -1
#define OVERFLOW -2
#define DEFAULT_CAPACITY 100 // 默认的初始容量
#define DEFAULT_INCREMENT 10 // 默认的初始增量

typedef struct {
	Rank _length; // 规模
	int _capacity; // 容量
	ElemType* _elem; // 数据区
}SqList;// SqList

ElemType GetElem_Sq(SqList L, Rank r) { // 得到L中秩为r的元素
	if(r < 0 || r > L._length) exit(ERROR); // r非法
	return L._elem[r]; // 返回元素
}

Status InitList_Sq(SqList &L) { // 构造一个空的线性表L
	L._elem = (ElemType*)malloc(DEFAULT_CAPACITY * sizeof(ElemType)); // 申请初始化容量空间大小
	if(!L._elem) exit(OVERFLOW); // 存储分配失败
	L._length = 0; // 空表规模为0
	L._capacity = DEFAULT_CAPACITY; // 初始化容量
	return OK; // 初始化成功
}// InitList_Sq

void ListExpand_Sq(SqList &L){ // 空间不足时扩容
	if(L._length < L._capacity) return; // 尚未满员，不必扩容
	ElemType* oldElem = L._elem; // 记录地址空间
	L._elem = (ElemType*)malloc((L._capacity <<= 1) * sizeof(ElemType)); // 容量加倍
	if(!L._elem) exit(OVERFLOW); // 存储分配失败
	for(int i = 0; i < L._length; i++) L._elem[i] = oldElem[i]; // 复制原表内容
	free(oldElem); // 释放原空间
} // ListExpand_Sq

Status ListInsert_Sq(SqList &L, Rank r, ElemType elem) { // 在顺序线性表L中将elem作为秩为r的新元素插入
	if(r < 0 || r > L._length) // r的合法值为 0 <= r <= L._length
		return ERROR; // r值不合法
	if(L._length >= L._capacity) ListExpand_Sq(L); //存储空间已满，重新分配空间
	for(int i = L._length; i > r; i--) L._elem[i] = L._elem[i - 1]; // 自后向前， 后继元素顺次后移一个单元
	L._elem[r] = elem; L._length++; // 插入新元素并更新规模
	return OK; // 插入成功
} // ListInsert_Sq

Status ListInsert_Sq(SqList &L, ElemType elem) { // 在顺序线性表末尾插入新的元素elem
	return ListInsert_Sq(L, L._length, elem); // 使用指定秩插入算法将新元素elem插入到顺序表末尾
} // ListInsert_Sq

int ListDelete_Sq(SqList &L, Rank lo, Rank hi) { // 在顺序线性表L中删除区间[lo, hi)，并返回删除元素个数
	if((lo < 0 || lo >= L._length) && (hi < 0 || hi > L._length) ) // lo和hi的合法值 0 <= lo < L._length，0 <= hi <= L._length
		return 0; // lo或hi值不合法
	while(hi < L._length) L._elem[lo++] = L._elem[hi++]; // [hi, _length)元素顺次前移hi - lo个单元
	L._length = lo; // 更新规模
	return hi - lo;  // 返回删除元素个数
} // ListDelete_Sq

ElemType ListDelete_Sq(SqList &L, Rank r) { // 删除顺序线性表L中秩为r的元素，并返回删除元素
	if(r < 0 || r >= L._length) // r的合法值为 0 <= r < L._length
		exit(ERROR); // r不合法
	ListDelete_Sq(L, r, r + 1); // 调用区间删除算法删除秩为r的元素
	return L._elem[r]; // 返回被删除元素
} // ListDelete_Sq

int ListUniquify_Sq(SqList &L) { // 删除已排序的顺序表中的重复元素，复杂度为O(n)
	Rank i  = 0, j = 0; // 各对相异相邻元素的秩
	while(++j < L._length) // 逐一扫描，直到末元素
		if(L._elem[i] != L._elem[j]) // 跳过相同元素
			L._elem[++i] = L._elem[j]; // 元素不同时直接前移至前者的右侧
	L._length = ++i; // 更新规模
	return j - i; // 返回被删除元素个数
} // ListUniquify_Sq

void ListInversion_Sq(SqList &L) { // 逆置顺序表 
	ElemType *oldElem = L._elem; // 记录原数据存储空间
	L._elem = (ElemType*)malloc(L._capacity * sizeof(ElemType)); // 申请逆置后的新空间
	if(!L._elem) exit(OVERFLOW); // 存储分配失败
	Rank oldRank = L._length; Rank newRank = 0; // 未逆置末元素与逆置首元素秩
	while(--oldRank >= 0) L._elem[newRank++] = oldElem[oldRank]; // 将原顺序表逆次放入新顺序表
} // ListInversion_Sq

void ListPrint_Sq(SqList &L) { // 输出顺序表
	for(int i = 0; i < L._length; i++) i == 0 ? printf("%d", L._elem[i]) : printf(" %d", L._elem[i]); // 顺次输出顺序表元素
	printf("\n"); // 换行
} // ListPrint_Sq

void ReverseMergeList_Sq(SqList La, SqList Lb, SqList &Lc) { // 逆序递减合并顺序表La，Lb至Lc
	Rank a = La._length - 1; Rank b = Lb._length - 1; // 顺序表La，Lb的末元素秩
	while(0 <= a || 0 <= b) // 秩a，b都小于0时退出循环
		// b小于0则将La中秩为a的元素插入Lc，a大于等于0且Lb中秩为b的元素小于La中秩为a的元素则将La中秩为a的元素插入Lc
		if((b < 0) || (0 <= a && (Lb._elem[b] < La._elem[a]))) ListInsert_Sq(Lc, La._elem[a--]);
		//其情况则将Lb中秩为b的元素插入Lc
		else ListInsert_Sq(Lc, Lb._elem[b--]);
} // ReverseMergeList_Sq