数据结构-栈，队列，顺序表，哈希

栈结构

FILO 先进后出，后来居上的一种存储方式

栈的基本属性：栈内存 ，栈顶标记，栈的当前元素个数

栈的基本操作：入栈，出栈，获取栈顶元素：栈顶标记的元素（头插法）

万金油操作：判断是否为NULL，当前栈中数据个数

根据实现方式，栈分为两种方式：链式栈，数组栈

队列

FIFO 先进先出，排队的方式（尾插法）

链式栈

main.cpp

# include <stdio.h>
# include <string.h>
# include <stdlib.h>
//链表结构
struct Node
{
	int data;
	struct Node* next;
};
 
struct Node* creatNode(int data)
{
	struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
	newNode->next = NULL;
	newNode->data = data;
	return newNode;
}
//栈结构
struct stack
{
	int sizeStack;//栈当前元素个数
	struct Node* stackTop;//栈顶标记用指针表示
};
//创建栈，描述栈的最初状态
struct stack* createStack()
{
	struct stack* pstack = (struct stack*)malloc(sizeof(struct stack));
	pstack->sizeStack = 0;
	pstack->stackTop = NULL;
	return pstack;
}
//万金油函数
int size(struct stack* pstack)
{
	return pstack->sizeStack;
}
int empty(struct stack* pstack)
{
	return pstack->sizeStack!=0;
}
//入栈操作--》链表的头插法，无头链表 栈顶指针永远指向第一个节点
void push(struct stack* pstack, int data)
{
	struct Node* newNode = creatNode(data);
	if (newNode == NULL)
	{
		return;
	}
	else
	{
		newNode->next = pstack->stackTop;
		pstack->stackTop = newNode;
		pstack->sizeStack++;
	}
}
//出栈：链表的删除：无头链表的头删法
void pop(struct stack* pstack)
{
	if (pstack->sizeStack == 0)
	{
		printf("栈为空，无法删除");
		return;
	}
	else
	{
		//堆内存实现的栈需内存释放
		struct Node* nextNode = pstack->stackTop->next;
		free(pstack->stackTop);
		pstack->stackTop = nextNode;
		pstack->sizeStack--;
	}
}
//获取栈顶元素
int top(struct stack* pstack)
{
	if (pstack->sizeStack == 0)
	{
		printf("栈为空，无法获取栈顶元素");
		return 0;
	}
	return pstack->stackTop->data;
}
 
int main()
{
	struct stack* mystack = createStack();
	int num = 1234;
	while (num != 0)
	{
		push(mystack, num % 2);
		num /= 2;
	}
	
	while (empty(mystack))
	{
		printf("%d", top(mystack));//栈顶元素先出
		pop(mystack);
	}
 
	return 0;
}
 

数组栈

方便，但是数组长度受限制，是自己申请的才要释放，不是自己的系统会自动回收！

main.cpp

int main()
{
	//struct stack* mystack = createStack();
	int num = 1234;
	//通常情况用数组充当栈内存
	int stack[20];
	int stackTop = -1;//下标充当位置
	while (num != 0)
	{
		//入栈操作
		stackTop++;
		stack[stackTop] = num % 2;//等同于stack[++stackTop] = num % 2;
		num /= 2;
	}
	//因为栈顶标记正好是等于数组下标
	while (stackTop != -1)
	{
		printf("%d ", stack[stackTop]);//获取栈顶元素
		//出栈，伪删除
		stackTop--;
	}
	return 0;
}

寻路问题

迷宫寻路

C语言知识回顾

main.cpp

 
# include <stdio.h>
 
//指针传参的两种方式
void print(int arr[],int a){}
void print2(int* arr,int a){}
 
int main()
{
	int arr[3] = { 1,2,3 };
	print(arr, 4);
	print2(arr, 4);
	return 0;
}

二级指针申请一段内存存放多个一级指针存放整数

main.cpp

