C++链表冒泡,归并,插入排序(纯指针)
2023-09-14 09:08:58 时间
#include <iostream>
using namespace std;
//别问我为什么要写链表的冒泡排序。
struct Node
{
int data;
Node *next;
Node(int d = int()) :data(d), next(NULL){}
};
class List
{
public:
List(int a[], int n)
{
first = NULL;
for (int i = 0; i < n; i++)
{
if (first == NULL)
{
first = new Node(a[i]);
}
else
{
Node *s = new Node(a[i]);
Node *p = first;
while (p->next != NULL)
{
p = p->next;
}
s->next = p->next;
p->next = s;
}
}
}
//////////////////////////////////////////////////////////////////////////////
//冒泡排序
void Bul()
{
Node *ptr_one = first;
Node *ptr_twe;
Node *pr_one = NULL;
Node *save = NULL;
if (ptr_one == NULL || ptr_one->next == NULL)return;
while (ptr_one != NULL && ptr_one->next != NULL)
{
Node *pr_twe = ptr_one;
Node *m2 = NULL;
save = ptr_one;
for (ptr_twe = ptr_one->next; ptr_twe != NULL;)
{
if (ptr_one->data > ptr_twe->data)
{
if (pr_one == NULL)
{
Node *m1;
Node *a;
m1 = ptr_twe->next;
m2 = ptr_one->next;
first->next = m1;
pr_twe->next = first;
a = first;
ptr_twe->next = m2;
first = ptr_twe;
save = ptr_twe;
ptr_twe = a;
ptr_one = first;
}
else
{
Swap(pr_one, pr_twe);
save = pr_one->next;
ptr_one = save;
ptr_twe = pr_twe->next;
}
}
pr_twe = ptr_twe;
if (ptr_twe == NULL)continue;
ptr_twe = ptr_twe->next;
}
pr_one = save;
ptr_one = pr_one->next;
}
}
void Swap(Node *prv1, Node *&prv2)
{
if (prv1->next == prv2)
{
Node *m = prv1->next;
Node *n = prv2->next;
m->next = n->next;
n->next = m;
prv1->next = n;
prv2 = n;
}
else
{
Node *m1 = prv1->next;
Node *save = m1->next;
Node *m2 = prv2->next;
m1->next = m2->next;
prv2->next = m1;
m2->next = save;
prv1->next = m2;
}
}
void Printf()
{
Node *p = first;
while (p != NULL)
{
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
//////////////////////////////////////////////////////////////////////////////////////
//2路归并排序。
Node *GetMidNode(Node* Start_Ptr)
{
Node *slow = Start_Ptr;
Node *fast = Start_Ptr;
if (Start_Ptr == NULL || Start_Ptr->next == NULL || Start_Ptr->next->next==NULL)return Start_Ptr;
while (fast != NULL)
{
if (fast->next == NULL)
{
break;
}
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
void Merge()
{
Merge(first);
}
Node* Merge(Node *Start_Ptr)
{
if (Start_Ptr==NULL || Start_Ptr->next == NULL) return Start_Ptr;
else
{
Node *Mid_Ptr = GetMidNode(Start_Ptr);
Node *Next_Ptr = Mid_Ptr->next;
Mid_Ptr->next = NULL;
return Merage(Merge(Start_Ptr),Merge(Next_Ptr));
}
}
Node* Merage(Node *ptr1, Node *ptr2)
{
Node* p1 = ptr1;
Node *p2 = ptr2;
Node *p = new Node();
Node *save = p;
while (p1 != NULL && p2 != NULL)
{
if (p1->data > p2->data)
{
p->next=p2;
p = p2;
p2 = p2->next;
}
else
{
p->next = p1;
p = p1;
p1 = p1->next;
}
}
if (p1 == NULL)
{
p->next = p2;
}
if (p2 == NULL)
{
p->next = p1;
}
first = save->next;
delete save;
save = NULL;
return first;
}
//////////////////////////////////////////////////////////////////////////////////////////
//插入排序。
void Insert()
{
Node *ptr_first = first;
Node *pr_first;
Node *ptr_twe;
Node *pr_twe;
Node *save;
for (; ptr_first != NULL;pr_first = ptr_first)
{
save = ptr_first->next;
if (ptr_first == first)
{
ptr_twe = ptr_first;
ptr_twe->next = NULL;
first = ptr_twe;
}
else
{
Node *p = ptr_twe;
Node *q = ptr_first;
while (p!=NULL&&p->data<q->data)
{
pr_twe = p;
p = p->next;
}
if (p == first)
{
//假设是第一个节点插入。
q->next = p;
ptr_twe = q;
first = ptr_twe;
}
else if(p == NULL)
{
pr_twe->next = q;
q->next = NULL;
}
else
{
q->next = pr_twe->next;
pr_twe->next = q;
}
}
ptr_first = save;
}
}
private:
Node *first;
};
int main()
{
int a[] = { 6,7,2,1,0,7,5,23,4,5,423,4,100,-32,4,-3,1};
List list(a, sizeof(a) / sizeof(int));
//list.Merge();
//list.Bul();
list.Insert();
list.Printf();
return 0;
}
相关文章
- 10min快速回顾C++语法(七)类、结构体、指针链表专题
- C++基础学习
- C/C++常见面试知识点总结附面试真题—-20220326更新
- c++中如何定义常量_电脑基础知识教程自学
- LeetCode1290 二进制链表转整数C++解法(vector实现)
- LeetCode141题环形链表C++(详解)
- leetcode:92. 反转链表 II(C++)
- C++内存池的简单原理及实现(纯代码解析)
- 链表排序总结(全)(C++)[通俗易懂]
- C++ ffmpeg+dxva2实现硬解码「建议收藏」
- C++基础——C++相比C语言的新特性梳理总结(C++新特性、输入输出方式、命名空间namespace)
- 【C++】STL 模拟实现之 vector
- C/C++:string类的模拟实现
- 图片JNI(C++/Java)高斯模糊 多线程详解手机开发
- C++ list,STL list(双向链表)详解
- 关于C/C++中typedef的定义与用法总结
- C++构造双向链表的实现代码
- 用C++实现单向循环链表的解决方法
- C++模版双向链表的实现详解
- 深入解析C++中的指针数组与指向指针的指针
- C++设计类不能被继承的方法实例讲解
- c++双向链表操作示例(创建双向链、双向链表中查找数据、插入数据等)