【笔记】数据结构—

@toc

静态链表

静态链表的存储结构

#define maxn 15struct space
{int cur;int key; 
}s[maxn];int LocateElem_SL(SLinkList *s,ElemType e)
{//在静态链表中查找第一个值为e的元素//若找到，则返回它在链表中的位置，否则返回0 i=s[0].cur;while(i&&s[i].data!=e)i=s[i].cur;return i;
}

集合(A-B)∪(B-A)

#include<stdio.h>#define MAXSIZE 15struct space
{int cur;int key; 
}s[MAXSIZE];void InitSpace_SL(struct space *s)
{
//space[cur]为头指针，0表示空指针
//space中各分量链成一个备用链表
//s[0].cur为头指针int i;for(i=0;i<MAXSIZE-1;i++)s[i].cur=i+1; s[MAXSIZE-1].cur=0;
}int Malloc_SL(struct space *s)
{
//分配空间，若备用空间链表非空，返回分配的节点下标int	i=s[0].cur;if(i)s[0].cur=s[i].cur;return i;
} void free_SL(struct space *s,int k)//将下标为k的空闲节点回收到备用链表 
{s[k].cur=s[0].cur;s[0].cur=k;
}void PrintSpace_SL(struct space *s)
{int i;for(i=s[1].cur;i!=0;i=s[i].cur)//第一个里面不存东西 printf("%d ",s[i].key);printf("\n");
}void different(struct space *s)
{InitSpace_SL(s);int head=Malloc_SL(s);int last=head;int i,j,k;int m,n;scanf("%d%d",&m,&n);//输入集合A和集合B的元素的个数for(j=1;j<=m;j++)//建立集合A的链表 {i=Malloc_SL(s);//分配节点 scanf("%d",&s[i].key);s[last].cur=i;//插入表尾 last=i; } s[last].cur=0;//尾结点的指针为空//PrintSpace_SL(s);int b;for(j=1;j<=n;j++){//依次输入B的元素，若不在当前表中，则插入，否则删除scanf("%d",&b);int p=head;k=s[head].cur;//k指向集合A中的第一个结点。while(k&&s[k].key!=b)//在当前表中查找{p=k;k=s[k].cur;}if(k==space[last].cur)//当前表中不存在该元素，插入last所在节点之后，且last的位置不变{i=Malloc_SL(s);s[i].key=b;s[i].cur=0;s[last].cur=i;last=i;}else{s[p].cur=s[k].cur;free_SL(s,k);if(last==k)r=p;//如果删除的是last所指向的结点，则需修改为节点。}} 
}int main()
{different(s);PrintSpace_SL(s);return 0;
}

在终端输入集合元素，先建立表示集合A的静态链表S，然后输入集合B的元素，同时查找S表。若存在和B相同的元素，则从S表中删除，否则将此元素插入S中。

代码参考了社区的da1234cao

栈

行编辑程序

接受用户从终端输入的程序或数据，并存入用户的数据区。由于用户在终端上输入的时，不能保证不出差错。

“每接收一个字符即存入用户数据区”的做法显然不是最恰当的。
较好的做法是设立一个输入缓冲区，接收一行的字符，逐行存入用户数据区。当用户发现刚刚键入一个字符是错的，可以补进一个退格符“#”表示前一个字符无效。同样的退行符“@”
【使用栈进行判别的方法】

