文章目录

3.1.栈3.1.2 栈的存储结构和实现顺序栈的C语言实现顺序栈的基本操作实现InitStack(&S)StackEmpty()Push(e):Pop(e):Gettop(): 3.2.队列3.2.2 队列的存储结构和实现链队列的C语言实现链队列基本操作的实现初始化入队出队 循环队列的C语言实现循环队列基本操作的实现初始化入队出队

---

3.1.栈

3.1.2 栈的存储结构和实现

顺序栈的C语言实现

// 初始容量 #define STACK_INIT_SIZE 100; // 容量的增量 #define STACKINCREMENT 10; typedef struct { ElemType *base; //栈底指针，栈构造前和销毁后为空 ElemType *top; //栈顶指针，指向栈顶元素的下一位置 int stacksize; //当前分配的栈的容量 } SqStack;

顺序栈的基本操作实现

InitStack(&S)

// 构造一个空栈 Status InitStack(SqStack &S) { // 栈底 S.base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType)); // 分配失败 if (!S.base) exit(OVERFLOW); // 栈顶=栈底，因为空栈没有元素 S.top = S.base; // 栈的容量 S.stacksize = STACK_INIT_SIZE; return OK; } //InitStack

StackEmpty()

top = base;

Push(e):

*top++ = e Status Push(SqStack &S, ElemType e) { // 满了 if (S.top – S.base == S.stacksize) return ERROR; // 栈顶 *S.top = e; // 栈顶扩展一个 S.top++; return OK; } //Push

Pop(e):

// 先自减一个，再取值 e = *--top

Gettop():

// 取建一个后的值 e = *(top-1)

3.2.队列

3.2.2 队列的存储结构和实现

链队列的C语言实现

// 链表结点类型 typedef struct QNode { QElemType data; struct QNode *next; } QNode, *QueuePtr; // 队列类型 typedef struct { QueuePtr front; // 队头指针 QueuePtr rear; // 队尾指针 } LinkQueue;

链队列基本操作的实现

初始化

// 构造一个空队列Q Status InitQueue(LinkQueue &Q) { // Q.front和Q.rear都指向链表的头结点，这就表示空队列 Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode)); // 分配失败 if (!Q.front) exit(OVERFLOW); // 链表头结点的指针域为空 Q.front->next = NULL; return OK; }

入队

// 将元素e插入到队列Q中 Status EnQueue(LinkQueue &Q, QElemType e) { // 链表结点 p = (QueuePtr)malloc(sizeof(QNode)); // 分配失败 if (!p) exit(OVERFLOW); // 赋值 p->data = e; // 指针域为空 p->next = NULL; // 将原来链表最后一个结点指向新增结点 Q.rear->next = p; // Q.rear指针更新，指向链表最后的元素，即新增元素 Q.rear = p; return OK; }

出队

// 若队列不空，则队头元素出队列，用e返回其值，返回OK；否则返回ERROR Status DeQueue(LinkQueue &Q, QElemType &e) { // 空队列 if (Q.rear == Q.front) return ERROR; // 获取队头元素（链表的第一个元素） p = Q.front->next; // 获取队头元素的值 e = p->data; // 链表的头结点的指针域更新，指向链表的第二个元素 Q.front->next = p->next; // 对于只有一个元素的队列（链表）出队时，那就变成了空队列（Q.rear = Q.front）。 if (Q.rear == p) Q.rear = Q.front; // 释放链表结点 free(p); return OK; }

循环队列的C语言实现

#define MAXSIZE 100 typedef struct { QElemType *base; int front; int rear; } SqQueue;

循环队列基本操作的实现

初始化

Status InitQueue(SqQueue &Q) { // 分配 Q.base = (QElemType *)malloc(MAXSIZE * sizeof(QElemType)); // 分配失败 if (!Q.base) exit(OVERFLOW); // 空对列，Q.front = Q.rear，都等于0 Q.front = Q.rear = 0; return OK; }

入队

// 将元素e插入队列Q的队尾 Status EnQueue(SqQueue &Q, QElemType e) { // 满了。因为Q.rear是从0开始的索引，所以要+1 if ((Q.rear + 1) % MAXSIZE == Q.front) return ERROR; // 直接填 Q.base[Q.rear] = e; // 加1 Q.rear = (Q.rear + 1) % MAXSIZE; return OK; }

出队

// 删除队列Q的队头元素并用e带回 Status DeQueue(SqQueue &Q, QElemType &e) { // 判空 if (Q.front == Q.rear) return ERROR; // 队首元素 e = Q.base[Q.front]; // 加1 Q.front = (Q.front + 1) % MAXSIZE; return OK; }