双链表实现

问题描述 投票：1回答：3

我出于教育目的而编写的双链表程序在语法上存在一些问题。我已经在头文件中创建了一个结构，我的主程序似乎还不错，但是在.cpp文件中实现我的功能给我带来了极大的困难。我很难辨别将记录插入列表的三种情况。具体来说，分配内存，初始化列表的开头和结尾以及语句的顺序令我感到困惑，因为传递要添加到我的列表中的记录副本也是如此。

我的头文件如下：

struct rec
{
   char * id;
   char firstname[15];
   char lastname[15];
   struct rec* prev;
   struct rec* next;
};


int AddItem ( rec r );
int DeleteItem ( char* delid );
void PrintList ( int order );

困难所在的我的.cpp文件如下：

#include <iostream>
#include "list.h"
#include <string.h>
using namespace std;

// These pointers refer to the head and tail of the list.
rec* first = NULL;
rec* last = NULL;

int AddItem( Rec r )
{

   rec* newRecEntry;
   rec* current = NULL;
   rec* previous = NULL;

   // Check for duplicate id
   current = first;
   while (current)
   {
     if( strcmp(current -> id, r.id) == 0)
      {
         return 0;
      }
     else
      // Create a new node
      {
         newRecEntry = new Rec;
         newRecEntry->id = new char[strlen(r.id)+1];
         strcpy(newRecEntry->id, r.id);
         strcpy(newRecEntry->firstname,r.firstname);
         strcpy(newRecEntry->lastname,r.lastname);
         newRecEntry->next = NULL;
         newRecEntry->prev = NULL;
      }
      // Find the appropriate position for the node and insert accordingly
      // Check to see if the list is empty
      if (first == NULL)
      {
         first = newRecEntry;
         last = newRecEntry;
      }
      else if ( r.lastname>last.lastname)
      {




      else
      {

   return 0;
}

/*int DeleteItem(char* ID)

我应该能够在列表的开头，中间和结尾插入。根据ID从列表中删除一个项目，并根据用户输入以升序或降序打印列表，但我首先只是想处理将项目添加到所述列表中。我的函数定义如下，并且还包含一些错误

lists.cpp

#include <iostream>
#include "list.h"
#include <string.h>
using namespace std;

// These pointers refer to the head and tail of the list.
   rec* first = NULL;
   rec* last = NULL;

int AddItem( Rec r )
{

   rec* newRecEntry;
   rec* current = NULL;
   rec* previous = NULL;

   // Check for duplicate id
   current = first;
   while (current)
   {
     if( strcmp(current -> id, r.id) == 0)
      {
         return 0;
      }
     else
     // Create a new node
      {
         newRecEntry = new Rec;
         newRecEntry->id = new char[strlen(r.id)+1];
         strcpy(newRecEntry->id, r.id);
         strcpy(newRecEntry->firstname,r.firstname);
         strcpy(newRecEntry->lastname,r.lastname);
         newRecEntry->next = NULL;
         newRecEntry->prev = NULL;
      }
      // Find the appropriate position for the node and insert accordingly
      // Check to see if the list is empty
      if (first == NULL)
      {
         first = newRecEntry;
         last = newRecEntry;
      }
      else if ( r.lastname>last.lastname)
      {




      else
      {

   return 0;
}

/*int DeleteItem(char* ID)
{
   rec
}
*/



/*void printList(int order)
{
loop
 {
   cout << ptr -> Id << " ";
   cout << ptr -> firstname << " ";
   cout << ptr -> lastname << " ";
   cout << ptr -> prev << " ";  // address of previous
   cout <<  ptr << " ";   // address of item
   cout << ptr -> next << " ";  //  address of next item
 }

}

主要如下：

#include <iostream>
#include "list.h"
#include <string.h>  // <string>

using namespace std;

void main (void)
{
   int choice, printorder;
   char idbuffer[100];
   rec r;


do
{
  cout << "Enter your choice 1 Add, 2 Delete, 3 Print, 0 quit "<<endl;
  cin >> choice;

   switch ( choice )
   {
      case 1:  //AddItem
         cout << "\nEnter ID ";
         cin >> idbuffer;

         r.id = idbuffer;
         cout << "\nFirst Name ";
         cin >> r.firstname;
         cout << "\nLast Name ";
         cin >>  r.lastname;
         if ( AddItem ( r ) )
         {
            cout << "\nSuccess!\n";
         }
         else
         {
            cout << "\nItem failed to be added\n";
         }

         break;
      case 2:  //Delete
         cout << "\nEnter id :";
         cin >> idbuffer;
         if ( DeleteItem ( idbuffer ) )
         {
            cout << "\nDelete OK\n";
         }
         else
         {
            cout << "\nDelete Failed for " << idbuffer;
         }
         break;
      case 3: // Print
        cout << "Enter order 0 - Ascending, 1 - Descending\n";
        cin >> printorder;
        PrintList (printorder);
        break;
      case 0:  // quit
         break;


      default: // bad choice
         break;
   } // end switch

}
while ( choice != 0 );// end do while
}  // end main
c++ doubly-linked-list
3个回答
1
投票

看起来可能不像，但即使这个功能

int AddItem(Record entry)
{
   Record* newRecordPointer;
   newRecordPointer=new Record;
   strcpy(newRecordPointer->firstName,entry.firstName);
   strcpy(newRecordPointer->lastName,entry.lastName);
   newRecordPointer->ID=new char[strlen(entry.ID)+1];
   strcpy(newRecordPointer->ID, entry.ID);
   return 0;
}

正在尝试做太多事情。

让我们编写将项目添加到列表的伪代码描述：

  1. 创建一个新节点
  2. 填充 新节点和提供的值
  3. attach从新节点到列表

我已经标记了所涉及的动词和名词，并且您已经可以看到函数中缺少名词之一。您要AddItem将一个项目添加到列表中...但是您没有提供要处理的列表。

清楚地写出您的期望也很有用：

  1. 在AddItem被调用之前：
    • 它需要工作清单
    • 我们没有列表容器类，只有记录，所以我们必须传递Record
    • 假设我们要添加新项目之后传入的Record
  2. AddItem被调用后：
    • 无论我们传入什么Record，它的Next都应指向新节点
    • 新节点的Previous应指向传入的节点
    • 等等等（这些是标准的双向链表插入行为）
  3. 稍后请注意：我们没有描述如何存储空白列表
    • 如果是循环列表，则空白列表将是Record，其Next和Previous成员指向其自身
    • 如果是线性的，它们可能都为NULL
    • 它可能只是一个NULL指针，但是将第一个节点添加到一个空列表需要更多的努力

因此，假设可能起作用的最小功能是：

void AddItem(Record *insert_after, Record value)
{
    Record *new_node = CreateRecord();
    CopyRecordValues(new_node, &value);
    AttachAfter(insert_after, new_node);
}

[请注意，如果我们正在编写真正的C ++，则前两行仅可以使用copy构造函数Record *new_node = new Record(value)，但是要比从我们开始的地方习惯的C ++代码进行更改，将花费更多的更改。

现在，您可以：

  • 实现这三个功能？ （CreateRecord和CopyRecordValues已在您当前的代码中处理过）
  • 为您的其他操作编写等效的伪代码，然后自行翻译？
0
投票

尝试更改此内容：

int AddItem(Record entry);

为此：

Record* AddItem(Record entry, Record *insertion_point = NULL );

如果insertion_point为NULL，则可以假定Record是新列表的开头。

现在您有足够的信息来设置Next和Previous指针，并返回新创建的节点。

0
投票

首先，您必须定义第一项和结束项。

可能是

  • 首先将Previous分配给NULL的项目。
  • 已将Next分配给NULL的项目结束。

为简单起见，我删除了Record的某些字段，这不是最好的，请小心，您应该执行许多错误处理并注意异常：

struct Record
{
    int id;
    Record* Next;
    Record* Previous;
};

Record *CreateList(int id)
{
    Record *rec = new Record;
    rec->id = id;
    rec->Next = NULL;
    rec->Previous = NULL;
    return rec;
}

void AddItemAfter(Record *item, int id)
{
    if (!item)
        return;

    Record* newRecordPointer = new Record;
    newRecordPointer->id = id;
    newRecordPointer->Next = NULL;
    newRecordPointer->Previous = NULL;

    newRecordPointer->Next = item->Next;
    item->Next = newRecordPointer;
    newRecordPointer->Previous = item;
}

void ShowList(Record *list)
{
    Record *ptr = list;
    while (ptr)
    {
        cout << ptr->id << endl;
        ptr = ptr->Next;
    }
}

int main()
{
    Record *list = CreateList(1);

    AddItemAfter(list, 2);
    AddItemAfter(list, 3);

    ShowList(list);
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.