Day25.C提高（数据机构02）

2023-12-04 23:18:40

C提高（数据结构02）

001.单向链表（版本二）

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

//链表结点数据结构
struct LinkNode
{
	struct LinkNode* next;
};

//链表结构体
struct LList
{
	struct LinkNode header;//头结点
	int size;
};

typedef void* LinkList;



//初始化链表
LinkList Init_LinkList()
{
	struct LList* list = malloc(sizeof(struct LList));
	if (NULL == list)
	{
		return NULL;
	}
	list->header.next = NULL;
	list->size = 0;

	return list;
}

//插入（按位置插入）
void Insert_LinkList(LinkList list, int position, void* data)
{
	if (NULL == list)
	{
		return;
	}
	if (NULL == data)
	{
		return;
	}

	struct LinkNode* mynode = (struct LinkNode*)data;
	struct LList* mylist = (struct LList*)list;
	if (position < 0 || position > mylist->size)
	{
		position = mylist->size;
	}
	//辅助指针
	struct LinkNode* pCurrent = &(mylist->header);
	//找到位置（要找到position前一个位置）
	for (int i = 0; i < position; ++i)
	{
		pCurrent = pCurrent->next;
	}
	//重新建立新节点的前驱和后继结点的关系
	mynode->next = pCurrent->next;
	pCurrent->next = mynode;
	//更新链表大小
	mylist->size++;

}

//遍历
void Foreach_LinkList(LinkList list, void(*FOREACH)(void*))
{
	if (NULL == list)
	{
		return;
	}
	if (NULL == FOREACH)
	{
		return;
	}

	struct LList* mylist = (struct LList*)list;
	struct LinkNode* pCurrent = mylist->header.next;

	while (pCurrent != NULL)
	{
		struct LinkNode* pNext = pCurrent->next;
		FOREACH(pCurrent);
		pCurrent = pNext;
	}

}

//删除结点
void RemoveByPos_LinkList(LinkList list, int Position)
{
	if (NULL == list)
	{
		return;
	}
	struct LList* mylist = (struct LList*)list;
	if (Position < 0 || Position > mylist->size - 1)
	{
		return;
	}
	//辅助指针
	struct LinkNode* pCurrent = &(mylist->header);
	for (int i = 0; i < Position; ++i)
	{
		pCurrent = pCurrent->next;
	}
	//缓存待删除结点位置
	struct LinkNode* pDel = pCurrent->next;
	//重新建立待删除结点的前驱和后继结点的关系
	pCurrent->next = pDel->next;
	//更新链表的大小
	mylist->size--;
}

//销毁链表
void Destroy_LinkList(LinkList list)
{
	if (NULL == list)
	{
		return;
	}
	free(list);
	list = NULL;
}


struct Person
{
	struct LinkNode node;
	char name[64];
	int age;
};

void myPrint(void* data)
{
	if (NULL == data)
	{
		return;
	}
	struct Person* person = (struct Person*)data;
	printf("Name:%s Age:%d\n", person->name, person->age);
}

void test101()
{
	//初始化链表
	struct LList* list = Init_LinkList();
	//创建数据
	struct Person p1 = { NULL,"aaa",10 };
	struct Person p2 = { NULL,"bbb",20 };
	struct Person p3 = { NULL,"ccc",30 };
	struct Person p4 = { NULL,"ddd",40 };
	struct Person p5 = { NULL,"eee",50 };
	struct Person p6 = { NULL,"fff",60 };

	//插入数据
	Insert_LinkList(list, 0, &p1);
	Insert_LinkList(list, 0, &p2);
	Insert_LinkList(list, 0, &p3);
	Insert_LinkList(list, 0, &p4);
	Insert_LinkList(list, 0, &p5);
	Insert_LinkList(list, 0, &p6);

	//遍历打印
	Foreach_LinkList(list, myPrint);

	//按位置删除元素
	RemoveByPos_LinkList(list, 2);

	//遍历打印
	printf("------------------\n");
	Foreach_LinkList(list, myPrint);

	//销毁链表
	Destroy_LinkList(list);
}

int main(void)
{
	test101();

	system("pause");
	return EXIT_SUCCESS;
}

002.受限线性表

栈

概念：

首先它是一个线性表，也就是说，栈元素具有线性关系，即前驱后继关系。只不过它是一种特殊的线性表而已。定义中说是在线性表的表尾进行插入和删除操作，这里表尾是指栈顶而不是栈底。

特性：

它的特殊之处在于限制了这个线性表的插入和删除的位置，它始终只在栈顶进行。这也就使得：栈底是固定的，最先进栈的只能在栈底。（栈不支持随机存取）

操作：

栈的插入操作，叫做进栈，也叫压栈。类似子弹入弹夹。
栈的删除操作，叫做出栈（弹栈，退栈）。类似弹夹中的子弹弹出弹夹。

栈的顺序存储：

基本概念：栈的顺序存储结构简称顺序栈，它是运算受限制的顺序表。顺序栈的存储结构是：利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序表中的位置。

设计与实现:因为栈是一种特殊的线性表，所以栈的顺序存储可以通过顺序线性表来实现。

