关于连续释放链表空间的有关问题，求指导

2013-12-28

关于连续释放链表空间的问题，求指导！是一元多项式运算的程序，在建立了各个链表之后，在最后想撤销它们，可是

关于连续释放链表空间的问题，求指导！
是一元多项式运算的程序，在建立了各个链表之后，在最后想撤销它们，可是连续调用六遍会出错，但是调用两遍却没事，不知是链表的问题还是del（）函数的问题，下面是我的程序，希望大侠能给出指导！（问题出在main（）最后的del（）上）

#include<iostream>
#include<cmath>
using namespace std;
typedef struct node{
   float a;
   int b;
   struct node *next;

}lnode,*linklist;



linklist creat_linklist(int k){
  linklist H;
  lnode *p,*r;
  int max,mid;
  float mark;
  H=r=NULL;
for(int i=0;i<k;i++){
     cout<<"请输入第"<<i+1<<"项的<系,指>：";
     cin>>mark>>mid;
     while(mark==0){
     cout<<"系数不能为零，请重新输入<系，指>：";
     cin>>mark>>mid;
     }
     if(i==0){
         max=mid;
     }
     else{
     while(mid<=max){
         cout<<endl;
     cout<<"请按照指数依次升高的原则重新输入<系，指>：";
     cin>>mark>>mid;
     
     } 
    }
     
    max=mid;
    
    p=new lnode;
    if(!p){cout<<"分配空间错误！"<<endl; exit(1);}
    p->a=mark;
    p->b=max;
    
    
    

    cout<<endl;
    if(H==NULL)
        H=p;
    else
        r->next=p;
        r=p;
    }
r->next=NULL;//若链表末尾不设置为空，其他函数将无法正常终止循环，因为s1=s1->next无法正常结尾；
cout<<endl;

return H;

}






void output(linklist H){
    
lnode *s=NULL;
s=H;

while(s){

    if(s!=H&&s->a>0){
        
         if(s->b==1&&s->a==1)
            cout<<"+x";
        
         else if(s->b==1){

             cout<<"+"<<s->a<<"x";
         }
         else if(s->b==0)
             cout<<"+"<<s->a;
        else if(s->a==1)
            
            cout<<"+"<<"x^"<<s->b;
        
        else
            cout<<"+"<<s->a<<"x^"<<s->b;
    }
    else{
        if(s==H&&s->a==0&&s->next==NULL)
            cout<<"0";
        else if(s->a==0){
            s=s->next;
            continue;
        }
        
        else if(s->b==0){
         
            cout<<s->a;
        }
        else if(s->b==1&&s->a==1)
            
            cout<<"x";
            
        else if(s->b==1&&s->a==-1)
            cout<<"-x";
        else if(s->b==1)
            cout<<s->a<<"x";
        else if(s->a==-1)
            cout<<"-x^"<<s->b;
        else if(s->a==1)
            cout<<"x^"<<s->b; 
 
        else
            cout<<s->a<<"x^"<<s->b;
    }        
            
            
            s=s->next;
    
            
}

}

