[数据结构与算法]一起来学数据结构——线性表1

一些概念以及定义

1.线性表，什么是线性表？
我们去买奶茶，排着一个长长的队伍，这就是线性表。
我们上课点名，点名册从上往下一列名字这也是线性表。

2.那么线性表的概念是什么？
由零个或者多个数据元素组成的有限序列。

3.需要注意的是：
1>.是序列
2>.第一个元素无前驱，最后一个无后继，其余的都有前驱后继
3>.有限性
4>.注意零个元素也是线性表

4.抽象数据类型
概念：一组数学模型以及定义在其上的一组操作

规定的抽象数据类型的伪代码格式：

ADT 抽象数据类型名称
Data
	数据元素之间逻辑关系的定义
Operation
	操作
endADT

线性表的顺序存储结构

# include<stdio.h>


# define OK 1
# define ERROR 0
# define TRUE 1
# define FALESE 0


// status 是函数的类型，其值是函数结果的状态代码，如OK等
typedef int status;

代码实现：

    // 线性表的顺序存储结构代码
    const int Maxsize = 20;
    typedef int Elemtype;
    typedef struct
    {
        Elemtype data[Maxsize];
        int length; // 线性表当前长度
    }Sqlist;

getelem

// getelem函数
/*
list中第i个元素的值作为e返回
*/
status Getelem(Sqlist list,int i,Elemtype *e)
{
    if(list.length == 0 || list.length < i)   
    {
        return ERROR;
    } 
    *e = list.data[i - 1];
    return *e;
}

listinsert

算法思路：
1.插入位置是否合理，合理就继续，不合理就返回错误
2.表从后往前直至要插入的位置（包括插入位置），每个数据都依次向后挪动一位
3.表的长度加一

// listinsert函数
/*
list中第i个位置插入新元素e
*/
status Listinsert(Sqlist *list,int i,Elemtype e)
{
    int k ;
    if (list->length == Maxsize)
    {
        return ERROR;
    }
    if ( i < 0 || i > list->length + 1)
    {
        return ERROR;
    }
    if ( i <= list->length)
    {
        for ( int k = list->length - 1; k >= i - 1; k --)
        {
            list->data[ k + 1 ] = list->data[k];
        }
    }
    list->data[i - 1] = e; // 将新元素插入，注意这里data下标是i - 1!

    list->length ++ ; // 这一步不要忘记！

    return OK; 

}

listdelete

这里只说一个按照位置删除
思路：
1.输入删除位置，如果位置不合理就返回错误
2.将删除位置的元素返回输出，将后面的位置的所有元素向前移动一位
3.表的长度减一

//Listdelete
status Listdelete (Sqlist *list,int i,Elemtype e)
{
    if(list->length == 0) // 第一次写的时候未考虑表为空的情况
    {
        return ERROR;
    }
    else if (i <= 0 || i > list->length) // 注意这两个条件是可以并起来的
    {
        return ERROR;
    }
    e = list->data[i - 1]; 
    printf("已删除e!\n");
    for(int k = i - 1; k <= list->length - 1; k ++)
    {
        list->data[k] = list->data[k + 1];
    }
    list->length --;

    return OK;
}

看完插入和删除操作，我们可以发现两个的时间复杂度是O(n),但是在读取或存入的时候，其实际复杂度都是O(1)。

由此可见，线性表的顺序存储结构的优点：
很快的读取存入元素。
缺点：
不能确定其空间大小，空间大小不能满足需求，或是浪费，或是不够（需求总可能变多，因此数组的长度总可能不够）
插入和删除很费时间

# include<stdio.h>
# include<stdlib.h>


# define OK 1
# define ERROR 0
# define TRUE 1
# define FALESE 0


// status 是函数的类型，其值是函数结果的状态代码，如OK等
typedef int status;


// 线性表的顺序存储结构代码
const int Maxsize = 20;
typedef int Elemtype;
typedef struct
{
    Elemtype data[Maxsize];
    int length; // 线性表当前长度
}Sqlist;



// getelem函数
/*
list中第i个元素的值作为e返回
*/
status Getelem(Sqlist list,int i,Elemtype *e)
{
    if(list.length == 0 || list.length < i)   
    {
        return ERROR;
    } 
    *e = list.data[i - 1];
    return *e;
}

// listinsert函数
/*
list中第i个位置插入新元素e
*/
status Listinsert(Sqlist *list,int i,Elemtype e)
{
    int k ;
    if (list->length == Maxsize)
    {
        return ERROR;
    }
    if ( i < 0 || i > list->length + 1)
    {
        return ERROR;
    }
    if ( i <= list->length)
    {
        for ( int k = list->length - 1; k >= i - 1; k --)
        {
            list->data[ k + 1 ] = list->data[k];
        }
    }
    list->data[i - 1] = e; // 将新元素插入，注意这里data下标是i - 1!

    list->length ++ ; // 这一步不要忘记！

    return OK; 

}

//Listdelete
status Listdelete (Sqlist *list,int i,Elemtype e)
{
    if(list->length == 0) // 第一次写的时候未考虑表为空的情况
    {
        return ERROR;
    }
    else if (i <= 0 || i > list->length) // 注意这两个条件是可以并起来的
    {
        return ERROR;
    }
    e = list->data[i - 1]; 
    printf("已删除e!\n");
    for(int k = i - 1; k <= list->length - 1; k ++)
    {
        list->data[k] = list->data[k + 1];
    }
    list->length --;

    return OK;
}

// listprint函数
status Listprint(Sqlist *list)
{
    printf("list: ");
    for(int i = 0; i < list->length; i ++)
    {
        printf("%d ",list->data[i]);
    }
    printf("\n");
    return OK;
}



int main()
{
    printf("hello world!\n");
    printf("------------------------------------------------------\n");
    printf("|选择菜单：\n");
    printf("|1.插入数字\n");
    printf("|2.按照位置删除\n");
    printf("------------------------------------------------------\n");
    printf("请输入一个数字：\n");

    //初始化一个list
    Sqlist list ;
    list.length = 0;
    
    //输入操作
    while(1)
    {
        int option;
        scanf("%d",&option);
        system("cls");
        if(option == 1)
        {
            //输入1 listinsert
            //插入元素
            
            int cnt;
            printf("请输入将要插入多少个元素：\n");
            scanf("%d",&cnt);
            for(int i = 1; i <= cnt ; i ++)
            {
                int e;
                printf("请输入要插入的数字:\n");
                scanf("%d",&e);
                // printf("i = %d ,e = %d\n",i,e);
                Listinsert(&list,i,e);
                Listprint(&list);
            }
        }
        else if (option == 2)
        {
            // 输入2 listdelete
            system("cls");
            printf("请输入要删除list中的第几个数字\n");
            int deln;
            scanf("%d",&deln);
            int e = 0;
            Listdelete(&list,deln,e);
            Listprint(&list);
        }
    }

    system("pause");
    return 0;
}