本文主要是介绍dead--栈队列,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
创建链表
分别用头插法和尾插法创建并输出带附加头结点的单链表。
头插法是指每个新元素都插入到链表的最前面,即头结点和链表第一个元素之间;
尾插法指的是每个新元素都插入到链表的最后面。输入描述
输入:一组整数,以EOF为结束。
输出描述
输出:分别创建好的两个链表的元素。
用例输入 1
-4 5 8 -34 0 9 36 -1 77用例输出 1
-4 5 8 -34 0 9 36 -1 77 77 -1 36 9 0 -34 8 5 -4
#include <stdio.h>
#include <stdlib.h>typedef struct LNode
{int data;struct LNode *next;
}LNode, *Linklist;void create_LIFO(Linklist &L, int a[], int n); //头插法
void create_FIFO(Linklist &L, int a[], int n); //尾插法
void printLinklist(Linklist L); //输出链表
void DistroyLinklist(Linklist &L); //释放链表
int main()
{Linklist L1, L2;int a[100], x, n;n = 0;while (scanf("%d", &x)!=EOF){a[n++] = x; }create_FIFO(L2, a, n); //尾插法建表printLinklist(L2);create_LIFO(L1, a, n); //头插法建表printLinklist(L1);DistroyLinklist(L1); //释放链表 DistroyLinklist(L2);return 0;
}//函数功能:头插法创建链表,链表元素类型为int void create_LIFO(Linklist &L, int a[], int n)
{int i;Linklist p;L = (Linklist) malloc (sizeof (LNode));L-> next = NULL; // 先建立一个带头结点的单链表for (i = 0; i <= n-1; ++i) { p = (Linklist) malloc (sizeof (LNode)); // 生成新结点p -> data = a[i];p -> next = L -> next; L -> next = p; // 插入到表头 }
}//* 函数功能:尾插法创建链表,链表元素类型为int *void create_FIFO(Linklist &L, int a[], int n)
{Linklist r, p;int i;L = (Linklist)malloc(sizeof(LNode));L -> next = NULL; //先建立一个带头结点的单链表r = L; //r为表尾元素指针for(i = 0; i < n; ++i){p = (Linklist)malloc(sizeof(LNode)); //生成新结点p -> data = a[i]; //元素值p -> next = NULL; r -> next = p; r = p; //插入到表尾}}void printLinklist(Linklist L)
{LNode *p;p = L->next;while (p!=NULL){printf("%d ",p->data);p = p->next;}printf("\n");
}void DistroyLinklist(Linklist &L)
{Linklist p;p=L;while(L != NULL){L = L -> next; //后移L指针free(p); //释放当前结点p = L; //后移p指针}
}
单链表逆置
用尾插法创建一个带头结点的单链表,并将链表就地逆置后输出。
输入描述
输入:一组整数,以EOF为结束。
输出描述
输出:逆置后的链表元素。
用例输入 1
-4 5 8 -34 0 9 36 -1 77用例输出 1
77 -1 36 9 0 -34 8 5 -4
#include <stdio.h>
#include <stdlib.h>typedef struct LNode
{int data;struct LNode *next;
}LNode, *Linklist;void create_FIFO(Linklist &L); //尾插法建表
void printLinklist(Linklist L); //输出链表
void DistroyLinklist(Linklist &L);//销毁链表
void ReverseLinklist(Linklist &L);//逆置链表int main()
{Linklist head;create_FIFO(head);ReverseLinklist(head);printLinklist(head);DistroyLinklist(head);return 0;
}/******************************************************
* 函数名:reverseLinklist *
* 函数功能:逆置链表。 *
* 入口参数:链表头指针 L *
* 出口参数:链表头指针 L *
******************************************************/
//头插法
void ReverseLinklist(Linklist &L)
{int i;Linklist p, q;p = L->next; //p保存第一个结点的指针L->next = NULL; //L置成空表 while(p!=NULL){ q = p->next; //q保存下一结点的指针p->next = L->next; //将结点p插入到L链表的表头结点后面L->next = p; p = q; //p指针后移}
}/******************************************************
* 函数名:create_FIFO *
* 函数功能:尾插法创建链表,链表元素类型为int *
* 入口参数:链表头指针 L *
* 出口参数:链表头指针 L *
******************************************************/
void create_FIFO(Linklist &L)
{int num;Linklist r, p;L = (Linklist)malloc(sizeof(LNode));L -> next = NULL; //先建立一个带头结点的单链表r = L; //r为表尾元素指针while( scanf("%d", &num) != EOF ){p = (Linklist)malloc(sizeof(LNode)); //生成新结点p -> data = num; //元素值p -> next = NULL; r -> next = p; r = p; //插入到表尾}}/******************************************************
* 函数名:printLinklist *
* 函数功能:输出链表元素,链表元素类型为int *
* 入口参数:链表头指针 L *
* 出口参数:无 *
******************************************************/
void printLinklist(Linklist L)
{LNode *p;p = L->next;while (p!=NULL){printf("%d ",p->data);p = p->next;}printf("\n");
}
/******************************************************
* 函数名:DestroyLinklist *
* 函数功能:释放链表 *
* 入口参数:链表头指针 L *
* 出口参数:空指针 *
******************************************************/
void DistroyLinklist(Linklist &L)
{Linklist p;p=L;while(L != NULL){L = L -> next; //后移L指针free(p); //释放当前结点p = L; //后移p指针}
}
单链表插入结点
已知一个有序的单链表,输入一个整数,将其插入到单链表中,
使得链表仍然保持有序。输入描述
输入:首先输入一个n,表示单链表中结点的个数。接下来输入n个有序整数。然后输入
待插入的整数。输出描述
输出:插入整数后的链表。
用例输入 1
5 1 3 5 7 9 6用例输出 1
1 3 5 6 7 9
#include <stdio.h>
#include <stdlib.h>typedef struct LNode
{int data;struct LNode *next;
}LNode, *Linklist;void create_FIFO(Linklist &L); //尾插法建表
void printLinklist(Linklist L); //输出链表
void DistroyLinklist(Linklist &L);//销毁链表
void InsertLinklist(Linklist L, int x); //在链表插入中插入元素
int main()
{int x;Linklist head; create_FIFO(head); //创建链表scanf("%d", &x);InsertLinklist(head, x); //插入结点printLinklist(head); //输出插入后的链表DistroyLinklist(head); //销毁链表return 0;
}//在有序链表中插入元素x,保持链表的有序性void InsertLinklist(Linklist L, int x)
{LNode *p, *q, *s;p = L->next; q=L;//q始终保存p结点的前驱结点的指针 while (p!=NULL && p->data<x) //双指针法查找插入位置//while ( p->data<x && p!=NULL ) //双指针法查找插入位置{ q = p; p = p->next;}//在p之前、q之后插入新元素xs = (LNode *)malloc( sizeof(LNode) ); //动态分配空间s->data = x;s->next = q->next; //将s插入到q结点后边q->next = s;}//尾插法创建链表void create_FIFO(Linklist &L)
{int x, i, n;Linklist r, p; L = (Linklist)malloc(sizeof(LNode));L -> next = NULL; //先建立一个带头结点的单链表r = L; //r为表尾元素指针scanf("%d", &n); //输入数据个数for( i=1;i<=n; i++){scanf("%d", &x); //输入每个数p = (Linklist)malloc(sizeof(LNode)); //生成新结点p -> data = x; //元素值p -> next = NULL; r -> next = p; //插入到表尾r = p; //尾指针后移}}void printLinklist(Linklist L)
{LNode *p;p = L->next;while (p!=NULL){printf("%d ",p->data);p = p->next;}printf("\n");
}void DistroyLinklist(Linklist &L)
{Linklist p;p=L;while(L != NULL){L = L -> next; //后移L指针free(p); //释放当前结点p = L; //后移p指针}
}
单链表删除结点
已知一个非递减有序的单链表,输入一个整数,在链表中查找,若找到,请删除这个整数,链表始终保持有序(若有多个,只删除第一个)。
输入描述
输入:首先输入一个n,表示单链表中结点的个数。接下来输入n个有序整数。然后输入
待删除的整数。输出描述
输出:删除整数后的链表。
用例输入 1
5 1 3 5 7 9 7用例输出 1
1 3 5 9
#include <stdio.h>
#include <stdlib.h>typedef struct LNode
{int data;struct LNode *next;
}LNode, *Linklist;void create_FIFO(Linklist &L); //尾插法建表
void printLinklist(Linklist L); //输出链表
void DistroyLinklist(Linklist &L);//销毁链表
void DeleteLinklist(Linklist L, int x); //删除链表中的结点int main()
{Linklist head;int x;create_FIFO(head);scanf("%d", &x);DeleteLinklist(head, x);printLinklist(head);DistroyLinklist(head); //销毁链表return 0;
}/******************************************************
* 函数名:DeleteLinklist *
* 函数功能:在有序链表中删除元素x,保持链表的有序性 *
* 入口参数:链表头指针 L *
* 出口参数:链表头指针 L *
******************************************************/
//void DeleteLinklist(Linklist L, int x)
//{
// LNode *p, *q;
//
// p = L->next;
// q = L;
// while( p!=NULL && p->data!=x ) //双指针法查找待删除结点,q总是指向p的前驱
// {
// q = p;
// p = p->next;
// }
// //删除q之后元素x
// if( p!=NULL ) //若p!=NULL,即链表中存在值为x的元素
// {
// q->next = p->next;
// free(p);
// }
//}void DeleteLinklist(Linklist L, int x)
{LNode *p, *s;p = L;while( p->next!=NULL && p->next->data!=x ) //单指针法查找待删除结点的前驱{ p = p->next;}//删除p之后元素x if( p>next!=NULL ) //若p->next!=NULL,即链表中存在值为x的元素{s = p->next;p->next = p->next->next;free(s); }
}
/******************************************************
* 函数名:create_FIFO *
* 函数功能:尾插法创建链表,链表元素类型为int *
* 入口参数:链表头指针 L *
* 出口参数:链表头指针 L *
******************************************************/
void create_FIFO(Linklist &L)
{int x, i, n;Linklist r, p; L = (Linklist)malloc(sizeof(LNode));L -> next = NULL; //先建立一个带头结点的单链表r = L; //r为表尾元素指针scanf("%d", &n); //输入数据个数for( i=1;i<=n; i++){scanf("%d", &x); //输入每个元素值p = (Linklist)malloc(sizeof(LNode)); //生成新结点p -> data = x; //元素值p -> next = NULL; r -> next = p; //插入到表尾r = p; //尾指针后移}}/******************************************************
* 函数名:printLinklist *
* 函数功能:输出链表元素,链表元素类型为int *
* 入口参数:链表头指针 L *
* 出口参数:无 *
******************************************************/
void printLinklist(Linklist L)
{LNode *p;p = L->next;while (p!=NULL){printf("%d ",p->data);p = p->next;}printf("\n");
}
/******************************************************
* 函数名:DestroyLinklist *
* 函数功能:释放链表 *
* 入口参数:链表头指针 L *
* 出口参数:空指针 *
******************************************************/
void DistroyLinklist(Linklist &L)
{Linklist p;p=L;while(L != NULL){L = L -> next; //后移L指针free(p); //释放当前结点p = L; //后移p指针}
}/*
while( p->data==x ){q->next = p->next;free(p);p = q->next;}
*/
多项式相加
给定两个多项式,实现两个多项式相加算法。
输入描述
输入:第一行输入包含两个整数m, n,后续为m行和n行数据,m, n分别代表两个多项式的
项数;后续每一行代表多项式的项,包含a, b两个数据,表示该项的系数和指数。输出描述
输出:从较高指数到较低指数,依次输出求得的和。每行一项,格式与输入相同,但无需输
出项数,系数为0的项也不输出。用例输入 1
2 3 1 2 1 1 2 2 1 1 2 0用例输出 1
3 2 2 1 2 0
#include <stdio.h>
#include <stdlib.h>typedef struct LNode
{int coef; //多项式每项的系数int exp; //多项式每项的指数struct LNode * next; //指向下一项的指针
}LNode, *Linklist;
typedef Linklist Polynomial;void create_FIFO(Polynomial &L, int n); //尾插法
void mergeLinklist(Polynomial ha, Polynomial &hb, Polynomial &hc);//多项式相加
void printLinklist(Polynomial L); //输出链表
void DistroyLinklist(Linklist &L); //销毁链表int main()
{Polynomial La, Lb, Lc;int m, n;scanf("%d%d", &m, &n); create_FIFO(La, m);create_FIFO(Lb, n);mergeLinklist(La, Lb, Lc); //多项式相加printLinklist(Lc);DistroyLinklist(Lc);return 0;
}/******************************************************
* 函数名:create_FIFO *
* 函数功能:尾插法创建链表,链表元素类型为 *
* 入口参数:链表头指针 L *
* 出口参数:链表头指针 L *
******************************************************/
void create_FIFO(Polynomial &L, int n)
{Polynomial p, r;int i, coef, exp;L = (Polynomial)malloc( sizeof(LNode) );L -> next = NULL; //先建立一个带头结点的单链表r = L; //r为表尾元素指针for (i=0; i<n; i++){scanf("%d%d", &coef, &exp);p = (Polynomial)malloc( sizeof(LNode) ); p->coef = coef;p->exp = exp;p->next = NULL;r->next = p; //插入到表尾r = p; //尾指针后移}} /******************************************************
* 函数名:printLinklist *
* 函数功能:输出链表元素,链表元素类型为int *
* 入口参数:链表头指针 head *
* 出口参数:无 *
******************************************************/
void printLinklist(Polynomial L)
{Polynomial p;p = L->next;while (p!=NULL) {printf("%d %d\n",p->coef, p->exp);p = p->next;}
}/******************************************************
* 函数名:mergeLinklist *
* 函数功能:多项式相加 *
* 入口参数:两个多项式链表头指针 ha, hb *
* 出口参数:相加后的多项式链表头指针hc *
******************************************************/void mergeLinklist(Polynomial ha, Polynomial &hb, Polynomial &hc)
{ Polynomial p, q, r, q1, p1;int x;p = ha->next; q = hb->next;hc = r = ha;while (p!=NULL && q!=NULL){ if (p->exp > q->exp){ r->next = p; //a表指数大 r = p;p = p->next;}else if (p->exp < q->exp){ r->next = q; //b表指数大r = q;q = q->next;} else //两表指数相等{ p->coef = p->coef + q->coef; if (p->coef != 0) //系数不为0 { r->next = p;r = p;p = p->next; //p指针后移}else //系数为0{p1=p;p = p->next; //p后移free(p1); //释放a表中对应结点} //释放b表中对应结点q1 = q; q = q->next; free(q1); } }if (p!=NULL) r->next = p;else r->next = q;free(hb);
}/******************************************************
* 函数名:DestroyLinklist *
* 函数功能:释放链表 *
* 入口参数:链表头指针 L *
* 出口参数:空指针 *
******************************************************/
void DistroyLinklist(Linklist &L)
{Linklist p;p=L;while(L != NULL){L = L -> next; //后移L指针free(p); //释放当前结点p = L; //后移p指针}
}
小孩报数问题
有N个小孩围成一圈,给他们从1开始依次编号,现指定从第W个开始报数,报到第S个时,
该小孩出列,然后从下一个小孩开始报数,仍是报到S个出列,如此重复下去,直到所有的
小孩都出列(总人数不足S个时将循环报数),求小孩出列的顺序。输入描述
第一行输入小孩的人数N(N<=64)
接下来每行输入一个小孩的名字(人名不超过15个字符)
最后一行输入W,S (W < N),用逗号","间隔输出描述
按人名输出小孩按顺序出列的顺序,每行输出一个人名
用例输入 1
5 Xiaoming Xiaohua Xiaowang Zhangsan Lisi 2,3用例输出 1
Zhangsan Xiaohua Xiaoming Xiaowang Lisi
#include <stdio.h>
#include <string.h>
#include <stdlib.h>typedef struct LNode
{char name[16];struct LNode *next;
}LNode, *Linklist;void create_FIFO(Linklist &L, int n); //尾插法建循环链表
void Joseph(Linklist &L, int start, int m); //约瑟夫环int main()
{Linklist head;int n, w, s;scanf("%d", &n);getchar(); //接收输入n后面的回车create_FIFO(head,n);scanf("%d,%d", &w, &s);Joseph(head, w, s);return 0;
}/******************************************************
* 函数名:Joseph *
* 函数功能:输出出圈顺序 *
* 入口参数:链表头指针 L ,起始位置start 报数n *
* 出口参数:链表头指针 L *
******************************************************/
void Joseph(Linklist &L, int start, int m)
{LNode *p, *q;int i, k;p = L;for( i=1; i<start; i++ ){p = p->next;}while( p->next != p ) { for( k=1; k<m; k++ ){q = p ; p = p->next;}printf("%s", p->name);q->next = p->next;free(p);p = q->next;}printf("%s",p->name);free(p);
}/******************************************************
* 函数名:create_FIFO *
* 函数功能:尾插法创建链表,链表元素类型为int *
* 入口参数:链表头指针 L , 结点个数 n *
* 出口参数:链表头指针 L *
******************************************************/
void create_FIFO(Linklist &L, int n)
{int i;Linklist r, p; L = (Linklist)malloc(sizeof(LNode));fgets(L->name,16,stdin); //输入第一个元素值//scanf("%s", L->name);L -> next = L; //先建立一个结点的循环链表r = L; //r为表尾元素指针for( i=2;i<=n; i++){ p = (Linklist)malloc(sizeof(LNode)); //生成新结点fgets(p->name,16,stdin); //输入每个元素值 //scanf("%s", L->name);p -> next = L ; //创建循环链表 r -> next = p; //插入到表尾r = p; //尾指针后移}}
双向报数
编号为1,2,…,100的100位小朋友依次成一列。从1号开始1、2、3报数,凡报到3者出列,
直至报数到队列尾部。此后,又从队列尾开始反向1、2、3报数,凡报到3者同样出列。这样
反复顺逆报数,直至队列中剩下2个小朋友为止,问最后未出列的两个小朋友的编号为多少?
第50个出列的是哪一个?输入描述
此题无输入
用例输入 1
无用例输出 1
无提示
(Tip:可采用双向链表结构,为方便,除附加头结点之外,额外增加一个附加尾结点)
#include <stdio.h>
#include <stdlib.h>
#define N 100
#define M 3typedef struct LNode {int data;struct LNode *next;struct LNode *prior; //前驱指针
}LNode, *Linklist;void create_FIFO(Linklist &head, Linklist &tail, int n); //尾插法
void Joseph(Linklist head, Linklist tail, int m); //
void printList(Linklist head, Linklist tail);
int main()
{Linklist head, tail;create_FIFO(head,tail, N);Joseph(head, tail, M);printList(head,tail);return 0;
}void printList(Linklist head, Linklist tail)
{LNode *p;p = head->next;while (p!=tail){printf("%4d",p->data);p = p->next;}}
/******************************************************
* 函数名:Joseph *
* 函数功能:输出出圈顺序 *
* 入口参数:链表头指针 head *
* 出口参数:链表头指针 head *
******************************************************/
void Joseph(Linklist head, Linklist tail, int m)
{LNode *p, *q;int k, count=0, fiftieth;do {p = head->next;while (p!=tail) { for (k=1; p!=tail && k<m; k++){p = p->next;}if (p!=tail) {count++;if (count==50)fiftieth = p->data;q = p->prior;q->next = p->next;p->next->prior = q;free(p);p = q->next;}}p = tail->prior;while (p!=head) { for (k=1; p!=head && k<m; k++){p = p->prior;}if (p!=head) {count++;if (count==50)fiftieth = p->data;q = p->next;q->prior = p->prior;p->prior->next = q;free(p);p = q->prior;}}}while (head->next->next!=tail->prior);//printf("\n最后未出列的两位小盆友编号是:");printf("%d %d\n",head->next->data, tail->prior->data);
// printf("第50个出列的小盆友编号是:");printf("%d\n", fiftieth);
}/******************************************************
* 函数名:create_FIFO *
* 函数功能:尾插法创建双向链表,链表元素类型为int *
* 入口参数:链表头指针 head, 链表尾指针 tail *
* 出口参数:双向链附加头结点指针 head,链表尾指针 tail *
******************************************************/
void create_FIFO(Linklist &head, Linklist &tail, int n)
{LNode *p, *q;int i;head = (LNode *) malloc(sizeof(LNode)); //动态分配空间tail = (LNode *) malloc(sizeof(LNode)); //动态分配空间head->next = tail;head->prior = NULL;tail->next = NULL;tail->prior = head;p = head;for(i=1; i<=n; i++) {q = (LNode *)malloc(sizeof(LNode)); q->data = i;q->next = p->next;p->next->prior = q;p->next = q;q->prior = p;p = q;}
}
括号匹配
给定一串字符,不超过100个字符,可能包括括号、数字、字母、标点符号、空格,编程
检查这一串字符中的( ) ,[ ],{ }是否匹配。输入描述
输入:在一行中给出一行字符串,不超过100个字符,可能包括括号、数字、字母、标点
符号、空格。输出描述
输出:如果括号配对,输出yes,否则输出no。
用例输入 1
sin(10+20) {[}]用例输出 1
yes no
#include <stdio.h>
#define Maxsize 100typedef struct stack {char data[Maxsize];int top;
}Stack;void initStack(Stack &s);
int emptyStack(Stack s);
void push(Stack &s, char x);
char pop(Stack &s);
int judge(char str[]);int main()
{char str[Maxsize]; while(gets(str)){if (judge(str))printf("yes\n");elseprintf("no\n");} return 0;
}int judge(char str[])
{Stack s;int i;char a, b;initStack(s);i = 0;while (str[i]!='\0'){if (str[i]=='(' || str[i]=='[' ||str[i]=='{') //左边括号,则压栈 push(s, str[i]);else if (str[i] == ')') //右边括号 {if (emptyStack(s)) //栈空,说明之前没有对应的左括号 return 0;a = pop(s);if (a!='(') //弹出的左括号跟当前的右括号不配对 return 0;}else if (str[i] == ']'){if (emptyStack(s))return 0;a = pop(s);if (a!='[')return 0;}else if (str[i] == '}'){if (emptyStack(s))return 0;a = pop(s);if (a!='{')return 0;}i++; }if (emptyStack(s))return 1;else return 0;
}int emptyStack(Stack s)
{return s.top == 0;
}void initStack(Stack &s)
{s.top = 0;
}void push(Stack &s, char x)
{s.data[s.top++] = x;
}char pop(Stack &s)
{return s.data[--s.top];
}
看病要排队
看病要排队这个是地球人都知道的常识。
不过经过细心的0068的观察,他发现了医院里排队还是有讲究的。 0068所去的医院有三个医生(汗,这么少)
同时看病。而看病的人病情有轻重,所以不能根据简单的先来先服务的原则。所以医院对每种病情规定了10种
不同的优先级。级别为10的优先权最高,级别为1的优先权最低。医生在看病时,则会在他的队伍里面选择一个
优先权最高的人进行诊治。如果遇到两个优先权一样的病人的话,则选择最早来排队的病人。
现在就请你帮助医院模拟这个看病过程。输入描述
输入数据包含多组测试,请处理到文件结束。
每组数据第一行有一个正整数N(0<N<2000)表示发生事件的数目。
接下来有N行分别表示发生的事件。
一共有两种事件:
1:“IN A B”,表示有一个拥有优先级B的病人要求医生A诊治。(0<A<=3,0<B<=10)
2:“OUT A”,表示医生A进行了一次诊治,诊治完毕后,病人出院。(0<A<=3)输出描述
对于每个"OUT A"事件,请在一行里面输出被诊治人的编号ID。如果该事件时无病人需要诊治,则输出"EMPTY"。 诊治人的编号ID的定义为:在一组测试中,"IN A B"事件发生第K次时,进来的病人ID即为K。从1开始编号。
用例输入 1
7 IN 1 1 IN 1 2 OUT 1 OUT 2 IN 2 1 OUT 2 OUT 1 2 IN 1 1 OUT 1用例输出 1
2 EMPTY 3 1 1
#include <stdio.h>
#include <stdlib.h>
#include <string.h>typedef struct qdata
{int prior;int patient;
} QData;
typedef struct qnode
{QData data;struct qnode * next;
} QNode, *LinkQueue;int emptyQueue(LinkQueue Q);
QData DeQueue(LinkQueue Q);
void EnQueue(LinkQueue Q, QData x);int main()
{char cmd[4];QData x;LinkQueue Q[4];int i, n, k, doctor;while (scanf("%d", &n)!=EOF){getchar();//初始化空队列for (i=1; i<4; i++){Q[i] = (QNode *)malloc(sizeof(QNode));Q[i]->next = NULL;}for (i=0, k=1; i<n; i++){scanf("%s %d", cmd, &doctor); //读入命令和医生编号if (strcmp(cmd,"IN")==0){scanf("%d", &x.prior); //读入优先级x.patient = k; //病人编号EnQueue(Q[doctor], x); //病人按优先级进入队列k++;}else{if (emptyQueue(Q[doctor])) //队列为空printf("EMPTY\n");else{x = DeQueue(Q[doctor]); //队首病人出队printf("%d\n", x.patient); //输出病人编号}}}}return 0;
}//进队列,按优先级
void EnQueue(LinkQueue Q, QData x)
{QNode *p,*r;p = Q;while(p->next&&p->next->data.prior>=x.prior){p = p->next;}r = (QNode *)malloc(sizeof(QNode));r->data = x;r->next = p->next;p->next = r;
}//出队列
QData DeQueue(LinkQueue Q)
{QNode * p;QData x;p = Q->next;Q->next = p->next;x = p->data;free(p);return x;
}//判断队列是否为空
int emptyQueue(LinkQueue Q)
{return Q->next==NULL;
}
简单计算器
Roliygu曾经沉迷于SICP大半个学期,在沉迷期间,他对LISP语言的算术表达式很感兴趣,于是类比写出了一种后缀表达式。
后缀表达式是指的将两个操作数之间的操作符移到两个操作数之后的表达式。比如原来的表达式为(1-2)*(4+5)=-9,写成后缀表达式就成了
1 2 - 4 5 + *
输入:
第一行输入n,0<n<10,表示有n行表达式
接下来的n行,每行一个后缀表达式,保证表达式合法,且不使用除四则运算之外的操作。不会输入负数
输出:
输出n行,每行为输入表达式的最终结果,结果保留两位小数,不需要高精度数。
注意:有多位数输入和小数输入
#include <stdio.h>
#define Maxsize 50typedef struct stack
{float data[Maxsize];int top;
}Stack;void initStack(Stack &s);
void push(Stack &s, float x);
float pop(Stack &s);int main()
{Stack s;char str[80]; int i, j, n, ten;float a, b;scanf("%d",&n); getchar();for (i=0; i<n; i++){initStack(s);//gets(str);fgets(str, 80, stdin);j = 0;while (str[j]!='\0'&&str[j]!='\n'){//整数部分if (str[j]>='0' && str[j]<='9'){a = 0;while(str[j] && (str[j]>='0' && str[j]<='9')){a = a*10 + str[j]-'0';j++;}push(s, a);}//小数部分else if (str[j]=='.'){j++; //跳过小数点b = 0;ten = 1;while (str[j] && (str[j]>='0' && str[j]<='9')){b = b*10 + str[j]-'0';ten = ten * 10;j++;}a = pop(s);a = a + b / ten;push (s, a);}//跳过空格else if (str[j]==' '){j++;}//遇到运算符else{b = pop(s);a = pop(s);switch(str[j]){case '+': a = a + b; break;case '-': a = a - b; break;case '*': a = a * b; break;case '/': a = a / b; break; }push(s,a);j++;}}a = pop(s);printf("%.2f\n", a);}return 0;
}void initStack(Stack &s)
{s.top = 0;
}void push(Stack &s, float x)
{s.data[s.top++] = x;
}float pop(Stack &s)
{return s.data[--s.top];
}
这篇关于dead--栈队列的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!