请教双向链表有序插入的问题--错在哪里？？

时间：2021-11-08 11:28:13

//建立一个双向链表,在输入data的同时将其有序插入链表
//


#include <stdlib.h>
#include <iostream.h>
#include <conio.h>
#include "malloc.h"

typedef struct DulListStu 
{
int data;
struct DulListStu * prior;
struct DulListStu * next;
}Stu, * DulList;

//建立双链表
void Create(DulList &L,int n)//n是结点个数

{
int i;
Stu *pS,*p1;//p1是每次的比较结点

L=(DulList)malloc(sizeof(Stu));
pS=(DulList)malloc(sizeof(Stu));
L->next=NULL;//初始化L
         L->prior=NULL;
  

for(i=n;i>0;--i)
{
cout<<"请输入数据:"<<endl;
                  cin>>pS->data;

if (L->next=NULL)//第一次输入data，连在L后
{
p1=pS;//将pS值赋给p1
L->next=p1;
p1->prior=L;
p1->next=NULL;
}
else 
{

if (pS->data<=p1->data)//ps比p1小时，将ps插入
{
pS->next=p1;
p1->prior=pS;
p1->prior->next=pS;
pS->prior=p1->prior;
}
else//else将ps插入p1后
{

p1->next=pS;
pS->prior=p1;
p1=pS;//将当前ps值赋给p1
p1->next=NULL;
}
}
        

}
if(n)
cout<<"双链表成功建立！"<<endl<<endl;
else
cout<<"Null!"<<endl;

}

//正序输出链表
void ShowDulList_1(DulList &L)
{
Stu *p;
p=L->next;
while (p)
{
cout<<p->data<<endl;
p=p->next;
}
}

//主函数
void main()

{
    DulList L;
int InitStudentNum;
cout<<"请输入双链表的结点个数:";
cin>>InitStudentNum;
Create(L,InitStudentNum);
cout<<"当前的链表为："<<endl;

ShowDulList_1(L);

}
//错误是不能写入内存？？为什么，错在哪里，请详细说说，谢谢~

14 个解决方案

#1

兄弟，这一行的比较变成赋值了，
if (L->next=NULL)//第一次输入data，连在L后

最好这样写 if(NULL == L->next)

#2

你建立链表的算法好象有问题，第二次及以后每次加入节点需要重新分配空间才行，并且按你的程序来看，即链表成功建立，也不会是一个有序的链表

#3

==的错误改过来了
还是不行
我正在改
楼上的大哥能说详细点吗
为什么不能有序？

#4

#include <stdlib.h>
#include <iostream.h>
#include <conio.h>
#include "malloc.h"

typedef struct DulListStu 
{
int data;
struct DulListStu * prior;
struct DulListStu * next;
}Stu, * DulList;

//建立双链表
void Create(DulList &L,int n)//n是结点个数

{
int i;
Stu *pS,*p1;//p1是每次的比较结点

L=(DulList)malloc(sizeof(Stu));
这句应该移到循环内部 pS=(DulList)malloc(sizeof(Stu));
L->next=NULL;//初始化L
         L->prior=NULL;
  

for(i=n;i>0;--i)
{
上面的句子应该在此          pS=(DulList)malloc(sizeof(Stu));
cout<<"请输入数据:"<<endl;
                  cin>>pS->data;

if (L->next=NULL)//第一次输入data，连在L后
应该是             if (L->next==NULL)//第一次输入data，连在L后
{
p1=pS;//将pS值赋给p1
L->next=p1;
p1->prior=L;
p1->next=NULL;
}
else 
{

if (pS->data<=p1->data)//ps比p1小时，将ps插入
{
pS->next=p1;
p1->prior=pS;
p1->prior->next=pS;
pS->prior=p1->prior;
应该是                     
pS->next=p1;
pS->prior=p1->prior;
p1->prior->next=pS;
p1->prior=pS;
}
else//else将ps插入p1后
{

p1->next=pS;
pS->prior=p1;
p1=pS;//将当前ps值赋给p1
p1->next=NULL;
}
}
        

}
if(n)
cout<<"双链表成功建立！"<<endl<<endl;
else
cout<<"Null!"<<endl;

}

