数据结构导论-2.1 线性表的顺序存储

灰太狼 2022-05-08 13:42 200阅读 0赞

**线性表顺序存储的类型定义：**

> Const Int Maxsize=100 //预先定义一个足够大的常数
> 
> typedef struct
> 
> \{ datatype data\[Maxsize\]; //存放数据的数组
> 
> int length; //顺序表的实际长度
> 
> \} SeqList; //顺序表的类型为SqeList
> 
> SeqList L; //定义L为一个顺序表

**顺序表的插入算法描述：**

> void InsertSeqList(SeqList L, DataType x, int i)
> 
> \{ int j;
> 
> if (L.length==maxsize) exit\{"表满"); //表空间已满，不能插入
> 
> if (i<1 || i>L.length+1) exit("位置错") ; //检查插入位置的正确性
> 
> for (j=L.length; j>=i; j--)
> 
> L.data\[j\]=L.data\[j-1\];  //\*结点向后移动
> 
> L.data\[i-1\]=x; //新元素插入
> 
> L.length++; //表长+1
> 
> \}

**顺序表的删除算法描述：**

> void DeleteSeqList(SeqList L, int i)
> 
> \{ int j;
> 
> if (i<1 || i>L.length) exit("非法位置") ; //检查位置是否合法
> 
> for (j=i; j<L.length; j++)
> 
> L.data\[j-1\]=L.data\[j\]; //\*结点向前移动
> 
> L.length--; //表长-1
> 
> \}

**顺序表的定位算法描述：**

> int LocateSeqList(SeqList L, DataType x)
> 
> \{ int i=0;
> 
> While ((i<L.length) && (L.data\[i\]!=x)) //顺序检查数据元素值为x的结点
> 
> i++;
> 
> if (i<L.length) return i+1; //查找成功，返回数据元素的序号
> 
> else return 0; //查找不成功，返回0
> 
> \}

**顺序表的求表长,读表元素运算**

顺序表的求表长操作Length(L)直接输出L.length即可。

顺序表的读表元素Get(L，i)直接输出L.data\[i-1\]即可。

**顺序表的时间复杂度**

顺序表的插入算法的时间复杂度为Ｏ(n)

顺序表的删除算法的时间复杂度为Ｏ(n)

顺序表的定位算法的时间复杂度为Ｏ(n)

顺序表的求表长和读表元素的时间复杂度为O(1)

**【顺序表算法设计举例】：**

有顺序表A和B，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表C，要求C的元素也是从小到大的升序排列。

算法思路分析：

依次扫描通过A和B的元素，比较当前的元素的值，将较小值的元素赋给C，如此直到一个线性表扫描完毕，然后将未完的那个顺序表中余下部分赋给C即可。C的容量要能够容纳A、B两个线性表相加的长度。

算法描述：

> void merge(SeqList A, SeqList B, SeqList C)
> 
> \{   int i,j,k;
> 
> i=0; j=0; k=0;
> 
> while ( i<A.length && j<B.length ) //将A和B的当前元素较小者复制到表C
> 
> if (A.data\[i\]<B.data\[j\])
> 
> C.data\[k++\]=A.data\[i++\];
> 
> else C.data\[k++\]=B.data\[j++\];
> 
> while (i<A.length ) /\*将A中剩余元素复制到表C\*/
> 
> C.data\[k++\]= A.data\[i++\];
> 
> while (j<B.length ) /\*将B中剩余元素复制到表C \*/
> 
> C.data\[k++\]=B.data\[j++\];
> 
> C.length=k;
> 
> \}