int** makeArray(int row, int cols)
{
	int** array = (int**)malloc(sizeof(int) * row);
	for (int i = 0; i < cols; i++)
	{
		array[i] = (int*)malloc(sizeof(int) * cols);
	}
	return array;
}

走迷宫流程：

默认从(1,1)开始走，默认方向是往右(0)走，准备往右走时先提前计算出往右走后落点处坐标，也就是(1,2),然后通过判断(1,2)是不是墙(判断是否为0)，如果是墙就换个方向测试直到下一个落脚点不是墙，如果4个方向都是墙那就直接退出外循环，现在当测到往下的方向(1)时可以走那就退出内循环然后把当前位置(1,1)入栈，再把下一个落脚点的坐标变成当前位置,也就是新的当前位置是(2,1),然后再把上一个落脚点堵住(置1)，然后把方向改回默认方向(0)，回到判断下一个是否为落脚点的语句里，像之前那样个个方向都判断，直到下一个落脚点不是墙为止，判断过后可以发现下一个落脚点就是(2,2),所以故技重施，把当前位置(2,1)入栈，再把下一个落脚点的坐标变成当前位置,也就是新的当前位置是(2,2)，再把上一个落脚点堵住(置1)，然后方向也改回默认方向，重复上面步骤，然后判断过后可以发现下一个落脚点就是(2,3),所以故技重施，把当前位置(2,2)入栈，再把下一个落脚点的坐标变成当前位置,也就是新的当前位置是(2,3)，然后继续当到出口时把(2,3)入栈，然后此时坐标是(3,3)已经是地图的右下角故不满足循环条件退出循环把(3,3)入栈。

main.cpp

# include <stdio.h>
# include <string.h>
# include <stdlib.h>
# define R 3//出口
# define C 3
 
//数组里面去寻路：位置- ->行和列
struct position
{
	int row;//行
	int cols;//列
};
struct position pathStack[100];//存放路径-->栈内存
int stackTop = -1;//栈顶标记
int** maze = NULL;//二维数组去描述地图
int size = 0;//迷宫大小
int** makeArray(int row, int cols)
{
	int** array = (int**)malloc(sizeof(int) * row);
	for (int i = 0; i < cols; i++)
	{
		array[i] = (int*)malloc(sizeof(int) * cols);
	}
	return array;
}
//用户输入一个迷宫
void createMaze()
{
	printf("输入迷宫大小：\n");
	scanf("%d", &size);
	maze = makeArray(size + 2, size + 2);//加2 表示边框
	printf("输入迷宫:\n");
	for (int i = 1; i <= size; i++)
	{
		for (int j = 1; j <= size; j++)
		{
			scanf("%d", &maze[i][j]);
		}
	}
	//加边框：1 表示不可以走
	for (int i = 0; i <= size; i++)
	{
		maze[0][i] = maze[size + 1][i] = 1;//上下两行
		maze[i][0] = maze[i][size + 1];//左右两列
	}
}
//找路径
int findPath()
{
	//偏移属性描述出来
	struct position offset[4];//0-3表示四个方向
	//往右走
	offset[0].row = 0;
	offset[0].cols = 1;
	//往左走
	offset[2].row = 0;
	offset[2].cols = -1;
	//往下走
	offset[1].row = 1;
	offset[1].cols = 0;
	//往上走
	offset[3].row = -1;
	offset[3].cols = 0;
	//选定入口
	struct position here = { 1,1 };//当前位置
	//走迷宫:记录走过的路
	//走过ID路标记为1
	maze[1][1] = 1;
	int option = 0;//下一个移动方向
	int endOption = 3;//终止方向
	while (here.row != R || here.cols != C)
	{
		//相邻的位置做移动
		int rowNum, colsNum;//记录下标变化
		while (option <= endOption)
		{
			//行的变化=原位置+偏移量 ，偏移量由方向决定
			rowNum = here.row + offset[option].row;
			colsNum = here.cols + offset[option].cols;
			//一旦确定一个方向可以走，就需去下一步
			if (maze[rowNum][colsNum] == 0)
				break;//退出循环走另一边
			//不能走就换方向测试
			option++;
		}
		//可以走
		if (option <= endOption)
		{
			//走到下一个
			pathStack[++stackTop] = here;
			//改变当前位置
			here.row = rowNum;
			here.cols = colsNum;
			//走过的路标记--->堵上
			maze[rowNum][colsNum] = 1;
			option = 0;//置0 去找下一个位置
		}
		else//option==4;表示没有可走的地方
		{
			//回到上一步去
			if (stackTop == -1)
				return 0;//无路可走表示没有路径
			//出栈方式去回退到上一步
			struct position next = pathStack[stackTop];
			stackTop--;
			//方向的处理
			if (next.row == here.row)//行没变，左右走的
			{
				//逆过来偏移公式
				option = 2 + next.cols - here.cols;
			}
			else
			{
				option = 3 + next.row - here.row;
 
			}
			here = next;//当前位置变成回退后的位置
		}
	}
	if (here.row == R && here.cols == C)
	{
		pathStack[++stackTop] = here;
	}
	//打印到出口后的地图
	printf("\n");
	for (int i = 1; i <= size; i++)
	{
		for (int j = 1; j <= size; j++)
		{
			printf("%d ", maze[i][j]);
		}
		printf("\n");
	}
	printf("\n");
	return 1;
 
}
//打印路径
void printPath()
{
	printf("路径方式：\n");
	struct position curPos;
	while (stackTop != -1)
	{
		curPos = pathStack[stackTop];
		stackTop--;
		printf("(%d ,%d)--->", curPos.row, curPos.cols);
	}
	printf("\n");
}
 
