《数据结构》(C语言版)——线性表的动态分配顺序存储结构

  • Post author:
  • Post category:其他


//P21 线性表的 顺序表示和实现
//函数结果状态代码
#define TRUE	1
#define FALSE	0
#define OK		1
#define ERROR	0
#define INFEASIBLE	-1
#define OVERFLOW	-2
//Status是函数的类型,其值是函数结果状态代码
typedef int Status;
//用到的库文件
#include <stdio.h>	//printf();scanf()
#include <stdlib.h> //exit()
#include <malloc.h>	//malloc()
#include <time.h>	//srand((unsigned)time(NULL));
//用宏定义确定ElemType类型
#define ElemType int
//-----线性表的动态分配顺序存储结构-----
#define LIST_INIT_SIZE 	100	//线性表存储空间的初始分配量
#define LISTINCREMENT	5 	//线性表存储空间的分配增量
typedef struct {
	ElemType *elem;			//存储空间基址
	int length;				//当前长度
	int listsize;			//当前分配的存储容量(以sizeof(ElemType)为单位)
} SqList;

// 操作结果:构造一个空的线性表L。
Status InitList_Sq(SqList &L) {	//构造一个空的顺序表,动态申请存储空间
	L.elem = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
	if (!L.elem) {				//存储分配失败
		printf("初始化失败");
		exit(OVERFLOW);			//exit(-1)程序异常退出
	}
	L.length = 0;				//空表的长度初始化为0
	L.listsize = LIST_INIT_SIZE;//空表的初始存储空间为 LIST_INIT_SIZE
	return OK;
}// InitList_Sq	算法2.3

// 初始条件:线性表L已存在。
// 操作结果:销毁线性表L。
Status DestroyList_Sq(SqList &L) {
	//free(L.elem);				//释放存储空间基址
	L.elem = NULL;				//存储空间基址置空
	L.length = 0;				//当前长度初始化为 0
	L.listsize = 0;				//分配的存储容量为 0
	return OK;
}// DestroyList_Sq

// 初始条件:线性表L已存在。
// 操作结果:将L重置为空表。
Status ClearList_Sq(SqList &L) {
	L.length = 0;
	return OK;
}// ClearList_Sq

// 初始条件:线性表L已存在。
// 操作结果:若L为空表,返回TRUE,否则返回FALSE。
Status ListEmpty_Sq(SqList L) {
	return L.length ? TRUE : FALSE;
}// ListEmpty_Sq

// 初始条件:线性表L已存在。
// 操作结果:返回L中数据元素个数。
int ListLength_Sq(SqList L) {
	return L.length;
}// ListLength_Sq

// 初始条件:线性表L已存在,1≤pos≤ListLength(L) 。
// 操作结果:用e返回L中第pos个数据元素的值。
Status GetElem_Sq(SqList L, int pos, ElemType &e) {
	if(L.length==0 || pos<1 || pos>L.length)
		return ERROR;
	e = L.elem[pos-1];
	return OK;
}// GetElem_Sq

// 初始条件:线性表L已存在,compare()是数据元素判定函数。
// 操作结果:返回L中第1个与e满足compare()的数据元素的位序,若这样的数据元素不存在,则返回值为0。
Status compare(ElemType listElem, ElemType e) {
	if(listElem==e)		//找到元素e
		return TRUE;
	else {
		//printf("在列表中没有值为%d的元素\n", e);
		return FALSE;
	}
}// Compare
int LocateElem_Sq(SqList L, ElemType e, Status (*pfn_compare)(ElemType, ElemType)) {
	int i = 1;			//i的初值为第1元素的位序
	ElemType *p = L.elem;	//p的初值为第1元素的存储位置
	//*p++代表*(p+1), 在循环中意味调用函数Status (*compare)(ElemType, ElemType),
	//用线性表中的每个元素与e比较,当*p++与e相等时,返回1,取反为0,循环中止。
	//compare是指向函数的指针
	while(i<=L.length && !(*pfn_compare)(*p++, e))
		++i;			//compare是一个指向函数的指针,返回值为Status(int)
	if (i<=L.length) {
		return i;		//i的值在线性表中,返回元素的位序
	} else
		return 0;
}// LocateElem_Sq 算法2.6

