[toc]

前言

线性表(Liner List)

线性表:是具有==相同数据类型==的n（n≥0）个数据元素的==有限==序列，其中n为表长，当n = 0时,线性表是一个空表。

特点:一对一,除第一个唯一前驱,除最后一个有唯一后继.

a1-->a2-->a3-->a4

数据结构三要素:逻辑结构,存储结构,运算.

线性表是一种逻辑结构,有两种存储结构:顺序表和链表.

基本操作

• 创建,销毁
• 增加元素
• 删除元素
• 按位查找
• 按值查找

常用操作

• 判断表空
• 求表长
• 打印表

整个项目的构建

image-20210328141636320

编程软件采用vscode,采用cmake管理多文件,不需要手动编译.

关于具体vscode的讲解,我有写,但是还没整理好.

顺序表(静态分配)

静态分配,元素为结构体的顺序表

定义

我们取元素为结构体,写一个复杂一点点的,注意比较结构体相同的时候,不能用==.

未命名文件

#define MAXSIZE 10

typedef struct{
    int number;  //序号
    string name; //姓名
    

}Student;

//定义一个静态,元素为字符的顺序表,最大元素10
typedef struct 
{
    int length;             //当前表长
    Student data[MAXSIZE] ; //数据

}Seqlist;

初始化

==典型错误==

//初始化
void initList(Seqlist & l){
    l.length=0;
}

• 由于内存中的脏数据,假如不初始化可能产生意想不到的效果.

我们强制打印一下,明显不是我们想要的结果

void test(){
    Seqlist l;
    initList(l);
    //insertListByOrder(l,1,'a');
    //printList(l);
    for(int i=0;i<10;i++){
        cout << "第" <<i <<"个" <<endl;
        cout << "名字是:"<<l.data[i].name << endl;
        cout << "序号是:" <<l.data[i].number << endl;
    }
}

image-20210328110744796

完善后的如下:

void initList(Seqlist & l){
    for(int i=0;i<Maxsize;i++){
        l.data[i].number=0;
        l.data[i].name="";
    }
    l.length=0;
}

image-20210328111320482

静态分配没必要销毁.

增

image-20210328143132687

• 注意健壮性,判断位置与表满,

• 尤其注意插入位置是1到表长+1

• 由于需要修改顺序表,注意采用&

bool insertList(Seqlist & l,int n,int number,string name){
    //插入位置检查
    if(n<1||n>l.length+1){
        cout <<"插入位置不合法" <<endl;
        return false;
    }
    //表满检查
    if(l.length>=MAXSIZE){
        cout <<"表已满" <<endl;
        return false;
    }
    /* //从最后开始往后移一个位置
    for(int i=l.length-1;i>=n-1;i--){
        l.data[i+1]=l.data[i];
    }
    l.data[n-1]=e;
    l.length++;
    return true; */
    for(int i=l.length;i>=n;i--){
        l.data[i].name=l.data[i-1].name;
        l.data[i].number=l.data[i-1].number;

    }
    l.data[n-1].name=name;
    l.data[n-1].number=number;
    l.length++;
    return true;
}

调用代码,注意返回是bool,所以可以判断是否插入成功,printList()在后面有解释

   if(insertList(l,1,0,"Alice")){
        cout <<"insert success" <<endl;
    }
    //insertList(l,1,0,"Alice");
    insertList(l,2,1,"Baker");
    insertList(l,3,2,"Chris");

    printList(l);

image-20210328140459095

删

• 注意有多个返回值,所以通过指针修改

• 删除位置的合法性判断,1到表长

bool deleteListByOrder(Seqlist & l,int n,int &number,string & name){
    if(n<1||n>l.length){
        cout <<"删除位置不合法" <<endl;
        return false;

    }

    number=l.data[n-1].number;
    name=l.data[n-1].name;
    for(int i=n;i<l.length;i++){
        l.data[i-1].name=l.data[i].name;
        l.data[i-1].number=l.data[i].number;
    }
    l.length--;
    return true;

}

调用

string name;
    int number;
    if(deleteListByOrder(l,2,number,name)){
        cout <<"删除的学生序号是" <<number <<endl;
        cout <<"删除的学生名字是" <<name <<endl;
    }
    printList(l);

[图片上传失败...(image-8a461d-1616913118803)]/upload/image-20210328140621044.png)

查

// 按位序查找元素
void findElementByOrder(Seqlist  l,int n,int & number,string & name);

// 按内容---姓名查找位置,第一次出现,,没有返回-1
int findElementByValue(Seqlist  l,string name);

//按内容---结构体查找位置
int findStructByValue(Seqlist  l,Student student);

• 注意判断结构体相同的方法
• 由于

void findElementByOrder(Seqlist  l,int n,int &number,string & name){
    if(n<1||n>l.length){
        cout <<"查找位置不合法" <<endl;
        return;

    }
    number=l.data[n-1].number;
    name=l.data[n-1].name;

}

int findElementByValue(Seqlist  l,string name){
    for(int i=0;i<l.length;i++){
        if(l.data[i].name==name){
            return i+1;
        }
    }
    return -1;


}

int findStructByValue(Seqlist  l,Student student){
    for(int i=0;i<l.length;i++){
        if(isSameStudent(l.data[i],student)){
            return i+1;
        }
    }
    return -1;



}

调用

    int n=2;
    string name2="";
    int number2;
    findElementByOrder(l,n,number2,name2);
    cout << "第" <<n <<"个位置的序号是" << number2 <<endl;
    cout << "第" <<n <<"个位置的名字是" << name2 <<endl;

    cout <<"Alice的位序是" <<findElementByValue(  l,"Alice") <<endl;

    Student a;
    a.number=0;
    a.name="Alice";
    if(findStructByValue(l,a)){
        cout <<"位序是" <<findStructByValue(l,a) <<endl;
    }

image-20210328141449802

工具

//打印一下顺序表
void printList(Seqlist  l);

//表长
int lengthOfList(Seqlist l);

//判断表空 
bool isEmpty(Seqlist l);

//判断结构体相同
bool isSameStudent(Student a,Student b);

void printList(Seqlist  l){
    for (int i=0;i<l.length;i++){
        cout <<"第" << i+1 <<"个学生序号是 " << l.data[i].number <<endl;
        cout <<"第" << i+1 <<"个学生名字是 " << l.data[i].name <<endl;
    }
}

int lengthOfList(Seqlist l){
    return l.length ;
}

bool isEmpty(Seqlist l){
    if(l.length!=0){
        return false;
    }
    return true;
}

bool isSameStudent(Student a,Student b){
    if(a.name==b.name&&a.number==b.number){
        return true;
    }
    return false;
}

源程序如有必要,留言.