C++ 顺序线性表的功能

顺序线性表的功能

//头文件 
#pragma once
 
#define LIST_INIT_SIZE   50
#define LIST_INCREMENT   20
#define OK 1
#define ERROR 0
 
typedef int Status;
 
typedef char ElemType;
 
typedef struct list_ {
	ElemType* elem;
	int length;
	int listize;
}SqList;
 
// 1 初始化 函数
Status InitList_Sq(SqList& L);
 
//2 想第i个位置插入数据
Status ListInsert_Sq(SqList& L, int i, ElemType e);
 
 
//3 显示所有元素
void PrintAll(SqList L, void print(ElemType));
 
//4 获取第i个元素的值
Status GetElem(SqList L, int i, ElemType& e);
 
//5 打印一个元素
void PrintOne(ElemType e);
 
//删除 第i个位置的元素
Status ListDelete(SqList& L, int i, ElemType& e);
 
// 用完释放
void DestroyList(SqList& L);
 
//获取e所在下标
 
size_t LocateElem(SqList L,ElemType e);

#include 
#include 
#include "mylist.h"
 
 
Status InitList_Sq(SqList& L) {
	L.elem = (ElemType*)malloc(sizeof(ElemType) * LIST_INIT_SIZE);
 
	if (!L.elem)
		return ERROR;
 
	L.length = 0;
	L.listize = LIST_INIT_SIZE;
	return OK;
}
 
Status ListInsert_Sq(SqList& L, int i, ElemType e) {
	// i必须大于0 ，小于等于 L.length + 1
	if (i<1 || i> L.length + 1)
		return ERROR;
 
	// 位置合理，空间不够
	if (L.length >= L.listize) {//扩空间
		ElemType* newbase = (ElemType*)realloc(L.elem, sizeof(ElemType) * (L.listize + LIST_INCREMENT));
		if (!newbase)
			exit(-1);
		L.elem = newbase;
		L.listize += LIST_INCREMENT;
	}
 
	ElemType* p;
	p = L.elem + (i - 1);
	p = &(L.elem[i - 1]);
	for (ElemType* q = L.elem + (L.length - 1); q >= p; q--)
		*(q + 1) = *q;
 
	*p = e;
	L.length += 1;
 
	return OK;
}
void PrintAll(SqList L, void print(ElemType)) {
	for (size_t i = 0; i < L.length; i++) {
		print(L.elem[i]);
	}
	printf("\n");
}
Status GetElem(SqList L, int i, ElemType& e) {
	// i必须大于0 ，小于等于 L.length 
	if (i<1 || i> L.length)
		return ERROR;
	e = L.elem[i - 1]; //e = *(L.elem + i - 1);	
	return OK;
}
 
void PrintOne(ElemType e) {
	printf("%d ", e);
}
 
Status ListDelete(SqList& L, int i, ElemType& e) {
	// i必须大于0 ，小于等于 L.length 
	if (i<1 || i> L.length)
		return ERROR;
 
	e = L.elem[i - 1]; //e = *(L.elem + i - 1);	
	for (ElemType* p = L.elem + i - 1; p < L.elem + L.length; p++)
		*p = *(p + 1);
	L.length--;
 
	return OK;
}
 
void DestroyList(SqList& L) {
	free(L.elem);
	L.length = 0;
	L.listize = 0;
}
 
size_t LocateElem(SqList L, ElemType e){	
	for (size_t i = 0; i < L.length; i++) {
		if (L.elem[i] == e) {
			return i + 1;
		}
	}
	return 0;
}

#include 
#include 
#include "mylist.h"
 
// a = a U b
void unionSet(SqList& a, SqList b);
 
void unionSet(SqList& a, SqList b) {
	//遍历b
	for (size_t i = 1; i <= b.length; i++) {//i代表位置，并非下标（从1开始），length不代表下标
		ElemType e;
		GetElem(b, i,e);
		//询问 e 是否在 a集合
		if (!LocateElem(a, e)) {
			ListInsert_Sq(a, a.length+1, e);
		}
	}
}
 
 
 
int main() {//2024-5-5
	SqList a, b;
	InitList_Sq(a);
	InitList_Sq(b);
	ListInsert_Sq(a, 1, 1);
	ListInsert_Sq(a, 2, 2);
	ListInsert_Sq(a, 3, 3);
	ListInsert_Sq(a, 4, 4);
	ListInsert_Sq(a, 5, 5);
 
	ListInsert_Sq(b, 1, 1);
	ListInsert_Sq(b, 2, 3);
	ListInsert_Sq(b, 3, 9);
	ListInsert_Sq(b, 4, 10);
 
	puts("A原来:");
	PrintAll(a,PrintOne);
 
	puts("B原来:");
	PrintAll(b, PrintOne);
 
	unionSet(a,b);
 
	puts("A现在:");
	PrintAll(a, PrintOne);
 
 
	return 0;
}
 
 
int main1() { //2024-5-4
	SqList L;
	if (!InitList_Sq(L)) {
		printf("线性表建立失败，程序退出。");
		exit(-1);
	}
 
	ListInsert_Sq(L,1,100);
	ListInsert_Sq(L, 2, 101);
	ListInsert_Sq(L, 3, 102);
	ListInsert_Sq(L, 4, 103);
	ListInsert_Sq(L, 5, 104);
	ListInsert_Sq(L, 6, 105);
	ListInsert_Sq(L, 7, 106);
	PrintAll(L,PrintOne);
 
	char e;
	GetElem(L, 2,e);
	PrintOne(e);
	printf("\n");
 
	ListDelete(L,2,e);
	puts("现在的列表：");
	PrintAll(L,PrintOne);
 
	printf("刚才删除的元素是:\n");
	PrintOne(e);
	printf("\n");
 
 
	return 0;
}