int main()
{
	createMaze();
	if (findPath())
	{
		printPath();
	}
	else
	{
		printf("没有路径\n");
	}
	
 
	return 0;
}
 

队列

链式队列

main.cpp

# include <stdio.h>
# include <string.h>
# include <stdlib.h>
 
struct Node
{
	int data;
	struct Node* next;
};
//创建节点过程，为队列做准备
struct Node* createNode(int data)
{
	struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
	if (!newNode)
	{
		return NULL;
	}
	else
	{
		newNode->data = data;
		newNode->next = NULL;
		return newNode;
	}
}
struct queue
{
	int sizeQueue;
	//链式结构实现：结构体指针
	//数组实现：数组下标
	struct Node* frontNode;//队头指针指向头节点
	struct Node* tailNode;//队尾指针指向尾节点
};
//使用一个东西表示整个队列
//描述最初状态
struct queue* createQueue()
{
	struct queue* myqueue = (struct queue*)malloc(sizeof(struct queue));
	if (!myqueue)
	{
		return NULL;
	}
	else
	{
		myqueue->sizeQueue = 0;
		myqueue->frontNode = myqueue->tailNode = NULL;
		return myqueue;
	}
}
//万金油函数
int size(struct queue* myqueue)
{
	return myqueue->sizeQueue;
}
//返回1表示不为NULL，返回0表示NULL
int empty(struct queue* myqueue)
{
	return myqueue->sizeQueue != 0;
}
//入队操作：无头链表再封装方式
void push(struct queue* myqueue, int data)
{
	struct Node* newNode = createNode(data);
	if (empty(myqueue) == 0)//队列为空
		myqueue->frontNode = newNode;
	else
		myqueue->tailNode->next = newNode;
 
	myqueue->tailNode = newNode;
	myqueue->sizeQueue++;
}
//出队操作：无头链表的头删法
void pop(struct queue* myqueue)
{
	//判断是否为空
	if (empty(myqueue) == 0)
	{
		printf("无法出队！");
		return;
	}
	//先保存下一个节点
	struct Node* nextNode = myqueue->frontNode->next;
	//然后删除结点
	free(myqueue->frontNode);
	myqueue->frontNode = NULL;
	//把指向头节点的指针指向新的头节点
	myqueue->frontNode = nextNode;
	myqueue->sizeQueue--;
}
//获取队头元素
int front(struct queue* myqueue)
{
	if (empty(myqueue) == 0)
	{
		printf("无法出队");
		exit(0);
	}
	else
		return myqueue->frontNode->data;
}
int main()
{
	struct queue* myqueue = createQueue();
	for (int i = 0; i < 1000; i++)
	{
		push(myqueue, i);
	}
	while (empty(myqueue))
	{
		printf("%d\t", front(myqueue));
		pop(myqueue);
	}
	return 0;
}
 

