线性表的顺序实现

1.线性表的定义与基本操作

1）定义

具有相同类型数据的有限序列（有次序）。表长、空表、位序（是线性表中第几个元素,从1开始）

2）基本操作

初始化:InitList(&L)；

增加元素:ListInsert(&L,i,e);

删除元素:LisDelete(&L,i,&e);//用e返回删除元素的值,要把数据“带回来”，传地址，其实也可以传e，用return语句带回来

销毁:DestroyList(&L);

按值查找:LacateElem(L,e);

按位查找:GetElem(L,i);

输出:PrintList(L);

判空:Empty(L);
.线性表的顺序表示

1）顺序表的定义

顺序存储实现的线性表。第一个a1元素位置，LOC(L);后续元素ai位置，LOC(L)+(i-1)*sizeof(ElemType)。

2）顺序表的实现

静态分配：

#define MaxSize 50
typedef struct{
    int data[MaxSize];
    int length;
}SqlList;

void InitList(SqlList &L)
{
    int i;
    for(i=0;i<L.length;i++) L.data[i]=0;
    L.length=0;
}

int main(void)
{
    SqlList L;
    InitList(L);
    int i;
    for(i=0;i<L.length;i++)printf("%d ",L.data[i]);
    return 0;
}

动态分配：

#include<stdio.h>
#include<stdlib.h>
#define InitSize 4 //默认长度
typedef struct{
    int * data;
    int MaxSize;
    int length;
}SeqList;

void InitList(SeqList &L)
{
    L.data=(int *)malloc(InitSize*sizeof(int));
    L.length=0;
    L.MaxSize=InitSize;
}

void IncreaseSize(SeqList &L,int len)
{
    int * p=L.data;
    L.data=(int *)malloc((L.MaxSize+len)*sizeof(int));
    for(int i=0;i<L.MaxSize;i++) L.data[i]=p[i];
    free(p);
    L.MaxSize=L.MaxSize+len;
}
int main(void)
{
    SeqList L;
    InitList(L);
    //这种插入数据的方式不规范，并没有改变length
    L.data[0]=1;
    L.data[1]=2;
    L.data[2]=3;
    L.data[3]=4;
    for(int i=0;i<L.MaxSize;i++) printf("a[%d]=%d,",i,L.data[i]);
    printf("\n");
    IncreaseSize(L,3);
    for(int i=0;i<L.MaxSize;i++) printf("a[%d]=%d,",i,L.data[i]);
    return 0;
}

3）顺序表的四大特点

可以随机访问。

存储密度高，只需存数据，不需存指针。

扩展容量不方便，静态分配无法扩展，动态分配需要把存储的内容复制到新分配的区域。

插入、删除效率低。

4）顺序表的基本操作

插入

#include<stdio.h>
#include<stdlib.h>
#define InitSize 10

typedef struct{
int * data;
int length;
int MaxSize;
}SeqList;

void InitList(SeqList &L)
{
    int i=0;
    L.data=(int *)malloc(InitSize*sizeof(int));
    for(i=0;i<L.MaxSize;i++)L.data[i]=0;
    L.length=0;
    L.MaxSize=InitSize;
}

bool ListInsert(SeqList &L,int i,int e)//i是位序,不是数组下标
{
    if(i<1||i>L.length+1) return false;
    if(i>L.MaxSize) return false;
    int j;
    for(j=L.length;j>=i;j--)
        L.data[j]=L.data[j-1];  //1
    L.data[i-1]=e;
    L.length++;
    return true;
}


int main(void)
{
    SeqList L;
    InitList(L);
    ListInsert(L,1,1);
    ListInsert(L,2,2);
    ListInsert(L,3,3);
    for(int i=0;i<L.length;i++)printf("data[%d]=%d,",i,L.data[i]);
    printf("\n");
    ListInsert(L,1,0);
    for(int i=0;i<L.length;i++)printf("data[%d]=%d,",i,L.data[i]);
    return 0;
}

最优时间复杂度：O（1），即插入到表尾——位序n+1处，不需要执行最深层的for循环（1处）；

最坏时间复杂度：O（n），插入到表头——位序为1处，最深层for循环执行n次；

平均复杂度：O（n），每个位序插入的可能性是1/（n+1）,(0+1+...+n)/(n+1)=n*(n+1)/2 /(n+1)=n/2;

删除

#include <stdio.h>
#include <stdlib.h>
#define InitSize 10

typedef struct{
int * data;
int MaxSize;
int length;
}SeqList;

void InitList(SeqList &L)
{
    int i;
    L.data=(int *)malloc(InitSize*sizeof(int));
    L.MaxSize=InitSize;
    for(i=0;i<L.MaxSize;i++) L.data[i]=0;
    L.length=0;
}

