1 //算法 2 //设计将两个递增有序带头结点链表合并为一个有序递减的链表。 3 //1,2,3,4,5 4 //2,5,9,10 5 void MergeList(LinkList &La,LinkList &Lb) 6 { 7 LNode *r,*pa=La->next,pb=Lb->next; 8 La->next=null;//将结果链表La初始化 9 while(pa&&pb) 10 { 11 if(pa->data<=pb->data){ 12 r=pa->next; 13 pa->next=La->next;//前插入法,所有新插入的结点都在 14 La->next=pa; 15 pa=r; 16 } 17 else 18 { 19 r=pb->next; 20 pb->next=La->next; 21 La->next=pb; 22 pb=r; 23 } 24 } 25 if(pa){ 26 pb=pa; 27 } 28 while(pb) 29 { 30 r=pb->next; 31 pb->next=La->next; 32 La->next=pb; 33 pb=r; 34 } 35 free(Lb); 36 } 37 38 39 //BFS广度优先遍历 40 bool visited[max_vertex]; 41 void BFSTraverse(Graph G) 42 { 43 for(i=0;i<G.vexnum;i++){ 44 visited[i]=false; 45 } 46 InitQueue(Q); 47 for(i=0;i<vexnum;i++){ 48 if(!visited[i]) 49 BFS(G,i); 50 } 51 } 52 void BFS(Graph G,int v){ 53 visit(v); 54 visited[v]=true; 55 EnQueue(Q,v); 56 while(!isEmpty(Q)) 57 { 58 DeQueue(Q,v); 59 for(w=FirstNeighbor(G,v);w>=0;w=NextNeighBor(G,v,w)){ 60 //检测所有邻结点 61 if(!visited[w]){ 62 visit(w); 63 visited[w]=true; 64 EnQueue(Q,w); 65 } 66 } 67 } 68 } 69 70 //单链表递增输出各结点的数据元素,并释放存储空间 71 void Min_Delete(LinkList head){ 72 LinkNode *pre_min,*pre;//pre_min指向最小 73 LinkNode *r; 74 while(head->next){ 75 pre_min=head; 76 pre=head->next; 77 while(pre->next){ 78 if(pre->next->data>pre_min->next->data){ 79 pre_min=pre; 80 } 81 } 82 r=pre_min->next; 83 pre_min->next=pre_min->next->next; 84 free(r); 85 } 86 free(head); 87 } 88 89 //二叉树的前中后序递归算法 90 91 void PreOrder(Btree BT){ 92 if(BT != NULL){ 93 cout<<BT->data<<endl; 94 PreOrder(BT->lchild); 95 PreOrder(BT->rchild); 96 } 97 } 98 //中序遍历 99 /* 100 void InOrder(Btree BT) { 101 if (BT != NULL) { 102 InOrder(BT->lchild); 103 cout << BT->data << endl; 104 InOrder(BT->rchild); 105 } 106 } 107 */ 108 109 //后序遍历 110 /* 111 void PostOrder(Btree BT) { 112 if (BT != NULL) { 113 PostOrder(BT->lchild); 114 PostOrder(BT->rchild); 115 cout << BT->data << endl; 116 } 117 } 118 */ 119 120 121 void PreOrderNoRecur(Btree root){ 122 stack<Btree> S; 123 while(root!=NULL||!S.empty()){ 124 while(root!=NULL) 125 { 126 cout<< root->data<<endl; 127 S.push(root); 128 root=root->lchild; 129 } 130 } 131 if(!S.empty()){ 132 root=S.top(); 133 S.pop(); 134 root=root->rchild; 135 } 136 } 137 138 139 //中序遍历非递归算法 140 /* 141 void InOrderNoRecur(Btree root) { 142 stack<Btree> S; 143 while (root != NULL || !S.empty()) { 144 while (root != NULL) { 145 S.push(root); 146 root = root->lchild; 147 } 148 149 if (!S.empty()) { 150 root = S.top(); 151 cout << root->data << endl; 152 S.pop(); 153 root = root->rchild; 154 } 155 } 156 } 157 */ 158 159 //后序遍历非递归算法 160 void PostOrderNoRecur(Btree root) { 161 stack<List> newS; 162 while (root != NULL || !newS.empty()) { 163 while (root != NULL) { 164 List element; 165 element.ptr = root; 166 element.flag = 1; 167 newS.push(element); 168 root = root->lchild; 169 } 170 while (!newS.empty() && newS.top().flag == 2) { 171 cout << newS.top().ptr->data << endl; 172 newS.pop(); 173 } 174 if (!newS.empty()) { 175 newS.top().flag = 2; 176 root = newS.top().ptr->rchild; 177 } 178 } 179 } 180 181 182 //设计一个算法将二叉树的叶结点按从左到右的顺序连成一个单链表,表头指针head。 183 //叶结点的右指针域来存放单链表指针 184 LinkList head; 185 LinkNode *pre=NULL; 186 LinkList InOrder(BiTree bt) 187 { 188 if(bt){ 189 InOrder(bt->lchild);//中序遍历左子树 190 if(bt->lchild=NULL&&bt->rchild=NULL){ //叶结点 191 if(pre==NULL){ //处理第一个叶结点 192 head->next=bt; 193 } 194 else{ 195 pre->right=bt; 196 } 197 pre=bt; 198 } 199 else{ 200 InOrder(bt->rchild);//中序遍历右子树 201 } 202 if(pre){ 203 pre->rchild=NULL;//设置链表尾 204 } 205 return head; 206 } 207 } 208 209 //编写一个利用广度优先搜索算法求解单源最短路径功能 210 void BFS_MIN_Distance(Grapsh G,int u){ 211 for(i=0;i<G.vexnul;i++){ 212 d[i]=oo;//从u到i结点的最短路径,w不存在 213 214 } 215 visited[u]=true; 216 d[u]=0; 217 EnQueue(Q,u); 218 while(!isEmpty(Q)){ 219 //BFS算法 220 DeQueue(Q,u); 221 for(w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w))//检测所有邻接点 222 { 223 if(!visted[w]){ 224 vistted[w]=true; 225 d[w]=d[u]+1; 226 EnQueue(Q,w); 227 } 228 } 229 } 230 } 231 232 233 //交换左子树右子树,递归 234 typedef struct BiTNode{ 235 ElemType data; 236 BiNode *lchild; 237 BiNode *rchild; 238 }*BiTree,BiTNode; 239 void Exchange(BiTree t){ 240 if(t==NULL){ 241 retrun; 242 } 243 Exchange(t->lchild);//对左子树进行交换操作 244 Exchange(t->rchild); 245 246 BiTNode *temp=t->lchild; 247 t->lchild=t->rchild; 248 t->rchild=temp; 249 } 250 251 252 253 254 255 //迪杰斯特拉 256 bool closed[N]={FALSE}; 257 int Min[N]={INF}; 258 closed[start]=true;//假设从start出发到其余各个点的最短路径 259 Min[start]=0; 260 for(int i=0;i<N;i++){ //将剩余的N-1个顶点距离start的最短路径求出 261 int k=-1; 262 for(int j=1;j<N;++j){ 263 if(!closed[j]&&(k=-1||Min[k]>Min[j])){ 264 k=j; 265 } 266 } 267 closed[k]=true;//将k加入已得出结果的集合 268 269 for(int j=0;j<N;++j){ 270 if(!visited[j]){ //更新未求得最短路径的结点得到start的最短距离 271 if(Min[j]>Min[k]+G[k][j]){ 272 Min[j]=Min[k]+G[k][j]; 273 } 274 275 } 276 } 277 278 }
标签:pre,常见,next,pb,算法,rchild,NULL,root From: https://www.cnblogs.com/donxiao-999/p/16948983.html