Chap 3: Lists, Stacks, and Queues⚓︎

// 链表的类型声明，一般放在 .h 文件中
#ifndef _List_H

struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;

List MakeEmpty(List L);
int IsEmpty(List L);
int IsLast(Position P, List L);
Position Find(ElementType X, List L);
void Delete(ElementType X, List L, Position P);
Position FindPrevious(ElementType X, List L);
void Insert(ElementType X, List L, Position P);
void DeleteList(List L);
Position Header(List L);
Position First(List L);
Position Advance(Position P);
ElementType Retrieve(Position P);

#endif

// 链表的具体实现，一般放在.c文件中

// 节点
struct Node
{
    ElementType Element;
    Position Next;
};

// 检查链表是否为空
int IsEmpty(List L)
{
    return L->Next == NULL;
}

// 检查节点 P 是否为最后一项
// 注意到链表 L 没有用上，放在这里是为了应付特殊情况的处理
int IsLast(Position P, List L)  
{
    return P->Next == NULL;
}

// 查找数据 X 在链表 L 中的位置
Position Find(ElementType X, List L)
{
    Position P;

    P = L->Next;
    while (P != NULL && P->Element != X)
        P = P->Next;

    return P;
}

// 删除链表 L 中的数据 X
void Delete(ElementType X, List L)
{
    Position P, TmpCell;

    P = FindPrevious(X, L);

    if (!IsLast(P, L))
    {
        TmpCell = P->Next;
        P->Next = TmpCell->Next;
        Free(TmpCell); // 删除节点时不要忘记释放内存！！！
    }
}

// 查找前一项
Position FindPrevious(ElementType X, List L)
{
    Position P;

    P = L;
    while (P->Next != NULL && P->Next->Element != X)
        P = P->Next;

    return P;
}

// 在位置 P 后插入新数据 X
void Insert(ElementType X, List L, Position P)
{
    Position TmpCell;

    TmpCell = (PtrToNode)malloc(sizeof(struct Node)); 
    if (TmpCell == NULL)
        FatalError("Out of Space!!!"); // 这里用到处理错误信息的自定义函数

    TmpCell->Element = X;
    TmpCell->Next = P->Next;
    P->Next = TmpCell;
}

// 链表的类型声明，一般放在.h文件中
#ifndef _Cursor_H

typedef int PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;

void InitializeCursorSpace(void);

List MakeEmpty(List L);
int IsEmpty(List L);
int IsLast(Position P, const List L);
Position Find(ElementType X, const List L);
void Delete(ElementType X, List L);
Position FindPrevious(ElementType X, const List L);
void Insert(ElementType X, List L, Position P);
void DeleteList(List L);
Position Header(const List L);
Position First(const List L);
Position Advance(const Position P);
ElementType Retrieve(const Position P);

#endif

// 链表的具体实现，一般放在.c文件中

// 节点
struct Node
{
    ElementType Element;
    Position Next;
};

struct Node CursorSpace[SpaceSize];

// 假设游标分配和释放函数已有函数原型
// 游标分配
static Position CursorAlloc(void)
{
    Position P;

    P = CursorSpace[0].Next;
    CursorSpace[0].Next = CursorSpace[P].Next;

    return P;
}

// 游标释放
static void CursorFree(Position P)
{
    CursorSpace[P].Next = CursorSpace[0].Next;
    CursorSpace[0].Next = P;
}

// 检查链表是否为空
int IsEmpty(List L)
{
    return CursorSpace[L].Next == 0;
}

// 检查节点 P 是否为最后一项
// 注意到链表 L 没有用上，放在这里以防特殊情况的处理
int IsLast(Position P, List L)  
{
    return CursorSpace[P].Next == 0;
}

// 查找数据 X 在链表 L 中的位置
Position Find(ElementType X, List L)
{
    Position P;

    P = CursorSpace[L].Next;
    while (P && CursorSpace[P].Element != X)
        P = CursorSpace[P].Next;

    return P;
}

// 删除链表 L 中的数据 X
void Delete(ElementType X, List L)
{
    Position P, TmpCell;

    P = FindPrevious(X, L);

    if (!IsLast(P, L))
    {
        TmpCell = CursorSpace[P].Next;
        CursorSpace[P].Next = CursorSapce[TmpCell].Next;
        CursorFree(TmpCell); // 删除节点时不要忘记释放内存！！！
    }
}

// 在位置 P 后插入新数据 X
void Insert(ElementType X, List L, Position P)
{
    Position TmpCell;

    TmpCell = CursorAlloc();
    if (TmpCell == 0)
        FatalError("Out of Space!!!"); // 这里用到处理错误信息的自定义函数

    CursorSpace[TmpCell].Element = X;
    CursorSpace[TmpCell].Next = CursorSpace[P].Next;
    CursorSpace[P].Next = TmpCell;
}