// 初始条件:线性表L已存在。
// 操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,否则操作失败,pre_e无定义。
Status PriorElem_Sq(SqList L, ElemType cur_e, ElemType &pre_e) {
	int i = LocateElem_Sq(L, cur_e, compare);
	if(i==0 || i==1) return ERROR;
	GetElem_Sq(L, i-1, pre_e);
	return OK;
}

// 初始条件:线性表L已存在。
// 操作结果:若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继,否则操作失败,pre_e无定义。
Status NextElem_Sq(SqList L, ElemType cur_e, ElemType &next_e) {
	int i = LocateElem_Sq(L, cur_e, compare);
	if(i==0 || i==L.length) return ERROR;
	GetElem_Sq(L, i+1, next_e);
	return OK;
}

// 初始条件:线性表L已存在,1≤pos≤ListLength(L)+1。
// 操作结果:在L中第pos个位置之前插入新的元素e,L的长度加1。
Status ListInsert_Sq(SqList &L, int pos, ElemType e) {
	if (pos<1 || pos>L.length+1) { 			//pos的合法值为1≤pos≤ListLength(L)+1。即插入元素的位置pos应大于 0,小于 线性表的长度+1
		printf("插入位置有问题");
		return ERROR;
	}
	if (L.length >= L.listsize) {			//当前存储空间已满,增加分配
		ElemType *newbase = (ElemType*)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof(ElemType));
		if (!newbase) {						//realloc更改已分配的内存单元大小
			printf("存储分配失败");
			exit(OVERFLOW);					//存储分配失败
		}
		L.elem = newbase;					//新基址
		L.listsize += LISTINCREMENT;		//增加存储容量
	}
	ElemType *q = &(L.elem[pos-1]);			//q为插入位置,即将插入位置的地址赋给q
	ElemType *p = &(L.elem[L.length-1]);	//p为最后一个元素的地址
	for ( ; p>=q; --p) {
		*(p+1) = *p;						//插入位置及之后的元素右移
	}
	*q = e;									//插入e
	++L.length;								//表长增1
	return OK;
}//ListInsert_Sq 算法2.4

// 初始条件:线性表L已存在且非空,1≤pos≤ListLength(L)。
// 操作结果:删除L的第pos个数据元素,并用e返回其值,L的长度减1。
Status ListDelete_Sq(SqList &L, int pos, ElemType &e) {
	if (pos>L.length || pos<1) {			//pos的合法值为1<=pos<=ListLength_Sq(L),即删除元素的位置pos应大于 0,小于 线性表的长度+1
		printf("被删除元素的位置有误");
		return ERROR;
	}
	ElemType *p = &(L.elem[pos-1]);			//p为被删除元素的位置 ,即将被删除元素的地址赋给p
	e = *p;									//被删除元素的值赋给e
	ElemType *q = L.elem + L.length - 1;	//表尾元素的位置
	for (++p; p<=q; ++p) {					//被删除元素之后的元素左移
		*(p-1) = *p; 						//假定在线性表{11 12 13 14 15}中删除13,变为{11 12 14 15},
	}										//则有  pos=3,e=13,p=&e,则循环初始条件++p=&(L.elem[3])即*p=14,*(p-1)=*p即将14往前移一位
	--L.length;								//表长减1
	return OK;
}// ListDelete_Sq 算法2.5

