设计双链表

dllist.h

#ifndef DLLIST_H_INCLUDED
#define DLLIST_H_INCLUDED
class DLLElement {
public:
    DLLElement( void *itemPtr, int sortKey ); // initialize a list element
    DLLElement *next; // next element on list
    // NULL if this is the last
    DLLElement *prev; // previous element on list
    // NULL if this is the first
    int key; // priority, for a sorted list
    void *item; // pointer to item on the list
};
class DLList {
public:
    DLList(); // initialize the list
    ~DLList(); // de-allocate the list
    void Prepend(void *item); // add to head of list (set key = min_key-1)
    void Append(void *item); // add to tail of list (set key = max_key+1)
    void *Remove(int *keyPtr); // remove from head of list
    // set *keyPtr to key of the removed item
    // return item (or NULL if list is empty)
    bool IsEmpty(); // return true if list has elements
    // routines to put/get items on/off list in order (sorted by key)
    void SortedInsert(void *item, int sortKey);
    void *SortedRemove(int sortKey); // remove first item with key==sortKey
    // return NULL if no such item exists
    void Print();
private:
    DLLElement *first; // head of the list, NULL if empty
    DLLElement *last; // last element of the list, NULL if empty
};

#endif // DLLIST_H_INCLUDED

dllist.cc

#include "dllist.h"
#include <iostream>

DLLElement::DLLElement(void *itemPtr,int sortKey)
{
    this->key=sortKey;
    this->next=NULL;
    this->prev=NULL;
    this->item=itemPtr;
}

//extern int error_type;

DLList::DLList()
{
    first = last = NULL;
}

DLList::~DLList()
{
    while (Remove(NULL) != NULL)
        ;
}

void DLList::Prepend(void *item)
{
    DLLElement *element = new DLLElement(item, 0);
    if (IsEmpty())
    {
        first = last = element;
        element->key = 0;
    }
    else
    {
        element->next = first;
        element->prev = NULL;
        element->key = first->key - 1;

        first->prev = element;
        first = element;
    }
}

void DLList::Append(void *item)
{
    DLLElement *element = new DLLElement(item, 0);
    if (IsEmpty())
    {
        first = last = element;
        element->key = 0;
    }

    else
    {
        element->next = NULL;
        element->prev = last;
        element->key = last->key + 1;

        last->next = element;
        last = element;
    }
}

void *DLList::Remove(int *keyPtr)
{
    DLLElement *element = first;
    void *thing;

    if (IsEmpty())
        return NULL;

    thing = first->item;
    if (first == last)
    { // dllist had one item, now has none
        first = NULL;
        last = NULL;
    }
    else
    {
        //bug 2
        /*
        if(error_type==2)
        {
            printf("[bug 2] Thread: ");
            currentThread->Print();
            printf("    Yield before remove first node (dllist.cc line78)\n\n");
            fflush(stdout);
            currentThread->Yield();
        }
        */
        first = element->next;
        first->prev = NULL;
    }
    if (keyPtr != NULL)
        *keyPtr = element->key;
    delete element;
    return thing;
}

bool DLList::IsEmpty()
{
    return first == NULL;
}