// .h文件代码：栈 ADT 的类型声明
#ifndef _Stack_h

struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode Stack;

int IsEmpty(Stack S);
Stack CreateStack(void);
void DisposeStack(Stack S);
void MakeEmpty(Stack S);
void Push(ElementType X, Stack S);
ElementType Top(Stack S);
void Pop(Stack S);

#endif /* _Stack_h*/

// .c 文件代码：链表方式的实现
struct Node
{
    ElementType Element;
    PtrToNode Next;
};

int IsEmpty(Stack S)
{
    return S->next == NULL;
}

Stack CreateStack(void)
{
    Stack S;

    S = (Stack)malloc(sizeof(struct Node));
    if (S == NULL)
        FatalError("Out of space!!"); // 自定义函数
    MakeEmpty(S);
    return S;
}

void MakeEmpty(Stack S)
{
    if (S == NULL)
        Error("Must use CreateStack first");  // 自定义函数
    else 
        while (!IsEmpty(S))
            Pop(S);
}

void Push(ElementType X, Stack S)
{
    PtrToNode TmpCell;

    TmpCell = (PtrToNode)malloc(sizeof(struct Node));
    if (TmpCell == NULL)
        FatalError("Out of space!!");
    else
    {
        TmpCell->Element = X;
        TmpCell->Next = S->Next;
        S->Next = TmpCell;
    }
}

ElementType Top(Stack S)
{
    if (!IsEmpty(S))
        return S->Next->Element;
    Error("Empty stack");
    return 0; // Return value used to avoid warning
}

void Pop(Stack S)
{
    PtrToNode FirstCell;

    if (IsEmpty(S))
        Error("Empty stack");
    else
    {
        FirstCell = S->Next;
        S->Next = S->Next->Next;
        free(FirstCell);
    }
}

// .h 文件代码：栈 ADT 的类型声明
#ifndef _Stack_h

struct StackRecord;
typedef struct StackRecord *Stack;

int IsEmpty(Stack S);
int IsFull(Stack S);
Stack CreateStack(int MaxElements);
void DisposeStack(Stack S);
void MakeEmpty(Stack S);
void Push(ElementType X, Stack S);
ElementType Top(Stack S);
void Pop(Stack S);
ElementType TopAndTop(Stack S);

#endif /* _Stack_h*/

// .c 文件代码：(动态分配)数组方式的实现
#define EmptyTOS (-1)   // 加括号是为了防止运算顺序的错误
#define MintackSize (5) // 同上
struct StackRecord
{
    int Capacity;
    int TopOfStack;
    ElementType *Array;
};

Stack CreateStack(int MaxElements)
{
    Stack S;

    if (MaxElemets < MinStackSize)
        Error("Stack size if too small");

    S = (Stack)malloc(sizeof(struct StackRecord));
    if (S == NULL)
        FatalError("Out of space!!!");
    S->Array = (ElementType *)malloc(sizeof(ElementType) * MaxElements);
    if (S->Array == NULL)
        FatalError("Out of Space!!!");
    S->Capacity = MaxElements;
    MakeEmpty(S);

    return S;
}

void DisposeStack(Stack S)
{
    if (S != NULL)
    {
        free(S->Array);
        free(S);
    }
}

int IsEmpty(Stack S)
{
    return S->TopOfStack == EmptyTOS;
}

void MakeEmpty(Stack S)
{
    S->TopOfStack = EmptyTOS;
}

void Push(ElementType X, Stack S)
{
    if(IsFull(S))
        Error("Full stack");
    else
        S->Array[++S->TopOfStack] = X;
}

ElementType Top(Stack S)
{
    if (!IsEmpty(S))
        return S->Array[S->TopOfStack];
    Error("Empty stack");
    return 0; // Return value used to avoid warning
}

void Pop(Stack S)
{
    PtrToNode FirstCell;

    if (IsEmpty(S))
        Error("Empty stack");
    else
    {
        S->TopOfStack--;
    }
}

// 市面上很多教材都会把 Pop 和 Top 函数集成到 Pop 函数上
// 而本书的作者将两者分开，但他也提供了集成的版本(前面没有写函数原型)
ElementType TopAndPop(Stack S)
{
    if(!IsEmpty(S))
        return S->Array[S->TopOfStack--];
    Error("Empty stack");
    return 0; // Return value used to avoid warning
}