linklist add(linklist H1,linklist H2){
linklist H3=NULL;
lnode *s1,*s2,*r;
lnode *pre;
int k=-1;
s1=H1;
s2=H2;
r=H3=NULL;
while(s1!=NULL&&s2!=NULL){
if(s1->b==s2->b){
     if(s1->a+s2->a==0){
         if(s1->next==NULL&&s2->next==NULL){
             k=0;
            
             s1=s1->next;
             s2=s2->next;
         }
         else if(s1->next==NULL&&s2->next!=NULL){
             s1=s1->next;
             s2=s2->next;
             k=1;
            
        //     continue;
         }
         else if(s2->next==NULL&&s1!=NULL){
             s1=s1->next;
             s2=s2->next;
             k=2;
        //     continue;
         }
         else{
         s1=s1->next;
         s2=s2->next;
    //     continue;
         }
     
     }


     else{
     pre=new lnode;
     
     pre->a=s1->a+s2->a;
     
     pre->b=s1->b;
     



     if(H3==NULL)
         H3=pre; 
                  
     else
     r->next=pre;
     r=pre;
     r->next=NULL;//此处同上处一样，若不将新建链表末尾置为NULL关于其循环将无法正常终止！！！
     s1=s1->next;
     s2=s2->next;
     }     
     
    
}
else if(s1->b<s2->b){
     pre=new lnode;
     pre->a=s1->a;
     pre->b=s1->b;
      if(H3==NULL)
         H3=pre; 
         
         
     else
     r->next=pre;
     r=pre;
     s1=s1->next;
    
     
}
else
{
     pre=new lnode;
     pre->a=s2->a;
     pre->b=s2->b;
      if(H3==NULL)
         H3=pre; 
         
         
     else
     r->next=pre;
     r=pre;
     
     s2=s2->next;

  }


} 


if(k==0){
     if(H3==NULL){
     H3=new lnode;
     H3->a=0;
     H3->b=0;
     H3->next=NULL;
     }
     r->next=NULL;

}
else if(k==1&&s2!=NULL){
     pre=new lnode; 
 
     pre->a=s2->a;
     pre->b=s2->b;
      if(H3==NULL)
         H3=pre; 
         
         
     else
     r->next=pre;
     r=pre;
     r->next=NULL;


}
    
else if(k==2&&s1!=NULL){
    pre=new lnode;
     pre->a=s1->a;
     pre->b=s1->b;
      if(H3==NULL)
         H3=pre; 
         
         
     else
     r->next=pre;
     r=pre;
     r->next=NULL;

}
    

else if(s1!=NULL)
     r->next=s1;
else
     r->next=s2;
     

return H3;
}
  









linklist sub(linklist H1,linklist H2){
linklist H4=NULL;
lnode *s1,*s2,*r;
lnode *pre;
int k=-1;
s1=H1;
s2=H2;
r=H4=NULL;
while(s1!=NULL&&s2!=NULL){
if(s1->b==s2->b){
     if(s1->a-s2->a==0){
         if(s1->next==NULL&&s2->next==NULL){
             k=0;
            
             s1=s1->next;
             s2=s2->next;
         }
         else if(s1->next==NULL&&s2->next!=NULL){
             s1=s1->next;
             s2=s2->next;
             k=1;
            
        //     continue;
         }
         else if(s2->next==NULL&&s1->next!=NULL){
             s1=s1->next;
             s2=s2->next;
             k=2;
        //     continue;
         }
         else{
         s1=s1->next;
         s2=s2->next;
    //     continue;
         }
     
     }


     else{
     pre=new lnode;
     
     pre->a=s1->a-s2->a;
     
     pre->b=s1->b;
     



     if(H4==NULL)
         H4=pre; 
                  
     else
     r->next=pre;
     r=pre;
     r->next=NULL;//此处同上处一样，若不将新建链表末尾置为NULL关于其循环将无法正常终止！！！
     s1=s1->next;
     s2=s2->next;
     }     
     
    
}
else if(s1->b<s2->b){
     pre=new lnode;
     pre->a=s1->a;
     pre->b=s1->b;
      if(H4==NULL)
         H4=pre; 
         
         
     else
     r->next=pre;
     r=pre;
     s1=s1->next;
    
     
}
else
{
     pre=new lnode;
     pre->a=-s2->a;
     pre->b=s2->b;
      if(H4==NULL) 
 
         H4=pre; 
         
         
     else
     r->next=pre;
     r=pre;
     
     s2=s2->next;

  }


} 


if(k==0){
     if(H4==NULL){
     H4=new lnode;
     H4->a=0;
     H4->b=0;
     H4->next=NULL;
     }
    else
     r->next=NULL;

}
else if(k==1&&s2!=NULL){
     while(s2!=NULL){
     pre=new lnode;
     pre->a=-s2->a;
     pre->b=s2->b;
      if(H4==NULL)
         H4=pre; 
         
         
     else
     r->next=pre;
     r=pre;
     r->next=NULL;
     s2=s2->next;
     }


}
    
else if(k==2&&s1!=NULL){
    pre=new lnode;
     pre->a=s1->a;
     pre->b=s1->b;
      if(H4==NULL)
         H4=pre; 
         
         
     else
     r->next=pre;
     r=pre;
     r->next=NULL;

}
    

else if(s1!=NULL){
    r->next=s1;
    while(s1!=NULL){
        
        s1->a=s1->a;
        s1=s1->next;
    }
}
else{
    r->next=s2;
    while(s2!=NULL){
        s2->a=-s2->a;
        s2=s2->next;
    }
    
}
     

return H4;


}







