顺序表上实现的基本运算

1.表的初始化
void InitList(SeqList *L)
{\\顺序表的初始化即将表的长度置为0
L->length=0;
}

2.求表长
int ListLength(SeqList *L)
{ \\求表长只需返回L->length
return L->length;
}

3.取表中第i个结点
DataType GetNode(L,i)
{\\取表中第i个结点只需返回和L->data[i-1]即可
if (i<1||i> L->length-1)
Error(“position error”);
return L->data[i-1];
}

4.查找值为x的结点
【参见参考书】

5. 插入
(1) 插入运算的逻辑描述
  线性表的插入运算是指在表的第i(1≤i≤n+1)个位置上,插入一个新结点x,使长度为n的线性表:
(a1,…,ai-1,ai,…an
变成长度为n+1的线性表:
(a1,…,ai-1x,ai,…an
注意:
① 由于向量空间大小在声明时确定,当L->length≥ListSize时,表空间已满,不可再做插入操作
② 当插入位置i的值为i>n或i<1时为非法位置,不可做正常插入操作

(2) 顺序表插入操作过程
  在顺序表中,结点的物理顺序必须和结点的逻辑顺序保持一致,因此必须将表中位置为n ,n-1,…,i上的结点,依次后移到位置n+1,n,…,i+1上,空出第i个位置,然后在该位置上插入新结点x。仅当插入位置i=n+1时,才无须移 动结点,直接将x插入表的末尾。
具体过程见【动画演示

(3)具体算法描述
   void InsertList(SeqList *L,DataType x,int i)
{//将新结点 x插入L所指的顺序表的第i个结点ai的位置上
int j;
if (i<1||i>L->length+1)
Error(“position error”);//非法位置,退出运行
if (L->length>=ListSize)
Error(“overflow”);     //表空间溢出,退出运行
for(j=L->length-1;j>=i-1;j–)
L->data[j+1]=L->data[j];//结点后移
L->data[i-1]=x;      //插入x
L->Length++;        //表长加1
}

(4)算法分析
① 问题的规模
表的长度L->length(设值为n)是问题的规模。
② 移动结点的次数由表长n和插入位置i决定
算法的时间主要花费在for循环中的结点后移语句上。该语句的执行次数是n-i+1。
当i=n+1:移动结点次数为0,即算法在最好时间复杂度是0(1)
当i=1:移动结点次数为n,即算法在最坏情况下时间复杂度是0(n)
③ 移动结点的平均次数Eis(n)

其中:
在表中第i个位置插入一个结点的移动次数为n-i+1
pi表示在表中第i个位置上插入一个结点的概率。不失一般性,假设在表中任何合法位置(1≤i≤n+1)上的插入结点的机会是均等的,则
p1=p2=…=pn+1=1/(n+1)

因此,在等概率插入的情况下,


即在顺序表上进行插入运算,平均要移动一半结点。

6. 删除
(1)删除运算的逻辑描述
线性表的删除运算是指将表的第i(1≤i≤n)个结点删去,使长度为n的线性表
(a1,…,ai-1ai,ai+1,…,an
变成长度为n-1的线性表
(a1,…,ai-1,ai+1,…,an
注意:
当要删除元素的位置i不在表长范围(即i<1或i>L->length)时,为非法位置,不能做正常的删除操作

(2)顺序表删除操作过程

在顺序表上实现删除运算必须移动结点,才能反映出结点间的逻辑关系的变化。若i=n,则只要简单地删除终端结点,无须移动结点;若1≤i≤n-1,则必 须将表中位置i+1,i+2,…,n的结点,依次前移到位置i,i+1,…,n-1上,以填补删除操作造成的空缺。其删除过程【参见动画演示

(3)具体算法描述
void DeleteList(SeqList *L,int i)
      {//从L所指的顺序表中删除第i个结点ai
int j;
if(i<1||i>L->length)
Error(“position error”); //非法位置
for(j=i;j<=L->length-1;j++)
L->data[j-1]=L->data[j]; //结点前移
L->length–;                //表长减小
}

(4)算法分析

①结点的移动次数由表长n和位置i决定:
i=n时,结点的移动次数为0,即为0(1)
i=1时,结点的移动次数为n-1,算法时间复杂度分别是0(n)
②移动结点的平均次数EDE(n)

其中:
删除表中第i个位置结点的移动次数为n-i
pi表示删除表中第i个位置上结点的概率。不失一般性,假设在表中任何合法位置(1≤i≤n)上的删除结点的机会是均等的,则
p1=p2=…=pn=1/n

因此,在等概率插入的情况下,

顺序表上做删除运算,平均要移动表中约一半的结点,平均时间复杂度也是0(n)。

Tagged on:

发表评论