顺序表

基本操作（创建，插入，删除，查找）

#include<iostream>
using namespace std;

#define Maxsize 50
typedef struct
{
    int data[Maxsize]={0};
    int length=0;
}List;

//插入
bool List_insert(List &L,int i,int num)
{
    if(i<1||i>L.length+1)
        return false;
    if(L.length>=Maxsize)
        return false;

    for(int j=L.length;j>=i;j--)
    {
        L.data[j]=L.data[j-1];
    }

    //这个地方我们输入的i是从1开始的，但是数组是从0开始的，所以i-1
    L.data[i-1]=num;
    L.length++;
    return true;
}

//将该位置被删除的数返回同时删除
int List_Delete(List &L,int i)
{
    if(i<1||i>L.length+1)
        return 0;

    int p=L.data[i-1];

    for(int j=i;j<L.length;j++)
    {
        //这里就是把删除的数的后面的数往前移动
        L.data[j-1]=L.data[j];
    }   
    L.length--;
    return p;
}

//查找某一数值是否存在
int List_locate(List &L,int num)
{
    int i=0;
    for(i=0;i<L.length;i++)
    {
        if(L.data[i]==num)
            return i+1;
    }
    return 0;
}

​ 接下来我们调用一下这些函数，实现一下。

int main()
{
    List sqlist;
    List_insert(sqlist,1,10);
    List_insert(sqlist,2,30);
    List_insert(sqlist,3,25);
    List_insert(sqlist,4,90);
    List_insert(sqlist,5,2);
    List_insert(sqlist,6,138);
    List_insert(sqlist,7,8);

    //输出表的长度并且遍历
    cout<<sqlist.length<<endl;
    for(int i=0;i<sqlist.length;i++)
    {
        cout<<sqlist.data[i]<<"   ";
    }
    cout<<endl;

    //按值查找
    int temp=List_locate(sqlist,139);
    if(temp==0)
        cout<<"The value you are looking for does not exist"<<endl;
    else
        cout<<"the value you are looking for does exist"<<temp<<endl;

    //删除某个值,按位置（从1开始的）删除
    int p=List_Delete(sqlist,2);
    cout <<"the value you delete is :"<< p << endl;

    return 0;
}

王道课后习题

//删除顺序表中最小的元素,该函数为P17-1(2022)
//删除顺序表中最小的元素,该函数为P18-1(2023)
int List_Del_Min(List &L)
{
    if(L.length==0)
        return 0;

    //temp的作用是存放当前最小的值
    //我们把表的数都遍历一遍，用temp存放最小值
    int temp=99999,j=0;
    for(int i=0;i<L.length-1;i++)
    {
        if(temp>=L.data[i])
        {
            temp=L.data[i];
            j=i;
        }
    }
    //空出的位置由最后一个元素补上
    //当然啦，你要是找到了最小的元素你也可以调用List_Delete函数
    L.data[j]=L.data[L.length-1];
    L.length--;
    return temp;
}

//顺序表逆置，高效算法，空间复杂度O（1），P17-2(2022)
//顺序表逆置，高效算法，空间复杂度O（1），P17-2(2023)
bool List_reverse(List &L)
{
    int temp=0;
    int j=L.length-1;
    for(int i=0;i<L.length/2;i++)
    {
        temp=L.data[i];
        L.data[i]=L.data[j-i];
        L.data[j-i]=temp;
    }
}

//删除线性表中所有值为X的数据元素，P17-3(2022)
//删除线性表中所有值为X的数据元素，P17-3(2023)
void List_Del_x(List &L,int x)
{
    int k=0;
    for(int i=0;i<L.length;i++)
    {
        if(L.data[i]!=x)
        {
            L.data[k]=L.data[i];
            k++;
        }
    }

    L.length=k;
}

lionの金库