数据结构（C实现）------- 顺序表

时间：2021-08-20 10:27:10

            线性表是由n(n>=0)个具有相同数据类型的数据元素组成的有限序列，通常记为：（a1,a2,..,ai-1,ai,ai+1,...,an），表中相邻元素之间存在着序偶关系，即<ai-1,ai>,其中ai-1称为ai的前驱，ai称为ai-1的后继，2<=i<=n。表中数据元素的个数n，称为线性表的长度，长度为0的线性表称为空表。在非空的线性表中，每个数据元素都有一个确定的位置，如a1是第一个元素，an是最后一个元素，ai是第i个元素，称i 为数据元素ai在线性表上的位序.

           顺序表是线性表的顺序存储结构，是指用一组连续的存储单元依次存储线性表的数据元素。在顺序表中，逻辑关系相邻的两个元素在物理位置上也相邻，元素之间的逻辑关系是通过下标反映出来的。

           数组可以用来描述顺序表，但考虑到顺序表的长度是不断变化的，所以通常将一维数据和顺序表的长度封装成一个结构体来描述顺序表。如下所示：

// 定义顺序表
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define ElemType int
typedef struct{
	ElemType *elem;//存储空间基址
	int length;	//当前长度　
	int listsize; 	//当前分配的存储容量
}SqList;
        

         针对线性表，有初始化，插入，删除，清空，得到表长度，打印顺序表，销毁，定位等操作，分另如下：

        

//宏定义
#define Status int 
#define OK 1
#define OVERFLOW 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
      

         顺序表的各种操作：

// 初始化
Status InitList_Sq(SqList *L){
	L->elem = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
	if(!L->elem)
		exit(OVERFLOW);
	L->length = 0;
	L->listsize = LIST_INIT_SIZE;
	return OK;
}

// 在指定位置插入元素
Status ListInsert_Sq(SqList *L,int i,ElemType e){
	//在顺序表Ｌ中的第i个位置之前插入新的元素e
	ElemType *q,*p;
	if(i < 1 || i > L->length+1){
		printf("位置不合法\n");
		return ERROR;
	}
	if(L->length >= L->listsize){
		ElemType *newbase = (ElemType*)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(ElemType));
		if(!newbase)
			exit(OVERFLOW);
		L->elem = newbase;
		L->listsize = 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++;
	printf("元素%d已被插入到顺序表中\n",e);
	return OK;	
}

//  打印顺序表
Status ListPrint_Sq(SqList *L){
	ElemType *p,*q;
	if(L->length == 0){
		printf("顺序表为空\n");
		return ERROR;
	}
	p = L->elem;//取出顺序表的首地址
	q = L->elem + L->length - 1;//取出顺序表的末地址
	printf("顺序表元素为：");
	while(p <= q ){
		printf("%d\t",*p);
		p++;
	}
	printf("\n");
	return OK;
}

// 删除顺序表中的第i个元素　
Status ListDelete_Sq(SqList *L,int i){
	ElemType *p,*q,e;
	if(i < 1 ||  i > L->length){
		printf("位置不合法\n");
		return ERROR;
	}
	p = &(L->elem[i-1]);//取出被删除元素的地址
	e = *p;//取出被删除元素
	q = L->elem + L->length -1;
	while(p < q){
		*p = *(p+1);
		p++;
	}
	L->length--;
	printf("元素%d已被删除\n",e);
	return OK;

}

//得到顺序表的长度
int  ListLength_Sq(SqList *L){
	return L->length;
}

//判断是否为空表
Status ListEmpty_Sq(SqList *L){
	if(L->length == 0){
		printf("表为空\n");
		return TRUE;
	}
	else{
		printf("表不空\n");
		return FALSE;

	}
}
//清空顺序表
Status ClearList_Sq(SqList *L){
	L->length = 0;
}

//销毁顺序表
Status DestroyList_Sq(SqList *L){
	free(L->elem);
	L->length = 0;
	return OK;
}

//查找指定位置的元素
Status GetListElem_Sq(SqList *L,int i){
	ElemType *p;
	if( i < 1 || i > L->length){
		printf("位置不合法\n");
		return ERROR;
	}
	p = &(L->elem[i-1]);
	printf("查找成功，顺序表的第i个元素为%d",*p);
	return OK;

}
// 查找满足条件的元素，并返回查找到第一个的位置
int LocateList_Sq(SqList *L,ElemType e){
	ElemType *p,*q;
	int l=0,flg=0;
	p = L->elem;
	q = L->elem + L->length -1;
	while(p  <= q){
		if( e == *p){
			flg = 1;
			break;
		}
		l++;
		p++;
	}
	if(flg == 0){
		printf("顺序一中没有这个元素\n");
		return 0;
	}
	printf("查找成功，该元素在顺序表中的第%d个位置",l);
	return l;

}

      测试时，在主函数里先定义一个结构体SqList L，然后就可以测试相关的函数了，如InitList_Sq(&L);或ListPrint_Sq(&L);

      顺序表总结：

             1. 在顺序表上进行插入运算时，需要移动表中的一半的数据元素，其时间复杂度为O(n)。

             2. 在顺序表上作删除运算时，大约需要移动表中一半的元素，其时间复杂度为O(n)。

             3. 线性的顺序存储结构的特点是线性表中逻辑关系上相信的数据元素在物理上也相邻，即用物理上相邻实现逻辑上相邻，它要求用连续的存储单元顺序存储线性表中的各个元素，这一特点使得顺序表有如下优缺点：

                  主要优点：

                       1） 无须为表示元素间的逻辑关系而增加额外的存储空间。

                       2） 可以方便地随机存取线性表中的任一元素。

                  主要缺点：

                       1） 插入和删除不方便。为了保持顺序表中数据元素之间的逻辑关系，在插入和删除运算时需要移动大量的元素，影响了去处的效率。

                       2） 顺序表的长度总有一定的限制，需要预先估算所用空间的大小，若估计小了，会造成顺序表的溢出；若估计大了，会造成存储空间的浪费。

标签：

相关文章