C Programming Tips - AdancedList

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

/*
线性表：
1.动态内存【有内存调度】
2.插入，删除
3.排序
4.使用函数指针进行不同排序，不同查找的简化
5.将文件句柄和标准输入输出统一
*/


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

//函数类型定义，MyTypeFun为排序，查找等函数的原型
typedef int (*MyTypeFun)(const MyType* v1, const MyType* v2);

void PrintMyType(const MyType* myType, FILE* fp);
int Equal(const MyType* v1, const MyType* v2);


const int c_deltaLne = 1024 * 2;
const MAX_LEN = 1024 * 16; //链表节点最大分配数目
struct MyTypeList
{
	MyType* buffer;
	int capacity;				//最大容量
	int len;					//当前使用长度
};

//初始化与清理
void InitList(struct MyTypeList* myList);
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(struct MyTypeList* myList, MyTypeFun fun);
void SortBubble_NameGreate(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_Value(struct MyTypeList* myList, int data);
MyType* Find_Name(struct MyTypeList* myList, const char* data);
MyType* Find(struct MyTypeList* myList, MyType data, MyTypeFun fun);

//测试键盘读入数据
void Test_Input()
{
	struct MyTypeList mylist;
	InitList(&mylist);

	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);

	//随机加入一些数据
	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_NameGreate(&mylist);
	PrintList(&mylist);

	{//按照value查找
		MyType* pData1 = Find_Value(&mylist, 2);
		if (pData1)
		{//找到

		}
		PrintList(&mylist);
	}
	{//按照name查找
		MyType* pData1 = Find_Name(&mylist, "Test");
		if (pData1)
		{//找到

		}
		PrintList(&mylist);
	}

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

	{//删除数据
		MyType data = {"A3", 4};
		Remove_Data(&mylist, data);
		PrintList(&mylist);
	}

	//保存到文件
	SaveList(&mylist, "test.txt");

	EmptyList(&mylist);
	return 0;
}


//初始化线性表，分配内存
void InitList(struct MyTypeList* myList)
{
	myList->capacity = c_deltaLne;
	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 1;
}

int ListIsFull(const struct MyTypeList* myList)
{
	if (myList->len == MAX_LEN) return 1;
	return 0;
}

int ListCount(const struct MyTypeList* myList)
{
	return myList->len;
}


//输入，文件句柄
void InputList_(struct MyTypeList* myList, int n, FILE* fp)
{
	for (int i = 0; i < n; i++)
	{
		MyType data;
		int cnt = fscanf(fp, "%s%d", data.name, &data.value);

		PushBack(myList, data);
	}
}


//键盘输入
void Input(struct MyTypeList* myList)
{
	int cnt;
	int n;
	cnt = scanf("%d", &n);

	InputList_(myList, n, stdin);
}


//从文件读入
void LoadList(struct MyTypeList* myList, const char* filename)
{
	FILE* fp = fopen(filename, "rt");
	int n = 0;

	//表头部分，如果存在

	//数据部分
	while (!feof(fp))
	{
		n++;
		char temp[2048];
		fgets(temp, 2048, fp);
	}
	rewind(fp); //回到文件开始

	//表头部分，如果存在
	
	//数据部分
	InputList_(myList, n, fp);
	
	fclose(fp);
}


//输出，文件句柄
void SaveList_(const struct MyTypeList* myList, FILE* fp)
{
	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 PrintList(const struct MyTypeList* myList)
{
	SaveList_(myList, stdout);
}


//保存到文件
void SaveList(const struct MyTypeList* myList, const char* filename)
{
	FILE* fp = fopen(filename, "W+t");
	//可以加上表头
	SaveList_(myList, fp);
	fclose(fp);
}


//线性表表尾插入数据
void PushBack(struct MyTypeList* myList, MyType data)
{
	if (myList->len + 1 >= myList->capacity)
	{//超出容量，申请一个更大的内存
		myList->capacity = myList->capacity + c_deltaLne;
		if (myList->capacity > MAX_LEN)//限制内存分配，以免无限扩大
			myList->capacity = MAX_LEN;
		myList->buffer = (MyType*)realloc(myList->buffer, sizeof(MyType) * (myList->capacity));
	}

	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;
		}
	}
}


//定义value的正序，由小到大
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;
}

//定义name的正序，由大到小
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;
}


//冒泡排序，value按照Func_ValueLess定义的顺序
void SortBubble(struct MyTypeList* myList, MyTypeFun fun)
{
	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 (!fun(&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;
		}
	}
}


//根据Name由大到小顺序排序
void SortBubble_NameGreate(struct MyTypeList* myList)
{
	SortBubble(myList, Func_NameGreat);
}


//根据value由小到大顺序排序
void SortBubble_ValueLess(struct MyTypeList* myList)
{
	SortBubble(myList, Func_ValueLess);
}


//查找函数，1，相等；0，不相等
int Func_Value(const MyType* v1, const MyType* v2)
{
	if (v1->value == v2->value)
		return 1;
	return 0;
}

//查找给定value
MyType* Find_Value(struct MyTypeList* myList, int data)
{
	MyType v = { "", data };
	return Find(myList, v, Func_Value);
}

int Func_Name(const MyType* v1, const MyType* v2)
{
	if (strcmp(v1->name, v2->name) == 0)
		return 1;
	return 0;
}

//查找给定的name
MyType* Find_Name(struct MyTypeList* myList, const char* data)
{
	MyType v;
	sprintf(v.name, "%s", data);
	//strcpy(v.name, data);
	return Find(myList, v, Func_Name);
}


//利用给定fun，查找包含data的节点
MyType* Find(struct MyTypeList* myList, MyType data, MyTypeFun fun)
{
	for (int i = 0; i < myList->len; i++)
	{
		if (fun(&myList->buffer[i], &data))
			return &myList->buffer[i];
	}

	return 0;
}