C语言手撕数据结构代码_顺序表_静态存储_动态存储

简介: 本文介绍了基于静态和动态存储的顺序表操作实现,涵盖创建、删除、插入、合并、求交集与差集、逆置及循环移动等常见操作。通过详细的C语言代码示例,展示了如何高效地处理顺序表数据结构的各种问题。
顺序表基于静态存储习题
1.创建一个顺序表
2.从顺序表中删除第i个元素
3.在第i个元素前插入e
4.从顺序表中删除最小元素,空出的位置由最后一个元素填补
5.在无序顺序表中删除值在s和t之间的所有元素
6.在非递减顺序表中删除值在区间[s,t]的所有元素
7.删除非递减顺序表中的重复元素
顺序表基于动态存储习题
8.顺序表A和B的元素个数分别为m和n,表A升序,表B降序排序,两个表中都不在相同的元素
8.1 将两表合并,两表中的元素存储到表C中(c表保持升序)
8.2 表A前r个元素递增有序,而表A中后n-r个元素递减有序,将表A进行升序排序
9.给定两个非空集合A和B,分别用升序顺序表La和Lb存储,设计算法求解交集
10.给定两个非空集合A和B,分别用升序顺序表La和Lb存储,设计算法求解A-B(差集)
11.设计算法算法逆置顺序表
12.将序列L循环左移动

1.创建一个顺序表

// 本程序为顺序表模版
#include <iostream>
#define MAX_SIZE 100 //确定顺序表总的空间大小为100
typedef int ElemType;
typedef struct sqlist
{
   
    ElemType list[MAX_SIZE];
    int length; //记录表长
}sqlist;

void print_list(sqlist a)
{
   
    for (int i=0; i<a.length; i++) {
   
        printf("%d->",a.list[i]);
    }
}
int main() {
   
    sqlist a;
    a.length=0; //初始化单链表表长为7
    for(int i=0;i<=6;i++)
    {
   
        a.list[i]=i+1;
        a.length++;
    }     //定义一个 1,2,3,4,5,6,7的顺序表

    printf("检查顺序表的第一个元素:%d\n当前顺序表的表长为:%d\n",a.list[0],a.length);
    printf("--------打印读入链表-----------\n");
    print_list(a);printf("\n");
    printf("-----------------------------\n");
    return 1;
}

2.从顺序表中删除第i个元素

void delete_i(sqlist &a,int x)
{
   
    for(int i=x;i<a.length;i++)
    {
   
        a.list[i-1]=a.list[i];
    }
    a.list[a.length-1]=0;//清空最后一个值的数据
    a.length--;
}

3.在第i个元素前插入e

void insert_i(sqlist &a,int x,int e)
{
   
    for(int i=a.length;i>=x;i--)
    {
   
        a.list[i]=a.list[i-1];
    }
    a.list[x-1]=e;
    a.length++;
}

4.从顺序表中删除最小元素,空出的位置由最后一个元素填补

void delete_min(sqlist &a)
{
   
    int min=100000;
    int flag=0;
    for(int i=0;i<a.length;i++)
    {
   
        if(a.list[i]<min)
        {
   
            min=a.list[i];
            flag=i;
        }
    }
    a.list[flag]=a.list[a.length-1];
    a.length--;
}

5.在无序顺序表中删除值在s和t之间的所有元素

void deleteElem(sqlist &a,int s,int t)
{
   
    int curlength=0;//指向表头的指针,同时也记录着新表的长度
    for(int i=0;i<a.length;i++)
    {
   
        if(a.list[i]<s||a.list[i]>t)
        {
   
            a.list[curlength++]=a.list[i];
        }
    }
    a.length=curlength;
}

6.在非递减顺序表中删除值在区间[s,t]的所有元素

从前后找到第一个s,从后往前找到最后一个t,将t后面加入到第一个s前面

//在无序顺序表中删除s和t之间的所有元素
void delete_st(sqlist &a,int s,int t)
{
   
    int first_s=0;
    int last_t=0;
    int curlength1=0; //记录s前新表长度
    int curlength2=0; //记录t后新表长度

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

        if(a.list[i]>=s)
        {
   
            first_s=i;
            break;
        }else curlength1++;

    }

    for(int j=a.length-1;j>=0;j--)
    {
   
        if(a.list[j]<=t)
        {
   
            last_t=j;
            break;
        }else curlength2++;
    }
    for(int i=first_s,j=last_t+1;j<a.length;j++,i++)
    {
   
        a.list[i]=a.list[j];
    }
    a.length=curlength1+curlength2;
    printf("length=%d\n",a.length);
}

7.删除非递减顺序表中的重复元素

思想:新表表尾和旧表元素不同时,加入新表

void delete_repeat(sqlist &a)
{
   
    int curlength=0;
    for(int i=1;i<a.length;i++)
    {
   
        if(a.list[curlength]!=a.list[i])
        {
   
            a.list[++curlength]=a.list[i];
        }
    }
    a.length=curlength+1; //长度=下标+1
}

从第8题开始,存储方式改为动态存储


