-
1.2 线性表的顺序表示
-
一.顺序表的定义
线性表的顺序存储有称之为顺序表。它是用一组地址连续的存储单元,依次存储线性表的数据元素,从而使得逻辑上相邻的两个元素在物理上也相邻。第一个元素存储在线性表的起始位置,第i个元素的存储位置后面紧接着存储的时第i+1个元素。
因此,顺序表的特点时表中元素的逻辑顺序与物理顺序相同。
这里,我们假定元素类型为ElemType,线性表的顺序存储类型则可以描述为:
#define MaxSize 50; typedef struct{ ElemType data[MaxSize]; int length; }SqList;
这种描述有时也称为“柔性数组”。这里说明下,《数据结构与算法》中其他章节的描述部分均采用的是C语言。
一维数组可以是静态分配的,也可以是动态分配的。
在静态分配时,由于数组的大小和空间事先已经确定,一旦空间占满,再加入新的数据将会产生溢出,导致程序崩溃。比如上述描述便是采用静态分配。
当采用动态分配时,存储数组的空间是在程序执行过程中通过动态存储分配语句分配的,一旦数据空间占满,可以另外开辟一块更大的存储空间,用以替换原来的空间,从而达到扩充数组空间的目的,因此不需要一次性划分所有的所需空间给线性表,具体描述如下:
#define InitSize 100 typedef struct{ ElemType *data; int MaxSize, length; }SeqList; 初始的动态分配语句为 L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);
因为顺序表采用的时顺序存储,因此具有顺序存储的几个重要特点:
具有随机访问特性,即通过首地址和元素序号可以在O(1)的时间内找到指定元素;
存储密度高,每个节点只存储数据元素;
逻辑上相邻的元素物理上同样相邻,所以插入和删除操作需要移动大量元素。
二.顺序表上基本操作的实现
在顺序表L的第i(1≤i≤L.length+1)个位置插入新新元素e,如果i的输入不合法,则返回-1,表示插入失败;否则,将顺序表的第i个元素以及其后的元素右移一个位置,腾出一个空位置插入新元素e,顺序表长度加1,插入成功,返回0;
int ListInsert(SqList *L, int i, int e) { if(i<0||i>L->length){ printf("The postion is out of border! \n"); return -1; }else if(L->length>=MaxSize){ printf("The length more over MaxSize! \n"); return -1; }else{ int j; for(j=L->length;j>=i;j--){ L->data[j]=L->data[j-1]; } L->data[j]=e; L->length++; return 0; } }
我们分析下时间复杂度:
最佳情况:在表尾直接插入(即i=n+1),无需移动任何元素,则时间复杂度为O(1);
最坏情况:在表头插入即(即i=1),每个元素后移一位,即移位语句执行n次,事件复杂度为O(n);
平均情况:假设pi(pi=1(n+1))是在第i个位置上插入一个节点的概率,则在长度为n的线性表中插入一个节点时所需移动节点的平均次数为
∑i=1n+1pi(n−i+1)=∑i=1n+11n+1(n−i+1)=1n+1∑i=1n+1(n−i+1)=1n+1n(n+1)2=n2
因此,线性插入算法的平均事件复杂度为O(n)。
2.2删除操作
删除顺序表L中第i(1≤i≤L.length)个位置的元素,成功返回0,否则返回-1,并将被删除的元素采用指针调用的方式返回。
int ListDelete(SqList *L, int i, ElemType *e) { if(i<0||i>L->length){ printf("The position over the border! \n"); return -1; } *e=L->data[i-1]; for(int j=i;j<L->length;j++){ L->data[j-1]=L->data[j]; } L->length--; return 0; }
分析下时间复杂度:
最佳情况:删除表尾元素(即i=n),无需移动任何元素,则时间复杂度为O(1);
最坏情况:删除表头元素(即i=1),需要移动除第一个元素外的所有元素,即移位语句执行n次,事件复杂度为O(n);
平均情况:假设pi(pi=1n)是删除第i个位置上节点的概率,则在长度为n的线性表中删除一个节点时所需移动节点的平均次数为
∑i=1npi(n−i)=∑i=1n1n(n−i)=1n∑i=1n(n−i)=1nn(n−1)2=n−12
因此,线性删除算法的平均事件复杂度为O(n)。
2.3按值查找(顺序查找)
在顺序表L中查找第一个元素值等于e的元素,并返回其下标,否则返回-1.
int LocateElem(SqList *L, ElemType e) { for(int i=0;i<L->length;i++){ if(L->data[i]==e){ printf("The elem is found!The Postion is %d !", i+1); return i+1; } } printf("The elem isn't found!\n"); return -1; }
最佳情况:需要查找的元素就在表头,仅需比较一次,其时间复杂度为O(1);
最坏情况:需要查找的元素就在表尾,需要比较n次,时间复杂度为O(n);
平均情况:假设pi(pi=1n)是查找第i个位置上节点的概率,则在长度为n的线性表中查找值为e时所需比较的平均次数为
∑i=1npi×i=∑i=1n1n×i=1n∑i=1n(n−i)=1n×n(n+1)2=n+12
因此,线性删除算法的平均事件复杂度为O(n)。
- 留下你的读书笔记
- 你还没登录,点击这里
-
用户笔记留言