数据结构从头开始
最近在重新学习数据结构与算法，对于常见的数据结构用c实现了一下，记性不好，我估计可能等不到这本书复习完我就忘了，所以整理到这方便用ipad复习，同时也记录一下过程中的一些想法、思路和笔记。
第一章 线性表第一章讲的逻辑结构是——线性表。这一章分为顺序表和链表两块，分别对应了线性表的顺序实现与链式实现。在严老师的数据结构教材中，采用了一下一些类C++的语法，所以如果要实现课本中的代码，要把代码文件的后缀改成".cpp",不然是无法通过编译的。
1.1顺序表顺序表风两种：静态分配和动态分配
静态分配：就是开辟一片固定大小的内存空间用来存数据，这片空间的大小一旦分配就不能再改变了，所以一般我们采用数组实现顺序表的静态分配。
**动态分配:**也是开辟一片连续的内存空间来存放数据同时定义一个指针指向这片区域的首地址（对于后续的地址的访问也可以通过指针实现，也就是指针的偏移），不同的是当这片空间的大小不够用的时候它可以重新开辟一片更大的空间去存放这些数据并把原来的空间给释放掉,从而实现扩容的效果（但实际上他这种效果用时间换空间，时间复杂度很高，所以这种方式并不理想）。
一般情况下，我们对于顺序表都采用静态分配，对于动态分配有所了解就好。
1.1.1静态实现（理解）思路：我们首先定义一个定义了数组和表长的结构体，用静态的数组来存放顺序表的元素用表长来记录长度方便操作。
#include #define MaxSize 10 //事先定义了数组最大长度属于是静态分配了 typedef struct{ //这个结构体的大小为max+1：数组长度再加上一个lengthint data[MaxSize];//用静态数组存放元素 int length; //顺序表的当前长度}SqList;//————————————————————关于操作的定义———————————————————————— //操作1：初始化一个顺序表 void InitList(SqList &L){//把&写道形参的位置是c++的语法，称为引用，这个时候操作L和主函数里边使用L等价的 /*for(int i=0;i=MaxSize) {return false;//判断：存满了 则返回false }for(int j=L.length;j>=i;j--){//依次后移 L.data[j] =L.data[j-1];}L.data[i-1]=e;L.length++; return true;}//操作3：删除一个元素并且返回删除的值 bool ListDelete(SqList L,int i,int &e) {//e是引用形变量，引用了我们自己定义的全局变量，如果没有&符号//那么函数就会在内部定义局部变量，改变也是改变的局部变量的值也就带不回来了 if(iL.length) return false;//删除的范围也就是元素的范围 e=L.data[i-1];//第i个位置对应数组的i-1号下标for(int j=i;jnext=NULL;return L;} //操作3：头插法建立单链表逆置 ！LinkList List_HeadInsert(LinkList &L){LNode *s;//s为要插入的新节点 int x;L=(LinkList)malloc(sizeof(LNode));L->next=NULL;scanf("%d",&x);while(x!=9999){s=(LNode *)malloc(sizeof(LNode));s->data=x;s->next=L->next;L->next=s;scanf("%d",&x);//逆置时逻辑不变，但是取值不是scanf而是用指针循环扫描遍历出所有元素，再用头插法插入进链表 }return L;}//操作4：前插和后插操作bool InsertNextNode(LNode *p,int e){if (p=NULL) return false;//??????????????????????????配合查找函数使用 LNode *s =(LNode *)malloc(sizeof(LNode));//if(s==NULL)return false;内存分配失败 s->data;s->next=p->next;p->next=s;return true;} //前插操作//1.bool InsertPriorNode(LinkList L,LNOde *p,int e) 传入头指针 时间复杂度为n//2.偷天换日 bool InsertPriorNode(LNode *p,int e){if (p==NULL) return false;LNode *s=(LNode *)malloc(sizeof(LNode));//if (s==NULL)return false;s->next=p->next;p->next=s;s->data=p->data;p->data=e;} //操作5：按位查找LNode *GetElem(LinkList L,int i){if(inext;//从第一个结点(也就是头节点的下一个节点)开始查找数据域为e的节点while(p!=NULL&&p->data != e)p=p->next;return p; //找到后返回该节点指针，否则返回null }//操作7：求表长int length(LinkList L){int len=0;LNode *p=L;while (p->next!=NULL){p=p->next;len++;}return len++;} //思路： /* 先判断位置是否合法，如果不合法直接返回false 如果合法，就定义一个指针指向头节点，定义一个计数器记录这个节点目前指向的位置 使用while找到插入节点的前一个位置即第i-1个位置，让新指针指向这个位置，这一步while要判断位置是否合法若next指向null则不合法返回false 然后开辟节点，修改指针指向，注意先顺序。 */ //操作8：插入（封装一下查找和后插《找到插入位置的前一个节点进行后插） bool ListInsert(LinkList L,int i,int e){LNode *p=GetElem(L,i-1); //找到第i-1个节点 /*if(idata=e;s->next=p->next;p->next=s;return true;*/}//操作10：按位删除(修改前驱节点的next指针+释放资源)bool ListDelete(LinkList &L,int i,int &e){//--------------------------------------if(inext==NULL)return false;//第i-1个之后已无其他节点LNode *q=p->next;e=q->data;p->next=q->next; free(q);return true; } //操作11：删除指定的节点(偷天换日)bool ListDelete (LNode *p){if(p==NULL)return false;LNode *q=p->next;p->data=p->next->data;//存在bug，如果要删除的是最后一个节点就会出错，因为最后一个节点的next是null此时会报空指针的错误，此时只能用传入头节点的方法来解决问题 p->next=q->next;//体现了单链表的局限性，无法逆向检索，只能顺着找后面的不能反着找前面的 free(q);return true;}//操作12：遍历链表 void PrintList(LinkList L) { L=L->next;//使头指针指向第一个数据节点while(L!=NULL){ printf("%d",L->data); L=L->next; } }int main(){LinkList L;List_HeadInsert(L); //List_TailInsert(L); PrintList(L);} 1.2.2不带头结点的单链表（了解） #include #include typedef struct LNode{int data;struct LNode *next;}LNode, *LinkList; //LNode 是指结构体= typedef struct LNode LNode； //*LinkList是指向LNode的指针 =typedef struct LNode *LinkList； //操作一：初始化 bool InitList(LinkList L){L=NULL;//这里的初始化是防止内存中有脏数据指向的下一节点就是存放数据的节点 return true;}//操作二：判空 bool Empty(LinkList L){return (L==NULL);} bool ListInsert(LinkList &L,int i,int e){if(idata=e;s->next=L;L=s;//头指针指向新节点 return true; }LNode *p;//指针p指向当前扫描到的节点 int j=1;//当前p指向的是第一个节点（没有头节点） p=L;while (p!=NULL&& jnext;j++;}if (p==NULL)return false;LNode *s=(LNode *)malloc (sizeof(LNode));s->data =e;s->next =p->next;p->next=s;return true;} int main(){LinkList L;//在这里只是定义了头节点，此处并没有创建一个节点 ，他只是一个指针并不是一个节点 InitList(L);ListInsert(L,1,1);}1.2.3双链表几个点： 1.双向链表的头结点的前向指针永远指向null 2.在查找操作上与单链表相同，在插入和删除操作上不同
静态链表：分配一整片连续空间，各个节点集中安置 。静态链表的每个节点包含两块，数据元素和下一个节点的数组下标（游标）。
1.数组为零的节点充当头节点不存放数据元素。 2.最后一个节点的游标为-1。 3.可以用一个特殊的数值表示空闲的节点，如：-2.
就是用数组实现的单链表；
优点：增删不需要移动大量元素 缺点：不支持随机存取；容量固定。 使用场景:不支持指针的低级语言；数据元素固定不变；
顺序表与链表的对比顺序表： 优点：1.支持随机存取、存储密度高 缺点：大片连续空间分配起来不方便，改变容量也不方便 使用场景：表长固定，查询操作多 链表： 优点：修改方便 缺点：存取密度低，不支持随机存取 使用场景：表长难以估计，增删操作多
第二章 栈和队列 2.1栈的实现栈就是操作受限的线性表，栈式是线性表的特殊化。
2.1.1顺序栈采用静态数组实现
//创销判空求表长增删改查 #include #include#define MaxSize 10typedef struct SqStack{int data[MaxSize];int top;//栈顶指针 记录的是数组的下标，从零开始 }SqStack;//初始化 void InitStack(SqStack &S){S.top=-1;}//销毁 bool DestoryStack(SqStack &S){S.top=-1;}//判空 bool StackEmpty(SqStack &S){if (S.top==-1)return true;else return false;} //求表长 int GetLength(SqStack &S){return S.top+1;}//增：进栈 bool Push(SqStack &S,int x){if(S.top==MaxSize-1)return false;S.top=S.top+1;//先加一再赋值 S.data[S.top]=x;//S.data[++S.top]=x return true;} //删：出栈 bool Pop(SqStack &S,int &a){if(S.top==-1)return false;a=S.data[S.top--];//先取值再下移指针，只是在逻辑上删除了元素但数据仍残留在内存中 return true;}//改查：读取栈bool GetTop(SqStack &S,int &y){if(S.top==-1)return false;y=S.data[S.top];return true;}int main(){SqStack S;InitStack(S);int a;//接收数据 int b;//接受栈顶元素 Push(S,0);Push(S,1);Push(S,2);Push(S,3);Push(S,4);Push(S,5);Push(S,6); a=GetLength(S); GetTop(S,b);printf("%d\n",a);printf("%d",b);} 2.1.2共享栈由于顺序栈采用静态数组实现，空间是一次开辟完成。为了正常使用通常会开辟一大块空间，但这样有时候会造成资源浪费，所以就出现了共享栈。共享栈相当于是两个栈共用一片存储空间，两端分别是栈顶，存储空间的中段是两个栈的栈底。
#define MaxSize 10typedef struct{int data[1000];int top0;int top1;}SHStack;void InitStack(ShStack &S){S.top0=-1;S.top1=MaxSize;}栈满条件：top0+1==top1
2.1.3 链栈’‘’ 链栈本质上就是限制在头部进行插入和删除操作的单链表 ‘’‘
//链栈本质上就是限制在头部进行插入和删除操作的单链表#include #includetypedef struct StackNode{int data;struct StackNode *next;}*LinkStack;//-------------------------此处实现不带头结点的版本----------------------------------------- //初始化 bool InitStack(LinkStack &S){ S=NULL; return true;}//销毁 bool DestoryStack(LinkStack &S){S=NULL;}//判空 bool StackEmpty(LinkStack &S){return (S==NULL); } //增：进栈 bool Push(LinkStack &S,int x){StackNode *s = (StackNode *)malloc (sizeof(StackNode));//开辟一个新的节点先存数据在插到链中 s->data=x;s->next=S;S=s; return true; } //删：出栈 bool Pop(LinkStack &S,int &a){if(S==NULL) return false;LinkStack p=NULL;a=S->data;p=S;S=S->next;free(p);return true;}//改查：读取栈int GetTop(LinkStack &S,int &y){if(S==NULL)return -1;y=S->data;return y;} //遍历栈 void PopStack(LinkStack &S){LinkStack P;P=S;while(P!=NULL){printf("%d\n",P->data);P=P->next;}}int main(){LinkStack S;InitStack(S);int a;//接收数据 int b;//接受栈顶元素 Push(S,0);Push(S,1);Push(S,2);Push(S,3);Push(S,4);Push(S,5);Push(S,6);// b=GetTop(S,a);//printf("%d\n",b);PopStack(S);}2022.1.26
2.2 队列的实现 2.2.1队列的顺序实现——循环队列 #include #include #define MaxSize 100//创销增删改查typedef struct {int data[MaxSize];int front,rear;//队头指向队头元素 队尾指针指向队尾元素的后一个位置也即是下一个元素的插入位置 }SqQueue;//初始化 void InitQueue(SqQueue &Q){ Q.front=Q.rear=0; //让队头队尾指针都指向数组的第一个位置 } //入栈 bool EnQueue(SqQueue &Q,int x){if((Q.rear+1)%MaxSize==Q.front) return false;Q.data[Q.rear]=x;Q.rear=(Q.rear+1)%MaxSize;return true; }//出队 bool DeQueue(SqQueue Q,int &x){if((Q.rear+1)%MaxSize==Q.front) return false;x =Q.data[Q.front];Q.front++;return true; }//遍历出队int PopQueue(SqQueue &Q) {int j=0;//计数器for(int i=Q.front;i!=Q.rear;i=(i+1)%MaxSize){printf("%d->",Q.data[i]);}printf("出队完成！\n");return j;}//获取队头 int GetHead(SqQueue Q){if(Q.rear!=Q.front) return Q.data[Q.front];}//判空bool QueueEmpty(SqQueue Q){return (Q.rear==Q.front);} int main(){SqQueue Q;EnQueue(Q,11);EnQueue(Q,22);EnQueue(Q,33);EnQueue(Q,44);EnQueue(Q,55);//int a=GetHead(Q);//printf("%d",a);int a=-1;DeQueue(Q,a);DeQueue(Q,a);DeQueue(Q,a);//printf("%d",a);PopQueue(Q); }注：
取模构成循环队列的原因是解决队头指针出队后上移动导致前面空出无法入队的空间造成假溢出的问题由于队空队满时候的判断条件相同，所以为了区别他们两个的状态我们有以下三种方法， 一、设置状态记录位当满时为1非满时候为0 二、设置队长记录位 三、空出一位不写入数据 【条件：队尾指针的下一个位置是队头即（Q.rear+1）%MaxSize==Q.front）】 3.计算队列中元素的个数：（rear+MaxSize-front）%MaxSize ——选择题常考2.2.2队列的链式实现 //带头节点的队列 #include #include typedef struct QNode{int data;struct QNode *next;}QNode,*QueuePtr; typedef struct {QueuePtr front;QueuePtr rear;}LinkQueue;//初始化bool InitQueue(LinkQueue &Q){Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));//k开辟一块一个节点大小的内存空间并用头尾保存此节点的内存地址 if(!Q.front) return false;Q.front->next=NULL;return true; }//销毁bool Destory(LinkQueue &Q){QNode *P;while(Q.front){P=Q.front->next;free(Q.front);Q.front=P;}return true;} //入队void EnQueue(LinkQueue &Q,int a){QueuePtr P=(QueuePtr)malloc(sizeof(QNode));P->data=a;P->next=NULL;Q.rear->next=P;Q.rear=P;}//出队bool DeQueue(LinkQueue &Q,int &b){if(Q.front==Q.rear) return false;QueuePtr P=Q.front->next;b=P->data;Q.front->next =P->next;if(Q.rear==P) Q.rear=Q.front;//这里比较特殊，意思是我们是采用了新的指针P暂存待删除元素的地址，但当是最后一个地址的时候已经无法再将节点向后移所以在最后一个时候要调整rear指针 free(P);return true;} //队头元素int GetHead(LinkQueue Q){return Q.front->next->data;} int main(){int a,b;LinkQueue Q;InitQueue(Q);EnQueue(Q,22);EnQueue(Q,33);DeQueue(Q,a);b=GetHead(Q);printf("%d",b);} 双端队列只允许从两端插入和删除的线性表 变体：输入受限和输出受限的双端队列 考题：判断输出顺序是否合法 卡特兰数. 
算法实现：
表达式由操作数、运算符、界限符组成。
中缀表达式就是日常使用的形式：运算符在两个表达式中间，例如a+b 后缀表达式应用场景多考察较多：运算符在两个表达式后面，例如ab+ 前缀表达式称为波兰表达式（后缀表达式称为逆波兰表达式）例如+ab
手算时，一个中缀表达式对应的后缀表达式不唯一 
为了算法的唯一性，机算采用左优先原则（只要左边的运算符能先计算就先算左边的），保证机算和手算的结果相同
实现：
中缀转前缀 
前缀表达式 
函数调用的特点：LIFO
在任何一段代码执行前，系统都会在内存中开辟一块函数调用栈，用这个栈来保持各个函数在调用过程中需要保存的地址如调用返回地址、实参、局部变量。
递归包括：递归表达式和边界条件，如斐波那契和汉诺塔
递归的复杂度很高如果对时间要求不较高一般不采用递归算法
2.3.4 队列的应用——树、图的广度优先遍历、操作系统资源分配策略 2.4.特殊矩阵的压缩存储 2.4.1 普通矩阵二维数组
2.4.2 对称矩阵
存储：只存储主对角线和下三角区 