欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

栈与队列链式存储结构一货物上架问题

程序员文章站 2022-05-03 22:49:49
#include #include static int n; //用于输入货架(货架即为栈)的大小 using namespace std; //信息结构体typedef struct /*Inform*/ //可以去掉Inform,在需要在结构体中定义结构 ......
#include <iostream>
#include<string.h>
static int n;                       //用于输入货架(货架即为栈)的大小
using namespace std;
 
//信息结构体
typedef struct /*inform*/      //可以去掉inform,在需要在结构体中定义结构体对象(指针)时不能去掉
{
    string name;
    int a;
}inform;
 
//栈的*顺序*结构体
typedef struct node
{
    inform e;
    struct node *next;
}stacknode,*linkstack;
 
//队列*链式*结构体
typedef struct qnode
{
    inform e;
    struct qnode *next;
}qnode,*queueptr;
 
//指向链式队列的头尾指针
typedef struct
{
    queueptr fro;
    queueptr rear;
}linkqueue;
void found1(linkstack &s);      //货物上架
void foundd(linkqueue &d);      //创建顺序队列
void turnsz1(linkstack &s1,linkqueue d);      //对于前天未剩余(第一天)倒货
void turnsz2(linkstack &s1,linkstack s2,linkstack s3);      //对于前天有剩余倒货
void print(linkstack s1);
int main()
{
    cout << "请输入每次上货的最大值\t";
    cin >> n;
    linkstack s1,s2,s3;
    s1=s2=s3=null;      //是否有必要定义构造函数,即建立一个空栈  建立一个队列,使其头尾指针指向队列未存货物信息的空结点
    linkqueue d;
    cout<<"第一天货物上架"<<endl;
    found1(s1);      //输入货物信息
    foundd(d);
    turnsz1(s1,d);
    print(s1);
    cout<<"第二天货物上架"<<endl;
    if(s1==null)
    {
        found1(s1);
        turnsz1(s1,d);
        print(s1);
    }
    else
    {
        found1(s2);
        turnsz2(s1,s2,s3);
        print(s1);
    }
    return 0;
}
void found1(linkstack &s)
{
    s=null;      //定义一个空栈,s连接在p上,即p->next=null
    inform i;
    i.name="";
    cout<<"输入break表示停止输入:"<<endl;
    while(1)
    {
       stacknode *p;
       p=new stacknode;
       cin>>i.name;
       if(i.name=="break")
        break;
       cin>>i.a;
       p->e=i;
       p->next=s;
       s=p;
    }
}
void foundd(linkqueue &q)
{
    q.fro=q.rear=new qnode;
    q.fro->next=null;
    q.rear->next=null;
}
void turnsz1(linkstack &s1,linkqueue d)      //此处队列表现出来的问题为 d.fro始终与d.rear相等。实际上为对接点的创建(多次使用只创建一次导致一直在修该此指针
                                             //而未存储下一个结点)还有delete的问题,怎填的结点指针并不能delete,否则该节点将会被删除
{
    inform i;
    //qnode *p=new qnode;      若无下面的,知识在修改队列第一个元素指向的值,而不是继续添加
    stacknode *s=new stacknode;
    while(s1!=null)
    {
        qnode *p=new qnode;     //此处十分重要
        i=s1->e;     //i=s1.e不正确 ,调用对象的成员时用“.”,如果是指针或者引用时,利用“->”调用其成员
        s=s1;
        s1=s->next;
        delete s;
        p->e=i;
        p->next=null;
        d.rear->next=p;
        d.rear=p;
        //cout<<"rear指向的名字"<<d.rear->e.name<<endl;
        //cout<<"fro指向的名字"<<d.fro->next->e.name<<endl;      //《问题》此处fro 与 rear 同时移动
    }
    qnode *p=new qnode;
    while(d.fro!=d.rear)
    {
        stacknode *s=new stacknode;
        p=d.fro->next;
        i=p->e;
        d.fro->next=p->next;
        if(p==d.rear)
            d.rear=d.fro;
        delete p;
        s->e=i;
        s->next=s1;
        s1=s;
    }
}
void turnsz2(linkstack &s1,linkstack s2,linkstack s3)
{
    inform i;
    while(s1!=null)
    {
        stacknode *s=new stacknode;
        s=s1;
        s1=s->next;
        s->next=s3;
        s3=s;
    }
    while(s2!=null)
    {
        stacknode *s=new stacknode;
        s=s2;
        s2=s->next;
        s->next=s1;
        s1=s;
    }
    while(s3!=null)
    {
        stacknode *s=new stacknode;
        s=s3;
        s3=s->next;
        s->next=s1;
        s1=s;
    }
}
void print(linkstack s1)
{
    //stacknode *s=new stacknode;
    while(s1!=null)
    {
        cout<<s1->e.name<<" "<<s1->e.a<<endl;
        s1=s1->next;
    }
}
 
栈与队列链式存储结构:
      1:掌握栈与队列的初始化问题,可以通过画图进一步理解并记忆其核心内容
            a:栈,初始化时申请一个 *s 指向null的空地址,存入时,申请空间并与s连接即可(注意栈的尾部结点的next->null)
            b:   队列:首先创建两个指针  *pro  he  *rear 指向同一个空节点,并令其next->null,存入时,创建新结点连在rear后面,并且将rear指向新节点,删除队列元素时,pro不                                动,删除pro->next即可
       2:特别问题:
             在存入和删除元素时,要注意新节点的创建与删除。
                    a:创建——存入一个元素需要创建一个新指针,不能创建一个多次对其赋值,这样不会存入,而是在不断改变第一个元素的值
                    b:delete也是如此,在元素存入时,若delete存入的指针,则会使存入的元素空间释放,即存入进去的内容被删除