void DLList::SortedInsert(void *item, int sortKey)
{
    DLLElement *element = new DLLElement(item, sortKey);
    DLLElement *ptr; // keep track

    //bug 3
    /*
    if(error_type==3)
        {
            printf("---[bug 3]--- Thread: ");
            currentThread->Print();
            printf("    Yield after 'new' a node space (dllist.cc line107)\n\n");
            fflush(stdout);
            currentThread->Yield();
        }
        */
    if (IsEmpty())
    {   // if list is empty
        first = element;

        //bug 4
        /*
        if(error_type==4)
        {
            printf("---[bug 4]--- Thread: ");
            currentThread->Print();
            printf("    Yield when list is empty (dllist.cc line120)\n\n");
            fflush(stdout);
            currentThread->Yield();
        }
        */
        last = element;
    }
    else if (sortKey < first->key)
    {
        // item goes on front of list
        element->next = first;
        element->prev = NULL;

        //bug 5
        /*
        if(error_type==5)
        {
            printf("---[bug 5]--- Thread: ");
            currentThread->Print();
            printf("    Yield when insert first node (dllist.cc line137)\n\n");
            fflush(stdout);
            currentThread->Yield();
        }
        */
        first->prev = element;
        first = element;
    }
    else
    { // look for first elt in list bigger than item
        for (ptr = first; ptr->next != NULL; ptr = ptr->next)
        {
            if (sortKey < ptr->next->key)
            {
                element->next = ptr->next;
                element->prev = ptr;
                ptr->next = element;

                //bug 6
                /*
                if(error_type==6)
                {
                    printf("---[bug 6]--- Thread: ");
                    currentThread->Print();
                    printf("    Yield when insert common node (dllist.cc line159)\n\n");
                    fflush(stdout);
                    currentThread->Yield();
                }
                */
                element->next->prev = element;
                return;
            }
        }
        // item goes at end of list
        element->prev = last;
        element->next = NULL;

        last->next = element;
        last = element;
    }
}

void *DLList::SortedRemove(int sortKey)
{
    void *thing;
    DLLElement *ptr; // keep track

    if (IsEmpty())
        return NULL;

    // goes at the begin of dllist
    ptr = first;
    if (ptr->key == sortKey)
    {
        thing = ptr->item;
        first = ptr->next;
        ptr->next->prev = NULL;
        delete ptr;
        return thing;
    }

    for (ptr = first->next; ptr->next != NULL; ptr = ptr->next)
    {
        if (sortKey == ptr->key)
        {
            ptr->next->prev = ptr->prev;
            ptr->prev->next = ptr->next;
            thing = ptr->item;
            delete ptr;
            return thing;
        }
    }

    // goes at the end of dllist
    if (ptr->key == sortKey)
    {
        thing = ptr->item;
        last = ptr->prev;
        ptr->prev->next = NULL;
        delete ptr;
        return thing;
    }

    return NULL;
}
void DLList::Print(){
    DLLElement* cur=first;
    while(cur)
    {
        int *item = (int *)cur->item;
        printf("Item: %d, Key: %d -> ", *item, cur->key);
        cur=cur->next;
    }
    printf("NULL\n");
}

dllist-test.cc

