黑马程序员技术交流社区

标题: C语言算法系列---1.队列和栈 [打印本页]

作者: lorem 时间: 2016-2-26 19:23
标题: C语言算法系列---1.队列和栈
#include<stdlib.h>
#include<stdio.h>
typedef int SElemType;  //声明栈元素类型为int
typedef int Status; //函数返回值的类型为int
#define MAXSIZE 20  //栈的容量

typedef struct
{
SElemType data[MAXSIZE];
int top;
}SqStock ;

Status InitStock(SqStock *);  //栈初始化函数声明
Status push(SqStock *,SElemType);  //入栈函数声明
Status pop(SqStock *,SElemType *);  //出栈函数声明
void Conversion();  //这是当时测验的一个转换函数，顺带贴了

/************函数区*******/
//0.初始化
Status InitStock(SqStock *s){
int StockDataArray[MAXSIZE];
for(int i=0;i<MAXSIZE;i++){
      s->data[i]='\0';
}
s->top=-1;
return 1;
}

//入栈
Status push(SqStock *s,SElemType e){
if(s->top==MAXSIZE-1){ //已达最大容量
      return 0;
};
s->top++;
s->data[s->top]=e;
return 1;

}

//出栈
Status pop(SqStock *s,SElemType *e){
if(s->top==-1){//已到栈底
      return 0;
}
*e=s->data[s->top--];
return 1;
}

//转化为8进制
void Conversion(){
int N;
SqStock *s;
s=(SqStock *)malloc( sizeof( SqStock)); //申请内存空间
InitStock(s);
printf("请输入一个十进制整数：");
scanf("%d",&N);
while(N){

      push(s,N%8);
      N=N/8;
}
int e;
while(s->top!=-1){
      pop(s,&e);
      printf("%d",e);
}
}
/************函数区*******/
上述代码思路：利用数组来实现栈的功能，平时用的时候完全直接使用数组和一个int型的top，其值为当前栈顶元素所在的下标。至于如何处理栈溢出的问题，要么将容量设置大一点，要么在快要溢出的时候动态申请一些内存空间。当然，肯定还有其他的方法，自己要有探索精神哦。

接着是队列的一些基本功能的算法：
1 #include <stdio.h>
  2 #include <tchar.h>
  3 #include<stdlib.h>
  4 #include<math.h>
  5 #include<time.h>
  6
  7
  8 #define MAXSIZE 20
  9
10 typedef int QElemType;
11 typedef int Status;
12 //使用循环队列
13 typedef struct {
14
15    QElemType Data[MAXSIZE];
16    int front;
17    int rear;
18 }XHQueue;
19
20 int getRand(int ,int );//当时测试随机数的，两个变量是上下限
21 void InitQueue(XHQueue *);  //初始化队列
22 Status EnQueue(XHQueue *,QElemType ); //入队
23 Status DeQueue(XHQueue *,QElemType *);//出队
24 Status IsEmpty(XHQueue *); //判断是否为空
25
26 /*****函数区***/
27 //产生随机函数
28 int getRand(int MinSize,int MMaxSize){
29    time_t t;
30    int r;
31    srand((unsigned)time(&t));
32    r=rand()%(MMaxSize-MinSize+1)+MinSize;
33    return r;
34 }
35
36
37 //队列初始化
38 void InitQueue(XHQueue *Q){
39    Q->front=0;
40    Q->rear=0;
41
42
43 }
44
45 //入队
46
47 Status EnQueue(XHQueue *Q,QElemType E){
48
49    if((Q->rear+1)%MAXSIZE ==Q->front)//队列已满
50    {
51       return 0;
52    }
53    Q->Data[Q->rear]=E;
54    Q->rear=(Q->rear+1)%MAXSIZE;
55    return 1;
56 }
57
58 //出队
59 Status DeQueue(XHQueue *Q,QElemType *E){ //至于为什么是*E,去看看c的传值与传址，在使用的时候要写成DeQueue（Q ,&变量），传址符不能少
60    if(Q->front==Q->rear){//队列已空
61       return 0;
62    }
63    *E=Q->Data[Q->front];
64    Q->front=(Q->front+1)%MAXSIZE;
65
66    return 1;
67
68 }
69
70 //判断是否为空
71 Status IsEmpty(XHQueue *Q){
72    if(Q->front==Q->rear){
73       return 1;
74    }
75    return 0;
76
77 }
78 /*****函数区***/
79
80 int _tmain(int argc, _TCHAR* argv[])
81 {
82    /*int r,r1;
83    r=getRand(20,35);
84    r1=getRand(20,40);
85    printf("%d %d\n",r,r1);*/
86
87    int Re;
88    XHQueue *Q;
89    Q=(XHQueue *)malloc(sizeof(XHQueue));
90    InitQueue(Q);
91    EnQueue(Q,2);
92    EnQueue(Q,0);
93    EnQueue(Q,1);
94    EnQueue(Q,5);
95    while(!IsEmpty(Q)){
96       DeQueue(Q,&Re);
97       printf("%d",Re);
98    }
99
100    system("pause");
101    return 0;
代码说明：原谅我比较懒。。好多都原封不动的贴上来了= =！从思路上来说，现实生活中的队列都是走一个，所有人往前移，但在程序中也写成这样，也不是不可以，但在队列比较长的时候，光移动这些元素就会花费大量的时间，是非常不划算的，所以，为了避免这样大规模的移动，使用循环队列的思想，即队头走了就走了，我们把队头指针往后移一个，队尾来人了，发现已经站不了了，那就去前面看看，前面说不定就能站呢。

   恩暂时就贴这么多啦~改天有空再贴些其他的~

作者: 黑马公公007 时间: 2016-2-26 19:31
写的很好很认真，总结的也很到位，日后定成为一名优秀的程序员。楼主加油

作者: ICHP 时间: 2016-2-26 19:39
赞，邦邦达。。。

作者: lorem 时间: 2016-2-26 19:44

ICHP 发表于 2016-2-26 19:39
赞，邦邦达。。。

谢谢亲

作者: dx206 时间: 2016-2-27 20:53
赞一个，虽然没看太懂，请问这是在oc阶段学的吗？

作者: Eric_Jia 时间: 2016-3-1 17:17
应该再文字描述一下栈和队列的区别会更好，加油！！！

作者: 海洋深处的8爪鱼 时间: 2016-3-1 19:02
我去好复杂，表示看不懂

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2