//正序输出链表
void ShowDulList_1(DulList &L)
{
Stu *p;
p=L->next;
while (p)
{
cout<<p->data<<endl;
p=p->next;
}
}

//主函数
void main()

{
    DulList L;
int InitStudentNum;
cout<<"请输入双链表的结点个数:";
cin>>InitStudentNum;
Create(L,InitStudentNum);
cout<<"当前的链表为："<<endl;

ShowDulList_1(L);

}

#5

谢谢~
现在每次新加结点都分配空间了
也有输出结果了
可是排序结果还是不正确？

#6

每次插入要有一个遍历链表的过程，也就是说要有一个循环的遍历，多次比较，直到找到插入点为止，而你只进行了一次比较，所以你只保证了插入节点和你所比较的节点的有序，但不能保证整个链表的有序。

#7

#include <stdlib.h>
#include <iostream.h>
#include <conio.h>
#include "malloc.h"

typedef struct DulListStu 
{
int data;
struct DulListStu * prior;
struct DulListStu * next;
}Stu, * DulList;

//建立双链表
void Create(DulList &L,int n)//n是结点个数

{
int i;
Stu *pS,*p1;//p1是每次的比较结点
Stu *Head;//Head是链表头

L=(DulList)malloc(sizeof(Stu));
这句应该移到循环内部 pS=(DulList)malloc(sizeof(Stu));
L->next=NULL;//初始化L
         L->prior=NULL;
         Head = L;
  

for(i=n;i>0;--i)
{
上面的句子应该在此          pS=(DulList)malloc(sizeof(Stu));
cout<<"请输入数据:"<<endl;
                  cin>>pS->data;

if (L->next=NULL)//第一次输入data，连在L后
应该是             if (L->next==NULL)//第一次输入data，连在L后
{
p1=pS;//将pS值赋给p1
L->next=p1;
p1->prior=L;
p1->next=NULL;
}
else 
{
                           pl = Head;
while(pl->Next != NULL)
                           {
                                if(pl->Data > ps->Data)
                                {
                                    break;
                                 }
                                 pl = pl->Next;
                           }
                           if(pl->Next != NULL)
                           {
    pS->next=p1;
    pS->prior=p1->prior;
    p1->prior->next=pS;
    p1->prior=pS;
                            }
                            else
                            {
                                pl->Next = pS;
                                pS->prior = pl;
                                pS->Next = NULL;
                            }
}
        

}
if(n)
cout<<"双链表成功建立！"<<endl<<endl;
else
cout<<"Null!"<<endl;

}

//正序输出链表
void ShowDulList_1(DulList &L)
{
Stu *p;
p=L->next;
while (p)
{
cout<<p->data<<endl;
p=p->next;
}
}

//主函数
void main()

{
    DulList L;
int InitStudentNum;
cout<<"请输入双链表的结点个数:";
cin>>InitStudentNum;
Create(L,InitStudentNum);
cout<<"当前的链表为："<<endl;

ShowDulList_1(L);

}

#8

你现在的排序,不过是把比pl小的的节点,放在pl前，比pl大的就放在pl后,

#9

好久不写代码了，写起来有点力不从心，我也是新手。
 houwenqiang() ，本来插入的就是一个有序队列，所以循环可改成
          while((p1->next!=NULL) && (pS->data > p1->data))
{
    p1=p1->next;
}
从效率上看好象要好一点。
另外找到插入点要考虑插入的是头、尾还是中间节点三种情况。
tusea(飞呀) 《数据结构》上关于这些有详细的算法，可以找书来看看。

#10

