善良先生

用户名：Officialmomo

访问量：23529

签　名：

此时已莺飞草长，爱的人正在路上

等　　级
排　　名	167
经　　验	7061
参赛次数	8
文章发表	42
年　　龄	0
在职情况	学生
学　　校	东莞理工学院
专　　业	计算机科学与技术

　　自我简介：

穿越人海只为与你相拥

TA的其他文章

你可能喜欢

A+B for Input-Output Practice (VI) （C++代码）

数据结构之顺序表

　　作者: 善良先生　　　　发表时间：2019-09-10 09:07:10 浏览：417　|　评论：0　

### 顺序表的创建
之前有写过链表的实现，不过也只是贴了一长串代码，今天我想再重新写一个顺序表，包括具体实现以及算法的细节地方

那么，顺序表是什么呢？顺序表是线性结构的最基本的一种结构，由它发展处多种线性结构，栈，队列，循环队列。我们所说的顺序表，顺序指的是什么呢？是位置，是地址，多有的元素都依次排列在一条线上，这就是跟我们所学的数组是一样的。

顺序表所涉及的功能特征与数组完全一样，所以我们就用数组来定义，再定义一个变量length来记录顺序表随时变化的长度。

您有两种定义方式：

1.用结构体的方式定义——“封装思想”
    1 typedef struct{
    2     int data[maxsize];
    3     int length;
    4 }Sqlist;

2.直接使用数组定义

1 int data[maxsize];
    2 int length;
     
    
> 这两种方式都是可以的，您可以根据自己的喜好选择。
本文中我们选择的是结构体定义

顺序表的特点是：最大长度不可变，长度从程序运行之前就已经固定。

插入元素的算法
假设数组元素是从小大大顺序排列，如下：

![](/image_editor_upload/20190910090558_44106.png)

现在想要将元素5插入进去，该如何做呢？

首先我们需要找到我们即将插入的位置，元素5应该插入到元素4的右边，那么，元素5的下标就应当是3.
![](/image_editor_upload/20190910090621_21703.png)

为了找到元素5插入位置的下标，我们只需要找到第一个比5大的元素（6）的下标，再记录下来就行了。所以有下面算法：

1 //找到第一个比 x 大的数字，返回其下标，如果未找到，则返回最后一位元素的下一位 
     2 
     3 int fineElem(Sqlist L,int x){
     4     int i;
     5     for(i = 0;i<L.length;i++){
     6         if(x<L.data[i]){
     7             return i;
     8         }
     9     }
    10     return i;
    11 }

然后是插入工作，怎么插入呢：

![](/image_editor_upload/20190910090631_37813.png)

方法显而易见。我们需要从最后一个元素依次向后挪，最后再实行插入工作。

void insertElem(Sqlist &L,int x){
        int p,i;
        p = findElem(L,x);                //p为大于x的第一个数字的下标 
        for(i = L.length-1;i>=p;i--){
            L.data[i+1] = L.data[i];
        }
        L.data[p] = x;
        L.length++;
    }
     
    
 下面是一些重要算法，下面算法的不同之处在于更加的人性化，对于插入和删除位置提供合法性判断。

1 //按照元素值的查找算法
     2 int findElem(Sqlist L,int e){
     3     int i;
     4     for(i = 0;i<L.length;i++){
     5         if(e == L.data[i])
     6             return i;
     7     }
     8     return -1;
     9 } 
    10 //插入数据元素的算法
    11 int insertElem(Sqlist &L,int p,int e){
    12     int i;
    13     if(p<0 || p>L.length || L.length == maxsize)        //p可以等于L.length的原因：因为插入元素可以插入到L.data[length] 
    14     {
    15         return 0;
    16     }
    17     for(i = L.length-1;i>=p;i--){
    18         L.data[i+1] = L.data[i];
    19     }
    20     L.data[p] = e;
    21     L.length++;
    22     return 1;
    23 }
    24 //删除元素 p为下标 
    25 int deleteElem(Sqlist &L,int p,int &e){
    26     int i;
    27     if(p<0 || p>L.length-1){        //如果指定删除的位置不合法，则返回0，L.length-1为最后一个元素的下标
    28         return 0;
    29     }
    30     e = L.data[p];                //将删除的值保存起来，由e保存
    31     for(i = p;i<L.length-1;i++){
    32         L.data[i] = L.data[i+1];
    33     }
    34     L.length--;
    35     return 1;
    36 }
    37 //初始化顺序表
    38 void initList(Sqlist &L){
    39     L.length = 0;
    40 } 
    41 int main(){
    42     Sqlist L;
    43     int n,i;
    44     cin>>n;
    45     for(i = 0;i<n;i++){
    46         cin>>L.data[i];
    47     }
    48     L.length = i;
    49     return 0;
    50 }

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

善良先生

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.8 （C++代码）

C语言程序设计教程（第三版）课后习题5.7 （C++代码）

C语言训练-计算1~N之间所有奇数之和（C语言代码）

A+B for Input-Output Practice (VI) （C++代码）

多输入输出练习1 （C语言代码）

数据结构之顺序表

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

【矩阵】（C++代码）

2^k进制数（C语言描述，蓝桥杯）

数组与指针的问题

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

JAM计数法（C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

三进制小数（C语言代码）

善良先生

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.8 （C++代码）

C语言程序设计教程（第三版）课后习题5.7 （C++代码）

C语言训练-计算1~N之间所有奇数之和 （C语言代码）

A+B for Input-Output Practice (VI) （C++代码）

多输入输出练习1 （C语言代码）

数据结构之顺序表

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

【矩阵】 （C++代码）

2^k进制数 （C语言描述，蓝桥杯）

数组与指针的问题

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

JAM计数法 （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

三进制小数 （C语言代码）

C语言训练-计算1~N之间所有奇数之和（C语言代码）

　　评论区

【矩阵】（C++代码）

2^k进制数（C语言描述，蓝桥杯）

JAM计数法（C语言代码）

三进制小数（C语言代码）