顺序表,就是内存中一块连续的区域,紧密排列了若干个相同类型的数据。显然,这种设计需要事先知道同样的元素一共有多少,不然就无法开辟出合适的内存区域(即会存在浪费或者不足)。为了解决数组这种元素数量不灵活的缺点而提出的方法就是链表。链表的基本单位是节点,每个节点拥有一个数据区和一个next指针,其中数据区用于存放数据,next指针指向下一个节点。与顺序表相比,链表可以根据需要自由选择节点的数量,从而解决了内存分配不合适的问题。

但是链表并不是万能的,是否选用链表要根据实际情况进行斟酌。第一,顺序表可以随机访问其中的元素,也就是说,使用顺序表可以以一个恒定的小代价访问其中的任意一个元素,即查找的时间复杂度为O(1);链表查找其中某一个位置的特定元素则必须从头开始一个一个的沿着next指针数过去,即查找的时间复杂度为O(N)。第二,顺序表在插入和删除元素的时候需要找到特定位置的元素,然后将其后面的全部元素都向前移动或者向后移动,以填补或腾出空位,因此顺序表的插入和删除的时间复杂度都是O(N);但是链表只需要摘去或者挂上一个节点就行了,因此链表的插入和删除的时间复杂度都是O(1)。

需要掌握的基本内容:

1.顺序表查找的时间复杂度为O(1),但插入和删除的时间复杂度为O(N)。和链表刚好相反

2.九种基本运算

九种运算

零.定义顺序表的结构体

数组用指针+最大长度来定义,便于后续molloc分配长度和增加长度.

顺序表的本质是数组,但我们还需要知道有效长度,便于后续的判断,插入删除等操作,因而需要还参数length.

typedef struct
{
    int * data;     //存数组第一个元素的地址
    int listSize;   //数组最大长度
    int length;     //有效长度
}SqList;

一.初始化顺序表InitList

动态分配空间

void InitList(SqList * L)
{
    L->data = (int *)malloc(sizeof(int) * MaxSize);    //调用molloc动态分配
    L->listSize = MaxSize;    //在前面自己定义想要的长度:#define MaxSize 10
    L->length = 0;    
}

//"动态"的体现——可以增加动态数组的长度
void IncreaseSize(SqList * L,int len)
{
    int *p = L->data;
    L->data = (int *)malloc(sizeof(int) * (L->listSize+len));  //关键:+len
    for(int i=0;i<L->length;i++)
        L->data[i] = p[i];    //将数据复制到新开辟的区域
    L->listSize = MaxSize + len;   //调整增长后的长度
    free(p);
}

可以实现了数组长度增长,但每次增长数组长度时,都要复制原空间的元素,时间复杂度高。

二.插入ListInsert

bool ListInsert(SqList * L,int i,int e)
{
    if(i<1 || i>L->length+1)   //注意:是大于长度+1
        return false;
    else
    {
        i--;    //逻辑序号转化为物理序号
        for(int j = L->length; j > i; j--)
        {
            L->data[j] = L->data[j-1];  //后移
        }
        L->data[i] = e;   //插入
        L->length ++;
        return true;
    }
}

注:超过最大长度范围时i > L->length + 1,因为i和L->length一样,都是从1开始,因此i可以是L->length+1的位置(在最后一位的后面插入),因此范围是大于L->length + 1 , 而不是大于L->length

实际在插入时,我们一般还需要判断分配的空间是否已满,满的话使用增加动态数组长度的方法添加长度,但在平时学习和考试时,不要求写。

三.删除数据元素ListDelete

和插入的逻辑一摸一样,就几处有细微的区别。

bool ListDelete(SqList * L,int i,int * e)   //e用于返回删除的元素
{ 
    if(i<1 || i>L->length)   //区别1,插入是i > L->length + 1
        return false;
    else
    {
        i--;
        * e = L->data[i];
        for(int j = i; j < L->length ; j++)  //区别2
            {
            L->data[j] = L->data[j+1];      //区别3
            }
        L->length --;     //区别4
        return true;
    }
}

