[数据结构与算法]数据结构代码合集

线性表

基本操作

线性表的主要操作如下：

不同存储类型的结构

顺序表

//静态分配
#define MaxSize 50
typedef struct{
	ElemType data[MaxSize];
	int length;
}SqList; 
//动态分配
#define InitSize 100
typedef struct{
	ElemType *data;
	int MaxSize,length;
}SeqList; 

InitList(&L):初始化表

初始化表，构造一个空的线性表
顺序表

//静态初始化
void InitList(SqList &L){
	L.length=0;
} 
//动态初始化
void InitList(SeqList &L){
	L.data=(ElemType*)malloc(InitSize*sizeof(ElemType));
	L.length=0;
	L.MaxSize=InitSize;
} 

Length（L）:求表长

顺序表
返回线性表L的长度，即L中数据元素的个数

//Length(L)
//静态 
int Length(SqList L){
	return L.length;
}
//动态
int Length(SeqList L){/
	return L.length;
} 

LocateElem(L,e):按值查找操作

在表L中查找具有给定关键字值的元素
顺序表

//动态和静态相同，以静态为例，区别在于结构名不同 
int LocateElem(SqList L,int e){//按值查找
	for(int i = 0;i < L.length;i++){
		if(L.data[i] == e){
			return i+1;//下标为i等于e时，返回位序为i+1 
		}
	}
	return -1;//查找失败的返回值 
}

平均时间复杂度为：O（n）

GetElem(L,i):按位查找操作

获取表L中第i个位置的元素的值
顺序表

int getElem(SqList L,int p,int &e){
	if(p<0||p>=L.length){//判断是否超过长度
		return 0;
	}
	e=L.data[p];//获取值
	return 1;
}

ListInsert(&L,i,e):插入操作

在表L中第i个位置上插入指定元素e
顺序表

bool ListInsert(SqList &L,int i,ElemType e){
	if(i<0||i>L.length+1)
		return false;
	if(L.length>=MaxSize)
		return false;
	for(int j=L.length;j>=i;j--)//把结点i及后面的结点后移一格 
		L.data[j]=L.data[j-1];
	L.data[i-1]=e;//在i-1处插入值 
	L.length++;//记得插入后需要+1 
	return true; 
}

平均时间复杂度为O（n）

ListDelete(&L,i,&e):删除操作

bool ListDelete(Sqlist &L, int p, ElemType &e){
	if (p<0||p>= L.length) {
		return false;
	}
	e = L.data[p];
	for (int i = p; i < L.length-1; i++) {
	L.data[i] = L.data[i+1];
	}
	--(L.length); 
	return true;
}

时间复杂度为O（n）

PrintList（L）:输出操作

按前后顺序输出线性表L的所有元素值

void PrintList(SqList L){//打印操作 
	for(int i = 0;i < L.length;i++){
		printf("%d",L.data[i]);
	}
}

Empty(L):判空操作

bool Empty(SqList L){//判空操作 
	if(L.length==0) return true;//证明是空的
	return false; 
} 

DestroyList(&L):销毁操作

顺序表
这是动态特有的，静态形式会自动回收

void DestroyList(SeqList &L){//销毁操作 
	if(L.data){
		free(L.data);
		L.data = NULL;//释放L.data指针本身
		L.length = 0;
		L.MaxSize = 0;
	}
}