黑马程序员技术交流社区

标题: 数据结构试验——栈与队列 [打印本页]

---

作者: Stars√永恒    时间: 2014-2-19 15:56
标题: 数据结构试验——栈与队列

1. #include<iostream>
   
2. using namespace std;
   
3. typedef int Elemtype;
   
4. typedef struct snode{
   
5.     Elemtype data;
   
6.     struct snode *next;
   
7. }Linkstack;
   
8. void Initstack(Linkstack **top)
   
9. {*top=(Linkstack *)malloc(sizeof(Linkstack));
   
10. (*top)->next=NULL;
    
11. cout<<"栈初始化成功!\n";
    
12. }
    
13. int push(Linkstack **top,Elemtype x)
    
14. {
    
15.     Linkstack *s;
    
16.     s=(Linkstack*)malloc(sizeof(Linkstack));
    
17.     s->data=x;
    
18.     s->next=(*top)->next;
    
19.     (*top)->next=s;
    
20.     return 1;
    
21. 
    
22. }
    
23. int Empty(Linkstack **top)
    
24. {return ((*top)->next==NULL?1:0);}
    
25. int pop(Linkstack **top,Elemtype *x)
    
26. {
    
27.     Linkstack *s;
    
28.     if(Empty(top))
    
29.     {
    
30.         cout<<"\n 栈为空!";
    
31.         return 0;
    
32.     }
    
33.         s=(*top)->next;
    
34.         *x=s->data;
    
35.         (*top)->next=s->next;
    
36.         free(s);
    
37.         return 1;
    
38. }
    
39. //队列功能的实现
    
40. typedef struct qnode{
    
41.     Elemtype data;
    
42.     struct qnode *next;
    
43. }qtype;
    
44. typedef struct sqtr{
    
45.     qtype *front,*rear;
    
46. }squeue;
    
47. void Initqueue(squeue *LQ)
    
48. {
    
49.     qtype *p;
    
50.     p=(qtype *)malloc(sizeof(qtype));
    
51.     p->next=NULL;
    
52.     LQ->front=LQ->rear=p;
    
53.     cout<<"队列初始化成功!\n";
    
54. }
    
55. int Enqueue(squeue *LQ,Elemtype x)
    
56. {
    
57.     qtype *s;
    
58.     s=(qtype *)malloc(sizeof(qtype));
    
59.     s->data=x;
    
60.     s->next=LQ->rear->next;
    
61.     LQ->rear->next=s;
    
62.     LQ->rear=s;
    
63.     return 1;
    
64. }
    
65. int Empty(squeue *LQ)
    
66. {return(LQ->front==LQ->rear?1:0);}
    
67. int Outqueue(squeue *LQ,Elemtype *x)
    
68. {
    
69.     qtype *p;
    
70.     if(Empty(LQ))
    
71.     {
    
72.         cout<<"队列为空!";
    
73.         return 0;
    
74.     }
    
75.     p=LQ->front->next;
    
76.     *x=p->data;
    
77.     LQ->front->next=p->next;
    
78.     if(LQ->front->next==NULL)
    
79.         LQ->rear=LQ->front;
    
80.     free(p);
    
81.     return 1;
    
82. }
    
83. 
    
84. void Dectoothers(int n,int b)
    
85. {
    
86.     char B[]="0123456789ABCDEF";
    
87.     Elemtype a,c;
    
88.     Linkstack *top;
    
89.     squeue LQ;
    
90.     Initstack (&top);
    
91.     Initqueue(&LQ);
    
92.     cout<<n<<"转化为"<<b<<"进制数为:";
    
93.     while(n)
    
94.     {
    
95.         push(&top,n%b);
    
96.         n=n/b;
    
97.     }
    
98.     while(!Empty(&top))
    
99.     {
    
100.         pop(&top,&a);
     
101.         Enqueue(&LQ,a);
     
102.         Outqueue(&LQ,&c);
     
103.         cout<<B[c]<<' ';
     
104.     }
     
105. 
     
106.     cout<<endl;
     
107. }
     
108. int main()
     
109. {
     
110.     char s;
     
111.     int n,b;
     
112.     do
     
113.     {
     
114.       cout<<"请输入要转化成其他进制数的非负数:";
     
115.       cin>>n;
     
116.       cout<<"请输入需要转化成的进制:";
     
117.       cin>>b;
     
118.       Dectoothers(n,b);
     
119.       cout<<"需要结束请输入N/n,继续输入Y/y:";
     
120.       cin>>s;
     
121.     }while((s!='n') && (s!='N'));
     
122.       return 0;
     
123. }
     
124. 
     
125. 
     

复制代码

---

作者: ___________゛M    时间: 2014-2-19 16:01

1. 队列——循环队列
   
2. # include <stdio.h>
   
3. # include <stdlib.h>
   
4. 
   
5. typedef struct Queue
   
6. {
   
7.     int * pData;
   
8.     int front ;
   
9.     int rear;
   
10. }QUEUE;
    
11. 
    
12. void init(QUEUE * pHead)
    
13. {
    
14.     pHead->pData = (int *)malloc(sizeof(Queue) *6);
    
15.     if(NULL == pHead->pData)
    
16.     {
    
17.         exit(-1);
    
18.     }
    
19.     pHead->front = 0;
    
20.     pHead->rear = 0;
    
21. 
    
22. }
    
23. 
    
24. bool full(QUEUE * pHead)
    
25. {
    
26.     if((pHead->rear + 1) % 6 ==pHead->front)
    
27.     {
    
28.         return true;
    
29.     }
    
30.     else
    
31.     {
    
32.         return false;
    
33.     }
    
34.    
    
35. }
    
36. 
    
37. bool empty(QUEUE * pHead)
    
38. {
    
39.     if(pHead->front == pHead->rear)
    
40.     {
    
41.         return true;
    
42.     }
    
43.       
    
44.     else
    
45.     {
    
46.         return false;
    
47.     }
    
48.       
    
49. }
    
50. 
    
51. void in(QUEUE * pHead, int a)
    
52. {
    
53.     if(full(pHead))
    
54.     {
    
55.         printf("队满\n");
    
56.         return;
    
57.     }
    
58.       
    
59.     pHead->pData[pHead->rear] = a;
    
60.     pHead->rear = (pHead->rear + 1) % 6;
    
61. }
    
62. 
    
63. void out(QUEUE * pHead,int * a)
    
64. {
    
65.     if(empty(pHead))
    
66.         exit(-1);
    
67.     * a = pHead->pData[pHead->front];
    
68.     pHead->front = (pHead->front + 1) % 6;
    
69. }
    
70. 
    
71. void print(QUEUE * pHead)
    
72. {
    
73.     if(empty(pHead))
    
74.         exit(-1);
    
75.     int a = pHead->front;
    
76.     while(a != pHead->rear)
    
77.     {
    
78.         printf("%d  ",pHead->pData[a]);
    
79.         a = (a + 1) % 6;
    
80.     }
    
81.     printf("\n");
    
82. }
    
83. 
    
84. int main()
    
85. {
    
86.     int a;
    
87.     QUEUE pHead;
    
88.     init(&pHead);
    
89.     in(&pHead,1);
    
90.     in(&pHead,2);
    
91.     in(&pHead,3);
    
92.     in(&pHead,4);
    
93.     in(&pHead,5);
    
94.     print(&pHead);
    
95.     in(&pHead,6);
    
96.     out(&pHead,&a);
    
97.     printf("out %d\n",a);
    
98.     print(&pHead);
    
99.     return 0;
    
100. }

复制代码

我以前写的循环队列。。。。。。。。。。。 也上一个C 版本的  。

---

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

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