线性表的插入、删除和查询操作

线性表的插入、删除和查询操作

1、定义线性表

定义一个线性结构，有列表默认长度设置为50，列表数量

#include <stdio.h>
#define MaxSize 50typedef int Element;
typedef struct{Element data[MaxSize];int length;
}SqList;

2、顺序表插入

插入顺序表

第一步：判断是否符合插入，插入的数据不能超过顺序表的长度

第二部：如何进行插入，可以这样理解，顺序表要插入，之前的数据肯定都是要向后移动的，所以直接从最后一个元素向后移动，不能从插入的位置向后移动，不然会把之后的元素覆盖，这样就找不到了，所以结束条件是到插入的位置，遍历循环是减减

第三步：插入之后，顺序表的长度增加了

#include <stdio.h>#define MaxSize 50typedef int Element;
typedef struct{Element data[MaxSize];int length;
}SqList;bool SqListInsert(SqList &L,Element position,Element num)
{if(position<1 || position>L.length){return false;}for(int i=L.length;i>=position;i--){L.data[i] = L.data[i-1];}L.data[position-1] = num;L.length++;return true;
}

3、顺序表打印

为了后面看到是否插入成功，可以写一个遍历打印顺序表元素

#include <stdio.h>
//定义固定大小
#define MaxSize 50
//类型重命名
typedef int Element;
//定义struct并命名
typedef struct{Element data[MaxSize];int length;
}SqList;
//顺序表插入
bool SqListInsert(SqList &L,Element position,Element num)
{if(position<1 || position>L.length){return false;}for(int i=L.length;i>=position;i--){L.data[i] = L.data[i-1];}L.data[position-1] = num;L.length++;return true;
}
//顺序表打印
void SqListPrint(SqList L)
{for(int i = 0;i<L.length;i++){printf("%5d",L.data[i]);}printf("\n");
}

4、顺序表插入执行

主函数进行测试顺序表插入是否正确

#include <stdio.h>
//定义固定大小
#define MaxSize 50
//类型重命名
typedef int Element;
//定义struct并命名
typedef struct{Element data[MaxSize];int length;
}SqList;
//顺序表插入
bool SqListInsert(SqList &L,Element position,Element num)
{if(position<1 || position>L.length){return false;}for(int i=L.length;i>=position;i--){L.data[i] = L.data[i-1];}L.data[position-1] = num;L.length++;return true;
}
//顺序表打印
void SqListPrint(SqList L)
{for(int i = 0;i<L.length;i++){printf("%5d",L.data[i]);}printf("\n");
}
//程序入口
int main(){//定义一个顺序表，变量lSqList l;// 给顺序表初始化元素l.data[0]=1;l.data[1]=0;l.data[2]=3;l.data[3]=4;l.data[4]=5;l.length=5; // 设置长度//判断标志变量bool ret;// 调用顺序表插入ret = SqListInsert(l,1,60);// 判断顺序表插入是否成功if (ret) {printf("SqList insert success!\n");SqListPrint(l);}else{printf("SqList insert failed!\n");}return 0;
}

执行结果如下

5、顺序表删除

同插入差不多，删除顺序表如下

第一步：判断是否符合删除条件，删除的位置是要在顺表的长度之内的

第二部：如何进行删除，可以这样理解，顺序表要删除，之后的数据肯定都是要向前移动的，所以直接从要删除位置开始向前移动，不能从最后的位置向前移动，不然会把之前的元素覆盖，这样就找不到了，所以结束条件是到最后长度的位置，遍历循环是加加

第三步：删除之后，顺序表的长度减少了

#include <stdio.h>
//定义固定大小
#define MaxSize 50
//类型重命名
typedef int Element;
//定义struct并命名
typedef struct{Element data[MaxSize];int length;
}SqList;
//顺序表插入
bool SqListInsert(SqList &L,Element position,Element num) 会改变SqList，需要引用
{if(position<1 || position>L.length){return false;}for(int i=L.length;i>=position;i--){L.data[i] = L.data[i-1];}L.data[position-1] = num;L.length++;return true;
}
// 顺序表表删除
bool SqListDelete(SqList &L,ElemType position,ElemType &del) //SqList &L是因为会改变SqList，需要引用；ElemType &del要保存删除的具体数据并输出
{if(position<1 || position>L.length){return false;}del = L.data[position - 1];for (int i = position; i < L.length; i++) {L.data[i - 1] = L.data[i];}L.length--;return true;
}
//顺序表打印
void SqListPrint(SqList L)
{for(int i = 0;i<L.length;i++){printf("%5d",L.data[i]);}printf("\n");
}

