线性表的顺序表示和实现


线性表的顺序表示和实现

  • 定义变量
  • 初始化线性表
  • 插入元素
  • 删除线性表中的元素
  • 查询
  • 输出线性表
  • 合并两个表
  • 逻辑运行(main)

定义变量
#include		//输入输出头文件#include			//malloc和free都在这个头文件里#define LIST_INIT_SIZE 100//线性表存储空间的初始分配量#define LISTINCREMENT	10//线性表存储空间的分配增量#define TRUE		1#define FALSE		0#define OK			1#define ERROR		0#define INFEASIBLE	-1#define OVERFLOW	-2typedef int Status;//函数类型,其值是函数结果状态代码typedef int ElemType;#define maxList		10ElemType* q;ElemType* p;ElemType* pa;ElemType* pb;ElemType* pc;ElemType* pa_last;ElemType* pb_last;int i;/******************元素类型*******************/typedef struct {
	ElemType* elem;//存储空间基址,L.elem[5]为第六位的地址
	int length;		//当前长度
	int listsize;	//当前分配的存储容量(以sizeof(ElemType)为单位)}SqList;

初始化线性表

创建一个空表,并将length置零,初始化存储容量

Status  InitList_Sq(SqList& L){
	//构建一个空的线性表L
	L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));//给L分配一个地址
	if (!L.elem)exit(OVERFLOW);		//exit函数是退出应用程序,并将应用程序的一个状态返回给OS
									//此句表示,如果分配失败,退出程序,返回值为OVERFLOW(-2)
	L.length = 0;					//初始化长度为0
	L.listsize = LIST_INIT_SIZE;	//初始存储容量
	return OK;//返回1}

插入元素

顺序表插入元素即为在位置i处插入一个元素,将原来i位置之后的所有元素向后移一位。
可以很明显的看出,此时的时间复杂度是线性的。

/***********插入**************/Status ListInsert_Sq(SqList& L, int i, ElemType e){
	ElemType* newbase;
	//在顺序表L中插入第i个位置之前插入新的元素e
	//i的合法性  0<i<ListLength.Sq(L)+1 //ListLength.Sq(表长)
	if (i<1 || i>L.length + 1)
		return ERROR;//i不合法

	/*当前存储空间已满,增加分配*/
	if (L.length >= L.listsize)
	{
		newbase = (ElemType*)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType));
		/*先释放原来L.elem所指内存区域,并重新分配大小为(L.listsize+LISTINCREMENT)*sizeof(ElemType)
		同时将原有数据从头到尾拷贝到新分配的内存区域,并返回该内存区域的首地址。*/

		if (!newbase)exit(OVERFLOW);	//此句表示,如果分配失败,退出程序,返回值为OVERFLOW(-2)
		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;}

删除线性表中的元素

在顺序表中,删除一个元素和插入一个元素的操作非常相似。删除一个元素即是将i位置之后的所有元素向前移一位。
在顺序存储结构中,插入或者删除一个元素,平均移动线性表中一半元素,时间复杂度均是O(n)。

/**************************删除第i个元素********************************/Status ListDelete_Sq(SqList& L, int i, ElemType& e){
	//在顺序表中删除第i个元素,并用e返回其值
	//i的合法性,0<i<L.ListLength.Sq(L)
	if ((i < 1) || (i > L.length))
		return ERROR;
	p = &(L.elem[i - 1]);			//p取地址为被删除的i元素的位置
	e = *p;						//被删除的元素值赋给e
	q = L.elem + L.length - 1;	//表尾元素的位置
	for (++p; p <= q; ++p)		//被删除元素之后的元素左移
		*(p - 1) = *p;
	--L.length;					//表长 -1
	return OK;}

查询

查询某个值在顺序表中是否存在,存在时,其位置是多少,其实就是将顺序表从第一个元素开始依次和这个值相比较。最多比较length次,最少比较一次。(表非空的情况下)

/*************************在顺序表中查询是否存在和e相同的元素**********************/int locateElem_Sq(SqList L, ElemType e){
	
	//若找到,则返回其在L中的位序,否则返回0
	i = 1;				//i的初值为第1个元素的位序
	p = L.elem;			//p的初值为第1个元素的存储位置
	while (i <= L.length && *p++!=e)
		i++;
	if (i <= L.length)
		return i;
	else
		return 0;}

输出线性表
void PrintList_sq(SqList L)//输出顺序表中的元素{
	int i;
	for (i = 0; i <L.length; i++)
		printf("%d ",L.elem[i]);
			printf("\n");}

合并两个表

将两个表合并,首先开辟可以存放合并两个表需要的空间。之后依次比较两个表的元素的大小,将小的先存放,之后继续进行比较,直到其中一个表的元素存放完,将另一个表剩余的元素都依次存放进表3中。

void MergeList_Sq(SqList La, SqList Lb, SqList& Lc){
	//已知顺序表La和Lb的元素按值非递减排列
	//归并La和Lb得到新的顺序表Lc,Lc的元素也按值非递减排列
	pa = La.elem;
	pb = Lb.elem;
	Lc.listsize = Lc.length = La.length + Lb.length;//Lc的表长为La+Lb
	pc = Lc.elem = (ElemType*)malloc(Lc.listsize * sizeof(ElemType));//给pc分配空间
	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)//当pa和pb没有超出相应的表时
	{
		//归并
		//*pa指针存储值
		//&pa指针地址
		if (*pa <= *pb)			//当pa<=pb时,pc赋给pa并且两个指针+1 
			*pc++ = *pa++;
		else
			*pc++ = *pb++;
	}
	//当表的长度不一样时,插入剩余的部分
	while (pa <= pa_last)
		*pc++ = *pa++;			//插入La的剩余元素
	while (pb <= pb_last)
		*pc++ = *pb++;			//插入Lb的剩余元素}

逻辑运行(main)
int main(){
	int options;
	SqList p;
	SqList q;
	int n;
	int e;
	int a[maxList];
	InitList_Sq(p);//初始化顺序表
	printf("请输入你要创建的元素个数:\n");
	scanf("%d", &n);//不能超过maxList

	for (int i = 1; i <= n; i++)
	{
		printf("请输入第%d个元素值\n", i);
		scanf("%d", &a[i]);
		ListInsert_Sq(p, i, a[i]);
	}
	PrintList_sq(p);
	int status1 = 1;
	while (status1)
	{
		printf("请输入你要进行的操作:1、插入;2、删除;3、查询;4、退出\n");
		scanf("%d", &options);
		switch (options)
		{
		case 1:
			//{
			printf("请输入你要存放的位置\n");
			scanf("%d", &i);
			printf("请输入你要插入的元素值\n");
			scanf("%d", &e);
			ListInsert_Sq(p, i, e);
			PrintList_sq(p);
			//}
			break;
		case 2:
			printf("请输入你要删除的位置\n");
			scanf("%d", &i);
			ListDelete_Sq(p, i, e);
			printf("删除%d成功\n", e);
			PrintList_sq(p);
			break;
		case 3:
			printf("请输入你要查询的值\n");
			scanf("%d", &e);
			i = locateElem_Sq(p, e);
			if (i != 0)
				printf("此值的位置为:%d\n", i);
			else
				printf("没有此值\n");
			PrintList_sq(p);
			break;
		case 4:
			exit(0);
		default:printf("\t错误\n"); exit(0);
			PrintList_sq(p); 
			break;
		}

	}
	printf("%d\n",p.length);
	return 0;}

上一篇:面试题:手写jquery要求考虑插件扩展性


下一篇:顺序表的插入运算 NOJ1 西工大 数据结构