顺序表的三道习题
1.在顺序表中删除第i个元素，既删除data[i-1]
1.1算法思想
-
判断表是否为空，如果为空则不能进行删除操作
-
判断删除的位置i是否合法，如果i<1或者i大于表长则不能进行删除操作
-
将位置i后的元素逐个前移
-
表长-1
1.2算法设计
int DelList1(Sqlist &L, int i)
/*1.在顺序表L中删除ai-1。i的合法取值为1≤i≤L.length */
{
int k;
if(L.length==0)
{
printf("表为空，无法进行删除操作");
return false;
}
if ((i < 1) || (i > L.length))
{
printf("删除位置不合法!\n");
return false;
}
for (k = i; k<=L.length-1; k++)
L.data[k - 1] = L.data[k]; /*将后面的元素依次前移*/
L.length--;
return true;
}2.在顺序表中删除第i个位置开始的k个元素，即删除data[i+k-1]
2.1算法思想
-
判断表是否为空，如果为空则不能进行删除操作
-
判断第一个位置i是否合法，如果i<1或者i大于表长则不能进行删除操作
-
判断第二个位置i+k是否合法，如果i+k<1或者i+k大于表长则不能进行删除操作
-
将位置i+k后的元素逐个前移
-
表长-1
2.2算法设计
int DelList2(Sqlist &L, int i, int k)
{
/*i的合法取值为1≤i≤L.length k的合法取值范围为 1≤i+k<=L.length */
int f;
if(L.length==0)
{
printf("表为空，无法进行删除操作");
return false;
}
if ((i < 1) || (i > L.length) )
{
printf("第一个位置i不合法!\n");
return false;
}
if((i+k<1) || (i + k > L.length))
{
printf("删除位置i+k不合法!\n");
return false;
}
for (f = i + k; f < L.length; f++)
L.data[f - 1] = L.data[f]; /*将后面的元素依次前移*/
L.length--;
return true;
}3.删除表中若干个不连续的元素
如果表中相邻的两个元素之差不为1，则删除后面一位元素
3.1算法思想
-
判断表是否为空，如果为空则不能进行删除操作
-
判断表中是否只含一个元素，如果只含一个元素则不能进行删除操作
-
利用指示器i 比较相邻的两个元素L.data[i]和L.data[i+1]
-
利用循环，如果L.data[i+1]-L.data[i]!=1,则删除L.data[i+1]
-
表长减少删除元素的个数
3.2算法设计
int DelList3(Sqlist &L)
{
/*在顺序表中 比较两个相邻的data是否相差只为1 如果相差值不为1 则删除后面一个元素*/
if (L.length == 0)
{
printf("表为空，无法删除\n");
return false;
}
if (L.length == 1)
{
printf("表内元素仅为1，无法比较\n");
return false;
}
for (int i = 0; i < L.length - 1; i++)
{
if (L.data[i + 1] - L.data[i] != 1) //如果后一项和前一项之差不为1
{
for (int k = i+2; k < L.length; k++) //因为要删去的是后一项也就是L.data[i+1] 所以给k赋值为i+2
{
L.data[k - 1] = L.data[k]; /*将后面的元素依次前移*/
}
L.length--;
i--;/*因为删除了后一项 所以i的值不能改变的同时还要比较a[i]与新的a[i + 1]
所以让这里的i减一 再加上for循环里的i++ 正好抵消*/
}
}
return true;
}