PPC的C/C++和人工智能学习笔记
每一篇学习笔记,都只是为了更好地掌握和理解

C语言基础(19)_栈与队列

C语言基础中的简单数据结构,栈与队列及其应用。

用数组和单链表分别实现栈与队列,最后用栈操作做一个进制转换的练习。

 

栈的特点:先进后出

队列的特点:先进先出

数组实现栈:

/********************************
Copyright(C) 2017,www.vsppc.com
FileName:数组_栈.c
Author:ppc
Version:
Date:2017-03-08
Description:用数组实现栈的基本操作
Others:
FunctionList:int InitStack(LPSTACK S); //初始化栈
 void DestroyStack(LPSTACK S); //销毁栈
 void PrintStack(const LPSTACK S); //打印栈内容
 int PushStack(LPSTACK S,int data); //压栈
 int PopStack(LPSTACK S, int* data); //出栈
 int IsEmpty(const LPSTACK S); //是否空
 int GetTop(const LPSTACK S, int* data); //获取栈顶元素
Histroy:
********************************/
#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 20 //数组的最大长度 20
typedef struct stack {
 int *arr; //栈内存
 int top; //栈顶标志
}STACK,*LPSTACK;

int InitStack(LPSTACK S); //初始化栈
void DestroyStack(LPSTACK S); //销毁栈
void PrintStack(const LPSTACK S); //打印栈内容
int PushStack(LPSTACK S,int data); //压栈
int PopStack(LPSTACK S, int* data); //出栈
int IsEmpty(const LPSTACK S); //是否空
int GetTop(const LPSTACK S, int* data); //获取栈顶元素
int main() {
 LPSTACK S = (LPSTACK)malloc(sizeof(STACK)); //为栈结构创建内存(没有创建栈的内存空间)
 if (NULL == S) return 0; //创建栈结构失败
 if (!InitStack(S)) return 0; //初始化栈失败
 PrintStack(S);
 if (IsEmpty(S)) printf("IsEmpty:空\n");
 else printf("IsEmpty:非空\n");
 printf("入栈:\n");
 PushStack(S, 10);
 PushStack(S, 20);
 PrintStack(S);
 if (IsEmpty(S)) printf("IsEmpty:空\n");
 else printf("IsEmpty:非空\n");
 int a = 0;
 GetTop(S, &a);
 printf("GetTop=%d\n", a);
 PrintStack(S);
 PopStack(S, &a);
 printf("出栈:%d\n", a);
 PrintStack(S);
 PopStack(S, &a);
 printf("出栈:%d\n", a);
 PrintStack(S);
 if(!PopStack(S, &a))
 printf("出栈:失败\n");
 PrintStack(S);
 DestroyStack(S); //销毁栈
 free(S);
 system("pause");
 return 0;
 //输出:打印:空栈
 //IsEmpty : 空
 //入栈:
 //打印:10->20->
 //IsEmpty : 非空
 //GetTop = 20
 //打印:10->20->
 //出栈:20
 //打印:10->
 //出栈:10
 //打印:空栈
 //出栈:失败
 //打印:空栈
}

int InitStack(LPSTACK S) { //初始化栈
 S->arr = (int*)malloc(sizeof(int)*MAX_SIZE); //创建栈内存
 if (NULL == S->arr) return 0;
 S->top = -1; //初始化 栈顶 =-1
 return 1;
}
void DestroyStack(LPSTACK S) { //销毁栈
 if (NULL != S->arr) {
 free(S->arr);
 S->arr = NULL;
 }
}
void PrintStack(const LPSTACK S) { //打印栈内容
 printf("打印:");
 if (NULL == S->arr || S->top == -1) {
 printf("空栈\n");
 return;
 }
 for (int i = 0; i <= S->top; i++) 
 printf("%d->", S->arr[i]);
 printf("\n");
}
int PushStack(LPSTACK S,int data) { //压栈
 if (NULL == S->arr || S->top == MAX_SIZE - 1) return 0; //栈无内存或栈满
 S->arr[++S->top] = data;
 return 1;
}
int PopStack(LPSTACK S, int* data) { //出栈
 if (NULL == S->arr || S->top == - 1) return 0; //栈无内存或栈空
 *data = S->arr[S->top--];
 return 1;
}
int IsEmpty(const LPSTACK S) { //是否空
 return S->top == -1;
}
int GetTop(const LPSTACK S, int* data) { //获取栈顶元素
 if (S->top < 0) return 0;
 *data = S->arr[S->top];
 return 1;
}

