C Programming Tips

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


//链表节点
struct MyTypeNode
{
	MyType data;
	struct MyTypeNode* next;
};

const MAX_LEN = 1024 * 16; //链表节点最大分配数目
//链表，第一个节点为表头，数据从head->next开始（如果非空）
struct MyLinkList
{
	struct MyTypeNode	head;
	struct MyTypeNode*	Tail;
};

//初始化以及清除
void InitLinkList(struct MyLinkList* linkList);
void EmptyLinkList(struct MyLinkList* linkList);
int LinkListIsEmpty(const struct MyLinkList* linkList);
int LinkListIsFull(const struct MyLinkList* linkList);
int LinkListCount(const struct MyLinkList* linkList);

//输入输出
void InputLinkList_(struct MyLinkList* linkList, int n, FILE* fp);
void InputLinkList(struct MyLinkList* linkList);
void LoadLinkList(struct MyLinkList* myList, const char* filename);
void SaveList_(const struct MyLinkList* linkList, FILE* fp);
void PrintLinkList(const struct MyLinkList* linkList);
void SaveLinkList(const struct MyLinkList* linkLis, const char* filename);

//插入删除
void PushBack(struct MyLinkList* linkList, MyType data);
void Remove(struct MyLinkList* linkList, MyType data, MyTypeFun fun);
void Remove_Name(struct MyLinkList* linkList, const char* name);
void Remove_Value(struct MyLinkList* linkList, int value);

//排序
void SortBubble(struct MyLinkList* linkList, MyTypeFun fun);
void SortBubble_NameGreate(struct MyLinkList* linkList);
void SortBubble_ValueLess(struct MyLinkList* linkList);

//查找
MyType* Find_Value(struct MyLinkList* linkList, int data);
MyType* Find_Name(struct MyLinkList* linkList, const char* data);
MyType* Find(struct MyLinkList* linkList, MyType data, MyTypeFun fun);

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

	InputLinkList(&mylist);
	PrintLinkList(&mylist);

	EmptyLinkList(&mylist);
}

//测试文件种读入数据
void Test_Load()
{
	struct MyLinkList mylist;
	InitLinkList(&mylist);

	LoadLinkList(&mylist, "test.txt");
	PrintLinkList(&mylist);

	EmptyLinkList(&mylist);
}

int main()
{
	struct MyLinkList mylist;
	InitLinkList(&mylist);
	
	//链表添加一些随机数据
	for (int i = 0; i < 10; i++)
	{
		struct Info info;
		sprintf(info.name, "No%d", i);
		info.value = rand() % 100;
		
		PushBack(&mylist, info);
	}
	PrintLinkList(&mylist);

	//按照name排序
	SortBubble_NameGreate(&mylist);
	PrintLinkList(&mylist);

	//把value==2的结点删除
	Remove_Value(&mylist, 2);
	PrintLinkList(&mylist);

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

	EmptyLinkList(&mylist);
	return 0;
}


//初始化链表
void InitLinkList(struct MyLinkList* linkList)
{
	linkList->head.next = NULL;
	linkList->Tail = &linkList->head;
}

//清除链表内存
void EmptyLinkList(struct MyLinkList* linkList)
{
	struct MyTypeNode* node = linkList->head.next;
	while (node)
	{
		struct MyTypeNode* temp = node;
		node = node->next;

		free(temp);
	}
}

int LinkListIsEmpty(const struct MyLinkList* linkList)
{
	if (linkList->head.next == 0)
		return 1;
	return 0;
}

int LinkListIsFull(const struct MyLinkList* linkList)
{
	int n = LinkListCount(linkList);
	if (n < MAX_LEN)
		return 0;
	return 1;
}

int LinkListCount(const struct MyLinkList* linkList)
{
	int count = 0;
	const struct MyTypeNode* node = &linkList->head;
	while (node->next)
	{
		node = node->next;
		count++;
	}
	return count;
}

