|
顺序表上实现的基本运算 表的初始化 void InitList（SeqList *L） {\\顺序表的初始化即将表的长度置为 L＞length= } 求表长 int ListLength（SeqList *L） { \\求表长只需返回L＞length return L＞length; } 取表中第i个结点 DataType GetNode（Li） {\\取表中第i个结点只需返回和L＞data[i]即可 if (i<||i> L＞length) Error(position error) return L＞data[i] } 查找值为x的结点 【参见参考书】 插入 （） 插入运算的逻辑描述线性表的插入运算是指在表的第i（≤i≤n+）个位置上插入一个新结点x使长度为n的线性表 （a…aiai…an） 变成长度为n+的线性表 （a…aixai…an） 注意 ① 由于向量空间大小在声明时确定当L＞length≥ListSize时表空间已满不可再做插入操作 ② 当插入位置i的值为i＞n或i＜时为非法位置不可做正常插入操作 （） 顺序表插入操作过程在顺序表中结点的物理顺序必须和结点的逻辑顺序保持一致因此必须将表中位置为n n…i上的结点依次后移到位置n+n…i+上空出第i个位置然后在该位置上插入新结点x仅当插入位置i=n+时才无须移动结点直接将x插入表的末尾 具体过程见【动画演示】 （）具体算法描述 void InsertList(SeqList *LDataType xint i) {//将新结点 x插入L所指的顺序表的第i个结点ai的位置上 int j; if (i<||i>L>length+) Error(position error);//非法位置退出运行 if (L>length>=ListSize) Error(overflow); //表空间溢出退出运行 for(j=L>length;j>=i;j) L>data[j+]=L>data[j];//结点后移 L>data[i]=x; //插入x L>Length++; //表长加 } （）算法分析① 问题的规模 表的长度L＞length（设值为n）是问题的规模 ② 移动结点的次数由表长n和插入位置i决定 算法的时间主要花费在for循环中的结点后移语句上该语句的执行次数是ni+ 当i=n+移动结点次数为即算法在最好时间复杂度是() 当i=移动结点次数为n即算法在最坏情况下时间复杂度是(n) ③ 移动结点的平均次数Eis(n) 其中 在表中第i个位置插入一个结点的移动次数为ni+ pi表示在表中第i个位置上插入一个结点的概率不失一般性假设在表中任何合法位置（≤i≤n+）上的插入结点的机会是均等的则 p=p=…=pn+=/(n+) 因此在等概率插入的情况下 即在顺序表上进行插入运算平均要移动一半结点 ． 删除 （）删除运算的逻辑描述 线性表的删除运算是指将表的第i（≤i≤n）个结点删去使长度为n的线性表 （a…aiaiai+…an） 变成长度为n的线性表 （a…aiai+…an） 注意 当要删除元素的位置i不在表长范围（即i＜或i＞L＞length）时为非法位置不能做正常的删除操作 （）顺序表删除操作过程 在顺序表上实现删除运算必须移动结点才能反映出结点间的逻辑关系的变化若i=n则只要简单地删除终端结点无须移动结点若≤i≤n则必须将表中位置i+i+…n的结点依次前移到位置ii+…n上以填补删除操作造成的空缺其删除过程【参见动画演示】 （）具体算法描述 void DeleteList(SeqList *Lint i) {//从L所指的顺序表中删除第i个结点ai int j; if(i<||i>L>length) Error(position error); //非法位置 for(j=i;j<=L>length;j++) L>data[j]=L>data[j]; //结点前移 L>length; //表长减小 } （）算法分析 ①结点的移动次数由表长n和位置i决定 i=n时结点的移动次数为即为() i=时结点的移动次数为n算法时间复杂度分别是(n) ②移动结点的平均次数EDE(n) 其中 删除表中第i个位置结点的移动次数为ni pi表示删除表中第i个位置上结点的概率不失一般性假设在表中任何合法位置（≤i≤n）上的删除结点的机会是均等的则 p=p=…=pn=/n 因此在等概率插入的情况下 顺序表上做删除运算平均要移动表中约一半的结点平均时间复杂度也是(n) |
