栈
栈的特点是先进后出，一张图简单介绍一下。
#include "stdio.h" #include "math.h" #include "stdlib.h" #define STACK_INIT_SIZE 20 #define STACKINCREMENT 10 typedef char ElemType; typedef struct{ ElemType *base; ElemType *top; int stacksize; }sqStack; void initStack(sqStack *s) { /*内存中开辟一段连续空间作为栈空间，首地址赋值给s->base*/ s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType)); if(!s->base) exit(0); /*分配空间失败*/ s->top = s->base; /*最开始，栈顶就是栈底*/ s->stacksize = STACK_INIT_SIZE; /*最大容量为STACK_INIT_SIZE */ } void Push(sqStack *s, ElemType e){ if(s->top - s->base >= s->stacksize){ /*栈满，追加空间*/ s->base = (ElemType *)realloc(s->base, (s->stacksize + STACKINCREMENT)*sizeof(ElemType)); if(!s->base) exit(0); /*存储分配失败*/ s->top = s->base + s->stacksize; s->stacksize = s->stacksize + STACKINCREMENT; /*设置栈的最大容量*/ } *(s->top) = e; /*放入数据*/ s->top++; } void Pop(sqStack *s , ElemType *e){ if(s->top == s->base) return;//栈里面没有元素了则返回 *e = *--(s->top); //删除栈顶的元素 } int StackLen(sqStack s){ return (s.top - s.base) ;//计算栈的长度 } void main() { ElemType c; sqStack s; int len , i , sum = 0; printf("Please input a Binary digit "); initStack(&s); /*创建一个栈，用来存放二进制字符串*/ /*输入0/1字符表示的二进制数，以#结束*/ scanf("%c",&c); while(c!='#')//遇到#则结束 { Push(&s,c);//输入一个压入一个 scanf("%c",&c); } len = StackLen(s); /*得到栈中的元素个数，即二进制数的长度*/ for(i=0;i<len;i++){ Pop(&s,&c); sum = (int)(sum + (c-48) * pow(2,i)); /*转换为十进制*/
//二进制转十进制的算法 } printf("Decimal is %d ",sum); }
队列
队列的特点是先进先出，就跟我们平常排队一个意思。
#include "stdio.h" #include "stdlib.h" typedef char ElemType; typedef struct QNode{ ElemType data; struct QNode *next; } QNode , *QueuePtr; typedef struct{ QueuePtr front; //队头指针 QueuePtr rear; //队尾指针 }LinkQueue; void initQueue(LinkQueue *q){ /*初始化一个空队列*/ q->front = q->rear = (QueuePtr)malloc(sizeof(QNode)); /*创建一个头结点，队头队尾指针 指向该结点*/ if( !q->front) exit(0); /*创建头结点失败*/ q->front->next = NULL; /*头结点指针域置NULL*/ } void EnQueue(LinkQueue *q, ElemType e){ QueuePtr p; p = (QueuePtr)malloc(sizeof(QNode)); /*创建一个队列元素结点*/ if( !q->front) exit(0); /*创建头结点失败*/ p->data = e;//元素节点写入数据 p->next = NULL;//元素节点的向后的指针指向空 q->rear ->next = p;//将队列中的队尾指针指向刚生成的元素节点 q->rear = p; } void DeQueue(LinkQueue *q, ElemType *e){ /*如果队列q不为空，删除q的队头元素，用e返回其值*/ QueuePtr p; if(q->front == q->rear) return; /*队列为空，返回*/ p = q->front->next;//队头给p *e = p->data;//取出来的队头的数据 q->front->next = p->next;//取出来的队头的下一个指向给新的队头的指向 if(q->rear == p) q->rear = q->front; /*如果队头就是队尾，则修改队尾指针*/ free(p); } /*测试函数*/ void main() { ElemType e; LinkQueue q; initQueue(&q); /*初始化一个队列q*/ printf("Please input a string into a queue "); scanf("%c",&e); while(e!='@'){ EnQueue(&q,e); /*向队列中输入字符串，以@表示结束*/ scanf("%c",&e); } printf("The string into the queue is "); while(q.front != q.rear){ /*将队列中的元素出队列，并打印在屏幕上*/ DeQueue(&q,&e); printf("%c",e); } printf(" "); }