《数据结构》爬坡 — —线性表算法应用题

太过爱你忘了你带给我的痛 2022-10-06 10:44 164阅读 0赞

### 线性表应用题 ###

*   *  一、综合应用题
     *   *   *  1.1 从顺序表中删除具有最小值的元素(假设唯一)并由函数返回被删元素的值，空出的位置由最后一个元素填补,若顺序表为空,则显示出错信息并退出运行。
             *  1.2 设计一个高效算法，将顺序表L的所有元素逆置,要求算法的空间复杂度为0(1)。
             *  1.3 对长度为n的顺序表L，编写一个时间复杂度为0(n)、空间复杂度为0(1)的算法，该算法删除线性表中所有值为x的数据元素。
             *  1.4 从顺序表中删除其值在给定值s与t之间 (包含s和t，要求s

--------------------

[1.《数据结构》的第一次爬坡][1.]

[2.《数据结构》爬坡 — — 算法的基本概念与效率的度量][2._ _ _]

[3.《数据结构》爬坡 — — 线性表的定义][3._ _ _]

[4.《数据结构》爬坡 — — 顺序表的初始化&基本操作][4._ _ _]

--------------------

## 一、综合应用题 ##

#### 1.1 从顺序表中删除具有最小值的元素(假设唯一)并由函数返回被删元素的值，空出的位置由最后一个元素填补,若顺序表为空,则显示出错信息并退出运行。 ####

**解：** 算法思想:搜索整个顺序表,查找最小值元素并记住其位置,搜索结束后用最后一个元素填补空出的原最小值元素的位置。

bool delete_min(SqList &L, ElemType &min_value){
        
        // 删除顺序表L中最小值元素结点,并通过引用型参数value返回其值
        // 若删除成功,则返回true;否则返回false
        if(L.length==0)     // 表空,中止操作返回
            return false;
        int pos = 0;
        min_value = L.data[0];      // 假定0号元素的值最小
        for(int i=1;i<L.length;i++){
            // 循环,寻找具有最小值的元素
            if(min_value > L.data[i]){
        
                min_value=L.data[i];  // value记忆当前具有最小值的元素
                pos = i
            }
            
        L.data[pos] = L.data[L.length-1];   // 空出的位登由最后一个元素填补
        L.length-- 
        return true;    // 此时, value即为最小值 
        }
    }

--------------------

#### 1.2 设计一个高效算法，将顺序表L的所有元素逆置,要求算法的空间复杂度为0(1)。 ####

**算法思想：** 扫描顺序表L的前半部分元素，对于元素L.data\[i\] (0<=i<L.length/2)，将其与后半部分的对应元素L.data\[L.length-i-1\] 进行交换。

void Reverse(SqList &L){
        
        int temp;   // 辅助变量
        for(int i=0;i<L.length/2;i++){
        
            temp = L.data[i];
            L.data[i] = L.data[L.length-i-1];
            L.data[L.length-i-1] = temp;  
        }
    }

--------------------

#### 1.3 对长度为n的顺序表L，编写一个时间复杂度为0(n)、空间复杂度为0(1)的算法，该算法删除线性表中所有值为x的数据元素。 ####

**算法思想：** 用k记录顺序表L中不等于x的元素个数(即需要保存的元素个数)，边扫描L边统计k，并将不等于x的元素向前移动k个位置，最后修改L的长度。

void del_data(SqList &L,ElemType x){
        
        int k = 0;
        for(int i=1;i<L.length;i++){
        
            if(L.data[i]!=x){
        
                L.data[k]=L.data[i];
                k++;
            }
        L.length=k;
        }

--------------------

#### 1.4 从顺序表中删除其值在给定值s与t之间 (包含s和t，要求s<t) 的所有元素，若s或t不合理或顺序表为空，则显示出错信息并退出运行。 ####

**算法思想:** 从前向后扫描顺序表L，用k记录下元素值在s到t之间元素的个数(初始时k=0)，对于当前扫描的元素，若其值不在s到t之间，则前移k个位置;否则执行k++。

bool  Del_s_t(SqList &L, int s, int t) {
        
         // 删除L中在给定值s与t之间的所有元素
         int i, k = 0;
         if (s >= t || L.length == 0)
             return false;
         for (i = 0; i < L.length; i++) {
        
             if (L.data[i]>=s && L.data[i]<=t) 
                 k++;
             else 
                 L.data[i-k] = L.data[i]; 
         }
         L.length -= k;
         return true;
    }

--------------------

#### 1.5 从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。 ####

**算法思想:** 注意是**有序**顺序表，值相同的元素一定在连续的位置上，初始时将第一个元素视为非重复的有序表。之后依次判断后面的元素是否与前面非重复有序表的最后一个元素相同，若相同，则继续向后判断；若不同，则插入前面的非重复有序表的最后，直至判断到表尾为止。

bool delete_same(SqList &L){
        
        if(L.length==0)
            return false;
            
        int i,j;
        for (i=0;j=1,j<L.length; j++) {
        
            if(L.data[i]!=L.data[j])    // 前一项与后一项不等
                L.data[++i]=L.data[j];
        }
        L.length=i+1;
        return true;
    }

--------------------

#### 1.6 将两个有序顺序表合并为一个新的有序顺序表,并由函数返回结果顺序表。 ####

**算法思想:** 首先，按顺序不断取下两个顺序表表头较小的结点存入新的顺序表中。然后，看哪个表还有剩余，将剩下的部分加到新的顺序表后面。

bool Merge(SeqList A, SeqList B, SeqList &C){
        
        // 将有序顺序表A与B合并为一-个新的有序顺序表C
        if (A.length+B.length>C.maxSize)  // 大于顺序表的最大长度
            return false;
        int i=0,j=0,k=0;
        while (i<A.1ength && j<B.1ength) {
         //循环，两两比较，小者存入结果表
            if(A.data[i]<=B.data[j])
                C.data[k++] = A.data[i++];
            else
                C.data[k++]=B.data[j++];
        }
        while (i<A. length) // 还剩-一个没有比较完的顺序表
            C.data [k++]=A.data[i++];
        while (j<B. length)
            C.datal[k++]=B.data[j++];
        C.length=k;
        return true;
    }

--------------------

[1.]: https://blog.csdn.net/weixin_44775255/article/details/117661143
[2._ _ _]: https://blog.csdn.net/weixin_44775255/article/details/117663730
[3._ _ _]: https://blog.csdn.net/weixin_44775255/article/details/117667577
[4._ _ _]: https://blog.csdn.net/weixin_44775255/article/details/117691388