栈的链式存储：

基本概念：栈的链式存储结构简称链栈

栈的顺序存储

SeqStack.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#ifdef __cplusplus
extern "C"{
#endif

#define MAX 1024

	//顺序栈数据结构
	struct SStack
	{
		void* data[MAX];//存放数据的数组
		int size;//栈中元素的个数
	};
	typedef void* SeqStack;
	//数组高下标的位置当作栈顶（因为在插入和删除的过程中不需要移动数组中的元素）

	//初始化
	SeqStack Init_SeqStack();
	//入栈
	void Push_SeqStack(SeqStack stake,void* data);
	//出栈
	void Pop_SeqStack(SeqStack stack);
	//获得栈顶元素
	void* Top_SeqStack(SeqStack stack);
	//获得栈的大小
	int Size_SeqStack(SeqStack stack);
	//销毁栈
	void Destroy_SeqStack(SeqStack stack);

#ifdef __cplusplus
}
#endif

SeqStack.c

#include"SeqStack.h"

//初始化
SeqStack Init_SeqStack()
{
	struct SStack* stack = malloc(sizeof(struct SStack));
	if (NULL == stack)
	{
		return NULL;
	}
	//初始化该内存区域
	//memset(stack->data, 0, sizeof(void*) * MAX);
	memset(stack, 0, sizeof(struct SStack));
	stack->size = 0;

}
//入栈
void Push_SeqStack(SeqStack stack, void* data)
{
	if (NULL == stack)
	{
		return;
	}
	if (NULL == data)
	{
		return;
	}
	struct SStack* mystack = (struct SStack*)stack;
	mystack->data[mystack->size] = data;
	mystack->size++;

}
//出栈
void Pop_SeqStack(SeqStack stack)
{
	if (NULL == stack)
	{
		return;
	}
	struct SStack* mystack = (struct SStack*)stack;
	mystack->data[mystack->size - 1] = NULL;
	mystack->size--;

}
//获得栈顶元素
void* Top_SeqStack(SeqStack stack)
{
	if (NULL == stack)
	{
		return NULL;
	}
	struct SStack* mystack = (struct SStack*)stack;
	if (mystack->size <= 0)
	{
		return NULL;
	}
	return mystack->data[mystack->size-1];
}
//获得栈的大小
int Size_SeqStack(SeqStack stack)
{
	if (NULL == stack)
	{
		return NULL;
	}
	struct SStack* mystack = (struct SStack*)stack;
	if (mystack->size <= 0)
	{
		return NULL;
	}
	return mystack->size;
}
//销毁栈
void Destroy_SeqStack(SeqStack stack)
{
	if (NULL == stack)
	{
		return;
	}
	free(stack);
	stack = NULL;
}

栈的顺序存储.c

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"SeqStack.h"

struct Person_2
{
	char name[64];
	int age;
};

void test201()
{
	//初始化栈
	struct SStack* stack = Init_SeqStack();
	//创建数据
	struct Person_2 p1 = { "aaa",10 };
	struct Person_2 p2 = { "bbb",20 };
	struct Person_2 p3 = { "ccc",30 };
	struct Person_2 p4 = { "ddd",40 };
	struct Person_2 p5 = { "eee",50 };
	struct Person_2 p6 = { "fff",60 };
	//数据入栈
	Push_SeqStack(stack, &p1);
	Push_SeqStack(stack, &p2);
	Push_SeqStack(stack, &p3);
	Push_SeqStack(stack, &p4);
	Push_SeqStack(stack, &p5);
	Push_SeqStack(stack, &p6);
	//输出栈中元素
	while (Size_SeqStack(stack) > 0)
	{
		//获得栈顶元素
		struct Person_2* person = (struct Person_2*)Top_SeqStack(stack);
		//打印
		printf("Name:%s Age:%d\n", person->name, person->age);
		//出栈
		Pop_SeqStack(stack);
	}

	//销毁栈
	Destroy_SeqStack(stack);
}

int main(void)
{
	test201();
	system("pause");
	return EXIT_SUCCESS;
}

栈的链式存储

LinkStack.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>


#ifdef __cplusplus
extern "C" {
#endif

	struct StackNode
	{
		struct StackNode* next;
	};

	struct LStack
	{
		struct StackNode header;
		int size;
	};
	typedef void* LinkStack;

	//初始化
	LinkStack Init_LinkStack();
	//入栈
	void Push_LinkStack(LinkStack stack, void* data);
	//出栈
	void Pop_LinkStack(LinkStack stack);
	//获得栈顶元素
	void* Top_LinkStack(LinkStack stack);
	//获得栈的大小
	int Size_LinkStack(LinkStack stack);
	//销毁栈
	void Destroy_LinkStack(LinkStack stack);




#ifdef __cplusplus
}
#endif

LinkStack.c

#include"LinkStack.h"