数组队列

main.cpp

# include <stdio.h>
# include <string.h>
# include <stdlib.h>
# define MAX 10
 
struct queue
{
	int* queueMemory;  //队列容量
	int frontPos;//队头元素下标
	int tailPos;//队尾元素下标
};
 
struct queue* createQueue()
{
	struct queue* myqueue = (struct queue*)malloc(sizeof(struct queue));
	//描述最初状态
	//数组当队列
	//一级指针-->一维数组：动态内存申请
	if (myqueue == NULL)
	{
		printf("创建失败");
		return NULL;
	}
	else
	{
		myqueue->queueMemory = (int*)malloc(sizeof(int) * MAX);
		myqueue->frontPos = myqueue->tailPos = -1;
		return myqueue;
	}
}
//入队
void push(struct queue* myqueue, int data)
{
	//用数组时一定要判断是否满了
	if (myqueue->tailPos == MAX - 1)
	{
		printf("队列已满");
		return;
	}
	myqueue->tailPos++;
	myqueue->queueMemory[myqueue->tailPos] = data;
}
 
//出队和获取队头元素合一起
int pop(struct queue* myqueue)
{
	if (myqueue->frontPos == myqueue->tailPos)
	{
		printf("队列为NULL");
		return -1;
	}
	return myqueue->queueMemory[++myqueue->frontPos];
}
int empty(struct queue* myqueue)
{
	return myqueue->frontPos !=myqueue->tailPos;
}
 
int main()
{
	struct queue* myqueue = createQueue();
	for (int i = 0; i < MAX; i++)
	{
		push(myqueue, i);
	}
	while (empty(myqueue))
	{
		printf("%d ", pop(myqueue));
	}
	return 0;
}
 

数组队列~逆序整数

main.cpp

# include <stdio.h>
# include <string.h>
# include <stdlib.h>
 
int main()
{
	int arr[10];
	int front = 0;
	int tail = -1;
	int Num = 123456;
	while (Num)
	{
		arr[++tail] = Num % 10;
		Num /= 10;
	}
	printf("\n逆序后：");
	while (front != tail + 1)
	{
		printf("%d ", arr[front++]);
	}
 
	return 0;
}
 

优先队列

main.cpp

 
# include <stdio.h>
# include <string.h>
# include <stdlib.h>
# define MAX 100
/*
	优先队列：根据优先权去决定你的出队的元素
	队列容量
	优先权--->数字，代表任务量，权重
	按照特殊值去做打印(选择排序)
	算法调度
	短作业优先法
*/
//数据有两部分组成
//数据本身+权值(关键字)
 