谢谢诸位
现在的问题正如ballguest()所言，新结点ps如比p1大，插在p1后，这是对的
但是如ps比p1小，就只是插在p1前，没有继续与更前的结点比较
不知说的对不对
我正在改：）

#11

#include <stdlib.h>
#include <conio.h>
#include <malloc.h>
#include <iostream.h>

typedef struct DulListStu //定义双链表结点结构体
{
int data;
struct DulListStu * prior;
struct DulListStu * next;
}Stu, * DulList;

//创建双链表，并在输入数据data的同时为各个结点排序
void Create(DulList &L,int n)//n是结点个数

{
int i;
Stu *pS,*p1,*p2;//?p1为每次被比较的当前结点
Stu *Head;//Head是链表头

L=(DulList)malloc(sizeof(Stu));

L->next=NULL;//链表初始化
    L->prior=NULL;
 

for(i=n;i>0;--i)
{
pS=(DulList)malloc(sizeof(Stu));//为新结点开辟空间
cout<<"请输入数据:"<<endl;
        cin>>pS->data;//输入新结点

if (L->next==NULL)//将第一个结点直接连上
{
p1=pS;//将pS赋给p1
L->next=p1;
p1->prior=L;
p1->next=NULL;
}
else 
{

if (pS->data<=p1->data)//?如果pS的值小于当前结点，插在其前方
{
p2=p1;//记录p1结点
while(p2->prior!=L)//p前面还有结点，继续比较
{
if (pS->data<=p2->prior ->data)//pS仍比当前结点小
{
p2=p2->prior;//继续将p2前移
}
                    else// pS比当前结点大，将pS插在当前结点后
{
p2->next=pS;
pS->prior=p2;
pS->next=p2->next;
p2->next->prior=pS;
}
if (p2->prior==L)//前面已无结点，插在当前结点前方
{
pS->next=p2;
pS->prior=p2->prior;
p2->prior->next=pS;
p2->prior=pS;
}


}


}



else//否则插在p1的后面
{

p1->next=pS;
pS->prior=p1;
p1=pS;//重新设立当前结点
p1->next=NULL;
}

}
        

}
if(n)
cout<<"双链表成功建立！"<<endl<<endl;
else
cout<<"Null!"<<endl;

}

//正序输出链表
void ShowDulList_1(DulList &L)
{
Stu *p;
p=L->next;
while (p)
{
cout<<p->data<<endl;
p=p->next;
}
}



//主函数
void main()

{
    DulList L;
int InitStudentNum;
cout<<"请输入双链表的结点个数:";
cin>>InitStudentNum;
Create(L,InitStudentNum);
cout<<"当前的链表为："<<endl;

ShowDulList_1(L);

//ShowDulList_2(L);


}
//现在只能输出最后一个数据，why？？

#12

看看我的代码，创建、排序、销毁都是经过测试没有问题。
编译：g++ -o dual_link dual_link.cpp
平台：RedHat9.0

#include <iostream.h>
#include <stdlib.h>

struct DualLink
{
int data;
struct DualLink *prior;
struct DualLink *next;
};

void Create_Link( struct DualLink *head, const int num )
{
if( num < 1 ) return;

struct DualLink *p = NULL;
struct DualLink *tmp = NULL;

head->prior = NULL;
head->next = NULL;

for(int i=0; i<num; i++)
{
p = new DualLink;
cout<<"Please input data:"<<endl;
cin >> p->data;

if( head->prior == NULL && head->next == NULL ) //第一次&Icirc; {
p->prior = head;
p->next = NULL;
head->next = p;
}
else
{
tmp = head->next;
while( tmp != NULL )
{
if( p->data < tmp->data ) //插到中间
{
p->next = tmp;
p->prior = tmp->prior;
tmp->prior->next = p;
tmp->prior = p;
break;
}
else if( tmp->next == NULL )//插到末尾
{
p->next = NULL;
p->prior = tmp;
tmp->next = p;
break;
};
tmp = tmp->next;
} 
}
}
};