// 这里的栈用的是数组表示法
// 而且该算法只能处理 10 以内的整数四则运算，仅供参考
int PostExp(char * exp, stack S)
{
    int len;
    int i;
    element a, b;
    int ans;

    len = strlen(exp);

    for (i = 0; i < len; i++)
    {
        if (exp[i] == ' ' || exp[i] == '\n')
            continue;
        else if (isdigit(exp[i]))
            Push(exp[i], S);
        else
        {
            b = Pop(S);
            a = Pop(S);
            if (!a || !b)
            {
                printf("wrong expression!\n");
                return INT_MAX; // 无穷大表示错误信号
            }
            switch(exp[i])
            {
                case '+':
                    Push(a + b - '0', S);
                    break;
                case '-':
                    Push(a - b + '0', S);
                    break;
                case '*':
                    Push((a - '0') * (b - '0') + '0', S);
                    break;
                case '/':
                    Push((a - '0') / (b - '0') + '0', S);
                    break;    
                default:
                    printf("wrong expression!\n");
                    return INT_MAX;     
            }

        }
    }
    ans = Pop(S) - '0';
    return ans;
}

// 直接摘自我的 project 2
Queue InToPost(char * exp)
{
    char * tmp = (char *)malloc(sizeof(char) * VLENGTH);  // Containing the variables or constant
    Stack s;   // The stack for operators, in order to getting the proper order in postfix form
    Queue q;   // The postfix expression, split them into variables, constants and operators in a queue
    char opt;  // The operator
    char * head = exp;  // Cheking if it's the first character in the expression
    
    // Initialization
    s = CreateStack();
    q = CreateQueue();
    tmp[0] = '\0';
    
    while (*exp != '\0') // Traversing the infix expression
    {
        if (isalnum(*exp))  // Finding the potential variables and constants
        {
            CharToString(*exp, tmp);  // Receiving it
        }
        else if (*exp == '-' && (exp == head || *(exp - 1) == '(')) // Handling with the case with minus sign
        {
            Enqueue("0", q);
            Push2(*exp, s);
        }
        else  // If it's an operator
        {
            if (strlen(tmp))  // If there is a variable or a constant
            {
                if (*exp == '(' && (!strcmp(tmp, "sin") || !strcmp(tmp, "cos") || !strcmp(tmp, "ln")))  // Dealing with math functions
                {
                    Enqueue("0", q);
                    switch (tmp[0])
                    {
                        case 's':           // sin
                            Push2('!', s);
                            break;
                        case 'c':           // cos
                            Push2('@', s);
                            break;
                        case 'l':           // ln
                            Push2('#', s);
                            break;
                    }
                }
                else
                    Enqueue(tmp, q);  // Outputting it
                tmp[0] = '\0';    // Resetting
            }
            // If it's an empty stack or the priority of the current operator is higher than the top element, or the top element is the left parentheses
            if (IsEmpty(s) || priority(*exp) < priority(s->top->operator) || s->top->operator == '(')
                Push2(*exp, s);  // Pushing the operator into the stack
            else if (*exp == ')')  // If it's a right parentheses
            {
                while (s->top->operator != '(')  // Poping out all the operators on the left parentheses in the stack
                {
                    opt = Top2(s);
                    Pop(s);
                    CharToString(opt, tmp);
                    Enqueue(tmp, q);  // Don't forget to output it!
                    tmp[0] = '\0';    // Resetting
                }
                Pop(s);  // Don't forget throw the left parentheses out!
                while (s->top->operator == '!' || s->top->operator == '@' || s->top->operator == '#') // Coping with math functions, but unluckily, there are still some bugs
                {
                    opt = Top2(s);
                    Pop(s);
                    CharToString(opt, tmp);
                    Enqueue(tmp, q);  // Don't forget to output it!
                    tmp[0] = '\0';    // Resetting
                }
            }
            else // Else Poping out all elements with the higher priority out, until encountering the '(' or the lower one
            {
                while (s->top->operator != '(' && priority(*exp) >= priority(s->top->operator))
                {
                    opt = Top2(s);
                    Pop(s);
                    CharToString(opt, tmp);
                    Enqueue(tmp, q);  // Don't forget to output it!
                    tmp[0] = '\0';    // Resetting
                }
                Push2(*exp, s);  // Pushing the new one to the stack
            }
        }
        exp++;  // Checking the next one
    }

    // Dealing with the remaining part(important!)
    if (strlen(tmp))
    {
        Enqueue(tmp, q);
        tmp[0] = '\0';
    }

    while (!IsEmpty(s))  // Disposing of the remaining elements in the stack
    {
        if (Top2(s) != '('  && Top2(s) != ')')  // Special case for parentheses
        {
            opt = Top2(s);
            Pop(s);
            CharToString(opt, tmp);
            Enqueue(tmp, q);
            tmp[0] = '\0';  
        }
        else
            Pop(s);        
    }

    return q;   // Returing the output sequence

}

// .h文件代码：队列ADT的类型声明
#ifndef _Queue_h

