-
-
[原创]C语言实现 栈排序算法
-
发表于:
2019-11-3 14:53
4523
-
这题正确姿势是用顺序表做。昨天没注意直接用链表做了。。
思路:利用辅助栈排序
第一步:
取原栈第一个元素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;
}
[培训]内核驱动高级班,冲击BAT一流互联网大厂工作,每周日13:00-18:00直播授课