数据结构-顺序表

 一、顺序表的常用操作

1、创建顺序表--CreateList

//建立顺序表
typedef int ElemType;
void CreateList(SqList*& L, ElemType a[], int n) {  //由a中的n个元素建立顺序表int i = 0,k = 0;    // k表示L中元素的个数，初始值为0L = (SqList*)malloc(sizeof(SqList));  // 分配存放线性表的空间while (i < n) {   //i扫描数组a的元素L->data[k] = a[i];   //将元素a[i]存放到L中k++; i++;}L->length = k;  //设置L的长度k
}

2、初始化线性表--InitList(&L)

//初始化线性表
void InitList(SqList*& L) {L = (SqList*)malloc(sizeof(SqList));  //分配存放线性表的空间L ->length = 0;  //置空线性表的长度
}

3、销毁线性表--DestroyList(&L)

//销毁线性表
void DestroyList(SqList*& L) {free(L);  //释放L所指的顺序表空间
}

4、判断线性表是否为空--ListEmpty(L)

//判断线性表是否为空表
bool ListEmpty(SqList * L){return(L->length==0);
}

5、求线性表的长度--ListLength(L)

//求线性表的长度
int ListLength(SqList* L) {return(L->length);
}

6、输出线性表--DispList(L)

//输出线性表
void DispList(SqList* L) {for (int i = 0; i < L->length; i++) {  //遍历顺序表的元素printf("%d ", L->data[i]);}printf("\n");
}

7、获取L中的第i个元素的值--GetElem(L,i,&e)

//获取L中的第i个元素的值
int GetElem(SqList* L, int i, ElemType& e) {if (i<1 || i>L->length) {return false;}e = L->data[i - 1]; //第i个元素的下标为i-1return true;
}

8、查找第一个值为e的元素的逻辑序号(即元素下标+1)--LocateElem( L, e) 

//查找第一个值为e的元素的逻辑序号(即元素下标+1)
int LocateElem(SqList* L, ElemType e) {for (int i = 0; i < L->length; i++) {if (L->data[i] == e) {  return i + 1; //找到元素e，返回逻辑序号(即元素下标+1)}}return 0;  //未找到时返回0
}

9、插入数据元素(在第i个位置插入元素e)--ListInsert(& L, i, ElemType e)

//插入数据元素(在第i个位置插入元素e)
bool ListInsert(SqList*& L, int i, ElemType e) {if (i<1 || i>L->length + 1 || L->length == MaxSize) {return false;  //参数i错误时，返回false}i--;  //将逻辑序号转换成物理序号(即下标)for (int j = L->length; j > i; j--) {L->data[j] = L->data[j - 1];  //将data[i]及后面的元素向后移动一个位置}L->data[i] = e;  //插入元素eL->length++;  //顺序表的长度增加1return true;  //成功插入返回true
}

10、删除元素(在第i个位置的元素e)--ListDelete(& L, i, & e)

//删除元素(在第i个位置的元素e)
bool ListDelete(SqList*& L, int i, ElemType& e) {if(i<1 || i>L->length) {return false;  //参数错误时，返回false}i--;  //将逻辑序号转换成物理序号(即下标)e = L->data[i];for (int j = i; j < L->length-1; j++) {L->data[j] = L->data[j + 1];   //将data[i]之后的元素向前移动一个位置}L->length--;  //顺序表的长度减1return true;  //成功删除，返回true
}

 整体代码

#include<iostream>
using namespace std;
#define MaxSize 50
//声明线性表的顺序存储类型
typedef struct {ElemType data[MaxSize];  //存放线性表中的元素int length;   //存放线性表的长度
}SqList;   //顺序表类型//建立顺序表
typedef int ElemType;
void CreateList(SqList*& L, ElemType a[], int n) {  //由a中的n个元素建立顺序表int i = 0,k = 0;    // k表示L中元素的个数，初始值为0L = (SqList*)malloc(sizeof(SqList));  // 分配存放线性表的空间while (i < n) {   //i扫描数组a的元素L->data[k] = a[i];   //将元素a[i]存放到L中k++; i++;}L->length = k;  //设置L的长度k
}//初始化线性表
void InitList(SqList*& L) {L = (SqList*)malloc(sizeof(SqList));  //分配存放线性表的空间L ->length = 0;  //置空线性表的长度
}//销毁线性表
void DestroyList(SqList*& L) {free(L);  //释放L所指的顺序表空间
}//判断线性表是否为空表
bool ListEmpty(SqList * L){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]);}printf("\n");
}//获取L中的第i个元素的值
int GetElem(SqList* L, int i, ElemType& e) {if (i<1 || i>L->length) {return false;}e = L->data[i - 1]; //第i个元素的下标为i-1return true;
}//查找第一个值为e的元素的逻辑序号(即元素下标+1)
int LocateElem(SqList* L, ElemType e) {for (int i = 0; i < L->length; i++) {if (L->data[i] == e) {  return i + 1; //找到元素e，返回逻辑序号(即元素下标+1)}}return 0;  //未找到时返回0
}//插入数据元素(在第i个位置插入元素e)
bool ListInsert(SqList*& L, int i, ElemType e) {if (i<1 || i>L->length + 1 || L->length == MaxSize) {return false;  //参数i错误时，返回false}i--;  //将逻辑序号转换成物理序号(即下标)for (int j = L->length; j > i; j--) {L->data[j] = L->data[j - 1];  //将data[i]及后面的元素向后移动一个位置}L->data[i] = e;  //插入元素eL->length++;  //顺序表的长度增加1return true;  //成功插入返回true
}//删除元素(在第i个位置的元素e)
bool ListDelete(SqList*& L, int i, ElemType& e) {if(i<1 || i>L->length) {return false;  //参数错误时，返回false}i--;  //将逻辑序号转换成物理序号(即下标)e = L->data[i];for (int j = i; j < L->length-1; j++) {L->data[j] = L->data[j + 1];   //将data[i]之后的元素向前移动一个位置}L->length--;  //顺序表的长度减1return true;  //成功删除，返回true
}int main() {return 0;
}

二、顺序表的应用

假设一个线性表采用顺序表表示，设计一个算法，删除其中所有值等于x的元素，要求算法的时间复杂度为O(n)，空间复杂度为O(1)

解法一：整体建表法

//整体建表法
void delnode1(SqList*& L, ElemType x) {int k = 0;  //k记录不等于x的元素的个数，即保留的元素的个数for (int i = 0; i < L->length; i++) {if (L->data[i] != x) {   //若当前元素不为x，将其插入到L中L->data[k] = L->data[i];k++;  //插入一个元素时，L中元素的个数增加1}}L->length = k;  //顺序表的长度为k
}

 解法二：元素平移法

//元素平移法
void delnode2(SqList*& L, ElemType x) {int k = 0;  //k记录等于x的元素的个数，即要删除的元素的个数for (int i = 0; i < L->length; i++) {if (L->data[i] == x) {  //当前元素为x，x的个数增加1k++;}else {L->data[i - k] = L->data[i];  //当前元素前面有几个x,就把当前元素向前移动几个位置}}L->length -= k; //顺序表的长度减小k
}