顺序表 严蔚敏 数据结构代码c语言

P20 例2-1，合并线性表（1）

将所有Lb中但不在la中的数据元素插入到La中

void union (List &La,List Lb){
	//将所有Lb中但不在la中的数据元素插入到La中
	La_len =ListLength(La);
	Lb_len =ListLength(Lb);
     //求线性表的长度
	for(i=1;i<=Lb_len;i++){
		GetElem(Lb,i,e);
       //取线性表b第i个元素赋值给e 
		if(!LocateElem(La,e,equal))
       //如果线性表a中不存在和e相同的数据元素 
		ListInsert(La,++La_len,e);
        //插入操作 
	} 
}

P21 例2-2 合并线性表（2）

归并La和Lb得到新的线性表Lc, Lc中的数据元素按值非递减排列 

void MergeList (List La,List Lb,List &Lc){
	//已知线性表La和Lb中的数据元素按值非递减排列 
	//归并La和Lb得到新的线性表Lc, Lc中的数据元素按值非递减排列 
	InitList(Lc);
	i=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);//取线性表a第i个元素赋值给ai 
		GetElem(Lb,j,bj);//取线性表b第j个元素赋值给bj 
		if(ai<=bj){
			ListInsert(Lc,++k,ai);
         //在线性表lc的第++k个元素之前插入新的元素
			++i;      }
		else{ ListInsert(Lc,++k,bj);//
			 ++j;}
		}
		
			while(i<=La_len){
			GetElem(La,i++,ai);
			ListInsert(Lc,++k,ai);
			}
			while(j<=Lb_len){
			GetElem(Lb,j++,bj);
			ListInsert(Lc,++k,bj);
			}
    }
	/*如果在主循环结束后，`La` 中还有剩余元素，那么这个循环会将它们全部插入到 `Lc` 中。
	同样，如果 `Lb` 中还有剩余元素，也会将它们插入到 `Lc` 中
	时间复杂度=O(LA+LB)*/	

P22   算法2-3线性表初始化定义

#define LIST_INIT_SIZE 100//初始分配量 
#define LISTINCREMENT  10
typedef struct {
	ElemType *elem;//数组指针 线性表的基地址 
	int length;//线性表的当前长度， 
	int listsize;//线性表最先分配的存储空间 
}SqList;


Status InitList_Sq(SqList &L)
//构造一个线性表L
 {L.elem = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
 if(! elem) exit(OVERFLOW);//存储分配失败
 L.length = 0;//空表的长度为零 ，目的是分配一个预定义大小的数组空间 
 L.listsize = LIST_INIT_SIZE;
 return OK; 
 }//初始化 

P24 算法2-4 线性表的插入

 Status ListInsert_Sq(SqList &L,int i,ElemType e) {
     if(i<1||i>L.length+1) return ERROR;  
	 //插入位置不合理 
     if(L.length>= L.listsize) {//如果列表的长度已经达到了当前分配的内存大小，就会通过 `realloc` 函数重新分配内存。
     	newbase =(ElemType*)realloc(L.elem,(L.list.size+LISTINCREMENT)*sizeof(ElemType));
     	if(!newbase) exit(OVERFLOW);
     	L.elem = newbase;
     	L.listsize +=LISTINCREMENT;
		 //新的内存大小是原来的大小加上一个增量 `LISTINCREMENT`。
		 //如果重新分配内存失败（返回 `NULL`），则程序会退出并标记为 `OVERFLOW`。
		 //如果成功，将新的内存地址赋值给 `L.elem`，并增加 `L.listsize`。
	 }
	  q=&(L.elem[i-1]);//获取插入位置前一个元素的指针 `q`。
     for(p=&( L.elem[L.length-1] );p>=q ; --p  ) 
	 //通过一个循环将从最后一个元素开始到`q`（包括 `q`）的所有元素向后移动一个位置，为插入新元素腾出空间。
	  *(p+1)=*p;
     *q=e;  //扎入e 
     ++L.length;  //长度+1 
     return OK;
 }

p24 算法2-5线性表的删除

Status ListDelete_Sq(SqList &L,int i,ElemType &e){
    if(i<1||i>L.length) return ERROR;  //删的位置不合理
      p=&(l.elem[i-1]);
      //获取要删除元素的指针 `p`
       e=*p;
       //将该元素的值赋值给变量 `e`，以便后续使用或存储。
       q=L.elem+L.length-1;
	   //设置一个指针 `q` 指向列表的最后一个元素。
    for(++p;p<=q;++p)  
	  *(p-1)=*p; //通过一个循环，将从 `p`（包括 `p`）到 `q` 的所有元素向前移动一个位置，覆盖要删除的元素。
      --L.length;
    return OK;
 }

p25 算法2-6 线性表元素的查找

 int LocateElem_Sq (SqList L,ElemType e,Status(*compare)(ElemType)) {
 //Status(*compare)(ElemType)：这是一个比较函数的指针，用于确定元素的顺序。
     i=1;
	 p=L.elem;
	 //i 被初始化为 1，p 指向顺序表的第一个元素。
	 while(i<=length &&!(*compare)(*p++,e)) 
	 ++i;
//只要 i 小于或等于顺序表的长度，并且当前元素 *p 不满足比较函数 *compare 与要查找的元素 e 的比较条件，
	 //就将 i 增加 1，并将 p 指向下一个元素
     if(i<=L.length) 
	    return i;   
     else return 0;
 }

P26 算法 合并线性表（3）

基本操作“元素赋值”

void MergeList_Sq (List La,List Lb,List &Lc){
	//已知线性表La和Lb中的数据元素按值非递减排列 
	//归并La和Lb得到新的线性表Lc, 
	//Lc中的数据元素按值非递减排列 
	pa =La.elem;pb =Lb.elem;
	//分别获取 La 和 Lb 顺序表的起始元素指针。
	Lc.listsize=Lc.length=La.length+Lb.length;
	//表示新的顺序表 Lc 的大小。
	pc=Lc.elem=(ElemTyoe*)malloc(Lc.listsize*sizeof(ElemType));
	//为 Lc 分配内存空间来存储合并后的元素。
	if(!Lc.elem)exit(OVERFLOW);
	
	pa_last=La.elem+La.length-1;
	pb_last=Lb.elem+Lb.length-1;
	//分别获取 La 和 Lb 顺序表的末尾元素的后一个位置。

	while((pa<=pa_last)&&(pb<=pb_last)){//归并 
	
		if(*pa<=*pb)//如果 *pa 小于或等于 *pb，
		//则将 *pa 的值复制到 *pc 并递增 pa 和 pc。
			*pc++=*pa++;   
		else
		     *pc++ = *pb++;
	//将 *pb 的值复制到 *pc 并递增 pb 和 pc  }
		}
		
			while(pa<=pa_last){
//将 *pb 的值复制到 *pc 并递增 pb 和 pc。
		*pc++=*pa++;
			}
			while(pb<=pb_last){
			*pc++ =*pb++;
			}
    }