// 初始条件:线性表L已存在。
// 操作结果:依次对L的每个数据元素调用函数visit()。一旦vistit()失败,刚操作失败。
Status visit(ElemType e) {
	printf("%d ", e);
	return OK;
}
Status ListTraverse_Sq(SqList L, Status (*pfn_visit)(ElemType)) {
	if(!L.elem)	{
		printf("\n线性表未初始化或被销毁了!!!");
		return ERROR;
	}
	if(L.length == 0)
		printf("线性表中无元素!!!");
	for (int i=0; i<L.length; i++) {
		visit(L.elem[i]);
		//printf("%d ", L.elem[i]);
	}
	printf("\n");
	return OK;
}

//将所有在线性表Lb中但不在La中的数据元素插入到La中
void union_Sq(SqList &La, SqList Lb) {
	ElemType e;
	int La_len = ListLength_Sq(La);
	int Lb_len = ListLength_Sq(Lb);				//求线性表的长度
	for (int i=1; i<=Lb_len; i++) {
		GetElem_Sq(Lb, i, e);					//取Lb中第i个数据元素赋给e
		if(!LocateElem_Sq(La, e, compare))
			ListInsert_Sq(La, ++La_len, e);	//La中不存在和e相同的数据元素,刚插入之
	}
}// union_Sq 算法2.1

//已知线性表La和Lb中的数据元素按值非递减排列。归并La和Lb得到新的线性表Lc,Lc的数据元素也按值非递减排列。
void MergeList(SqList La, SqList Lb, SqList &Lc) {
	InitList_Sq(Lc);
	int i = 1, j = 1;
	int k = 0;
	ElemType ai, bj;
	int La_len = ListLength_Sq(La);
	int Lb_len = ListLength_Sq(Lb);				//求线性表的长度
	while((i<=La_len) && (j<=Lb_len)) {		//La和Lb均非空
		GetElem_Sq(La, i, ai);				//取La中第i个元素赋给ai
		GetElem_Sq(Lb, j, bj);
		if(ai<=bj) {
			ListInsert_Sq(Lc, ++k, ai);		//插入La中的元素
			++i;
		} else {
			ListInsert_Sq(Lc, ++k, bj);		//插入Lb中的元素
			++j;
		}
	}
	while(i<=La_len) {						//插入La剩余的元素
		GetElem_Sq(La, i++, ai);
		ListInsert_Sq(Lc, ++k, ai);
	}
	while(i<=Lb_len) {						//插入Lb剩余的元素
		GetElem_Sq(Lb, i++, bj);
		ListInsert_Sq(Lc, ++k, bj);
	}
}// MergeList 算法2.2

//已知线性表La和Lb中的数据元素按值非递减排列。归并La和Lb得到新的线性表Lc,Lc的数据元素也按值非递减排列。
void MergeList_Sq(SqList La, SqList Lb, SqList &Lc) {
	InitList_Sq(Lc);
	ElemType *pa = La.elem, *pb = Lb.elem;	//指向各表基地址
	Lc.listsize = Lc.length = La.length + Lb.length;//新表Lc的表长
	ElemType *pc = Lc.elem = (ElemType*)malloc(Lc.listsize*sizeof(ElemType));//pc指向新开辟内存空间的基地址
	if(!Lc.elem)	exit(OVERFLOW);			//存储分配失败
	int *pa_last = La.elem + La.length - 1;	//指向最后一个元素的地址
	int *pb_last = Lb.elem + Lb.length - 1;
	while(pa<=pa_last && pb<=pb_last) {		//归并
		if(*pa<=*pb) *pc++ = *pa++;			//插入La中的元素
		else		*pc++ = *pb++;			//插入Lb中的元素
	}
	while(pa<=pa_last)	*pc++ = *pa++;		//插入La剩余的元素
	while(pb<=pa_last)	*pc++ = *pb++;		//插入Lb剩余的元素
}// MergeList_Sq 算法2.7

