数据结构例子-将两个线性表合并(2)

By | 07月23日
Advertisement

将线性表la和lb合并为lc【link_la+lb=lc】
#include <iostream.h>
#include <stdlib.h>
typedef struct node{
int data;
struct node *next;
}lnode; //链表结点定义
#ifndef NULL
const int NULL=0;
#endif // 定义NULL常量
lnode * buildlink(int leng,lnode *p);
void output(lnode * p);
lnode* merge(lnode *la,lnode *lb,lnode *lc);
void main(void)
{
lnode *la,*lb,*lc;
int n,m;
cout<<"input the length of the la and lb:";
cin>>n>>m;
cout<<'\n';
la=(lnode *)malloc(sizeof(lnode));
if(la==NULL)
cout<<"la memory has not accessed ! false";//测试头节点空间是否成功
lb=(lnode *)malloc(sizeof(lnode));
if(lb==NULL)
cout<<"lb memory has not accessed ! false";
la->data=n;
la->next=NULL;
lb->data=n;
lb->next=NULL;
lc=(lnode *)malloc(sizeof(lnode));
if(lc==NULL)
cout<<"lc memory has not accessed ! false";
lc->next=NULL;
cout<<"la:"<<endl;
la=buildlink(n,la); //建立链表
cout<<"lb:"<<endl;
lb=buildlink(m,lb);
lc=merge(la,lb,lc); //合并链表
output(lc); //输出链表
}

lnode* buildlink(int leng,lnode *p)
{
lnode *h;
int i=1;
h=p;
while(i<=leng)
{
lnode *s;
s=(lnode *)malloc(sizeof(lnode));
s->next=NULL;
// cout<<"input the "<<i<<"th data:"<<ends;
cin>>s->data;
h->next=s;
h=s;
i++;
}
return(p);
}

lnode* merge(lnode *la,lnode *lb,lnode *lc)
{
lnode *p,*q,*r;
p=la->next;
q=lb->next;
r=lc;
while((p!=NULL)&&(q!=NULL))
{
if (p->data>q->data)
{ r->next=q;
q=q->next;
r=r->next;
r->next=NULL;
}
else if (p->data<q->data)
{ r->next=p;
p=p->next;
r=r->next;
r->next=NULL;
}
else
{ r->next=p;
p=p->next;
q=q->next;
r=r->next;
r->next=NULL;
}
}
if(p!=NULL) r->next=p;
if (q!=NULL) r->next=q;
return(lc);
}

void output(lnode * p)
{
lnode *h;
cout<<"output the linear_link datas :"<<endl;
h=p->next;
while(h)
{
cout<<h<<":"<<h->data<<endl;
h=h->next;
}
}