void Show_Link(const struct DualLink *head)
{
struct DualLink *tmp = head->next;

while( tmp != NULL )
{
cout<<tmp->data<<endl;
tmp = tmp->next;
};
};

void Destroy_Link(const struct DualLink *head)
{
struct DualLink *tmp = head->next;
struct DualLink *cur = head->next;

while( tmp != NULL )
{
tmp = tmp->next;
delete cur;
cur = tmp;
};
};

int main()
{
int number;
DualLink head;

cout<<"Please input node number:"<<endl;
cin>>number;
cout<<"Link node number is "<<number<<endl;

printf("----- Create Link -----\n");
Create_Link(&head, number);
printf("----- Show Link -----\n");
Show_Link(&head);
printf("----- Destroy Link -----\n");
Destroy_Link(&head);

return 1;
}

#13

看不懂！唉。。。。

#14

yuanlei1978113() 的程序写的很漂亮
谢谢各位：）
我已经明白了

#1

兄弟，这一行的比较变成赋值了，
if (L->next=NULL)//第一次输入data，连在L后

最好这样写 if(NULL == L->next)

#2

你建立链表的算法好象有问题，第二次及以后每次加入节点需要重新分配空间才行，并且按你的程序来看，即链表成功建立，也不会是一个有序的链表

#3

==的错误改过来了
还是不行
我正在改
楼上的大哥能说详细点吗
为什么不能有序？

#4

#include <stdlib.h>
#include <iostream.h>
#include <conio.h>
#include "malloc.h"

typedef struct DulListStu 
{
int data;
struct DulListStu * prior;
struct DulListStu * next;
}Stu, * DulList;

//建立双链表
void Create(DulList &L,int n)//n是结点个数

{
int i;
Stu *pS,*p1;//p1是每次的比较结点

L=(DulList)malloc(sizeof(Stu));
这句应该移到循环内部 pS=(DulList)malloc(sizeof(Stu));
L->next=NULL;//初始化L
         L->prior=NULL;
  

for(i=n;i>0;--i)
{
上面的句子应该在此          pS=(DulList)malloc(sizeof(Stu));
cout<<"请输入数据:"<<endl;
                  cin>>pS->data;

if (L->next=NULL)//第一次输入data，连在L后
应该是             if (L->next==NULL)//第一次输入data，连在L后
{
p1=pS;//将pS值赋给p1
L->next=p1;
p1->prior=L;
p1->next=NULL;
}
else 
{

if (pS->data<=p1->data)//ps比p1小时，将ps插入
{
pS->next=p1;
p1->prior=pS;
p1->prior->next=pS;
pS->prior=p1->prior;
应该是                     
pS->next=p1;
pS->prior=p1->prior;
p1->prior->next=pS;
p1->prior=pS;
}
else//else将ps插入p1后
{

p1->next=pS;
pS->prior=p1;
p1=pS;//将当前ps值赋给p1
p1->next=NULL;
}
}
        

}
if(n)
cout<<"双链表成功建立！"<<endl<<endl;
else
cout<<"Null!"<<endl;

}

//正序输出链表
void ShowDulList_1(DulList &L)
{
Stu *p;
p=L->next;
while (p)
{
cout<<p->data<<endl;
p=p->next;
}
}

//主函数
void main()

{
    DulList L;
int InitStudentNum;
cout<<"请输入双链表的结点个数:";
cin>>InitStudentNum;
Create(L,InitStudentNum);
cout<<"当前的链表为："<<endl;

ShowDulList_1(L);

}

#5

谢谢~
现在每次新加结点都分配空间了
也有输出结果了
可是排序结果还是不正确？

#6

每次插入要有一个遍历链表的过程，也就是说要有一个循环的遍历，多次比较，直到找到插入点为止，而你只进行了一次比较，所以你只保证了插入节点和你所比较的节点的有序，但不能保证整个链表的有序。