数组实现循环队列:

/********************************
Copyright(C) 2017,www.vsppc.com
FileName:数组_队列.c
Author:ppc
Version:
Date:2017-03-08
Description:用数组实现循环队列的基本操作
Others:
FunctionList:int InitQueue(LPQUEUE Q); //初始化队列
 void DestroyQueue(LPQUEUE Q); //销毁队列
 void PrintQueue(const LPQUEUE Q); //打印队列
 int PushQueue(LPQUEUE Q, int data); //插入队列
 int PopQueue(LPQUEUE Q, int* data); //出队列
Histroy:
********************************/
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 5 //队列最大元素值
typedef struct queqe {
 int* arr; //队列内存
 int front; //队列头,出数据 从这里出
 int rear; //队列尾,入数据 从这里入
 int count; //当前队列的有效数据元素个数
}QUEUE,*LPQUEUE;
int InitQueue(LPQUEUE Q); //初始化队列
void DestroyQueue(LPQUEUE Q); //销毁队列
void PrintQueue(const LPQUEUE Q); //打印队列
int PushQueue(LPQUEUE Q, int data); //插入队列
int PopQueue(LPQUEUE Q, int* data); //出队列
int main() {
 LPQUEUE Q = (LPQUEUE)malloc(sizeof(QUEUE));
 if (NULL == Q) return 0; 
 if (InitQueue(Q) == 0) return 0; //初始化失败
 PrintQueue(Q);
 printf("Push 10\n");
 PushQueue(Q, 10);
 printf("Push 20\n");
 PushQueue(Q, 20);
 printf("Push 30\n");
 PushQueue(Q, 30);
 printf("Push 40\n");
 PushQueue(Q, 40);
 printf("Push 50\n");
 PushQueue(Q, 50);
 printf("Push 60\n");
 PushQueue(Q, 60);
 PrintQueue(Q);
 int e = 0;
 PopQueue(Q, &e);
 printf("pop=%d\n", e);
 PrintQueue(Q);
 PopQueue(Q, &e);
 printf("pop=%d\n", e);
 PrintQueue(Q);
 printf("Push 60\n");
 PushQueue(Q, 60);
 PrintQueue(Q);
 PopQueue(Q, &e);
 printf("pop=%d\n", e);
 PrintQueue(Q);
 PopQueue(Q, &e);
 printf("pop=%d\n", e);
 PrintQueue(Q);
 PopQueue(Q, &e);
 printf("pop=%d\n", e);
 PrintQueue(Q);
 PopQueue(Q, &e);
 printf("pop=%d\n", e);
 PrintQueue(Q);
 if(!PopQueue(Q, &e))
 printf("pop nonthing\n");
 PrintQueue(Q);
 DestroyQueue(Q);
 free(Q);
 Q = NULL;
 system("pause");
 return 0;
 //输出:打印:空队列
 //Push 10
 //Push 20
 //Push 30
 //Push 40
 //Push 50
 //Push 60
 //打印:10->20->30->40->50->
 //pop = 10
 //打印:20->30->40->50->
 //pop = 20
 //打印:30->40->50->
 //Push 60
 //打印:30->40->50->60->
 //pop = 30
 //打印:40->50->60->
 //pop = 40
 //打印:50->60->
 //pop = 50
 //打印:60->
 //pop = 60
 //打印:空队列
 //pop nonthing
 //打印:空队列
}