struct data
{
	int priority;//权值
	int element;//数据本身
};
//队列
struct priQueue
{
	int sizeQueue;//队列当前元素
	struct data queue[MAX];//队列容量
};
struct priQueue* createQueue()
{
	struct priQueue* myqueue = (struct priQueue*)malloc(sizeof(struct priQueue));
	myqueue->sizeQueue = 0;
	//数组初始化
	memset(myqueue->queue, 0, sizeof(struct data) * MAX);
	return myqueue;
}
//万金油
int empty(struct priQueue* myqueue)
{
	return myqueue->sizeQueue != 0;
}
int size(struct priQueue* myqueue)
{
	return myqueue->sizeQueue;
}
//入队,从文件中读出来，入队
void push(struct priQueue* myqueue,struct data curData)
{
	if (myqueue->sizeQueue == MAX)
	{
		printf("队列满了，无法入队！");
		return;
	}
	else
	{
		myqueue->queue[myqueue->sizeQueue] = curData;
		myqueue->sizeQueue++;
	}
}
//出队
void pop(struct priQueue* myqueue, struct data* popData)
{
	if (myqueue->sizeQueue == 0)
	{
		printf("无法出队，队列为NULL\n");
		return;
	}
	struct data minData;//去找最小权值的数据
	//假设第一个是最小的
	minData = myqueue->queue[0];
	int minIndex = 0;
	for (int i = 1; i < myqueue->sizeQueue; i++)
	{
		//比的是权值
		if (myqueue->queue[i].priority < minData.priority)
		{
			minData = myqueue->queue[i];
			minIndex = i;
		}
	}
	//popData:指针        muqueue->queue[minINdex]:结构体
	*popData = myqueue->queue[minIndex];
	//调整队列，做一个伪删除
	for (int i = minIndex; i < myqueue->sizeQueue; i++)
	{
		myqueue->queue[i] = myqueue->queue[i + 1];
	}
	myqueue->sizeQueue--;
}
 
int main()
{
	struct priQueue* myqueue = createQueue();
	struct data readData;
	FILE* fp = fopen("1.txt", "r");
	if (fp == NULL)
	{
		printf("打开文件失败");
		return 0;
	}
	while(!feof(fp))
	{
		fscanf(fp, "%d %d\n", &readData.element, &readData.priority);
		push(myqueue, readData);
	}
	fclose(fp);
	int workIndex = 1;
	printf("\t序号\t编号\t工作量\n");
	while (empty(myqueue))
	{
		pop(myqueue, &readData);
		printf("\t%d\t%d\t%d\n", workIndex, readData.element, readData.priority);
		workIndex++;
	}
 
 
	return 0;
}
 

线性结构~顺序表

数组结构

顺序表：顺序表的内存，顺序表的索引—>数组下标

main.cpp

 
# include <stdio.h>
# include <string.h>
# include <stdlib.h>
 
struct linerList
{
	char* element;//以存储char类型的数据
	int arrayLength;//顺序表的最大长度
	int listSize;//顺序表当前元素个数
};
//顺序表的创建
struct linerList* createlist(int capacity)
{
	if (capacity < 1)
	{
		printf("创建顺序表失败！\n");
		return NULL;
	}
	else
	{
		struct linerList* list = (struct linerList*)malloc(sizeof(struct linerList));
		list->listSize =0;
		list->arrayLength = capacity;
		list->element = (char*)malloc(sizeof(capacity));
		return list;
	}
}
 
//二维数组的扩充
void changeArray(char** array, int oldLength, int newLength)
{
	if (newLength < 0)
	{
		printf("数组扩充失败\n");
		return;
	}
	int length = oldLength > newLength ? oldLength : newLength;
	*array =(char*)realloc(*array, length * sizeof(char));
}
//移动数组元素
void copyBackward(char* array,int arrayNum,int theIndex)
{
	for (int i = arrayNum; i > theIndex; i--)
	{
		array[i] = array[i - 1];
	}
}
//插入元素
void insertElement(struct linerList* list,int theIndex,int theElement)
{
	//索引无效
	if (theIndex<0 || theIndex>list->listSize)
	{
		printf("索引无效");
		return;
	}
	//插入的索引正好等于数组下标
	if (list->listSize == list->arrayLength)
	{
		//扩展数组
		changeArray(&list->element, list->arrayLength, 2 * list->arrayLength);
		list->arrayLength = 2 * list->arrayLength;
	}
	//储存
	copyBackward(list->element, list->listSize, theIndex);
	list->element[theIndex] = theElement;//在前索引下存储当前元素
	list->listSize++;
 
}
//删除需要把后面的元素往前移
void copyFrontward(char* array, int arrayNum, int theIndex)
{
	for (int i = theIndex; i < arrayNum; i++)
	{
		array[i] = array[i + 1];
	}
}
//删除
void deleList(struct linerList* list,int theIndex)
{
	if (theIndex < 0 || theIndex >= list->listSize)
	{
		printf("无索引，删除失败");
		return;
	}
	else
	{
		copyFrontward(list->element, list->listSize, theIndex);
		list->listSize--;
	}
}
void printList(struct linerList* list)
{
	for (int i = 0; i < list->listSize; i++)
	{
		printf("%c ", list->element[i]);
	}
	printf("\n");
}
int main()
{
	struct linerList* list = createlist(2);
	insertElement(list,0, 'A');
	insertElement(list, 1, 'b');
	insertElement(list, 2, 'K');
	insertElement(list, 2, 'P');
	deleList(list, 0);
	printList(list);
 
 
 
	return 0;
}
 