struct QueueRecord;
typedef struct QueueRecord *Queue;

int IsEmpty(Queue Q);
int IsFull(Queue Q);
Stack CreateQueue(int MaxElements);
void DisposeQueue(Queue Q);
void MakeEmpty(Queue Q);
void Enqueue(ElementType X, Queue Q);
ElementType Front(Queue Q);
void Dequeue(Queue Q);
ElementType FrontAndDequeue(Queue Q);

#endif /* _Queue_h*/

// .c 文件代码：(动态分配)数组方式的实现
#define MintackSize (5) // 加括号是为了防止运算顺序的错误
struct QueueRecord
{
    int Capacity;
    int Front;
    int Rear;
    int Size;
    ElementType *Array;
};

int IsEmpty(Queue Q)
{
    return Q->Size == 0;
}

void MakeEmpty(Queue Q)
{
    Q->Size = 0;
    Q->Front = 1;
    Q->Rear = 0;
}

// 形成循环队列
static int Succ(int Value, Queue Q)
{
    if (++Value == Q->Capacity)
        Value = 0;
    return Value;
}

void Enqueue(ElementType X, Queue Q)
{
    if (IsFull(Q))
        Error("Full Queue");
    else
    {
        Q->Size++;
        Q->Rear = Succ(Q->Rear, Q);
        Q->Array[Q->Rear] = X;
    }
}

void Dequeue(Queue Q)
{
    if (IsEmpty(Q))
        Error("Empty Queue");
    else
    {
        Q->Size--;
        Q->Front = Succ(Q->Front, Q);
    }
}

ElementType Front(Queue Q)
{
    if (IsEmpty(Q))
        Error("Empty Queue");
    else
        return Q->Array[Q->Front];
}

// Declaration
typedef struct QueueNode * PtrToQueue;  // The pointer to a queue node
typedef struct queue * Queue;           // The actual queue
struct QueueNode                        // The node(double linked list)
{
    char var[VLENGTH];
    PtrToQueue next;                    // The pointer to the next node
    PtrToQueue pre;                     // The pointer to the previous node
};

struct queue                            // just a structure, the real one is defined above!
{
    PtrToQueue front;                 
    PtrToQueue rear;
    int size;
};

int IsEmptyQ(Queue Q);                  // Detecting whether the queue is empty
Queue CreateQueue();                    // Creating the queue
void DisposeQueue(Queue Q);             // Clearing the queue
void Enqueue(char * x, Queue Q);        // Putting the element into the queue
char * Front(Queue Q);                  // Obtaining the front element
void Dequeue(Queue Q);                  // Deleting the front element


// Functions
int IsEmptyQ(Queue Q)
{
    return Q->size == 0;   // Just Cheking the size
}

// Creating the queue
Queue CreateQueue()
{
    Queue q;
    // Allocating spaces for the while queue, the front node and the rear node
    q = (Queue)malloc(sizeof(struct queue));
    q->front = (PtrToQueue)malloc(sizeof(struct QueueNode));
    q->rear = (PtrToQueue)malloc(sizeof(struct QueueNode));
    q->front = q->rear; // Letting the front pointer and the rear pointer point to the same position, representing the empty queue
    q->size = 0;   // Letting the size be 0(empty)

    return q;
}

// Clearing the queue
void DisposeQueue(Queue Q)
{
    while (!IsEmptyQ(Q))  // Deleting all the element until all the element is out
        Dequeue(Q);
}

// Putting the element into the queue
void Enqueue(char * x, Queue Q)
{   // Allocating a space for the temporary node
    PtrToQueue tmp = (PtrToQueue)malloc(sizeof(struct QueueNode));

    strcpy(tmp->var, x);  // Assignment
    tmp->pre = Q->rear;   // Building the relationship with the originally rear node
    tmp->next = Q->rear->next;
    Q->rear->next = tmp;
    Q->rear = tmp;        // Setting the new node as the rear node
    Q->size++;            // Incrementing the size
}

// Obtaining the front element
char * Front(Queue Q)
{
    if (!IsEmptyQ(Q))           // If not empty, obtaining the front node
        return Q->front->next->var;

    printf("Empty Queue!!!\n");  // Warning!!!
    return 0;
}

// Deleting the front element
void Dequeue(Queue Q)
{// Allocating a space for the temporary node
    if (IsEmptyQ(Q))     // Warning!
        printf("Empty Queue!!!");
    else
    {
        PtrToQueue tmp = Q->front->next; // Remember the queue has a dummy header!
        Q->front->next = tmp->next;   // Setting the next node as the new front node
        tmp->next->pre = Q->front;
        free(tmp);   // Deleting the originally front node
        Q->size--;   // Decrementing the size
    }

}