int InitQueue(LPQUEUE Q) { //初始化队列
 if (NULL == Q) return 0;
 Q->arr = (int*)malloc(sizeof(int)*MAX_SIZE); //分配队列内存
 if (NULL == Q->arr) return 0;
 Q->front = Q->rear = Q->count = 0;
 return 1;
}
void DestroyQueue(LPQUEUE Q) { //销毁队列
 if (NULL == Q->arr) return;
 free(Q->arr);
 Q->arr = NULL;
}
void PrintQueue(const LPQUEUE Q) { //打印队列
 printf("打印:");
 if (Q == NULL || Q->count == -0 || Q->front == Q->rear) {
 printf("空队列\n");
 return;
 }
 if (Q->rear > Q->front) { //尾在后(循环队列)
 for (int i = 0; i < Q->rear - Q->front; i++)
 printf("%d->", Q->arr[i + Q->front]);
 }
 else if (Q->rear < Q->front) { //尾在前了,先读到最后,然后再读前面的
 for (int i = Q->front; i < MAX_SIZE; i++)
 printf("%d->", Q->arr[i]);
 for (int i = 0; i < Q->rear; i++)
 printf("%d->", Q->arr[i]);
 }
 printf("\n");
}
int PushQueue(LPQUEUE Q, int data) { //插入队列
 if (NULL == Q || NULL == Q->arr) return 0;
 if (Q->count >= MAX_SIZE) return 0;
 if (Q->rear == MAX_SIZE) Q->rear = 0;
 Q->arr[Q->rear] = data;
 ++Q->rear;
 ++Q->count;
 return 1;
}
int PopQueue(LPQUEUE Q, int* data) { //出队列
 if (NULL == Q || NULL == Q->arr) return 0;
 if (Q->count == 0) return 0;
 *data = Q->arr[Q->front];
 if (Q->front+1 == MAX_SIZE) Q->front = 0;
 else ++Q->front;
 --Q->count;
 return 1;
}

用单链表实现栈操作:

//单链表_栈.c
//用单链表来实现栈的操作
//栈是先进后出,用链表的头插法 和 头取法,就可以实现这个功能

#include <stdio.h>
#include <malloc.h>
typedef struct List {
 int data;
 struct List * pNext;
}LIST,*LPLIST;

LPLIST CreateNode(int data) { //创建节点
 LPLIST p = (LPLIST)malloc(sizeof(LIST));
 if (NULL == p) abort();
 p->data = data;
 p->pNext = NULL;
 return p;
}
void DestroyList(LPLIST p) { //销毁节点
 while (p!=NULL) {
 LPLIST q = p->pNext;
 free(p);
 p = q;
 }
}
void PrintList(LPLIST p) { //打印
 if (p == NULL || p->pNext == NULL) {
 printf("空LIST\n");
 return;
 }
 p = p->pNext;
 while (p) {
 printf("%d,", p->data);
 p = p->pNext;
 }
 printf("\n");
}
int Push(LPLIST p,int data) { //头插,入栈操作
 if (NULL == p) return 0; //失败
 LPLIST q = CreateNode(data);
 q->pNext = p->pNext;
 p->pNext = q;
 return p; //返回成功
}
int Pop(LPLIST p, int * e) { //头删,出栈操作
 if (p == NULL || p->pNext == NULL) return 0;//失败
 *e = p->pNext->data;
 LPLIST q = p->pNext;
 p->pNext = p->pNext->pNext;
 free(q);
 return 1; //返回成功
}

int main() {
 LPLIST pList = CreateNode(0); //创建1个节点,作为头结点
 Push(pList, 1);
 Push(pList, 2);
 Push(pList, 3);
 Push(pList, 4);
 Push(pList, 5); //以 1 2 3 4 5的次序入栈
 PrintList(pList);
 int data;
 while (Pop(pList, &data)) {
 printf("pop:%d\n", data);//以 5 4 3 2 1的次序出栈
 }
 PrintList(pList);
 DestroyList(pList);
 return 0;
}

用单链表实现队列操作:

//单链表_队列.c
//用单链表实现队列
//队列是先进先出,列表的 头插,尾删 就是队列
#include <stdio.h>
#include <malloc.h>
typedef struct List {
 int data;
 struct List * pNext;
}LIST, *LPLIST;

LPLIST CreateNode(int data) { //创建节点
 LPLIST p = (LPLIST)malloc(sizeof(LIST));
 if (NULL == p) abort();
 p->data = data;
 p->pNext = NULL;
 return p;
}
void DestroyList(LPLIST p) { //销毁节点
 while (p != NULL) {
 LPLIST q = p->pNext;
 free(p);
 p = q;
 }
}
void PrintList(LPLIST p) { //打印
 if (p == NULL || p->pNext == NULL) {
 printf("空LIST\n");
 return;
 }
 p = p->pNext;
 while (p) {
 printf("%d,", p->data);
 p = p->pNext;
 }
 printf("\n");
}
int Push(LPLIST p, int data) { //头插,入队操作
 if (NULL == p) return 0; //失败
 LPLIST q = CreateNode(data);
 q->pNext = p->pNext;
 p->pNext = q;
 return p; //返回成功
}
int Pop(LPLIST p, int * e) { //尾删,出队操作
 if (p == NULL || p->pNext == NULL) return 0;//失败
 LPLIST q = p->pNext; //p在前面,q在后面
 while (q->pNext) {
 p = p->pNext;
 q = q->pNext;
 }
 *e = q->data;
 p->pNext = NULL;
 free(q);
 return 1; //返回成功
}