#7

#include <stdlib.h>
#include <iostream.h>
#include <conio.h>
#include "malloc.h"

typedef struct DulListStu 
{
int data;
struct DulListStu * prior;
struct DulListStu * next;
}Stu, * DulList;

//建立双链表
void Create(DulList &L,int n)//n是结点个数

{
int i;
Stu *pS,*p1;//p1是每次的比较结点
Stu *Head;//Head是链表头

L=(DulList)malloc(sizeof(Stu));
这句应该移到循环内部 pS=(DulList)malloc(sizeof(Stu));
L->next=NULL;//初始化L
         L->prior=NULL;
         Head = L;
  

for(i=n;i>0;--i)
{
上面的句子应该在此          pS=(DulList)malloc(sizeof(Stu));
cout<<"请输入数据:"<<endl;
                  cin>>pS->data;

if (L->next=NULL)//第一次输入data，连在L后
应该是             if (L->next==NULL)//第一次输入data，连在L后
{
p1=pS;//将pS值赋给p1
L->next=p1;
p1->prior=L;
p1->next=NULL;
}
else 
{
                           pl = Head;
while(pl->Next != NULL)
                           {
                                if(pl->Data > ps->Data)
                                {
                                    break;
                                 }
                                 pl = pl->Next;
                           }
                           if(pl->Next != NULL)
                           {
    pS->next=p1;
    pS->prior=p1->prior;
    p1->prior->next=pS;
    p1->prior=pS;
                            }
                            else
                            {
                                pl->Next = pS;
                                pS->prior = pl;
                                pS->Next = NULL;
                            }
}
        

}
if(n)
cout<<"双链表成功建立！"<<endl<<endl;
else
cout<<"Null!"<<endl;

}

//正序输出链表
void ShowDulList_1(DulList &L)
{
Stu *p;
p=L->next;
while (p)
{
cout<<p->data<<endl;
p=p->next;
}
}

//主函数
void main()

{
    DulList L;
int InitStudentNum;
cout<<"请输入双链表的结点个数:";
cin>>InitStudentNum;
Create(L,InitStudentNum);
cout<<"当前的链表为："<<endl;

ShowDulList_1(L);

}

#8

你现在的排序,不过是把比pl小的的节点,放在pl前，比pl大的就放在pl后,

#9

好久不写代码了，写起来有点力不从心，我也是新手。
 houwenqiang() ，本来插入的就是一个有序队列，所以循环可改成
          while((p1->next!=NULL) && (pS->data > p1->data))
{
    p1=p1->next;
}
从效率上看好象要好一点。
另外找到插入点要考虑插入的是头、尾还是中间节点三种情况。
tusea(飞呀) 《数据结构》上关于这些有详细的算法，可以找书来看看。

#10

谢谢诸位
现在的问题正如ballguest()所言，新结点ps如比p1大，插在p1后，这是对的
但是如ps比p1小，就只是插在p1前，没有继续与更前的结点比较
不知说的对不对
我正在改：）

#11

#include <stdlib.h>
#include <conio.h>
#include <malloc.h>
#include <iostream.h>

typedef struct DulListStu //定义双链表结点结构体
{
int data;
struct DulListStu * prior;
struct DulListStu * next;
}Stu, * DulList;

//创建双链表，并在输入数据data的同时为各个结点排序
void Create(DulList &L,int n)//n是结点个数

