精华内容
下载资源
问答
  • 有序顺序表实现集合的各种运算 用有序顺序表完成集合与集合的交集,差集,并集,包含于之间的运算以及元素与集合的判断关系
  • 有序顺序表完成集合集合的交集,差集,并集,包含于之间的运算以及元素与集合的判断关系.
  • (2)实现存储递增有序集合顺序表的建立、求交集运算; // main.cpp // 数据结构作业 // // Created by 周 on 16/10/7. // Copyright © 2016年 周. All rights reserved. //

    采用递增有序的顺序表表示集合,求解两个集合的交、并集

    1)定义顺序表的存储结构;

    2)实现存储递增有序集合的顺序表的建立、求交集运算;

    //  main.cpp

    //  数据结构作业

    //

    //  Created by on 16/10/7.

    //  Copyright © 2016 . All rights reserved.

    //


    #include <iostream>

    #include <stdio.h>

    #include <stdlib.h>

    #define LIST_INIT_SZIE 100


    //顺序表的存储结构

    typedef struct{

        int *elem;

        int length;

    }SqList;


    //构造一个空的线性表

    int InitList(SqList &l)

    {

        l.elem=(int *)malloc(LIST_INIT_SZIE *sizeof(int));

        if(!l.elem) return -1;

        l.length = 0;

        return 0;

    }


    //e返回L中第i个数据元素的值

    void GetElem(SqList l,int i,int &e)

    {

        e=l.elem[i];

    }


    //打印顺序表l中的元素

    void DispalyElem(SqList l)

    {

        for(int i=0;i<l.length;i++)

            printf("%d ",l.elem[i]);

        printf("\n");

    }


    //插入操作,l中第i个位置之前插入新的元素e

    int ListInsert(SqList &l,int i,int e)

    {

        if(i<1 || i>l.length+1) return -1;

        int *q = &(l.elem[i-1]);

        for(int *p = &(l.elem[l.length-1]);p>=q;--p)

            *(p+1) = *p;

        *q=e;

        ++l.length;

        return 0;

    }


    //删除操作,在线性表l中删除第i个元素并用e返回其值;

    int  ListDelete(SqList &l,int i,int e)

    {

        if(i<1 || i>l.length+1) return -1;

        int *p = &(l.elem[i-1]);

        e=*p;

        int *q=l.elem+l.length-1;

        for(++p;p<=q;++p)

            *(p-1)=*p;

        --l.length;

        return 0;

    }


    //查找操作,在线性表l中查找与e相同的第一个元素,并返回其下标

    int LocateElem(SqList l,int e)

    {

        int i;

        for(i=0;i<l.length;i++)

            if(l.elem[i]==e)

                return i+1;

        return 0;

    }


    /*------------函数功能:求两个线性表的交集------------*/

    void Intersection(SqList A,SqList B,SqList &C)

    {

        printf("求线性表的交集\n");

        int i,j,k=0;

        for(i=0;i<A.length;i++)

        {

            j=0;

            while(j<B.length && B.elem[j]!=A.elem[i])

                j++;

            if(j<B.length)

            {

                C.elem[k++]=A.elem[i];

            }

        }

        C.length=k;

    }


    /*------------函数功能:求两个线性表的并集------------*/

    void MergeList(SqList A,SqList B,SqList &C)

    {

        printf("求线性表的并集\n");

        int res=InitList(C);

        int i=0,j=0,k=0;//?

        int ai,bi;

        while((i<=A.length-1)&&(j<=B.length-1))

        {

            GetElem(A,i,ai);

            GetElem(B,j,bi);

            if(ai<=bi)

            {

                C.elem[k++]=A.elem[i++];

            }

            else

            {

                C.elem[k++]=B.elem[j++];

            }

        }

        while(i<=A.length-1)

        {

            GetElem(A,i,ai);

            C.elem[k++]=A.elem[i++];

        }

        while(j<=B.length-1)

        {

            GetElem(B,j,bi);

            C.elem[k++]=B.elem[j++];

        }

        C.length=k;

    }


    int main(int argc, const char * argv[]) {

        SqList A,B,C;

        int res;

        res=InitList(A);//初始化线性表A

        res=InitList(B);//初始化线性表B

        //i=InitList(C);

        printf("输入线性表A元素个数:\n");

        scanf("%d",&A.length);

        printf("输入线性表A中的元素:\n");

        for(int j=0;j<A.length;j++)

        {

            scanf("%d",&A.elem[j]);

        }

        printf("输入线性表B元素个数:\n");

        scanf("%d",&B.length);

        printf("输入线性表B中的元素:\n");

        for(int j=0;j<B.length;j++)

        {

            scanf("%d",&B.elem[j]);

        }

        Intersection(A,B,C);

        DispalyElem(C);

        MergeList(A,B,C);

        DispalyElem(C);

        return 0;

    }



    展开全文
  •  printf("请输入集合A,集合B元素的个数:\n");  scanf("%d %d", &La.length, &Lb.length);  printf("请输入集合A的元素:\n");  for (i = 0; i ; i++){  scanf("%d", &La.elem[i]);  }  printf(...

    #include<stdio.h>
    #include<stdlib.h>
    #define max 100
    typedef struct {

        int elem[max];
        int length;

    }List;
    void UnionList();
    void IntersectionList();
    void setdifferenceList();
    void DataSort(List &L, int n);
    int main(){
        UnionList();
        IntersectionList();
        setdifferenceList();
        return 0;

    }

    //并集
    void  UnionList() {
        int i, j, e;
        List La, Lb;
        printf("并集\n");
        printf("请输入集合A,集合B元素的个数:\n");
        scanf("%d %d", &La.length, &Lb.length);
        printf("请输入集合A的元素:\n");
        for (i = 0; i < La.length; i++){
            scanf("%d", &La.elem[i]);
        }
        printf("请输入集合B的元素:\n");
        for (i = 0; i < Lb.length; i++){
            scanf("%d", &Lb.elem[i]);
        }
        for (i = 0; i<Lb.length; i++)
        {
            e = Lb.elem[i];
            j = 0;
            while ((j<La.length) && (La.elem[j] != e))
                j++;
            if (j == La.length){
                La.elem[La.length] = e;
                La.length++;
            }
        }
        DataSort(La, La.length);
        for (i = 0; i<La.length; i++) {
            printf("%d ", La.elem[i]);
        }
        printf("\n");

    }

    //交集
    void IntersectionList(){
        int i, j, d = 0;
        List La, Lb, Lc;
        printf("交集\n");
        printf("请输入集合A,集合B元素的个数:\n");
        scanf("%d %d", &La.length, &Lb.length);
        printf("请输入集合A的元素:\n");
        for (i = 0; i < La.length; i++){
            scanf("%d", &La.elem[i]);
        }
        printf("请输入集合B的元素:\n");
        for (i = 0; i < Lb.length; i++){
            scanf("%d", &Lb.elem[i]);
        }
        for (i = 0; i<La.length; i++) {
            for (j = 0; j<Lb.length; j++){
                if (La.elem[i] == Lb.elem[j]){
                    Lc.elem[d++] = La.elem[i];
                    break;
                }
            }

        }
        DataSort(Lc, d);
        for (i = 0; i<d; i++) {
            printf("%d ", Lc.elem[i]);
        }
        printf("\n");
    }

    //差集
    void setdifferenceList() {
        int i, j, d = 0, c;
        List La, Lb, Lc;
        printf("差集\n");
        printf("请输入集合A,集合B元素的个数:\n");
        scanf("%d %d", &La.length, &Lb.length);
        printf("请输入集合A的元素:\n");
        for (i = 0; i < La.length; i++){
            scanf("%d", &La.elem[i]);
        }
        printf("请输入集合B的元素:\n");
        for (i = 0; i < Lb.length; i++){
            scanf("%d", &Lb.elem[i]);
        }

        for (i = 0; i<La.length; i++) {
            c = 0;
            for (j = 0; j<Lb.length; j++){
                if (La.elem[i] != Lb.elem[j]){
                    c++;
                }
            }
            if (c == Lb.length)
                Lc.elem[d++] = La.elem[i];
        }
        DataSort(Lc, d);
        for (i = 0; i<d; i++) {
            printf("%d ", Lc.elem[i]);
        }
        printf("\n");
    }

    //排序
    void DataSort(List &L, int n) {
        int i, j, temp;
        for (i = 0; i<n - 1; i++){
            for (j = i + 1; j<n; j++){
                if (L.elem[j]<L.elem[i]) {
                    temp = L.elem[j];
                    L.elem[j] = L.elem[i];
                    L.elem[i] = temp;
                }
            }
        }
    }

    展开全文
  • #include <iostream> #define MAXSIZE 100 using namespace std; typedef struct SqList { int *data; int length;... "请输入有序集合元素的个数:" << endl; cin >> m; for (i =.
    #include <iostream>
    #define MAXSIZE 100
    using namespace std;
    typedef struct SqList
    {
        int *data;
        int length;
    } SqList;
    void Input(SqList &L)
    {
        int m, i;
        cout << "请输入有序集合元素的个数:" << endl;
        cin >> m;
        for (i = 1; i <= m; i++)
        {
            cout << "请输入第【" << i << "】个元素:";
            cin >> L.data[i - 1];
            L.length++;
        }
    }
    void MergeList(SqList La, SqList Lb)
    {
        SqList Lc;
        Lc.data = new int[MAXSIZE];
        Lc.length = La.length + Lb.length;
        int *pa, *pb, *pc;
        pa = La.data;
        pb = Lb.data;
        pc = Lc.data;
        int i = 1, j = 1;
        while (i <= La.length && j <= Lb.length)
        {
            if (*pa <= *pb)
            {
                *pc++ = *pa++;
                i++;
            }
            else
            {
                *pc++ = *pb++;
                j++;
            }
        }
        while (i <= La.length)
        {
            *pc++ = *pa++;
            i++;
        }
        while (j <= Lb.length)
        {
            *pc++ = *pb++;
            j++;
        }
        cout << "合并后的集合:" << endl;
        for (i = 0; i < Lc.length; i++)
            cout << Lc.data[i] << endl;
    }
    int main()
    {
        while (1)
        {
            int F;
            SqList La, Lb;
            La.data = new int[MAXSIZE];
            La.length = 0;
            Lb.data = new int[MAXSIZE];
            Lb.length = 0;
            cout << "请输入集合A中元素的个数" << endl;
            Input(La);
            cout << endl
                 << endl;
            cout << "请输入集合B中元素的个数" << endl;
            Input(Lb);
            MergeList(La, Lb);
            cout << "\t\t\t按【0】退出" << endl;
            cout << "\t\t\t按【1】继续" << endl;
            cin >> F;
            if (F == 0)
                break;
            if (F == 1)
                continue;
        }
        return 0;
    }
    

     

    展开全文
  • 目的:使用自行设计的顺序表ADT或STL中的vector模板,设计并实现顺序表应用场合的一些简单算法设计。 应用6:假设以两个元素依值递增有序排列的线性表A和B分别表示两个集合(即同一表中的元素值各不相同),现...

    问题描述 :

    目的:使用自行设计的顺序表ADT或STL中的vector模板,设计并实现顺序表应用场合的一些简单算法设计。

     

    应用6:假设以两个元素依值递增有序排列的线性表A和B分别表示两个集合(即同一表中的元素值各不相同),现要求设计一个算法,另辟空间构成一个线性表C,其元素为A和B中元素的交集,且C中的元素也依值递增有序排列。

     

    参考函数原型:

    (1)顺序表ADT版本

    template<class ElemType>

    void Intersect_Sq_OL_C( const SqList<ElemType> &A, const SqList<ElemType> &B, SqList<ElemType> &C );

    (2)vector版本

    template<class ElemType>

    void Intersect_Sq_OL_C( const vector<ElemType> &A, const vector<ElemType> &B, vector<ElemType> &C );

     

    输入说明 :

    第一行:顺序表的数据元素类型标记(0:int;1:double;2:char;3:string;其余值:输出err)

    第二行:有序顺序表A的数据元素(数据元素之间以空格分隔)

    第三行:有序顺序表B的数据元素(数据元素之间以空格分隔)

     

    输出说明 :

    第一行:顺序表A的遍历结果(数据元素之间以“,”分隔)

    第二行:顺序表B的遍历结果(数据元素之间以“,”分隔)

    空行

    第三行:顺序表C的遍历结果(数据元素之间以“,”分隔)

     

    输入范例 :

    0
    1 3 5 7 9
    1 2 3 4 5 6 9 11

    输出范例 :

    1,3,5,7,9
    1,2,3,4,5,6,9,11

    1,3,5,9

    解题代码: 

    #include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <string>
    #include <vector>
    #include <queue>
    #include <sstream>
    #include <stack>
    #include <map>
    #include <ctime>
    #include <array>
    #include <set>
    using namespace std;
    template<class ElemType>
    void output(vector<ElemType>& A)
    {
    	int i;
    	if (A.size() == 0)
    	{
    		cout << "NULL" << endl;
    		return;
    	}
    	for (i = 0; i < A.size() - 1; i++)
    		cout << A[i] << ',';
    	cout << A[i];
    	cout << endl;
    	return;
    }
    vector<int> departString_int(string data)
    {
    	vector<int> back_part;//output type
    	int i, j;
    	vector<string> part;
    	string A_part;
    	stringstream room;
    	room.str(data);
    	while (room >> A_part)
    		part.push_back(A_part);
    	for (i = 0; i < part.size(); i++)
    	{
    		int num_cahe;
    		num_cahe = atoi(part[i].c_str());
    		back_part.push_back(num_cahe);
    	}
    	return back_part;
    }
    vector<double> departString_double(string data)
    {
    	vector<double> back_part;//output type
    	int i, j;
    	vector<string> part;
    	string A_part;
    	stringstream room;
    	room.str(data);
    	while (room >> A_part)
    		part.push_back(A_part);
    	for (i = 0; i < part.size(); i++)
    	{
    		double num_cahe;
    		num_cahe = atof(part[i].c_str());
    		back_part.push_back(num_cahe);
    	}
    	return back_part;
    }
    vector<char> departString_char(string data)
    {
    	vector<char> back_part;//output type
    	int i, j;
    	vector<string> part;
    	string A_part;
    	stringstream room;
    	room.str(data);
    	while (room >> A_part)
    		part.push_back(A_part);
    	for (i = 0; i < part.size(); i++)
    	{
    		char num_cahe;
    		num_cahe = part[i].at(0);
    		back_part.push_back(num_cahe);
    	}
    	return back_part;
    }
    vector<string> departString_string(string data)
    {
    	vector<int> back_part;//output type
    	int i, j;
    	vector<string> part;
    	string A_part;
    	stringstream room;
    	room.str(data);
    	while (room >> A_part)
    		part.push_back(A_part);
    	return part;
    }
    //===================================================
    template<class ElemType>
    void Intersect_Sq_OL_C(vector<ElemType>& A, vector<ElemType>& B)
    {
    	vector<ElemType> C;
    	int i, j=0;
    	if (A.size() > B.size())
    		A.swap(B);
    	for (i = 0; i < A.size(); i++)
    	{
    		while (A[i] > B[j] && j<B.size())
    			j++;
    		if (B[j] == A[i])
    			C.push_back(A[i]),j++;
    	}
    	output(C);
    }
    //===================================================
    int main()
    {
    	int i, j;
    	int kinds;
    	string s1, s2;
    	int m;
    	//数值类型输入判断
    	cin >> kinds;
    	if (kinds != 0 && kinds != 1 && kinds != 2 && kinds != 3)
    	{
    		cout << "err" << endl;
    		return 0;
    	}
    	cin.get();
    	vector<int> I_1, I_2;
    	vector<double> D_1, D_2;
    	vector<char> C_1, C_2;
    	vector<string> S_1, S_2;
    	//---------------
    	getline(cin, s1);
    	if (kinds == 0)
    		I_1 = departString_int(s1);
    	if (kinds == 1)
    		D_1 = departString_double(s1);
    	if (kinds == 2)
    		C_1 = departString_char(s1);
    	if (kinds == 3)
    		S_1 = departString_string(s1);
    	//--------------
    	getline(cin, s2);
    	if (kinds == 0)
    		I_2 = departString_int(s2);
    	if (kinds == 1)
    		D_2 = departString_double(s2);
    	if (kinds == 2)
    		C_2 = departString_char(s2);
    	if (kinds == 3)
    		S_2 = departString_string(s2);
    	//--------------
    	if (kinds == 0)
    		output(I_1);
    	if (kinds == 1)
    		output(D_1);
    	if (kinds == 2)
    		output(C_1);
    	if (kinds == 3)
    		output(S_1);
    	//--------------
    	if (kinds == 0)
    		output(I_2);
    	if (kinds == 1)
    		output(D_2);
    	if (kinds == 2)
    		output(C_2);
    	if (kinds == 3)
    		output(S_2);
    	//--------------
    	cout << endl;
    	//+++++++++++++++++++++++++
    	if (kinds == 0)
    		Intersect_Sq_OL_C(I_1, I_2);
    	if (kinds == 1)
    		Intersect_Sq_OL_C(D_1, D_2);
    	if (kinds == 2)
    		Intersect_Sq_OL_C(C_1, C_2);
    	if (kinds == 3)
    		Intersect_Sq_OL_C(S_1, S_2);
    	return 0;
    }

     

    展开全文
  • 注: 用有序实现。 效率高于上一个。通常情况下 ,不用整个 顺序表 扫描了   #include using namespace std; const list_size=10; const listincreament=10; typedef char datatype; typedef ...
  • 目的:使用STL中的vector模板,设计并实现顺序表应用场合的一些简单算法设计。 应用6:假设以两个元素依值递增有序排列的线性表A和B分别表示两个集合(即同一表中的元素值各不相同),现要求设计一个算法,另辟空间...
  • 跳跃是一种有序的数据结构 每个节点都维护多个指向其他节点的...跳跃在redis中用于有序集合实现。另外也用在集群节点的内部数据结构。 一、跳跃实现 zskiplist 该结构保存了跳跃节点的信息。跳跃节点...
  • (2)实现存储递增有序集合顺序表的建立、求交集运算; 2. 采用递增有序的链表表示集合,求解两个集合的交集 (1)定义链表的存储结构; (2)实现存储递增有序集合的链表的建立、求交集运算; 3. 比较顺序表...
  • (2)实现存储递增有序集合顺序表的建立、求交集、并集和差集等运算; (3)要求算法的时间性能在线性时间复杂度内; (4)和采用无序顺序表所表示的集合的有关运算的时间性能进行比较。 采用递增有序的链表...
  • 文章目录1. 跳跃实现2. 跳跃节点2.1 层2.2 前进指针2.3 跨度...Redis 使用跳跃作为有序集合键的底层实现之一: 如果一个有序集合包含的元素数量比较多, 又或者有序集合中元素的成员(member)是比较长的字符
  • 1.有序顺序表的元素按照从小到大有序存储; 2.实现有序顺序表的类模板,它的操作如下: ...3.用有序顺序表表示集合实现两个有序顺序表的并和交(并和交仍是有序顺序表)并分析它们的时间复杂度;
  • 集合A-B 顺序表

    2018-12-02 22:19:07
    有序集合是指集合中的元素有序排列。已知两个有序集合A和B,现要求一个新的有序集合C=A-B。...(3)创建A,B两个已知数据的有序顺序表,从A中的第一个数据开始循环查找B中的数据,如果B中不存在则将A中的这个数据存...
  • redis有序集合zset的底层实现——跳跃skiplist redis作为一种内存KV数据库,提供了string, hash, list, set, zset等多种数据结构。其中有序集合zset在增删改查的性质上类似于C++ stl的map和Java的TreeMap,提供了...
  • 编程实现下列功能:假设以两个元素依值非递减有序排列的顺序表A和B 分别表示两个集合(同一表中的元素值各不相同),求一个新的集合C=A-B,且表C中的元素也是依值递增有序排列。 # include <stdio.h> # ...
  • 跳跃 跳跃(skiplist)是一种有序数据结构, 它通过在每个...Redis 使用跳跃作为有序集合键的底层实现之一: 如果一个有序集合包含的元素数量比较多, 又或者有序集合中元素的成员(member)是比较长的字符...
  • 跳跃跳跃实现跳跃结点层前进指针跨度后退指针分值和成员跳跃重点 跳跃 跳跃是一种有序的数据结构,他通过在在每个结点中维护多个指向其他节点的...Redis只在两个地方使用了跳跃,一个是实现有序集合.
  • 线性结构是n个数据元素的有序集合。这个集合有以下特点: 1、集合中必存在唯一的一个"第一个元素"; 2.集合中必存在唯一的一个"最后的元素"; 3.除最后元素之外,其它数据元素均有唯一的"后继"; 4.除第一...
  • 顺序表实现和应用

    2019-06-07 22:37:57
    ⑷线性表的应用:①设线性表L1和L2分别代表集合A和B,试设计算法求A和B的并集C,并用线性表L3代表集合C;②(选做)设线性表L1和L2中的数据元素为整数,且均已按值非递减有序排列,试设计算法对L1和L2进行合并,用...
  • 数据结构(一)——顺序表实现

    千次阅读 2011-09-16 20:49:35
    先了解一下线性表,毕竟顺序表和链表都是线性表。 线性表就是有线性结构的表。什么是线性结构呢?线性结构是n个数据元素的有序集合。它有四个基本特征:  1.集合中必存在唯一的一个"第一个元素";  2...
  • 顺序表

    2019-07-18 13:56:38
    顺序表: 将元素有序的存放在一块连续的存储区里面,元素间的顺序关系由他们的存储顺序自然表示。 顺序表的基本形式 a : 每个元素所占的存储单元大小固定相同 b: 每个元素所占的存储单元大小不相同,存储一个链接...
  • ②A,B两个顺序表递增有序,执行C=AUB,算法时间复杂度要求为 O(n+m)(A,B这两个顺序表只允许遍历一次); ③//实现顺序表的就地逆置,即利用原表的存储空间将线性表(a1,...,an)逆置为(an,...,a1); ④//设A=(a1,...,...
  • 同样是有序,两者大不一样,LinkedHashMap是按照插入顺序排序,而TreeMap是按照Key的自然顺序或者Comprator的顺序进行排序。在实现原理上LinkedHashMap是双向链表,TreeMap是红黑树。TreeMap还有个好兄弟叫TreeSet,...
  • 集合对象类型本质上是采用哈希方法进行编码的,因为其保存的key都是无序的,而有序集合会为每一个key关联一个double类型的分值,基于这个分值,有序集合会对其内部存储的key按照分值从小到大的顺序进行排序。...
  • 6. 在顺序表实现两个集合的并集; 7. 归并两个非递减有序顺序表。 ` #include <iostream> #include <stdio.h> #include <stdlib.h> #include<limits.h> using namespace std; #...
  • 1.用顺序表和链表分别分别编程实现教材中例子2-1与2-2。要求: (1) 只能用C语言编程实现; (2) 完全 保持书中算法2.1 Union 与算法2.2MergeLis 形式,不允许有任何变化,除非语法上不允许;所调用各函数参照书中...
  • 有序表

    2020-10-02 08:56:00
    已知A和B均是由整型数据组成的集合,使用顺序表表示集合,设计算法求集合A、B的交集和并集,功能包括输入集合A,输入集合B,求A和B的并集,求A和B的交集。本题中, 线性表的第一个元素位置为1,线性表的最大长度为20...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 628
精华内容 251
关键字:

有序顺序表实现集合