[数据结构与算法]数据结构！

数据结构

数据表的顺序表示和实现

1.线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。

2.线性表的插入操作

？？？什么时候不能插入？

表满：length>=MaxSize

合理插入位置：1<=i<=length+1(i指的是元素的位序)

！一般情况下，在第i（1<=i<=n)个元素之前插入一个元素时，需将第n至i（共n-i+1)个元素向后移动一个位置。

实现步骤：

• 将第n至i位的元素向后移动一个位置；

• 将要插入的元素写到第i个位置；

• 表长加1

注意：事先应判断：

插入位置i是否合法？应当有1<=i<=n+1

表是否已满？ 若满，增加分配

核心语句：

q=&(L.elem[i-1]);

for(p=&(L.elem[L.length-1]);p>=q;--p);

*(p+1)= *p; //插入位置及之后元素右移一个位置

*q=e; //插入e

++L.length; //表长加1

3.线性表的删除操作

？？？什么时候不能删除？

合理的删除位置：1<=i<=length (i指的是元素的位序)

！一般情况下，删除第i（1<=i<=n)个元素时，需将第i+1至第n（共n-i)个元素依次向前移动一个位置。

实现步骤：

• 将要删除的元素记录；

• 将第i+1至第n位的元素向前移动一个位置；

• 表长减1

注意：事先应判断：

删除位置i是否合法？ 应当有1<=i<=n

核心语句：

p=&(L.elem[i-1]); //p为被删除元素的位置

e=*p; //被删除元素赋给e

q=L.elem+L.length-1; //表尾元素位置

for(++p;p<=q;++p)

*(p-1) = *p; //被删除元素之后的元素左移一个位置

--L.length; //表长减一