数据结构五

一、关于线性表中栈的顺序存储和链式存储方式的实现方式

1.栈的顺序存储

#include "stdio.h"
#include "stdlib.h"

#define MaxSize 10 //定义栈中元素的最大个数
typedef struct {
    int data[MaxSize]; //静态数组存放栈中元素
    int top;//栈顶指针
}SqStack;
//判断栈是否为空
int EmptyStack(SqStack* s){
    if(s->top==-1)
        return 1;
    else
        return 0;
}
void InitStack(SqStack* s){
    s->top=-1;//初始化栈顶指针
}
//新元素入栈
int Push(SqStack* s,int x){
    if(s->top==MaxSize-1)
        return 0;
    s->top++;
    s->data[s->top]=x;
    return 1;
}
//出栈操作
int Pop(SqStack* s,int* x){
    if(s->top==-1)
        return 0;
    *x=s->data[s->top];
    s->top--;
    return 1;
}
int GetTop(SqStack* s,int* x){
    if(s->top==-1)return 0;
    *x=s->data[s->top];
    return 1;
}
int main(){
    //1.声明一个栈
    SqStack s;
    //2.初始化栈
    InitStack(&s);
    //3.判断栈是否为空
    int IsEmpty= EmptyStack(&s);
    printf("The sequence-stack is %s.\n",IsEmpty?"empty":"not empty");
    //4.插入元素
    if(Push(&s,2)){
        printf("The sequence-stack inserts one data,and data which is inserted is %d\n",s.data[s.top]);
    }else{
        printf("The sequence-stack doesn't insert one data,and sequence-stack is full!\n");
    }
    Push(&s,5);
    //5.删除一个元素
    int x=-1;
    if(Pop(&s,&x)){
        printf("The sequence-stack deletes one data,and data which is deleted is %d.\n",x);
    }else{
        printf("The sequence-stack doesn't delete one data,and sequence-stack is empty!\n");
    }
    //获取栈顶元素
    if(GetTop(&s,&x)){
        printf("The sequence-stack reads top,and top data is %d.\n",x);
    }else{
        printf("The sequence-stack doesn't read top,and sequence-stack is empty!\n");
    }
    return 0;
}

实现结果：

D:\project\clion\ch1\cmake-build-debug\sequential_stack.exe
The sequence-stack is empty.
The sequence-stack inserts one data,and data which is inserted is 2
The sequence-stack deletes one data,and data which is deleted is 5.
The sequence-stack reads top,and top data is 2.

Process finished with exit code 0

2.栈的链式存储

#include "stdlib.h"
#include "stdio.h"
struct LinkNode{
    int data;
    struct LinkNode* next;
};

//创建一个节点
struct LinkNode* CreateNode(int data){
    struct LinkNode* p=(struct LinkNode*) malloc(sizeof(struct LinkNode));
    if(!p){
        printf("No enough memory to allocate!\n");
        exit(0);
    }
    p->data=data;
    p->next=NULL;
    return p;
}
//插入一个节点(入栈)
struct LinkNode* Push(struct LinkNode* L,int x){
    struct LinkNode* p=L,*s=NULL;
    s= CreateNode(x);
    if(p->next!=NULL)
        s->next=p->next;
    p->next=s;
    return L;
}
//删除一个节点(出栈)
struct LinkNode* Pop(struct LinkNode* L,int* x){
    struct LinkNode* p=L,*pr=NULL;//p是头节点
    *x=p->next->data;//获取数据
    pr=p->next;
    if(p->next!=NULL){
        p->next=pr->next;
        free(pr);
    }
    return L;
}
//读取栈顶元素
int GetTop(struct LinkNode* L,int* x){
    struct LinkNode* p=L->next;
    if(!p) return 0;
    *x=p->data;
    return 1;
}
//栈的判空
int EmptyStack(struct LinkNode* L){
    return L->next==NULL;
}
int main(){
    int x= -1;
    //1.创建头指针
    struct LinkNode* L=NULL;
    //2.创建头节点
    L= CreateNode(0);

    //栈的判空
    printf("The linked-stack is %s\n", EmptyStack(L)?"empty":"not empty");

    //3.插入元素
    L= Push(L,2);

    //栈的判空
    printf("The linked-stack is %s\n", EmptyStack(L)?"empty":"not empty");

    L= Push(L,5);

    //读栈顶
    if(GetTop(L,&x)){
        printf("The top of linked-stack is %d\n",x);
    }else{
        printf("The linked-stack is empty!\n");
    }
    //4.删除元素
    L= Pop(L,&x);
    printf("The linked-stack deletes top of stack,and data which is deleted is %d\n",x);

    //读栈顶
    if(GetTop(L,&x)){
        printf("The top of linked-stack is %d\n",x);
    }else{
        printf("The linked-stack is empty!\n");
    }

    //删除栈顶
    L= Pop(L,&x);
    printf("The linked-stack deletes top of stack,and data which is deleted is %d\n",x);

    //5.读取栈顶元素
    if(GetTop(L,&x)){
        printf("The top of linked-stack is %d\n",x);
    }else{
        printf("The linked-stack is empty!\n");
    }

    //6.判断栈是否为空
    printf("The linked-stack is %s\n", EmptyStack(L)?"empty":"not empty");
    return 0;
}

实现结果：

D:\project\clion\ch1\cmake-build-debug\linked_stack.exe
The linked-stack is empty
The linked-stack is not empty
The top of linked-stack is 5
The linked-stack deletes top of stack,and data which is deleted is 5
The top of linked-stack is 2
The linked-stack deletes top of stack,and data which is deleted is 2
The linked-stack is empty!
The linked-stack is empty

Process finished with exit code 0