一、线性表

1、线性表

1.1、线性表的定义

1.2、线性表的操作

2、顺序表

2.1、顺序表的实现–静态分配

静态的数组分配后固定不变

Sq:sequence–顺序，序列

#include<stdio.h>
#define MaxSize 10typedef struct{int data[MaxSize];int length;
}SqList;void InitList(SqList &L){for(int i=0;i<MaxSize;i++){L.data[i]=0;}L.length=0;
}
int main(){SqList L;InitList(L);for(int i=0;i<MaxSize;i++)printf("data=%d\n",L.data[i]);return 0;
} 

2.2、顺序表的实现–动态分配

#include<stdlib.h>
#define InitSize 10//结构体 
typedef struct{int *data;int MaxSize;int length;
}SeqList;//初始化顺序表 
void InitList(SeqList &L){L.data=(int *)malloc(InitSize*sizeof(int));L.MaxSize=InitSize;L.length=0;
}
//增加长度操作
void IncreaseSize(SeqList &L,int len){int *p=L.data;L.data=(int *)malloc((InitSize+len)*sizeof(int));//将以前的数据复制到新区域for(int i=0;i<L.length;i++){L.data[i]=p[i];} L.MaxSize=L.MaxSize+len;//销毁无效区域 free(p);
}int main(){SeqList L;InitList(L);IncreaseSize(L,5);return 0;
}

2.2、顺序表的特点

3、顺序表的基本操作

3.1、插入操作

#include<stdlib.h>
#include<stdio.h>
#define InitSize 10
#define MaxSize 10
typedef struct{int *data;int length;
}SqList;//初始化顺序表
void InitList(SqList &L){L.data=(int *)malloc(sizeof(int)*InitSize);L.length=0;
} //顺序表插入
bool ListInsert(SqList &L,int i,int e){//为了代码的健壮性，判断i的范围是否有效if(i<1||i>L.length+1)return false;//判断存储空间是否已满 if(L.length>=MaxSize)return false; //i及其i之后数据向后移动一位for(int j=L.length;j>=i;j--){L.data[j]=L.data[j-1];} //赋值L.data[i-1]=e; //长度+1L.length=L.length+1; return true;
} 
int main(){SqList L;InitList(L);//给顺序表赋值for(int i=0;i<5;i++){L.data[i]=i+1;L.length++;} ListInsert(L,3,3);for(int i=0;i<=5;i++){printf("%d\n",L.data[i]);} return 0;
}

插入操作的时间复杂度：

3.2、删除操作

#include<stdlib.h>
#include<stdio.h>
#define InitSize 10
#define MaxSize 10
typedef struct{int *data;int length;
}SqList;//初始化顺序表
void InitList(SqList &L){L.data=(int *)malloc(sizeof(int)*InitSize);L.length=0;
} //顺序表插入
bool ListInsert(SqList &L,int i,int e){//为了代码的健壮性，判断i的范围是否有效if(i<1||i>L.length+1)return false;//判断存储空间是否已满 if(L.length>=MaxSize)return false; //i及其i之后数据向后移动一位for(int j=L.length;j>=i;j--){L.data[j]=L.data[j-1];} //赋值L.data[i-1]=e; //长度+1L.length++; return true;
} 
//顺序表删除
bool ListDelete(SqList &L,int i,int &e){//判断合法性if(i<1||i>L.length+1)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(){int e=-1;SqList L;InitList(L);//给顺序表赋值for(int i=0;i<5;i++){L.data[i]=i+1;L.length++;} ListInsert(L,3,3);ListDelete(L,5,e);for(int i=0;i<L.length;i++){printf("%d\n",L.data[i]);} printf("delete data = %d",e);return 0;
}

删除操作的时间复杂度：

3.3、查找操作

3.2、按位查找

按位查找的时间复杂度

3.2、按值查找

#include<stdlib.h>
#include<stdio.h>
#define InitSize 10typedef struct{int *data;int MaxSize;int length;
}SeqList;//初始化顺序表
void InitList(SeqList &L){L.data=(int *)malloc(sizeof(int)*InitSize);L.length=0;L.MaxSize=InitSize;
} 
//按值查找
int LocateElem(SeqList L,int e){for(int i=0;i<L.length;i++){if(L.data[i]==e)return i+1;}return 0;
} 
int main(){SeqList L;InitList(L);//给顺序表赋值for(int i=0;i<5;i++){L.data[i]=i+1;L.length++;} int number=LocateElem(L,3);printf("%d",number);return 0;
}

结构类型比较：

时间复杂度