6、顺序表删除执行

主函数进行测试顺序表删除是否正确

#include <stdio.h>
//定义固定大小
#define MaxSize 50
//类型重命名
typedef int Element;
//定义struct并命名
typedef struct{Element data[MaxSize];int length;
}SqList;
//顺序表插入
bool SqListInsert(SqList &L,Element position,Element num)
{if(position<1 || position>L.length){return false;}for(int i=L.length;i>=position;i--){L.data[i] = L.data[i-1];}L.data[position-1] = num;L.length++;return true;
}
//顺序表打印
void SqListPrint(SqList L)
{for(int i = 0;i<L.length;i++){printf("%5d",L.data[i]);}printf("\n");
}
//程序入口
int main(){//定义一个顺序表，变量lSqList l;// 给顺序表初始化元素l.data[0]=1;l.data[1]=0;l.data[2]=3;l.data[3]=4;l.data[4]=5;l.length=5; // 设置长度//判断标志变量bool ret;// 调用顺序表删除ElemType del;ret = SqListDelete(l,2,del);if (ret) {printf("SqList delete success!\n");printf("delete element is %3d\n", del);SqListPrint(l);} else {printf("SqList delete failed!\n");}return 0;
}

执行结果如下

7、顺序表查询

查询就比较简单，进行遍历循环是否相等就可以，这里我们不进行有重复的元素

#include <stdio.h>
//定义固定大小
#define MaxSize 50
//类型重命名
typedef int Element;
//定义struct并命名
typedef struct{Element data[MaxSize];int length;
}SqList;
//顺序表插入
bool SqListInsert(SqList &L,Element position,Element num) 会改变SqList，需要引用
{if(position<1 || position>L.length){return false;}for(int i=L.length;i>=position;i--){L.data[i] = L.data[i-1];}L.data[position-1] = num;L.length++;return true;
}
// 顺序表表删除
bool SqListDelete(SqList &L,ElemType position,ElemType &del) //SqList &L是因为会改变SqList，需要引用；ElemType &del要保存删除的具体数据并输出
{if(position<1 || position>L.length){return false;}del = L.data[position - 1];for (int i = position; i < L.length; i++) {L.data[i - 1] = L.data[i];}L.length--;return true;
}
// 顺序表查找
int SqListQuery(SqList L, ElemType num) //ElemType num要查看的具体数据
{for(int i = 0;i<L.length;i++){if(num == L.data[i]){return i+1; // 返回要查看的数据在那个第几个，从1开始，元素下标加1}}return 0;
}
//顺序表打印
void SqListPrint(SqList L)
{for(int i = 0;i<L.length;i++){printf("%5d",L.data[i]);}printf("\n");
}

8、循序表查询执行

主函数进行测试顺序表查询是否正确

#include <stdio.h>
//定义固定大小
#define MaxSize 50
//类型重命名
typedef int Element;
//定义struct并命名
typedef struct{Element data[MaxSize];int length;
}SqList;
//顺序表插入
bool SqListInsert(SqList &L,Element position,Element num)
{if(position<1 || position>L.length){return false;}for(int i=L.length;i>=position;i--){L.data[i] = L.data[i-1];}L.data[position-1] = num;L.length++;return true;
}
//顺序表打印
void SqListPrint(SqList L)
{for(int i = 0;i<L.length;i++){printf("%5d",L.data[i]);}printf("\n");
}
//程序入口
int main(){//定义一个顺序表，变量lSqList l;// 给顺序表初始化元素l.data[0]=1;l.data[1]=0;l.data[2]=3;l.data[3]=4;l.data[4]=5;l.length=5; // 设置长度// 调用顺序表查找ElemType num; // 接收要查找元素的位置num = SqListQuery(l,0); // 0为要查找的具体数值if (num == 0) {printf("do not find the element!\n");} else {printf("find the element!\n");printf("the elemet is %d postion!\n", num);}return 0;
}

结果如下