数据结构（一） 链表

``````#pragma once
#include <iostream>
#include <stdio.h>
#include <time.h>
#include <vector>
#include <algorithm>
#include <string>
#include <math.h>
#include <stack>
using namespace std;

class listNode
{
public:
int data;
listNode* next;
listNode(int element) :data(element), next(nullptr) {};
};

class SingleList
{
public:
SingleList();
~SingleList();
listNode* insert(int data, int index);
void del(int index);
private:
listNode* root;
listNode* currentNode;
int size;
};

//单链表反转
listNode* reverse(listNode* root);
//求链表交点
class CircularList
{
public:
CircularList();
~CircularList();
void Init(listNode* root);
listNode* insert(listNode* root, int data, int index);
//listNode* insert(int data, int index);
void del(listNode* &root, int index);
private:
listNode* root;
listNode* m_pCurrentNode;
listNode* rootCopy;
int size;
};

class _NODE
{
public:
int data;
_NODE* prev;
_NODE* next;
_NODE(int input): data(input), prev(nullptr), next(nullptr){};
};
//双向链表
typedef _NODE node;
class DoubleList
{
public:
DoubleList();
~DoubleList();
void insert(int data, int index);
void del(int index);
private:
node* root;
node* m_pCurrentNode;
node* rootCopy;
int size;
};``````

cpp代码如下：

``````#include "DS_list.h"/

SingleList::SingleList()
{
size = 0;
root = new listNode(0);
currentNode = root;
}

SingleList::~SingleList()
{
listNode* temp = root;
while (temp!=nullptr)
{
listNode* p = temp->next;
delete temp;
temp = p;
}
root = nullptr;
}

listNode*  SingleList::insert(int data, int index)
{
listNode* temp = new listNode(data);

//插在首节点
if (index==0)
{
temp->next = root->next;
root->next = temp;
}

//插在尾节点后,
else if (index == size)
{
currentNode = root->next;
while (currentNode->next != nullptr)
{
currentNode = currentNode->next;
}
currentNode->next = temp;

}
//插在中间
else
{
currentNode = root->next;
listNode* prev = nullptr;
int count = -1;
while (currentNode != nullptr)
{
++count;
if (count == index)
{
break;
}
prev = currentNode;
currentNode = currentNode->next;
}
prev->next = temp;
temp->next = currentNode;
}
++size;

return root;
}

void SingleList::del(int index)
{
if (size == 0 || index>= size)
{
return;
}

if (index == 0)
{
root->next = root->next->next;
}
else if (index == size - 1)
{
listNode* currentNode = root->next;
listNode* prev = nullptr;
while (currentNode->next!=nullptr)
{
prev = currentNode;
currentNode = currentNode->next;
}
prev->next = nullptr;
}
else
{
listNode* currentNode = root->next;
listNode* prev = nullptr;
int count = -1;
while (currentNode != nullptr)
{
++count;
if (count==index)
{
break;
}
prev = currentNode;
currentNode = currentNode->next;
}
prev->next = currentNode->next;
}
--size;

}

listNode* reverse(listNode* root)
{
if (root == nullptr)
{
return nullptr;
}

listNode* p = root->next;
listNode* q = p->next;
listNode* r = nullptr;

while (q != nullptr)
{
p->next = r;
r = p;
p = q;
q = q->next;
}
q = r;
r = p;
r->next = q;
//root->next = r;
return r;
}

CircularList::CircularList()
{
size = 0;
//root = new listNode('#');
}

CircularList::~CircularList()
{
listNode* temp = rootCopy;
while (temp->next != rootCopy)
{
listNode* p = temp->next;
delete temp;
temp = p;
}
delete temp;
temp = nullptr;
}

void CircularList::Init(listNode* root)
{
m_pCurrentNode = root;
root->next = m_pCurrentNode;
rootCopy = root;
}

{
listNode* temp = new listNode(data);

while (m_pCurrentNode->next != root)
{
m_pCurrentNode = m_pCurrentNode->next;
}

m_pCurrentNode->next = temp;
m_pCurrentNode = temp;
m_pCurrentNode->next = root;
++size;
}

listNode* CircularList::insert(listNode* root, int data, int index)
{
listNode* temp = new listNode(data);
//temp->next = root;

if (index == 0)
{
temp->next = root;
listNode* currentNode = root;
while (currentNode->next != root)
{
currentNode = currentNode->next;
}
currentNode->next = temp;
////尝试把无数据域的头节点拿掉
root = temp;
}
else
{
listNode* currentNode = root;
listNode* prev = nullptr;
int count = -1;
while (currentNode->next != root)
{
//当头节点数据域是无效数据时，类内建立头节点从而建立环形链表是十分困难的，
++count;

if (count == index)
{
break;
}

prev = currentNode;
currentNode = currentNode->next;
}
prev->next = temp;
temp->next = currentNode;
}
++size;
return root;
}

