数据结构教程--李春葆版（总结）之线性表-顺序存储结构练习题

野性酷女 2022-01-05 06:51 222阅读 0赞

**本文的主要内容来自数据结构教程--李春葆版，由“你是木头人”博主进行总结。**

【**例2.2】**假设有两个集合A和B，分别用两个线性表LA和LB表示，即线性表中的数据元素为集合中的元素。利用线性表的基本运算编写一个算法求一个新的集合C=AUB,即将两个集合的并集放在线性表LC中。

void unionList(List LA,List LB,List &C)
    
    {
    int lena,i;
    ElemType e;
    InitList(LC);//第一步：初始化LC表
    for(i=1;i<=ListLength(LA),i++)//第二步，把LA表复制到Lc表中
    {
    GetElem(LA,i,e);
    ListInsert(LC,i,e);
    }
    for(i=1;i<=ListLength(LB),i++)//第三步，扫描LB表与LC表对比，判断是否存在相同的元素。
    {
    GetElem(LB,i,e);
    if(!LocateElem(LA,e))//若存在相同的元素e，则不复制该元素到LC表尾中。若无，则复制到LC表中。
    ListInset(LC,++lena,e);
    }
    }

**【例2.3】**假设一个线性表采用顺序表表示，设计一个算法，删除其中所有值等于x的元素。要求算法的时间复杂度为O(n)，空间复杂度O(1)。

**解法一：**

void delnodel(SqList *&L,ElemType x)
    {
    int k=0,i;//k表示为不等于x的元素个数
    for(i=0;i<L->length;i++)
    if(L->data[i]!=x)
    {
    L->data[k]=L->data[i];
    k++;
    }
    L->length=k;
    }

**该题图解所示：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW4xMDgzMzc2NTEx_size_16_color_FFFFFF_t_70][]

**解法二：**

void delnode2(SqList *&L,ElemType x)
    {
    int k=0,i=0;//k表示记录等于x的元素个数
    while(i<L->length)
    {
    
      if(L->data[i]==x)
    
        k++;
    
      else
        L->data[i-k]=L->data[i];
    i++;
    }
    L->length-=k;
    }

**该题图解所示：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW4xMDgzMzc2NTEx_size_16_color_FFFFFF_t_70 1][]

【例2.4】有一个顺序表L，假设元素类型ElemType为整型。设计一个算法以第一个元素为分界线，将所有小于等于它的元素移到该元素的前面，将所有大于它的元素移到该元素的后面。

**解法一：**

void move1(SqList *&L)
    {
             int i=0,j=L->length-1;
             ElemType pivot=L->data[0];//以data[0]作为基准
             ElemType tmp;
             while(i<j)
             {
             while(i<j&&L->data[j]>pivot)
                       j--;//从右向左扫描，找一个小于等于pivot的元素
             while(i<j&&L->data[i]<=pivot)
                       i++;//从左向右扫描，找一个大于pivot的元素
                       if(i<j)
                       {
                       tmp=L->data[i];
                       L->data[i]=L->data[j];
                       L->data[j]=tmp;
                       }
             }
            //基准data[0]和data[j]交换
             tmp=L->data[0];
             L->data[0]=L->data[j];
             L->data[j]=tmp;
             printf("i=%d\n",i);
    }

**解法一图解：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW4xMDgzMzc2NTEx_size_16_color_FFFFFF_t_70 2][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW4xMDgzMzc2NTEx_size_16_color_FFFFFF_t_70]: /images/20211229/a4a6147d9dee43c7b263ea820b455485.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW4xMDgzMzc2NTEx_size_16_color_FFFFFF_t_70 1]: /images/20211229/6f368534d656438c958a0182b415a86f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW4xMDgzMzc2NTEx_size_16_color_FFFFFF_t_70 2]: /images/20211229/de6509f7575745e58f5ae3d0f5d7eb25.png