不带头节点的链式存储实现链栈

1.先创建一个结构体类型，有数据域和指针域

typedef struct LNode { int data; struct LNode* next; }LNode,*LinkStack;

2.以头节点为栈口进行操作进栈和出栈

头节点进栈

int HeadPush(LinkStack* Ps, int elem) { if ((*Ps) == NULL) { (*Ps) = (LNode*)malloc(sizeof(LNode)); if ((*Ps) == NULL) { return 1; } (*Ps)->data = elem; (*Ps)->next = NULL; return 0; } LNode* s = (LNode*)malloc(sizeof(LNode)); if (NULL ==s) { return 1; } s->data = elem; s->next = (*Ps); (*Ps) = s; return 0; }

头节点出栈

int HeadPop(LinkStack* Ps)//头节点出栈 { if ((*Ps) == NULL) { return 1; } LNode* p = (*Ps); (*Ps) = (*Ps)->next; free(p); return 0; } LNode* GetTail(LinkStack* Ps) { LNode* p = (*Ps); if (NULL == p) { return p; } while (p->next) { p = p->next; } return p; }

3.以尾节点为栈口进行操作进栈和出栈，因为是不带头节点的链栈，在处理尾节点的时候需要考虑到没有头节点，需要进行特殊处理

尾节点进栈

int TailPush(LinkStack*Ps,int elem) { if ((*Ps) == NULL) { (*Ps) = (LNode*)malloc(sizeof(LNode)); if ((*Ps) == NULL) { return 1; } (*Ps)->next = NULL; (*Ps)->data = elem; return 0; } LNode* p = GetTail(Ps);//得到了最后一个非空的节点 LNode* s = (LNode*)malloc(sizeof(LNode)); if (NULL == s) { return 1; } s->data = elem; s->next = p->next; p->next = s; return 0; }

尾节点出栈

int TailPop(LinkStack* Ps) { if ((*Ps) == NULL)//没有元素能够出栈 return 1; //需要找到倒数第二个非空的节点 if ((*Ps)->next == NULL) { LNode* temp = (*Ps);//只有一个元素 (*Ps) = (*Ps)->next; free(temp); return 0; } //if ((*Ps)->next->next == NULL) //{ // LNode* temp = (*Ps)->next; // (*Ps)->next = temp->next; // free(temp); // return 0; //} LNode* p = (*Ps); while (p->next->next) { p = p->next; } LNode* temp = p->next; p->next = temp->next; free(temp); return 0; }

4.打印链栈

void Display(LinkStack* Ps) { LNode* p = (*Ps); while (p) { printf("%d->", p->data); p = p->next; } printf("NULL\n"); }

5.判断一个链栈是不是空的，如果不是空的返回top元素

以头节点进行操作的top节点

void GetTop(LinkStack* Ps)//判断空栈和返回top元素 { if ((*Ps) == NULL)//说明是空表 { return 1; } return (*Ps)->data;//返回栈顶元素 }

以尾节点进行操作的top节点

LNode* GetTail(LinkStack* Ps) { LNode* p = (*Ps); if (NULL == p) { return p; } while (p->next) { p = p->next; } return p; }

6.全局代码，可以多测试几组，看是不是符合条件，主要是头节点和尾节点一定要考虑清楚

typedef struct LNode { int data; struct LNode* next; }LNode,*LinkStack; void InitStack(LinkStack* Ps) { (*Ps) = NULL;//头节点为空指针 } int HeadPush(LinkStack* Ps, int elem) { if ((*Ps) == NULL) { (*Ps) = (LNode*)malloc(sizeof(LNode)); if ((*Ps) == NULL) { return 1; } (*Ps)->data = elem; (*Ps)->next = NULL; return 0; } LNode* s = (LNode*)malloc(sizeof(LNode)); if (NULL ==s) { return 1; } s->data = elem; s->next = (*Ps); (*Ps) = s; return 0; } int HeadPop(LinkStack* Ps)//头节点出栈 { if ((*Ps) == NULL) { return 1; } LNode* p = (*Ps); (*Ps) = (*Ps)->next; free(p); return 0; } LNode* GetTail(LinkStack* Ps) { LNode* p = (*Ps); if (NULL == p) { return p; } while (p->next) { p = p->next; } return p; } int TailPush(LinkStack*Ps,int elem) { if ((*Ps) == NULL) { (*Ps) = (LNode*)malloc(sizeof(LNode)); if ((*Ps) == NULL) { return 1; } (*Ps)->next = NULL; (*Ps)->data = elem; return 0; } LNode* p = GetTail(Ps);//得到了最后一个非空的节点 LNode* s = (LNode*)malloc(sizeof(LNode)); if (NULL == s) { return 1; } s->data = elem; s->next = p->next; p->next = s; return 0; } int TailPop(LinkStack* Ps) { if ((*Ps) == NULL)//没有元素能够出栈 return 1; //需要找到倒数第二个非空的节点 if ((*Ps)->next == NULL) { LNode* temp = (*Ps);//只有一个元素 (*Ps) = (*Ps)->next; free(temp); return 0; } //if ((*Ps)->next->next == NULL) //{ // LNode* temp = (*Ps)->next; // (*Ps)->next = temp->next; // free(temp); // return 0; //} LNode* p = (*Ps); while (p->next->next) { p = p->next; } LNode* temp = p->next; p->next = temp->next; free(temp); return 0; } void Display(LinkStack* Ps) { LNode* p = (*Ps); while (p) { printf("%d->", p->data); p = p->next; } printf("NULL\n"); } void GetTop(LinkStack* Ps)//判断空栈和返回top元素 { if ((*Ps) == NULL)//说明是空表 { return 1; } return (*Ps)->data;//返回栈顶元素 } int main() { LinkStack S; InitStack(&S); //HeadPush(&S, 1); //HeadPush(&S, 2); //HeadPush(&S, 3); HeadPop(&S); TailPush(&S, 1); TailPush(&S, 2); TailPush(&S, 3); TailPush(&S, 4); TailPush(&S, 5); TailPop(&S); TailPop(&S); TailPop(&S); TailPop(&S); TailPop(&S); /*HeadPop(&S); HeadPop(&S); HeadPop(&S);*/ Display(&S); return 0; }