哈希结构

哈希：数据和地址的一种映射关系

映射关系：数学中的函数关系：哈希构造函数

y(x)=x; 直接地址法

哈希地址：不是指真正意义上的地址（指针），抽象的参照地址

举例：数组中数组下标就可以充当哈希地址

数据1 2 19 11 23

y=x%10;//0~9

哈希冲突：在哈希地址中已经存在元素

处理哈希冲突方案：1.开放地址法2.数组链表的方式

main.cpp

 
# include <stdio.h>
# include <string.h>
# include <stdlib.h>
 
//数组hash
struct pair
{
	int first;//构造一个关键字为构建hash地址做准备
	char second[20];//数据
};
 
struct hashTable
{
	struct pair **table;//为什么初始化二级指针，便于判断为NULL的时候
	int divisor; // y=x%dividor
	int sizeHash;
};
 
struct hashTable* createHash(int divisor)
{
	struct hashTable* hash = (struct hashTable*)malloc(sizeof(struct hashTable));
	hash->divisor=divisor;
	hash->sizeHash = 0;
	hash->table = (struct pair**)malloc(sizeof(struct pair) * hash->divisor);
	//hash->table[divisor]:一级指针
	for (int i = 0; i < divisor; i++)
	{
		hash->table[i] = NULL;
	}
	return hash;
}
//找到正确的地址去做插入
int search(struct hashTable* hash, int first)
{
	int pos = first % (hash->divisor);//value%divisor
	int curPos = pos;
	do
	{
		if (hash->table[curPos] == NULL || hash->table[curPos]->first == first)
		{
			//hash地址中没有元素或者相同键值（first）的元素返回
			return curPos;
		}
		curPos = (curPos + 1) % (hash->divisor);//每一次往后移一位
	} while (curPos != pos);
	return curPos;
}
//哈希插入
void insertHash(struct hashTable* hash, struct pair data)
{
	int pos = search(hash, data.first);
	if (hash->table[pos] == NULL)
	{
		hash->table[pos] = (struct pair*)malloc(sizeof(struct pair));
		memcpy(hash->table[pos], &data, sizeof(struct pair));
	}
	else//冲突处理
	{
		if (hash->table[pos]->first == data.first)
		{
			strcpy(hash->table[pos]->second, data.second);
		}
		else
		{
			printf("表满了，无法插入");
			return;
		}
	}
}
//打印
void printHash(struct hashTable* hash)
{
	for (int i = 0; i < hash->divisor; i++)
	{
		if (hash->table[i] == NULL)
			printf("NULL\n");
		else
			printf("%d %s\t\n", hash->table[i]->first, hash->table[i]->second);
	}
}
int main()
{
	struct hashTable* hash = createHash(10);
	struct pair array[5] = { 1,"循环",11,"信息",9,"上厕所",19,"bscc",10,"试试水" };
	for (int i = 0; i < 5; i++)
	{
		insertHash(hash, array[i]);
	}
	printHash(hash);
	return 0;
}
 

结束语

虽然写了这么多，但是还是有点懵，以后遇到了再回来看看笔记应该可以的，OK，搞下一个