首页 > 其他分享 >数据结构实验一

数据结构实验一

时间：2024-12-05 16:11:09浏览次数：4  
标签：val int h1 h2 L2 L1 实验 数据结构

数据结构实验一

2024.12.5

  1. 采用递增有序的顺序表表示集合，求解两个集合的交集、并集和差集
    （1）定义顺序表的存储结构；
    （2）实现存储递增有序集合的顺序表的建立、求交集、并集和差集等运算；
    （3）要求算法的时间性能在线性时间复杂度内；
    （4）和采用无序顺序表所表示的集合的有关运算的时间性能进行比较。
  2. 采用递增有序的链表表示集合，求解两个集合的交集、并集和差集
    （1）定义链表的存储结构；
    （2）实现存储递增有序集合的链表的建立、求交集、并集和差集等运算；
    （3）要求算法的时间性能在线性时间复杂度内；
    （4）和采用无序链表所表示的集合的有关运算的时间性能进行比较。
    3.比较顺序表和链表的优缺点和适用场合
  3. 采用顺序栈完成进制转换
    （1）定义顺序栈的存储结构；
    （2）实现顺序栈的初始化、判断是否为空、进栈、出栈等基本操作；
    （3）调用顺序栈的基本操作实现进制转换。
  4. 采用循环队列或链队列实现病人看病的模拟程序
    （1）定义队列的存储结构；
    （2）实现队列的初始化、判断是否为空、入队、出队等基本操作；
    （3）调用队列的基本操作实现病人看病模拟程序包括排队、就诊、查询、退出等功能；
    6.比较栈和队列的区别

1>

#include <stdio.h>
#include <stdlib.h>
#define bug(BUG) printf("bug::%d\n", BUG);

const int N = 1e6;
struct SqList
{
    int data[N];
    int size;
};

//  初始化
void initList(SqList *&L)
{
    L = (SqList *)malloc(sizeof(SqList)); // error sizeof(SqList *)
    L->size = 0;
}

//  输入
void input(SqList *&L, int x)
{
    L->data[L->size] = x;
    L->size++;
}

//  输出
void output(SqList *&L)
{
    for (int i = 0; i < L->size; i++)
        printf("%d ", L->data[i]);
    puts("");
}

//  销毁
void destroyList(SqList *&L)
{
    free(L);
}

//	求交集
void intersection(SqList *&L, SqList *&L1, SqList *&L2)
{
    int i = 0, j = 0;
    int n = L1->size, m = L2->size;
    for (; i < n && j < m;)
        if (L1->data[i] <= L2->data[j])
        {
            if (L1->data[i] == L2->data[j])
                input(L, L1->data[i]);
            i++;
        }
        else
            j++;
}

//  并集
void getAndSet(SqList *&L, SqList *&L1, SqList *&L2)
{
    int i = 0, j = 0;
    int n = L1->size, m = L2->size;
    for (; i < n && j < m;)
        if (L1->data[i] <= L2->data[j])
        {
            input(L, L1->data[i]);
            if (L1->data[i] == L2->data[j])
                i++, j++;
            else
                i++;
        }
        else
        {
            input(L, L2->data[j]);
            j++;
        }
    for (; i < n; i++)
        input(L, L1->data[i]);
    for (; j < m; j++)
        input(L, L2->data[j]);
}

//  差集
void getL1_L2Set(SqList *&L, SqList *&L1, SqList *&L2, SqList *&interSet)
{
    int i = 0, j = 0;
    int n = L1->size, m = interSet->size;
    for (; i < n; i++)
        if (j == m || L1->data[i] < interSet->data[j])
            input(L, L1->data[i]);
        else
            j++;
}

int main()
{
    SqList *L1, *L2;
    initList(L1);
    initList(L2);

    //  输入
    int n1, n2; // 定义两顺序表大小
    scanf("%d%d", &n1, &n2);
    for (int i = 0; i < n1; i++)
    {
        int x;
        scanf("%d", &x);
        input(L1, x);
    }
    for (int i = 0; i < n2; i++)
    {
        int x;
        scanf("%d", &x);
        input(L2, x);
    }

    //  输出
    puts("顺序表1的集合：");
    output(L1);
    puts("顺序表2的集合：");
    output(L2);

    //  交集
    SqList *interSet;
    initList(interSet);
    intersection(interSet, L1, L2);
    puts("两顺序表的交集为：");
    output(interSet);

    //  并集
    SqList *andSet;
    initList(andSet);
    getAndSet(andSet, L1, L2);
    puts("两顺序表的并集为：");
    output(andSet);

    //  差集
    SqList *L1_L2Set, *L2_L1Set;
    initList(L1_L2Set);
    initList(L2_L1Set);
    getL1_L2Set(L1_L2Set, L1, L2, interSet);
    getL1_L2Set(L2_L1Set, L2, L1, interSet);
    puts("L1-L2的差集为：");
    output(L1_L2Set);
    puts("L1-L2的差集为：");
    output(L2_L1Set);

    //  销毁
    destroyList(L1);
    destroyList(L2);
    return 0;
}

