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语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
122 9
|
25天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
63 16
|
25天前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
82 8
|
28天前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
54 4
|
29天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
29天前
|
存储 C语言
【数据结构】顺序表(c语言实现)(附源码)
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列,常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构,其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别,并重点介绍了动态顺序表的实现,包括初始化、销毁、打印、增删查改等操作。最后,文章总结了顺序表的时间复杂度和局限性,并预告了后续关于链表的内容。
60 3
|
29天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明
|
28天前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
41 0
|
17天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
22 1
|
4天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
25 5