线性表的顺序表示和实现<算法2.1-2.7>

/*这个程序我不用全局变量，因为这个习惯不好，
在大型工程里面不合适会产生冲突*/
#include<stdio.h>
#include<malloc.h>

/*线性表存储空间的初始分配量,分配5个以typedef
为单位的存储内存，为了实验realloc函数，这里设为5,1*/
#define LIST_INIT_SIZE 5
#define LISTINCREMENT 1//线性表存储空间的分配增量

struct LIST{
	int *elem;
	int length;
	int listsize;
};

typedef struct LIST List;

void InitList(List &L);
int ListLength(List L);
void GetElem(List L, int i, int &e);
void ListInsert(List &L, int i, int e);
void ListDelete(List &L, int i, int &e);
void unionAB(List &La, List Lb);
int LocateElem(List L, int e);
void MergeList1(List La, List Lb, List &Lc);
void MergeList2(List La, List Lb, List &Lc);
void PrintList(List L);


main() {
	List La, Lb, Lc;
	int i=1, j=1, n;
	int dta;
	int length;
	/**************************************/
	//线性表的创建与初始化 
	InitList(La);
	InitList(Lb);
	printf("初始化线性表Lan");
	for(n=1; n<=8; n++) {
		printf("第%d个数据元素为：", n);
		scanf("%d", &dta);
		ListInsert(La, i++, dta);
	}
	printf("n初始化线性表Lbn");
	for(n=1; n<=8; n++) {
		printf("第%d个数据元素为：", n);
		scanf("%d", &dta);
		ListInsert(Lb, j++, dta);
	}
	printf("输出线性表La和Lb的元素值n");
	PrintList(La);
	PrintList(Lb);
	
	//**************************************
	
	//函数ListLength,GetElem的验证
	length = ListLength(La);
	printf("线性表La的长度为：%dn", length);
	
	GetElem(Lb, 4, dta);
	printf("线性表Lb的第4个元素值为：%dn", dta);
	
	//**************************************
	
	//函数 ListDelete,LocateElem的验证
	printf("输出线性表La的内容n");
	PrintList(La);
	printf("删除La中第4个元素n");
	ListDelete(La, 4, dta);
	printf("删除后的线性表Lan");
	PrintList(La);
	printf("删除的元素为：%dn", dta); 
	
	//**************************************
	
	//函数unionAB的验证
	unionAB(La, Lb);
	printf("输出线性表La中的内容n");
	PrintList(La);	
	
	//**************************************
	
	//函数MergeList1，MergeList2的验证
	printf("输出线性表La,Lb的内容n");
	PrintList(La);
	PrintList(Lb);
	MergeList1(La, Lb, Lc);
	//MergeList2(La, Lb, Lc);
	printf("输出线性表Lc的内容n");
	PrintList(Lc);
	
	//**************************************
}

/************算法2.3***************/
//构造一个空的线性表
void InitList(List &L) {
	//指向Node结构的地址 
	L.elem = (int *)malloc(LIST_INIT_SIZE*sizeof(int));
	
	// 存储分配失败
	if(!L.elem) {
		printf("error!");
		return;
	} 	
	L.length = 0;//空表长度为0
	L.listsize = LIST_INIT_SIZE;//初始存储容量
}


//返回L中数据元素个数 
int ListLength(List L)
{
	return L.length;
}

/*用e返回L中第i个元素的值*/
void GetElem(List L, int i, int &e)
{
	e = L.elem[i-1];
}


/************算法2.4***************/
/*在L中第i个位置之前插入新的数据元素e，L的长度加1*/
void ListInsert(List &L, int i, int e) {
	int *newbase, *q, *p;
	if(i<1 || i>(L.length + 1)) {
		printf("i值不合法");
		return;
	}
	if(L.length >= L.listsize) {
		newbase = (int *)realloc(L.elem, (L.listsize + LISTINCREMENT)*sizeof(int));
		if(!newbase) {
			printf("error");
			return;
		}	
		L.elem = newbase;
		L.listsize += LISTINCREMENT;
	}
	q = &(L.elem[i-1]);
	for(p=&(L.elem[L.length-1]); p>=q; --p) {
		*(p+1) = *p;
	}
	*q = e;
	++ L.length;
}

/************算法2.5***************/
/*在顺序表L中删除第i个元素，并用e返回其值*/
void ListDelete(List &L, int i, int &e) {
	int *q, *p;
		
	if(i<1 || i>(L.length + 1)) {
		printf("i值不合法");
		return;
	}
	q = &(L.elem[i-1]);
	e = *q;
	//p = &(L.elem[L.length-1]);
	p = L.elem + L.length - 1;
	for(++q; q<=p; ++q) {
		*(q-1) = *q;
	}
	-- L.length;	
} 

/************算法2.1***************/ 
/*将所有在线性表Lb中但不在La中的数据元素插入到La中*/
void unionAB(List &La, List Lb) {
	int La_len, Lb_len;
	int e, i;
	
	La_len = ListLength(La);
	Lb_len = ListLength(Lb);
	for(i=1; i<=Lb_len; i++) {
		GetElem(Lb, i, e);
		if(!LocateElem(La, e))
			ListInsert(La, ++La_len, e);
	}
} 

/************算法2.6***************/
/*判定线性表中是否存在元素e*/
int LocateElem(List L, int e) {
	int *p;
	
	for(p=&(L.elem[0]); p<=&(L.elem[L.length-1]); p++) {
		if(*p == e) 
			return 1;
	}
	return 0;
}

/************算法2.2***************/
/*归并La和Lb得到新的线性表Lc，La,Lb,Lc均按值的非递减排列*/
void MergeList1(List La, List Lb, List &Lc) {
	int La_len, Lb_len;
	int ai, bj;
	int i, j, k;
	
	InitList(Lc);
	i=j=1;
	k=0;
	La_len = ListLength(La);
	Lb_len = ListLength(Lb);
	while((i<=La_len) && (j<=Lb_len)) {
		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) {
		ListInsert(Lc, ++k, ai);
		++ i;
	}
	while(j<=Lb_len) {
		ListInsert(Lc, ++k, bj);
		++ j;	
	}
} 

/************算法2.7***************/
/*归并La和Lb得到新的线性表Lc，La,Lb,Lc均按值的非递减排列*/
void MergeList2(List La, List Lb, List &Lc) {
	int *pa, *pb, *pc;
	int *pa_last, *pb_last;
	pa = La.elem;
	pb = Lb.elem;
	Lc.listsize = Lc.length = La.length + Lb.length;
	pc = Lc.elem = (int *)malloc(Lc.listsize*sizeof(int));
	if(!Lc.elem) {
		printf("error");
		return;
	}
	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++ = *pa++;
	}
}

/*遍历输出线性表的元素值*/
void PrintList(List L) {
	int *p;
	for(p=L.elem; p<=(L.elem + L.length - 1); ++p) {
		printf("%d ", *p);
	}
	printf("n"); 
} 

最后

以上就是诚心白昼为你收集整理的线性表的顺序表示和实现<算法2.1-2.7>的全部内容，希望文章能够帮你解决线性表的顺序表示和实现<算法2.1-2.7>所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。