欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构-线性表的顺序表示实现

程序员文章站 2024-03-20 14:28:52
...
#include<stdio.h>
#include<stdlib.h>
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef int Elemtype;
typedef struct {
	Elemtype* elem;
	int length;
	int listsize;
}SqList;
//初始化
void  InitList_Sq(SqList*L) {
	(*L).elem = (Elemtype*)malloc(LIST_INIT_SIZE * sizeof(Elemtype));
	if (!(*L).elem) {
		printf("内存申请失败");
		return ;
	}
	(*L).length = 0;
	(*L).listsize = LIST_INIT_SIZE;
	printf("初识化成功\n");
}//插入数据
void ListInsert_Sq(SqList*L, int i, Elemtype e) {
	if (i<1 || i>(*L).length + 1) {
		printf("插入数据 %d 失败!!!\n",e);
		return;
	} 
	if ((*L).length >= (*L).listsize) {
		int* newbase=NULL;
		newbase = (Elemtype*)realloc((*L).elem, ((*L).listsize + LISTINCREMENT) * sizeof(Elemtype));
		if (!newbase) {
			printf("内存申请失败");
			return;
		}
		(*L).elem = newbase;
		L->listsize += LISTINCREMENT;
	}
	int* q,*p;
	q = &((*L).elem[i - 1]);
	for (p = &((*L).elem[(*L).length - 1]); p >= q; --p)
	{
		*(p + 1) = *p;
	}	
	*q = e;
	++(*L).length;
	printf("插入数据 %d 成功\n",e);
}
//删除表中第i位置数据
void ListDelete_Sq(SqList* L, int i, Elemtype* e) {
	if ((i < 1) || (i > (*L).length)) {
		printf("无法删除第 %d 位置上的元素\n", i);
		return;
	}
	int* p,*q;
	p = &((*L).elem[i-1]);
	(*e) = *p;
	q = (*L).elem + (*L).length - 1;
	for (++p; p <= q; ++p) *(p - 1) = *p;
	--(*L).length;
	printf("删除元素 %d 成功\n", *e);
	return;
}
//线性表已存 在将L重置为空表
void ClearList_Sq(SqList* L){
	if ((*L).elem != NULL) {
		(*L).length = 0;
		printf("线性表已清空\n");
	}
	else {
		printf("线性表不存在\n");
	}
}
//线性表存在 若L为空返回True,否则返回false
void ListEmpty_Sq(SqList* L) {
	if ((*L).elem != NULL) {
		if ((*L).length == 0) {
			printf("线性表为空\n");
		 }
		else {
			printf("线性表不为空\n");
		}
	}
	else {
		printf("线性表不存在\n");
	}
	
}
//线性表存在 销毁线性表
void DestroyList_Sq(SqList* L) {
	if ((*L).elem != NULL) {
		free((*L).elem);
		(*L).length = 0;
		(*L).listsize = 0;
		(*L).elem = NULL;
		printf("线性表销毁成功\n");
	}
	else{
		printf("线性表不存在\n");
	}
	
}
//线性表存在 返回L中元素的个数
int  ListLength_Sq(SqList* L) {
	if ((*L).elem != NULL) {
		printf("线性表的长度是 %d\n", (*L).length);
		return (*L).length;
	}
	else {
		printf("线性表不存在\n");
		return -1;
	}
}
//线性表存在 用e返回L中的第i个数据元素的值
void GetElem(SqList* L,int i,Elemtype *e) {
	if ((*L).elem != NULL){
		if (i<1 || i>(*L).length) {
			printf("无法获取此位置上的元素\n");
			return ;
		}
		(*e) =(*L).elem[i - 1];
	}
	else {
		printf("线性表不存在\n");
	}
}
//比较两个元素是否相等
int compare(Elemtype a , Elemtype b) {
	if (a == b) {
		return 1;
	}
	else {
		return 0;
	}
}

