首页 > 代码库 > 基于无头节点的单链表的升序冒泡排序（C++实现）
基于无头节点的单链表的升序冒泡排序（C++实现）
由于基础代码的特殊（链表为无头链表），以下冒泡排序算法采用两种方式进行排序。首先对首节点往后的所有节点进行排序，这里使用的是对其索引顺序改变的方法。然后对首节点进行排序，只需要一次循环即可，这里使用的是对节点中的数值进行交换的方法。
1 #include <iostream> 2 using namespace std ; 3 4 #define ERROR -1 5 #define CORRECT 1 6 7 //定义 8 struct LNode { 9 int data ; 10 LNode *next ; 11 } ; 12 LNode *LinkList ; 13 14 //查找 15 LNode *SearchLinkList (LNode *L , int i) 16 { 17 int j ; 18 LNode *p ; 19 20 p = L ; 21 j = 1 ; 22 while (p &&j < i) 23 { 24 p = p -> next ; 25 j++ ; 26 } 27 if (!p || j>i) 28 { 29 return (p) ; 30 } 31 } 32 33 //插入 34 int InsertLinkList (LNode *L , int e , int i) 35 { 36 //在链表L中第i个位置插入元素e 37 LNode *p , *s ; 38 p = SearchLinkList (L , i-1) ; 39 if (!p) 40 { 41 return (ERROR) ; 42 } 43 s = new LNode ; 44 //节点插入L中 45 s -> data =http://www.mamicode.com/ e ; 46 s -> next = p -> next ; 47 p -> next = s ; 48 49 return (CORRECT) ; 50 } 51 52 //表单创建 53 LNode *CreateLinkList (int *r , int n) 54 { 55 int j ; 56 LNode *L , *p , *s ; 57 58 if (n <= 0) 59 { 60 return (NULL) ; 61 } 62 s = new LNode ; 63 s -> data = http://www.mamicode.com/r[1] ; 64 s -> next = NULL ; 65 L = s ; 66 p = L ; 67 for (j = 2 ; j <= n ; j++) 68 { 69 /* 70 s = new LNode ; 71 s -> data = http://www.mamicode.com/r[j] ;> 72 s -> next = NULL ; 73 p -> next = s; 74 p = s ; 75 */ 76 77 InsertLinkList (L , r[j] , j) ; 78 } 79 return (L) ; 80 } 81 82 //删除 83 int DeleteLinkList (LNode *L , int i) 84 { 85 //在表中删除第i个位置 86 int e ; 87 LNode *p , *q ; 88 89 p = SearchLinkList (L , i-1) ; 90 if (!p) 91 { 92 return (ERROR) ; 93 } 94 q = p -> next ; 95 p -> next = p -> next -> next ; //不可用q，因为q是用来指示将要删除的内存 96 e = q -> data ; 97 delete (q) ; 98 99 return (e) ;100 }101 102 //结果输出103 int ShowLinkList (LNode *L)104 {105 LNode *p ;106 107 if (!L)108 {109 return (ERROR) ;110 }111 p = L ;112 while (p -> next)113 {114 cout << p -> data <<" " ;115 p = p -> next ;116 }117 cout << p -> data << endl ;118 return (CORRECT) ;119 }120 121 //升序排序(完全用指针操作，有bug)122 int BubbleSortPoint (LNode *L)123 {124 LNode *HeadNode ;125 HeadNode = new LNode ;126 127 LNode *p ;128 LNode *q ;129 130 LNode *a1 ;131 LNode *a2 ;132 LNode *a3 ;133 if (!L)134 {135 return (ERROR) ;136 }137 138 HeadNode -> next = L ; //增加头节点139 140 cout << "HeadNode ->next ->data = http://www.mamicode.com/" <<HeadNode ->next->data << endl; //打印调试141 142 /*由于链表L为无头节点链表，故先对首节点数据进行处理*/143 144 for (p = HeadNode ; p -> next != NULL ; p = p -> next)145 {146 for (q = HeadNode; q -> next -> next != NULL ; q = q -> next)147 {148 /*节点指针*/149 a1 = q -> next ;150 a2 = q -> next -> next ; 151 a3 = q -> next -> next -> next ;152 153 /*打印调试*/154 cout << "a1 -> data = http://www.mamicode.com/" <<a1->data << endl ;155 cout << "a2 -> data = http://www.mamicode.com/" <<a2->data << endl ;156 if (a3!=NULL)157 {158 cout << "a3 -> data = http://www.mamicode.com/" <<a3->data << endl ;159 }160 else161 {162 cout << "a3 -> data = http://www.mamicode.com/NULL" <<endl ;163 }164 165 cout <<endl;166 167 /*打印调试*/168 if (a1 -> data > a2 -> data)169 {170 /*节点交换*/171 q -> next = a2 ;172 a2 -> next = a1 ;173 a1 -> next = a3 ;174 }175 }176 }177 178 //对首节点进行处理179 cout << "HeadNode -> next -> data = http://www.mamicode.com/" << HeadNode -> next -> data << endl ;180 p = L ;181 L = HeadNode -> next ;182 cout << "L -> data = http://www.mamicode.com/" << L -> data << endl ;183 cout << "L -> next -> data = http://www.mamicode.com/" << L -> next ->data << endl ;184 cout << "L -> next -> next -> data = http://www.mamicode.com/" << L -> next -> next ->data << endl ;185 cout << "L -> next -> next -> next -> data = http://www.mamicode.com/" << L -> next -> next -> next ->data << endl ;186 cout << "L -> next -> next ->next -> next -> data = http://www.mamicode.com/" << L -> next -> next -> next -> next ->data << endl ;187 188 return (CORRECT) ;189 }190 191 //升序冒泡排序(指针与data交换结合)192 int BubbleSort (LNode *L)193 {194 LNode *p ;195 LNode *q ;196 int middleData ; //中间数据，用于实现首节点数据的沉底操作197 198 /*用于节点索引顺序交换操作的指针定义*/199 LNode *a1 ;200 LNode *a2 ;201 LNode *a3 ;202 203 if (!L)204 {205 return (ERROR) ;206 }207 208 209 /*先用指针索引更改的方式排序首节点以后的元素*/210 211 for (p = L ; p -> next != NULL ; p = p -> next)212 {213 for (q = L ; q -> next -> next != NULL ; q = q -> next)214 {215 /*节点指针*/216 a1 = q -> next ;217 a2 = q -> next -> next ; 218 a3 = q -> next -> next -> next ;219 220 if (a1 -> data > a2 -> data)221 {222 /*节点交换*/223 q -> next = a2 ;224 a2 -> next = a1 ;225 a1 -> next = a3 ;226 }227 }228 }229 230 /*再对首节点数据采取数值交换的方式使其沉底*/231 p = L ;232 while (p -> next)233 {234 if (p -> data > p -> next -> data)235 {236 middleData = http://www.mamicode.com/p -> data ;237 p -> data = http://www.mamicode.com/p -> next -> data ;238 p -> next -> data =http://www.mamicode.com/ middleData ;239 }240 p = p -> next ;241 }242 243 return (CORRECT) ;244 245 }246 247 int main (int argc , char * argv[])248 {249 int r[100] , i ,SampleNum , SearchPos , NewPos , NewItem , DelPos ;250 LNode *p ;251 252 cin >> SampleNum ;253 for (i = 1 ; i <= SampleNum ; i++)254 {255 cin >> r[i] ;256 }257 LinkList = CreateLinkList (r , SampleNum) ;258 ShowLinkList (LinkList) ;259 260 cout << "冒泡排序：" << endl ;261 BubbleSort (LinkList) ;262 ShowLinkList (LinkList) ;263 264 cin >> SearchPos ;265 p = SearchLinkList (LinkList , SearchPos) ;266 cout << p -> data << endl ;267 268 cin >> NewPos ; 269 cin >> NewItem ;270 InsertLinkList (LinkList , NewItem , NewPos) ;271 ShowLinkList (LinkList) ;272 273 cin >> DelPos ;274 DeleteLinkList (LinkList , DelPos) ;275 ShowLinkList (LinkList) ;276 277 return 0;278 }
基于无头节点的单链表的升序冒泡排序（C++实现）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。