#include "dllist.h"
#include<iostream>
struct MyItem {
    int data;
};
void test1()
{
    DLList list;
    int keys[] = {10, 5, 20, 1, 15};  // 要插入的数组
    int keyPtr;
    std::cout << "Adding items to the list:" << std::endl;
    for (int i = 0; i < 5; ++i) {
        if (i % 2 == 0) {
            // 偶数索引，使用Append
            list.Append(keys+i);
        } else {
            // 奇数索引，使用Prepend
            list.Prepend(keys+i);
        }
        std::cout << "Inserted item with value: " << keys[i] << std::endl;
    }

    // 测试Remove操作
    std::cout << "\nRemoving items from the list:" << std::endl;
    for (int i = 0; i < 5; ++i) {
        void* Item = list.Remove(&keyPtr);
        if (Item) {
            std::cout << "Removed item with key " << keyPtr << ", item : " << *(static_cast<int*>(Item)) << std::endl;
        } else {
            std::cout << "Attempted to remove an item but the list was empty." << std::endl;
        }
    }

    // 再次尝试移除元素，以测试链表为空的情况
    std::cout << "\nAttempting to remove from an empty list:" << std::endl;
    void* removedItem = list.Remove(&keyPtr);
    if (!removedItem) {
        std::cout << "List is empty, cannot remove any items." << std::endl;
    }
}
void test2()
{
    DLList list;

    // 测试IsEmpty函数
    if (list.IsEmpty()) {
        std::cout << "List is initially empty. (Pass)" << std::endl;
    } else {
        std::cout << "List is not initially empty. (Fail)" << std::endl;
    }

    // 创建一个MyItem实例，并添加到列表中
    MyItem item1 = {1};
    list.Prepend(&item1);

    // 再次测试IsEmpty函数
    if (!list.IsEmpty()) {
        std::cout << "List is not empty after Prepend. " << std::endl;
    } else {
        std::cout << "List is empty after Prepend. " << std::endl;
    }

    // 测试SortedInsert函数
    MyItem item2 = {2};
    list.SortedInsert(&item2, 0);
    MyItem item3 = {15};
    list.SortedInsert(&item3, 15);

    MyItem item4 = {5};
    list.SortedInsert(&item4, 15);
    //利用Remove函数测试链表是否有序
    int sortkey;
    void *removedItem = list.Remove(&sortkey);
    if(removedItem){
        std::cout << "Removed item with key: "<<sortkey<<" and data: "<<((MyItem*)removedItem)->data<<". " << std::endl;
    }
    else{
        std::cout << "Failed to remove item from the head of the list" << std::endl;
    }

    // 测试SortedRemove函数
    removedItem = list.SortedRemove(15);
    if (removedItem) {
        std::cout << "Removed item with key 15 and data: "<<((MyItem*)removedItem)->data<<". " << std::endl;
    } else {
        std::cout << "Failed to remove item with key 15. " << std::endl;
    }
    removedItem = list.SortedRemove(15);
    if (removedItem) {
        std::cout << "Removed item with key 15 and data: "<<((MyItem*)removedItem)->data<<". " << std::endl;
    } else {
        std::cout << "Failed to remove item with key 15. " << std::endl;
    }
    removedItem = list.SortedRemove(15);
    if (removedItem) {
        std::cout << "Removed item with key 15 and data: "<<((MyItem*)removedItem)->data<<". " << std::endl;
    } else {
        std::cout << "Failed to remove item with key 15. " << std::endl;
    }
    // 进一步测试可以通过遍历列表并检查每个元素来实现
    // 但由于当前代码未提供遍历函数，我们仅通过已知操作的结果进行验证

    // 清理：由于析构函数应负责释放内存，我们在此不手动删除元素
    // 但为了完整性，可以添加代码来验证析构后的状态（如列表是否为空）
}
void test3()
{
    DLList list;
    int t=1;
    while(t)
    {
        std::cin>>t;
        int* p=new int(t);
        list.Append(p);
    }
    list.Print();
}
void test(int signal)
{
    switch(signal)
    {
        case 1:
            test1();
            break;
        case 2:
            test2();
            break;
        case 3:
            test3();
            break;
        default:
            break;
    }
}

dllist-driver.cc

// dllist-driver.cc
#ifndef dllist_driver_cc
#define dllist_driver_cc

#include "dllist.h"
#include <utility>
#include <cstdio>
#include<cstdlib>

extern int error_type;

void GenerateN(DLList *dllist, int N)
{
    while(N--)
    {
        int keyValue=rand()%100;
        int *item=new int;
        *item=keyValue-1;
        dllist->SortedInsert(item,keyValue);
        //printf("[thread]:");
        //currentThread->Print();
        printf("%d:%d has been inserted into the DLList\n",*item,keyValue);
    }
}

void RemoveN(DLList *dllist, int N)
{
    int *keyValue=NULL;
    while(N--)
    {
        int *item=(int*)dllist->Remove(keyValue);
        //printf("[thread]:");
        //currentThread->Print();
        printf("%d has been removed from the DLList\n",*item);
    }
}

#endif

main.cc

#include <iostream>
#include "dllist.h"
using namespace std;
DLList *dllist=new DLList();

extern void test(int);
extern void GenerateN(DLList *dllist, int N);
extern void RemoveN(DLList *dllist, int N);
void GenerateAndRemove(int N){
    GenerateN(dllist,N);
    // Bug 1
    /*
    if(error_type==1)
    {

        printf("---[bug 1]--- Thread: ");
        currentThread->Print();
        printf("    Yield after insert N node. (dllist.cc line76)\n\n");
        fflush(stdout);
        currentThread->Yield();
    }
    */
    RemoveN(dllist,N);
}
int main()
{
    int signal;
    cin>>signal;
    //test(signal);
    GenerateAndRemove(signal);
    return 0;
}