-
2022-04-16 20:51:01
1.什么是线性表?
线性表可以看作一条链子除了第一个元素和最后一个元素,其他每个元素都有一个前驱
元素和一个后继元素有且只有一个。
若一个元素都没有,则称为空表。
元素之间的关系是一一对应的关系。(就比如a2的前驱元素只有一个并且一定是a1,a2的后继元素也只有一个并且一定是a3)
2.线性表的顺序存储结构:
指用一段连续地址的存储单元依次存储线性表的数据元素。(就是用数组来存储线性表的数据元素)
定义一个顺序存储结构的线性表
typedef struct
{
type data[max]; //需要定义数组长度
int length; //线性表的当前长度,就是当前
// 线性表有几个元素
}
还要知道起始的位置,就是data的首地址
因为数组是从下标0开始计起的,所以线性表的第 i 个元素存储在数组的下标为 i-1 的位置
由于每个元素都有自己对应的下标位置且数组的第一个位置也是知道的,所以存入和读取数据的时间复杂度为O(1)。例如:把100存入第i个数据或读取第i个数据,只需找下标为 i-1 的元素进行存入或读取操作就行了,相当于执行了一次,所以算法复杂度为O(1)。
3.顺序存储结构的插入和删除
想一下在饭堂排队的情况,如果这时候有人插队,那么这个人后面的所有人都要向后移动一位。如果有个人看到另一队人少,就去排另一队了,那么这个人后面的所有人都向前移动一位。
顺序存储结构的插入和删除也是一样:
插入元素:
1.判断:如果元素插入的位置不合理或者线性表长度大于数组长度则抛出异常。 O(1)
2.移动:从最后一个元素遍历到第i个元素的位置,把它们分别向后移动一位。O(n)
3.插入元素:把新元素插入位置 i 。 O(1)
4.线性表长度+1。
删除元素:
1.判断:如果元素删除的位置不合理则抛出异常。 O(1)
2.删除元素:把位置 i 的元素取出,赋给*e。 O(1)
3.移动:从第 i+1 个元素遍历到最后一个元素,把它们分别向前移动一位。O(n)
4.线性表长度 -1。
由上面可以看出顺序存储结构在存入、读取数据时的时间复杂度为O(1),而插入或删除元素时的时间复杂度为O(n)。说明它比较适合元素个数不太变化,而更多是存储数据的应用。
更多相关内容 -
C语言线性表顺序存储结构实例详解
2020-08-30 03:47:12主要介绍了C语言线性表顺序存储结构实例详解的相关资料,需要的朋友可以参考下 -
线性表顺序存储结构实现通讯录
2011-04-01 23:33:49C++数据结构 线性表顺序存储结构实现通讯录 -
线性表定义 && 线性表顺序存储结构
2020-09-15 08:29:22文章目录线性表的定义线性表的顺序存储结构线性表顺序存储结构的优缺点线性表的基本操作顺序存储结构数据的插入和删除 线性表的定义 线性表:由零个或多个数据元素组成的有限序列。简单的说,就像排队一样,具有先...写在前面:本文章来自于在学习过程中的总结,供大家参考。因水平有限,博客中难免会有不足,恳请大佬们不吝赐教!
线性表的定义
线性表:由零个或多个数据元素组成的有限序列。简单的说,就像排队一样,具有先一样性质的结构。
关键:
- 首先它是一个序列,也就是说元素之间是有个先来后到的。
- 若元素存在多个,则第一个无前驱,而最后一个元素无后继,其他元素有且只有一个前驱和后继。
- 另外,线性表强调是有限的,事实上无论计算机发展到多强大,它所处理的元素都是有限的。
数据元素的个数称为线性表的长度,当线性表长度为零时,称为空表。
表起始位置称表头,表结束位置称表尾。
线性表的顺序存储结构
线性表有两种物理存储结构 :顺序存储结构和链式存储结构。
线性表的顺序存储结构:用一段地址连续的存储单元依次存储线性表的数据元素。
物理上的存储方式事实上就是在内存中找个初始地址,然后通过占位的形式,把一定的内存空间给占了,然后把相同数据类型的数据元素依次放在这块空地中。
#define MAXSIZE 20 typedef int ElemType; typedef struct { ElemType data[MAXSIZE]; int length; //线性表当前长度 }SqList;
这里封装了一个结构,事实上就是对数组进行封装,增加了当前长度的变量罢了。
顺序存储结构的封装需要三个属性:
- 存储空间的起始位置,数组data,它的存储位置就是线性表存储空间的存储位置。
- 线性表的最大存储容量:数组的长度MAXSIZE
- 线性表的当前长度:length
注意:数组的长度与线性表的当前长度要区分一下:数组的长度是存放线性表的存储空间的总长度,一般初始化后不变。而线性表的当前长度是线性表中元素的个数,是会变化的。
线性表顺序存储结构的优缺点
线性表的顺序存储结构,在存、读数据时,不管是在哪个位置时,时间复杂度都是O(1)。而在插入或删除时,时间复杂度都是O(n)。
这就说明,它比较适合元素个数比较稳定,不经常插入和删除元素,而更多的操作是存取数据的应用。
优点:
- 无须为表示元素之间的逻辑关系而增加额外的存储空间。
- 可以快速存取表中任意位置的元素。
缺点: - 插入和删除操作需要移动大量元素。
- 当线性表长度变化较大时,难以确定存储空间的容量。
- 容易遭成存储空间的“碎片”。
为什么当插入和删除时,就要移动大量的元素?因为在相邻两元素的存储位置也具有邻居关系,它们在内存中的位置是紧挨着的,中间没有间隙,当然就无法快速插入和删除。
线性表的基本操作
顺序存储结构数据的插入和删除
数据的插入:
//数据元素的插入 Status ListInsert(SqList* L, int i, ElemType e) { int k; if (L->length == MAXSIZE) //顺序线性表已满 return ERROR; if (i<1 || i>L->length - 1) //当i不在范围内时 return ERROR; if (i <= L->length) //若插入数据位置不在表尾 { for (k = L->length - 1; k >= i - 1; k--) L->data[k + 1] = L->data[k]; } L->data[i - 1] = e; L->length++; return OK; }
数据的删除:
//数据元素的删除 Status ListDelete(SqList* L, int i) { int k; if (L->length == 0) //线性表为空 return ERROR; if (i<1 || i>L->length) //当i不在范围时 return ERROR; if (i < L->length) //如果删除不是最后位置 { for (k = i; k < L->length; k++) //将删除位置后继元素前移 L->data[k - 1] = L->data[k]; } L->length--; return OK; }
完整代码:
#include <stdio.h> #include <malloc.h> #define MAXSIZE 20 typedef int ElemType; typedef struct { ElemType data[MAXSIZE]; int length; }SqList; #define OK 1 #define ERROR 0 #define TURE 1 #define FALSE 0 typedef int Status; //数据元素的获取 Status GetElem(SqList L, int i, ElemType* e) { if (L.length == 0 || i<1 || i>L.length) return ERROR; *e = L.data[i - 1]; return OK; } //数据元素的插入 Status ListInsert(SqList* L, int i, ElemType e) { int k; if (L->length == MAXSIZE) //顺序线性表已满 return ERROR; if (i<1 || i>L->length - 1) //当i不在范围内时 return ERROR; if (i <= L->length) //若插入数据位置不在表尾 { for (k = L->length - 1; k >= i - 1; k--) L->data[k + 1] = L->data[k]; } L->data[i - 1] = e; L->length++; return OK; } //数据元素的删除 Status ListDelete(SqList* L, int i) { int k; if (L->length == 0) //线性表为空 return ERROR; if (i<1 || i>L->length) //当i不在范围时 return ERROR; if (i < L->length) //如果删除不是最后位置 { for (k = i; k < L->length; k++) //将删除位置后继元素前移 L->data[k - 1] = L->data[k]; } L->length--; return OK; } int main() { SqList *L; int i = 0; L = (SqList*)malloc(sizeof(SqList)); L->length = 0; for (i = 0; i < 3; i++) { scanf("%d", &L->data[i]); L->length++; } //ListInsert(L, 1, 4); ListDelete(L, 1); printf("%d\n", L->length); for (i = 0; i < L->length; i++) { printf("%d\n", L->data[i]); } return 0; }
由于水平有限,博客难免会有不足,恳请大佬们不吝赐教!
-
数据结构实验指导书,线性表顺序存储结构的操作
2011-05-30 21:53:19线性表顺序存储结构的操作及其应用实验,编写C语言描述的线性表操作的12种算法的顺序存储结构实现的代码; -
线性表顺序存储结构的基本实现
2020-04-14 17:34:14那么这一篇博客我们就来说说线性表的两种物理结构中的第一种—顺序存储结构。 一、顺序存储定义 线性表的顺序存储结构指的是用一段地址连续的存储单元依次线性表的数据元素。顺序存储的示意图如下: 二、线性表的...在上一篇博客中我们只是简单得了解了线性表的一些基本的概念。那么这一篇博客我们就来说说线性表的两种物理结构中的第一种—顺序存储结构。
一、顺序存储定义
线性表的顺序存储结构指的是用一段地址连续的存储单元依次线性表的数据元素。顺序存储的示意图如下:
二、线性表的地址计算方法
由于c语言的数组的下标是从0开始的,所以线性表第i个元素存储在第i-1的位置。如下图所示:
由于每个数据元素,不管它是整型还是字符型。都占有一定的存储单元空间。假设占用的是c个单位的存储单元。那么线性表中第i+1个元素的存储位置和第i个元素的存储位置满足以下条件。
LOC(a(i+1)) = LOC(ai) + c
则可以推断出第i个元素ai的位置由a1计算得出:
LOC(ai) = LOC(a1) + (i-1)*c
三、顺序存储结构的插入和删除等操作
1、获取元素(GetElem):既将线性表的第i个元素的下标返回。int GetElem (SqList L,int i,ElemType *e) { if (L->length==0 || i<l || i>L->length) return 0; else return *e=L->data[i-1];
2、插入操作(ListInsert):
(1)如果插入位置不合理,返回0;
(2)如果线性表长度大于等于数组长度,返回0;
(3)从最后一个元素开始向前遍 历到第i个位置,分别将它们都向后移动一个位置;
(4)将要插入元素填入位置i处;
(5)表长加1。
代码实现:bool ListInsert ( SqList *L, int i, ElemType e ) { int k; if (L->length==MAXSIZE)/*顺序线性表已经满*/ return false; if(i<1 || i>L->length+1) /*当i不在范围内时*/ return false; if (i<=L->length) /*若插入数据位置不在表尾*/ { for (k=L->length-1;k>=i-1;k--)/*将要插入位置后数据元素向后移动一位*/ L->data[k+1]-L->data[k]; } L->data[i-1]=e;/*将新元素插入*/ L-> length++; return true; }
3、删除操作(ListDelete)
(1)如果删除位置不合理,return 0;
(2)取出删除元素;
(3)从删除元素位置开始遍历到最后一个元素位置,分别将它们都向前移动一个位置;
(4)表长减1。
代码实现:bool ListDelete (SqList *L,int i, ElemType *e) { int k; if (L->length==0 )//线性表为空 return false; if (i<1 || i>L->length)//删除位置不对 return false; *e-L->data(i-1]; if ( i<L->length )//如果删除不是最后位置 { for (k=i;k<L->length;k++) //将删除位置后继元素后移 L->data[k-1]=L->data [k]; } L-> length--; return true; }
四、顺序存储结构的优缺点
优点:1、不用为表中的元素之间的逻辑关系而增加额外的存储空间。
2、可以快速存取表中任意位置的元素。
缺点:1、删除和插入需要移动大量的元素。
2、当长度变化较大时无法确定存储空间的容量。 -
4.线性表顺序存储结构.pdf
2021-05-21 11:07:014.线性表顺序存储结构.pdf -
c代码-线性表顺序存储结构
2021-07-16 12:02:21c代码-线性表顺序存储结构 -
数据结构——线性表顺序存储结构(C++代码)
2011-09-28 10:39:34简单的线性表顺序存储的示例,代码主要完成在顺序存储中的插入及删除元素的操作。 本程序在VS2008下编译通过 -
线性表的顺序存储结构
2021-10-21 22:05:32说这么多的线性表,我们来看看线性表的两种物理结构的第一种——顺序存储结构。 线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素。线性表(a1,a2……,an)的顺序存储示意图如下: 顺序...顺序存储定义
说这么多的线性表,我们来看看线性表的两种物理结构的第一种——顺序存储结构。
线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素。线性表(a1,a2……,an)的顺序存储示意图如下:顺序存储方式
线性表的顺序存储结构,说白了,就是在内存中找了块地儿,通过占位的形式,把一定内存空间给占了,然后把相同数据类型的数据元素依次存放在这块空地中。既然线性表的每个数据元素的类型都相同,所以可以用C语言(其他语言也相同)的一维数组来实现顺序存储结构,即把第一个数据元素存到数组下标为0的位置中,接着把线性表相邻的元素存储在数组中相邻的位置。
线性表中,我们估算这个线性表的最大存储容量,建立一个数组,数组的长度就是这个最大存储容量。但在实际使用中,我们并不是每个时刻都使用这最大的存储容量,我们希望能够更加高效的使用空间,因此我们使用malloc申请空间,realloc来调整空间大小,做到此点。可看空间分配与释放来具体了解函数作用。
来看线性表的顺序存储的结构代码。
#define INITSIZE 20 //初始化的大小 #define EXPANDTIMES 2 //每次的扩容倍数 typedef int ELemType; //用int来模拟数据项类型 typedef struct { ElemType* data; //存储数据的初始位置 int capacity; //容量(总共的:未使用的+已经使用的) int size;//已经使用的 }Sqlist;
关于数组和指针我在这就不多讲了,想要了解的可以去看我的数组与指针。
Init_List(*L)
bool Init_List(Sqlist *L) { assert(L != NULL);//对输入也检测一下,使用空指针可能会导致程序奔溃,具体原因自己去搜,后续不解释 L->data = (int*)malloc(sizeof(ELemType) * INITSIZE);//申请一段堆空间来存储元素 //assert(L->data != NULL);//因为malloc可能会申请失败,判断一下 if (L->data == NULL) { return false; } else { L->capacity = INITSIZE;//初始容量通过宏定义设定 L->size = 0;//初始使用的大小当然是0喽 return true; } }
为了能够拥有动态空间大小,我们在这使用了堆空间作为存储空间,不用了记得free
Change_List(*L, flag)
bool Change_List(Sqlist* L,int flag)//改变容量 { assert(L != NULL); ELemType* temp = L->data; int newsize = flag == -1 ? L->capacity / EXPANDTIMES : L->capacity * EXPANDTIMES;//简单的判断, temp = (ELemType*)realloc(temp,newsize * sizeof(ELemType));//扩容也可能会失败,这样做是防止旧数据丢失 if (temp == NULL) { return false; } else { L->data = temp;//将申请到的空间交给data L->capacity = newsize;//更改容量 return true; } }
Is_Empty(*L)
bool Is_Empty(Sqlist* L) { assert(L != NULL); return L->size == 0;//只用检测一下使用的大小为不为0,就ok }
Clear_List(*L)
bool Clear_List(Sqlist* L) { assert(L != NULL); free(L->data);//因为空间是malloc来的,不用就free掉 Init_List(L);//最简单的做法,重新给他初始化下,就消除了数据,也缩小了容量 //L->size = 0;//最最最简单的方法因为数据是否有效,我们说了算,容量没变 return true; }
GetElem_List(*L,i)
ELemType GetElem_List(Sqlist* L, int i) { assert(L != NULL && i < L->size && i >= 0);//保证改下标必须为有效下标,后续不解释 return L->data[i]; }
LocateElem_List(*L,e)
int LocateElem_List(Sqlist* L, ELemType e) { assert(L != NULL); int pos = -1; for (int i = 0; i < L->size; i++)//遍历是必须的 { if (e == L->data[i]) { pos = i; break; } } return pos; }
Insert_List(*L,i,e)
bool Insert_List(Sqlist* L,int i,ELemType e) { assert(L != NULL && i >= 0 && i <= L->size);//为满足线性表的定义,应对下标进行检测 if (L->capacity == L->size)//容量不足是需要进行扩容 { if (!Change_List(L,1)) //扩容成功才能继续放数据 { return false; } } int pos = L->size; while (L->size != i)//向后挪动一位 { L->data[pos] = L->data[pos - 1]; pos--; } L->data[pos] = e; L->size++; return true; }
尾插的话,i=L->size;头插i=0;
Delect_List(*L, i)
与插入反向操作
bool Delect_List(Sqlist* L, int i)// { assert(L != NULL && i < L->size && i >= 0); while (i != L->size-1)//向前挪动一位 { L->data[i] = L->data[i+1]; i++; } L->size--; if (L->capacity > INITSIZE && L->size < L->capacity / EXPANDTIMES) Change_List(L, -1); return true; }
Length_List(*L)
int Length_List(Sqlist* L) { assert(L != NULL); return L->size;//我们有专门的数据项来记录长度,直接返回就行 }
Destory_List(*L)
因为clear只会清除数据(存储空间有一部分清不掉),我们要专门free掉
bool Destroy_List(Sqlist* L) { L->capacity = 0; L->size = 0; free(L->data);//Destroy以后就彻底不能用了,因为0乘以任何数还是0 L->data = NULL; return true; }
线性表顺序存储结构的优缺点
优点
无须为表示表中元素之间的逻辑关系而增加额外的存储空间。
可以快速地存取表中任位置的元素。(顺序读取快,O(1));缺点
插入和删除操作需要移动大量元素 O(n)
当线性表长度变化较大时,难以确定存储空间的容量 (用数组就是这样,所以我们有扩容/缩容)
造成存储空间的“碎片”(绝大部分时间capacity > size,有一部分空间闲置) -
线性表顺序存储结构的插入和删除
2020-09-10 23:13:151、顺序链表的插入操作。 Status ListInsert(SqList *L,int i,ElemType e) { int k; if(L->length == MAXSIZE)//顺序链表已经满了 { return ERROR; } if(i <= 1 || i>L->length+1)//当i不在这个... -
《数据结构与算法》——线性表顺序存储结构的插入与删除
2020-03-14 15:42:38对于线性表的顺序存储结构来说,如果我们要实现GetElem操作,即将线性表L中的第i个 位置元素值返回,其实是非常简单的。就程序而言,只要i的数值在数组下标范围内,就 是把数组第i-1下标的值返回即可。 来看代码:... -
数据结构线性表顺序存储结构和主要算法实现
2019-11-29 01:05:25(1) 线性表的定义。 零个或多个数据元素的有限序列 序列线性表中有直接后继元素,有且仅有一个直接后继,有且仅有一个直接前驱,数据元素之间的关系是一对一的关系 常用的List操作: Operation InitList(*L)://... -
线性表顺序存储结构的优缺点
2014-07-21 23:07:10优点:1、无须为表示表中元素之间的逻辑关系而增加额外的存储空间。... 2、当线性表长度变化较大时,难以确定存储空间的容量。 3、造成存储空间的“碎片”。 ============================== -
数据结构--线性表的顺序存储结构(c语言实现)
2018-06-17 12:04:38c语言实现的线性表顺序存储结构,包括初始化,设置线性表的值,增,删,改,查。 -
线性表顺序存储结构下基本操作的实现(初始化、赋值、取值、插入、删除、归并等)
2019-01-01 17:36:34printf("请输入顺序表中元素的个数:"); scanf("%d",&N); printf("请输入顺序表中的元素:"); for(i=0; i; i++) { scanf("%d",&L.elem[i]); L.length++; } } void ListTraverse(SqList L) { //遍历序表顺L... -
线性表顺序存储结构——查找、插入、删除的平均比较/移动次数&时间复杂度计算
2020-04-02 18:41:27假设线性表长度为n 查找 查找特定元素x,最好的情况是第一个位置就找到,最坏的情况是最后一个位置找到。 总的比较次数是:1+2+…+n,即n(n+1)2\frac{n(n+1)}{2}2n(n+1); 元素x共有n种位置; 则:平均... -
线性表的顺序存储结构创建
2020-10-23 21:09:41线性表的顺序存储结构 定义: 指的是用一段地址连续的存储单元依次存储线性表的数据元素. 优点: 无需为表示表中元素之间逻辑关系而增加额外存储空间 可快速存取表中任意一个位置的元素值 缺点: 插入和删除需要移动... -
数据结构:线性表顺序存储
2020-09-08 22:04:36文章目录一、线性表(List):0个或多个数据结构的有限序列二、线性表的顺序存储结构1.顺序存储定义2.顺序存储方式3.顺序存储结构的插入与删除总结 一、线性表(List):0个或多个数据结构的有限序列 这里要强调几... -
线性表顺序存储结构的实现
2018-04-14 13:00:49线性表是一个有序序列,若元素存在多个,则第一...线性表有两种物理结构,第一种为顺序存储结构,另一种为链式存储结构。这一章先来利用C++实现顺序存储结构。 头文件声明lineartable.h #pragma once /* 线性... -
线性表的顺序存储结构C语言版
2021-05-19 15:20:02算法: #include 线性表之顺序存储结构(C语言动态数组实现) 线性表的定义:N个数据元素的有限序列 线性表从存储结构上分为:顺序存储结构(数组)和 链式存储结构(链表) 顺序存储结构:是用一段连续的内存空间存储表中的...