本人坚持更新C语言和数据结构知识,可以收藏+关注随时了解😜😜😜
目录
栈的链式存储主要是用到了两个结构体
一个结构体存放栈顶指针和栈底指针
之所以这样,是因为栈属于一个操作受限的线性表,对栈的操作只能在栈顶执行
一个结构体是存放结点
结点包括数据域和指针域,类似于链表
- typedef struct Node //结点
- {
- int data;
- struct Node *pNext;
- } Node, *PNODE;
- // Node<=>struct Node
- // PNODE <=>struct Node *
-
-
- typedef struct Stack //存放栈顶指针和栈底指针
- {
- PNODE pTop; // pTop指向的数据类型为struct Node
- PNODE pBottom;
- } STACK, *PSTACK;
- //Stack<=>struct Stack
- //PSTACK<=>struct Stack*
(1)我们创建存放栈顶栈底指针的结构体(也就是栈的结构体),并动态创建一个结点,作为栈底,栈底的指针域为空
(2)初始状态下,栈顶指针(S.top)和栈底指针(S.bottom)都指向栈底
- void initStack(PSTACK pS)
- {
- pS->pTop = (PNODE)malloc(sizeof(Node)); //动态生成一个结点,使得pTop指针指向它,pTop保存这个结点第一个字节的地址
- if (NULL == pS->pTop)
- {
- printf("dynamic memory is failed to allocate,procedure is over!\n");
- exit(-1);
- }
- else
- {
- pS->pBottom = pS->pTop; //让pBottom和pTop指向同一个结点
- pS->pBottom->pNext = NULL; // pS->pTop->pNext = NULL;令栈底的指针域为空
- }
- }
栈的操作只能在栈顶进行,所以重点是移动栈顶指针的位置,让S.Ptop指向栈顶元素
(1)动态生成一个结点pNew
(2)pNew指向栈底,栈顶指针指向pNew
(3)以此类推
- void pushStack(PSTACK pS, int val)
- {
- PNODE pNew = (PNODE)malloc(sizeof(Node));
- pNew->data = val;
- pNew->pNext = pS->pTop; // pS->pTop不能改成pS->pBottom
- pS->pTop = pNew; // pTop指向pNew
- }
出栈是压栈的逆过程,只需要将S.pTop指针下移,然后释放被删除节点的内存就可以
- /把pS所指向的栈出栈一次,并把出栈的元素存入pVal形参所指向的变量中
- bool pop(PSTACK pS, int *pVal)
- {
- if (empty(pS))
- return false;
- else
- {
- PNODE r = pS->pTop;
- *pVal = r->data;
- pS->pTop = pS->pTop->pNext; // ps->pTop=r->pNext
- free(r);
- r = NULL;
- return true;
- }
- }
栈空的条件为,栈顶指针和栈底指针指向同一个存储单元
- bool empty(PSTACK pS)
- {
- if (pS->pBottom == pS->pTop)
- {
- return true;
- }
- else
- {
- return false;
- }
- }
1.定义一个结构体指针指向栈顶,和S.pTop指向同一个位置
2.每读取一个元素就将p下移一次,直到p指向的节点的指针域为NULL
- void traverse(PSTACK pS)
- {
- PNODE p;
- p = pS->pTop;
- cout << "stack's datas are:" << endl;
- while (p->pNext != NULL)
- {
- cout << p->data << endl;
- p = p->pNext;
- }
- }