//更改函数,其中,elem为要更改的元素,newElem为新的数据元素
Status changeElem(SqList &L,ElemType elem,ElemType newElem) {
	int pos = LocateElem_Sq(L, elem, compare);
	L.elem[pos-1] = newElem;
	return OK;
}
//顺序表的建立
Status CreateList(SqList &L) {
	int i;
	srand((unsigned)time(NULL));
	for(i=0; i < LISTINCREMENT; i++) {
		L.elem[i] = rand()%100;
		L.length++;
	}
	return OK;
}
void initMenu(SqList L) {
	printf("\n\t\t*****************************************\n");
	printf("\n\t\t  初始化成功,L.length=%d\n", L.length);
	printf("\n\t\t  1.创建随机链表\t  2.遍历线性表\n\t\t  3.清空线性表\t\t  4.线性表插入\n\t\t  5.查找表中元素");
	printf("\t  6.判断元素是否在表中\n\t\t  7.删除某个元素\t  8.线性表长度\n\t\t  9.线性表是否为空\t 10.回到主菜单\n\t\t  0.退出");
}
void mainMenu() {
	printf("\n\t\t*****************************************\n");
	printf("\n\t\t 欢迎回到主菜单\n");
	printf("\n\t\t  1.创建随机链表\t  2.遍历线性表\n\t\t  3.清空线性表\t\t  4.线性表插入\n\t\t  5.查找表中元素");
	printf("\t  6.判断元素是否在表中\n\t\t  7.删除某个元素\t  8.线性表长度\n\t\t  9.线性表是否为空\t 10.回到主菜单\n\t\t  0.退出");
}
int main() {
	int lLength, pos;
	ElemType e;
	SqList L;

	InitList_Sq(L);
	initMenu(L);
	int select;
	while(select != 0) {
		printf("\n请选择你的操作:");
		scanf("%d", &select);
		switch(select) {
			case 1:
				CreateList(L);
				printf("创建随机链表:");
				ListTraverse_Sq(L, visit);
				break;
			case 2:
				printf("遍历线性表:");
				ListTraverse_Sq(L, visit);
				break;
			case 3:
				ClearList_Sq(L);
				printf("清空L后:L.length = %d\n", L.length);
				ListTraverse_Sq(L, visit);
				break;
			case 4:
				printf("请输入要插入的元素位置和元素的值:");
				scanf("%d %d", &pos, &e);
				while(ListInsert_Sq(L, pos, e)) {
					printf("插入完毕,现在线性表为:");
					ListTraverse_Sq(L, visit);
					printf("是否继续? 1.是  0.否");
					int selectAgain;
					scanf("%d", &selectAgain);
					if(selectAgain==0)	break;
					printf("请输入要插入的元素位置和元素的值:");
					scanf("%d %d", &pos, &e);
				}
				printf("\n");
				break;
			case 5:
				printf("请输入要查找的元素位置:");
				scanf("%d",&pos);
				if(GetElem_Sq(L, pos, e))
					printf("第%d个元素的值为:%d\n", pos, e);
				else printf("请输入正常的数字!!!\n");
				break;
			case 6:
				printf("请输入你想知道是否在表中的数值:");
				scanf("%d", &e);
				// 这里假定随机数组中的元素互不重复
				pos = LocateElem_Sq(L, e, compare);
				if(pos)
					printf("值为%d是表中的第%d个元素\n", e, pos);
				else
					printf("没有值为%d的元素\n", e);
				break;
			case 7:
				printf("请输入要删除的元素位置:");
				scanf("%d", &pos);
				if(ListDelete_Sq(L, pos, e)){
					printf("元素%d删除完毕,现在线性表为:\n", e);
					ListTraverse_Sq(L, visit);
				}else printf("\n");
				break;
			case 8:
				lLength = ListLength_Sq(L);
				printf("线性表的长度为: %d \n", lLength);
				break;
			case 9:
				if (!ListEmpty_Sq(L))	printf("该线性表为空.\n");
				else	printf("该线性表非空.\n");
				break;
			case 10:
				mainMenu();
				break;
			case 0:
				break;
			default:
				printf("请输入正确的数字!!!\n");
				break;
		}
	}
	return 0;
}



版权声明:本文为prlhnxx原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。