Similar Posts:

  • 2.2.2笔记-线性表合并

    数据结构笔记三 把顺序线性表合并,在教材P26中有个算法2.7.算法2.7的大致意思是:已知顺序线性表La和Lb的元素按值非递减排列,然后要求归并La和Lb得到新的顺序线性表Lc,Lc的元素也要按值非递减排列.下面程序的时间复杂度O(La.length+Lb.length). 备注:若以线性表表示集合并进行集合的各种运算,应先对表中元素进行排序.(教材P26) 源代码 #include<stdio.h> #include<stdlib.h> #include<math.h&g

  • 数据结构教程 第八课 线性表的链式表示与实现

    数据结构教程 第八课 线性表的链式表示与实现 本课主题: 线性表的链式表示与实现 教学目的: 掌握线性链表.单链表.静态链表的概念.表示及实现方法 教学重点: 线性链表之单链表的表示及实现方法. 教学难点: 线性链表的概念. 授课内容: 一.复习顺序表的定义. 二.线性链表的概念: 以链式结构存储的线性表称之为线性链表. 特点是该线性表中的数据元素可以用任意的存储单元来存储.线性表中逻辑相邻的两元素的存储空间可以是不连续的.为表示逻辑上的顺序关系,对表的每个数据元素除存储本身的信息之外,还需存储

  • 数据结构(第二课)--线性表

    数据结构,之前感觉不到其重要性,线性表对我们以后的编程会有什么帮助呢,今天看到关于一个java方面的问题才发现其重要性,在java中,我们所用到的集合list等,都是通过线性表来实现的,了解了线性表,我们对这些的理解会更深入,用起来会更加的得心应手,程序中的数据大致分为四种姐帮你的逻辑结构,集合,线性结构,树形结构,图状结构或网状结构,对于数据的不同逻辑结构,计算机在物理磁盘上通常有点2中方式,一个是链式存储结构,一种是顺序存储结构. 线性表是线性结构中最常用的数据结构. 顺序存储结构: 线性表

  • 《大话数据结构》读书笔记之线性表基本操作(静态单链表实现)

    /* Name: 线性表抽象数据类型(使用静态单链表实现) Copyright: Author: 巧若拙 Date:06-10-14 14:16 Description: 近一个月前我总结了线性表抽象数据类型(使用动态单链表实现),实际上更让我感兴趣的是静态链表.这种无需指针而有能够实现链表功能的结构, 对于那些不支持指针的高级语言来说,无疑是个巨大的福音.既可以像数组一样随机存取数据---它本身就是一个数组,又具有链表方便地实现插入和删除结点的功能: 由于它是模拟的"动态分配空间",

  • 数据结构基础(2)-------------线性表

    1.线性表顺序存储结构的优点:一是无需为元素之间的逻辑关系而增加额外的存储空间:二是可以迅速的取表中任意位置的元素.其缺点为:一是插入和删除需要移动大量的元素:二是线性表需要固定的存储空间,不适用于线性表长度变化较大的场合,也就是不灵活:三是有存储空间的碎片:(其实,动态数组在一定程度上可以避免此类情况的发生,比如STL中的std::vector) 2. 线性表的链式存储结构: 不仅要存储数据的信息,还要存储元素之间的逻辑关系,也即是后继元素的地址或者是前继元素的地址: 有了头结点,对第一元素的

  • 数据结构基础温故-1.线性表(下)

    在上一篇中,我们了解了单链表与双链表,本次将单链表中终端结点的指针端由空指针改为指向头结点,就使整个单链表形成一个环,这种头尾相接的单链表称为单循环链表,简称循环链表(circular linked list). 一.循环链表基础 1.1 循环链表节点结构 循环链表和单链表的主要差异就在于循环的判断条件上,原来是判断p.next是否为空,现在则是p.next不等于头结点,则循环未结束. 1.2 循环链表的O(1)访问时间 在单链表中,有了头结点,我们可以在O(1)时间访问到第一个节点,但如果要访

  • 《数据结构》一般线性表的合并

    一般线性表的合并 算法思想: 遍历表A和表B,查看B的每一个元素是否在A中,若不在,将B的该元素插入到A的表尾,A表的表长+1. 算法的时间复杂度和A.B的长度有关,O(m*n). //合并 void Combine(SqList &A,SqList &B){ for(int i=0;i<B.length;i++){ int count=0; for(int j=0;j<A.length;j++){ if(A.elem[j]==B.elem[i]){ count+=1; } }

  • 【数据结构】顺序存储的线性表

    马上要找工作了,最近一段时间要复习下数据结构,在此处记些复习笔记,一与读者共勉,二鼓励自己坚持下去. 顺序存储的线性表结构定义如下: typedef struct{ ElemType *elem; int length; int listsize; }SqList; 首先要申请一块儿连续的存储空间,指定长度为0. //线性表初始化 Status InitList(SqList *L) { (*L).elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(E

  • javascript实现数据结构:线性表--简单示例及线性表的顺序表示和实现

    线性表(linear list)是最常用且最简单的一种数据结构.一个线性表是n个数据元素的有限序列.在稍复杂的线性表中,一个数据元素可以由若干个数据项(item)组成. 其中: 数据元素的个数n定义为表的长度 = "list".length() ("list".length() = 0(表里没有一个元素)时称为空表) 将非空的线性表(n>=0)记作:(a[0],a[1],a[2],-,a[n-1]) 数据元素a[i](0≤i≤n-1)只是个抽象符号,其具体含义

  • 线性表2 - 数据结构和算法07

    线性表2 让编程改变世界 Change the world by program 线性表的抽象数据类型 上节课我们讲到了线性表的定义,讲到了所谓抽象数据类型就是把数据类型和相关操作捆绑在一起. 那么我们接下来分析一下,线性表应该有什么样的相关操作呢? 还是回到小甲鱼组织大家春游的例子,小甲鱼把鱼油们按照规律安排成一队,并且是长期使用这样的顺序排队,大家只需要记住自己的前驱鱼油就可以了. 那么这个考虑和安排的过程其实就是一个线性表的创建和初始化过程. 一开始小甲鱼没经验呀,把鱼油们按照名字第一个字

Tags: