【icoding 顺序表】习题

1 、删除指定范围

题目： 设计一个高效的算法，从顺序表L中删除所有值介于x和y之间(包括x和y)的所有元素（假设y>=x），要求时间复杂度为O(n)，空间复杂度为O(1)。 函数原型如下： void del_x2y(SeqList *L, ElemType x, ElemType y) 相关定义如下：

struct _seqlist{ ElemType elem[MAXSIZE]; int last; }; typedef struct _seqlist SeqList;

答案代码：

#include "list.h" // 请不要删除，否则检查不通过 #include <stdio.h> #include <stdlib.h> void del_x2y(SeqList* L, ElemType x, ElemType y) { int i, j = 0; for (i = 0; i <= L->last; i++) { if (L->elem[i] < x || L->elem[i] > y) { //不在范围内不需要删除 L->elem[j] = L->elem[i]; //从头排起即可 j++; } } L->last = j - 1;//末下标为长度减1 }

以上这道题，类比删除所有x（思路：需要找到第一个x为基准，后面往前填补，详见线性表总结博客）

2、删除重复

题目： 编写算法，在一非递减的顺序表L中，删除所有值相等的多余元素。要求时间复杂度为O(n)，空间复杂度为O(1)。 函数原型如下： void del_dupnum(SeqList *L) 相关定义如下：

struct _seqlist{ ElemType elem[MAXSIZE]; int last; }; typedef struct _seqlist SeqList;

答案代码：

#include "list.h" // 请不要删除，否则检查不通过 #include <stdio.h> #include <stdlib.h> void del_dupnum(SeqList* L) { int i, j; i = j = 0; for (i = 0; i <= L->last; i++) { //i往前走，j滞后一点，如果遇到相同的数j就不走，直到有不同的数放入j位置 if (L->elem[j] != L->elem[i]) { j++; L->elem[j] = L->elem[i]; } } L->last = j; //此处的j就是末尾下标 }

3、数据调整

题目： 已知顺序表L中的数据元素类型为int。设计算法将其调整为左右两部分，左边的元素（即排在前面的）均为奇数，右边所有元素（即排在后面的）均为偶数，并要求算法的时间复杂度为O(n),空间复杂度为O（1）。 函数原型如下： void odd_even(SeqList *L) 相关定义如下：

struct _seqlist{ ElemType elem[MAXSIZE]; int last; }; typedef struct _seqlist SeqList;

答案代码：

#include "list.h" // 请不要删除，否则检查不通过 #include <stdio.h> #include <stdlib.h> void odd_even(SeqList* L){ SeqList M; //用新的顺序表存放目标数列 int start=0, end=L->last; for(int i=0; i<end; i++){ if(L->elem[start]%2!=0){ //奇数 M.elem[start]=L->elem[i]; start++; }else{ //偶数 M.elem[end]=L->elem[i]; end--; } } }