线性表的顺序实现和基本函数_C

最近在学习数据结构，决定将所有的代码写一遍。其他的数据结构逐步推进。

预处理文件与顺序表结构

基本函数与实现

初始化

求长度

打印表

添加节点

随机赋值

快速排序

删除节点

查找节点

获取特定节点元素

判断是否为空

删除顺序表

预处理文件与顺序表结构

 #include 
 #define LIST_INIT 100		//初始化分配的地址 
 #define LIST_INCREMENT 10	//增加的大小，分配增量 
 #define ElemType int
 using namespace std; 
 
typedef struct{
 	ElemType 	*elem;		//存储地址基地址 
 	int 		length;		//当前长度 
 	int 		listsize;	//当前分配的存储容量(以sizeof(ElemType))为单位 
 }SqList;

基本函数与实现初始化

 int init(SqList &sqlist){
 	sqlist.elem = (ElemType*)malloc(LIST_INIT*(sizeof(ElemType)));
 	if(!sqlist.elem)exit(0);
 	sqlist.listsize = LIST_INIT;
 	sqlist.length = 0;
 	
 	return 1;
 }

求长度

 int listLength_Sq(SqList L){
 	if(L.elem == NULL){
 		return -1;
	 }
	return L.length;
 }

打印表

 int printList(SqList L){
 	for(int i=0;i

 
添加节点 
int add(SqList &L,int position , int elem){
 	if(position<1||position>L.length+1){
 		return -1;
	 }
	if(L.length>=L.listsize){
		ElemType* newbase = (ElemType*)realloc(L.elem,(L.listsize+LIST_INCREMENT)*(sizeof(ElemType)));
		if(!newbase) return 0;
		L.elem = newbase;
		L.listsize+=LIST_INCREMENT;
	}
	int i = L.length;
	while(i >= position){
		L.elem[i] = L.elem[i-1];
		i--;
	}
	L.elem[i] = elem;
	L.length++;
	return i;
 } 
随机赋值 
 int assignment(SqList &L,int j){
 	for(int i=1;i<=j;i++){
 		ElemType target = rand()%100+1;
 		
 		add(L,i,target);
	 }
 } 
快速排序 
/*
  * 绝对分割函数 
  */ 
 int partition(SqList &L,int low,int high){
 	int base = L.elem[low];
 	while(low < high){
 		while(L.elem[high] >= base && low < high){	// 要是倒序的话 就把这里换成小于等于 
			high--;
		}
		L.elem[low] = L.elem[high];
 		while(L.elem[low] <= base && low < high){	// 要是倒序的话 就把这里换成大于等于 
 			low++;
		 }
		L.elem[high] = L.elem[low];
	 }
	 L.elem[low] = base;
	 return low;
	
 }
 
 
  /*
  * 快排
  */ 
 int quickSort(SqList &L,int low, int high){
 	if(low < high){
 		int pivot = partition(L,low,high);
 		quickSort(L,low,pivot-1);
 		quickSort(L,pivot+1,high);
	 }
 } 
删除节点 
int listDelete_Sq(SqList &L,int position,ElemType &e){
 	if(position<1||position>listLength_Sq(L)){
 		return -1;
	 }
	 
	 e =L.elem[position -1];
	 int i = position;
	 while(i <= listLength_Sq(L)-1){
	 	L.elem[i-1] = L.elem[i];
	 	i++;
	 }
	 L.length--;
	 return 0;
 } 
合并顺序表 
int Union(SqList l1,SqList l2,SqList &l3){
 	int l1_length = listLength_Sq(l1);
 	int l2_length = listLength_Sq(l2);
	init(l3);
	int index=1,index1=0,index2=0;
	while(index1 < l1_length && index2 < l2_length){
		if(l1.elem[index1] <= l2.elem[index2]){
			ElemType elem = l1.elem[index1];
			add(l3,index,elem);
			index1++;
		}else{
			ElemType elem = l2.elem[index2];
			add(l3,index,elem);
			index2++;
		}
		index++;
	}
	while(index1 < l1_length){
		ElemType elem = l1.elem[index1++];
		add(l3,index++,elem);
	}
	while(index2 < l2_length){
		ElemType elem = l2.elem[index2++];
		add(l3,index++,elem);
	}
	
	return 1; 
 } 
查找节点 
 int locateElem(SqList &L,ElemType e){
 	int i = 0;
 	while(L.elem[i] != e && i < listLength_Sq(L)){
 		i++;
	 }
	 if(i == listLength_Sq(L))
	 	return -1;
	return i+1;
 } 
获取特定节点元素 
 int getElem(SqList &L,int position){
 	if(position<1 || position > listLength_Sq(L)){
 		return -1;
	 }
	 return L.elem[position-1];
 } 
判断是否为空 
int isEmpty(SqList &L){
 	if(!L.elem){
 		return -1;
	 }
	return 1;
 } 
删除顺序表 
 int destroyList(SqList &L){
 	free(L.elem);
 	L.elem = NULL;
 	L.length = 0;
 	L.listsize = 0;
 	return 1;
 } 
					
										


					
						欢迎分享，转载请注明来源：内存溢出
原文地址: https://www.outofmemory.cn/langs/717128.html

线性表的顺序实现和基本函数

发表评论

评论列表（0条）