数据结构与算法(1)-顺序表

线性表的介绍

线性表是一种常用的数据结构。在实际应用中，线性表都是以栈、队列、字符串、数组等特殊线性表的形式来使用的。
特征：

1.存在唯一的一个被称做“第一个”的数据元素；
2.存在唯一的一个被称做“最后一个”的数据元素；
3.除第一个之外，集合中的每个数据元素只有一个前驱；
4.除最后一个外，集合中每个数据元素均只有一个后继

顺序表（线性表的顺序表示）

顺序表是在计算机内存中以数组的形式保存的线性表。（一般用数组表示）

• 优点：支持随机查找 可以在O(1)内查找元素
• 缺点：插入和和删除的时候，需要移动大量的元素
• 适用于需要大量访问元素的，而少量增添/删除元素的程序

顺序表的操作（C语言实现）

结构体定义

// 顺序表的大小
#define MAXSIZE 100

typedef int elemtype;
typedef struct {
    elemtype data[MAXSIZE];
    int length;
}sqlist;

顺序表的判空

/*判断线性表是否为空，返回1为空，0为不空*/
int list_empty(sqlist L)
{
    if (0 == L.length)
        return 1;
    else
        return 0;
}

查找

根据索引查找可以在O(1)的时间下找到

/*按序号查找，查找第i个元素的值（从0开始），找到返回1，将结果保存在e中，查找失败返回-1*/
int get_elem(sqlist L,int i,elemtype *e)
{
    if (i<0||i>L.length-1)
        return -1;
    *e = L.data[i];
    return i;
}

根据值查找需要遍历顺序表查找

/*按内容查找，查找线性表中值为e的元素，查找成功返回对应的序号，返回0表示失败*/
int local_elem(sqlist L, elemtype e)
{
    int i;

    for (i = 0; i < L.length; i++) {
        if (e == L.data[i])
            return i;
    }
    return 0;
}

插入操作

顺序表在进行插入操作时，需要将插入位置之后的元素都向后移动，注意要从后往前操作，不然元素会被覆盖

顺序表-插入

/*插入操作，在线性表的第i个位置插入元素e，返回1表示成功*/
int list_insert(sqlist *L,int i,elemtype e)
{
    int j;
    if (i<0||i>L->length)
    {
        printf("插入位置错误");
        return -1;
    }
    else if(L->length>=MAXSIZE)
    {
        printf("顺序表已满，不能插入元素");
        return 0;
    }
    else
    {
        for (j=L->length;j>i;j--)
        {
            L->data[j] = L->data[j-1];
        }
        L->data[i] = e;
        L->length = L->length + 1;
        return 1;
    }
}

删除操作

顺序表在进行删除操作时，需要将删除元素后面的元素往前移动，不能让删除元素的位置空着，注意要从前往后操作

顺序表-删除

/*删除线性表中第i个位置的元素*/
int list_delete(sqlist *L,int i)
{
    int j;
    if (L->length<=0)
    {
        printf("顺序表已空，不能删除！");
        return -1;
    }else if(i<0||i>L->length-1)
    {
        printf("删除位置错误！");
        return -1;
    }
    else
    {
        for (j=i;j<L->length-1;j++)
        {
            L->data[j] = L->data[j+1];
        }

        L->length = L->length - 1;
        return 1;
    }
}

插入和删除操作在最好情况下其时间复杂度为O(1)（这个元素在最后一个位置，不用移动元素），最坏情况下其时间复杂度为O(n)

顺序表的使用

#include "sqlist.h"
int main(void)
{
    sqlist La;
    int i,x;
    int n,m;//线性表长度

    init_list(&La);
    printf("请输入线性表La的长度:");
    scanf ("%d",&n);
    La.length = n;
    printf("请输入线性表La中的元素:");
    for(i=0; i<n; i++)
        scanf ("%d",&La.data[i]);

    printf("请输入要插入到线性表La中的数字x和插入的位置i:");
    scanf("%d%d",&x,&i);
    list_insert(&La,i,x);
    printf("线性表La=");
    for(i=0; i<La.length; i++)
        printf("%d ",La.data[i]);

    printf("\n请输入要删除的数字的位置:");
    scanf("%d",&i);
    list_delete(&La,i) ;
    printf("线性表La=");
    for(i=0; i<La.length; i++)
        printf("%d ",La.data[i]);

    printf("\n请输入要查找的数字:");
    scanf("%d",&x);
    printf("数字%d所在的位置为%d\n",x,local_elem(La,x));
    clean_list(&La);
    return 0;
}