家庭网站建设,建设网站需要什么人员,企业公司网页设计方案,公司网站运营维护单位目录
顺序栈
结构
初始化一个空顺序栈
压栈
出栈
例子 十进制转八进制
链式栈
管理结构体的定义
初始化
压栈
出栈 顺序栈
顺序栈的实现#xff0c;主要就是定义一块连续的内存来存放这些栈元素#xff0c;同时为了方便管理#xff0c; 再定义一个整数变量来代表…目录
顺序栈
结构
初始化一个空顺序栈
压栈
出栈
例子 十进制转八进制
链式栈
管理结构体的定义
初始化
压栈
出栈 顺序栈
顺序栈的实现主要就是定义一块连续的内存来存放这些栈元素同时为了方便管理 再定义一个整数变量来代表当前栈顶元素在此连续内存中的偏移量这样就可以很方便地知 道栈的状态和当前栈顶元素的位置便于压栈和出栈操作。将栈内存地址和栈顶元素偏移量 放在一起形成一个专门用来管理顺序栈的结构体我们称之为管理结构体 结构
struct sequent_stack // 栈的管理结构体
{int *stack; // 用 stack 指向一块连续的内存来存储栈元素int size; // size 保存了该顺序栈的总大小int top; // 用 top 来指示栈顶元素的偏移量
};
初始化一个空顺序栈
一个空栈意味着栈中 没有元素首先将 stack 指向的内存清零其次更重要的是将 top 置为-1同时规定-1 为 空栈的标志这么做的好处是将来压栈第一个元素之后立即将 top 加 1 就会得到 0 而第一个元素就放在 stack 所指向的内存的开端处偏移量刚好为 0
struct sequent_stack *init_stack(int size) // 参数 size 表明空栈的初始大小
{struct sequent_stack *s;s malloc(sizeof(struct seqent_stack)); // 申请栈管理结构体if(s ! NULL){s-stack calloc(size, sizeof(int)); // 申请栈空间并由 stack 指向s-size size;s-top -1; // 将栈顶偏移量置为-1代表空栈}return s;
}
压栈
假设栈中已有一些元素压栈的第一步首先要判 断栈是否已满如果已满就要考虑扩充栈空间或者直接出错返回如果未满则需要将新的 栈顶元素堆叠到原栈顶之上
bool stack_full(struct sequent_stack *s)
{return s-top s-size-1; // 判断栈是否已满
}
bool push(struct sequent_stack *s, int data)
{if(stack_full(s)) // 如果栈已满则出错返回return false;s-top;s-stack[s-top] data;return true;
}
出栈
出栈之前需要判断栈是否为空
bool stack_empty(struct sequent_stack *s)
{return s-top -1; // 判断栈是否为空
}
bool pop(struct sequent_stack *s, int *p) // p 指向存放栈顶元素的内存
{if(stack_empty(s)) // 如果栈为空则出错返回return false;*p s-stack[s-top];s-top--;return true;
}
例子 十进制转八进制
int main(void)
{struct sequent_stack *s;s init_stack(10); // 初始化一个具有 10 个元素空间的顺序栈int n;scanf(%d, n); // 让用户输入一个需要转换的十进制数while(n 0){push(s, n%8); // 使用短除法将余数统统压栈n / 8;}int m;while(!stack_empty(s)) // 只要栈不为空就继续循环{pop(s, m); // 出栈并打印出来printf(%d, m);}printf(\n);return 0;
}链式栈
对于链式栈而言同样也需要一系列基本操作初始化、压栈、出栈、判断是否为空、 判断是否已满等等。首先初始化一个空栈意味着使得 top 指向 NULL而 size 记为 0 管理结构体的定义
struct node // 栈节点结构体
{int data;struct node *next;
};
struct linked_stack // 栈管理结构体
{struct node *top;int size;
};
初始化
struct linked_stack *init_stack(void)
{struct linked_stack *s;s malloc(sizeof(struct linked_stack)); // 申请一个管理结构体if(s ! NULL){s-top NULL; // j 将栈置空s-size 0;}return s;
}
压栈
压栈首先需要一个新节点然后 将新的节点的 next 指针指向原来的栈顶再让 top 指针指向该新的栈顶元素即可 创建新结点
struct node *new_node(int data) // 创建一个新的节点
{struct node *new;new malloc(sizeof(struct node));if(new ! NULL){new-data data;new-next NULL;}return new;
}
将新节点 new 压栈
bool push(struct linked_stack *s, struct node *new) // 将新节点 new 压栈
{if(s NULL || new NULL)return false;new-next s-top; // 第①步见上图s-top new; // 第②步s-size;return true;
}
出栈
对于出栈来说首先要判断栈是否为空如果不为空则先要用一个指针 tmp 来保存 原栈顶元素的地址然后返回栈顶元素再将 top 指针指向下一个元素最后要注意释放 tmp 所指向的原栈顶元素的内存空间 bool pop(struct linked_stack *s, int *p)
{if(s NULL || p NULL || stack_empty(s))return false;struct node *tmp s-top; // 第①步*p tmp-data; // 第②步s-top s-top-next; // 第③步free(tmp); // 第④步s-size--;return true;
}
