c++ - 使用数组的链表实现
问题描述
我刚刚开始了一个作业问题,要求我使用动态数组实现一个链表。
此分配的目的是对具有增长数组的单链表进行内存管理。C++ 类操作两个单链表(一个是空闲节点,另一个是占用节点),但不是拥有指向内存中地址的指针,而是动态数组和数组元素的索引将成为包含元素值和下一个节点索引的“节点”。
这是我的 .h 文件
class LList {
public:
// create an empty list
LList();
// determine if the list is empty
bool isEmpty() const;
// insert x at the beginning of the list
// precondition: there is enough heap memory
// postcondition: x is placed in the list as first element
void cons(int x);
// append x to the end of the list
// precondition: there is enough heap memory
// postcondition: x is placed as the last element
void append(int x);
// return a string consisting of all the elements of the list
// in the order in which they are in the list from first to last in this format:
// -> the string starts with "[" followed by the LList::DELIMITER
// -> for each element: the element's value followed by the LList::DELIMITER
// -> the string finishes with "]"
// e.g. a string of 3 elements "[ 41 36 999 ]"
std::string toString() const;
// return the number of elements in the list
int length() const;
// search x in the list
// postcondition: return true if found, false oth
bool found(int x) const;
// return the first element of the list and LList::NOT_DEFINED if the list is empty
int first() const;
// return the last element of the list and LList::NOT_DEFINED if the list is empty
int last() const;
// delete the first occurrence of x in the list
// postcondition: return true if x was removed, false otherwise
// give the length of the list, i.e. the number of elements in this list
bool remove(int x);
// mutator method (function) that reverses the list
void reverse();
// mutator method to transfer all the elements from the 'other' list into
// this list and place them at position pos of this list
// e.g. when pos == 0, all the elements of the 'other' list will
// be placed before the (original) elements of this list
// if pos >= length(), (i.e. if pos is greater than the length of this list),
// then all the elements of the 'other' list are appended to this list
// precondition: pos >= 0, length() >= 0, other.length() >= 0
// postcondition: all the elements of the 'other' list are removed from the 'other' list
// and placed into this list starting at position pos
// The lengths of both lists change:
// other.length() becomes 0 (all the elements get removed)
// All the elements of the 'other' list are now in this list and the first element
// of the 'other' list is at position pos of this list or at the end if pos >= length()
void splice(LList& other, int pos);
// return true if the lfSide list is equal to the rtSide list
friend bool operator == (const LList& lfSide, const LList& rtSide);
// copy constructor
// we assuming that there is enough heap memory to make a copy
LList(const LList&);
// overloaded assignment operator
// we assuming that there is enough heap memory to make a copy
LList& operator = (const LList&);
// destructor
~LList();
// string that separates the values of the list in toString
static const std::string DELIMITER;
// value returned when there is no last or no first element in the list
static const int NOT_DEFINED;
#ifndef NDEBUG
// dump the array (print the contents of the internal array)
// using the ostream passed which defaults to std::cout
void dumpNodesArray(std::ostream& out = std::cout) const;
#endif
private:
struct Node {
int item;
int next;
};
// the array of nodes has INITIAL_CAPACITY nodes
static const int INITIAL_CAPACITY = 4;
// dynamic array of nodes
Node *nodes;
// index of the first node in the linked list
int head;
// index of the first node of the "free nodes' list"
int free;
};
我的问题是我应该在哪里声明这个动态数组。在LList()
这个函数中?私下里?
还有如何声明这个数组,以便在它满时可以增加它的大小。
有人可以帮我找到一个开始的地方。
解决方案
推荐阅读
- java - Override equals on a cglib proxy
- android - 如何在 Firebase 通知中停止铃声管理器正在播放但不停止
- python - 使用 GridSearchCV 但不使用 GridSearchCV 时出错 - Python 3.6.7
- python-3.x - 如何收集光束变换的所有结果?
- google-app-engine - 在 Travis CI 中部署谷歌应用引擎时如何在运行时获得动态版本名称?
- blazor-server-side - 如何在 Blazor 中将存储在 DB 中的图像显示为字节 []
- xml - 如何在 Spring Boot 2 中使用内容协商建立自定义 xml 序列化
- airflow - 虚拟运算符的用例
- c++ - 如何使用排序和比较这两个函数在 C++ 中对 char 数组进行排序?
- html - 表格固定标题和可滚动正文,标题后面的内容有问题