数据结构（一）——线性表的顺序存储原理及实现

一、线性表介绍

1、定义：由n（n>0）个相同类型的元素组成的有序集合，如图

这里所说的线性表是逻辑结构，表示元素一对一的相邻关系，是独立于存储结构（顺序表和链表）的，他们属于不同层面的概念

2、特点：

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

3、实现方式——顺序表、链表

3.1顺序表：线性表的顺序表示

逻辑上相邻的两个元素在物理位置上也相邻

以上代码描述：使用结构体定义， 数组一开始要定义好大小60，访问时通过下标，注意数组的长度和线性表的长度不一样

3.2优缺点：

优点：

• ➢可以随机存取(根据表头元素地址和元素序号)表中任意一个元素。
• ➢存储密度高，每个结点只存储数据元素。

缺点：

• ➢插入和删除操作需要移动大量元素。
• ➢线性表变化较大时，难以确定存储空间的容量。
• ➢存储分配需要一整段连续的存储空间，不够灵活。

3.3插入操作：7,6,5,4要往后移动一位，才把x插到4的位置

• 最好情况:在表尾插入元素，不需要移动元素，时间复杂度为O(1)。
• 最坏情况:在表头插入元素，所有元素依次后移，时间复杂度为O(n)。
• 平均情况:在插入位置概率均等的情况下，平均移动元素的次数为n/2，时间复杂度O(n)

• 时间复杂度O(n) 要把系数和一阶项都去掉

伪代码：

这里L就是定义出来的SqList 结构体的缩写

3.4 删除操作：5,6,7前移一位

•  ➢最好情况:删除表尾元素，不需要移动元素，时间复杂度为O(1)。
• ➢最坏情况:删除表头元素，之后的所有元素依次前移，时间复杂度为O(n)。
• ➢平均情况:在删除位置概率均等的情况下，平均移动元素的次数为(n-1)/2，时间复杂度为O(n)。

伪代码：

 注意：插入和删除的时候，变量i的范围是不一样的

3.5动态分配的数组属于顺序存储结构吗？

动态分配：int *p = malloc(sizeof(int )*20)，仍然属于顺序存储，物理结构没有变化，还是随机存取的，只是分配的空间可以在运行时决定，访问任意一个元素都可以通过地址 

【随机存取就是通过一个公式可以拿到任意一个元素】

【直接定义数组是在栈空间上的，申请动态分配的数组是在堆空间上，都支持随机存取】

 二、代码

顺序表的增、删、查

#include 
#include 
#include #define MAXSIZE 60
typedef int ElemType;//顺序表中的元素类型
//静态分配
typedef struct  {ElemType data[MAXSIZE];//定义的数组，用来存元素int length;//当前顺序表中的元素个数
}SqList;
/*插入*/
//参数：顺序表、插入位置、插入的元素
bool ListInsert(SqList &L,int i,ElemType elem)
{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-1]=elem;//插入第一个位置，访问的下标为0L.length++;//顺序表长度+1return true;
}
/*删除*/
//参数：顺序表、删除位置、删除的元素（要打印）
//elem使用引用是为了拿出删除元素对应的值
bool ListDelete(SqList &L,int i,ElemType &elem)
{if (i<1 || i>L.length){return false;}if (L.length == 0)//顺序表中无元素{return false;}elem = L.data[i-1];//删除的第i个元素赋值给elemfor (int j = i;j

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！