顺序表之C语言实现

线性表的类型定义

线性表(linear-list)是最常用且最简单的一种数据结构。简言之,一个线性表是n个数据元素的有限序列。

在稍复杂的线性表中,一个数据元素可以由若干个数据项(item)组成。在这种情况下,常把数据元素称为记录(record),含有大量记录的线性表又称文件(file)。

线性结构的特点是:在数据元素的非空有限集中，

• (1)存在惟一的一个被称做“第一个”的数据元素;
• (2)存在惟一的一个被称做“最后一个”的数据元素;
• (3)除第一个之外,集合中的每个数据元素均只有一个前驱;
• (4)除最后一个之外,集合中每个数据元素均只有一个后继。

线性表中元素的个数n(n≥0)定义为线性表的长度,n=0时称为空表。

在非空表中的每个数据元素都有一个确定的位置,如a1是第一个数据元素,an是最后一个数据元素,ai是第i个数据元素,称i为数据元素a;在线性表中的位序。
线性表是一个相当灵活的数据结构,它的长度可根据需要增长或缩短，即对线性表的数据元素不仅可以进行访问,还可进行插入和删除等。

线性表的顺序表示和部分实现

线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。

假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC(Ai+1)和第i个数据元素的存储位置LOC(ai,)之间满足下列关系:

一般来说,线性表的第i个数据元素a;的存储位置为

式中LOC(a1)是线性表的第一个数据元素a1的存储位置，通常称做线性表的起始位置或基地址。

顺序线性表的特点是以元素在计算机内“物理位置相邻"来表示线性表中数据元素之间的逻辑关系。每一个数据元素的存储位置都和线性表的起始位置相差一个和数据元素在线性表中的位序成正比的常数。

由此，只要确定了存储线性表的起始位置,线性表中任一数据元素都可随机存取,所以线性表的顺序存储结构是一种随机存取的存储结构。

线性表的动态分配顺序存储结构

#define SEQLIST_INIT_SIZE 6
#define INC_SIZE 3

typedef struct SeqList{
	ElemType *base;
	int capacity;
	int size;
}SeqList;

typedef int ElemType;

初始化

void InitSeqList(SeqList *list){
	list->base = (ElemType*)malloc(sizeof(ElemType) * SEQLIST_INIT_SIZE);
	assert(list->base != NULL);
	list->capacity = SEQLIST_INIT_SIZE;
	list->size = 0;
}

增配线性表空间大小

bool INC(SeqList *list){
	ElemType *newbase = (ElemType*)realloc(list->base,sizeof(ElemType)*(list->capacity+INC_SIZE));
	if(newbase == NULL){
		printf("增配空间失败！内存不足\n");
		return false;
	}
	list->base = newbase;
	list->capacity += INC_SIZE;
	return true;
}

头插法添加元素

void PushFornt(SeqList *list, ElemType data){
	if(Is_Full(list) && !INC(list)){
			printf("顺序表空间已满！头部插入数据%d失败！\n", data);
			return;
		}
	for(int i=list->size;i>0;--i){
		list->base[i] = list->base[i-1];
	}
	list->base[0] = data;
	list->size++;
}

头部删除元素

ElemType PopFornt(SeqList *list){
	if(Is_Empty(list)){
			printf("顺序线性表为空！删除失败！\n");
			return -1;
		}
	ElemType temp = -1;
	temp = list->base[0];
	for(int i=0;i<list->size-1;i++){
		list->base[i] = list->base[i+1];
	}
	list->size--;
	return temp;
	
}

按位置插入元素

void InsertPost(SeqList *list,int pos,ElemType data){
//	if(Is_Full(list)){
//		printf("顺序线性表已满，插入失败！\n");
//		return;
//	}
	if(pos<0 || pos>list->size){
		printf("插入位置非法，插入失败！\n");
		return;
	}
	/*if(0 == pos)
		PushFornt(list,data);
	else if(pos == list->size)
		PushBack(list,data);
	else{
		for(int i = list->size;i>pos;--i){
				list->base[i] = list->base[i-1];
			}
			list->base[pos] = data;
			list->size++;
	}*/
	
	for(int i = list->size;i>pos;--i){
		list->base[i] = list->base[i-1];
	}
	list->base[pos] = data;
	list->size++;
}

按位置删除元素

ElemType DeletePost(SeqList *list,int pos){
	if(Is_Empty(list)){
		printf("顺序线性表元素为空，无法删除！\n");
		return -1;
	}
	if(pos<0 ||pos>=list->size){
		printf("删除位置非法\n");
		return -1;
	}
	ElemType temp;
	temp = list->base[pos];
	for(int i=pos;i<list->size-1;i++){
		list->base[i] = list->base[i+1];
	}
	list->size--;
	return temp;
}

采用冒泡排序法进行排序

void Sort(SeqList *list, bool reverson){
	if(list->size<2)
		return;
	if(reverson){
		for(int i=0;i<list->size-1;i++){
			bool isSorted = true;
			for(int j=0;j<(list->size-i)-1;j++){
				if(list->base[j]>list->base[j+1]){
					ElemType temp = list->base[j];
					list->base[j] = list->base[j+1];
					list->base[j+1] = temp;
					isSorted = false;
				}
			}
			if(isSorted) break;   //如果没有发生交换，证明数组已为降序
		}
	}
	else {
			//····
    }
}

倒置线性表内元素

void Inversion(SeqList *list){
	if(list->size<2)
		return;
	ElemType temp;
	int high = list->size-1;
	int low = 0;
	while(low<=high){
		temp = list->base[low];
		list->base[low] = list->base[high];
		list->base[high] = temp;
		high--;
		low++;
	}
}

销毁

void Distory(SeqList *list){
	free(list->base);
	list->base = NULL;
	list->capacity = 0;
	list->size = 0;
}

合并两个顺序表

void Merge(SeqList *list_1,SeqList *list_2,SeqList *list){
	list->capacity = list_1->size + list_2->size;
	list->base = (ElemType*)malloc(sizeof(ElemType)*list->capacity);
	assert(list->base != NULL);
	int i = 0;
	int i1 = 0;
	int i2 = 0;
	while(i1<list_1->size && i2<list_2->size){
		if(list_1->base[i1] < list_2->base[i2])
			list->base[i++] = list_1->base[i1++];
		else
			list->base[i++] = list_2->base[i2++];
	}
	while(i1 < list_1->size){
		list->base[i++] = list_1->base[i1++];
	}
	
	while(i2 < list_2->size){
			list->base[i++] = list_2->base[i2++];
		}
	list->size = list_1->size + list_2->size;
}

获取完整实现代码

微信关注