linklist der(linklist H){
    
lnode *p,*s;
p=H;
while(p){
    if(p->b==0){ 
        if(p==H){
            s=p;
            p=p->next;
            H=p;
            delete s;
        }
        else{    
            p->a=0;
            p=p->next;
        }

    }
    else{
    p->a=p->a*p->b;
    
    p->b=p->b-1;
p=p->next;
    }
    
    
}
return H;


}



    
void del(linklist H){
lnode *p,*s;
p=H;
while(p){
    s=p;
    p=p->next;
    delete s;
  }

}    







int main(){
linklist H1=NULL,H2=NULL,H3=NULL,H4=NULL,H5=NULL,H6=NULL;
int m,n;

cout<<"                温馨提示：多项式请按指数依次递增的规则输入"<<endl;    
cout<<"请输入多项式a的项数";
cin>>m;
while(m<=0){
     cout<<endl;
     cout<<"不符合数学逻辑，请重新输入:";
     cin>>m;
     
}

H1=creat_linklist(m);

cout<<"请输入多项式b的项数";
cin>>n;
  while(n<=0){
     cout<<endl;
     cout<<"不符合数学逻辑，请重新输入:";
     cin>>n;
  }
     
  H2=creat_linklist(n);
  
  cout<<"多项式a为:";
  output(H1);
  cout<<endl;


cout<<"多项式b为:";
output(H2); 
 
cout<<endl;
H3=add(H1,H2);
cout<<"相加的结果为：";
output(H3);
cout<<endl;

cout<<"相减的结果为：";
H4=sub(H1,H2); 
output(H4);
cout<<endl;

cout<<"对a的求导结果：";
H5=der(H1);
output(H5);
cout<<endl;

cout<<"对b的求导结果：";
H6=der(H2);
output(H6);

cout<<endl;

del(H1);
del(H2);
del(H3);
del(H4);
del(H5);
del(H6);
cout<<"各链表空间释放完毕！！！"<<endl;
return 0;
}

