核心代码
多数组实现链表
#include<iostream>
#include<vector>
using namespace std;
class List{
public:
vector<int> next;
vector<int> key;
vector<int> prev;
int free=0;
int head=-1;
int len=0;
List(int size){
next=vector<int>(size);
key=vector<int>(size);
prev=vector<int>(size);
for(int i=0;i<size;i++)next[i]=i+1;
next[size-1]=-1;
}
int allocate(){
if(free == -1)return -1;
int obj = free;
free = next[free];
return obj;
}
void add(int index,int val){
if(free==-1)return;
len++;
int obj=allocate();
key[obj]=val;
if(head==-1){
head=obj;
prev[obj]=-1;
next[obj]=-1;
return;
}
int p = head;
while(index>0 && next[p]!=-1){p=next[p];index--;}
if(index > 0){
next[p]=obj;
prev[obj]=p;
next[obj]=-1;
}else{
if(p==head){
head=obj;
next[head]=p;
prev[p]=head;
}else{
next[obj]=p;
prev[obj]=prev[p];
next[prev[obj]]=obj;
prev[p]=obj;
}
}
return;
}
void update(int index,int val){
int p = head;
while(index>0){p=next[p];index--;}
key[p] = val;
}
void remove(int index){
len--;
int p=head;
while(index>0){p = next[p];index--;}
if(p==head){
if(next[p]!=-1)prev[next[p]]=-1;
head = next[p];
}else if(next[p]==-1){
next[prev[p]]=-1;
}else{
next[prev[p]]=next[p];
prev[next[p]]=prev[p];
}
free1(p);
}
void free1(int obj){
next[obj]=free;
free=obj;
}
int search(int index){
int p=head;
while(index > 0){p = next[p];index--;}
return key[p];
}
void print1(){
int p=head;
while(p!=-1){
cout<<key[p]<<" ";
p=next[p];
}
cout<<endl;
}
void sort1(){
int p=next[head];
next[head]=-1;
while(p!=-1){
int tmp=next[p];
int t=head;
while(next[t] != -1 && key[t] < key[p])t=next[t];
if(key[t]<key[p]){
next[t]=p;
prev[p]=t;
next[p]=-1;
}else if(t == head){
next[p]=t;
prev[t]=p;
head=p;
}else{
next[p] = t;
prev[p] = prev[t];
next[prev[p]] = p;
prev[t] = p;
}
p=tmp;
}
}
};
int n;
int main(){
cin>>n;
List list(n);
int type,index,val;
for(int i=0;i<n;i++){
cin>>type;
if(type==0){
cin>>index>>val;
list.add(index,val);
}
else if(type==1){
cin>>index;
list.remove(index);
}
else if(type==2){
cin>>index;
cout<<list.search(index)<<" "<< endl;
}
else if(type==3){
cin>>index>>val;
list.update(index,val);
}
else if(type == 4)list.sort1();
if(type!=2)list.print1();
}
return 0;
}
指针实现链表
#include<iostream>
using namespace std;
class Node{
//双向链表的节点
public:
int data;
Node * Next;Node * Prev;
};
class List{
//双向链表本身
public:
Node *Head;Node *Tail;
int length;
List(int length){
//创建
this->length=length;
Head=new Node();
Head->Prev=NULL;
Tail=Head;
for(int i=0;i<length;i++){
Node *tmp=new Node();
cin>>tmp->data;
tmp->Next=NULL;
tmp->Prev=Tail;
Tail->Next=tmp;
Tail=tmp;
}
}
~List(){ //析构函数，销毁时用
Node *q;
Node *p=Head->Next;
while(p!=NULL){
q=p;
p=p->Next;
delete q;
}
p=NULL;q=NULL;
}
void add(int val,int index){
Node *p=Head->Next;
if(index>length||index<=0)return;
for(int i=0;i<index-1;i++)p=p->Next;
Node * tmp=new Node();
tmp->data=val;
tmp->Next=p;
tmp->Prev=p->Prev;
p->Prev->Next=tmp;
p->Prev=tmp;
length++;
}
void update(int val,int index){
//修改
Node * p=Head->Next;
if(index>length||index<=0)return;
for(int i=0;i<index-1;i++)p=p->Next;
p->data=val;
}
void remove(int index){
//删除
Node * p=Head->Next;
if(index>length||index<=0)return;
for(int i=0;i<index-1;i++)p=p->Next;
p->Prev->Next=p->Next;
p->Next->Prev=p->Prev;
delete p;
length--;
}
int search(int index){
//查找
Node * p=Head->Next;
if(index>length||index<=0)return 0;
for(int i=0;i<index-1;i++)p=p->Next;
return p->data;
}
void sort1(){
//插入排序
if(Head->Next==NULL||Head->Next->Next==NULL)return;
Node * p2=Head->Next->Next;
Node * p1=Head;
Head->Next->Next=NULL;
while(p2){
Node * p3=p2->Next;
while(p1->Next){
if(p2->data<p1->Next->data){
p2->Next=p1->Next;
p2->Prev=p1;
p1->Next->Prev=p2;
p1->Next=p2;
break;
}
p1=p1->Next;
}
if(p1->Next==NULL){
p2->Next=NULL;
p2->Prev=p1;
p1->Next=p2;
}
p2=p3;
}
Node * pt=Head;
while(pt->Next)pt=pt->Next;
Tail=pt;
}
void print1(){
Node * p=Head->Next;
while(p!=NULL){
cout<<p->data<<" ";
p=p->Next;
}
cout<<endl;
}
/*
void sort2(){
//冒泡排序
Node * p=new Node();
Node * q=new Node();
int tmp;
for(p=Head->Next;p->Next!=NULL;p=p->Next)
{
for(q=p->Next;q!=NULL;q=q->Next)
{
if(q->data<p->data)
{
tmp=q->data;
q->data=p->data;
p->data=tmp;
}
}
}
}
*/
};
int n;
int main(){
cin>>n;
List list(n);
list.sort1();
list.print1();
return 0;
}
test1
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class MultiArrayObject {
private:
vector<int> data; // 存储元素的数组
vector<int> next; // 存储每个元素的下一个节点的索引
int head; // 链表头指针
public:
MultiArrayObject() {
head = -1;
}
// 在指定位置插入元素
void insert(int index, int val) {
if (index < 0 || index > data.size()) {
return;
}
data.insert(data.begin() + index, val);
next.insert(next.begin() + index, -1);
if (index == 0) {
next[index] = head;
head = index;
} else {
next[index - 1] = index;
next[index] = next[index - 1];
}
}
// 删除指定位置的元素
void remove(int index) {
if (index < 0 || index >= data.size()) {
return;
}
if (index == head) {
head = next[index];
} else {
int curr = head;
while (next[curr] != index) {
curr = next[curr];
}
next[curr] = next[index];
}
data.erase(data.begin() + index);
next.erase(next.begin() + index);
}
// 获取指定位置的元素
int get(int index) {
if (index < 0 || index >= data.size()) {
return -1;
}
return data[index];
}
// 修改指定位置的元素
void set(int index, int val) {
if (index < 0 || index >= data.size()) {
return;
}
data[index] = val;
}
// 对链表进行选择排序
void selectionSort() {
int i, j, min_idx;
for (i = 0; i < data.size() - 1; i++) {
min_idx = i;
for (j = i + 1; j < data.size(); j++) {
if (data[j] < data[min_idx]) {
min_idx = j;
}
}
if (min_idx != i) {
int temp = data[i];
data[i] = data[min_idx];
data[min_idx] = temp;
int next_temp = next[i];
next[i] = next[min_idx];
next[min_idx] = next_temp;
}
}
}
};
int main() {
int N, op, pos, val;
cin >> N;
MultiArrayObject obj;
for (int i = 0; i < N; i++) {
cin >> op;
switch (op) {
case 0: // 增加（插入）
cin >> pos >> val;
obj.insert(pos, val);
for(int j=0;i<obj.data.size();i++)cout<<obj[j]<<" ";
break;
case 1: // 删除
cin >> pos;
obj.remove(pos);
for(int j=0;i<obj.data.size();i++)cout<<obj[j]<<" ";
break;
case 2: // 查找
cin >> pos;
cout << obj.get(pos) << endl;
for(int j=0;i<obj.data.size();i++)cout<<obj[j]<<" ";
break;
case 3: // 修改
cin >> pos >> val;
obj.set(pos, val);
for(int j=0;i<obj.data.size();i++)cout<<obj[j]<<" ";
break;
case 4: // 排序
obj.selectionSort();
for(int j=0;i<obj.data.size();i++)cout<<obj[j]<<" ";
break;
}
}
}
test2.py
class MultiArrayObject:
def __init__(self):
self.data = [] # 存储元素的数组
self.next = [] # 存储每个元素的下一个节点的索引
self.head = -1 # 链表头指针
# 在指定位置插入元素
def insert(self, index, val):
if index < 0 or index > len(self.data):
return
self.data.insert(index, val)
self.next.insert(index, -1)
if index == 0:
self.next[index] = self.head
self.head = index
else:
self.next[index - 1] = index
self.next[index] = self.next[index - 1]
# 删除指定位置的元素
def remove(self, index):
if index < 0 or index >= len(self.data):
return
if index == self.head:
self.head = self.next[index]
else:
curr = self.head
while self.next[curr] != index:
curr = self.next[curr]
self.next[curr] = self.next[index]
self.data.pop(index)
self.next.pop(index)
# 获取指定位置的元素
def get(self, index):
if index < 0 or index >= len(self.data):
return -1
return self.data[index]
# 修改指定位置的元素
def set(self, index, val):
if index < 0 or index >= len(self.data):
return
self.data[index] = val
# 对链表进行选择排序
def selection_sort(self):
for i in range(len(self.data) - 1):
min_idx = i
for j in range(i + 1, len(self.data)):
if self.data[j] < self.data[min_idx]:
min_idx = j
if min_idx != i:
self.data[i], self.data[min_idx] = self.data[min_idx], self.data[i]
self.next[i], self.next[min_idx] = self.next[min_idx], self.next[i]
# 主程序
N = int(input())
obj = MultiArrayObject()
for i in range(N):
op = list(map(int, input().split()))
if op[0] == 0:
pos, val = op[1], op[2]
obj.insert(pos, val)
for j in range(len(obj.data)):
print(obj.data[j],end=" ")
elif op[0] == 1:
pos = op[1]
obj.remove(pos)
for j in range(len(obj.data)):
print(obj.data[j],end=" ")
elif op[0] == 2:
pos = op[1]
print(obj.get(pos))
for j in range(len(obj.data)):
print(obj.data[j],end=" ")
elif op[0] == 3:
pos, val = op[1], op[2]
obj.set(pos, val)
for j in range(len(obj.data)):
print(obj.data[j],end=" ")
elif op[0] == 4:
obj.selection_sort()
for j in range(len(obj.data)):
print(obj.data[j],end=" ")
test3
#include<iostream>
#include<vector>
using namespace std;
class List{
public:
vector<int> next;
vector<int> key;
vector<int> pre;
int free = 0;
int head = -1;
int length = 0;
List(int size){
next = vector<int>(size);
key = vector<int>(size);
pre = vector<int>(size);
for(int i=0;i<size-1;i++)
next[i] = i + 1;
next[size - 1] = -1;
}
bool add(int index,int val){
if(free == -1)
return false;
length++;
int obj = allocate_object();
key[obj] = val;
if(head == -1){
head = obj;
pre[obj] = -1;
next[obj] = -1;
return true;
}
int p = head;
while(index > 0 && next[p] != -1){
p = next[p];
index--;
}
if(index > 0){
next[p] = obj;
pre[obj] = p;
next[obj] = -1;
}
else{
if(p == head){
head = obj;
next[head] = p;
pre[p] = head;
}
else{
next[obj] = p;
pre[obj] = pre[p];
next[pre[obj]] = obj;
pre[p] = obj;
}
}
return true;
}
void update(int index,int val){
int p = head;
while(index > 0){
p = next[p];
index--;
}
key[p] = val;
}
void remove(int index){
length--;
int p = head;
while(index > 0){
index--;
p = next[p];
}
if(p == head){
if(next[p] != -1)
pre[next[p]] = -1;
head = next[p];
}
else if(next[p] == -1){
next[pre[p]] = -1;
}
else{
next[pre[p]] = next[p];
pre[next[p]] = pre[p];
}
free_obj(p);
}
int search(int index){
int p = head;
while(index > 0){
p = next[p];
index--;
}
return key[p];
}
void println(){
int p = head;
while(p != -1){
cout << key[p] << ' ';
p = next[p];
}
cout << endl;
}
void sortList(){
int p = next[head];
next[head] = -1;
while(p != -1){
int s = next[p];
int t = head;
while(next[t] != -1 && key[t] < key[p])
t = next[t];
if(key[t] < key[p]){
next[t] = p;
pre[p] = t;
next[p] = -1;
}
else if(t == head){
head = p;
next[p] = t;
pre[t] = p;
}
else{
next[p] = t;
pre[p] = pre[t];
next[pre[p]] = p;
pre[t] = p;
}
p = s;
}
}
private:
int allocate_object(){
if(free == -1)
return -1;
int obj = free;
free = next[free];
return obj;
}
int free_obj(int obj){
next[obj] = free;
free = obj;
}
};
int main(){
int n;
cin >> n;
List list(n);
int type,index,val;
for(int i=0;i<n;i++){
cin >> type;
if(type == 0){
cin >> index;
cin >> val;
list.add(index,val);
}
else if(type == 1){
cin >> index;
list.remove(index);
}
else if(type == 2){
cin >> index;
cout << list.search(index) << endl;
}
else if(type == 3){
cin >> index;
cin >> val;
list.update(index,val);
}
else
list.sortList();
if(type != 2)list.println();
}
return 0;
}
test4
#include<iostream>
#include<vector>
#include <fstream>
using namespace std;
ofstream fout("test10.out");
class List{
public:
vector<int> next;
vector<int> key;
vector<int> pre;
int free = 0;
int head = -1;
int length = 0;
List(int size){
next = vector<int>(size);
key = vector<int>(size);
pre = vector<int>(size);
for(int i=0;i<size-1;i++)next[i] = i + 1;
next[size - 1] = -1;
}
bool add(int index,int val){
if(free == -1)return false;
length++;
int obj = allocate_object();
key[obj] = val;
if(head == -1){
head = obj;
pre[obj] = -1;
next[obj] = -1;
return true;
}
int p = head;
while(index > 0 && next[p] != -1){
p = next[p];
index--;
}
if(index > 0){
next[p] = obj;
pre[obj] = p;
next[obj] = -1;
}
else{
if(p == head){
head = obj;
next[head] = p;
pre[p] = head;
}
else{
next[obj] = p;
pre[obj] = pre[p];
next[pre[obj]] = obj;
pre[p] = obj;
}
}
return true;
}
void update(int index,int val){
int p = head;
while(index > 0){
p = next[p];
index--;
}
key[p] = val;
}
void remove(int index){
length--;
int p = head;
while(index > 0){
index--;
p = next[p];
}
if(p == head){
if(next[p] != -1)
pre[next[p]] = -1;
head = next[p];
}
else if(next[p] == -1){
next[pre[p]] = -1;
}
else{
next[pre[p]] = next[p];
pre[next[p]] = pre[p];
}
free_obj(p);
}
int search(int index){
int p = head;
while(index > 0){
p = next[p];
index--;
}
return key[p];
}
void println(){
int p = head;
while(p != -1){
fout << key[p] << ' ';
p = next[p];
}
fout << endl;
}
void sortList(){
int p = next[head];
next[head] = -1;
while(p != -1){
int s = next[p];
int t = head;
while(next[t] != -1 && key[t] < key[p])
t = next[t];
if(key[t] < key[p]){
next[t] = p;
pre[p] = t;
next[p] = -1;
}
else if(t == head){
head = p;
next[p] = t;
pre[t] = p;
}
else{
next[p] = t;
pre[p] = pre[t];
next[pre[p]] = p;
pre[t] = p;
}
p = s;
}
}
int allocate_object(){
if(free == -1)return -1;
int obj = free;
free = next[free];
return obj;
}
void free_obj(int obj){
next[obj] = free;
free = obj;
}
};
int main(){
ifstream fin("10.in");
int n;
fin >> n;
List list(n);
int type,index,val;
for(int i=0;i<n;i++){
fin >> type;
if(type == 0){
fin >> index;
fin >> val;
list.add(index,val);
}
else if(type == 1){
fin >> index;
list.remove(index);
}
else if(type == 2){
fin >> index;
fout << list.search(index) <<" "<< endl;
}
else if(type == 3){
fin >> index;
fin >> val;
list.update(index,val);
}
else if(type == 4){
list.sortList();
}
if(type != 2)list.println();
}
fin.close();
fout.close();
return 0;
}
test5
#include<iostream>
#define NOEXIST 0x7fffffff
using namespace std;
template <typename T> class list;
template <typename T> ostream& operator<<(ostream&, const list<T> &);
template <typename T>
class list{
private:
size_t *next;
T *key;
size_t *prev;
size_t free;//管理自由节点链表，单链表即可
size_t head;//管理已用结点链表，双链表
size_t list_size;//链表总大小，包括自由链表
friend ostream& operator<< <T>(ostream&, const list &);
size_t getFree();//获得自由节点
void addFree(size_t index)
{//添加空闲空间到自由链表
next[index] = free;
free = index;
}
void newList(size_t n)
{//分配空间
key = new T[n];
next = new size_t[n];
prev = new size_t[n];
}
void deleteList(size_t *p, T *k, size_t *n)
{//收回空间
delete[] p;
delete[] k;
delete[] n;
}
void copyList(size_t *p, T *k, size_t *n, size_t s)
{//复制链表
copy(p, p + s, prev);
copy(n, n + s, next);
copy(k, k + s, key);
}
void setFree(size_t start_index)
{//设置自由链表
next[list_size - 1] = NOEXIST;
for (size_t i = start_index; i != list_size - 1; ++i)
next[i] = i + 1;
free = start_index;
}
public:
list() :free(NOEXIST), head(NOEXIST), list_size(8)//-1表示空，最初链表有8个空间
{//初始化，设置free链表
newList(list_size);
setFree(0);
}
list(T *beg, T *end) :list() { insert(beg, end); }
void setData(size_t index, const T &t) { key[index] = t; }
T getData(size_t index)const { return key[index]; }
void insert(const T&);
void insert(T*, T*);
size_t locate(const T&);
void erase(const T&);
void erase(size_t);
void edit(const T&, const T&);
bool empty() { return head == NOEXIST; }//链表是否为空
~list()
{
deleteList(prev, key, next);
}
//bool full() { return free == -1; }
};
template <typename T>
inline size_t list<T>::getFree()
{
if (free == NOEXIST)
{//若自由链表已空，则需补充空间
size_t *old_next = next, *old_prev = prev;
T *old_key = key;
size_t old_list_size = list_size;
list_size *= 2;
newList(list_size);
copyList(old_prev, old_key, old_next, old_list_size);
deleteList(old_prev,old_key,old_next);
setFree(old_list_size);
}
size_t index = free;
free = next[index];
return index;
}
template <typename T>
void list<T>::insert(const T &t)
{
size_t index = getFree();
key[index] = t;
if (head == NOEXIST)
{//插入的是第一个节点
next[index] = NOEXIST;
prev[index] = NOEXIST;
head = index;
}
else
{//否则
next[index] = head;
prev[head] = index;
prev[index] = NOEXIST;
head = index;
}
}
template <typename T>
void list<T>::insert(T *beg, T *end)
{
for (; beg != end; ++beg)
insert(*beg);
}
template <typename T>
size_t list<T>::locate(const T &t)
{
size_t p = head;
while (p != NOEXIST && key[p] != t)
p = next[p];
return p;
}
template <typename T>
void list<T>::erase(size_t index)
{
if (index == head)//删除的是头结点
head = next[index];
else
{
next[prev[index]] = next[index];
if (next[index] != NOEXIST)//若删除的不是最后一个节点
prev[next[index]] = prev[index];
}
addFree(index);
}
template <typename T>
void list<T>::erase(const T &t)
{
size_t index = locate(t);
if (index != NOEXIST)
erase(index);
}
template <typename T>
void list<T>::edit(const T &old_key, const T &new_key)
{
size_t index = locate(old_key);
if (index == NOEXIST)
{
cout << old_key << " isn't exist!" << endl;
return;
}
key[index] = new_key;
}
template <typename T>
ostream& operator<<(ostream &out, const list<T> &lst)
{
size_t p = lst.head;
while (p != NOEXIST)
{
out << lst.key[p];
if (lst.next[p] != NOEXIST) out << ' ';
p = lst.next[p];
}
return out;
}
int main(){
int a[] = { 1, 2, 3, 4, 5, 6 };
list<int> lst(a,a + 6);
cout << lst << endl << endl;
for (int i = 10; i != 20; ++i)
lst.insert(i);
cout << lst << endl << endl;
for (int i = 1; i != 1000; ++i)
{
size_t f = lst.locate(i);
if (f != NOEXIST)
lst.insert(-i);
}
cout << lst << endl;
getchar();
return 0;
}
others
#include<iostream>
using namespace std;
class Node{
//双向链表的节点
public:
int data;
Node * Next;Node * Prev;
};
class List{
//双向链表本身
public:
Node *Head;Node *Tail;
int length;
List(int length){
//创建
this->length=length;
Head=new Node();
Head->Prev=NULL;
Tail=Head;
for(int i=0;i<length;i++){
Node *tmp=new Node();
cin>>tmp->data;
tmp->Next=NULL;
tmp->Prev=Tail;
Tail->Next=tmp;
Tail=tmp;
}
}
~List(){ //析构函数，销毁时用
Node *q;
Node *p=Head->Next;
while(p!=NULL){
q=p;
p=p->Next;
delete q;
}
p=NULL;q=NULL;
}
void add(int val,int index){
Node *p=Head->Next;
if(index>length||index<=0)return;
for(int i=0;i<index-1;i++)p=p->Next;
Node * tmp=new Node();
tmp->data=val;
tmp->Next=p;
tmp->Prev=p->Prev;
p->Prev->Next=tmp;
p->Prev=tmp;
length++;
}
void update(int val,int index){
//修改
Node * p=Head->Next;
if(index>length||index<=0)return;
for(int i=0;i<index-1;i++)p=p->Next;
p->data=val;
}
void remove(int index){
//删除
Node * p=Head->Next;
if(index>length||index<=0)return;
for(int i=0;i<index-1;i++)p=p->Next;
p->Prev->Next=p->Next;
p->Next->Prev=p->Prev;
delete p;
length--;
}
int search(int index){
//查找
Node * p=Head->Next;
if(index>length||index<=0)return 0;
for(int i=0;i<index-1;i++)p=p->Next;
return p->data;
}
void sort1(){
//插入排序
if(Head->Next==NULL||Head->Next->Next==NULL)return;
Node * p2=Head->Next->Next;
Node * p1=Head;
Head->Next->Next=NULL;
while(p2){
Node * p3=p2->Next;
while(p1->Next){
if(p2->data<p1->Next->data){
p2->Next=p1->Next;
p2->Prev=p1;
p1->Next->Prev=p2;
p1->Next=p2;
break;
}
p1=p1->Next;
}
if(p1->Next==NULL){
p2->Next=NULL;
p2->Prev=p1;
p1->Next=p2;
}
p2=p3;
}
Node * pt=Head;
while(pt->Next)pt=pt->Next;
Tail=pt;
}
void print1(){
Node * p=Head->Next;
while(p!=NULL){
cout<<p->data<<" ";
p=p->Next;
}
cout<<endl;
}
/*
void sort2(){
//冒泡排序
Node * p=new Node();
Node * q=new Node();
int tmp;
for(p=Head->Next;p->Next!=NULL;p=p->Next)
{
for(q=p->Next;q!=NULL;q=q->Next)
{
if(q->data<p->data)
{
tmp=q->data;
q->data=p->data;
p->data=tmp;
}
}
}
}
*/
};
int n;
int main(){
cin>>n;
List list(n);
list.sort1();
list.print1();
return 0;
}
#include<iostream>
#include<vector>
using namespace std;
class List{
public:
List(int size){
next = vector<int>(size);
key = vector<int>(size);
pre = vector<int>(size);
for(int i=0;i<size-1;i++)
next[i] = i + 1;
next[size - 1] = -1;
}
bool add(int index,int val){
if(free == -1)
return false;
length++;
int obj = allocate_object();
key[obj] = val;
if(head == -1){
head = obj;
pre[obj] = -1;
next[obj] = -1;
return true;
}
int p = head;
while(index > 0 && next[p] != -1){
p = next[p];
index--;
}
if(index > 0){
next[p] = obj;
pre[obj] = p;
next[obj] = -1;
}
else{
if(p == head){
head = obj;
next[head] = p;
pre[p] = head;
}
else{
next[obj] = p;
pre[obj] = pre[p];
next[pre[obj]] = obj;
pre[p] = obj;
}
}
return true;
}
void update(int index,int val){
int p = head;
while(index > 0){
p = next[p];
index--;
}
key[p] = val;
}
void remove(int index){
int p = head;
while(index > 0){
index--;
p = next[p];
}
if(p == head){
if(next[p] != -1)
pre[next[p]] = -1;
head = next[p];
}
else if(next[p] == -1){
next[pre[p]] = -1;
}
else{
next[pre[p]] = next[p];
pre[next[p]] = pre[p];
}
free_obj(p);
length--;
}
int search(int index){
int p = head;
while(index > 0){
p = next[p];
index--;
}
return key[p];
}
void println(){
int p = head;
while(p != -1){
std::cout << key[p] << ' ';
p = next[p];
}
cout << endl;
}
void sortList(){
int p = next[head];
next[head] = -1;
while(p != -1){
int s = next[p];
int t = head;
while(next[t] != -1 && key[t] < key[p])
t = next[t];
if(key[t] < key[p]){
next[t] = p;
pre[p] = t;
next[p] = -1;
}
else if(t == head){
head = p;
next[p] = t;
pre[t] = p;
}
else{
next[p] = t;
pre[p] = pre[t];
next[pre[p]] = p;
pre[t] = p;
}
p = s;
}
}
int getLength(){
return length;
}
private:
vector<int> next;
vector<int> key;
vector<int> pre;
int free = 0;
int head = -1;
int length = 0;
int allocate_object(){
if(free == -1)
return -1;
int obj = free;
free = next[free];
return obj;
}
int free_obj(int obj){
next[obj] = free;
free = obj;
}
};
class LinkedList {
public:
struct Node{
int val;
Node * next;
Node(int val ):val(val), next(nullptr){};
Node(int val , Node* next):val(val), next(next){}
};
LinkedList() {
//虚拟节点方便计算
_dummyHead = new Node(0);
_maxindex = -1;
}
int get(int index) {
if(index < 0 || index >_maxindex)
return -1;
Node * cur = _dummyHead;
for(int i = 0; i <= index; i++){
cur = cur->next;
}
return cur->val;
}
void printList(){
auto p = _dummyHead->next;
while(p){
cout << p->val << ' ';
p = p->next;
}
cout << endl;
}
void addAtHead(int val) {
Node * newNode = new Node(val, _dummyHead->next);
_dummyHead->next = newNode;
_maxindex++;
}
void addAtTail(int val) {
Node * cur = _dummyHead;
while(cur->next != nullptr){
cur = cur->next;
}
Node * newNode = new Node(val);
cur->next = newNode;
_maxindex++;
}
void addAtIndex(int index, int val) {
if(index == _maxindex +1 )
addAtTail(val);
else if(index > _maxindex+1)
return ;
else{
Node * cur = _dummyHead;
for(int i = 0 ; i < index; i++){
cur = cur->next;
}
Node * newNode = new Node(val);
newNode->next = cur->next;
cur->next = newNode;
_maxindex++;
}
}
void deleteAtIndex(int index) {
if(index < 0 || index > _maxindex)
return ;
Node * cur = _dummyHead;
for(int i = 0 ; i < index; i++){
cur = cur->next;
}
Node * p = cur->next;
cur->next = p->next;
delete p;
_maxindex--;
}
void sortList()
{
Node* head = _dummyHead->next;
if (head == NULL || head->next == NULL)
{
return;
}
Node* left = head;//记录已排序序列的最后一个节点
Node* cur = head->next;//记录待排序列的第一个节点
Node* pre = NULL;
while (cur)
{
if (cur->val >= left->val)
{
left = left->next;
}
else
{
pre = _dummyHead;
while (pre->next->val < cur->val)
{
pre = pre->next;
}
left->next = cur->next;
cur->next = pre->next;
pre->next = cur;
}
cur = left->next;
}
}
int getLength(){
return _maxindex + 1;
}
private:
int _maxindex;
Node * _dummyHead;
};
vector<int> create(int N,int low,int high){
vector<int> arr(N);
for(int i=0;i<N;i++)
arr[i] = rand() % (high - low + 1) + low;
return arr;
}
int main(){
int N = 100000;
int low = 0,high = 100000;
vector<int> arr = create(N,low,high);
List list1(N);
LinkedList list2;
long time1,time2;
/*time1 = clock();
for(int i=0;i<arr.size();i++)
list1.add(0,arr[i]);
time2 = clock();
cout << "多重数组链表使用头插法建立链表用时：\t" << ((double)time2 - time1) / CLOCKS_PER_SEC << endl;
time1 = clock();
for(int i=0;i<arr.size();i++)
list2.addAtHead(arr[i]);
time2 = clock();
cout << "指针链表使用头插法建立链表用时：\t" << ((double)time2 - time1) / CLOCKS_PER_SEC << endl;
cout << "------------------------------------------------" << endl;
time1 = clock();
for(int i=0;i<arr.size();i++){
list1.add(list1.getLength(),arr[i]);
}
time2 = clock();
cout << "多重数组链表使用尾插法建立链表用时：\t" << ((double)time2 - time1) / CLOCKS_PER_SEC << endl;
time1 = clock();
for(int i=0;i<arr.size();i++){
list2.addAtTail(arr[i]);
}
time2 = clock();
cout << "指针链表使用尾插法建立链表用时：\t" << ((double)time2 - time1) / CLOCKS_PER_SEC << endl;
cout << "-------------------------------------------------" << endl;
for(int i=0;i<arr.size();i++)
list1.add(0,arr[i]);
for(int i=0;i<arr.size();i++)
list2.addAtHead(arr[i]);
time1 = clock();
for(int i=0;i<arr.size();i++){
list1.remove(0);
}
time2 = clock();
cout << "多重数组链表删除链表用时：\t" << ((double)time2 - time1) / CLOCKS_PER_SEC << endl;
time1 = clock();
for(int i=0;i<arr.size();i++){
list2.deleteAtIndex(0);
}
time2 = clock();
cout << "指针链表删除链表用时：\t" << ((double)time2 - time1) / CLOCKS_PER_SEC << endl;*/
std::cout << "-------------------------------------------------" << endl;
for(int i=0;i<arr.size();i++)
list1.add(0,arr[i]);
for(int i=0;i<arr.size();i++)
list2.addAtHead(arr[i]);
time1 = clock();
list1.sortList();
time2 = clock();
std::cout << "多重数组链表排序用时：\t" << ((double)time2 - time1) / CLOCKS_PER_SEC << endl;
time1 = clock();
list2.sortList();
time2 = clock();
std::cout << "指针链表排序用时：\t" << ((double)time2 - time1) / CLOCKS_PER_SEC << endl;
}