// 10 10
// 1 2 3 4 6 8 10 12 13 18
// 2 4 5 6 7 10 12 14 16 20

2>

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#define bug(BUG) std::cout << "bug::" << BUG << std::endl;
#define bug2(BUG1, BUG2) std::cout << "bug::" << BUG1 << ' ' << BUG2 << std::endl;

struct LinkNode
{
    int val;
    LinkNode *next;
};

//  初始化
void init(LinkNode *&H)
{
    H = (LinkNode *)malloc(sizeof(LinkNode));
    H->next = NULL;
}

//  尾插输入
void add(LinkNode *&H, int x)
{
    LinkNode *t = H, *s;
    while (t->next != NULL)
        t = t->next;
    init(s);
    s->val = x;
    t->next = s;
}

//  输出
void output(LinkNode *&H)
{
    LinkNode *t = H->next;
    while (t != NULL)
    {
        printf("%d ", t->val);
        t = t->next;
    }
    puts("");
}

//  销毁
void destroyList(LinkNode *&H)
{
    auto pre = H, ne = H->next;
    while (ne != NULL)
    {
        free(pre);
        pre = ne;
        ne = ne->next;
    }
    free(pre);
}

// 求交集
void intersection(LinkNode *&H, LinkNode *&H1, LinkNode *&H2)
{
    auto h1 = H1->next, h2 = H2->next;
    for (; h1 != NULL && h2 != NULL;)
    {
        if (h1->val <= h2->val)
        {
            if (h1->val == h2->val)
                add(H, h1->val);
            h1 = h1->next;
        }
        else
            h2 = h2->next;
    }
}

//  并集
void getAndSet(LinkNode *&H, LinkNode *&H1, LinkNode *&H2)
{
    auto h1 = H1->next, h2 = H2->next;
    for (; h1 != NULL && h2 != NULL;)
    {
        if (h1->val <= h2->val)
        {
            // bug2(h1->val, h2->val);
            add(H, h1->val);
            if (h1->val == h2->val)
                h2 = h2->next;
            h1 = h1->next; // 顺序error 先移动会使比较出错
        }
        else
        {
            add(H, h2->val);
            h2 = h2->next;
        }
    }
    for (; h1 != NULL; h1 = h1->next)
        add(H, h1->val);
    for (; h2 != NULL; h2 = h2->next)
        add(H, h2->val);
}

//  差集
void getL1_L2Set(LinkNode *&H, LinkNode *&H1, LinkNode *&H2, LinkNode *&interSet)
{
    LinkNode *h1 = H1->next, *h2 = interSet->next;
    for (; h1 != NULL; h1 = h1->next)
    {
        // bug2(h1->val, h2->val);
        if (h2 == NULL || h1->val < h2->val)
            add(H, h1->val);
        else
            h2 = h2->next;
        // bug2(h1->val, h2->val);
    }
}
int main()
{
    LinkNode *H1, *H2;
    init(H1);
    init(H2);

    //  输入
    int n1, n2; // 定义两顺序表大小
    scanf("%d%d", &n1, &n2);
    for (int i = 0; i < n1; i++)
    {
        int x;
        scanf("%d", &x);
        add(H1, x);
    }
    for (int i = 0; i < n2; i++)
    {
        int x;
        scanf("%d", &x);
        add(H2, x);
    }

    //  输出
    puts("链表1的集合：");
    output(H1);
    puts("链表2的集合：");
    output(H2);

    //  交集
    LinkNode *interSet;
    init(interSet);
    intersection(interSet, H1, H2);
    puts("两链表的交集为：");
    output(interSet);

    //  并集
    LinkNode *andSet;
    init(andSet);
    getAndSet(andSet, H1, H2);
    puts("两链表的并集为：");
    output(andSet);

    //  差集
    LinkNode *L1_L2Set, *L2_L1Set;
    init(L1_L2Set);
    init(L2_L1Set);
    getL1_L2Set(L1_L2Set, H1, H2, interSet);
    getL1_L2Set(L2_L1Set, H2, H1, interSet);
    puts("L1-L2的差集为：");
    output(L1_L2Set);
    puts("L1-L2的差集为：");
    output(L2_L1Set);

    //  销毁
    destroyList(H1);
    destroyList(H2);
    return 0;
}

// 10 10
// 1 2 3 4 6 8 10 12 13 18
// 2 4 5 6 7 10 12 14 16 20

