2022-1-24数据结构总结（2）

2022-1-24数据结构总结（2）

栈与队列

1、栈的顺序存储实现 

#include
#include
#define MaxSize 10


typedef struct{
    ElemType data[MaxSize];    //静态数组存放栈中元素
    int top;    //栈顶指针
}SqStack;

//初始化栈
void InitStack(SqStack){
    S.top=-1;    //初始化栈顶指针，top指针指向栈顶元素
}
//如果定义S.top=0则判断栈空条件为S.top=0，也意味着top指针始终指向下一个可以插入的位置
//对应进栈 *** 作为：S.data[S.top++]=x;对应出栈 *** 作为：x=S.data[--S.top];


//新元素进栈
bool Push(SqStack &S, ElemType x){
    if(S.top==MaxSize-1)
        return false;
    S.data[++S.top]=x;
    return ture;
}

//出栈 *** 作
bool Pop(SqStack &S, ElemType &x){
    if(S.top==-1)
        return false;
    x=S.data[S.top--];
    return ture;
}

//读栈顶 *** 作
bool GetTop(SqStack S, ElemType &x){
    if(S.top==-1)
        return false;
    x=S.data[S.top];
    return true;
}

//判断栈空
bool StackEmpty(SqStack S){
    if(S.top==-1)
        return ture;
    else
        return false;
}

void testStack(){
    SqStack S;
    InitStack(S);
}

 2、链栈的实现与头插法实现单链表雷同

 3、队列的顺序实现

#include
#include
#define MaxSize 10

typedef struct{
    ElemType data[MaxSize];
    int front, rear;
}SqQueue;

void InitQueue(SqQueue &Q){
    //初始时，队头队尾指针指向0
    Q.rear=Q.front=0;
}

//判断队列是否为空
bool QueueEmpty(SqQueue){
    if(Q.rear=Q.front)
        return true;
    else
        return false;
}

//入队 *** 作
bool EnQueue(SqQueue &Q,ElemType x){
    if((Q.rear+1)%MaxSize==Q.front)    //判断队满
//由于判断队空的条件为Q.rear=Q.front，因此设置为队尾的下一个位置为队头时队满
//从而队满时，队尾指针指向的位置没有插入值，即浪费了一个存储单元
        return false;
    Q.data[Q.rear]=x;    //新元素插入队尾
    Q.rear=(Q.rear+1)%MaxSize;    //队尾指针加1取模，使得队尾指针取值映射到0，1，2，...，rear的范围内
//队尾指针加1取模运算将其队列变为逻辑上的“环状”    
    return true;
}

//出队 *** 作(删除一个队头元素，并用x返回)
bool DeQueue(SqQueue &Q, ElemType &x){
    if(Q.rear==Q.front)    //队空则报错
        return false;
    x=Q.data[Q.front];
    Q.front=(Q.front+1)%MaxSize;    //队头指针后移
    return true;
}

//获取队头元素值，用x返回
bool GetHead(SqQueue Q, ElemType &x){
    if(Q.rear==Q.front)
        return false;    //队空则报错
    x=Q.data[Q.front];
    return true;
}

void testQueue(){
    SqQueue Q;
    InitQueue(Q);
    //......
    int num;
    num=(Q.rear+MaxSize-Q.front)%MaxSize;    //计算队列元素个数
}


//设置队列的第二种方法，目的是使队列空间得到完全应用

//设置队列的第三种方法，目的也是使队列空间得到完全应用

 4、队列的链式实现

#include
#include

typedef struct linkNode{
    ElemType data;
    struct linkNode *next;
}linkNode;

typedef struct {
    linkNode *front, *rear;
}linkQueue;

//初始化队列，带头结点
void InitQueue(linkQueue &Q){
    //初始时，front,rear都指向头结点,
    Q.rear=Q.front=(linkNode *)malloc(sizeof(linkNode));
    Q.front->next=NULL;
}

//判断队列是否为空
bool IsEmpty(linkQueue Q){
    if(Q.rear=Q.front)
        return true;
    else
        return false;
}

//入队 *** 作
bool EnQueue(linkQueue &Q,ElemType x){
    linkQueue *s=(linkQueue *)malloc(sizeof(linkNode));
    s->data=x;
    s->next=NULL;
    Q.rear->next=s;    //新节点插入到队尾指针之后
    Q.rear=s;    //移动队尾指针位置
}

//出队 *** 作
bool DeQueue(linkQueue &Q, ElemType &x){
    if(Q.rear==Q.front)    //队空则报错
        return false;
    linkQueue *p=Q.front->next;
    x=p->data;
    Q.front->next=p->next;
    if(Q.rear==p)    //最后一个结点出队
        Q.rear=Q.front;
    free(p);
    return true;
}

void testlinkQueue(){
    linkQueue Q;
    InitQueue(Q);
    //......
}