本文共 1581 字，大约阅读时间需要 5 分钟。

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

【例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
   
    length;i++)if(L->data[i]!=x){L->data[k]=L->data[i];k++;}L->length=k;}
   

该题图解所示：

解法二：

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

该题图解所示：

【例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
   
    data[j]>pivot)                   j--;//从右向左扫描，找一个小于等于pivot的元素         while(i
    
     data[i]<=pivot)                   i++;//从左向右扫描，找一个大于pivot的元素                   if(i
     
      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);}
     
    
   

解法一图解：

转载地址：http://iwwab.baihongyu.com/