bool ListInsert(SeqList &L,int i,int e)
{
    int j;
    if(i<1||i>L.length+1)return false;
    if(i>L.MaxSize)return false;
    for(j=L.length;j>=i;j--)
        L.data[j]=L.data[j-1];
    L.data[i-1]=e;
    L.length++;
    return true;
}
//按位删除
bool ListDelete(SeqList &L,int i,int &e) //此处传入的参数i是位序为i的元素，即删除对应下标为i-1的元素
{
    if(i<1||i>L.length)return false;
    e=L.data[i-1]; 
    int j;
    for(j=i;j<L.length;j++)
        L.data[j-1]=L.data[j];
    L.length--;
    return true;
}

int main(void)
{
    int e=-1;
    SeqList L;
    InitList(L);
    ListInsert(L,1,1);
    ListInsert(L,2,2);
    ListInsert(L,3,3);
    for(int i=0;i<L.length;i++)printf("data[%d]=%d,",i,L.data[i]);
    printf("\n");
    if(ListDelete(L,1,e))
        printf("Delete %d\n",e);
    else
        printf("Failure!\n");
    for(int i=0;i<L.length;i++)printf("data[%d]=%d,",i,L.data[i]);
    return 0;
}

最好时间复杂度：O（1);

最坏时间复杂度：O（n);

平均复杂度：O（n）;

按位查找

#include<stdio.h>
# define MaxSize 10
typedef struct{
    int data[MaxSize];
    int length;
}SeqList;

void InitList(SeqList &L)
{
    int i;
    for(i=0;i<MaxSize;i++)L.data[i]=0;
    L.length=0;
}

bool ListInsert(SeqList &L,int i,int e)
{
    int j;
    if(i<1||i>L.length+1)return false;
    if(i>MaxSize)return false;
    for(j=L.length;j>=i;j--)
        L.data[j]=L.data[j-1];
    L.data[i-1]=e;
    L.length++;
    return true;
}

int GetElem(SeqList L,int i){
    if(i<1||i>L.length) return -1;
    return L.data[i-1];
}

int main(void)
{
    SeqList L;
    InitList(L);
    ListInsert(L,1,1);
    ListInsert(L,2,2);
    ListInsert(L,3,3);
    printf("%d,",GetElem(L,1));
    printf("%d\n",GetElem(L,0));
    return 0;
}

时间复杂度：O（1）

按值查找

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

最好时间复杂度：O(1)

最坏时间复杂度：O(n)

平均时间复杂度：O(n)

5）练习题

T1 删除顺序表中的最小值（假设唯一），并由函数返回被删元素的值。若顺序表为空则显示出错信息并退出运行

//删除最小元素，并返回该元素的值
bool ListDelete(SeqList &L,int &min)
{
    int i; 
    int index=0;//记录最小元素的位序
    if(L.length==0) return false; //如果链表为空，则返回false
    min=L.data[0];
    //查找最小的元素
    for(i=1;i<L.length;i++)
    {
        if(L.data[i]<min) min=L.data[i];
        index=i+1;
    }
    //将空出来的位置由最小的元素代替
    L.data[index]=L.data[L.length-1];
    L.length--;
    return true; 
}

T2 设计算法将顺序表中的元素逆序，要求算法的空间复杂度O(1);

bool ReverseList(SeqList &L)
{
    if(L.length==0)return false;
    int i;
    int j;
    int temp;
    for(i=0;i<(L.length)/2;i++)
    {
        j=L.length-i-1;
        temp=L.data[i];
        L.data[i]=L.data[j];
        L.data[j]=temp;
    }
    return true;
}

*T3 长度为n的顺序表L，编写一个时间复杂度为O(n)，空间复杂度为O(1)的算法。该算法删除线性表中所有值为x的元素。

void DeleteByValue(SeqList &L,int x)
{
    int k=0;//用来存储不是x的数的个数
    for(int i=0;i<L.length;i++)
    {
        if(L.data[i]!=x)
        {
            L.data[k]=L.data[i];
            k++;
        }
    }
    L.length=k;
}

T4 从有序顺序表中删除其值在给定值s与t之间(要求s<t)的所有元素，如果s或者t不合理或顺序表为空，则显示出错信息并退出运行。

bool DeleteBetweenValue(SeqList &L,int s,int t,int &start,int &end)
{
    if(L.length==0) return false;
    if(s>=t) return false;
    int i;
    for(i=0;i<L.length;i++)
    {
        if(L.data[i]==s)start=i+1;
        if(L.data[i]==t)end=i+1;
    }
    return true;
}

int main(void)
{
    int e=0;
    SeqList L;
    InitList(L);
    int start;
    int end;
    ListInsert(L,1,1);
    ListInsert(L,2,2);
    ListInsert(L,3,3);
    for(int i=0;i<L.length;i++)printf("%d,",L.data[i]);
    DeleteBetweenValue(L,1,2,start,end);
    printf("\n");
    int k=end-start+1;
    for(int j=0;j<k;j++) ListDelete(L,start,e);
    for(int i=0;i<L.length;i++)printf("%d,",L.data[i]);
    return 0;
}