8.顺序表A和B的元素个数分别为m和n,表A升序,表B降序排序,两个表中都不在相同的元素

关于动态存储顺序表

typedef int ElemType;
typedef struct SqList
{
   
    ElemType *PList;
    int length;
    int listSize;
}SqList;

8.1 将两表合并,两表中的元素存储到表C中(c表保持升序)

void combine(sqList &a,sqlist &b,sqlist &c)
{
   
    c.length=a.length+b.length;
    c.list=(ElemType *)malloc(sizeof(ElemType)*c.length);
    int curlength=0;
    int index_a=0; //指向a第一个元素的指针
    int index_b=b.length-1; //指向b最后一个元素的指针
    while(index_a<a.length&&index_b>=0)
    {
   
        if(a.list[index_a]<b.list[index_b])
        {
   
            //把a加入c
            c.list[curlength++]=a.list[index_a];
            index_a++;
        }else{
   
            //把b加入c
            c.list[curlength++]=b.list[index_b];
            index_b--;
        }
    }
    //把a或b中的剩余元素加入c中
    while(index_a<a.length)
    {
   
        c.list[curlength++]=a.list[index_a];
        index_a++;
    }
    while(index_b>=0)
    {
   
        c.list[curlength++]=b.list[index_b];
        index_b--;
    }
}

8.2 表A前r个元素递增有序,而表A中后n-r个元素递减有序,将表A进行升序排序

一直以最后一个元素为目标,依次的插入进前面的递增序列。不断更新最后一个元素。

void combine_a(sqList &a ,int k)
{
   
            for(int i=0;i<a.length-1;i++)
            {
   
                if(a.list[a.length-1]<=a.list[i])
                {
   
                    int temp=a.list[a.length-1];
                    for(int j=a.length-1;j>i;j--)//包括i在内的所有元素后移
                    {
   
                        a.list[j]=a.list[j-1];
                    }
                    a.list[i]=temp;
                }
            }
}

9.给定两个非空集合A和B,分别用升序顺序表La和Lb存储,设计算法求解交集

解析:

分别设置两个指针指向两个集合开头,若集合A开头元素小于B集合开头元素,则说明B集合的其他元素都大于A,故A后移一位,反之B后移一位,每当相等的时候,加入交集,同时A和B同时后移一位,直到其中一个表为空时,退出循环。在a表中存储交集

设计样例:
A:1 2 5 7 9 15
B:0 4 5 7 8 9

输出:应为 5 7 9
代码如下:

void jiaoji(sqList &a,sqlist &b)
{
   
    int curlength=0;
    int index_a=0;
    int index_b=0;
    while (index_a<a.length||index_b<b.length) {
   
        if(a.list[index_a]<b.list[index_b])
        {
   
            index_a++;
        }
        else if(a.list[index_a]==b.list[index_b])
        {
   
            a.list[curlength++]=a.list[index_a];
            index_a++;
            index_b++;
        }else{
   
            index_b++;
        }

    }
    a.length=curlength;
}

10.给定两个非空集合A和B,分别用升序顺序表La和Lb存储,设计算法求解A-B(差集)

解析:

每次将A小于的元素加入进差集当中
设计样例:
A:1 2 5 7 9 15
B:0 4 5 7 8 9

输出:应为 1 2 15
代码如下:

void chaji(sqList &a,sqlist &b)
{
   
    int curlength=0;
    int index_a=0;
    int index_b=0;
    while (index_a<a.length||index_b<b.length) {
   
        if(a.list[index_a]<b.list[index_b])
        {
   
            a.list[curlength++]=a.list[index_a++];
        }
        else if(a.list[index_a]==b.list[index_b])
        {
   
            index_a++;
            index_b++;
        }else{
   
            index_b++;
        }

    }

    while (index_a<a.length) {
    //如果b短,将a中剩余的元素加入
        a.list[curlength++]=a.list[index_a++];
    }
    a.length=curlength;

}

11.设计算法算法逆置顺序表

void reverse(sqList &a)
{
   
    int low=0;
    int high=a.length-1;
    while (low<high) {
   
        int temp=a.list[low];
        a.list[low++]=a.list[high];
        a.list[high--]=temp;
    }
}

12.将序列L循环左移动

解析:使用三次逆置

