将节点插入到双链表中
我想将包含名称的新节点插入到双链表的正确位置。基本上插入排序是我想在这里实现的。将节点插入到双链表中
这是插入函数的代码却存在问题:
- 如果您将使用相同的值一次以上的节点,突破了双向链表!
- 它没有正确排序列表。
下面是类代码:
class Doubly
{
private:
struct node
{
string name; //stores name
node* next; //points to next node
node* prev; //points to previous node
};
node* head; //points to the first node in the list
node* last; //points to the last node in the list
public:
Doubly(); //cstrctr
~Doubly(); //dstrctr
bool empty() const { return head==NULL; }
void insert(const string&);
void remove(const string&);
void print(ostream& OutStream) const;
void sort (bool);
};
这里是插入的代码:我认为这个问题是在列表的头部插入时
void Doubly::insert (const string& input)
{
// Insertion into an Empty List.
if(empty()) //create a new list with one node = Head/Null
{
node* name = new node;
head = name;
last = name;
name -> prev = NULL;
name -> next = NULL;
name -> name = input; //
}
//Insertion into a populated list
else
{
node* newnode;
newnode = head;
while (input > newnode -> name && newnode -> next != last -> next)
newnode = newnode -> next;
if (newnode == head)
{
node* name = new node;
name -> name = input;
name -> prev = newnode;
name -> next = NULL;
head -> next = name;
last = name;
}
else
{
if (newnode == last && input > last -> name) //Add the name to the end of the linked list
{
last -> next = new node;
(last -> next) -> prev = last;
last = last -> next;
last -> next = NULL;
last -> name = input;
}
else
{
node* name = new node;
name -> name = input;
name -> next = newnode;
(newnode -> prev) -> next = name;
name -> prev = newnode -> prev;
newnode -> prev = name;
}
}
}
}
,并你只有一个元素,while (input > newnode -> name && newnode -> next != last -> next)
可以退出是因为2个原因,并且你假设如果指针仍然在头部,你必须在后面插入它,但是也许它刚刚离开,因为只有一个元素你呢必须在头部之前插入新的。
所以你可能必须做一些事情,如:
if (newnode->next == head->next) {
// Create the node and set the common values for all the cases
node* name = new node;
name->name = input;
if (input > newnode->name) { // Insert as second element
name->prev = newnode;
name->next = NULL;
newnode->prev = NULL;
newnodw->next = name;
head = newnode;
last = name;
}
else { // Insert as first element
name->prev = NULL;
name->next = newnode;
newnode->prev = name;
newnodw->next = NULL;
head = name;
last = newnode;
}
如果您的*两个分支都有重复代码的*很多* - 您可以通过重构使其更具可读性。 – tucuxi 2015-04-27 13:03:32
@tucuxi不是很多的代码,但你是对的,一些重构来改进它是一个很好的选择 – pconcepcion 2015-05-04 10:52:55
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
struct dnode
{
int data;
struct dnode *p,*n;
};
typedef struct dnode dnode;
dnode *start,*last;
dnode *createNode(int ele)
{
dnode *nnode;
nnode=(dnode*)malloc(sizeof(dnode));
nnode->n=NULL;
nnode->data=ele;
return nnode;
}
dnode *insertBegining(int ele)
{
dnode *nnode,*curr,*prev;
nnode=createNode(ele);
if(start==NULL)
{
start=nnode;
nnode->p=NULL;
return start;
}
curr=start;
start=nnode;
nnode->p=NULL;
nnode->n=curr;
curr->p=nnode;
return start;
}
dnode *insertLast(int ele)
{
dnode *nnode,*curr,*prev;
nnode=createNode(ele);
if(start==NULL)
{
start=nnode;
nnode->p=NULL;
return start;
}
curr=start;
while(curr!=NULL)
{
prev=curr;
curr=curr->n;
}
prev->n=nnode;
nnode->p=prev;
return start;
}
void display()
{
dnode *curr;
curr=start;
while(curr!=NULL)
{
printf("%d--->",curr->data);
curr=curr->n;
}
}
void main()
{
int ch,ele;
clrscr();
do
{
printf("\nEnter choice");
printf("\n1-insert beginning");
printf("\n2-insert last");
printf("\n3-display");
printf("\n4-Exit");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\nEnter Number");
scanf("%d",&ele);
insertBegining(ele);
break;
case 2:
printf("enter number");
scanf("%d",&ele);
insertLast(ele);
break;
case 3:
display();
break;
}
}
while(ch!=4);
getch();
}
复制和粘贴很多没有评论的代码通常是不被赞同的。解释原始代码中的问题要好得多。 – tucuxi 2015-04-27 13:04:56
这比我预期的是读了'newnode更难 - > name';所有这些额外的空间都很难超越。 :) – sarnold 2011-03-23 11:29:06
一个建议:使列表头看起来足够像列表项目并使列表循环。由于空列表是一个指向“next”和“prev”的头部,所以你总是可以访问任何东西的“next”和“prev”,所以你只有一个而不是四个,减少了代码量并因此可能出现四次错误的地方。 – 2011-03-23 11:48:35
另一个建议:除非你正在做家庭作业(如果你这样做,你应该如此标记你的问题),**不要自己实现列表**你标记了C++的问题,所以你有STL,如果你需要特别的东西,可以拉升。理解链表是很好的,但从不在实践中自己写。 – 2011-03-23 11:51:34