为了解决一个单片机项目的需求，解决频繁地跳转到某地址执行指令的问题，需要使用并维护一个序列
刚开始实在想不出办法，查了很多资料，也都用不上，后来知道链表结构的存在才解决了这个问题，花了一天半的时间从无到有接触单链表，记录一下基本操作集合，其中大部分都可以用来解决我单片机项目的问题
操作集
class LNode {
public:
int data;
LNode *next;
public:
explicit LNode(int x = -1) {
this->data = x;
this->next = nullptr;
}
~LNode() {
this->next = nullptr;
}
void DestroyList();
void Traverse();
void Delete_X(ElemType X);
LNode *Reverse();
void Delete_Min();
void SortLinkedList();
void Delete_S_2_E(ElemType Start, ElemType End);
void FindFirstCommonNode(LNode *L);
void SortLinkedList_NoTmpSpace();
void Divide_Odd_Even();
void MakeElemsUnique();
void Merge2LinkList_Dec(LNode *L2);
void Merge2LinkList_Inc(LNode *L2);
void Get2LinkListsIntersection(LNode *L2);
bool IsSuccessiveSeq(LNode *B);
bool FindReverseKthElem(unsigned int K);
void MakeElemsUniqueAbs(unsigned int dataRange);
private:
static unsigned int Partition(ElemType A[], unsigned int low, unsigned int high);
static void QuickSort(ElemType A[], unsigned int low, unsigned int high);
unsigned int GetLength();
LNode *FindMin();
};
源代码
#include <iostream>
#include <algorithm>
#define abs(a) (a >= 0) ? a : (0 - a)
using namespace std;
typedef int ElemType;
class LNode {
public:
int data;
LNode *next;
public:
explicit LNode(int x = -1) {
this->data = x;
this->next = nullptr;
}
~LNode() {
this->next = nullptr;
}
void DestroyList();
void Traverse();
void Delete_X(ElemType X);
LNode *Reverse();
void Delete_Min();
void SortLinkedList();
void Delete_S_2_E(ElemType Start, ElemType End);
void FindFirstCommonNode(LNode *L);
void SortLinkedList_NoTmpSpace();
void Divide_Odd_Even();
void MakeElemsUnique();
void Merge2LinkList_Dec(LNode *L2);
void Merge2LinkList_Inc(LNode *L2);
void Get2LinkListsIntersection(LNode *L2);
bool IsSuccessiveSeq(LNode *B);
bool FindReverseKthElem(unsigned int K);
void MakeElemsUniqueAbs(unsigned int dataRange);
private:
static unsigned int Partition(ElemType A[], unsigned int low, unsigned int high);
static void QuickSort(ElemType A[], unsigned int low, unsigned int high);
unsigned int GetLength();
LNode *FindMin();
};
void Create(LNode *&L) {
ElemType num;
cin >> num;
auto p = L;
while (num != -1) {
auto ins = new LNode(num);
p->next = ins;
p = p->next;
cin >> num;
}
}
void LNode::DestroyList() {
auto p = this->next;
while (p) {
auto del = p;
p = p->next;
delete del;
}
}
LNode *LNode::Reverse() {
if (!this->next) {
return this;
}
auto res = this->next->Reverse();
this->next->next = this;
this->next = nullptr;
return res;
}
void LNode::Traverse() {
auto p = this->next;
if (!p) {
cout << "List is null" << endl;
return;;
}
while (p) {
printf(" %d", p->data);
p = p->next;
}
printf("\n");
}
void LNode::Delete_X(ElemType X) {
LNode *p = this;
while (p) {
if (p->next->data == X) {
auto del = p->next;
p->next = del->next;
delete del;
//del = nullptr;
}
p = p->next;
}
}
void LNode::Delete_Min() {
if (!this->next) {
return;
} else if (!this->next->next) {
delete this->next;
this->next = nullptr;
return;
}
auto NextIsDel = this;
//auto DelData = NextIsDel->next->data;
auto cur = this;
while (cur->next) {
if (cur->next->data <= NextIsDel->next->data) {
NextIsDel = cur;
}
cur = cur->next;
}
NextIsDel->next = NextIsDel->next->next;
//delete NextIsDel->next;
}
unsigned int LNode::Partition(ElemType A[], unsigned int low, unsigned int high) {
ElemType pivot = A[low];
while (low < high) {
while (low < high && A[high] >= pivot) {
--high;
}
A[low] = A[high];
while (low < high && A[low] <= pivot) {
++low;
}
A[high] = A[low];
}
A[low] = pivot;
return low;
}
void LNode::QuickSort(ElemType A[], unsigned int low, unsigned int high) {
if (low < high) {
unsigned int pivotpos = Partition(A, low, high);
QuickSort(A, low, pivotpos - 1);
QuickSort(A, pivotpos + 1, high);
}
}
void LNode::SortLinkedList() {
if (!this->next || !this->next->next) {
printf("Needn't to be sorted\n");
return;
}
auto p = this->next;
unsigned int TopOfA = 0;
ElemType A[this->GetLength()];
while (p) {
A[TopOfA] = p->data;
TopOfA++;//When the loop breaks, TopOfA is the num of the elems in this linkedList
p = p->next;
}
sort(A, A + TopOfA);
//QuickSort(A, 0, TopOfA);
p = this->next;
auto cur = 0;
while (p) {
p->data = A[cur];
cur++;
p = p->next;
}
}
void LNode::Delete_S_2_E(ElemType Start, ElemType End) {
bool flag = false;
auto BeforeDel = this;
while (BeforeDel->next) {
if ((BeforeDel->next->data >= Start) && (BeforeDel->next->data <= End)) {
printf(" %d", BeforeDel->next->data);
BeforeDel->next = BeforeDel->next->next;
flag = true;
} else {
BeforeDel = BeforeDel->next;
}
}
if (flag) {
printf(", which are in the range of %d to %d has been deleted\n", Start, End);
} else {
printf("No elem is deleted\n");
}
}
unsigned int LNode::GetLength() {
unsigned int count = 0;
auto p = this->next;
while (p) {
count++;
p = p->next;
}
return count;
}
void LNode::FindFirstCommonNode(LNode *L2) {
auto Len1 = this->GetLength();
auto Len2 = L2->GetLength();
if (!Len1 || !Len2) {
printf("No common node\n");
return;
}
auto tmp1 = this->next;
auto tmp2 = L2->next;
while (Len1 != Len2) {
if (Len1 > Len2) {
tmp1 = tmp1->next;
Len1--;
} else {
tmp2 = tmp2->next;
Len2--;
}
}
while (tmp1 && tmp2) {
if (tmp1 == tmp2) {
printf("Common Node found, its addr is %p, its data is %d\n", tmp1, tmp1->data);
return;
}
tmp1 = tmp1->next;
tmp2 = tmp2->next;
}
printf(" Common Node not found\n");
}
LNode *LNode::FindMin() {
if (!this->next) {
return nullptr;
}
auto p = this->next;
auto LocMin = p;
while (p) {
if (p->data <= LocMin->data) {
LocMin = p;
}
p = p->next;
}
return LocMin;
}
void LNode::SortLinkedList_NoTmpSpace() {
auto newHead = new LNode;
LNode *tmp = newHead;
while (this->next) {
auto del = this->FindMin();
auto ins = new LNode(del->data);
tmp->next = ins;
tmp = tmp->next;
this->Delete_Min();
}
this->next = newHead->next;
delete newHead;
}
/*P37.10, P37.11*/
void LNode::Divide_Odd_Even() {
auto A = new LNode;
auto B = new LNode;
auto tmpA = A;
auto tmpB = B;
unsigned int cur = 1;
auto TMP = this->next;
while (TMP) {
if (cur % 2 == 1) {
auto insA = new LNode(TMP->data);
tmpA->next = insA;
tmpA = tmpA->next;
} else {
auto insB = new LNode(TMP->data);
tmpB->next = insB;
tmpB = tmpB->next;
}
cur++;
TMP = TMP->next;
}
printf("TraverseOdd:");
A->Traverse();
A->DestroyList();
printf("TraverseEven:");
B->Traverse();
B->DestroyList();
}
/*P37.12*/
/*I promise you the linkedlist has been sorted*/
void LNode::MakeElemsUnique() {
if (!this->next || !this->next->next) {
return;
}
auto cur_node = this->next;
while (cur_node) {
auto next_node = cur_node;
while (next_node && next_node->data == cur_node->data) {
auto del = next_node;
next_node = next_node->next;
if (del != cur_node) {
delete del;
cur_node->next = next_node;
}
}
cur_node = next_node;
}
}
/*P37.13*/
/*I promise you the linkedlist has been sorted*/
void LNode::Merge2LinkList_Dec(LNode *L2) {
auto newHead = new LNode;
auto tmpHead1 = this->next;
auto tmpHead2 = L2->next;
while (tmpHead1 && tmpHead2) {
if (tmpHead1->data < tmpHead2->data) {
auto ins = tmpHead1;
tmpHead1 = tmpHead1->next;
ins->next = newHead->next;
newHead->next = ins;
} else {
auto ins = tmpHead2;
tmpHead2 = tmpHead2->next;
ins->next = newHead->next;
newHead->next = ins;
}
}
if (tmpHead1) {
while (tmpHead1) {
auto ins = tmpHead1;
tmpHead1 = tmpHead1->next;
ins->next = newHead->next;
newHead->next = ins;
}
}
if (tmpHead2) {
while (tmpHead2) {
auto ins = tmpHead2;
tmpHead2 = tmpHead2->next;
ins->next = newHead->next;
newHead->next = ins;
}
}
this->next = newHead->next;
delete newHead;
}
/*P37.14*/
/*I promise you the linkedlist has been sorted increasingly*/
void LNode::Merge2LinkList_Inc(LNode *L2) {
auto newHead = new LNode;
auto cur = newHead;
auto tmp1 = this->next;
auto tmp2 = L2->next;
while (tmp1 && tmp2) {
if (tmp1->data < tmp2->data) {
auto tmp1_next = tmp1->next;
tmp1->next = nullptr;
cur->next = tmp1;
tmp1 = tmp1_next;
} else {
auto tmp2_next = tmp2->next;
tmp1->next = nullptr;
cur->next = tmp2;
tmp2 = tmp2_next;
}
cur = cur->next;
}
if (!tmp1) {
cur->next = tmp2;
}
if (!tmp2) {
cur->next = tmp1;
}
this->next = newHead->next;
delete newHead;
}
/*P37.15*/
/*I promise you the linkedlist has been sorted increasingly*/
void LNode::Get2LinkListsIntersection(LNode *L2) {
auto newHead = new LNode;
auto cur = newHead;
auto tmp1 = this->next;
auto tmp2 = L2->next;
while (tmp1 && tmp2) {
if (tmp1->data == tmp2->data) {
auto tmp1_next = tmp1->next;
tmp1->next = nullptr;
cur->next = tmp1;
tmp1 = tmp1_next;
tmp2 = tmp2->next;
cur = cur->next;
} else if (tmp1->data < tmp2->data) {
auto del = tmp1;
tmp1 = tmp1->next;
delete del;
} else {
auto del = tmp2;
tmp2 = tmp2->next;
delete del;
}
}
this->next = newHead->next;
delete newHead;
}
/*P37.16*/
bool LNode::IsSuccessiveSeq(LNode *B) {
if (!this->next || !B->next) {
return false;
}
auto cur_A = this->next;
while ((cur_A->data != B->next->data) && cur_A) {
cur_A = cur_A->next;
}
if (!cur_A) {
return false;
} else {
auto cur_B = B->next;
while (cur_A && cur_B) {
if (cur_A->data != cur_B->data) {
return false;
}
cur_A = cur_A->next;
cur_B = cur_B->next;
}
if (!cur_A && cur_B) {
return false;
}
}
return true;
}
/*P37.21【2009】*/
bool LNode::FindReverseKthElem(unsigned int K) {
auto p = this;
auto copy_K = K;
while (K-- && p) {
p = p->next;
}
if (!p) {
return false;
} else {
auto rear = this;
while (p) {
rear = rear->next;
p = p->next;
}
cout << " Reversed " << copy_K << "th elem is " << rear->data << endl;
}
return true;
}
void LNode::MakeElemsUniqueAbs(unsigned int dataRange) {
if (!this->next || !dataRange) {
return;
}
bool *Hash = new bool[dataRange + 1]; //TODO:数据绝对值范围小于等于n，需要开辟n+1个数组空间
for (unsigned int i = 0; i < dataRange + 1; i++) {
Hash[i] = false;
}
auto newHead = new LNode;
auto cur = newHead;
auto p = this->next;
while (p) {
if (!Hash[abs(p->data)]) {
Hash[abs(p->data)] = true;
auto ins = new LNode(p->data);
cur->next = ins;
cur = ins;
}
p = p->next;
}
this->next = newHead->next;
delete[]Hash;
delete newHead;
}
void Sln3() {
cout << "P37.3: Reverse traverse:" << endl;
auto L1 = new LNode;
Create(L1);
cout << "Successfully create:";
L1->Traverse();
cout << __FUNCTION__ << ":";
L1->next = L1->next->Reverse();
L1->Traverse();
}
void Sln4() {
cout << "P37.4: Delete min:" << endl;
LNode *L1 = new LNode;
Create(L1);
cout << "Successfully create:";
L1->Traverse();
cout << __FUNCTION__ << ":";
L1->Delete_Min();
L1->Traverse();
}
void Sln5() {
cout << "P37.5: Reverse directly:" << endl;
LNode *L1 = new LNode;
Create(L1);
cout << "Successfully create:";
L1->Traverse();
cout << __FUNCTION__ << ":";
L1->next = L1->next->Reverse();
L1->Traverse();
}
void Sln6() {
cout << "P37.6: Sort increasingly:" << endl;
LNode *L1 = new LNode;
Create(L1);
cout << "Successfully create:";
L1->Traverse();
cout << __FUNCTION__ << ":";
L1->SortLinkedList();
L1->Traverse();
}
void Sln7() {
cout << "P37.7: Delete elems in range:" << endl;
LNode *L1 = new LNode;
Create(L1);
cout << "Successfully create:";
L1->Traverse();
ElemType Start, End;
cout << "Start: ";
cin >> Start;
cout << "End: ";
cin >> End;
cout << "P37.7: Delete elems from :" << Start << " to " << End << ":" << endl;
cout << __FUNCTION__ << ":";
L1->Delete_S_2_E(Start, End);
L1->Traverse();
}
void Sln8() {
cout << "P37.8: FindFirstCommonNode:" << endl;
LNode *L1 = new LNode;
Create(L1);
cout << "Successfully create:";
L1->Traverse();
LNode *L2 = new LNode;
Create(L2);
auto p = L2;
while (p->next) {
p = p->next;
}
p->next = L1->next->next->next->next->next->next;
cout << __FUNCTION__ << ":";
L1->FindFirstCommonNode(L2);
L1->Traverse();
}
void Sln9() {
cout << "P37.9: SortLinkedList_NoTmpSpace:" << endl;
LNode *L1 = new LNode;
Create(L1);
cout << "Successfully create:";
L1->Traverse();
L1->SortLinkedList_NoTmpSpace();
cout << __FUNCTION__ << ":";
L1->Traverse();
}
void Sln10() {
cout << "P37.10: Divide_Odd_Even:" << endl;
LNode *L1 = new LNode;
Create(L1);
cout << "Successfully create:";
L1->Traverse();
cout << __FUNCTION__ << ":";
L1->Divide_Odd_Even();
}
void Sln12() {
cout << "P37.12: MakeElemsUnique:" << endl;
cout << "Create a increasing list: ";
LNode *L1 = new LNode;
Create(L1);
cout << "Successfully create:";
L1->Traverse();
cout << __FUNCTION__ << ":";
L1->MakeElemsUnique();
L1->Traverse();
}
void Sln13() {
cout << "P37.13: Merge2LinkList_Dec:" << endl;
cout << "Create the first increasing lists: ";
LNode *L1 = new LNode;
Create(L1);
cout << "Successfully create:";
L1->Traverse();
cout << "Create the second increasing lists: ";
LNode *L2 = new LNode;
Create(L2);
cout << "Successfully create:";
L2->Traverse();
cout << __FUNCTION__ << ":";
L1->Merge2LinkList_Dec(L2);
L1->Traverse();
}
void Sln15() {
cout << "P37.15: Get2LinkListsIntersection:" << endl;
cout << "Create the first increasing lists: ";
LNode *L1 = new LNode;
Create(L1);
cout << "Successfully create:";
L1->Traverse();
cout << "Create the second increasing lists: ";
LNode *L2 = new LNode;
Create(L2);
cout << "Successfully create:";
L2->Traverse();
cout << __FUNCTION__ << ":";
L1->Get2LinkListsIntersection(L2);
L1->Traverse();
}
void Sln16() {
cout << "P37.16: IsSuccessiveSeq:" << endl;
cout << "Create the first lists: ";
LNode *L1 = new LNode;
Create(L1);
cout << "Successfully create:";
L1->Traverse();
cout << "Create the lists: ";
LNode *L2 = new LNode;
Create(L2);
cout << "Successfully create:";
L2->Traverse();
cout << __FUNCTION__ << ":";
cout << L1->IsSuccessiveSeq(L2) << endl;
L1->Traverse();
}
void Sln21() {
cout << "P37.21: FindReverseKthElem:" << endl;
cout << "Create the lists: ";
LNode *L1 = new LNode;
Create(L1);
cout << "Successfully create:";
L1->Traverse();
cout << "K: ";
unsigned int K;
cin >> K;
cout << __FUNCTION__ << ":";
if (!(L1->FindReverseKthElem(K))) {
cout << K << " is out of range" << endl;
}
}
void Sln23() {
cout << "P37.23: MakeElemsUniqueAbs:" << endl;
cout << "Create the lists: ";
LNode *L1 = new LNode;
Create(L1);
cout << "Successfully create:";
L1->Traverse();
cout << __FUNCTION__ << ":";
L1->MakeElemsUniqueAbs(100);
L1->Traverse();
}
int main() {
Sln3();
Sln4();
Sln5();
Sln6();
Sln7();
Sln8();
Sln9();
Sln10();
Sln12();
Sln13();
Sln15();
Sln16();
Sln21();
Sln23();
return 0;
}
测试数据和输出
P37.3: Reverse traverse:
1 2 3 4 5 -1
Successfully create: 1 2 3 4 5
Sln3: 5 4 3 2 1
P37.4: Delete min:
9 5 1 7 8 6 2 0 3 4 -1
Successfully create: 9 5 1 7 8 6 2 0 3 4
Sln4: 9 5 1 7 8 6 2 3 4
P37.5: Reverse directly:
1 2 3 4 -1
Successfully create: 1 2 3 4
Sln5: 4 3 2 1
P37.6: Sort increasingly:
9 5 1 7 8 4 6 3 2 0 -1
Successfully create: 9 5 1 7 8 4 6 3 2 0
Sln6: 0 1 2 3 4 5 6 7 8 9
P37.7: Delete elems in range:
1 2 3 4 5 6 7 8 9 -1
Successfully create: 1 2 3 4 5 6 7 8 9
Start:-10
End:10
P37.7: Delete elems from :-10 to 10:
Sln7: 1 2 3 4 5 6 7 8 9, which are in the range of -10 to 10 has been deleted
List is null
P37.8: FindFirstCommonNode:
1 2 3 4 5 6 7 8 9 -1
Successfully create: 1 2 3 4 5 6 7 8 9
1 2 3 -1
Sln8:Common Node found, its addr is 00000000007b6770, its data is 6
1 2 3 4 5 6 7 8 9
P37.9: SortLinkedList_NoTmpSpace:
2 3
-1
Successfully create: 2 3
Sln9: 2 3
P37.10: Divide_Odd_Even:
1 2 3 4 5 6 7 8 9 10 -1
Successfully create: 1 2 3 4 5 6 7 8 9 10
Sln10:TraverseOdd: 1 3 5 7 9
TraverseEven: 2 4 6 8 10
P37.12: MakeElemsUnique:
Create a increasing list:1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 3 3 10 -1
Successfully create: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 3 3 10
Sln12: 1 2 3 10
P37.13: Merge2LinkList_Dec:
Create the first increasing lists:1 2 3 4 5 -1
Successfully create: 1 2 3 4 5
Create the second increasing lists:1 2 3 4 5 -1
Successfully create: 1 2 3 4 5
Sln13: 5 5 4 4 3 3 2 2 1 1
P37.15: Get2LinkListsIntersection:
Create the first increasing lists:1 2 3 4 5 6 7 8 -1
Successfully create: 1 2 3 4 5 6 78
Create the second increasing lists:4 5 6 10 -1
Successfully create: 4 5 6 10
Sln15: 4 5 6
P37.16: IsSuccessiveSeq:
Create the first lists:1 2 3 4 5 6 7 8 9 -1
Successfully create: 1 2 3 4 5 6 7 8 9
Create the lists:2 3 4 -1
Successfully create: 2 3 4
Sln16:1
1 2 3 4 5 6 7 8 9
P37.21: FindReverseKthElem:
Create the lists:1 2 3 4 5 6 -1
Successfully create: 1 2 3 4 5 6
K:5
Sln21: Reversed 5th elem is 2
P37.23: MakeElemsUniqueAbs:
Create the lists:-9 -8 -7 -6 -5 -4 -3 -2 0 1 2 3 4 5 6 7 8 9 10 -1
Successfully create: -9 -8 -7 -6 -5 -4 -3 -2 0 1 2 3 4 5 6 7 8 9 10
Sln23: -9 -8 -7 -6 -5 -4 -3 -2 0 1 10
进程已结束，退出代码 0
京公网安备 11010502036488号