//线性表L已存在,compare()是数据元素判定函数 返回L中第一个与e满足关系compare()的数据元素的位,若这样的数据元素不存在,则返回0
int LocateElem_Sq(SqList *L, Elemtype e, int (*compare)(Elemtype,Elemtype)){
	Elemtype * p;
	int i;
	i = 1;
	p = (*L).elem;
	while (i <= L->length && !(*compare)(*p++, e))++i;
	if (i <= (*L).length) return i;
	else return 0;
}
//线性表L已存在cur_e是L的数据元素且不是第一个 返回元素cur_e的前驱元素
void PriorElem(SqList* L, Elemtype cur_e, Elemtype* pre_e){
	int i=LocateElem_Sq(L, cur_e, compare);
	*pre_e = (*L).elem[i-2];
}
//线性表L已存在cur_e是L的数据元素且不是最后一个 返回元素next_e的后继元素
void NextElem(SqList* L, Elemtype cur_e, Elemtype* pre_e) {
	int i = LocateElem_Sq(L, cur_e, compare);
	*pre_e = (*L).elem[i];
}
void visit(Elemtype i) {
	printf(" %d", i);
}
//线性表已存在 依次对L的每个数据元素调用函数visit()
void ListTraverse_Sq(SqList* L, void (*visit)(Elemtype)) {
	int i = 0;
	while (i < (*L).length) {
		(*visit)((*L).elem[i]);
		i++;
	}
	printf("\n");
}
int equal(SqList* L, Elemtype *e) {
	int i=0;
	while (i < (*L).length) {
		if ((*e) == (*L).elem[i]) return 1;
		i++;
	}
	return 0;
}
int LocateElem(SqList* L, Elemtype e, int (*equal)(SqList*, Elemtype)){
	return (*equal)(L, &e);
}

void Aunion(SqList *La,SqList Lb){
	int La_len = ListLength_Sq(La);
	int Lb_len = ListLength_Sq(&Lb);
	for (int i = 1; i <= Lb_len; i++) {
		int e;
		GetElem(&Lb, i, &e);
		if (!LocateElem(La, e, equal)) ListInsert_Sq(La, ++La_len, e);
	}
}
void MergeList_Sq(SqList La, SqList Lb, SqList* Lc) {
	Elemtype * pa, * pb,*pc;
	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) {
		printf("内存申请失败");
		return;
	}
	Elemtype* pa_last, * pb_last;
	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++ = *pb++;
}
int main() {
	//SqList L;
	//InitList_Sq(&L);
	//
	测试		
	printf(" %d %d", L.length,L.listsize);
	//
	//int i=0;
	//while (i<10) {
	//	L.elem[i] = i;
	//	i++;
	//	L.length++;
	//}
	//
	测试
	///*int j = 0;
	//while (j < 10) {
	//	printf("%d ", L.elem[j]);
	//	j++;
	//	
	//}*/
	//
	//ListInsert_Sq(&L, 1, 10);
	//
	测试是否插入成功
	///*int x = 0;
	//while (x < 11) {
	//	printf("%d ", L.elem[x]);
	//	x++; 
	//}*/
	// 
	//ListInsert_Sq(&L, 0, 11);
	//int e;
	//ListDelete_Sq(&L, 2, &e);
	//printf("e = %d\n", e);

	测试
	//int x = 0;
	//while (x < L.length) {
	//	printf("%d ", L.elem[x]);
	//	x++;
	//}
	//printf("\n");

	//ListLength_Sq(&L);
	//
	//GetElem(&L, 1, &e);
	//printf("获取元素为e = %d\n", e);
	//
	//e = LocateElem_Sq(&L, 10, compare);
	//printf("元素 10 的位置为 %d\n", e);
	//e = LocateElem_Sq(&L, 5, compare);
	//printf("元素 5 的位置为 %d\n", e);
	//
	//int pre_e;
	//PriorElem(&L, 1, &pre_e);
	//printf("1的前驱元素是 %d\n", pre_e);
	//NextElem(&L, 1, &pre_e);
	//printf("1的元素是 %d\n", pre_e);

	//ListTraverse_Sq(&L,visit);

	//ClearList_Sq(&L);
	//ListEmpty_Sq(&L);

	//DestroyList_Sq(&L);
	//ListEmpty_Sq(&L);
	//--------------------------------------------
	SqList L2;
	InitList_Sq(&L2);
	int i2 = 0;
	while (i2 < 5) {
		L2.elem[i2] = i2;
		i2++;
		L2.length++;
	}
	SqList L3;
	InitList_Sq(&L3);
	int i3 = 0;
	while (i3 < 5) {
		L3.elem[i3] = i3+5;
		i3++;
		L3.length++;
	}

	//int j = 0;
	//while (j < L2.length) {
	//	printf("%d ", L2.elem[j]);
	//	j++;
	//}
	//printf("\n");
	//j = 0;
	//while (j < L3.length) {
	//	printf("%d ", L3.elem[j]);
	//	j++;
	//}
	//printf("\n");
	//Aunion(&L3, L2);
	//j = 0;
	//while (j < L3.length) {
	//	printf("%d ", L3.elem[j]);
	//	j++;
	//}
	//printf("\n");
	//--------------------------------------------
	SqList L4;
	InitList_Sq(&L4);
	MergeList_Sq(L2,L3,&L4);
	int j = 0;
	while (j < L4.length) {
		printf("%d ", L4.elem[j]);
		j++;
	}
	system("pause");
	return 0;
}