[解决办法]


     else
     r->next=pre;
     r=pre;
     r->next=NULL; //加上这个
     s1=s1->next;
     
      
}
else
{
     pre=new lnode;
     pre->a=s2->a;
     pre->b=s2->b;
      if(H3==NULL)
         H3=pre; 
          
          
     else
     r->next=pre;
     r=pre;
     r->next=NULL; //加上这个 
     s2=s2->next;

以上是198行到218行的代码。你del错误无非就是next没弄成NULL，所以你只要搜索所有new的地方，看看最后new出来的东西的next有没有弄成NULL就行了，这是一件很无脑的事，你自己做就行了，我已经帮你找出2处了~
[解决办法]
仅供参考

//假设带表头结点的单向链表头指针为head，试编写一个算法将值为5的结点插入到连接表的第k个结点前，删除第k个节点，并对该链表进行排序。
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>
struct NODE {
    int          data;
    struct NODE *next;
} H,*head,*p,*q,*s1,*s2,*s3,*s4,*s;
int i,j,k,n,t,m;
int main() {
    srand(time(NULL));

    //填写头节点数据
    H.data=-1;
    H.next=NULL;
    head=&H;

    //创建10个节点的单链表
    p=head;
    for (i=0;i<10;i++) {
        q=(struct NODE *)malloc(sizeof(struct NODE));
        if (NULL==q) return 1;
        q->data=rand()%100;//填写0..99的随机值
        q->next=NULL;
        p->next=q;
        p=q;
    }

    //输出整个单链表
    s=head->next;
    while (1) {
        if (NULL==s) {
            printf("\n");
            break;
        }
        printf("%02d->",s->data);
        s=s->next;
    }

    //将值为5的结点插入到单链表的第k个结点前
    k=3;
    n=0;
    p=head;
    while (1) {
        if (NULL==p) {
            break;
        }
        n++;
        if (k==n) {
            q=(struct NODE *)malloc(sizeof(struct NODE));
            if (NULL==q) return 1;
            q->data=5;
            q->next=p->next;
            p->next=q;
            break;
        }
        p=p->next; 
 
    }

    //输出整个单链表
    s=head->next;
    while (1) {
        if (NULL==s) {
            printf("\n");
            break;
        }
        printf("%02d->",s->data);
        s=s->next;
    }

    //删除第k个节点
    k=5;
    n=0;
    p=head;
    while (1) {
        if (NULL==p) {
            break;
        }
        n++;
        if (k==n) {
            q=p->next;
            if (q) {
                p->next=q->next;
                free(q);
            }
            break;
        }
        p=p->next;
    }

    //输出整个单链表
    s=head->next;
    while (1) {
        if (NULL==s) {
            printf("\n");
            break;
        }
        printf("%02d->",s->data);
        s=s->next;
    }

    //从小到大排序
    for (p=head;p!=NULL && p->next!=NULL;p=p->next) {
        for (q=p->next;q!=NULL && q->next!=NULL;q=q->next) {
            if (p->next->data > q->next->data) {

                //交换data
//              printf("swap %02d %02d\n",p->next->data,q->next->data);
//              t=p->next->data;p->next->data=q->next->data;q->next->data=t;

                //或者

                //交换next
//              printf("swap %02d %02d\n",p->next->data,q->next->data);
                s1=p->next;
                s2=p->next->next;
                s3=q->next;
                s4=q->next->next;

                if (s2!=s3) {
                     p->next=s3;
                    s3->next=s2;
                     q->next=s1;
                    s1->next=s4;
                } else {
                     p->next=s3;
                    s3->next=s1;
                           q=s3;
                    s1->next=s4;
                }

                //输出整个单链表
//              s=head->next; 
 
//              while (1) {
//                  if (NULL==s) {
//                      printf("\n");
//                      break;
//                  }
//                  printf("%02d->",s->data);
//                  s=s->next;
//              }
//              getchar();
            }
        }
    }

    //输出整个单链表
    s=head->next;
    while (1) {
        if (NULL==s) {
            printf("\n");
            break;
        }
        printf("%02d->",s->data);
        s=s->next;
    }

    //将单链表中前 m 个结点和后 n 个结点进行互换,m+n为链表总长10
    m=4;
    n=6;
    k=0;
    p=head;
    while (1) {
        if (NULL==p) {
            break;
        }
        k++;
        if (m+1==k) {
            q=p;
        }
        s=p;
        p=p->next;
    }
    s1=head->next;
    head->next=q->next;
    s->next=s1;
    q->next=NULL;

    //输出整个单链表
    s=head->next;
    while (1) {
        if (NULL==s) {
            printf("\n");
            break;
        }
        printf("%02d->",s->data);
        s=s->next;
    }

    //释放所有节点
    p=head->next;
    while (1) {
        if (NULL==p) {
            break;
        }
        q=p->next;
        free(p);
        p=q;
    }

    return 0;
}
//18->94->58->17->27->20->43->57->75->78->
//18->94->05->58->17->27->20->43->57->75->78->
//18->94->05->58->27->20->43->57->75->78->
//05->18->20->27->43->57->58->75->78->94->
//43->57->58->75->78->94->05->18->20->27->
//

[解决办法]

引用:

Quote: 引用:

另外，楼主，你这k=1和k=2的赋值完全是多余啊，因为你后面使用时判断完k的值后，还是判断了指针的情况，这和你赋值时候的情况相同啊。还有就是k为1或者2的时候，链表3只取了未完链表后面的一个节点，而不是取出后面所有节点放入新链表。既然不管什么情况下都要执行s1=s1->next;s2=s2->next，为什么不放在if。。。else的外面做呢?


if(s1->a+s2->a==0){
         if(s1->next==NULL&&s2->next==NULL){
             k=0;
             
             s1=s1->next;
             s2=s2->next;
         }
         else if(s1->next==NULL&&s2->next!=NULL){
             s1=s1->next;
             s2=s2->next;
             k=1; 
 
             
        //     continue;
         }
         else if(s2->next==NULL&&s1!=NULL){
             s1=s1->next;
             s2=s2->next;
             k=2;
        //     continue;
         }
         else{
         s1=s1->next;
         s2=s2->next;
    //     continue;
         }

这个程序是一点点扩充的，这个地方改啦好多次，到最后我也发现啦，也就没再改！（谢谢你这么认真的读我的程序）

重复释放的问题，我在9楼用你的加法代码举例子说了一下，你还需要再检查一下代码中其他类似地方。所以这个代码不是delete2次不出问题，而是只要先delete了原链表，再delete运算结果的链表，应该就会出问题了。

热点排行

C++

关于连续释放链表空间的有关问题，求指导