线性表(二)

线性表（一）

 

问题：

有2个线性表LA,LB，现在要求组成一个新的集合A=A+B

 

 

void merge(sqList *LA,sqList *LB){
	int i;
	elemType e;
	for(i=1;i<=listLength(LB);i++){
		e = getElem(LB,i);
		if(!locateElem(LA,e)){
			
			listInsert(LA,listLength(LA)+1,e);
		}
	}
}

 

线性表的顺序表示和实现

线性表的顺序表示是指用一组地址连续的存储单元以此存储线性表的数据元素。

 

LOC(a[i]) = LOC(a[1]) + (i-1)*d

 

d表示每个元素所占的存储单元

LOC(a[1])是线性表的第一个数据元素a[1]的存储位置，通常叫做线性表的起始位置或基地址。

采用顺序存储的线性表，只要确定了存储线性表的起始位置，线性表中任一数据元素都可以随机存取，线性表的顺序存储结构式一种随机存取的存储结构。

 

带动态分配存储空间功能的线性表顺序存储C语言表示：

#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAXSIZE 5

typedef int elemType;
typedef struct{
	elemType *list;
	int length;	
	int maxSize;
}sqList;
/*1.初始化线性表L，分配内存空间*/
void initList(sqList *L){
	L->list = malloc(MAXSIZE * sizeof(elemType));
	if(!L->list){
		printf("空间分配失败!\n");
		exit(0);
	}
	L->length = 0;
	L->maxSize = MAXSIZE;
	printf("空间分配成功!\n");
	return;
}
/*2.销毁线性表，释放内存空间*/
void destroyList(sqList *L){
	if(!L->list){
		printf("该线性表不存在!\n");
		exit(0);
	}
	free(L->list);
	L->list = NULL;
	L->length = L->maxSize = 0; 
	printf("线性表销毁成功!\n");
	return;
}
/*3.将线性表置为空表，不释放存储空间*/
void clearList(sqList *L){
	if(L->list != NULL){
		L->length = 0;
	}
	return;
}
/*4.若L为空表，则返回TRUE，否则返回FALSE*/
int listEmpty(sqList *L){
	return L->length == 0 ? TRUE : FALSE;
}
/*5.返回线性表L中数据元素的个数*/
int listLength(sqList *L){
	return L->length;
}
/*6.获取线性表中指定位置的元素*/
elemType getElem(sqList *L,int i){
	if(i<1 || i >listLength(L)){
		printf("序号越界!");
		exit(0);
	}
	return L->list[i-1];
}
/*7.返回L中第1个等于e的数据元素的位序，不存在，则返回0*/
int locateElem(sqList *L,elemType e){
	elemType *p = L->list;
	int i=0;
	while(i<listLength(L) && *p!=e){
		p++;
		i++;
	}
	if(i == listLength(L)){
		i=-1;
	}
	return i+1;
}
/*8.若cur_e是L的数据元素，且不是第一个，则用e返回它的前驱，否则操作失败*/
elemType priorElem(sqList *L,elemType cur_e){
	int i;
	elemType *p = L->list;
	for(i=1;i<listLength(L);i++,p++){
		if(*p == cur_e){
			break;
		}
	}
	if(i == listLength(L)){
		printf("输入的不是该线性表的元素!");
		exit(0);
	}
	if(i == 1){
		printf("输入的元素没有前驱元素!");
		exit(0);
	}
	return L->list[i-2];
}
/*9.若cur_e是L的数据元素，且不是最后一个，则用e返回它的后继，否则操作失败*/
elemType nextElem(sqList *L,elemType cur_e){
	int i;
	elemType *p = L->list;
	for(i=1;i<listLength(L);i++,p++){
		if(*p == cur_e){
			break;
		}
	}
	if(i == listLength(L)){
		printf("输入的不是该线性表的元素!");
		exit(0);
	}
	if(i == listLength(L)-1){
		printf("输入的元素没有后继元素!");
		exit(0);
	}
	return L->list[i];
}
/*10.在线性表L中第i个位置之前插入新的数据元素e,L的长度+1*/
void listInsert(sqList *L,int i,elemType e){
	if(i < 1 || i >listLength(L)+1){
		printf("序号越界，插入失败!\n");
		exit(0);
	}
	if(listLength(L) == L->maxSize){
		elemType *p = realloc(L->list,(L->maxSize+1) * sizeof(elemType));
		if(!p){
			printf("空间再分配失败!");
			exit(0);
		}
		L->list = p;
		L->maxSize++;
	}
	int j=listLength(L);
	while(j >= i){
		L->list[j] = L->list[j-1];
		j--;
	}
	L->list[i-1] = e;
	L->length++;
	return;
}
/*11.删除线性表L的第i个元素，并使用e返回，L长度-1*/
void listDelete(sqList *L,int i,elemType e){
	if(i < 1 || i >listLength(L)){
		printf("序号越界，插入失败!\n");
		exit(0);
	}
	e = L->list[i-1];
	while(i<listLength(L)+1){
		L->list[i-1] = L->list[i];
		i++; 
	}
	L->length--;
}
/*12.依次对线性表L的每个元素调用函数visit()*/
void listTraverse(sqList *L,void (*visit)(elemType)){
	int i;
	for(i=1;i<=listLength(L);i++){
		visit(getElem(L,i));
	}
	printf("\n");
	return;
}

void visit(elemType e){
	printf("%d ",e);
}

int compare(elemType a,elemType b){
	return a-b;
}

void merge(sqList *LA,sqList *LB){
	int i;
	elemType e;
	for(i=1;i<=listLength(LB);i++){
		e = getElem(LB,i);
		if(!locateElem(LA,e)){
			listInsert(LA,listLength(LA)+1,e);
		}
	}
}

int main(){
	sqList L;
	initList(&L);
	int a[6] =  {3,6,7,9,11,13}; 
	int i;
	printf("线性表 maxSize = %d \n",L.maxSize);
	for(i=0;i<6;i++){
		listInsert(&L,i+1,a[i]);
	}
	listTraverse(&L,visit);
	printf("线性表 maxSize = %d \n",L.maxSize);
	
	destroyList(&L);
	return 0;	
}