线性表

àì夳堔傛蜴生んèń 2022-04-16 02:09 241阅读 0赞

**线性表的定义：**一个线性表是n个数据元素的有限序列。

在复杂的线性表中，一个数据元素可以由若干个**数据项**组成，这种情况下，通常把数据元素称为**记录**，含有大量记录的线性表称为**文件**。

在线性表中，数据元素a2有且仅有一个直接前驱元素a1，和一个直接后继元素a3。（a1,a2,a3......ai.....an）

在线性表的顺序存储结构中，逻辑上相邻的数据元素在物理位置上也是相邻的。

下面讨论，在线性表的顺序存储结构中，数据元素的插入和删除：

一般情况下，在第i(1≤i≤n)个元素之前插入一个元素时，需将第n至第i(共n-i+1)个元素向后移动一个位置。

线性表数据元素插入的算法：

Status ListInsert.Sq(SqList &L ,int i ,ElemType e){
    	//在顺序线性表L中第i个位置之前插入新的元素e
    	//i的合法值为1≤i≤ListLength.Sq(L)+1
    	if (1<i || i>L.length+1) return Error;//i值不合法
    
    	if (L.length>=L.listsize)//当前存储空间已满，增加分配
    	{
    		newbase = (ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
    		if (!newbase) exit(OVERFLOW);//存储分配失败
    		L.elem=newbase;//新基址
    		L.listsize+=LISTINCREMENT;//增加存储容量
    	}
    
    	q=&(L.elem[i-1]);//q为插入位置
    	for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p;//插入位置及之后的元素右移
    
    	*q=e;//插入e
    	++L.length;//表长增加1
    	return OK;
    }//ListInsert_Sq

数组指针elem指示线性表的基址；length是线性表的当前长度；listsize是顺序表当前分配的存储空间的大小。

一般情况下，删除第i(1≤i≤n)个元素是，需将第i+1至第n(共n-i)个元素向前移动一个位置。

线性表数据元素删除的算法：

Status ListInsert.Sq(SqList &L ,int i ,ElemType e){
    	//在顺序线性表L中删除第i个元素，并用e返回其值
    	//i的合法值为1≤i≤ListLength.Sq(L)+1
    	if (1<i || i>L.length+1) return Error;//i值不合法
    	
    	p=&(L.elem[i-1]);//p为被删除元素的位置
    	e=*q;//被删除元素的值赋给e
    	q=L.elem+L.length-1;//表尾元素的位置
    
    	for(++p;p=<q;++p) *(p-1)=*p;//被删除元素之后的元素左移
    
    	--L.length;//表长减少1
    	return OK;
    }//ListInsert_Sq

顺序表的合并：

void MergeList_Sq(SqList La,SqList Lb,SqList &Lc){
    	//已知顺序线性表La和Lb的元素按值非递减排列
    	//归并La和Lb得到新的顺序线性表Lc，Lc的元素也按值非递减排列
    	pa = La.elem;
    	pb = Lb.elem;
    
    	Lc.listsize = Lc.length = La.length+Lb.length;
    
    	pc = Lc.elem = (EnemType *)malloc(Lc.listsize * sizeof(EnemType));
    	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++;//插入La剩余的元素
    	while(pb <= pb.last) *pc++ == *pb++;//插入Lb剩余的元素
    }//MergeList.Sq