回 帖 发 新 帖 刷新版面

主题:用栈逆制链表问题

我的问题代码如下:
//-------------------------------------------------------
void Stack::ReverseList(LinkNode *head){
    StackType temp;  //定义栈的结构体对象。
    LinkList *list=NULL; //LinkList为链表类,包含链表的几种操作
    LinkNode *p,*q;
    p=head->next;
    this->InitStack(&temp); //初始化栈
    while(p){       //把链表所有元素进栈
        if(this->StackPush(&temp,p->data)==0)
            exit(0);
        else{
            q=p;
            p=p->next;
            delete q;
        }
    }
    //cout<<"a"<<endl;
    //问题在下面这个while循环里。这个循环本意是让栈中元素依次跳出。
    //并且加在原链表后面,达到逆制效果。
    while(temp.next){ 
        /*
        if(list->BackInsertList(head,this->StackTop(&temp)->node)==1)
            cout<<"insert success";
            */
        cout<<this->StackTop(&temp)->node<<","; //取栈顶元素
        this->StackPop(&temp); //出栈
        cout<<temp.next<<endl;
    }
    cout<<"end";
}
//-------------------------------------------------------
int main(){
    Stack Demo;
    cout<<"\n Reverse List with Stack Test::\n";
    LinkList List;
    LinkNode head;
    List.InitLinkList(&head); //初始化链表
    for(int i=1;i<11;i++){  //链表插入数据(1-10)
        List.InsertNode(&head,i,i);
    }
    cout<<"The original list is:";
    for(i=1;i<=List.LengthOfLink(&head);i++){
        cout<<List.FindNode(&head,i)->data<<",";
    }
    cout<<"\nThe reverse list is:";
    Demo.ReverseList(&head); //转换函数。问题就出在这里!!
    for(i=1;i<=10;i++)
        cout<<List.FindNode(&head,i)->data<<",";
    return 0;
}
最终转换结果无法输出。问题就出在Demo.ReverseList(&head)这句里。我在调试的时候
发现如果不加if(list->BackInsertList(head,this->StackTop(&temp)->node)==1)这句,
然后测试进出栈元素是正确的。但是加上后程序就会死掉。观察BackInsertList函数原形,
觉得应该是head地址传递错误,但是不知应该如何修改?

其中BackInsertList函数原形为:
//---------------------------------------------------
int LinkList::BackInsertList(LinkNode *L,DataType data){
    LinkNode *p,*q;
    if((p=(LinkNode *)malloc(sizeof(LinkNode)))==NULL){
        cout<<"Back insert error!"<<endl;
        return 0;
    }
    else{
        p->data=data;
        p->next=NULL;
        q=L;
        while(q->next){
            q=q->next;
        }
        q->next=p;
        return 1;
    }
}

回复列表 (共3个回复)

沙发

个人意见,仅供参考

temp.next 是要判断栈空么?应该做成一个接口

C++尽量避免直接malloc和free,用new用delete

StackTop(&temp)貌似像读栈顶的函数不像出栈函数

StackPush(&temp,p->data)
this->StackTop(&temp)->node)

好像压入的和弹出的不是一类东西???

板凳

temp.next 是要判断栈空么?   是的
StackTop(&temp) 是取栈顶元素,
this->StackPop(&temp); 是出栈

谢谢你

3 楼

如果你能给出所有代码就好了.

我来回复

您尚未登录,请登录后再回复。点此登录或注册