精华内容
下载资源
问答
  • 由两个递增有序线性表A、B归并新的递减有序线性表C 数据结构题目 严蔚敏版数据结构教材题集2.24 假设有两个按元素值递增有序排列的线性表A和B,均以单链表作存储结构,请编写算法将A表和B表归并成一个按元素值递减...

    由两个递增有序线性表A、B归并新的递减有序线性表C

    数据结构题目

    严蔚敏版数据结构教材题集2.24

    假设有两个按元素值递增有序排列的线性表A和B,均以单链表作存储结构,请编写算法将A表和B表归并成一个按元素值递减有序(即非递增有序,允许表中含有值相同的元素)排列的线性表C,并要求利用原表(即A表和B表)的结点空间构造C表。

    此题的算法思想为:首先将B表连接到A表后面,即连接后的A表为新的C表,再进行递减有序的排序。

    c++代码如下:

    #include <iostream>
    #include <stdlib.h>
    using namespace std;
    
    typedef struct LNode
    {
    	int data;										//数据域
    	struct LNode *next;								//指针域 
    } LNode, *LinkList;
    
    typedef struct SListInfo
    {
    	LinkList head;									//表头结点指针
    	LinkList tail;									//表尾结点指针
    	LNode *pCurNode;								//当前结点指针位置 
    	int length;										//单链表的长度(元素个数) 
    } SListInfo;
    
    void InitList( SListInfo &L )
    {	//初始化单链表 
    	cout<<"-进行初始化操作-"<<endl;
    	L.head = (LNode *)malloc(sizeof(LNode));		//申请头结点存储空间
    	if( L.head == NULL )
    		cout<<"error1"<<endl;						//存储空间申请失败
    	L.head->next = NULL;							//头结点后无其他结点
    	L.tail = L.head;								//尾结点指针也指向头结点
    	L.pCurNode = L.head;							//当前指针也指向头结点
    	L.length = 0;									//单链表长度为零
    }	//InitList
    
    void ListTraverse( SListInfo L )
    {	//从链表的第一个元素开始,依次访问并输出链表的数据元素
    	cout<<"-输出单链表如下-"<<endl;
    	if( L.head->next == NULL )
    		cout<<"error6"<<endl;;
    	L.pCurNode = L.head->next;
    	while( L.pCurNode->next != NULL)
    	{
    		cout<<L.pCurNode->data<<endl;				//输出元素 
    		L.pCurNode = L.pCurNode->next;
    	}
    	cout<<L.pCurNode->data<<endl;					//输出表尾元素 
    }	//ListTraverse
    
    void InsertElem( SListInfo &L, int i, int e )
    {	//在第i个位置后插入新的数据元素e
    	LNode *s = (LNode *)malloc(sizeof(int));		//申请新的结点
    	if( s == NULL )
    		cout<<"error8"<<endl;;						//申请失败
    	s->data = e; 									//将e存入新结点 
    	L.pCurNode = L.head;
    	for( ; i > 0; i -- )							//找到位置i 
    	{
    		if( L.pCurNode->next == NULL)
    		{
    			cout<<"error9"<<endl;
    			break;
    		}
    		L.pCurNode = L.pCurNode->next;
    	}
    	if( L.pCurNode->next != NULL)
    	{
    		s->next = L.pCurNode->next;					//插入元素e 
    		L.pCurNode->next = s;
    		L.length += 1;								//链表长度+1 
    	}
    	else
    	{
    		L.pCurNode->next = s;
    		s->next = NULL;
    		L.length += 1;
    		L.tail = s;
    	}
    }	//InsertElem
    
    int RankList( SListInfo &L )
    {
    	LNode *p;
    	L.pCurNode = L.head->next;
    	while( L.pCurNode->next != NULL )
    	{
    		p = L.pCurNode->next;
    		while( p != NULL )											//冒泡排序(递减) 
    		{
    			if( L.pCurNode->data < p->data )
    			{
    				L.pCurNode->data = L.pCurNode->data + p->data;		//交换数值 
    				p->data = L.pCurNode->data - p->data;
    				L.pCurNode->data = L.pCurNode->data - p->data;
    			}
    			p = p->next;
    		}
    		L.pCurNode = L.pCurNode->next;
    	}
    }
    
    SListInfo newList( SListInfo &La, SListInfo &Lb )
    {	//合并A、B表为C表,并使其递减有序
    	La.tail->next = Lb.head->next;					//连接两个链表
    	La.tail = Lb.tail;								//现在的A表即为新的C表 
    	La.length = La.length + Lb.length;
    	RankList(La);									//递减排序 
    	return La;
    }	//newList
    
    int main()
    {
    	int i, n, d;
    	int &e = d;
    	SListInfo La, Lb;
    	InitList(La);
    	InitList(Lb);
    	cout<<"-请输入链表A的长度-"<<endl;
    	cin>>n;
    	cout<<"-请依次输入A表数据元素-"<<endl;
    	for( i = 0; i < n; i ++ )
    	{
    		cin>>d;
    		InsertElem(La,i,e);
    	}
    	cout<<"-请输入链表B的长度-"<<endl;
    	cin>>n;
    	cout<<"-请依次输入B表数据元素-"<<endl;
    	for( i = 0; i < n; i ++ )
    	{
    		cin>>d;
    		InsertElem(Lb,i,e);
    	}
    	La = newList(La,Lb);
    	cout<<"-输出新表如下-"<<endl;
    	ListTraverse(La);
    }
    
    展开全文
  • HNCU1324 算法2-2 有序线性表的有序合并 线性表
                   

    http://hncu.acmclub.com/index.php?app=problem_title&id=111&problem_id=1324

    题目描述

    已知线性表 LA 和 LB 中的数据元素按值非递减有序排列,现要求将 LA 和 LB 归并为一个新的线性表 LC, 且 LC 中的数据元素仍然按值非递减有序排列。例如,设LA=(3,5,8,11) ,LB=(2,6,8,9,11,15,20) 则
    LC=(2,3,6,6,8,8,9,11,11,15,20)
    算法描述如下:
    从上述问题要求可知,LC中的数据元素或是LA中的数据元素,或是LB中的数据元素,则只要先设LC为空表,然后将LA或LB中的元素逐个插入到LC中即可。为使LC中元素按值非递减有序排列,可设两个指针 i 和 j 分别指向LA和LB中某个元素,若设 i 当前所指的元素为 a,j 所指的元素为 b,则当前应插入到 LC 中的元素 c 为 c = a < b ? a : b显然,指针 i 和 j 的初值均为1(实际写代码时往往是从 0 开始的),在所指元素插入 LC 之后,在 LA 或者 LB 中顺序后移。上述归并算法如下图:
     
    图:有序列表有序插入算法

    输入格式

    有多组测试数据,每组测试数据占两行。第一行是集合A,第一个整数m0<=m<=100)代表集合A起始有m个元素,后面有m个非递减排序的整数,代表A中的元素。第二行是集合B,第一个整数n(0<=n<=100)代表集合B起始有n个元素,后面有n个非递减排序的整数,代表B中的元素。每行中整数之间用一个空格隔开。

    输出

    每组测试数据只要求输出一行,这一行含有 m+n个来自集合 A和集合B中的元素。结果依旧是非递减的。每个整数间用一个空格隔开。

    样例输入

    4 3 5 8 11
    7 2 6 8 9 11 15 20

    样例输出

    2 3 5 6 8 8 9 11 11 15 20

     

     

    #include<string.h>#include<malloc.h> /* malloc()等 */#include<stdio.h> /* EOF(=^Z或F6),NULL */#include<stdlib.h> /* atoi() */#include<math.h> /* floor(),ceil(),abs() */#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define LIST_INIT_SIZE 10 /* 线性表存储空间的初始分配量 */#define LISTINCREMENT 2 /* 线性表存储空间的分配增量 */typedef int ElemType;typedef int Status;typedef int Boolean;typedef struct{    ElemType *elem; /* 存储空间基址 */    int length; /* 当前长度 */    int listsize; /* 当前分配的存储容量(以sizeof(ElemType)为单位) */} SqList;Status InitList(SqList *L) /* 算法2.3 */{    /* 操作结果:构造一个空的顺序线性表 */    (*L).elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));    if(!(*L).elem)        exit(OVERFLOW); /* 存储分配失败 */    (*L).length=0; /* 空表长度为0 */    (*L).listsize=LIST_INIT_SIZE; /* 初始存储容量 */    return OK;}Status ListInsert(SqList *L,int i,ElemType e) /* 算法2.4 */{    /* 初始条件:顺序线性表L已存在,1≤i≤ListLength(L)+1 */    /* 操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1 */    ElemType *newbase,*q,*p;    if(i<1||i>(*L).length+1) /* i值不合法 */        return ERROR;    if((*L).length>=(*L).listsize) /* 当前存储空间已满,增加分配 */    {        newbase=(ElemType *)realloc((*L).elem,((*L).listsize+LISTINCREMENT)*sizeof(ElemType));        if(!newbase)            exit(OVERFLOW); /* 存储分配失败 */        (*L).elem=newbase; /* 新基址 */        (*L).listsize+=LISTINCREMENT; /* 增加存储容量 */    }    q=(*L).elem+i-1; /* q为插入位置 */    for(p=(*L).elem+(*L).length-1; p>=q; --p) /* 插入位置及之后的元素右移 */        *(p+1)=*p;    *q=e; /* 插入e */    ++(*L).length; /* 表长增1 */    return OK;}Status ListTraverse(SqList L,void(*vi)(ElemType*)){    /* 初始条件:顺序线性表L已存在 */    /* 操作结果:依次对L的每个数据元素调用函数vi()。一旦vi()失败,则操作失败 */    /*           vi()的形参加'&',表明可通过调用vi()改变元素的值 */    ElemType *p;    int i;    p=L.elem;    for(i=1; i<=L.length; i++)    {        if(i!=1)            printf(" ");        vi(p++);    }    printf("\n");    return OK;}int ListLength(SqList L){    /* 初始条件:顺序线性表L已存在。操作结果:返回L中数据元素个数 */    return L.length;}Status GetElem(SqList L,int i,ElemType *e){    /* 初始条件:顺序线性表L已存在,1≤i≤ListLength(L) */    /* 操作结果:用e返回L中第i个数据元素的值 */    if(i<1||i>L.length)        exit(ERROR);    *e=*(L.elem+i-1);    return OK;}void print(ElemType *c){    printf("%d",*c);}void MergeList(SqList La,SqList Lb,SqList *Lc) /* 算法2.2 */{    /* 已知线性表La和Lb中的数据元素按值非递减排列。 */    /* 归并La和Lb得到新的线性表Lc,Lc的数据元素也按值非递减排列 */    int i=1,j=1,k=0;    int La_len,Lb_len;    ElemType ai,bj;    InitList(Lc); /* 创建空表Lc */    La_len=ListLength(La);    Lb_len=ListLength(Lb);    while(i<=La_len&&j<=Lb_len) /* 表La和表Lb均非空 */    {        GetElem(La,i,&ai);        GetElem(Lb,j,&bj);        if(ai<=bj)        {            ListInsert(Lc,++k,ai);            ++i;        }        else        {            ListInsert(Lc,++k,bj);            ++j;        }    }    while(i<=La_len) /* 表La非空且表Lb空 */    {        GetElem(La,i++,&ai);        ListInsert(Lc,++k,ai);    }    while(j<=Lb_len) /* 表Lb非空且表La空 */    {        GetElem(Lb,j++,&bj);        ListInsert(Lc,++k,bj);    }}int main(){    int n,m,a[105],b[105],j;    while(~scanf("%d",&n))    {        int j;        for(j = 0; j<n; j++)            scanf("%d",&a[j]);        scanf("%d",&m);        for(j = 0; j<m; j++)            scanf("%d",&b[j]);        SqList La,Lb,Lc;        InitList(&La); /* 创建空表La */        for(j=1; j<=n; j++) /* 在表La中插入n个元素 */            ListInsert(&La,j,a[j-1]);        InitList(&Lb); /* 创建空表Lb */        for(j=1; j<=m; j++) /* 在表Lb中插入m个元素 */            ListInsert(&Lb,j,b[j-1]);        MergeList(La,Lb,&Lc);        /* 输出表Lc的内容 */        ListTraverse(Lc,print);    }    return 0;}


     

               
    展开全文
  • 有序线性表合并

    2015-04-05 18:30:31
    有序线性表的合并,用C语言来描述的,是线性表的基本操作
  • 合并有序线性表.doc

    2009-10-17 13:55:32
    合并有序线性表.doc合并有序线性表.doc合并有序线性表.doc合并有序线性表.doc
  • 这个程序的功能是将两个有序线性表合并为一个有序线性表,要求另辟空间。
  • la, lb均为非递减有序线性表 现要由la, lb构造非递减有序线性表lc 算法如下: void mergelist(list la, list lb, &list lc){ init(lc); i = j = 1; k = 0; len_a = length(la); len_b = length(lb); ...

    la, lb均为非递减有序线性表

    现要由la, lb构造非递减有序线性表lc

    算法如下:

    void mergelist(list la, list lb, &list lc){
    
    	init(lc);
    	i = j = 1;
    	k = 0;
    	len_a = length(la);
    	len_b = length(lb);
    
    	while(i <= len_a && j <= len_b){
    		get(ai);
    		get(bj);
    		if (ai <= bj){
    			insert(lc, ai, ++k);
    			i++;
    		}
    		else{
                insert(lc, bj, ++k);
    			j++;
    		}
    		
    	}
        
    	while(i <= len_a){
    		get(ai);
            insert(lc, ai, ++k);
    	}
    
    	while(j <= len_b){
    		get(bj);
            insert(lc, bj, ++k);
    	}
    
    }
    



    展开全文
  • 已知线性表 LA 和 LB 中的数据元素按值非递减有序排列, 现要求将 LA 和 LB 归并为一个新的线性表 LC, 且 LC 中 的数据元素仍然按值非递减有序排列。例如,设LA=(3,5,8,11) ,LB=(2,6,8,9,11,15,20) 则 LC=(2,3,5,6,...

    Description
    已知线性表 LA 和 LB 中的数据元素按值非递减有序排列,
    现要求将 LA 和 LB 归并为一个新的线性表 LC, 且 LC 中
    的数据元素仍然按值非递减有序排列。例如,设LA=(3,5,8,11)
    ,LB=(2,6,8,9,11,15,20) 则
    LC=(2,3,5,6,8,8,9,11,11,15,20)
    算法描述如下:
    从上述问题要求可知,LC中的数据元素或是LA中的数据元素,
    或是LB中的数据元素,则只要先设LC为空表,然后将LA或LB中
    的元素逐个插入到LC中即可。为使LC中元素按值非递减有序排列,
    可设两个指针 i 和 j 分别指向LA和LB中某个元素,若设 i 当
    前所指的元素为 a,j 所指的元素为 b,则当前应插入到 LC 中
    的元素 c 为 c = a < b ? a : b显然,指针 i 和 j 的初值均为1
    (实际写代码时往往是从 0 开始的),在所指元素插入 LC 之后,
    在 LA 或者 LB 中顺序后移
    Input
    有多组测试数据,每组测试数据占两行。第一行是集合A,第一
    个整数m(0<=m<=100)代表集合A起始有m个元素,后面有m个
    非递减排序的整数,代表A中的元素。第二行是集合B,第一个整数
    n(0<=n<=100)代表集合B起始有n个元素,后面有n个非递减排序的
    整数,代表B中的元素。每行中整数之间用一个空格隔开。
    Output
    每组测试数据只要求输出一行,这一行含有 m+n 个来自集合 A 和
    集合B 中的元素。结果依旧是非递减的。每个整数间用一个空格隔开。
    Sample Input
    4 3 5 8 11
    7 2 6 8 9 11 15 20
    Sample Output
    2 3 5 6 8 8 9 11 11 15 20

    在这里插入代码片
    #include<stdio.h>
    #include<stdlib.h>
    int insert(int *a,int *b,int *c,int n,int m,int nm)
    {
     for(int i = 0;i < n;i++)
     {
      c[i] = a[i];
     }
     for(int i = 0;i < m;i++)
     {
      c[n + i] = b[i];
     }
    }
    int comp(const void *d,const void * e)
    {
     return *(int *)d - *(int *)e;
    }
    int main(void)
    {
     int a[101],b[101],c[202],n,m,nm;
     while(scanf("%d",&n) != EOF)
     {
      for(int i = 0;i < n;i++)
      scanf("%d",&a[i]);
      scanf("%d",&m);
      nm = n + m;
      for(int i = 0;i < m;i++)
      scanf("%d",&b[i]);
      insert(a,b,c,n,m,nm);
      qsort(c,nm,sizeof(c[0]),comp);
      for(int i = 0;i < nm;i++)
      {
       printf("%d ",c[i]);
      }
      printf("\n");
     }
    }
    展开全文
  • 数据结构:有序线性表类中,返回素数表 文章目录数据结构:有序线性表类中,返回素数表一、题目描述二、设计思路1.素数的定义2.实现查找素数的方法2.1 使用数组存储+排除法2.2 直接循环实现插入3.实现返回素数表的...
  • 有序线性表指定元素的全部删除

    千次阅读 2014-05-01 18:55:31
    设计一种O(n)级算法从有序线性表中删除与给定的数据项相匹配的所有数据项。假设线性表用数组表示
  • 之前写了线性表的顺序存储结构和有序线性表的顺序存储结构以及线性表的链式存储结构,今天接着写有序线性表的链式存储结 数据结构之线性表的顺序存储结构 数据结构之有序线性表的顺序存储结构 数据结构之线性表的...
  • 已知线性表 LA 和 LB 中的数据元素按值非递减有序排列,现要求将 LA 和 LB 归并为一个新的线性表 LC, 且 LC 中的数据元素仍然按值非递减有序排列。例如,设LA=(3,5,8,11) ,LB=(2,6,8,9,11,15,20) 则 LC=(2,3,6,6,8...
  • 1324: 算法2-2:有序线性表的有序合并 时间限制: 1 Sec 内存限制: 32 MB 提交: 1583 解决: 335 题目描述 已知线性表 LA 和 LB 中的数据元素按值非递减有序排列,现要求将 LA 和 LB 归并为一个新的线性表 LC...
  • 有序线性表定义 指线性表中的元素按值或者关键字的大小先后有序(升序或者降序)。 之前讲了线性表的顺序存储结构 数据结构之线性表的顺序存储结构 有序线性表是在之前的基础上构建的,相对于之前的线性表的操作,...
  • 1324:算法2-2:有序线性表的有序合并分数: 1.5 时间限制:1 秒 内存限制:32 兆 特殊判题: 否 提交:590 解决: 113 题目描述 已知线性表 LA 和 LB 中的数据元素按值非递减有序排列...
  • 有序线性表 SortedList package list; public interface SortedList { void insert(Object obj); Object delete(Object obj); int check(Object obj); } SequenceSortedList package list; /*...
  • 1324: 算法2-2:有序线性表的有序合并题目地址点击题目描述已知线性表 LA 和 LB 中的数据元素按值非递减有序排列,现要求将 LA 和 LB 归并为一个新的线性表 LC, 且 LC 中的数据元素仍然按值非递减有序排列。...
  • 有序线性表的插入与删除#include #include # define LIST_INIT_SIZE 100 # define LISTINCREMENT 10 # define ElemType int # define OVERFLOW -1 # define ERROR -1 using namespace std; typedef struct {
  • 已知线性表 LA 和 LB 中的数据元素按值非递减有序排列,现要求将 LA 和 LB 归并为一个新的线性表 LC, 且 LC 中的数据元素仍然按值非递减有序排列。例如,设LA=(3,5,8,11) ,LB=(2,6,8,9,11,15,20) 则 LC=(2,3,6,6,8...
  • Description已知线性表 LA 和 LB 中的数据元素按值非递减有序排列,现要求将 LA 和 LB 归并为一个新的线性表 LC, 且 LC 中的数据元素仍然按值非递减有序排列。例如,设LA=(3,5,8,11) ,LB=(2,6,8,9,11,15,20) 则LC=...
  • 有序线性表的有序合并 (c语言)

    千次阅读 2018-09-22 14:21:52
    已知线性表 LA 和 LB 中的数据元素按值非递减有序排列,现要求将 LA 和 LB 归并为一个新的线性表 LC, 且 LC 中的数据元素仍然按值非递减有序排列。例如,设LA=(3,5,8,11) ,LB=(2,6,8,9,11,15,20) 则 LC=(2,3,6,6,8,...
  • 已知线性表 LA 和 LB 中的数据元素按值非递减有序排列,现要求将 LA 和 LB 归并为一个新的线性表 LC, 且 LC 中的数据元素仍然按值非递减有序排列。例如,设LA=(3,5,8,11) ,LB=(2,6,8,9,11,15,20) 则 LC=(2,3,6,6,8...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,058
精华内容 1,623
关键字:

有序线性表