C Programming Tips - DynamicList

DynamicList.c，RUN
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
线性表：
1.动态内存【但没有动态管理，一次申请，不再调整】
2.插入，删除
3.排序
*/

struct Info
{
	char	name[16];
	int		value;
};
//typedef的用法，让类型本身有描述性
typedef struct Info MyType;
//以下用MyType类型，这样更换MyType类型时，后续代码不用大的变化！

struct MyTypeList
{
	MyType* buffer;
	int capacity;				//最大容量
	int len;					//当前使用长度
};

void InitList(struct MyTypeList* myList, int capacity);
void EmptyList(struct MyTypeList* myList);

int ListIsEmpty(const struct MyTypeList* myList);
int ListIsFull(const struct MyTypeList* myList);
int ListCount(const struct MyTypeList* myList);

//输入输出
void Input(struct MyTypeList* myList);
void LoadList(struct MyTypeList* myList, const char* filename);
void PrintList(const struct MyTypeList* myList);
void SaveList(const struct MyTypeList* myList, const char* filename);

//排序
void SortBubble_NameGreat(struct MyTypeList* myList);
void SortBubble_ValueLess(struct MyTypeList* myList);

//插入删除
void PushBack(struct MyTypeList* myList, MyType data);
void Remove_Index(struct MyTypeList* myList, int index);
void Remove_Data(struct MyTypeList* myList, MyType data);

//查找
MyType* Find(struct MyTypeList* myList, MyType data);

//测试键盘输入
void Test_Input()
{
	struct MyTypeList mylist;
	InitList(&mylist, 1024);

	Input(&mylist);
	PrintList(&mylist);

	EmptyList(&mylist);
}

//测试文件读入
void Test_Load()
{
	struct MyTypeList mylist;
	LoadList(&mylist, "list.txt");
	PrintList(&mylist);

	EmptyList(&mylist);
}

int main()
{
	//Test_Input();
	//Test_Load();

	struct MyTypeList mylist;
	InitList(&mylist, 1024);

	MyType arr[] = { {"A1", 5}, {"A3", 4}, {"A2", 4}, {"A5", 3}, {"A4", 1} };
	for (int i = 0; i < sizeof(arr) / sizeof(MyType); i++)
	{
		MyType data = arr[i];
		PushBack(&mylist, data);
	}
	PrintList(&mylist);

	//name由大到小排序
	SortBubble_NameGreat(&mylist);
	PrintList(&mylist);

	//查找
	MyType data = { "Test", 2 };
	MyType* pData1 = Find(&mylist, data);
	if (pData1)
	{//找到

	}
	PrintList(&mylist);

	//value由小到大排序
	SortBubble_ValueLess(&mylist);
	PrintList(&mylist);

	//删除给定数据
	Remove_Data(&mylist, data);
	PrintList(&mylist);

	//输出到文件
	SaveList(&mylist, "test.txt");

	EmptyList(&mylist);
	return 0;
}


//初始化线性表，分配内存
void InitList(struct MyTypeList* myList, int capacity)
{
	myList->capacity = capacity;
	myList->buffer = (MyType*)malloc(sizeof(MyType) * myList->capacity);
	myList->len = 0;
}


//重置线性表，清空内存
void EmptyList(struct MyTypeList* myList)
{
	if (myList->buffer)
	{
		free(myList->buffer);
		myList->buffer = 0;
		myList->capacity = 0;
	}
	myList->len = 0;
}

//线性表是否为空
int ListIsEmpty(const struct MyTypeList* myList)
{
	if (myList->len == 0) return 1;
	return 0;
}

//线性表是否为满
int ListIsFull(const struct MyTypeList* myList)
{
	if (myList->len == myList->capacity) return 1;
	
	return 0;
}

//线性表长度
int ListCount(const struct MyTypeList* myList)
{
	return myList->len;
}


//键盘输入
void Input(struct MyTypeList* myList)
{
	int cnt;
	int n;
	cnt = scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		MyType data;
		cnt = scanf("%s%d", data.name, &data.value);

		PushBack(myList, data);
	}
}


//文件读入
void LoadList(struct MyTypeList* myList, const char* filename)
{
	int cnt;

	FILE* fp = fopen(filename, "rt");
	
	//表头部分，如果存在

	//数据部分
	while (!feof(fp))
	{
		MyType data;
		cnt = fscanf(fp, "%s%d", data.name, &data.value);

		PushBack(myList, data);
	}

	fclose(fp);
}


//输出到屏幕
void PrintList(const struct MyTypeList* myList)
{
	for (int i = 0; i < myList->len; i++)
	{
		printf("%s %d", myList->buffer[i].name, myList->buffer[i].value);
		if (i == myList->len - 1)
			printf("\n");
		else
			printf("\t");
	}
}


//保存到文件
void SaveList(const struct MyTypeList* myList, const char* filename)
{
	FILE* fp = fopen(filename, "W+t");
	for (int i = 0; i < myList->len; i++)
	{
		fprintf(fp, "%s %d", myList->buffer[i].name, myList->buffer[i].value);
		if (i == myList->len - 1)
			fprintf(fp, "\n");
		else
			fprintf(fp, "\t");
	}
	fclose(fp);
}


//线性表表尾插入数据
void PushBack(struct MyTypeList* myList, MyType data)
{
	if (myList->len + 1 >= myList->capacity)
	{//超出容量
		return;
	}

	if (myList->buffer)
		myList->buffer[myList->len++] = data;
}


//线性表指定位置删除数据
void Remove_Index(struct MyTypeList* myList, int index)
{
	if (index < 0 || index >= myList->len)//判断下标
		return;

	for (int i = index; i < myList->len - 1; i++)
	{
		myList->buffer[i] = myList->buffer[i + 1];
	}
	myList->len--;
}

//定义相等
int Func_Equal(const MyType* v1, const MyType* v2)
{
	if (v1->value == v2->value && strcmp(v1->name, v2->name) == 0)
		return 1;
	return 0;
}

//线性表删除指定数据
void Remove_Data(struct MyTypeList* myList, MyType data)
{
	for (int i = 0; i < myList->len; i++)
	{
		if (Func_Equal(&myList->buffer[i], &data))
		{//找到，删除，退出循环

			for (int k = i; k < myList->len - 1; k++)
			{
				myList->buffer[k] = myList->buffer[k + 1];
			}
			myList->len--;

			break;
		}
	}
}


//定义顺序：0，逆序；1，顺序
int Func_ValueLess(const MyType* v1, const MyType* v2)
{
	if (v1->value < v2->value ||
		(v1->value == v2->value && strcmp(v1->name, v2->name) < 0) )
		return 1;
	return 0;
}

//冒泡排序，value按照Func_ValueLess定义的顺序
void SortBubble_ValueLess(struct MyTypeList* myList)
{
	for (int i = 0; i < myList->len - 1; i++)
	{//n-1轮处理
		// Last i elements are already in place
		int bChanged = 0;
		for (int j = 0; j < myList->len - i - 1; j++)
		{
			if (!Func_ValueLess(&myList->buffer[j], &myList->buffer[j + 1]))
			{//相邻元素逆序，进行交换
				MyType tmp = myList->buffer[j + 1];
				myList->buffer[j + 1] = myList->buffer[j];
				myList->buffer[j] = tmp;

				bChanged = 1;
			}
		}
		if (!bChanged)
		{//没有出现位置调整的情况，也就是说，数组已经有序
			return;
		}
	}
}


int Func_NameGreat(const MyType* v1, const MyType* v2)
{
	if ((strcmp(v1->name, v2->name) > 0) ||
		(strcmp(v1->name, v2->name) == 0 && v1->value < v2->value)
		)
		return 1;
	return 0;
}

//冒泡排序，name按照Func_NameGreat定义的顺序
void SortBubble_NameGreat(struct MyTypeList* myList)
{
	for (int i = 0; i < myList->len - 1; i++)
	{//n-1轮处理
		// Last i elements are already in place
		int bChanged = 0;
		for (int j = 0; j < myList->len - i - 1; j++)
		{
			if (!Func_NameGreat(&myList->buffer[j], &myList->buffer[j + 1]))
			{//相邻元素逆序，进行交换
				MyType tmp = myList->buffer[j + 1];
				myList->buffer[j + 1] = myList->buffer[j];
				myList->buffer[j] = tmp;

				bChanged = 1;
			}
		}
		if (!bChanged)
		{//没有出现位置调整的情况，也就是说，数组已经有序
			return;
		}
	}
}


MyType* Find(struct MyTypeList* myList, MyType data)
{
	for (int i = 0; i < myList->len; i++)
	{
		if (Func_Equal(&myList->buffer[i], &data))
			return &myList->buffer[i];
	}

	return 0;
}