void r_reverse(sqList &a,int low,int high)
{
   
    while (low<high) {
   
        int temp=a.list[low];
        a.list[low++]=a.list[high];
        a.list[high--]=temp;
    }
}
void ROL(sqList &a,int r)
{
   
    r_reverse(a,0,r-1);
    r_reverse(a,r,a.length-1);
    r_reverse(a, 0,a.length-1);
}
相关文章
|
26天前
|
存储 编译器 C语言
C语言存储类详解
在 C 语言中,存储类定义了变量的生命周期、作用域和可见性。主要包括:`auto`(默认存储类,块级作用域),`register`(建议存储在寄存器中,作用域同 `auto`,不可取地址),`static`(生命周期贯穿整个程序,局部静态变量在函数间保持值,全局静态变量限于本文件),`extern`(声明变量在其他文件中定义,允许跨文件访问)。此外,`typedef` 用于定义新数据类型名称,提升代码可读性。 示例代码展示了不同存储类变量的使用方式,通过两次调用 `function()` 函数,观察静态变量 `b` 的变化。合理选择存储类可以优化程序性能和内存使用。
140 82
|
11天前
|
存储 Java
java数据结构,线性表链式存储(单链表)的实现
文章讲解了单链表的基本概念和Java实现,包括头指针、尾节点和节点结构。提供了实现代码,包括数据结构、接口定义和具体实现类。通过测试代码演示了单链表的基本操作,如添加、删除、更新和查找元素,并总结了操作的时间复杂度。
java数据结构,线性表链式存储(单链表)的实现
|
12天前
|
安全 C语言
在C语言中,正确使用运算符能提升代码的可读性和效率
在C语言中,运算符的使用需要注意优先级、结合性、自增自减的形式、逻辑运算的短路特性、位运算的类型、条件运算的可读性、类型转换以及使用括号来明确运算顺序。掌握这些注意事项可以帮助编写出更安全和高效的代码。
25 4
|
27天前
|
存储 人工智能 C语言
数据结构基础详解(C语言): 栈的括号匹配(实战)与栈的表达式求值&&特殊矩阵的压缩存储
本文首先介绍了栈的应用之一——括号匹配,利用栈的特性实现左右括号的匹配检测。接着详细描述了南京理工大学的一道编程题,要求判断输入字符串中的括号是否正确匹配,并给出了完整的代码示例。此外,还探讨了栈在表达式求值中的应用,包括中缀、后缀和前缀表达式的转换与计算方法。最后,文章介绍了矩阵的压缩存储技术,涵盖对称矩阵、三角矩阵及稀疏矩阵的不同压缩存储策略,提高存储效率。
|
27天前
|
C语言
数据结构基础详解(C语言):图的基本概念_无向图_有向图_子图_生成树_生成森林_完全图
本文介绍了图的基本概念,包括图的定义、无向图与有向图、简单图与多重图等,并解释了顶点度、路径、连通性等相关术语。此外还讨论了子图、生成树、带权图及几种特殊形态的图,如完全图和树等。通过这些概念,读者可以更好地理解图论的基础知识。
|
29天前
|
存储 算法 C语言
C语言手撕实战代码_二叉排序树(二叉搜索树)_构建_删除_插入操作详解
这份二叉排序树习题集涵盖了二叉搜索树(BST)的基本操作,包括构建、查找、删除等核心功能。通过多个具体示例,如构建BST、查找节点所在层数、删除特定节点及查找小于某个关键字的所有节点等,帮助读者深入理解二叉排序树的工作原理与应用技巧。此外,还介绍了如何将一棵二叉树分解为两棵满足特定条件的BST,以及删除所有关键字小于指定值的节点等高级操作。每个题目均配有详细解释与代码实现,便于学习与实践。
|
29天前
|
存储 算法 C语言
C语言手撕实战代码_二叉树_构造二叉树_层序遍历二叉树_二叉树深度的超详细代码实现
这段代码和文本介绍了一系列二叉树相关的问题及其解决方案。其中包括根据前序和中序序列构建二叉树、通过层次遍历序列和中序序列创建二叉树、计算二叉树节点数量、叶子节点数量、度为1的节点数量、二叉树高度、特定节点子树深度、判断两棵树是否相似、将叶子节点链接成双向链表、计算算术表达式的值、判断是否为完全二叉树以及求二叉树的最大宽度等。每道题目均提供了详细的算法思路及相应的C/C++代码实现,帮助读者理解和掌握二叉树的基本操作与应用。
|
29天前
|
存储 算法 C语言
C语言手撕实战代码_循环单链表和循环双链表
本文档详细介绍了用C语言实现循环单链表和循环双链表的相关算法。包括循环单链表的建立、逆转、左移、拆分及合并等操作;以及双链表的建立、遍历、排序和循环双链表的重组。通过具体示例和代码片段,展示了每种算法的实现思路与步骤,帮助读者深入理解并掌握这些数据结构的基本操作方法。
|
29天前
|
算法 C语言 开发者
C语言手撕实战代码_单链表
本文档详细介绍了使用C语言实现单链表的各种基本操作和经典算法。内容涵盖单链表的构建、插入、查找、合并及特殊操作,如头插法和尾插法构建单链表、插入元素、查找倒数第m个节点、合并两个有序链表等。每部分均配有详细的代码示例和注释,帮助读者更好地理解和掌握单链表的编程技巧。此外,还提供了判断子链、查找公共后缀等进阶题目,适合初学者和有一定基础的开发者学习参考。
|
11天前
|
存储 Java
java数据结构,线性表顺序存储(数组)的实现
文章介绍了Java中线性表顺序存储(数组)的实现。线性表是数据结构的一种,它使用数组来实现。文章详细描述了线性表的基本操作,如增加、查找、删除、修改元素,以及其他操作如遍历、清空、求长度等。同时,提供了完整的Java代码实现,包括MyList接口和MyLinearList实现类。通过main函数的测试代码,展示了如何使用这些方法操作线性表。