//初始化
LinkStack Init_LinkStack()
{
	struct LStack* stack = malloc(sizeof(struct LStack));
	if (NULL == stack)
	{
		return NULL;
	}
	stack->header.next = NULL;
	stack->size = 0;
	return stack;

}
//入栈
void Push_LinkStack(LinkStack stack, void* data)
{
	if (NULL == stack)
	{
		return;
	}
	if (NULL == data)
	{
		return;
	}
	struct LStack* mystack = (struct LStack*)stack;
	struct StackNode* newNode = (struct StackNode*)data;
	//创建辅助指针
	struct StackNode* pNext = mystack->header.next;
	//建立入栈元素与前驱后继的关系
	mystack->header.next = newNode;
	newNode->next = pNext;
	//更新栈的大小
	mystack->size++;

}

//出栈
void Pop_LinkStack(LinkStack stack)
{
	if (NULL == stack)
	{
		return;
	}
	struct LStack* mystack = (struct LStack*)stack;
	if (mystack->size <= 0)
	{
		return;
	}
	//缓存一下第一个结点
	struct StackNode* pFirst = mystack->header.next;
	mystack->header.next = pFirst->next;
	mystack->size--;

}

//获得栈顶元素
void* Top_LinkStack(LinkStack stack)
{
	if (NULL == stack)
	{
		return NULL;
	}
	struct LStack* mystack = (struct LStack*)stack;
	if (mystack->size <= 0)
	{
		return NULL;
	}
	return mystack->header.next;
}


//获得栈的大小
int Size_LinkStack(LinkStack stack)
{
	if (NULL == stack)
	{
		return -1;
	}
	struct LStack* mystack = (struct LStack*)stack;
	return mystack->size;
}
//销毁栈
void Destroy_LinkStack(LinkStack stack)
{
	if (NULL == stack)
	{
		return;
	}
	free(stack);
	stack = NULL;
}

栈的链式存储.c

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"LinkStack.h"

struct Person_3
{
	struct StackNode node;
	char name[64];
	int age;
};

void test301()
{
	//初始化栈
	struct LStack* stack = Init_LinkStack();
	//创建数据
	struct Person_3 p1 = { NULL,"aaa",10 };
	struct Person_3 p2 = { NULL,"bbb",20 };
	struct Person_3 p3 = { NULL,"ccc",30 };
	struct Person_3 p4 = { NULL,"ddd",40 };
	struct Person_3 p5 = { NULL,"eee",50 };
	struct Person_3 p6 = { NULL,"fff",60 };
	//数据入栈
	Push_LinkStack(stack, &p1);
	Push_LinkStack(stack, &p2);
	Push_LinkStack(stack, &p3);
	Push_LinkStack(stack, &p4);
	Push_LinkStack(stack, &p5);
	Push_LinkStack(stack, &p6);
	//输出栈中元素
	while (Size_LinkStack(stack) > 0)
	{
		//获得栈顶元素
		struct Person_3* person = (struct Person_3*)Top_LinkStack(stack);
		//打印
		printf("Name:%s Age:%d\n", person->name, person->age);
		//出栈
		Pop_LinkStack(stack);
	}

	//销毁栈
	Destroy_LinkStack(stack);
}

int main(void)
{
	test301();

	system("pause");
	return EXIT_SUCCESS;
}

栈的应用（就近匹配）

几乎所有的编译器都具有检测括号是否匹配的能力，那么如何实现编译器中的符号成对检测？如下字符串：
5+5*(6)+9/3*1)-(1+3(

算法思路：
1、从第一个字符开始扫描
2、当遇见普通字符串时忽略
3、当遇见左符号时压入栈中
4、当遇见右符号时从栈中弹出栈顶符号，并进行匹配
5、匹配成功：继续读入下一个字符
6、匹配失败：立即停止，并报错
结束：
成功：所有字符扫描完毕，且栈为空
失败：匹配失败或者所有字符扫描完毕但栈非空

代码实现：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"SeqStack.h"

int IsLeft(char ch)
{
	return ch == '(';
}

int IsRight(char ch)
{
	return ch == ')';
}

void printError(const char* str, char* errMsg, char* pos)
{
	printf("错误信息：%s\n", errMsg);
	printf("%s\n", str);

	int dis = pos - str;
	for (int i = 0; i < dis; ++i)
	{
		printf(" ");
	}
	printf("A\n");
}


void test401()
{
	const char* str = "5+5*(6)+9/3*1)-(1+3(";
	char* p = (char*)str;
	//初始化栈
	SeqStack stack = Init_SeqStack();

	while (*p != '\0')
	{
		//判断当前字符是否为左括号
		if (IsLeft(*p))
		{
			Push_SeqStack(stack, p);
		}
		//判断当前字符是否为右括号
		if (IsRight(*p))
		{
			if (Size_SeqStack(stack) > 0)
			{
				//弹出栈顶元素
				Pop_SeqStack(stack);
			}
			else
			{
				printError(str, "右括号没有匹配的左括号", p);
			}
		}
		p++;

	}
		
		while (Size_SeqStack(stack) > 0)
		{
			printError(str, "没有匹配的右括号！", Top_SeqStack(stack));
			//弹出栈顶元素
			Pop_SeqStack(stack);
		}

	//销毁栈
	Destroy_SeqStack(stack);
}

int main(void)
{
	test401();

	system("pause");
	return EXIT_SUCCESS;
}

码农公寓