数据结构学习---有序链表的合并
递归调用 简单
有点像归并排序的合并部分吧。
因为是用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
#include
// TODO: 在此处引用程序需要的其他头文件
#include
#include
using namespace std;
查看评论 回复