【数据结构】之堆栈与用栈实现十进制到二进制的转换

青旅半醒 2023-10-07 11:04 2阅读 0赞

### 1、可以使用栈来实现，将一个十进制的数转化为二进制的数 ###

#include<stdio.h>
    #include<stack>
    using namespace std;
    int convert(int n){
        
    	int i, result = 0;
    	stack<int> res;
    	while(n != 0){
        	
    		res.push(n % 2);
    		n /= 2;
    	}
    	//弹出相应的元素
    	while(!res.empty()){
        
    		printf("%d", res.top());
    		res.pop();	
    	} 
    } 
    int main(void){
        
    	int n; 
    	printf("请输入一个十进制的数："); 
    	scanf("%d", &n);
    	convert(n);
    	return 0;
    }

### 2：后缀表达式 ###

中缀表达式：运算符号位于两个运算数之间。如，a + b \* c - d / e  
后缀表达式：运算符号位于两个运算数之后。如，a b c \*+d e /-

**当遇到运算符时把最近的两个运算数放进去运算**

### 3：定义及操作 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3_size_16_color_FFFFFF_t_70 3]

n个数据元素依次入栈，出栈顺序：**C(2n,n)-C(2n,n+1)**  
n个字符入栈全排列有**n!种**排列方式  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][20200509104118430.png]

typedef  struct SNode *PtrToSNode;
    struct  SNode {
        
    	ElementType  *Data;   /* 存储元素的数组 */
    	int  Top;        /* 栈顶指针的位置*/
           int Maxsize；     /* 堆栈最大容量 */
    };
    typedef  PtrToSNode  Stack;

**操作：**  
1：(1)生成空堆栈

Stack CreateStack(int Maxsize)
    {
        
        Stack S = (Stack)malloc(sizeof(struct SNode));
        S->Data = (ElementType *)malloc(Maxsize * sizeof(ElementType));
        S->Top = -1;
        S->Maxsize = Maxsize;
        return S;
    }

2:(2)入栈

bool IsFull( Stack S )
    {
           
        return (S->Top == S->MaxSize-1);
    }
    
    bool Push( Stack S, ElementType X )
    {
          
       if ( IsFull(S) ) {
        
            printf("堆栈满");  
            return false;
        }
        else {
        
            S->Data[++(S->Top)] = X;
            return true;
        }
    }

3:(3)出栈

bool IsEmpty( Stack S )
    {
         
       return (S->Top == -1);
    }
    ElementType Pop( Stack S )
    {
           if ( IsEmpty(S) ) {
        
            printf("堆栈空");
            return ERROR; /* ERROR是ElementType的特殊值，标志错误 */
        }
        else    
            return ( S->Data[(S->Top)--] );
    }

### 例： ###

请用一个数组实现两个堆栈，要求最大地利用数组空间，使数组只要有空间入栈操作就可以成功。写出相应的入栈和出栈操作函数。  
**【分析】 一种比较聪明的方法是使这两个栈分别从数组的两头开始向中间生长；当两个栈的栈顶指针相遇时，表示两个栈都满了。此时，最大化地利用了数组空间**

typedef  int Position;
    typedef  struct  SNode *PtrToSNode;
    struct  SNode {
        
    	ElementType  *Data;   /* 存储元素的数组 */
    	Position  Top1;              /* 堆栈1的栈顶指针 */
    	Position  Top2;              /* 堆栈2的栈顶指针 */ 
                    int  MaxSize;                 /* 堆栈最大容量 */
    };
    typedef  PtrToSNode  Stack;
    S->Top1 =  -1; 
    S->Top2 = MaxSize;
    bool Push( Stack S, ElementType X, int Tag )
    {
           /* Tag作为区分两个堆栈的标志，取值为1和2 */
        if ( S->Top2-S->Top1 == 1) {
         /* 堆栈满 */
    	printf("堆栈满\n");    return false;
        }
        else {
        
    	if ( Tag == 1 )   S->Data[++(S->Top1)] = X;
    	else              S->Data[--(S->Top2)] = X;
    	return true;
        }
    }
    ElementType Pop( Stack S, int Tag )
    {
           /* Tag作为区分两个堆栈的标志，取值为1和2 */
        if ( Tag == 1 ) {
         /* 对第一个堆栈操作 */
    	if ( S->Top1 == -1 ) {
         /* 堆栈1空 */
    		printf("堆栈1空\n");   return ERROR;
    	}
    	else return S->Data[(S->Top1)--];
        }
        else {
         /* 对第二个堆栈操作 */
    	if ( S->Top2 == S->MaxSize ) {
         /* 堆栈2空 */
    		printf("堆栈2空\n");    return ERROR;
    	}
    	else  return S->Data[(S->Top2)++];
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3_size_16_color_FFFFFF_t_70 6]  
(1) 堆栈初始化（建立空栈）  
(2) 判断堆栈S是否为空

Stack CreateStack( ) 
    {
         /* 构建一个堆栈的头结点，返回该结点指针 */
      Stack S;
      S = malloc(sizeof(struct SNode));
      S->Next = NULL;
      return S;
    }
    
    bool IsEmpty ( Stack S )
    {
         /* 判断堆栈S是否为空，若是返回true；否则返回false */
      return ( S->Next == NULL );
    }
    bool Push( Stack S, ElementType X )
    {
         /* 将元素X压入堆栈S */
    	PtrToSNode TmpCell;
    	TmpCell = (PtrToSNode)malloc(sizeof(struct SNode));
    	TmpCell->Data = X;
    	TmpCell->Next = S->Next;
    	S->Next = TmpCell;
    	return true;
    }
    
    ElementType Pop( Stack S )  
    {
         /* 删除并返回堆栈S的栈顶元素 */
    	PtrToSNode FirstCell;
    	ElementType TopElem;
    	if( IsEmpty(S) ) {
        
    		printf("堆栈空");   return ERROR;
    	}
    	else {
        
    		FirstCell = S->Next; 
    		TopElem = FirstCell->Data;
    		S->Next = FirstCell->Next;
    		free(FirstCell);
    		return TopElem;
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200509101407674.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200509101504938.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200509101829106.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200509101925465.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200509103924826.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200509104050335.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3,size_16,color_FFFFFF,t_70
[20200509104118430.png]: https://img-blog.csdnimg.cn/20200509104118430.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200509105543942.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjU2MDc3,size_16,color_FFFFFF,t_70