设计双链表
dllist.h
#ifndef DLLIST_H_INCLUDED
#define DLLIST_H_INCLUDED
class DLLElement {
public:DLLElement( void *itemPtr, int sortKey ); // initialize a list elementDLLElement *next; // next element on list// NULL if this is the lastDLLElement *prev; // previous element on list// NULL if this is the firstint key; // priority, for a sorted listvoid *item; // pointer to item on the list
};
class DLList {
public:DLList(); // initialize the list~DLList(); // de-allocate the listvoid 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 existsvoid Print();
private:DLLElement *first; // head of the list, NULL if emptyDLLElement *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 nonefirst = 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 emptyfirst = 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 listelement->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 itemfor (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 listelement->prev = last;element->next = NULL;last->next = element;last = element;}
}void *DLList::SortedRemove(int sortKey)
{void *thing;DLLElement *ptr; // keep trackif (IsEmpty())return NULL;// goes at the begin of dllistptr = 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 dllistif (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) {// 偶数索引，使用Appendlist.Append(keys+i);} else {// 奇数索引，使用Prependlist.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;
}