线性表代码实战

10.2 线性表的顺序表示原理解析

一、命名规范：

1. 下划线命名法 list_insert
2. 驼峰命名法 ListInsert(每个单词的首字母大写)

二、线性表的定义：

​ 由n(n>=0)个相同类型的元素组成的有序集合。

三、线性表特点：

1. 表中元素的个数时有限的；
2. 表中元素的数据类型都相同。意味着每一个元素占用相同大小的空间；
3. 表中元素具有逻辑上的顺序性，在序列中各元素排序有其先后顺序。

==！！！==以上均描述的是线性表的逻辑结构，是独立于存储结构的

四、线性表的顺序表示(简称 顺序表)

1.顺序表的定义：

2.优缺点：

3.插入操作的伪代码：

4.删除操作的伪代码：

5.写代码时的注意事项：

1. !!!定义、插入、删除操作一定要修改线性表长度呀！！！

2. 插入和删除操作的i的合法范围是不一样的：

操作	i的合法范围
插入	【1，n+1】
删除	【1，n】

#include <stdio.h>
#define Maxsize 50

typedef int ElemType;//让顺序表存储其他类型元素时，可以快速完成代码修改

// 顺序表的初始化
typedef struct{
    ElemType data[Maxsize];
    ElemType length;
}SqList;

// 插入操作
bool list_insert(SqList &l, int i, ElemType element){
    //判断插入位置是否合理
    if(i < 1 || i > l.length+1){
        return false;
    }
    //是否线性表的位置已经满了
    if(l.length == Maxsize){
        return false;
    }
    //插入元素
    for(int j = l.length; j >= i; j--){
        l.data[j] = l.data[j - 1];
    }
    l.data[i] = element;
    l.length++;
    return true;
}

// 输出线性表
void print_list(SqList l){
    for(int j = 0; j < l.length; j++){
        printf("%3d", l.data[j]);
    }
    printf("\n");
}

// 顺序表的删除操作，并打印出删除的元素
bool delete_list(SqList &l, int i, ElemType &element){
    //判断删除的位置是否合理
    if(i < 1 || i > l.length){
        return false;
    }
    //先把元素提取出来，赋值给element
    element = l.data[i - 1];
    //进行删除操作
    for(int j = i; j < l.length; j++){
        l.data[j - 1] = l.data[j];
    }
    l.length--;//顺序表长度的变化一定一定不能忘记了！！！！
    return true;
}

// 顺序表的查找操作，并打印出所查找元素的位置
bool select_list(SqList l, int &pos, ElemType element){
    for(int j = 0; j <l.length; j++){
        if(element == l.data[j]){
            pos = j + 1;
            return true;
        }
    }
    pos = 0;
    return false;
}

int main() {
    SqList l;//新建一个线性表
    l.data[0] = 0;//放置元素
    l.data[1] = 1;
    l.data[2] = 2;
    l.data[3] = 3;
    l.length = 4;//线性表的长度一定要记得初始化呀！！！
    print_list(l);
    int ret;
    ret = list_insert(l, 4, 7);
    if(ret){
        printf("insert succeed!!! congratulation\n");
    }else{
        printf("insert fail!!! come on");
    }
    printf("---------------------------\n");
    print_list(l);
    int del;//用来读取被删除的元素
    ret = delete_list(l,5,del);
    if(ret){
        print_list(l);
        printf("delete succeed!!! congratulation\n");
        printf("delete element = %d",del);
    }else{
        printf("delete fail!!! come on");
    }
    printf("---------------------------\n");
    print_list(l);
    int pos;//用来保存所查找元素的位置
    ret = select_list(l,pos,3);
    if(ret){
        print_list(l);
        printf("select succeed!!! congratulation\n");
        printf("pos element = %d",pos);
    }else{
        printf("select fail!!! come on");
    }
    return 0;
}

五、线性表的链式表示(简称，链表)

1.单链表结点的定义：

2.头指针与头结点的区别：

！！！注意：

1.头结点不是链表第一个结点，第一个结点指的是头结点后面的结点；

2.头指针一定不为空，但是头结点不是必须的。

3.优缺点：

4.插入操作：

5.删除操作：

6.按序号查找结点：

7.按值查找结点：

原文地址：https://blog.csdn.net/m0_58321769/article/details/145233193

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！