r6300v2做网站佛山网站设计的外文名是

当前位置： 首页 > news >正文

r6300v2做网站,佛山网站设计的外文名是,wordpress 文章分页 插件,网络设计解决:如何将初步规划中的各个子系统从内部一 栈的概念 栈是一种特殊的线性表#xff0c;栈内数据遵循先进后出(LIFO)的原则#xff0c;对于栈#xff0c;只能在同一侧进行入栈和出栈操作。 入栈操作和出栈操作是在栈的同一侧进行的#xff0c;如图示#xff1a; 对于栈这种数据类型#xff0c;我们可以采用链表或…一  栈的概念 栈是一种特殊的线性表栈内数据遵循先进后出(LIFO)的原则对于栈只能在同一侧进行入栈和出栈操作。 入栈操作和出栈操作是在栈的同一侧进行的如图示 对于栈这种数据类型我们可以采用链表或者数组来实现但是我们一般采取数组的形式进行实现。 二  栈的实现 1.栈的声明 对于一个用数组形式来实现的栈来说我们需要声明: 指向栈的有效地址指针栈顶(栈的有效空间)top,  栈的最大容量capacity typedef int TypeData; typedef struct Stack {TypeData* a;int top; //有效个数int capacity; //最大空间 }ST; 这里top为什么时栈的有效个数呢因为我们让top指向了当前数组存在有效数据的最大下标1的位置这样top更加直观的表达当前栈内的元素 2.栈的初始化 在一个栈创建后需要对栈进行初始化后才能进行使用对于栈的初始状态 指向数组首元素地址的指针为NULL 栈初始的最大容量为0 栈顶top的指向为数组为0的下标也就是当前栈的有效数据个数为0 void STInit(ST* ps) { assert(ps);ps-a NULL;ps-capacity ps-top 0; } 初始化后栈的图示如下  3.栈的入栈 当我们往栈中入数据时我们不能一昧的往里面入数据在每次入数据前需要考虑当前栈的容量是否已经满了如果当前栈的容量已满我们需要先将栈的最大容量扩充后再进行入栈操作。 在扩充最大容量操作时我们应当使用realloc函数因为我们需要保留原本栈中存放的数据 在空栈时入栈那么第一次扩充的栈的大小是4个数据类型空间也可以是8个10个等 如果栈中本来就有数据那么当栈满时新栈的最大容量为旧栈的两倍或整数倍 void STPush(ST* ps, TypeData x) {assert(ps);//检查空间是否足够if (ps-capacity ps-top) {int newcapacity ps-capacity 0 ? 4 : ps-capacity * 2;//创建newcapacity个空间ST* tmp (ST*)realloc(ps-a, sizeof(TypeData) * newcapacity);//如果开辟空间失败if (tmp NULL) {perror(realloc);exit(-1);}ps-capacity newcapacity;ps-a tmp;}//空间足够ps-a[ps-top] x; } 4.栈的出栈前提 当进行出栈操作时需要判定栈是否为空如果栈为空也就是没有数据则无法出栈。 当栈顶为0时说明当前栈中无数据返回true否则返回false  bool StackEmpty(ST* ps) {assert(ps);return ps-top 0; } 5.栈的出栈 在栈的出栈操作前需要判断当前栈中是否存有数据否则不能进行出栈操作 通过栈顶指针-1即可完成出栈操作 //出栈 void STPop(ST* ps) {assert(ps);assert(!StackEmpty(ps));–ps-top; } 6.取栈顶元素 取栈顶元素前和出栈操作一样需要判断当前栈是否为空否则无法取栈顶元素 取栈顶元素返回的是top-1位置的数据并非top位置 TypeData STTop(ST* ps) {assert(ps);assert(!StackEmpty(ps));//栈为空栈时无法取栈顶元素return ps-a[ps-top - 1]; } 7.获取栈的有效个数 直接返回top即可因为top不仅代表了栈顶还代表了当前栈中的有效个数 //获取栈中有效元素个数 int STSize(ST* ps) {assert(ps);return ps-top; } 8.栈的销毁 栈的销毁和顺序表基本一致 void STDestroy(ST* ps) {assert(ps);if (ps-a)free(ps-a);ps-a NULL;ps-top ps-capacity 0; } 9.栈的全码 #includestdio.h #includestdlib.h #includeassert.h #includestdbool.h typedef int TypeData; typedef struct Stack {TypeData* a;int top; //有效个数int capacity; //最大空间 }ST;//初始化 void STInit(ST* ps) { assert(ps);ps-a NULL;ps-capacity ps-top 0; }//销毁 void STDestroy(ST* ps) {assert(ps);if (ps-a)free(ps-a);ps-a NULL;ps-top ps-capacity 0; }//入栈 void STPush(ST* ps, TypeData x) {assert(ps);//检查空间是否足够if (ps-capacity ps-top) {int newcapacity ps-capacity 0 ? 4 : ps-capacity * 2;//创建newcapacity个空间ST* tmp (ST*)realloc(ps-a, sizeof(TypeData) * newcapacity);//如果开辟空间失败if (tmp NULL) {perror(realloc);exit(-1);}ps-capacity newcapacity;ps-a tmp;}//空间足够ps-a[ps-top] x; }//检查是否为空栈 bool StackEmpty(ST* ps) {assert(ps);return ps-top 0; }//出栈 void STPop(ST* ps) {assert(ps);assert(!StackEmpty(ps));–ps-top; }//取栈顶元素 TypeData STTop(ST* ps) {assert(ps);assert(!StackEmpty(ps));//栈为空栈时无法取栈顶元素return ps-a[ps-top - 1]; }//获取栈中有效元素个数 int STSize(ST* ps) {assert(ps);return ps-top; } int main(){return 0;} 三  队列的概念 队列是一种只允许在一侧入数据操作另一侧出数据操作的线性表具有先进先出的的原则 在入数据操作的一端称作队尾在出数据的一端称作队头 而对于队列的底层我们可以选择数组或者链表来实现在这里我们使用链表来实现因为采用数组来实现是在出队操作后数组需要相继往前移动一位这样才能使后面的的数据接着出队因此采用数组的话在出队操作时效率会比链表低 队列的内部数据用链表来表示 1.队列的声明 在 上面队列的概念中我们了解到队列的底层由链表来实现而队列有队头和队尾因此队列的结构体声明有些许不同可以理解为队列由两部分组成链表和队列本身因此我们需要声明两个结构体 //队列的在链表的基础上实现所以结构体有两个一个是链表结点(头删尾插) typedef int TypeData;//链表结点结构声明 typedef struct QueueNode {TypeData data;struct QueueNode* next; }Node; //队列本身的声明 typedef struct Queue {struct QueueNode* phead;//队头struct QueueNode* ptail;//队尾int size;//记录队列的元素个数每次入队1出队-1 }Queue; 2.队列的初始化 当我们创建一个队列时队列中是不存在数据的也就是不存在链表结点因此我们在初始化时不需要初始化链表结点结构体 //队列初始化 void QueueInit(Queue* ps) {assert(ps);ps-phead ps-ptail NULL;ps-size 0; } 初始化时队尾指针和队头指针应当为空因为此时队列中还不存在数据结点 初始化后图示 3.队列的入队  在队列的入队操作中其实是对队列中链表的尾插操作 入队步骤 1创建新结点 2在结点插入时需要判断当前队列是否为空也就是链表是否为空如果队列为空那么新创建的结点就是链表的头结点此时队尾指针和队头指针都指向头结点 3如果当前队列不为空那么直接在原队列上进行尾插即在链表进行尾插原链表最后一个结点被尾指针指向所以原最后一个结点的指针指向新结点原尾指针更新指向新结点 4记录队列元素个数的size 1 //队列的入队尾插 void QueuePush(Queue* ps, TypeData x) {//申请新结点Node* newNode (Node)malloc(sizeof(Node));if (newNode NULL) {perror(malloc);exit(1);}newNode-data x;newNode-next NULL;//两种情况队列为空与不为空if (ps-phead NULL) {ps-phead ps-ptail newNode;}else {//队列不为空ps-ptail-next newNode;ps-ptail newNode;}ps-size; } 4.队列的出队前提 队列的出队与栈一样在出队前对队列判断当前队列是否为空只有队列非空的时候才能进行出队操作 //判断队列是否为空 bool QueueEmpty(Queue ps) {//头节点为空证明队列为空return ps-phead NULL; } 5.队列的出队 对于队列的出队操作其实就是链表的头删 先记录下队头结点的下一个结点Next再释放队头结点并将队头结点指向队头结点的下一个结点Next,最后再将记录队列元素size成员-1 //队列出队头删 void QueuePop(Queue* ps) {assert(ps);assert(!QueueEmpty(ps));Queue* Next ps-phead-next;free(ps-phead);ps-phead Next;ps-size–; } 但是这样子其实考虑的并不完全如果队列中只有一个结点队尾指针和队头 指针都指向该结点那么 Next的指向为NULL当结点释放后队头指针指向Next达到了置空的作用但是队尾指针却没有置空那么此时队尾指针就成为了野指针这是不被允许的 因此我们需要分两种情况进行讨论队列只有一个结点和队列有多个结点 怎样判断队列是否只有一个结点当队头指针和队尾指针的指向相同时 //队列出队头删 void QueuePop(Queue* ps) {assert(ps);assert(!QueueEmpty(ps));//如果队列只有一个结点if (ps-phead ps-ptail) {free(ps-phead);ps-phead ps-ptail NULL;}else {//队列有多个结点Queue* Next ps-phead-next;free(ps-phead);ps-phead Next;}ps-size–; } 6.取队头元素 无需多言队头指针指向的数据就是队头元素直接返回即可 //取队头元素 TypeData QueueFront(Queue* ps) {assert(ps);assert(!QueueEmpty(ps));return ps-phead-data; } 7.取队尾元素 无需多言队尾指针指向的元素就是队尾元素直接返回即可 //取队尾元素 TypeData QueueBack(Queue* ps) {assert(ps);assert(!QueueEmpty(ps));return ps-ptail-data; } 8.队列的销毁 利用指针del指向要删除的结点指针Next记录删除结点的下一个结点当del为空时证明队列已经销毁再将队列所有的指针置空队列有效个数置0 //队列的销毁 void DestoryQueue(Queue* ps) {assert(ps);assert(!QueueEmpty(ps));Node* del ps-phead;while (del) {Queue* Next del-next;free(del);del Next;}ps-phead ps-ptail del NULL;ps-size 0; } 9.获取队列的有效元素个数 直接返回结构体成员变量size即可 TypeData QueueNums(Queue* ps) {return ps-size; } 10.队列的全码 #includestdio.h #includestdlib.h #includeassert.h #includestdbool.h//队列的在链表的基础上实现所以结构体有两个一个是链表结点(头删尾插) typedef int TypeData;//链表结点结构声明 typedef struct QueueNode {TypeData data;struct QueueNode* next; }Node;typedef struct Queue {struct QueueNode* phead;struct QueueNode* ptail;int size; }Queue;//队列初始化 void QueueInit(Queue* ps) {assert(ps);ps-phead ps-ptail NULL;ps-size 0; }//队列的入队尾插 void QueuePush(Queue* ps, TypeData x) {//申请新结点Node* newNode (Node)malloc(sizeof(Node));if (newNode NULL) {perror(malloc);exit(1);}newNode-data x;newNode-next NULL;//两种情况队列为空与不为空if (ps-phead NULL) {ps-phead ps-ptail newNode;}else {//队列不为空ps-ptail-next newNode;ps-ptail newNode;}ps-size; }//判断队列是否为空 bool QueueEmpty(Queue ps) {//头节点为空证明队列为空return ps-phead NULL; }//队列出队头删 void QueuePop(Queue* ps) {assert(ps);assert(!QueueEmpty(ps));//如果队列只有一个结点if (ps-phead ps-ptail) {free(ps-phead);ps-phead ps-ptail NULL;}else {//队列有多个结点Queue* Next ps-phead-next;free(ps-phead);ps-phead Next;}ps-size–; }//取队头元素 TypeData QueueFront(Queue* ps) {assert(ps);assert(!QueueEmpty(ps));return ps-phead-data; }//取队尾元素 TypeData QueueBack(Queue* ps) {assert(ps);assert(!QueueEmpty(ps));return ps-ptail-data; }//队列的销毁 void DestoryQueue(Queue* ps) {assert(ps);assert(!QueueEmpty(ps));Node* del ps-phead;while (del) {Queue* Next del-next;free(del);del Next;}ps-phead ps-ptail del NULL;ps-size 0; }TypeData QueueNums(Queue* ps) {return ps-size; }