void LineEdit(){
//利用字符栈S，从终端接受一行并传送至调用过程的数据区。
InitStack(S);
ch=getchar();while(ch!=EOF){while(ch!=EOF&&ch!='\n'){switch(ch){case '#':Pop(S,c);break;//仅当非空栈的退栈case '@':ClearStack(S);break;//重置S为空栈default: Push(S,ch);break;//有效字符进栈，未考虑栈满情形}ch=getchar();//接收下一个字符	}//将从栈底到栈顶的栈内字符传送至调用过程的数据区ClearStack(S);if(ch!=EOF)ch=getchar();}DestroyStack(S);
}//LineEdit

迷宫求解

求迷宫中从入口到出口的所有路径，从入口，顺着某一方向能走通则继续前进，否则沿原路返回，换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，需要用到栈。
栈+回溯法
在这里插入图片描述

2.方向的定义
可以根据迷宫的入口和出口大致方向去决定优先方向，这里的迷宫入口在出口的西北方向，那么优先的方向我依次为东、南、西、北，也就是说优先往东走，其次是南、西、北。方向的移动可以根据当前坐标进行上下左右的移动，只需要去定义一个方向数组，然后加上这个数组的方向即可。
在这里插入图片描述

int maze[6][6] = {{1,1,1,1,1,1},{1,0,0,1,1,1},{1,0,0,0,0,0},{1,0,1,1,1,0},{1,0,0,0,0,1},{1,1,1,1,1,1}};//试探方向存储结构
typedef struct {int xx, yy;
}Direction;
//东南西北
Direction dire[4] = { {0,1},{1,0},{0,-1},{-1,0} };

走迷宫代码

走迷宫的代码逻辑
**参考严蔚敏的《数据结构》

设当前位置的初值为[入口位置]；
do{if(当前位置可通){将当前位置cur插入栈顶；//纳入路径if(当前位置是[出口位置])，则结束；//求得路径存放在栈中else 切换当前位置的东邻方块为新的当前位置}else{if(栈不空且栈顶位置尚有其他方向未探索) 设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块//endifif(栈不空但栈顶位置的四周均不可通){删去栈顶位置；if(栈不空)，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空}//endif}//endelse
}（栈不空）

#include<stdio.h>
#include<assert.h>
#include"stack.h"//试探方向存储结构
typedef struct {int xx, yy;
}Direction;
//东南西北
Direction dire[4] = { {0,1},{1,0},{0,-1},{-1,0} };//判断能不能走出去,路径放入到了栈里面去//⭐⭐⭐重点代码
bool Findpath(int maze[][6],Stack* stack ,Direction dir[],int startx,int starty,int endx,int endy) {//startx,starty是起点的坐标;endx、endy是终点的坐标.assert(stack);int x, y, di;int line, col;//初始化maze[startx][starty] = -1;ElemType start = { startx,starty,-1 };push(stack, start);while (!isEmpty(stack)) {Node* po = pop(stack);ElemType temp = po->data;x = temp.x;y = temp.y;di = temp.di++;//使得栈储存了一条通路while (di < 4) {line = x + dire[di].xx;col = y + dire[di].yy;if (maze[line][col] == 0) {//储存上一个节点的位置，入栈temp = { x,y,di };push(stack, temp);x = line;y = col;maze[line][col] = -1;if (x == endx && y == endy) {//把终点的位置入栈temp = { x,y,-1 };push(stack, temp);return true;}elsedi = 0;}elsedi++;}}return false;
}int main() {int maze[6][6] = {{1,1,1,1,1,1},{1,0,0,1,1,1},{1,0,0,0,0,0},{1,0,1,1,1,0},{1,0,0,0,0,1},{1,1,1,1,1,1}};Stack stack;stack_init(&stack);printf("能否出去：%d\n", Findpath(maze, &stack, dire, 1, 1, 4, 4));show_path(stack.point);//输出遍历的结果
}

栈的cpp代码：

#include<stdio.h>
#include<stdlib.h>//数据类型
typedef struct datatype {int x, y, di;
}ElemType;
//节点
typedef struct node {ElemType data;struct node* next;
}Node;
//栈顶指示
typedef struct stack {int count;	//计数Node* point;
}Stack;//创建节点
Node* create_node(ElemType data) {Node* new_node = (Node*)malloc(sizeof(Node));if (new_node) {new_node->data = data;new_node->next = NULL;return new_node;}else{printf("ERROR\n");}
}//初始化
void stack_init(Stack* top) {top->count = 0;top->point = NULL;
}int isEmpty(Stack* top) {if (top->count == 0) {return 1;}return 0;
}//入栈
void push(Stack* top, ElemType data) {Node* new_node = create_node(data);if (new_node) {top->count++;if (top->count == 1) {//如果入栈是第一个节点的话top->point = new_node;}else{new_node->next = top->point;top->point = new_node;}}elsereturn;
}//出栈
Node* pop(Stack* top) {Node* pop_node = NULL;if (!isEmpty(top)) {pop_node = top->point;top->point = pop_node->next;top->count--;}return pop_node;
}//递归输出路径
void show_path(Node* node) {if (!node)return;show_path(node->next);printf("(%d,%d)\n", node->data.x, node->data.y);
}

栈的头文件h代码

#pragma once
//链表栈
//数据类型
typedef struct datatype {int x, y, di;
}ElemType;
//节点
typedef struct node {ElemType data;struct node* next;
}Node;
//栈顶指示
typedef struct stack {int count;	//计数Node* point;
}Stack;void stack_init(Stack* top);
int isEmpty(Stack* top);
void push(Stack* top, ElemType data);
Node* pop(Stack* top);
void show_path(Node* node);

部分文字参考
Fitz&

递归

递归的数学函数
拥有递归特性的数据结构：二叉树，广义表
可递归求解的问题：八皇后 hanoi塔

被调用函数和调用函数的栈关系

【信息传递】和【控制转移】都通过栈进行
系统将整个程序运行时所需的【数据空间】都安排在栈中
当前运行程序数据区在【栈顶】

运行被调用函数之前，系统需要完成3件事
A调用B
A:调用函数
B:被调用函数
1）将所有的实在参数、返回地址等信息传递给被调用函数保存
2）为被调用函数的局部变量分配存储区
3）将控制转移到被调函数的入口。
而从被调用函数返回调用函数之前完成3件事情。
1）保存被调用函数的计算结果
2）释放被调用函数的数据区
3）依照被调用函数保存的返回地址将控制转移到调用函数

队列

队头队尾

操作系统作业排队
运行结果都需要通过通道输出，就要按请求输出的先后次序排序
通道传输完毕可以接受新的输出任务，队头作业先从队列中退出作输出操作。申请输出的作业都从队尾进入队列。

链队列

插入和删除需要修改尾指针和头指针
一般删除队列头元素，仅需修改队头结点的指针，但【删除最后一个元素】的时候，队列尾指针需要重新赋值指向头结点。

队列尾指针指向队列尾元素的下一个位置【是空的】
单纯的带尾指针的单链表/循环链表尾指针指向最后一个结点。【不空】

[循环队列]两种判空和判满的方法

另设一个标志位区别队列空还是满
少用一个元素空间约定以“队列头指针在队列尾指针的下一位置”作文队列呈满的状态

串

串的定长顺序存储表示

#define MAXSTRLEN 255
typedef unsigned char SString[MAXSTRLEN+1]

串的长度表示
- 0的数组分量存放串的实际长度
- 串值后面加上一个不计入串长的结束标志“\0”

串的堆存储表示
动态分配串的大小，且具有顺序存储的特点

typedef struct{
char *ch;
int length;
}
⭐
T.ch = (char*)malloc((s1.length+s2.length)*sizeof(char))
free(T.ch)

串的块链存储表示[存储占用量大]

typedef struct Chunk{
char ch[CHUNKSIZE];
struct Chunk *next;
}Chunk;
typedef struct{Chunk *head,*tail;int curlen;
}LString;

串操作实例

文本编辑
实质是修改字符数据的形式或格式，串的查找删除插入
用户可以利用换行符和换页符将文本划分成若干页，每页有若干行
文本看成一个字符串，页是文本串的子串，行是页的子串

需要建立行表和页表
行号/页号，起始地址，长度

建立词索引表
书名关键字索引，折半查找，顺序混出
索引项：关键词，书号索引

数组和广义表

稀疏矩阵
广义表
通常采用链式存储结构，列表中的数据元素可能为原子或列表
需要两种结构的节点：表结点原子节点

typdef enum{ATOM,LIST}ElemTag;//ATOM=0 原子，LIST=1:子表
typedef struct GLNode{ElemTag tag;//公共部分，用于区分原子和列表union{AtomType atom;//atom是原子结点的值域，AtomType由用户定义struct{struct GLNode *hp,*tp;}ptr ;//ptr表结点的指针域，ptr.hp ptr.tp//ptr.hp可能指向原子节点或表结点//ptr.tp指向列表表尾，除非表尾为空，则指针空，否则必为表节点。}}*GList;

另一种表示方法

typdef enum{ATOM,LIST}ElemTag;//ATOM=0 原子，LIST=1:子表
typedef struct GLNode{ElemTag tag;//公共部分，用于区分原子和列表union{AtomType atom;//atom是原子结点的值域，AtomType由用户定义struct GLNode *hp;}struct GLNODE *tp;//相当于线性链表的下一个元素节点
}*GList;