3>

比较顺序表和链表的优缺点和适用场合


顺序表：
优点：
1.内存空间连续，支持随机访问，可以高效地按下标进行操作，时间复杂度是O(1)。
2. 尾插、尾删效率较高，时间复杂度是O(1)。
3. 方法简单，各种高级语言中都有数组，容易实现。
4. 不用为表示结点间的逻辑关系而增加额外的存储开销。
缺点：
1. 在顺序表中间插入或删除元素时都涉及到元素的移动，效率较低，时间复杂度为O(N)。
2. 顺序表长度固定，有时需要扩容，且需要预先分配足够大的存储空间，估计过大可能会导致顺序表后部大量闲置，预先分配过小又会造成溢出。
适用场合：
1. 线性表的长度变化不大、易于确定其大小时，适合采用顺序表作为存储结构。
2. 若线性表主要操作是查找，很少进行插入或删除操作时，适合采用顺序表作为存储结构。
3. 顺序表可以用于实现数组、哈希表中的开放地址法解决冲突的问题，还可以用于实现二分查找算法。

链表：
优点：
1. 内存空间不连续，没有空间限制，不会溢出，可以存储很多元素。
2. 如果知道要处理节点的前一个位置，则进行插入和删除的复杂度为O(1)；头插、头删的效率高，时间复杂度是O(1)。
3. 不用事先估计存储规模。
缺点：
1. 不支持随机访问，查找元素效率低，需要遍历节点，时间复杂度是O(n)。
2. 链表的存储密度较低，存储密度是指一个结点中数据元素所占的存储单元和整个结点所占的存储单元之比，链式存储结构的存储密度小于1。
适用场合：
1. 对于频繁进行插入和删除的线性表，应该使用链表作为存储结构。
2. 链表作为一种基础且常用的数据结构，在很多领域都有广泛地应用，
如操作系统中的资源管理、编译器中的符号表存储、数据库中的索引和事务日志实现等。

4>

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#define bug(BUG) std::cout << "bug::" << BUG << std::endl;
#define bug2(BUG1, BUG2) std::cout << "bug::" << BUG1 << ' ' << BUG2 << std::endl;

const int MaxSize = 1e6;
struct stack
{
    int data[MaxSize];
    int top;
};
void init(stack *&stk) // &stk必要
{
    stk = (stack *)malloc(sizeof(stack));
    stk->top = -1;
}
bool empty(stack *&stk)
{
    return stk->top == -1;
}
bool push(stack *&stk, int val)
{
    if (stk->top == MaxSize - 1)
        return false;
    stk->data[++stk->top] = val;
    return true;
}
int top(stack *&stk)
{
    return stk->data[stk->top];
}
void pop(stack *&stk)
{
    stk->top--;
}
void destroy(stack *&stk)
{
    free(stk);
}
int main()
{
    stack *stk;
    init(stk);
    int n, k; // 原始数字与需要转化的进制
    scanf("%d%d", &n, &k);

    int back_n = n;
    while (back_n)
    {
        push(stk, back_n % k);
        back_n /= k;
    }
    printf("%d转化为%d进制后为：", n, k);
    while (!empty(stk))
    {
        printf("%d", top(stk));
        pop(stk);
    }
    destroy(stk);
}

5>

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#define bug(BUG) std::cout << "bug::" << BUG << std::endl;
#define bug2(BUG1, BUG2) std::cout << "bug::" << BUG1 << ' ' << BUG2 << std::endl;

const int MaxSize = 1e6, mod = MaxSize;

struct queue
{
    int data[MaxSize];
    int head, tail;
};
void init(queue *&q)
{
    q = (queue *)malloc(sizeof(queue));
    q->head = q->tail = 0;
}
void destroy(queue *&q)
{
    free(q);
}
bool empty(queue *&q)
{
    return q->head == q->tail;
}
bool push(queue *&q, int val)
{
    if ((q->tail + 1) % mod == q->head)
        return false; // 队满 MaxSize-1个元素
    q->data[++q->tail] = val;
    return true;
}
int pop(queue *&q)
{
    q->head = (q->head + 1) % mod;
    return q->data[q->head];
}
int count(queue *&q)
{
    return (q->tail - q->head + mod) % mod;
}
int main()
{
    queue *q;
    init(q);
    //  排队
    for (int i = 1; i <= 12; i++)
        push(q, i);
    //  查询
    printf("排队人数：%d\n", count(q));
    //  就诊 退出
    while (!empty(q))
        printf("当前就诊：%d\n", pop(q));
}

6>

比较栈和队列的区别