int main() {
 LPLIST pList = CreateNode(0); //创建1个节点,作为头结点
 Push(pList, 1);
 Push(pList, 2);
 Push(pList, 3);
 Push(pList, 4);
 Push(pList, 5); //以 1 2 3 4 5的次序入队
 PrintList(pList);
 int data;
 while (Pop(pList, &data)) {
 printf("pop:%d\n", data); //以 1 2 3 4 5的次序出队
 }
 PrintList(pList);
 DestroyList(pList);

 return 0;
}

 

用栈操作实现进制转换:

/********************************
Copyright(C) 2017,www.vsppc.com
FileName:进制转换.c
Author:ppc
Version:
Date:2017-03-08
Description:用栈操作进行进制转换
Others:
FunctionList:
Histroy:
********************************/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 33 //数组的最大长度 33
typedef struct stack {
 char *arr; //栈内存
 int top; //栈顶标志
}STACK, *LPSTACK;

int Push(LPSTACK pS,char data);
int Pop(LPSTACK pS, char* data);

int main() {
 STACK S;
 LPSTACK pS = &S;
 pS->arr = (char*)malloc(sizeof(char)*MAX_SIZE);
 if (NULL == pS->arr) return -1;
 pS->top = -1;
 int jinzhi = 2, num = 0; //转换为的进制 和输入的10进制数
 while (1) {
 printf("请输入10进制的数和需要转为的进制(2,8,16):\n");
 printf("输入9999退出。\n");
 scanf("%d%d", &num, &jinzhi);
 if (num == 9999) break;
 int tmp = num;
 char str[17];
 switch (jinzhi) {
 case 2:
 strcpy(str, "01");
 break;
 case 8:
 strcpy(str, "01234567");
 break;
 case 16:
 strcpy(str, "0123456789ABCDEF");
 break;
 default:
 strcpy(str, "0123456789"); //默认还是转为10进制
 }
 while (tmp) {
 int yu = tmp % jinzhi;
 Push(pS, str[yu]);
 tmp = tmp / jinzhi;
 }

 char out[50];
 int i = 0, total = pS->top;
 for (i = 0; i <= total; i++)
 Pop(pS, out + i);
 out[i] = '\0';
 printf("%d的%d进制结果是:%s\n", num, jinzhi, out);
 }
 free(pS->arr);
 pS->arr = NULL;
 system("pause");
 return 0;
 //请输入10进制的数和需要转为的进制(2, 8, 16):
 //输入9999退出。
 //99 2
 //99的2进制结果是:1100011
 //请输入10进制的数和需要转为的进制(2, 8, 16):
 //输入9999退出。
 //99 8
 //99的8进制结果是:143
 //请输入10进制的数和需要转为的进制(2, 8, 16):
 //输入9999退出。
 //99 16
 //99的16进制结果是:63
 //请输入10进制的数和需要转为的进制(2, 8, 16):
 //输入9999退出。
 //1099 16
 //1099的16进制结果是:44B
 //请输入10进制的数和需要转为的进制(2, 8, 16):
 //输入9999退出。
 //9999 2
 //请按任意键继续. . .
}
int Push(LPSTACK pS,char data) {
 if (pS->top >= MAX_SIZE - 1) return 0;
 pS->arr[++pS->top] = data;
 return 1;
}
int Pop(LPSTACK pS, char* data) {
 if (pS->top == -1) return 0;
 *data = pS->arr[pS->top--];
 return 1;
}

 

(2017-03-08 www.vsppc.com)

学习笔记未经允许不得转载:PPC的C/C++和人工智能学习笔记 » C语言基础(19)_栈与队列

分享到:更多 ()

评论 71

评论前必须登录!