数据结构学习---有序链表的合并-白红宇

数据结构学习---有序链表的合并

阅读量：5173 次

发布时间：2019-06-13

本文共 2307 字，大约阅读时间需要 7 分钟。

递归调用简单

有点像归并排序的合并部分吧。

因为是用vs创建的工程，所以主函数是_tmain。

1 // 链表.cpp : 定义控制台应用程序的入口点。 2 // 3  4 #include "stdafx.h" 5  6  7 typedef struct Node { 8     int data; 9     struct Node *next;10 11 } LinkList;12 13 14 //链表组合的函数 输入：两个有序无头结点链表 输出：将链表组合成一个无头结点有序链表15 LinkList * combie(LinkList *l1, LinkList * l2) {16 17     LinkList * p=NULL;18 19     if (l1==NULL && l2==NULL)20     {21         p = NULL;22     }23     if (l1==NULL&&l2!=NULL)24     {25         p = (LinkList *)malloc(sizeof(LinkList));26         p->data = l2->data;27         p->next = combie(NULL, l2->next);28 29     }30 31     if (l2 == NULL&&l1 != NULL)32     {33         p = (LinkList *)malloc(sizeof(LinkList));34         p->data = l1->data;35         p->next = combie(l1->next,NULL);36 37     }38     if (l1!=NULL && l2!=NULL)39     {40         p = (LinkList *)malloc(sizeof(LinkList));41 42         p->data = l1->data <= l2->data ? l1->data : l2->data; 43         p->next = combie(l1->data <= l2->data ? l1->next : l1, l1->data <= l2->data ? l2 : l2->next);44     45     }46     return p;47 }48 49 50 51 //根据数组创建无头结点的链表52 LinkList * create(int a[], int n) {53     LinkList *h = NULL, *p, *pre = NULL;54     for (int i = 0; i < n; i++)55     {56         p=(LinkList *)malloc(sizeof(LinkList));57         p->data = a[i];58         if (pre) pre->next = p;59         pre = p;60         if (i == 0) h = p;61         if (i == n - 1) p->next = NULL;62         63     }64     return h;65 66 67 }68 69 70 //打印输出无头结点的链表71 void display(LinkList *list) {72     LinkList *p = list;73     while (p != NULL)74     {75         cout << p->data << " ";76         p = p->next;77     }78     cout << endl;79 80 }81 82 int _tmain(int argc, _TCHAR* argv[])83 {84     int a []= { 1, 2, 10, 80,500 };85     LinkList *l1 = create(a,5);86     display(l1);87     int b[] = { 0,4, 5, 100, 177,250 };88     LinkList *l2 = create(b, 6);89     display(l2);90     LinkList * p = combie(l1, l2);91     display(p);92     system("pause");93     return 0;94 }

stdafx.h 的内容挺简单的

// stdafx.h : 标准系统包含文件的包含文件，// 或是经常使用但不常更改的// 特定于项目的包含文件//#pragma once#include "targetver.h"#include 
     
      #include 
      
       // TODO:  在此处引用程序需要的其他头文件#include 
       
        #include 
        
         using namespace std;