数据结构_day3

目录

4.栈 stack

4.2.1 特性

练习：

4.3 链式栈

4.3.1 特性

总结：

---

4.栈 stack

代码实现：

#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
typedef struct seqstack
{int maxlen;     //表示数组元素总个数datatype *data; //指向存放数据的数组的指针int top;        //栈顶有可以称栈针，本质还是最后一个有效元素下标等同于之前学的顺序表的last
} seqstack_t;//创建空顺序栈, len代表创建栈时的最大长度
seqstack_t *createEmptySeqStack(int len)
{//1. 开辟顺序栈结构体大小空间seqstack_t *p = (seqstack_t *)malloc(sizeof(seqstack_t));if (NULL == p){perror("p malloc err");return NULL;}//2. 初始化结构体空间p->top = -1;                                          //如同之前的last初始化为-1，因为元素个数是0，下标是0-1=-1p->maxlen = len;                                      //保存数组长度可以通过传参获取p->data = (datatype *)malloc(sizeof(datatype) * len); //开辟数组大小空间，单个元素大小乘以元素个数if (NULL == p->data){perror("p->data malloc err");return NULL;}return p;
}//判断是否为满,满返回1 未满返回0
int isFullSeqStack(seqstack_t *p)
{return p->top + 1 == p->maxlen;
}//入栈,data代表入栈的数据
int pushStack(seqstack_t *p, int data)
{//  1. 判满： p->top + 1 == p->maxlenif (isFullSeqStack(p)){printf("pushStack err\n");return -1;}// 让top栈顶加一p->top++;// 将数据入栈p->data[p->top] = data;return 0;
}//判断栈是否为空
int isEmptySeqStack(seqstack_t *p)
{return p->top == -1;
}//出栈
int popSeqStack(seqstack_t *p)
{//1.容错判断if (isEmptySeqStack(p)){printf("popSeqStack\n");return -1;}//printf("%d\n", p->data[p->top]);  //或者加打印也可以//2. 将栈针top减一p->top--;//3. 返回要出栈数据return p->data[p->top + 1];
}int main(int argc, char const *argv[])
{seqstack_t *p = createEmptySeqStack(6);for (int i = 0; i < 7; i++)pushStack(p, i); //最后报一个pushStack err，因为栈满了while (!isEmptySeqStack(p))printf("%d\n", popSeqStack(p));  //5 4 3 2 1 0 后进先出return 0;
}

#include <stdio.h>
#include <stdlib.h>void get_mem(int *q) //q=NULL
{q = (int *)malloc(sizeof(int)); //改变q不会影响到函数外的p， 开辟空间也不够
}int main(int argc, char const *argv[])
{int i;int *p = NULL;get_mem(p); //函数调用完成后p还是等于NULLfor (i = 0; i < 10; i++)p[i] = i;for (i = 0; i < 10; i++)printf("%d\n", p[i]);free(p);return 0;
}

​​​​​​​​​​​​​​

#include <stdio.h>
#include <stdlib.h>void get_mem(int **q) //q=&p
{*q = (int *)malloc(sizeof(int) * 10); //*q = *&p =p ,也就是操作*q就等同操作函数外的p
}int main(int argc, char const *argv[])
{int i;int *p = NULL;get_mem(&p); //函数调用结束后p真的指向了堆区for (i = 0; i < 10; i++)p[i] = i;for (i = 0; i < 10; i++)printf("%d\n", p[i]);free(p);return 0;
}

代码实现：

#include <stdio.h>
#include <stdlib.h>typedef int datatype;
typedef struct node
{datatype data;struct node *next;
} node_t, *node_p;//创建一个空栈
void createEmptyLinkStack(node_p *p) //p=&top
{*p = NULL; //*p = top = NULL
}//入栈, data是入栈的数据
int pushLinkStack(node_p *p, datatype data) //因为要用p接收函数外的&top来在函数内找到top, 所以参数需要为二级指针。
{// 创建新节点node_p pnew = (node_p)malloc(sizeof(node_t));if (NULL == pnew){perror("pnew malloc err");return -1;}// 将要入栈数据存入新节点pnew->data = data;pnew->next = NULL;// 将新节点连入到链表中pnew->next = *p; //*p=top// 移动栈针到新的栈顶节点*p = pnew;return 0;
}//判断栈是否为空
int isEmptyLinkStack(node_p p)
{return p == NULL;
}//出栈
datatype popLinkStack(node_p *p) //p=&top
{node_p pdel = NULL;//1. 判空：*p == NULL;if (isEmptyLinkStack(*p)) //*p=top{printf("popLinkStack err\n");return -1;}//2. 让指针pdel指向栈顶节点pdel = *p;//3. 移动栈针到下一个节点*p = (*p)->next; //*p=pdel->next;//4. 定义临时变量保存要出栈数据: temp = pdel->data;datatype temp = pdel->data;//5. 释放要被删除节点: free(pdel);free(pdel);//6. 返回要出栈数据：return temp;return temp;
}//求栈的长度
int lengthLinkStack(node_p p) //传递一级指针，因为不需要移动栈针(也就是主函数的top)。
{int len = 0;while (p != NULL){len++;p = p->next;}return len;
}int main(int argc, char const *argv[])
{node_p top;createEmptyLinkStack(&top); //top=NULLpushLinkStack(&top, 1);pushLinkStack(&top, 2);pushLinkStack(&top, 3);printf("len=%d\n", lengthLinkStack(top));while (!isEmptyLinkStack(top)){printf("%d\n", popLinkStack(&top)); //3 2 1}return 0;
}