动态分配数组实现的顺序表

今天也要努力学习，争取考上杭电。

顺序表的知识

顺序表即线性表的顺序存储。
用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。所以，顺序表的特点是表中元素的逻辑顺序与其物理顺序相同。
用到的一维数组可以静态分配，也可以动态分配。
静态分配：静态分配时，因为数组大小和空间已经固定好，占满了新数据就会溢出。
动态分配：占满了就开辟一块新的，不需要一次性就为线性表划分所有空间。
注意动态分配不是链式存储！它同样属于顺序存储结构！依然是随机存取方式！只是分配的空间大小可以在运行时决定！
主要特点是随机访问，通过首地址和元素序号可以在O(1)内找到元素。另一特点是逻辑顺序与其物理顺序相同，所以插入删除要移动大量元素，复杂度O(n)。

C代码实现

结构体定义：

//动态分配数组实现的顺序表 
typedef struct{
	ElemType *spoint,*epoint;	//spoint头指针，epoint尾指针
	int MaxSize;				//最大长度
	int length;					//当前长度
}SqList,*SLP;

相关函数代码：
头文件、用到的宏定义：

#include<stdio.h>
#include<malloc.h>
#include<string.h>

//_bool类型 
#define _bool int
#define true 1
#define false 0

//顺序表元素数据类型 ElemType
#define ElemType int

//默认动态分配空间大小 
#define IniSize 10 

初始化、扩展、销毁、遍历：

//初始化表
_bool IniList(SLP p){
	//void* malloc(unsigned int size);
	p->spoint=(ElemType*)malloc(sizeof(ElemType)*IniSize);
	if(p->spoint==NULL)	return false;
	p->epoint=p->spoint;		//初始没有元素，尾和头一样
	p->MaxSize=IniSize;			//初始值等于默认值
	p->length=0; 
	return true;
}

//扩展表空间
_bool ExpandList(SLP p,int raise){
	ElemType *newspace=(ElemType*)malloc(sizeof(ElemType)*(raise+p->MaxSize));
	if(newspace==NULL)	return false;
	//void *memcpy(void *destin, void *source, unsigned n);
	memcpy(newspace,p->spoint,sizeof(ElemType)*p->MaxSize);
	free(p->spoint);
	p->spoint=newspace;
	p->epoint=p->spoint+p->length;
	p->MaxSize+=raise;
	return true;
} 

//遍历表   返回当前长度 
int TraversalList(SqList l){
	if(l.length==0)	printf("NULL");
	while(l.length--)
		printf("%-5d",*l.spoint++);
	printf("\n");
	return l.length;
}

//销毁表 
_bool DestroyList(SLP p){
	free(p->spoint);
}

添加、插入、删除、查找：

//顺序添加元素
_bool AddList(SLP p,ElemType data){
	if(p->length>=p->MaxSize){
		printf("Cannot add because it exceeds the MaxSize(%d)!\n",p->MaxSize);
		return false;
	}
	*(p->epoint)=data;
	p->epoint++;
	p->length++;
	return true;
}

//指定位置插入元素
_bool InsertList(SLP p,int destin,ElemType data){
	if(destin>=p->MaxSize){
		printf("Cannot insert because %d exceeds the MaxSize(%d)!\n",destin,p->MaxSize);
		return false;
	}
	if(destin>(p->length+1)){
		printf("Cannot insert because %d exceeds the existing length!\n",destin,p->length);
		return false;
	}
	ElemType *q=p->epoint;
	int n=p->length-destin+1;
	while(n--){
		*q=*(q-1);
		*q--; 
	}*q=data;
	p->epoint++;
	p->length++;
	return true;	
}

//删除指定位置元素
_bool DeleteList(SLP p,int destin,ElemType *res){
	if(destin>(p->length)){
		printf("%d is a non-existent position ! Cannot delete!\n",destin);
		return false;
	}
	ElemType *q=p->spoint+(destin-1);
	*res=*(p->spoint+(destin-1));
	int n=p->length-destin;
	while(n--){
		*q=*(q+1);
		*q++; 
	}
	p->epoint--;
	p->length--;
	return true;
}

//按位查找 
_bool GetByDestin(SqList l,int destin){
	if(destin>l.length){
		printf("%d is a non-existent position!\n",destin);
		return false;
	}
	printf("%d / %d : %d\n",destin,l.length,*(l.spoint+(destin-1)));
	return true;
}

//按值查找   成功查找返回第一次出现位序，失败返回false(0) 
int GetByValue(SqList l,ElemType data){
	int i=0;
	if(l.epoint==l.spoint){
		printf("NULL!\n");
		return false;
	}
	while((l.spoint+i)!=l.epoint){
		if(*(l.spoint+i++)==data){
			printf("%d in position %d / %d\n",data,i,l.length);
			return i;
		}
	}
	printf("%d is a non-existent value!\n",data);
	return false;
}

作为菜鸡的我，今天也很努力的好好命名了。动态分配和静态分配的一样也可以用下标访问的。但是我一开始用的地址，后来就也没用下标。删除发完了才发现应该写个按值删除。
嘻嘻嘻嘻，静态的就不写了。明天写链表。
什么时候才能把数据结构书上的数据结构和算法从新整理一遍啊啊啊啊啊啊！！！