408-数据结构

数据结构在学什么？
1.用代码把问题信息化
2.用计算机处理信息

ch1

数据：数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据是计算机程序加工的原料。

ch2

//假设线性表的元素类型为ElemType，则静态分配的顺序表存储结构描述为
#define MaxSize 50				//定义线性表的最大长度
typedef struct {
	ElemType data[MaxSize];		//顺序表的元素
	int length;					//顺序表的当前长度
}SqList;						//顺序表的类型定义

//动态分配的顺序表存储结构描述为
#define InitSize 100			//表长度的初始定义
typedef struct {
	ElemType* data;				//指示动态分配数组的指针
	int MaxSize, length;		//顺序表的最大容量和当前个数
}SeqList;						//动态分配数组顺序表的类型定义
//C的初始动态分配语句为
L.data = (ElemType*)malloc(sizeof(ElemType) * InitSize);
//C++的初始动态分配语句为
L.data = new ElemType[InitSize];

#define MaxSize 50
//静态分配的顺序表，定义一个数组，它包括数据类型和数据长度
typedef struct {
	int data[MaxSize];
	int length;				//表示数据表的当前长度
}SqList;

//基本操作——初始化一个顺序表
void InitList(SqList& L) {
	//for (int i = 0; i < MaxSize; i++)
	//	L.data[i] = 0;
	L.length = 0;
}
int main() {
	SqList L;
	InitList(L);
	//尝试“违规”打印整个data数组
	for (int i = 0; i < MaxSize; i++)//i < L.length
		printf("data[%d] = %d ", i, L.data[i]);
	return 0;
}

#define InitSize 10
//动态分配的顺序表，定义一个指针，它包括数据类型，但需要分配数据长度
typedef struct {
	int* data;
	int MaxSize, length;	//表示数据表的最大长度和当前长度
}SqList;

void InitList(SqList& L) {
	L.data = (int*)malloc(sizeof(int) * InitSize); //开辟内存空间
	L.MaxSize = InitSize;
	L.length = 0;
}

void IncreaseSize(SqList& L, int len) {
	int* p = L.data;		//临时变量p暂存L.data的内容
	L.data = (int*)malloc(sizeof(int) * (L.MaxSize + len)); //开辟新的内存空间
	for (int i = 0; i < L.length; i++) {
		L.data[i] = p[i];	//暂存的的内容还给L.data
	}
	free(p);				//释放p的内存空间
}

int main() {
	SqList L;
	InitList(L);
	IncreaseSize(L, 5);

	return 0;
}

bool ListInsert(SqList& L, int i, int e) {//在第i个位置插入元素e，下标为i-1
	if (i<1 || i> L.length + 1 || L.length == MaxSize) {
		return false;
	}
	for (int j = L.length; j >= i; j--) {
		L.data[j] = L.data[j - 1];
	}
	L.data[i - 1] = e;
	L.length++;
	return true;
}

bool ListDelete(SqList& L, int i, int& e) {
	if (i<1 || i>L.length) {
		return false;
	}
	e = L.data[i - 1];
	for (int j = i; j < L.length - 1; j++) {//下标为i-1的元素不要，从i开始逐个前移
		L.data[j - 1] = L.data[j];
	}
	L.length--;
	return true;
}

int GetElem(SqList L, int i) {
	return L.data[i - 1];
}

int LocateElem(SqList L, int e){
	for (int i = 0; i < L.length; i++) {
		if (L.data[i] == e)
			return i + 1;				//返回的是位序，不是下标
	}
	return 0;
}