主题:用栈逆制链表问题
我的问题代码如下:
//-------------------------------------------------------
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;
}
}
//-------------------------------------------------------
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;
}
}