[原创]C语言实现 栈排序算法

22小时前 199

这题正确姿势是用顺序表做。昨天没注意直接用链表做了。。

思路：利用辅助栈排序

第一步：
取原栈第一个元素a，压辅助栈a 删除原栈a
大循环
第二步：循环
取原栈第一个元素a，删除原栈a 。*循环1：在辅助栈中找< 或 >的元素
计数k++ 循环1-
循环2 助栈空压回原栈k个元素 循环2- ，把a压栈辅助栈，循环3 再把原栈里的数据全部压回辅助栈 循环3-
大循环-

#include <iostream>
#include<stdio.h>
#include<stdlib.h> 
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int size=0;
typedef struct no
{
int data;
struct no *pnext;                       //构造栈 

}node;

typedef struct 
{
node head;                 //构造栈头和栈尾   头尾不存储数据 
node tail;

}lht;

void steak_show(const lht *p)
 { node *pn=(node*)p->head.pnext;

     while(pn!=&p->tail)
     {

         printf("%d ",pn->data);                    //遍历显示栈 
         pn=pn->pnext;
     }
     printf("\n");
 }

void steak_init(lht *p)
 {
     p->head.pnext=&p->tail;
     p->tail.pnext=NULL;                //初始化栈 
 }

int steak_add(lht *p,int i)
{

      node *pf=NULL,*pm=NULL,*pl=NULL,*pn=NULL;   //进栈 
      pn=(node*)malloc(sizeof(node));
      if(pn==NULL)
      return 0;
      pf=&p->head;
      pm=pf->pnext;
      pl=pm->pnext;

    pf->pnext=pn;
      pn->pnext=pm;

    pn->data=i;

    return 1;
}

void steak_order(lht *p) 
{    
    int a=0;
    lht l={0};
    steak_init(&l);
    node *pf=NULL,*pm=NULL,*pn=NULL;
    pf=&p->head;
    pm=pf->pnext;

    a=pm->data;   
    steak_add(&l,a);    //压辅助栈
    pf->pnext=pm->pnext;//删除原栈元素a
    free(pm);
    pm=pf->pnext;

    node *pff=NULL,*pmm=NULL,*pnn=NULL;
    pff=&l.head;            //辅助栈指针 
    pmm=pff->pnext;

    int k=0;  //辅助栈插入位置计数    
    steak_show(&l);
    while(pm!=&p->tail)  
    {
        a=pm->data;               cout<<"取数"<<a<<endl;
        pf->pnext=pm->pnext;
        free(pm);
        pm=pf->pnext;

        k=0; 
        pff=&l.head;            //辅助栈指针 
        pmm=pff->pnext;

        while(pmm!=&l.tail )
        {
            if( pmm->data > a)     //升序降序 
                break;
            k++;//计数 
            pn=(node*)malloc(sizeof(node));  //把辅助 栈的节点压回原栈并删除节点 
            pn->data=pmm->data;
            pn->pnext=pf->pnext;
            pf->pnext=pn;

            pff->pnext=pmm->pnext;
            free(pmm);
            pmm=pff->pnext;
        } 
        //cout<<"辅助栈插入前"<<endl; 
        steak_show(&l);
    pnn=(node*)malloc(sizeof(node));  //把a插入辅助栈 
    pnn->data=a;
    pnn->pnext=pmm;
    pff->pnext=pnn;
            //    cout<<"辅助栈插入后"<<endl; 
            //    steak_show(&l); cout<<"pm"<<pf->pnext->data<<endl; 
    int i=1;//计数，把原栈里的k个节点压到辅助栈里 
    while(i<=k)
    {
    //cout<<"原栈pm要删除的节点"<<pf->pnext->data<<endl; 
        pnn=(node*)malloc(sizeof(node)); //把原栈的节点压栈到辅助栈 
        pnn->data=pf->pnext->data;
        pnn->pnext=pff->pnext;
        pff->pnext=pnn;

        node *pd=NULL;
        pd=pf->pnext->pnext;  //原栈出栈 

        free(pf->pnext);
        pf->pnext=pd;
        pm=pf->pnext;
        i++; 
    } 

        steak_show(&l);

  }


  pff=&l.head;     //把辅助栈里的节点压回原栈 
   pmm=pff->pnext;

  while(pmm!=&l.tail)
  {
  pn=(node*)malloc(sizeof(node));
  pn->data=pmm->data;

  pn->pnext=pf->pnext;
  pf->pnext=pn;

  pmm=pmm->pnext;



 } 

}

int main(int argc, char *argv[]) 
{

    lht l1={0};
    steak_init(&l1);
    steak_add(&l1,1000);
    steak_add(&l1,3);
    steak_add(&l1,5);
    steak_add(&l1,2);
    steak_add(&l1,99);
    steak_add(&l1,88);
    steak_add(&l1,77);
    steak_add(&l1,99);
    steak_add(&l1,-1);
    steak_add(&l1,-99);
    steak_show(&l1);
    steak_order(&l1); 
    steak_show(&l1);
    return 0;
}

[公告][征集寄语] 看雪20周年年会 | 感恩有你，一路同行