栈是一种后进先出的数据结构。它只允许在一端（称为栈顶）进行数据的插入和删除操作。
队列队列是一种先进先出的数据结构。它允许在一端（称为队尾）进行数据的插入操作，在另一端（称为队头）进行数据的删除操作。

访问顺序
栈：数据是按照后进先出的顺序被访问的。这意味着最后添加的元素会最先被移除。
队列：数据是按照先进先出的顺序被访问的。这意味着最先添加的元素会最先被移除。
应用场景
栈：
递归实现：函数调用栈。
表达式求值：后缀表达式、中缀表达式转换为前缀表达式。
括号匹配：检查字符串中的括号是否成对出现。
路径导航：如浏览器的前进和后退功能。
队列：
任务调度：如操作系统中的任务队列。
广度优先搜索（BFS）：图遍历算法。
缓冲区管理：如打印队列、消息队列。
队列管理：如网络请求队列。

栈和队列的主要区别在于数据的访问顺序和操作方式。
栈是后进先出，适用于需要回溯的场景；队列是先进先出，适用于需要按顺序处理的场景。

标签：val,int,h1,h2,L2,L1,实验,数据结构
From： https://www.cnblogs.com/jkkk/p/18588800

相关文章

  • mysql索引概念以及索引底层数据结构
    一、什么是MySQL索引索引是数据库管理系统中一种用于提高数据检索效率的数据结构。通过在表的一个或多个列上创建索引，可以显著加快数据查询的速度，但会增加插入、删除和更新操作的开销。MySQL中索引的核心作用是快速定位数据位置，减少磁盘I/O操作，从而提高查询效率。索......
  • 实验5 c语言指针应用编程
    1#include<stdio.h>2#defineN534voidinput(intx[],intn);5voidoutput(intx[],intn);6voidfind_min_max(intx[],intn,int*pmin,int*pmax);78intmain(){9inta[N];10intmin,max;1112printf("录入%d......
  • 数据结构：顺序表详解
    1.顺序表的概念与定义2.顺序表的初始化与销毁3.顺序表的头/尾部的插入与删除4.顺序表指定位置的插入和删除4.对顺序表中的数据的查找5.总结我以过客之名，祝你前程似锦一.顺序表的概念与定义1.概念：顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是......
  • # 20222403 2024-2025-1 《网络与系统攻防技术》实验八实验报告
    1.实验内容(1)Web前端HTML能正常安装、启停Apache。理解HTML，理解表单，理解GET与POST方法，编写一个含有表单的HTML。(2)Web前端javascipt理解JavaScript的基本功能，理解DOM。在（1）的基础上，编写JavaScript验证用户名、密码的规则。在用户点击登陆按钮后回显“欢迎+输入的用户名”尝......
  • NoSQL数据库实习头歌实验知识点整理（三）-Redis部分
    文章目录1初识Redis1.1Redis简介1.1.1Redis与其他数据库的对比1.1.2Redis的特性1.2快速安装Redis与Python1.3Redis数据结构简介1.3.1Redis中的字符串1.3.2Redis中的列表1.3.3Redis中的集合1.3.4Redis中的哈希1.3.5Redis中的有序集合1.4使用Python与R......
  • c++实验五
    task1:publisher.hpp:1#pragmaonce23#include<iostream>4#include<string>56usingstd::cout;7usingstd::endl;8usingstd::string;910//发行/出版物类：Publisher（抽象类）11classPublisher{12public:13Publisher(const......
  • 今天继续补实验
    packageMain;importjava.io.IOException;importorg.apache.hadoop.conf.Configuration;importorg.apache.hadoop.hbase.HBaseConfiguration;importorg.apache.hadoop.hbase.TableName;importorg.apache.hadoop.hbase.client.Admin;importorg.apache.hadoop.hbas......
  • 数据结构（栈Stack）
    1.前言：在计算机科学中，栈（Stack）是一种基础而存在的数据结构，它的核心特性是后进先出（LIFO，LastIn,FirstOut）。想象一下，在现实生活中我们如何处理一堆托盘——我们总是将新托盘放在最上面，而取托盘时则从最上面开始，这正好与托盘的操作方式相吻合。栈的简单结构和高效的操作，使得在......
  • 实验1-5编程
    实验1floor,ceil#向下取整，向上取整a,b,c=map(int,input().split())a,b=map(int,input().split())#得到输入的去空格的int型数值,分别赋予a,bx=complex(a,b)#x用来表示一个复数,比如complex(1,2)实为1+2iwhile1:#当有输入时a,b,c=map(int,input().split())y=......
  • 实验5 继承和多态
    1.实验任务1publisher.hpp1#pragmaonce23#include<iostream>4#include<string>56usingstd::cout;7usingstd::endl;8usingstd::string;910//Publisher11classPublisher{12public:13Publisher(conststring&s=......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99