{
int i;
Stu *pS,*p1,*p2;//?p1为每次被比较的当前结点
Stu *Head;//Head是链表头

L=(DulList)malloc(sizeof(Stu));

L->next=NULL;//链表初始化
    L->prior=NULL;
 

for(i=n;i>0;--i)
{
pS=(DulList)malloc(sizeof(Stu));//为新结点开辟空间
cout<<"请输入数据:"<<endl;
        cin>>pS->data;//输入新结点

if (L->next==NULL)//将第一个结点直接连上
{
p1=pS;//将pS赋给p1
L->next=p1;
p1->prior=L;
p1->next=NULL;
}
else 
{

if (pS->data<=p1->data)//?如果pS的值小于当前结点，插在其前方
{
p2=p1;//记录p1结点
while(p2->prior!=L)//p前面还有结点，继续比较
{
if (pS->data<=p2->prior ->data)//pS仍比当前结点小
{
p2=p2->prior;//继续将p2前移
}
                    else// pS比当前结点大，将pS插在当前结点后
{
p2->next=pS;
pS->prior=p2;
pS->next=p2->next;
p2->next->prior=pS;
}
if (p2->prior==L)//前面已无结点，插在当前结点前方
{
pS->next=p2;
pS->prior=p2->prior;
p2->prior->next=pS;
p2->prior=pS;
}


}


}



else//否则插在p1的后面
{

p1->next=pS;
pS->prior=p1;
p1=pS;//重新设立当前结点
p1->next=NULL;
}

}
        

}
if(n)
cout<<"双链表成功建立！"<<endl<<endl;
else
cout<<"Null!"<<endl;

}

//正序输出链表
void ShowDulList_1(DulList &L)
{
Stu *p;
p=L->next;
while (p)
{
cout<<p->data<<endl;
p=p->next;
}
}



//主函数
void main()

{
    DulList L;
int InitStudentNum;
cout<<"请输入双链表的结点个数:";
cin>>InitStudentNum;
Create(L,InitStudentNum);
cout<<"当前的链表为："<<endl;

ShowDulList_1(L);

//ShowDulList_2(L);


}
//现在只能输出最后一个数据，why？？

#12

看看我的代码，创建、排序、销毁都是经过测试没有问题。
编译：g++ -o dual_link dual_link.cpp
平台：RedHat9.0

#include <iostream.h>
#include <stdlib.h>

struct DualLink
{
int data;
struct DualLink *prior;
struct DualLink *next;
};

void Create_Link( struct DualLink *head, const int num )
{
if( num < 1 ) return;

struct DualLink *p = NULL;
struct DualLink *tmp = NULL;

head->prior = NULL;
head->next = NULL;

for(int i=0; i<num; i++)
{
p = new DualLink;
cout<<"Please input data:"<<endl;
cin >> p->data;

if( head->prior == NULL && head->next == NULL ) //第一次&Icirc; {
p->prior = head;
p->next = NULL;
head->next = p;
}
else
{
tmp = head->next;
while( tmp != NULL )
{
if( p->data < tmp->data ) //插到中间
{
p->next = tmp;
p->prior = tmp->prior;
tmp->prior->next = p;
tmp->prior = p;
break;
}
else if( tmp->next == NULL )//插到末尾
{
p->next = NULL;
p->prior = tmp;
tmp->next = p;
break;
};
tmp = tmp->next;
} 
}
}
};

void Show_Link(const struct DualLink *head)
{
struct DualLink *tmp = head->next;

while( tmp != NULL )
{
cout<<tmp->data<<endl;
tmp = tmp->next;
};
};

void Destroy_Link(const struct DualLink *head)
{
struct DualLink *tmp = head->next;
struct DualLink *cur = head->next;

while( tmp != NULL )
{
tmp = tmp->next;
delete cur;
cur = tmp;
};
};

int main()
{
int number;
DualLink head;

cout<<"Please input node number:"<<endl;
cin>>number;
cout<<"Link node number is "<<number<<endl;

printf("----- Create Link -----\n");
Create_Link(&head, number);
printf("----- Show Link -----\n");
Show_Link(&head);
printf("----- Destroy Link -----\n");
Destroy_Link(&head);

return 1;
}

#13

看不懂！唉。。。。

#14

yuanlei1978113() 的程序写的很漂亮
谢谢各位：）
我已经明白了
标签：

相关文章