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


递归调用 简单

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

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

// 链表.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"


typedef struct Node {
    int data;
    struct Node *next;

} LinkList;


//链表组合的函数 输入：两个有序无头结点链表 输出：将链表组合成一个无头结点有序链表
LinkList * combie(LinkList *l1, LinkList * l2) {

    LinkList * p=NULL;

    if (l1==NULL && l2==NULL)
    {
        p = NULL;
    }
    if (l1==NULL&&l2!=NULL)
    {
        p = (LinkList *)malloc(sizeof(LinkList));
        p->data = l2->data;
        p->next = combie(NULL, l2->next);

    }

    if (l2 == NULL&&l1 != NULL)
    {
        p = (LinkList *)malloc(sizeof(LinkList));
        p->data = l1->data;
        p->next = combie(l1->next,NULL);

    }
    if (l1!=NULL && l2!=NULL)
    {
        p = (LinkList *)malloc(sizeof(LinkList));

        p->data = l1->data <= l2->data ? l1->data : l2->data;
        p->next = combie(l1->data <= l2->data ? l1->next : l1, l1->data <= l2->data ? l2 : l2->next);
   
    }
    return p;
}

 

//根据数组创建无头结点的链表
LinkList * create(int a[], int n) {
    LinkList *h = NULL, *p, *pre = NULL;
    for (int i = 0; i < n; i++)
    {
        p=(LinkList *)malloc(sizeof(LinkList));
        p->data = a[i];
        if (pre) pre->next = p;
        pre = p;
        if (i == 0) h = p;
        if (i == n - 1) p->next = NULL;
       
    }
    return h;


}


//打印输出无头结点的链表
void display(LinkList *list) {
    LinkList *p = list;
    while (p != NULL)
    {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;

}

int _tmain(int argc, _TCHAR* argv[])
{
    int a []= { 1, 2, 10, 80,500 };
    LinkList *l1 = create(a,5);
    display(l1);
    int b[] = { 0,4, 5, 100, 177,250 };
    LinkList *l2 = create(b, 6);
    display(l2);
    LinkList * p = combie(l1, l2);
    display(p);
    system("pause");
    return 0;
}

stdafx.h 的内容挺简单的

// stdafx.h : 标准系统包含文件的包含文件，
// 或是经常使用但不常更改的
// 特定于项目的包含文件
//

#pragma once

#include "targetver.h"

#include <stdio.h>
#include <tchar.h>

 

// TODO:  在此处引用程序需要的其他头文件
#include <iostream>
#include <cstdlib>
using namespace std;

本文永久更新链接地址：

相关内容