void CircularList::del(listNode* &root, int index)
{
if (size == 0)
{
return;
}

//删除头节点
if (index == 0)
{
listNode* currentNode = root;
while (currentNode->next!=root)
{
currentNode = currentNode->next;
}

root = root->next;
currentNode->next = root;
}
else
{
listNode* currentNode = root;
listNode* prev=nullptr;
int count = -1;
while (currentNode->next != root)
{
/*if (currentNode->data=='#')
{
prev = currentNode;
currentNode = currentNode->next;
continue;
}*/

++count;
if (count == index)
{
break;
}
prev = currentNode;
currentNode = currentNode->next;
}
prev->next = currentNode->next;
}
}

DoubleList::DoubleList()
{
size = 0;
}

DoubleList::~DoubleList()
{

}

{
root = new node(data);
size = 1;
}

void DoubleList::insert(int data, int index)
{
node* temp = new node(data);

if (index == 0)
{
root->prev = temp;
temp->next = root;
root = temp;
}
else if (index == size)
{
node* currentNode = root;
while (currentNode->next != nullptr)
{
currentNode = currentNode->next;
}
currentNode->next = temp;
temp->prev = currentNode;
}
else
{
node* currentNode = root;
int count = -1;
while (currentNode->next != nullptr)
{
++count;

if (count == index)
{
break;
}

currentNode = currentNode->next;
}
currentNode->prev->next = temp;
temp->prev = currentNode->prev;
temp->next = currentNode;
currentNode->prev = temp;
}
++size;
}

void DoubleList::del(int index)
{
if (index == 0)
{
node* temp = root;
node* currentNode = root->next;
delete temp;
temp = nullptr;
currentNode->prev = nullptr;

root = currentNode;
}
else if (index == size - 1 )
{
node* currentNode = root;
while (currentNode->next != nullptr)
{
currentNode = currentNode->next;
}
currentNode->prev->next = nullptr;
delete currentNode;
}
else
{
node* currentNode = root;
int count = -1;

while (currentNode->next != nullptr)
{
++count;

if (count==index)
{
break;
}

currentNode = currentNode->next;
}

currentNode->prev->next = currentNode->next;
currentNode->next->prev = currentNode->prev;
delete currentNode;
currentNode = nullptr;
}
--size;
}
//
{
int nListA = 0, nListB = 0;

while (currentNodeA != nullptr)
{
++nListA;
currentNodeA = currentNodeA->next;
}

while (currentNodeB != nullptr)
{
++nListB;
currentNodeB = currentNodeB->next;
}

if (nListA > nListB)
{
int t = 0;
while (currentNodeA!=nullptr)
{
currentNodeA = currentNodeA->next;
++t;
if (t == nListA - nListB)
{
break;
}
}

while (currentNodeA != nullptr)
{
if (currentNodeA == currentNodeB)
{
return currentNodeA;
}
currentNodeA = currentNodeA->next;
currentNodeB = currentNodeB->next;
}

return nullptr;

}
else if (nListA< nListB)
{
int t = 0;
while (currentNodeB != nullptr)
{
currentNodeB = currentNodeB->next;
++t;
if (t == nListB - nListA)
{
break;
}
}

while (currentNodeA != nullptr)
{
if (currentNodeA == currentNodeB)
{
return currentNodeA;
}
currentNodeA = currentNodeA->next;
currentNodeB = currentNodeB->next;
}

return nullptr;
}
else
{
while (currentNodeA != nullptr)
{
if (currentNodeA == currentNodeB)
{
return currentNodeA;
}
currentNodeA = currentNodeA->next;
currentNodeB = currentNodeB->next;
}
return nullptr;
}

}

//合并两个有序链表
{
{
return nullptr;
}

{
}

{
}

listNode* root = new listNode('#');
listNode* p = root;
while (currentA != nullptr)
{
if (currentA != nullptr && currentB != nullptr)
{
if (currentA->data > currentB->data)
{
p->next = currentB;
currentB = currentB->next;
}
else
{
p->next = currentA;
currentA = currentA->next;
}
p = p->next;
}

if (currentB == nullptr &&currentA != nullptr)
{
p->next = currentA;
break;
}

}

if (currentA == nullptr &&currentB!=nullptr)
{
p->next = currentB;
}

return root->next;
}

``````

main.cpp

``````	SingleList singleList;
singleList.insert(1, 0);
singleList.insert(2, 1);
singleList.insert(3, 2);
singleList.insert(4, 1);
listNode* r = singleList.insert(5, 0);

CircularList circularList;
listNode* root = new listNode(1);
circularList.Init(root);

root = circularList.insert(root, 5, 1);
root = circularList.insert(root, 6, 0);

circularList.del(root, 0);
circularList.del(root, 1);

DoubleList doubleList;
doubleList.insert(2, 0);
doubleList.insert(3, 2);
doubleList.insert(10, 1);
doubleList.insert(11, 1);

doubleList.del(0);
doubleList.del(2);
doubleList.del(1);

``````

;