顺序表的相关操作--静态动态分配实现初始化、插入、删除、查找、判空、求表长_顺序表静态分配了还要动态初始化吗

一、顺序表的实现：

静态分配顺序表的定义：

#define MaxSize 10                         //定义最大长度
typedef struct{                            
    ElemType data[MaxSize];                //用静态的数组存放元素
    int length;                            //顺序表的当前长度
}Sqlist;                                   //顺序表的类型定义

静态分配实现顺序表：

#include <stdio.h>
#define MaxSize 10
Typedef struct {
    ElemType data[MaxSize];
    int length;
}SqList;
 
void InitList(Sqlist &L){
    int i;
    for(i=0;i<MaxSize;i++)
        L.data[i]=0;   //防止脏数据
    L.length=0;
}
 
 int main(){
    Sqlist L;
    InitSqlist(L);
    return 0;
}

动态分配顺序表的定义：

#define InitSize 10                        //初始大小
tyepdef struct{
    ElemType *data;                       //data指针指向malloc分配函数占一个ElemType的地址空间
    int MaxSize;
    int length;
}Sqlist;

动态分配实现顺序表：

#include <stdio.h>  //用到malloc和free函数
#define InitSize 10
typedef struct{
    int *data;//定义数据元素的类型为int型
    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.length;i++){
        L.data[i]=p[i];        //将数据复制到新区域
    }
    L.MaxSize=L.MaxSize+len;
    free(p);  //释放原来的内存空间，p也会被自动收回
}
 
int main(){
    Seqlist L;
    InitList(L);
    IncreaseSize(L,len);
    return 0;
}
 

二、插入和删除：

ListInsert(&L,i,e)在表中第i位插入指定元素e。

ListDelete(&L,i,&e)在表中第i位指定元素，并用e返回删除元素的值。

静态分配顺序表的插入和删除：

//插入
#define MaxSize 10
typedef struct{
    int data[MaxSize];//定义数据元素的类型为int型
    int length;
}Sqlist;
 
void InitList(Sqlist &L){
    int j;
    for(j=0;j<MaxSize;j++)
        L.data[j]=0;   //防止脏数据
    L.length=0;
}
 
bool ListInsert(Sqlist &L, int i ,int e){
    if(i<1||i>length+1)
        return false;
    if(L.length>=MaxSize)
        return false;
    for(intj=L.length;j>=i;j--)
        L.data[j]=L.data[j-1];
    L.data[i-1]=e;
    L.length++;
    return true;
}
 
int main(){
    Sqlist L;
    InitList(L);
    ListInsert(L,i,e);
    return 0;
}

最好时间复杂度O(1),最坏时间复杂度O(n),平均时间复杂度为(1/n+1)·n·(n+1)/2=n/2,T(n)=n/2

//删除
#define MaxSize 10
typedef struct{
    int data[MaxSize];//定义数据元素的类型为int型
    int length;
}Sqlist;
 
void InitList(Sqlist &L){
    for(int j=0;j<MaxSize;j++){
        data[j]=0;
    }
    L.length=0;
}
 
bool ListDelete(Sqlist &L, int i ,int &e){
    if(i<1||i>length)
        return false;
    e=L.data[i-1];
    for(int j=i;j<L.length;j++)
        L.data[j-1]=L.data[j];
    L.length--;
    return true;
}
 
 
int main(){
    Sqlist L;
    InitList(L);
//此处省去插入元素代码
    int e = -1;
    if(ListDelete(L,i,e))
        print("已删除第i个元素，值位%d\n",e);//如果在删除方法中e不加&，则改变的是e的复制品，此处输出的e仍为-1
                     //同理，Sqlist L也一样
    else
        print("位序不合法，失败\n");
    return 0;
}

最好时间复杂度O(1),最坏时间复杂度O(n),平均时间复杂度为(1/n)·n·(n-1)/2=n/2,T(n)=(n-1)/2

动态分配顺序表的插入和删除：

