template <class Type> int Seqlist<Type>: Insert(Type &x int 1) 将x插入表中i处,若成功返回1,否则返回0 if(i<oli>last+ l last==Maxsize-1)return 0 last++ for(int j=last ]>1: j--)data[]=datalj-1] datai=-X, return 1 2021222
2021/2/22 16 template <class Type> int Seqlist<Type>::Insert(Type & x, int i) //将 x 插入表中 i 处，若成功返回 1 ，否则返回 0 { if (i<0||i>last+1||last==Maxsize-1) return 0; else { last++; for(int j=last;j>i;j--) data[j]=data[j-1]; data[i]=x; return 1; } }
(4)顺序表删除操作 为了删除第i个元素,必须把从i+1到last的所有元素 向前移动一个元素位置,把第i个元素覆盖掉 i+1 last-1 last 2021222
2021/2/22 17 （4）顺序表删除操作 为了删除第 i 个元素，必须把从 i＋1 到 last 的所有元素 向前移动一个元素位置，把第 i 个元素覆盖掉： 1 2 . . . 0 1 i-1 i i+1 last-1 last . . . . . . . . . . . . . .
template <class Type> int Seqlist< Type>: Remove(Type x) 将x从表中删除。若ⅹ在表中并成功删除则返回1 /则返回0 int i=Find(x) if(1>=0) last--? for (int j=i, j<=last j ++)data[]-dataj+1] return 1 return O 2021222
2021/2/22 18 template <class Type> int Seqlist<Type>::Remove(Type & x) //将 x 从表中删除。若 x 在表中并成功删除则返回 1， //否则返回 0 { int i=Find(x); if (i>=0) { last--; for (int j=i;j<=last;j++) data[j]=data[j+1]; return 1; } return 0; }
顺序存储结构的优缺点 ■优点: 1)算法简单、可读性好、开发代价低 ■缺点: 1)插入、删除操作时需要移动大量元素, 效率较低; (2)最大表长难以估计,太大了浪费空间, 太小了容易溢出。 2021222
2021/2/22 19 顺序存储结构的优缺点 ◼ 优点： （1）算法简单、可读性好、开发代价低 ◼ 缺点： （1）插入、删除操作时需要移动大量元素， 效率较低； （2）最大表长难以估计，太大了浪费空间， 太小了容易溢出
顺序表应用举例 当将两个顺序表作集合考虑时的“并”与“交”操作算法 template <class Type> void Union (Seqlist <Type>& la, Seqlist <Type>& lB) //合并顺序表LA与LB,重复元素只留一个,结果在LA中 int n=LA Length int m=LB Length for(int i=0; i=m-1; i++) Type X=LB.Get(i);//从顺序表LB中取一元素 int k=LA Find(x) //在顺序表LA中查找该元素 if(k=-1) //未找到 LA. Insert(x,n);//将该元素追加到LA中 2021222 20
2021/2/22 20 顺序表应用举例 当将两个顺序表作集合考虑时的“并”与“交”操作算法 template <class Type> void Union(Seqlist <Type> & LA,Seqlist <Type> & LB) // 合并顺序表 LA 与 LB ，重复元素只留一个，结果在 LA 中。 { int n=LA.Length(); int m=LB.Length(); for (int i=0;i<=m-1;i++) { Type x=LB.Get(i); // 从顺序表 LB 中取一元素 int k=LA.Find(x); // 在顺序表 LA 中查找该元素 if (k==-1) // 未找到 { LA.Insert( x ,n); // 将该元素追加到 LA 中 n++; } } }