//保存，文件句柄
void SaveList_(const struct MyLinkList* linkList, FILE* fp)
{
	const struct MyTypeNode* node = linkList->head.next;
	while (node)
	{
		fprintf(fp, "%s,%d\t", node->data.name, node->data.value);

		node = node->next;
	}
	fprintf(fp, "\n");
}


//输出到屏幕
void PrintLinkList(const struct MyLinkList* linkLis)
{
	SaveList_(linkLis, stdout);
}


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


//输入，文件句柄
void InputLinkList_(struct MyLinkList* linkList, int n, FILE* fp)
{
	int cnt;
	for (int i = 0; i < n; i++)
	{
		MyType info;
		cnt = fscanf(fp, "%s", info.name);
		//fscanf_s(fp, "%s", info.name, 16); //或者
		cnt = fscanf(fp, "%d", &info.value);

		PushBack(linkList, info);
	}
}


//键盘输入
void InputLinkList(struct MyLinkList* linkList)
{
	int cnt;
	int n;
	cnt = scanf("%d", &n);

	InputLinkList_(linkList, n, stdin);
}


//文件读入
void LoadLinkList(struct MyLinkList* linkList, const char* filename)
{
	FILE* fp = fopen(filename, "rt");
	int n = 0;

	//表头部分，如果存在

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

	//表头部分，如果存在

	//数据部分
	InputLinkList_(linkList, n, fp);

	fclose(fp);
}

//链表尾部插入数据
void PushBack(struct MyLinkList* linkList, MyType data)
{
	if (LinkListIsFull(linkList)) return;

	struct MyTypeNode* node = (struct MyTypeNode*)malloc(sizeof(struct MyTypeNode));
	if (node)
	{
		node->data = data;
		node->next = NULL;
	}

	linkList->Tail->next = node;
	linkList->Tail = node;
}


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

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

//定义Value相等的函数
int Equal_Value(const MyType* v1, const MyType* v2)
{
	if (v1->value == v2->value)
		return 1;
	return 0;
}


//根据给定的比较函数，删除data
void Remove(struct MyLinkList* linkList, MyType data, MyTypeFun fun)
{
	struct MyTypeNode* node = &linkList->head;
	while (node->next)
	{
		if (fun(&node->next->data, &data))
		{
			struct MyTypeNode* temp = node->next;
			node->next = node->next->next;
			free(temp);
			break;
		}
		node = node->next;
	}
}


//删除给定name的节点
void Remove_Name(struct MyLinkList* linkList, const char * name)
{
	MyType data;
	sprintf(data.name, "%s", name);
	Remove(linkList, data, Equal_Value);
}


//删除给定value的节点
void Remove_Value(struct MyLinkList* linkList, int value)
{
	MyType data;
	data.value = value;
	Remove(linkList, data, Equal_Name);
}


//利用给定fun提供的顺序，冒泡排序
void SortBubble(struct MyLinkList* linkList, MyTypeFun fun)
{
	int len = LinkListCount(linkList);
	for (int i = 0; i< len - 1; i++)
	{//n-1轮处理
		// Last i elements are already in place
		int bChanged = 0;
		struct MyTypeNode* node = linkList->head.next;
		struct MyTypeNode* next = node->next;
		for (int j = 0; j <len - i - 1; j++)
		{
			if (!fun(&node->data, &next->data))
			{//相邻元素逆序，进行交换
				MyType tmp = next->data;
				next->data = node->data;
				node->data = tmp;

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


//定义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;
}

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


//定义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;
}

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


//查找给定value
MyType* Find_Value(struct MyLinkList* linkList, int data)
{
	MyType v = { "", data };
	return Find(linkList, v, Equal_Value);
}


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


//利用给定fun，查找包含data的节点
MyType* Find(struct MyLinkList* linkList, MyType data, MyTypeFun fun)
{
	struct MyTypeNode* node = linkList->head.next;
	while (node)
	{
		if (fun(&(node->data), &data))
		{
			return &(node->data);
		}
		node = node->next;
	}

	return 0;
}
C Programming Tips - Link
