栈和队列的基本操作

待我称王封你为后i 2023-10-17 16:26 168阅读 0赞 
  1. /*
  3. 对栈实现初始化，插入栈顶元素，删除栈顶元素，遍历栈，清空栈等基本操作
  5. */
  7. 1 #include <stdio.h>
  8.   2 #include <malloc.h>
  9.   3 #include <stdlib.h>
  10.   4 
  11.   5 #define true 1
  12.   6 #define false 0
  13.   7 
  14.   8 
  15.   9 typedef struct Node
  16.  10 {
  18.  11     int data;
  19.  12     struct Node *pNext;
  20.  13 }NODE, *PNODE;
  21.  14 
  22.  15 typedef struct Stack
  23.  16 {
  25.  17     PNODE pTop;
  26.  18     PNODE pBottom;
  27.  19 }STACK, *PSTACK;
  28.  20 
  29.  21 void init(PSTACK pS);
  30.  22 void push(PSTACK pS, int val);
  31.  23 void traverse(PSTACK pS);
  32.  24 int pop(PSTACK pS , int *val);
  33.  25 void clear(PSTACK pS);
  34.  26 int empty(PSTACK pS);
  35.  27 
  36.  28 int main(void)
  37.  29 {
  39.  30     STACK S ;
  40.  31     int val;
  41.  32     int i;
  42.  33     
  43.  34     init(&S);
  44.  35     
  45.  36     push(&S,1);
  46.  37     push(&S,2);
  47.  38     push(&S,3);
  48.  39     push(&S,4);
  49.  40     push(&S,5);
  50.  41     push(&S,6);
  51.  42 
  52.  43     traverse(&S);
  53.  44     
  54.  45     if(pop(&S ,&val))
  55.  46     {
  57.  47         printf("遍历成功，出栈元素为%d\n",val);
  58.  48     }
  59.  49     else
  60.  50     {
  62.  51         printf("出栈失败！\n");
  63.  52     }
  64.  53     traverse(&S);
  65.  54 
  66.  55     clear(&S);
  67.  56     
  68.  57     traverse(&S);
  69.  58     
  70.  59     return 0 ;
  71.  60 }
  72.  61 
  73.  62 //栈的初始化
  74.  63 void init(PSTACK pS)
  75.  64 {
  77.  65     pS -> pTop = (PNODE)malloc(sizeof(NODE));
  78.  66     
  79.  67     if(NULL == pS -> pTop)
  80.  68     {
  82.  69         printf("动态内存分配失败！");
  83.  70         exit(-1);
  84.  71     }
  85.  72     else
  86.  73     {
  88.  74         pS -> pBottom = pS -> pTop;
  89.  75         pS -> pTop -> pNext = NULL;
  90.  76     }
  91.  77     
  92.  78     return ;
  93.  79 }
  94.  80 
  95.  81 //插入元素到栈顶
  96.  82 void push(PSTACK pS , int val)
  97.  83 {
  99.  84     PNODE pNew = (PNODE)malloc(sizeof(NODE));
  100.  85     
  101.  86     pNew -> data = val;
  102.  87     pNew -> pNext = pS -> pTop;
  103.  88     pS -> pTop = pNew;
  104.  89     
  105.  90     return ;
  106.  91 }
  107.  92 
  108.  93 //遍历栈S
  109.  94 void traverse(PSTACK pS)
  110.  95 {
  112.  96     PNODE p = pS -> pTop;
  113.  97     
  114.  98     printf("栈内元素为：");
  115.  99     while(p != pS -> pBottom)
  116. 100     {
  118. 101         printf("%d\t", p -> data);
  119. 102         p = p -> pNext;
  120. 103     }
  121. 104     
  122. 105     printf("\n");
  123. 106     return ;
  124. 107 }
  125. 108 
  126. 109 //判断栈是否为空
  127. 110 int empty(PSTACK pS)
  128. 111 {
  130. 112     if(pS -> pTop == pS -> pBottom)
  131. 113     {
  133. 114         return true;
  134. 115     }
  135. 116     else
  136. 117         return false;
  137. 118 }
  138. 119 
  139. 120 //删除栈顶元素并将其值赋给*val
  140. 121 int pop(PSTACK pS , int *val)
  141. 122 {
  143. 123     if(empty(pS))
  144. 124     {
  146. 125         return false;
  147. 126     }
  148. 127     else
  149. 128     {
  151. 129         PNODE r = pS -> pTop;
  152. 130         *val = r -> data;
  153. 131         pS -> pTop = r -> pNext;
  154. 132         free(r);
  155. 133         r = NULL;
  156. 134     }
  157. 135 }
  158. 136 
  159. 137 //清空栈S
  160. 138 void clear(PSTACK pS)
  161. 139 {
  163. 140     if(empty(pS))
  164. 141     {
  166. 142         return;
  167. 143     }
  168. 144     else
  169. 145     {
  171. 146         PNODE p = pS -> pTop;
  172. 147         PNODE q = NULL;
  173. 148         
  174. 149         while(p != pS -> pBottom)
  175. 150         {
  177. 151             q = p -> pNext;
  178. 152             free(p);
  179. 153             p = q ;
  180. 154         }
  181. 155         
  182. 156         pS -> pTop = pS -> pBottom;
  183. 157         
  184. 158         return;
  185. 159     }
  186.  160 } 1.链式队列 //队列结点结构体 typedef struct QNode { QElemType data;   QNode *next; }*Queueptr; ------------------------------ //指向结点的指针 struct LinkQueue {  Queueptr front,rear; } 
  209.     <STRONG><SPAN style="COLOR: #000066; FONT-SIZE: 18px">void InitQueue(LinkQueue &Q) 
  210.     { // 构造一个空队列Q 
  211.     if(!(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)))) 
  212.     exit(OVERFLOW); 
  213.     Q.front->next=NULL; 
  214.     } 
  216.     void DestroyQueue(LinkQueue &Q) 
  217.     { // 销毁队列Q(无论空否均可) 
  218.     while(Q.front) 
  219.     { 
  220.     Q.rear=Q.front->next; 
  221.     free(Q.front); 
  222.     Q.front=Q.rear;//释放一块内存要做两点：1.释放指向它的指针。2.将该指针指向空 
  223.     } 
  224.     } 
  226.     void ClearQueue(LinkQueue &Q) 
  227.     { // 将Q清为空队列 
  228.     QueuePtr p,q; 
  229.     Q.rear=Q.front; 
  230.     p=Q.front->next; 
  231.     Q.front->next=NULL;//只留下头结点 
  232.     while(p) 
  233.     { 
  234.     q=p; 
  235.     p=p->next; 
  236.     free(q); 
  237.     } 
  238.     } 
  240.     Status QueueEmpty(LinkQueue Q) 
  241.     { // 若Q为空队列，则返回TRUE，否则返回FALSE 
  242.     if(Q.front->next==NULL)//注意不要把链式队列的判空条件与循环队列混淆 
  243.     return TRUE; 
  244.     else 
  245.     return FALSE; 
  246.     } 
  248.     int QueueLength(LinkQueue Q) 
  249.     { // 求队列的长度 
  250.     int i=0; 
  251.     QueuePtr p; 
  252.     p=Q.front; 
  253.     while(Q.rear!=p) 
  254.     { 
  255.     i++; 
  256.     p=p->next; 
  257.     } 
  258.     return i; 
  259.     } 
  261.     Status GetHead(LinkQueue Q,QElemType &e) 
  262.     { // 若队列不空，则用e返回Q的队头元素，并返回OK，否则返回ERROR 
  263.     QueuePtr p; 
  264.     if(Q.front==Q.rear) 
  265.     return ERROR; 
  266.     p=Q.front->next; 
  267.     e=p->data; 
  268.     return OK; 
  269.     } 
  271.     void EnQueue(LinkQueue &Q,QElemType e) 
  272.     { // 插入元素e为Q的新的队尾元素 
  273.     QueuePtr p; 
  274.     if(!(p=(QueuePtr)malloc(sizeof(QNode)))) // 存储分配失败 
  275.     exit(OVERFLOW); 
  276.     p->data=e; 
  277.     p->next=NULL; 
  278.     Q.rear->next=p; 
  279.     Q.rear=p; 
  280.     } 
  282.     Status DeQueue(LinkQueue &Q,QElemType &e) 
  283.     { // 若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR 
  284.     QueuePtr p; 
  285.     if(Q.front==Q.rear) 
  286.     return ERROR; 
  287.     p=Q.front->next; 
  288.     e=p->data; 
  289.     Q.front->next=p->next; 
  290.     if(Q.rear==p) 
  291.     Q.rear=Q.front;//如果只有一个节点，那么删除这个节点后rear指针也就丢了，需重新赋值 
  292.     free(p); 
  293.     return OK; 
  294.     } 
  296.     void QueueTraverse(LinkQueue Q,void(*vi)(QElemType)) 
  297.     { // 从队头到队尾依次对队列Q中每个元素调用函数vi() 
  298.     QueuePtr p; 
  299.     p=Q.front->next; 
  300.     while(p) 
  301.     { 
  302.     vi(p->data); 
  303.     p=p->next; 
  304.     } 
  305.     printf("\n"); 
  306.     }</SPAN></STRONG>   
  330.     <strong><span style="font-size:18px;color:#000066;">void InitQueue(LinkQueue &Q)   
  331.     { // 构造一个空队列Q   
  332.       if(!(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode))))   
  333.         exit(OVERFLOW);   
  334.       Q.front->next=NULL;   
  335.     }   
  337.     void DestroyQueue(LinkQueue &Q)   
  338.     { // 销毁队列Q(无论空否均可)   
  339.       while(Q.front)   
  340.       {   
  341.         Q.rear=Q.front->next;   
  342.         free(Q.front);   
  343.         Q.front=Q.rear;//释放一块内存要做两点：1.释放指向它的指针。2.将该指针指向空   
  344.       }   
  345.     }   
  347.     void ClearQueue(LinkQueue &Q)   
  348.     { // 将Q清为空队列   
  349.       QueuePtr p,q;   
  350.       Q.rear=Q.front;   
  351.       p=Q.front->next;   
  352.       Q.front->next=NULL;//只留下头结点   
  353.       while(p)   
  354.       {   
  355.         q=p;   
  356.         p=p->next;   
  357.         free(q);   
  358.       }   
  359.     }   
  361.     Status QueueEmpty(LinkQueue Q)   
  362.     { // 若Q为空队列，则返回TRUE，否则返回FALSE   
  363.       if(Q.front->next==NULL)//注意不要把链式队列的判空条件与循环队列混淆   
  364.         return TRUE;   
  365.       else   
  366.         return FALSE;   
  367.     }   
  369.     int QueueLength(LinkQueue Q)   
  370.     { // 求队列的长度   
  371.       int i=0;   
  372.       QueuePtr p;   
  373.       p=Q.front;   
  374.       while(Q.rear!=p)   
  375.       {   
  376.         i++;   
  377.         p=p->next;   
  378.       }   
  379.       return i;   
  380.     }   
  382.     Status GetHead(LinkQueue Q,QElemType &e)   
  383.     { // 若队列不空，则用e返回Q的队头元素，并返回OK，否则返回ERROR   
  384.       QueuePtr p;   
  385.       if(Q.front==Q.rear)   
  386.         return ERROR;   
  387.       p=Q.front->next;   
  388.       e=p->data;   
  389.       return OK;   
  390.     }   
  392.     void EnQueue(LinkQueue &Q,QElemType e)   
  393.     { // 插入元素e为Q的新的队尾元素   
  394.       QueuePtr p;   
  395.       if(!(p=(QueuePtr)malloc(sizeof(QNode)))) // 存储分配失败   
  396.         exit(OVERFLOW);   
  397.       p->data=e;   
  398.       p->next=NULL;   
  399.       Q.rear->next=p;   
  400.       Q.rear=p;   
  401.     }   
  403.     Status DeQueue(LinkQueue &Q,QElemType &e)   
  404.     { // 若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR   
  405.       QueuePtr p;   
  406.       if(Q.front==Q.rear)   
  407.         return ERROR;   
  408.       p=Q.front->next;   
  409.       e=p->data;   
  410.       Q.front->next=p->next;   
  411.       if(Q.rear==p)   
  412.         Q.rear=Q.front;//如果只有一个节点，那么删除这个节点后rear指针也就丢了，需重新赋值   
  413.       free(p);   
  414.       return OK;   
  415.     }   
  417.     void QueueTraverse(LinkQueue Q,void(*vi)(QElemType))   
  418.     { // 从队头到队尾依次对队列Q中每个元素调用函数vi()   
  419.       QueuePtr p;   
  420.       p=Q.front->next;   
  421.       while(p)   
  422.       {   
  423.         vi(p->data);   
  424.         p=p->next;   
  425.       }   
  426.       printf("\n");   
  427.     }</span></strong>   
  432. 2.顺序队列---循环队列 结构体定义如下: struct SqQueue {QElemType *base;//指向开辟的空间的首地址   int front;   int rear; } 
  444.      [cpp] 
  447.      view plain
  450.      copy
  453.      print
  456.      ?
  469.     void InitQueue(SqQueue &Q) 
  470.     { // 构造一个空队列Q 
  471.     Q.base=(QElemType *)malloc(MAX_QSIZE*sizeof(QElemType)); 
  472.     if(!Q.base) // 存储分配失败 
  473.     exit(OVERFLOW); 
  474.     Q.front=Q.rear=0; 
  475.     } 
  477.     void DestroyQueue(SqQueue &Q) 
  478.     { // 销毁队列Q，Q不再存在 
  479.     if(Q.base) 
  480.     free(Q.base); 
  481.     Q.base=NULL; 
  482.     Q.front=Q.rear=0; 
  483.     } 
  485.     void ClearQueue(SqQueue &Q) 
  486.     { // 将Q清为空队列 
  487.     Q.front=Q.rear=0; 
  488.     } 
  490.     Status QueueEmpty(SqQueue Q) 
  491.     { // 若队列Q为空队列，则返回TRUE；否则返回FALSE 
  492.     if(Q.front==Q.rear) // 队列空的标志 
  493.     return TRUE; 
  494.     else 
  495.     return FALSE; 
  496.     } 
  498.     int QueueLength(SqQueue Q) 
  499.     { // 返回Q的元素个数，即队列的长度 
  500.     return(Q.rear-Q.front+MAX_QSIZE)%MAX_QSIZE; 
  501.     } 
  503.     Status GetHead(SqQueue Q,QElemType &e) 
  504.     { // 若队列不空，则用e返回Q的队头元素，并返回OK；否则返回ERROR 
  505.     if(Q.front==Q.rear) // 队列空 
  506.     return ERROR; 
  507.     e=Q.base[Q.front];//等价于e=*(Q.base+Q.front) 
  508.     return OK; 
  509.     } 
  511.     Status EnQueue(SqQueue &Q,QElemType e) 
  512.     { // 插入元素e为Q的新的队尾元素 
  513.     if((Q.rear+1)%MAX_QSIZE==Q.front) // 队列满 
  514.     return ERROR; 
  515.     Q.base[Q.rear]=e;//等价于*(Q.base+Q.rear)=e 
  516.     Q.rear=(Q.rear+1)%MAX_QSIZE; 
  517.     return OK; 
  518.     } 
  520.     Status DeQueue(SqQueue &Q,QElemType &e) 
  521.     { // 若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR 
  522.     if(Q.front==Q.rear) // 队列空 
  523.     return ERROR; 
  524.     e=Q.base[Q.front]; 
  525.     Q.front=(Q.front+1)%MAX_QSIZE; 
  526.     return OK; 
  527.     } 
  529.     void QueueTraverse(SqQueue Q,void(*vi)(QElemType)) 
  530.     { // 从队头到队尾依次对队列Q中每个元素调用函数vi() 
  531.     int i; 
  532.     i=Q.front; 
  533.     while(i!=Q.rear) 
  534.     { 
  535.     vi(Q.base[i]); 
  536.     i=(i+1)%MAX_QSIZE; 
  537.     } 
  538.     printf("\n"); 
  539.     }

发表评论

表情：
评论列表 （有 0 条评论，168人围观）

还没有评论，来说两句吧...

相关阅读

    相关 队列的基本操作

    目录 一、什么是队列？ 二、用数组实现队列 代码实现： 数组实现的缺点： 三、用链表实现队列 代码实现： -------------------- 一、什么

    r囧r小猫r囧r小猫/ 0 赞/ 166 阅读

    相关 循环队列的基本操作

    循环队列设置不同队空与队满条件的解决方案 为了解决顺序队列假溢出的问题，我们采用的方案是少用一个元素空间，此时的指针状态是队尾指针加1才与队头指针重合，于是此时队满的判定

    ゝ一世哀愁。ゝ一世哀愁。/ 0 赞/ 350 阅读