博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
C++链表冒泡,归并,插入排序(纯指针)
阅读量:6000 次
发布时间:2019-06-20

本文共 6200 字,大约阅读时间需要 20 分钟。

#include 
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
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;}

转载地址:http://ahbmx.baihongyu.com/

你可能感兴趣的文章
directive ngChecked
查看>>
面试110道题
查看>>
python 08 文件操作
查看>>
强势解决:windows 不能在本地计算机中起动Tomcat参考特定错误代码1
查看>>
Gradle 配置debug和release工程目录
查看>>
curl指令的使用
查看>>
LNAMP第二版(nginx 1.2.0+apache 2.4.2+php 5.4)
查看>>
MongoDB repl set权限认证配置步骤
查看>>
java学习笔记(1)
查看>>
禁止Mysql默认端口访问Internet - MySQL - IT技术网
查看>>
基于用户投票的排名算法(二):Reddit
查看>>
下午最后的草坪
查看>>
Maven学习总结(七)——eclipse中使用Maven创建Web项目
查看>>
用PHP读取和编写XML DOM4
查看>>
1.部分(苹果)移动端的cookie不支持中文字符,2.从json字符串变为json对象时,只支持对象数组...
查看>>
vim配置及快捷键
查看>>
2018省赛赛第一次训练题解和ac代码
查看>>
UWP Composition API - 锁定列的FlexGrid
查看>>
[转载] win10进行端口转发
查看>>
利用JavaScript jQuery实现图片无限循环轮播(不借助于轮播插件)-----转载
查看>>