Lab3.1：Priority Sorted Doubly Linked List

设计双链表

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
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;
}

DLList::DLList() : first(NULL), last(NULL) {}

DLList::~DLList() {
    int key;
    while (!IsEmpty()) {
        Remove(&key);
    }
}

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

void DLList::Append(void *item) {
    int sortkey=100;
    if(last)sortkey=last->key+1;
    DLLElement *element = new DLLElement(item, sortkey);
    if (last == NULL) {
        first = last = element;
    } else {
        element->prev = last;
        last->next = element;
        last = element;
    }
}

void *DLList::Remove(int *keyPtr) {
    if (IsEmpty()) return NULL;
    DLLElement *element = first;
    *keyPtr = element->key;
    first = first->next;
    if (first == NULL) last = NULL;
    else first->prev = NULL;
    void *item = element->item;
    delete element;
    return item;
}

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

void DLList::SortedInsert(void *item, int sortKey) {
    DLLElement *newElement = new DLLElement(item, sortKey);
    DLLElement *current = first;
    if(first==NULL){//链表为空
        first=last=newElement;
        return;
    }
    while (current != NULL && current->key < sortKey) {
        current = current->next;
    }
    if (current == NULL) {
        last->next = newElement;
        newElement->prev = last;
        last = newElement;
    } else if (current->prev == NULL) {
        first = newElement;
        newElement->next = current;
        current->prev = newElement;
    } else {
        newElement->next = current;
        newElement->prev = current->prev;
        current->prev->next = newElement;
        current->prev = newElement;
    }
}

void *DLList::SortedRemove(int sortKey) {
    DLLElement *current = first;
    while (current != NULL && current->key < sortKey) {
        current = current->next;
    }
    if (current == NULL) return NULL;
    if (current->key!=sortKey)return NULL;
    void *item = current->item;
    if(current==first){
        first = first->next;
        if(first==NULL)last=NULL;
        else first->prev=NULL;
    }
    else if(current==last){
        last = last->prev;
        if(last==NULL)first=NULL;
        else last->prev=NULL;
    }
    else
    {
        DLLElement *element2 = current->next;
        DLLElement *element1 = current->prev;
        element1->next=element2;
        element2->prev=element1;
    }
    delete current;
    return item;
}

dllist-driver.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 test(int signal)
{
    switch(signal)
    {
        case 1:
            test1();
            break;
        case 2:
            test2();
            break;
        default:
            break;
    }
}

main.cc

#include <iostream>

using namespace std;
extern void test(int);
int main()
{
    int signal;
    cin>>signal;
    test(signal);
    return 0;
}