数据结构（严版）课本代码重敲——第三章

  1 #include <iostream>
  2 #include <string.h>
  3 #include <stdio.h>
  4 #include <stdlib.h>
  5 #define maxSize 20
  6 #define ERROR -1
  7 using namespace std;
  8 /*
  9     题目：数据结构 cha3  栈和队列
 10     内容：1. 顺序栈、链栈、顺序队列、链队列
 11     日期：2018/3/10
 12     时间：tomato * 
 13 
 14 */
 15 typedef struct 
 16 {
 17     Elemtype data[maxSize];
 18     int top;
 19 }Sqstack;
 20 void initStack(Sqstack *&sq)
 21 {
 22     sq.top = -1;
 23 }
 24 int push_Sqstack(Sqstack *&sq,Elemtype x)
 25 {
 26    if (sq.top == maxSize-1)
 27         return ERROR;
 28    sq.top++;
 29    sq.data[sq.top] = x;
 30    return 1;
 31 } 
 32 int pop_Sqstack(Sqstack *&sq,Elemtype &x)
 33 {
 34     if (sq.top == -1)
 35         return ERROR;
 36     x = sq.data[sq.top];
 37     sq.top--;
 38     return 1;
 39 }
 40 
 41 typedef struct LNode
 42 {
 43     Elemtype data;
 44     struct LNode *next;
 45 }LNode;
 46 // 链栈为空的标志是ls->next == NULL 
 47 // 头插法建立链栈
 48 int init_LNode(LNode *&lst)
 49 {
 50     (LNode *)malloc(sizeof(LNode));
 51 }
 52 int push_LNode(LNode *&lst,Elemtype x)
 53 {
 54     LNode *p = (LNode *)malloc(sizeof(LNode));
 55     p->data = x;
 56     p->next = lst->next;
 57     lst->next = p;
 58 }
 59 
 60 int pop_LNode(LNode *&lst,Elemtype &x)
 61 {
 62     // 头摘 出栈首先要判断是否栈空
 63     if (lst->next == NULL)
 64         return -1;
 65     x = lst->next->data;
 66     LNode *p = lst->next;
 67     lst->next = p->next;
 68     free(p);
 69     return 1;
 70 }
 71 typedef struct 
 72 {
 73     Elemtype data[maxSize];
 74     int rear;
 75     int front;
 76 }Squeue;
 77 void init_Squeue(Squeue *&sq)
 78 {
 79     sq->rear = sq->front = 0; // front = rear时为空队列
 80 }
 81 int enqueue (Squeue *&sq,Elemtype x)
 82 {
 83     if (sq->front == (sq->rear+1)%maxSize)
 84         return -1;
 85     sq->data[++sq->rear%maxSize] = x;
 86     return 1;
 87 }
 88 int dequeue(Squeue *&sq,Elemtype &x)
 89 {
 90     if (sq->front == sq->rear)
 91         return -1;
 92     x = sq->data[++sq->front%maxSize];
 93     return 1;
 94 }
 95 // 链队列比较特殊，头结点中有两个指针，指向普通的数据节点
 96 typedef struct 
 97 {
 98     struct QLNode *rear;
 99     struct QLNode *front;
100 }Liqueue;
101 typedef struct QLNode
102 {
103     Elemtype data;
104     struct QLNode *next;
105 }QLNode;
106 int init_Liqueue(Liqueue *&lq)
107 {
108     lq = (Liqueue *)malloc(sizeof(Liqueue));
109     lq->front = lq-> rear = NULL;
110     return 1;
111 }
112 void enQueue(Liqueue *&lq,Elemtype x)
113 {
114     QLNode *p = (QLNode *)malloc(sizeof(QLNode));
115     p->data = x;
116     // 从rear后插入结点元素
117     if (lq->front == NULL)
118     {
119         // 第一个元素，既是队尾也是队头
120         lq->front = lq->rear = p;
121     }
122     else 
123     {
124         lq->rear->next = p;
125         lq->rear = p;
126     }
127     free(p);
128 
129 }
130 int  deQueue(Liqueue *&lq,Elemtype &x)
131 {
132     // 判断队列是否为空
133     if (lq->front == NULL || lq->rear == NULL)
134         return -1;
135     // 判断是否是只有一个结点的特殊情况
136     p = lq->front;
137     if (lq->front == lq->rear)
138     {
139         lq->front = lq->rear = NULL;
140     }
141     else 
142     {
143         lq->front = lq->front->next;
144     }
145     x = p->data;
146     free(p);    
147     return 1;
148 }
149 
150 // 括号匹配问题
151 
152 int match(char exp[],int n)
153 {
154     Sqstack *sq;
155     initStack(sq);
156     char c;
157     for (int i = 0;i < strlen(exp) ; i++)
158     {
159         // 遍历该字符数组，如果是左括号则push进去
160         // 如果是右括号：栈空则不匹配，否则弹栈
161         if (exp[i] == ‘(‘)
162         {
163             push_Sqstack(sq,exp[i]);
164         }
165         else
166         {
167             if (exp[i] == ‘)‘)
168             {
169                 if (sq->top == -1)
170                     return -1;
171                 else
172                     pop_Sqstack(sq,c;
173             }
174         }
175     }
176     return 1;
177 }
178 // 后缀式求值
179 int op(int a,char op,int b)
180 {
181     // 完成a op b 的运算
182     switch (op)
183     {
184     case ‘+‘:return a+b;
185     case ‘-‘:return a-b;
186     case ‘*‘:return a*b;
187     case ‘\‘:return a/b; // 需要判断被除数b是否为0
188     default:return 0;
189     }
190 }
191 int com(char exp[])
192 {
193     // exp 数组中存放后缀表达式，最后一个字符为\0 
194     // 栈用来起到一个存储暂时不用的数据的作用
195     Sqstack *sq;
196     initStack(sq);
197 
198     int i=0;
199     while (exp[i]!=‘\0‘)
200     {
201         if (exp[i]>‘0‘ && exp[i]<=9)
202         {
203          // 如果是数字则push，如果是操作符则弹栈两次运算
204          push(sq,exp[i]-‘0‘);
205         }
206         else 
207         {
208             int a,b;
209             pop_Sqstack(sq,a);
210             pop_Sqstack(sq,b);
211             int result = match(a,exp[i],b);
212             push_Sqstack(sq,result);
213         }
214 
215     }
216     return sq->data[sq->top]; // 最终栈中只保留一个结果
217 }
218 int main()
219 {
220 
221     return 0;
222 }