数据结构—总结
没写完
1.线性表
顺序表
typedef int ElemenType;
typedef struct {
ElemenType *data; // 数据域
int length;
}Node;
// 顺序表初始化
void InitNode(Node *t){
t->data = (Node *)malloc(sizeof(Node) * 100);
if(t->data == NULL)
exit(0);
t->length = 0;
}
单链表
/**
出现过一个概念，头结点，而且单链表是以结点的形式存在的，所有我们操作单链表时，其实也实在操作我们的结点
所有每一次才都需要一个结点
*/
typedef int ElemenType;
typedef struct {
ElemenType data;
struct LNode * next;
}LNode,*LinkList;
// 单链表需要初始化头结点
void InitLNode(LinkList *t){
t = (LNode *)malloc(LNode);
(*t)->next = NULL;
}
// 创造单链表
void CreateLNode(LinkList *t){
int n = 0;
LinkList p;
// 单链表的长度 理清楚结点还有各种指针之间的变化
scanf("%d",&n);
for(int i = 0; i < n; i++){
p = (LNode *)malloc(LNode);
scanf("%d",&p->data);
p->next = (*t)->next;
(*t)->next = p;
}
}
// 插入与删除
双向链表
typedef int ElemenType;
typedef struct {
ElemenType data; // 数据域
struct DuLNode * prior; // 前指针
struct DuLNode * next; // 后指针
}DuLNode,*DuLinkList;
循环链表
2.栈
顺序栈
// 定义一个栈
#define MAXSIZE 100
typedef char ELemenType;
typedef struct{
ElemenType * top; // 头指针
ElemenType * base; // 尾指针
int stacksize; // 栈可用最大容量
}SqStack;
// 重要条件 判断栈空与栈满
// 初始化
void InitStack(SqStack * s){
s.base = (SqStack *)malloc(sizeof(SqStack)*MAXSIZE);
if(!s.base){
exit(0);
}
s.top = s.base; // 空栈
s.stacksize = MAXSIZE;
}
// 入栈 当栈未满时就可以入栈
void Push(SqStack *s,ElemenType e){
if(s.top - s.base == s.stacksize) exit(0);
s.top++=e;
}
// 出栈 当栈未空时出栈
void Pop(SqStack *s,ElemenType e){
if(s.top == s.base) exit(0);
e=*--s.top;
}
链栈
// 链栈
typedef char ElemenType;
typedef struct {
ElemenType data; // 数据域
struct StackNode * next; // 指针域
}StackNode,*LinkStack;
// 初始化
void InitSqstack(LinkStack *s){
s = NULL; // 创建一个空栈s,栈顶指针为空，
}
// 入栈
void Push(LinkStack *s,ElemenType e){
StackNode p = (StackNode *)malloc(sizeof(StackNode));
p->data = e;
p->next = s;
s = p;
}
// 出栈
void Pop(LinkStack *s,ElemenType *e){
if(s == NULL) exit(0);
e = s->data;
p = s;
s = s->next;
delete p;
}
3.队列
循环队列
#define MAXSIZE 100
typedef char ElemenType;
typedef struct {
ElemenType * base; // 存储空间的基地址
int front; // 队头指针
int rear; // 队尾指针
}SqQueue;
/**
使用一种方式来实现循环队列
队空 : Q.front == Q.rear;
队满 : (Q.rear + 1)%MAXSIZE == Q.front;
*/
// 初始化
void InitQueue(SqQueue *q){
q.base = (SqQueue *)malloc(sizeof(SqQueue)*MAXSIZE);
if(!q.base) exit(0);
q.front = q.rear = 0; // 队头队尾置为0，队列为空
}
// 入队 入队要判断是不是满队
void EnQueue(SqQueue *q,ElemenType e){
if((q.rear + 1)%MAXSIZE == q.front)
exit(0);
q.base[q.rear] = e;
q.rear = (q.rear + 1)% MAXSIZE;
}
// 出队 出队要看是不是空队
void DeQueue(SqQueue *q,ElemenType *e){
if(q.front == q.rear) exit(0);
e = q.base[q.front];
q.front = (q.front + 1)%MAXSIZE;
}
链队
typedef char ElemenType;
typedef struct{
ElemenType data;
struct QNode * next;
}QNode,*QueuePtr;
typedef struct {
QueuePtr front; // 队头指针
QueuePtr read; // 队尾指针
}LinkQueue;
4.串，数组，广义表
串
串(string)(或字符串)是由零个或多个字符组成的有限序列，一般记为 s = “a1a2a3…….an”(n>=0) 其中，s是串的名，用双引号括起来的字符序列是串的值；ai(1<=i<=n)可以是字母，数字或其他符号；串中的字符的数目n称为串的长度，零个字符的串称为空串(null string) ，其长度为零。
串中任意个连续的字符组成的子序列称为该串的子串，包含字串的串相应的称为主串。通常称字符在序列中的序号为该字符在串中的位置。字串在主串中的位置则以字串的第一个字符在主串中的位置来表示。
// ------ 串的定长顺序存储结构 ----
#define MAXLEN 255 // 串的最大长度
typedef struct {
char ch[MAXLEN + 1]; // 存储串的一维数组
int length; // 串的当前长度
}SString;
// ------ 串的堆式顺序存储结构 ----
typedef struct{
char *ch; // 若是非空串，则按串长分配存储区，否则ch为NULL
int length; // 串的当前长度
}HString;
// ------ 串的链式存储结构 -------
#define CHUNKSIZE 80 // 可由用户定义的块的大小
typedef struct Chunk{
char ch [CHUNKSIZE];
struct Chunk *next;
}Chunk;
typedef struct{
Chunk *head,*tail; // 串的头和尾指针
int length; // 串的当前长度
}LString;
串中两种重要算法 BF KMP 算法
// ----- BF (Brute-Force)算法 ---------
/*
【概述】
模式匹配不一定是从主串的第一个位置开始，可以指定主串中查找的起始位置pos.如果采用字符串顺序存储结构，
可以写出不依赖于其他串操作的匹配算法
【算法步骤】
1.分别利用计数指针i和j指示主串S和模式T中当前正待比较的字符位置，i初始化pos,j初值为1.
2.如果两个串均未比较到串尾，即i和j分别指示串中下个位置，继续比较后续字符；
2.1 S.ch[i] 和 T.ch[j] 比较，若相等，则i和j分别知识串中下个位置，继续比较后续字符；
2.1 若不等，指针后退重新开始匹配，从主串的下一个字符(i=i-j+2)起再重新和模式的第一个字符(j=1)比较
3.如果j>T.length,说明模式T中的每个字符串依次和主串S中的一个连续字符序列相等，则匹配成功返回和模式T中第一个字符相等的字符串在主串S中的序号(i-T.length);否则称匹配不成功，返回0。
*/
//【算法描述】
int Index_BF(SString S,SString T,int pos){
// 返回模式T在主串S中第pos个字符开始第一次出现的位置
// 其中，T非空，1 <= pos <= S.length;
int i,j;
i = pos; j = 1; // 初始化
while(i <= S.length && j <= T.length){ // 两个串均为比较到串尾
if(S[i].ch == T[j].ch){ // 继续比较后继字符
++i;
++j;
}
else { // 指针后退重新开始匹配
i = i - j + 2;
j = 1
}
}
if(j>T.length) // 匹配成功
return i - T.length;
else
return 0; // 匹配失败
}
// ----- KMP 算法 ---------
// 【算法描述】
int Index_KMP(SString S,SString T,int pos){
// 利用模式串T的next函数求T在主串S中第pos个字符之后的位置
// 其中，T非空，1 <= pos <= S.length
i = pos, j = 1;
while(i <= S.length && j <= S.length){
if(i == 0 || S[i] == T[j]){
++i;
++j;
}else {
j = next[j];
}
}
if(j > T[0])
return i - T[0];
else return 0;
}
// 计算next函数值
void get_next(SString T,int next[]){
//求模式串T的next函数值并存入数组next
i = 1;
next[1] = 0;
j = 0;
while(i < T.length){
if(j == 0 || T.ch[i]){
++i;
++j;
next[i] = j;
}else {
j = next[j];
}
}
}
// next函数的修订值
void get_nextval(SString T, int nextval[]){
i = 1;
nextval[1] = 0;
j = 0;
while(i < T.length){
if(j == 0 || T.ch[i] == T.ch[j]){
++i;
++j;
if(T.ch[i] != T.ch[j])
nextval[i] = j;
else
nextval[i] = nextval[j];
}else {
j = nextval[j];
}
}
}
数组
数据是由类型相同的数据元素构成的有序集合，每个元素称为数组元素，每个元素受n(n >= 1)个线性关系的约束，每个元素在n个线性关系中的序号i1,i2,…….in称为该元素的下标，可以通过下标访问该数组元素。因为数组中每个元素处于n(n >= 1) 个关系中，故称该数组为n维数组。
广义表
广义表是线性表的推广，也称为列表。广泛用于人工智能等领域的表处理语言LISP语言，吧广义表作为基本的数据结构，就连程序也表示为一系列的广义表
//—————————广义表的头尾链表存储表示————————————
typedef 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.hp和ptr.tp分别指向表头和表尾
}ptr;
};
}*GList; // 广义表类型
5.树和二叉树
树（Tree）是n个结点的有限集，它或为空树；或为非空树，对于非空树T;
1) 有且有一个称之为根的结点
2）除根结点以外的其余节点可分为m个互不相交的有限集T1,T2,……Tm,其中每一个集合本身又是一颗树，并且呈为根的字数（Sub Tree）
//--------二叉树的顺序存储结构--------
#define MAXTSiZE 100
typedef TElemType SqBiTree[MAXTSIZE];
SqBiTree bt;
/*
顺序存储就跟数组存储差不多
*/
//--------二叉树的链式存储结构--------
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//--------二叉树的二叉线索存储结构--------
typedef struct BiThrNode{
TElemType data;
struct BiThrNode *lchild,*rchild;
int LTag,RTag;
}BiThrNode,*BiThrTree;
//--------树的二叉链表（孩子-兄弟）存储表示-
typedef struct CSNode{
ElemType data;
struct CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;
//--------哈夫曼存储结构--------
typedef struct {
int weight;
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
6.图
图G由两个集合V和E组成，记为G=(V,E),其中v是顶点的有穷非空集合，E是V中定点偶对的有穷集合，这些顶点偶对边称为边，V为点集，E为边集
//--------图的邻接矩阵存储结构--------
#define MaxInt 32767
#define MVNum 100
typedef char VerTexType;
typedef int ArcType;
typedef struct{
VerTexType vexs[MVNum];
ArcType arcs[MVNum][MVNum];
int vexnum,arcnum;
}AMGraph;
//--------图的邻接表存储结构--------
#define MVNum 100
typedef struct ArcNode;
{
int adjvex;
struct ArcNode * nextarc;
Otherinfo info;
}ArcNode;
typedef struct VNode{
VerTexType data;
ArcNode *firstarc;
}VNode,AdjList[MVNum];
typedef struct{
AdjList vertices;
int vexnum,arcnum;
}ALGraph;
//-------有向图的十字链表存储表示存储结构--------
#define MAX_VERTEX_NUM 20
typedef struct ArcBox{
int tailvex,headvex;
struct ArcBox *hlink,*tlink;
infoType *info;
}ArcBox;
typedef struct VexNode{
VextexType data;
ArcBox *firstin,*firstout;
}VexNode;
typedef struct {
VexNode xlist[MAX_VERTEX_NUM];
int vexnum,arcnum;
}OLGraph;
//--------无向图的邻接多重表存储结构--------
#define MAX_VERTEX_NUM 20
typedef enum{unisited,visited} Visitlf;
typedef struct EBox{
Visitlf mark;
int ivex,jvex;
struct EBox *ilink,*jlink;
infoType *info;
}EBox;
typedef struct VexBox {
VertexType data;
EBox *firstedge;
}VexBox;
typedef struct {
VexBox adjmulist[MAX_VERTEX_NUM];
int vexnum,edgenum;
}AMLGraph;
7.查找
查找方法：
- 线性表查找
- 顺序查找
- 折半查找
- 分块查找
- 树表查找
- 二叉排序树
- 平衡二叉树
- B-树
- B+树
- 散列表查找
8.排序
查找方法：
- 内部排序法
- 插入类：直接插入排序，折半插入排序，希尔排序
- 交换类：冒泡排序，快速排序
- 选择类：简单选择排序，树形选择排序，堆排序
- 归并类：2-路归并排序
- 分配类：基数排序
- 外部排序法
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/278853.html