C++ implements an instance of a static single linked list
- 2020-05-24 05:53:24
- OfStack
C++ implements instances of static single linked lists
The use of array to achieve static single linked list, and yan weimin book implementation is slightly different, do not set a recovery space. If you have any BUG or mistake, please give me more feedback. Thank you very much
/* Author : Moyiii
* Mail: lc09@vip.qq.com
* Static linked list implementation, for learning purposes only, of course if
* You can use it if you want.
*/
#include <iostream>
using namespace std;
#define MAX_LIST_SIZE 100
class Node
{
public:
int data;
int cur;
};
class SLinkList
{
public:
SLinkList();
// It's not that different from a normal linear list. Except for two distributions
// And the recovery node space function, the specific algorithm please refer to the textbook or
// The network information
int newNode();
bool deleteNode(int pos);
bool insertElem(int pos, int elem);
bool deleteElem(int pos);
int& getElem(int pos);
int getLength();
bool isEmpty();
void print();
void clear();
private:
int head;// You don't have to do that. Default is equal to 0
int space;
int length;
Node *elems;
};
SLinkList :: SLinkList()
{
// 0 The number position is the first few points, can not be changed, the initial point itself
// from 1~MAXLENGTH Is an assignable node, originally created by space management
elems = new Node[MAX_LIST_SIZE];
if(!elems)
{
cout << "Malloc failed!" << endl;
}
head = space = length = 0;
for(int i = 0; i < MAX_LIST_SIZE; ++i)
{
elems[i].data = i;
elems[i].cur = i + 1;
}
elems[MAX_LIST_SIZE - 1].cur = 0;
elems[0].cur = 0;
space = 1;
}
// from space Remove from the linked list of alternate nodes to point to 1 A node
int SLinkList :: newNode()
{
if(space == 0)
{
cout << "Space is full!" << endl;
return 0;
}
int pos = space;
space = elems[space].cur;
elems[pos].cur = 0;
return pos;
}
// Recovery node space
bool SLinkList :: deleteNode(int pos)
{
if(pos == 0)
{
cout << "Free space Error!" << endl;
return false;
}
elems[pos].cur = space;
space = pos;
return true;
}
// Insert the node, the idea is similar, to find the deleted node before 1 A node
// And then change the direction
bool SLinkList :: insertElem(int pos, int elem)
{
if(length == MAX_LIST_SIZE)
{
cout << "Space is Full" << endl;
return false;
}
if(pos < 1 || pos > length + 1)
{
cout << "Insert Over Bound" << endl;
return false;
}
int index = head;
for(int i = 1; i <= pos - 1; ++i)
{
index = elems[index].cur;
}
int node = newNode();
if(node == 0)
{
cout << "Space malloc failed" << endl;
return false;
}
elems[node].data = elem;
elems[node].cur = elems[index].cur;
elems[index].cur = node;
length++;
return true;
}
//1 Yes, be careful to recycle the deleted nodes to space
bool SLinkList :: deleteElem(int pos)
{
if(pos < 1 || pos > length)
{
cout << "Delete Node over Bound!" << endl;
return false;
}
int index = head;
for(int i = 1; i <= pos - 1; ++i)
{
index = elems[index].cur;
}
int node = elems[index].cur;
elems[index].cur = elems[node].cur;
deleteNode(node);
length--;
return true;
}
void SLinkList :: print()
{
int index = elems[head].cur;
while(index != 0)
{
cout << elems[index].data << " ";
index = elems[index].cur;
}
cout << endl;
return;
}
int SLinkList :: getLength()
{
return length;
}
bool SLinkList :: isEmpty()
{
if(length == 0)
{
return true;
}
else
{
return false;
}
}
int& SLinkList :: getElem(int pos)
{
int index = head;
for(int i = 1; i <= pos; ++i)
{
index = elems[index].cur;
}
return elems[index].data;
}
void SLinkList :: clear()
{
for(int i = 0; i < MAX_LIST_SIZE; ++i)
{
elems[i].data = i;
elems[i].cur = i + 1;
}
elems[MAX_LIST_SIZE - 1].cur = 0;
elems[0].cur = 0;
space = 1;
}
int main()
{
// Test the data to see if the insert and delete Spaces overflow
SLinkList myList;
for(int i = 1; i <= 105; ++i)
{
myList.insertElem(1,i);
}
//myList.print();
for(int i = 1; i <= 105; ++i)
{
myList.deleteElem(1);
}
//myList.print();
// Common test
for(int i = 1; i <= 10; ++i)
{
myList.insertElem(1,i);
}
myList.print();
cout << "Length= " << myList.getLength() <<endl;
myList.deleteElem(5);
myList.print();
cout << "Length= " << myList.getLength() <<endl;
cout << myList.isEmpty() << endl;
int &elem = myList.getElem(3);
elem = 99;
myList.print();
myList.clear();
myList.print();
return 0;
}
Thank you for reading, I hope to help you, thank you for your support of this site!