四.判断是否为空ListEmpty

bool ListEmpty(SqList * L)
{
    if(L->length == 0)   
        return true;
    else
        return false;
}
//也可以直接写:return (L->length==0)

五.求长度ListLength

int ListLength(SqList * L)
{
    return(L->length);
}

六.遍历输出顺序表DispList

void DispList(SqList * L)
{
    for(int i=0;i<L->length;i++)
    {
        printf("%d ",L->data[i]);    // L->data[i] 等价于 *(L->data + i)
    }
    printf("\n ");
}

七.按元素值查找LocateElem

int LocateElem(SqList * L, int e)
{
    for(int i=0;i<L->length;i++)
    {
        if(L->data[i] == e)
            return (i+1);
    }
    return -1;
}

八.按逻辑序号查找GetElem

int GetElem(SqList * L, int i)
{
    if(i<1 || i>L->length)
        return 0;
    else
        return L->data[i-1];
}

九.销毁顺序表DestroyList

void DestroyList(SqList * L)
{
    free(L);
}

总代码

1.九种运算总代码

typedef struct
{
    int * data;     //数组第一个元素的地址
    int listSize;   //数组最大长度
    int length;     //有效长度
}SqList;


void InitList(SqList * L)
{
    L->data = (int *)malloc(sizeof(int) * MaxSize);    //调用molloc动态分配
    L->listSize = MaxSize;    //在前面自己定义想要的长度:#define MaxSize 10
    L->length = 0;
}


bool ListInsert(SqList * L,int i,int e)
{
    if(i<1 || i>L->length+1)    //注意:是大于长度+1
        return false;
    else
    {
        i--;    //逻辑序号转化为物理序号
        for(int j = L->length; j > i; j--)
        {
            L->data[j] = L->data[j-1];  //后移
        }
        L->data[i] = e;   //插入
        L->length ++;
        return true;
    }
}


bool ListDelete(SqList * L,int i,int * e)   //e用于返回删除的元素
{
    if(i<1 || i>L->length)    //区别1
        return false;
    else
    {
        i--;
        * e = L->data[i];
        for(int j = i; j < L->length ; j++)  //区别2
            {
            L->data[j] = L->data[j+1];      //区别3
            }
        L->length --;     //区别4
        return true;
    }
}


bool ListEmpty(SqList * L)
{
    if(L->length == 0)
        return true;
    else
        return false;
}
//也可以直接写:return (L->length==0)


int ListLength(SqList * L)
{
    return(L->length);
}


void DispList(SqList * L)
{
    for(int i=0;i<L->length;i++)
    {
        printf("%d ",*(L->data + i));    // L->data[i] 等价于 *(L->data + i)
    }
    printf("\n ");
}


int LocateElem(SqList * L, int e)
{
    for(int i=0;i<L->length;i++)
    {
        if(L->data[i] == e)
            return (i+1);
    }
    return -1;
}


int GetElem(SqList * L, int i)
{
    if(i<1 || i>L->length)
        return 0;
    else
        return L->data[i-1];
}

2.测试

调用代码

int main()
{
    SqList L;
    InitList(& L);
    printf("%s","-----给第一到第四个元素赋值1-4 -----\n");
    ListInsert(& L,1,1);
    ListInsert(& L,2,2);
    ListInsert(& L,3,3);
    ListInsert(& L,4,4);
    DispList(&L);

    printf("%s","-----给第二个元素插入9 -----\n");
    ListInsert(& L,2,9);
    DispList(&L);

    printf("%s","-----删除第三个元素:3 -----\n");
    int e = 0;
    ListDelete(& L,3,&e);
    printf("删除的元素是:%d\n",e);
    DispList(&L);

    printf("%s","-----查找元素9所在的位置 -----\n");
    printf("元素9在:第%d个\n",LocateElem(& L,9));

    printf("%s","-----查找第二个数的值 -----\n");
    printf("第二个数是:%d\n",GetElem(& L,2));
}

运行结果