//插入
#include<stdio.h>
#define InitSize 10
typedef struct{
    int *data;//定义数据元素的类型为int型
    int MaxSize;
    int Length;
}Seqlist;
 
bool InitList(Seqlist &L){
    L.data=(int *)malloc(sizeof(int *));
    for(int j=0; j<L.Maxsize; j++){
        L.data[j]=0;
    L.length=0;
    return true;
}
 
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.length;i++){
        L.data[i]=p[i];        //将数据复制到新区域
    }
    L.MaxSize=L.MaxSize+len;
    free(p);  //释放原来的内存空间，p也会被自动收回
}
 
void InsertList(Seqlist &L, int i, int e){
    if(i<1||i>length+1)
        return false;
    if(L.length>=L.MaxSize)
     //此处添加代码提示增加空间
        IncreaseSize(L, int len);
    for(int j=L.length; j>=i; j--)
        L.data[j]=L.data[j-1];
    L.data[i-1]=e;
    L.length++;
    return true;
}
 
int main(){
    Seqlist L;
    InitList(L);
    InsertList(L,i,e);
}

//删除
#include<stdio.h>
#define InitSize 10
typedef struct{
    int *data;//定义数据元素的类型为int型
    int MaxSize;
    int length;
}Seqlist;
 
 
void InitList(Seqlist &L){
    for(int j=0;j<MaxSize;j++){
        L.data[j]=0;
    }
    L.length=0;
}
 
bool ListDelete(Seqlist &L, int i ,int &e){
    if(i<1||i>length)
        return false;
    e=L.data[i-1];
    for(int j=i;j<L.length;j++)
        L.data[j-1]=L.data[j];
    L.length--;
    return true;
}
 
int main(){
    Sqlist L;
    InitList(L);
//此处省去插入元素代码
    int e = -1;
    if(ListDelete(L,i,e))
        print("已删除第i个元素，值位%d\n",e);//如果在删除方法中e不加&，则改变的是e的复制品，此处输出的e仍为-1
                     //同理，Seqlist L也一样
    else
        print("位序不合法，失败\n");
    return 0;
}

四、静态分配顺序表的查找：

按位查找主代码

GetElem(L,i)获取表中第i个位置的元素  

//以静态分配为例
#define MaxSize 10
typedef struct{
    ElemType data[MaxSize];
    int Length;
}Sqlist;
    
ElemType getElem(Sqlist L,int i){ 
    return L.data[i-1];
}

//以动态分配为例
#define InitSize 10
typedef struct{
    ElemType *data;//data指针指向malloc分配函数占一个ElemType的地址空间
    int MaxSize;
    int Length;
}Seqlist;
    
ElemType getElem(Seqlist L,int i){ 
    return L.data[i-1];//如果sizeof(ElemType)=6,malloc分配到的起始地址空间为200，
                       //那么data[0]从200开始，data[1]从2006开始
}

两种分配方式的时间复杂度都是O(1)。

按值查找：

LocateElem(L,e),在表L中查找具有给定关键字值的元素。

#define MaxSize 10
typedef struct{
    ElemType data[MaxSize];//此处不指定数据类型
    int Length;
}Sqlist;
 
int LocateElem(Sqlist L, ElemType e){ 
    for(int i=0; i<L.length; i++){
        if(L.data[i]== e)
            return i+1;//返回位序
    renturn 0;
}

#define InitSize 10
typedef struct{
    ElemType data;//此处不指定数据类型
    int Length;
    int MaxSize;
}Seqlist;
 
int LocateElem(Seqlist L, ElemType e){ 
    for(int i=0; i<L.length; i++){
        if(L.data[i]== e)
            return i+1;//返回位序
    renturn 0;
}

两种分配方式按值查找的时间复杂度都是O(n)

顺序表的判空便是长度为0；

bool IsEmpty(SqList L)						//判断List是否为空
{
	if (L.length == 0)
		return OK;
	else
		return false;
}