顺序表和线性表的算法补充（个人复盘）-Toy模板网

这篇具有很好参考价值的文章主要介绍了顺序表和线性表的算法补充（个人复盘）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、顺序表

（1）有序表的归并---1

将两个均为升序线性表 la 、lb合并成一个新的升序线性表lc。

算法的基本思想:先设lc为空表，然后按从表头到表尾顺序对la 、lb中的当前元素a、b进行比较，将较小者插到lc的表尾。

步骤：

1) 设置两个指针i 、j分别为la 、lb中当前进行比较的元素a、b的位序，i和j的初值均为１，再设置指针k表示lc的表尾位置，初值为０。　

2) 元素 a 、 b 比较后，将较小者插入 lc ，同时应后移较小者所在线性表（ la 或 lb ）的指针（ i 或 j ）。

3) 当一个表的所有元素均已插入 lc 后，另一个表尚有残尾，应将其接到 lc 之后。

代码：

void MergeList (List La , List Lb , List &Lc )  {
     //将两个均为升序表 la 、lb 归并为新的升序表lc 
     InitList(Lc);  i=1;   j=1 ;   k=0 ; 
     La_len = ListLength (La);  
     Lb_len = ListLength (Lb); 
     while(i<= La_len)&&(j<= Lb_len)  // La和Lb均有待插元素
       {
        GetElem( La , i , ai ) ; 
        GetElem( Lb , j , bj ) ; 
        if (ai<= bj)  
            { ListInsert( Lc , ++k, ai ) ;  ++i ; }
        else 
            { ListInsert( Lc , ++k, bj ) ;  ++j ; } 
        }

     while (i<= La_len )  // La尚有剩余元素（残尾）
      { GetElem( La , i++ , ai ) ; 
        ListInsert( Lc , ++k_, ai ) ; }        
       while (j<= Lb_len )  // Lb尚有剩余元素（残尾）
      { GetElem( Lb , j++ , bj ) ;
        ListInsert( Lc , ++k_, bj ) ; 
      }
 }

（2）线性表的顺序存储结构的优缺点和归并算法

优点： 无须为表示结点间的逻辑关系而增加额外的 存储空间 ;

可以方便的随机存取表中的任一结点。

缺点： 插入和删除运算不方便，需移动大量元素；

由于要求占用连续的存储空间，存储分配只 能按最大存储空间预先进行，致使存储空间不能得到充分利用； 表的容量难以扩充。

（2-1）有序顺序表的归并： 已知顺序线性表La和Lb的元素按值非递减排列

void MergeList_Sq (SqList La , SqList Lb , SqList &Lc )  {
  //将两个均为升序顺序表La、Lb 归并为新的升序顺序表Lc 
  pa= La.elem;      pb= Lb.elem; 
  Lc.listsize= Lc.length= La.length +Lb.length;
  pc=Lc.elem=(ElemType*)malloc(Lc.listsize  *sizeof(ElemType));
  if(! Lc.elem)exit(OVERFLOW);
  pa_last=La.elem+La.length-1;
  pb_last=Lb.elem+Lb.length-1;
   while ( pa<= pa_last ) &&( pb<= pb_last ) 
      { if(*pa<=*pb) *pc++=*pa++; else *pc++ = *pb++; } 
  while ( pa<= pa_last ) *pc++ = *pa++; 
  while ( pb<= pb_last ) *pc++ = *pb++; }// MergeList_Sq

二、单链表相关

1.L为带头结点的单链表头指针，当i元素存在时，其值赋给e

Status GetElem_L(LinkList L,int i,ElemType &e){
       //L为带头结点的单链表的头指针
   p=L->next;     j=1;
   while ( p && j < i) { //顺指针向后查找，直到P指向

                                      //第i个数据元素或p为空。

      p = p->next ;    ++j; }
    if ( !p || j > i ) return ERROR; //第i个数据元素不存在
    e = p->data;     //取第i个数据元素

   return OK;
} //GetElem_L

2.带头结点的单链线性表L中第i个位置之前插入元素e

Status ListInsert_ L(LinkList &L, int i, ElemType e) {
//在带头结点的单链线性表L中第i个位置之前插入元素e
p = L;   j = 0;
while ( p &&  j <  i-1 )  { p =p -> next;  ++ j; }
              //寻找第i-1个结点
if ( !p || j  > i- l ) return ERROR;  //不存在第i个元素
s = (LinkList) malloc ( sizeof (LNode));
s -> data = e;    s -> next = p -> next;
p -> next = s;
return OK;
} // LinstInsert_L

3.带头结点的单链线性表L中，删除第i个元素，并由e返回

Status ListDelete_ L(LinkList &L, int i, ElemType &e) {
//在带头结点的单链表L中，删除第i个元素，并由e返回其值
      p=L;     j = 0;
      while(p -> next & & j < i- 1) {
              //寻找第i个结点，并令P指向其前驱
         p = p->next;     ++ j;    }
    if ( ! (p -> next) ||  j > i-1 ) return ERROR
    q = p -> next;      p -> next = q -> next;
    e = q -> data;      free(q);
    return OK;
}  // ListDelete_ L

4.已知单链线性表La和Lb的元素按值非递减排列，归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列

注意：①La、Lb和 Lc不可移动； ②不可释放La的 头结点；③操作的结果仅保存链表Lc，而两操作链表不复存在。

viod MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc)

{ pa=La->next;   pb=Lb->next;

     Lc=pc=La; // La 的头结点作为Lc 的头结点

     while(( pa != NULL ) && ( pb != NULL ))

          if ( pa->data < pb->data )
              { pc->next =pa; pc=pa; pa=pa->next; }

          else { pc->next =pb; pc=pb; pb=pb->next; }

      pc->next = pa ？pa ：pb; //插入残尾

      free (Lb) ; //释放Lb的头结点

} // MergeList_L  文章来源地址https://www.toymoban.com/news/detail-740316.html