线性表的基本操作
顺序表的实现——静态分配
#define Maxsize 10 //定义最大的长度
typedef struct{
ElemType data[MaxSize]; //用静态的数组存放数据元素
int length; //顺序表的当前长度
}SqList; //顺序表的类型定义（静态分配方式）
- 具体代码
#include<stdio.h>
#define MaxSize 10 //定义最大长度
typeof struct{
int data[MaxSize]; //用静态数组存放数据，数据的大小为最大长度
int length; //顺序表的当前长度，就是当前存放了多少个数据
}SqList; //顺序表的类型定义
//基本操作——初始化一个顺序表
void IniList(SqList &L){
/* for(int i = 0; i < MaxSize; i++) 这里也可以省略，虽然内存中会遗留脏数据，但是我们访问只会访问小于顺序表长度的数据，并不会访问的后面的脏数据
L.data[i] = 0; */ //将所有数据元素设置成默认初始值
L.length = 0; //顺序表初始长度为0，这个是不能省略的
}
int main(){
SqList L; //声明一个顺序表
InitList(L); //初始化顺序表
.......
return 0;
}
顺序表的实现——动态分配
#define InitList 10 //顺序表的初始长度
typedef struct{
ElemType *data; //指示动态分配数组的指针
int MaxSize; //顺序表的最大容量
int length; //顺序表的当前长度
}SqList; //顺序表的类型定义（动态分配的方式）
- key：动态申请和释放内存空间
c—— malloc、free函数
L.data = (ElemType *)malloc(sizeof(ElemType)*InitSize);
c++——new、delete关键字
- ElemType：malloc函数返回一个指针，需要强制转换为你定义的数据元素类型的指针
- InitSize：malloc函数的参数，指明要分配多大的连续内存空间
- 具体代码
#define InitSize 10 //默认的最大长度
typedef struct{
int *data;//指示动态分配数组的指针
int MaxSize;//顺序表的最大容量
int length;//顺序表的当前长度
}SeqList;
void InitList(SeqList &L){
//用malloc函数申请一片连续的存储空间
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;//顺序表最大长度增加len
free(p);//释放原来的内存空间
}
int main(){
SeqList L;//声明一个顺序表
InitList(L);//初始化顺序表
......//往顺表中插入几个元素
IncreaseSize(L,5);
return 0;
}
顺序表的基本操作——插入
- ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e。
#define MaxSize 10//定义最大长度
typedef struct{
ElemType data[MaxSize];//用静态的数组存放数据元素
int length;//顺序表的当前长度
}SqList;//顺序表的类型定义
- 具体代码
#define MaxSize 10 //定义最大长度
typedef struct{
int data[MaxSize];//用静态的数组存放数据元素
int length;//顺序表的长度
}SqList;//顺序表的类型定义
//插入代码不够健壮，因为如果i大于length，就会出现问题
void ListInsert(SqList &L, int i , int e){
for(int j = L.length; j >= i; j--)//将第i个元素及之后的元素后移，从最后一个元素开始移动
L.data[j] = L.data[j - 1];
L.data[i - 1] = e;//循环结束后，在位置i处放入e
L.length++;//长度加1
}
int main(){
SqLlist L;//声明一个顺序表
InitList(L);//初始化顺序表
//。。。。。插入几个元素
ListInsert(L,3,3);
return 0;
}
修改插入操作代码：
bool ListInsert(SqList &L,int i, int e){//bool类型的函数，返回值是false或true
if(i < 1 || i > L.length + 1)//判断i的范围是否有效
return false;
if( L.length >= MaxSize)//当前的存储空间已满，不能插入
return false;
for(int j = L.length; j >=i; j--)//将第i个元素及之后的元素后移
L.data[j] = L.data[j - 1];
L.data[i - 1] = e;//在位置i处放入e
L.length++;//长度加1
return true;
}
- 时间复杂度：问题规模n = L.length
- 最好情况：新元素插入到表尾，不需要移动元素O(1)
- 最坏情况：新元素插入到表头，每个元素都需要移动O(n)
- 平均情况：新元素插入到任何一个位置的概率相同O(n/2)
顺序表的基本操作——删除
- ListDelete(&L,i,&e):删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值
bool ListDelete(Sq.List &L, int i, int &e){
if(i < 1 || i > L.length)//判断i的范围是否有效
return false;
e = L.data[i - 1];//将被删除的元素赋值给e
for(intn j = i; j < L.length; i++)//将第i个位置后的元素前移，前移操作从前到后依次进行
L.data[j - 1] = L.data[j];
L.length--;//线性表长度减1
return true;
}
int main(){
SqList L;//声明一个顺序表
InitList(L);//初始化顺序表
//插入几个元素
int e = -1;//用变量e把删除的元素“带回来”
if(ListDelete(L,3,e))
printf("已删除第3个元素，删除元素值为=%d\n", e);
else
printf("位序i不合法，删除失败\n");
return 0;
}
-
时间复杂度：
- 最好情况：删除表位元素，不需要移动其他元素O(1)
- 最坏情况：删除表头元素，需要将后续的n-1个元素全都向前移动O(n)
- 平均情况：删除任何一个元素的概率相同O((n-1)/2)
-
代码要点：
- 代码中注意位序i和数组下标的区别
- 算法要有健壮性，注意判断i的合法性
- 注意移动元素的时候，从考前的元素开始，还是从表尾开始
顺序表的按位查找
-
GetElem(L,i)/;按位查找。获取表L中第i个位置的元素的值。
-
静态分配下的按位查找
#define MaxSize 10 typedef struct{ ElemType data[MaxSize]; int length; }SqList; ElemType GetElem(SqList L, int i){//这里还可以判断一下i的值是否合法 return L.data[i-1]; } -
动态分配下的按位查找
#define InitSize 10 typedef struct{ ElemType *data; int MaxSize; int length; }SeqList; ElemType GetElem(SeqList L, int i){ return L.data[i - 1];//和访问普通数组的方法一样 }动态分配的指针指向的是连续地址的初始位置，在加入下标之后，电脑是自动按指针类型来访问相应位置所以对用的数据。如下图
-
时间复杂度：O(1)
顺序表中的按值查找
-
LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素
#define InitSize 10 typedef struct{ ElemType *data; int MaxSize; int length; }SeqList; //在顺序表L中查找第一个元素值等于e的元素，并返回其位序 int LocateElem(SeqList L,ElemType e){ for(int i = 0; i < L.length; i++) if(int L.data[i] == e)//基本数据类型：int、char、double、float等可以直接用运算符“==”比较，但是结构类型是不能用“==”进行比较的 return i+1;//数组下标为i的元素值等于e，返回其位序i-1 return 0;//退出循环，说明查找失败 }如果是比较结构体，需要依次对比各个分量来判断两个结构体是否相等
if(a.num == b.num && a.people == b.people){ printf("相等"); }else{ printf("不相等"); }更好的方法：定义一个函数
bool isCustomerEqual(Customer a, Customer b){ if(a.num == b.num && a.people == b.people) return true; else return false;c }在数据结构考研初试中，手写代码可以直接用==，无论是基本数据类型还是结果类型
时间复杂度
-
时间复杂度：
- 最好情况：目标出现在表头：O(1)
- 最坏情况：目标元素在表尾：O(n)
- 平均情况：目标元素在每个位置的概率相同O(n)