shuju.cpp

配合严蔚敏数据结构（C版）是对单向顺序表的部分源码

#include"shuju.h"


//#include<malloc.h>
int *newbase;
int *q,*p,i,*pa,*pb,*pc,*pa_last,*pb_last;
Status InitList_Sq(SqList &L){
	//构造一个空的线型表T
	L.elem =(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
	if(!L.elem)exit(OVERFLOW);//存储失败
	L.length=0;                //空表长度为0
	L.listsize=LIST_INIT_SIZE;//初始存储容量
	return OK;
}//InitList_Sq
Status ListInsert_Sq(SqList &L,int i,ElemType e){
	if(i<1||i>L.length+1)return ERROR;
	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
Status ListDelete_Sq(SqList &L,int i,ElemType &e){
	//在顺序线性表L中删除第i 个元素	
	if ((i<1)||(i>L.length))return ERROR;
	p=&(L.elem[i-1]);		//p为被删除元素的位置
	e=*p;					//被删除元素的值赋给e
	q=L.elem+L.length-1;	//表尾元素的位置
	for(++p;p<=q;++p)*(p-1)=*p;//
	--L.length;
	return OK;
}//listDelete_Sq
int locateElem_Sq(SqList l,ElemType e,Status(*compare)(ElemType ,ElemType)){
	//在线形表L中查找1个值与e满足compare()的元素的位序
	i=1;						//i的初始值为第1个元素的位序
	p=l.elem;					//p的初始值为第1个元素的存储 位序
	while(i<=l.length&&!(*compare)(*p++,e))++i;
	if(i<=l.length)return i;
	else return 0;
}//LocateElem_Sq
void MergeList_Sq(SqList La,SqList Lb,SqList &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++;			//插入La的剩余元素
	while(pb<=pb_last)*pc++=*pb++;			//插入Lb的剩余元素
}//MetgeList_Sq
void DestoryList(SqList &L){
	free(L.elem);
}
Status CleatList(SqList &L){
	L.length=0;
	return OK;
}