线性表复习: 1.线性表定义:线性表是由n(n>=0)个具有相同数据类型的的数据元素构成的有限序列 常记为: A=(a1,a2,a3,...,an) 其中: A是线性表名,n为线性表长度 2.线性表有两种存储方式:顺序存储和链式存储
3.线性表分为：顺序表和链式表 写算法时,先写逻辑结构要使用的数据结构和基本运算,然后选定了具体的存储结构 才能写运算的具体实现代码。 4.顺序表的基本操作 SeqList 是结构体名字 DataType 是结构体中数据元素的类型 逻辑结构上:
1.数据元素的定义
typedef int DataType; //使int重命名为DataType
typedef struct{
DataType data[MAXSIZE]; //定义DataType为int ，存储结构为顺序存储
int length;
}SeqList;
2.基本操作定义----这里使用的是文字描述（自然语言)
1.创建线性表:create_List(SeqList &L)
2.输出线性表中的元素:out_List(SeqList &L)
注意事项:要判断线性表是否为空
3.求线性表的长度:length_List(SeqList &L)
4.简单查找(根据给定元素返回x第一次出现的位置):check_List(SeqList &L,DataType x)
5.复杂查找(根据给定元素返回x出现的所有位置):checkAll_List(SeqList &L,DataType x)
6.插入操作(根据给定的第i个位置插入元素x):insert_List(SeqList &L,int i,DataType x)
注意事项:插入时,
1.要判断插入位置是否合法和线性表是否是满了
2.插入完成后,要把线性表的表长+1
7.简单删除操作(删除线性表中第i个位置的元素):delete_List(SeqList &L,int i)
注意事项:删除时,
1.要判断删除位置是否合法和线性表是不是空表
2.建议使用while循环,从第i-1个位置向后循环,让后面元素覆盖前一个元素位置实现删除操作 ,i++
3.删除完成后线性表长度要-1
8.复杂删除操作(从线性表L的第i个位置删除k个元素):deleteK_List(SeqList &L,int i,int k)
注意事项:删除时，
1.要判断删除位置是否合法和线性表是不是空表
2.建议使用while循环,从第i+k-1个位置到结尾,循环体内把 i+k-1位置元素赋值给i-1位置的元素,i++
3.删除完成后线性表长度要-1
//因为选定的是顺序表，数据结构为线性表，存储结构为顺序存储，所以可以写存储结构的具体实现了 这里用的是c语言
//物理结构实现
#include <iostream>
#define MAXSIZE 100
using namespace std;
typedef int DataType; //使int重命名为DataType
typedef struct{
DataType data[MAXSIZE]; //定义DataType为int ，存储结构为顺序存储
int length;
}SeqList;
//创建顺序表
void create_List(SeqList &L){
cout<<"请输入要输入的数据个数:";
cin>>L.length;
cout<<"请输入要输入的数据:"<<"
";
for(int i=0;i<L.length;i++){
cin>>L.data[i];
}
}
//输出顺序表中的元素
void out_List(SeqList &L){
//判断线性表是否为空
if(L.length != 0){
for(int i=0;i<L.length;i++){
cout<<L.data[i]<<" ";
}
}else{
cout<<"线性表为空"<<"
";
}
}
//求线性表的长度(求线性表中数据元素的个数)
int length_List(SeqList &L){
return L.length;
}
//简单查找 返回-1表示线性表为空 返回i表示x在书虚表中的位置(从0开始)
int check_List(SeqList &L,DataType x){
//判断线性表是否为空
if(L.length != 0){
for(int i=0;i<L.length;i++){
if(L.data[i] == x){
//cout<<"x在顺序表中的位置是:"<<i<<"
";
return i;
}
}
}else{
//否则线性表为空
return -1;
}
}
//复杂查找
void checkAll_List(SeqList &L,DataType x){
//判断线性表是否为空
if(L.length != 0){
int count=0; //用来定义未找到的情况 count=0,未找到
cout<<"复杂查找元素x在线性表中的位置分别是:";
for(int i=0;i<L.length;i++){
if(L.data[i] == x){
cout<<i<<" ";
count++;
}
}
//判断未找到的情况
if(count == 0){
cout<<"未找到!"<<"
";
}else{
cout<<"
";
}
}else{
//否则线性表为空
cout<<"线性表为空,复杂查找失败!"<<"
";
}
}
//插入操作 在第i个位置插入元素类型为DataType的元素x
//n个元素有n+1个位置可以插入
int insert_List(SeqList &L,int i,DataType x){
//判断插入位置是否合法 i取值范围i>=0 && i<=L.length+1
if(i<0 || i>L.length+1){
cout<<"插入位置不合法!"<<"
";
return -1; //异常退出
}
//如果线性表满了,插入不了
if(L.length == MAXSIZE){
cout<<"线性表空间满了!无法插入!"<<"
";
return -1;
}
//如果线性表为空
if(L.length == 0){
if(i == 1){
L.data[i-1] = x;
L.length++;
}else{
cout<<"插入失败!
";
return -1;
}
return 0;
}
//正常情况 先移动位置,在插入
for(int j=L.length-1;j>=i-1;j--){
L.data[j+1]=L.data[j];
}
L.data[i-1] = x;
L.length++;
cout<<"插入成功!"<<"
";
return 0;
}
//简单删除操作 删除i位置的元素
int delete_List(SeqList &L,int i){
//飞控表时判断删除位置是否合法
//非空表时:i>=0 && i<L.length
//空表时: i>0 && i<L.length
if(i<0 || i>L.length){
cout<<"删除位置不合法!
";
return -1;
}
//判断是不是空表
if(L.length == 0){
cout<<"空表,无法进行删除操作!";
return -1;
}else{
while(i<L.length){
L.data[i-1] = L.data[i];
i++;
L.length--;
cout<<"删除成功!
";
return 0;
}
}
}
//复杂删除操作 从i位置删除k个数据元素
//n个元素可以有n个位置可以删除
int deleteK_List(SeqList &L,int i,int k){
//飞控表时判断删除位置是否合法
//非空表时:i>=0 && i<L.length
//空表时: i>0 && i<L.length
if(i<0 || i>L.length){
cout<<"删除位置不合法!
";
return -1;
}
//判断是不是空表
if(L.length == 0){
cout<<"空表,无法进行删除操作!";
return -1;
}else{ //用笔画一下就出来了
for(int j=i+k;j<=L.length;j++){
L.data[j-k-1] = L.data[j-1];
}
L.length=L.length-k;
return 0;
}
}
//主函数用来测试
int main(int argc, char** argv) {
SeqList L;
create_List(L);
out_List(L);
cout<<"
";
cout<<"元素个数是:"<<length_List(L)<<"
";
deleteK_List(L,2,2);
out_List(L);
cout<<"
";
cout<<"元素个数是:"<<length_List(L)<<"
";
return 0;
}