# dataStructures

**Repository Path**: hjwei305/data-structures

## Basic Information

- **Project Name**: dataStructures
- **Description**: 数据结构学习
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2021-06-11
- **Last Updated**: 2022-04-15

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# dataStructures

数据结构学习

-[1.学习大纲](#1学习大纲)

-[2.线性表](#2线性表)

### 1.学习大纲

![](./picture/1-知识架构.png)



### 2.线性表

![](./picture/2-线性表.png)


//1、结构初始化

status InitList_Sq(SeList &L){

	L.elem = (ElemType*)malloc(LIST_INT_SIZE * sizeof(Elemtype));
	
	if(!L.elem)
		exit(OVERFLOW);	
		
	L.length = 0;
	
	L.listsize = LIST_INT_SIZE;
	
	return OK;
	
}

//2、扩展线性表L的容量-ExtendList的实现

status ExtendList_Sq(SqList &L){
	
	newbase = (ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
	
	if(!newbase)
		exit(OVERFLOW);
		
	L.elem=newbase;
	
	L.listsize+=LISTINCREMENT;
	
	return OK;
	
}

3、查找元素

算法时间复杂度:O(ListLength(L))

int LocateElem_Sq(SqList L,ElemType e,Status(*compare)(ElemType,Elemtype)){
	
	i = 1;
	p = L.elem;
	
	while(i<=L.length&&!(*compare)(*p++,e))
	
		++i;
		
	if(i<=L.length)
		return i;
		
	else
		return 0;
}

4、线性表的插入

时间复杂度:

线性表中任何一项插入的概率是相等的：p(n) =  1 / n+1 ;

全部项的插入移动综合 (1+n) * n / 2;

所以时间复杂度为    [1/(n+1)]*[(1+n)*n/2]  O(n/2)记O(n)

Status ListInser_Sq(SqList &L,int i,ElemType e){
	
	//判断插入元素位置是否合法
	
	if(i<1||i>L.length+1)
		return ERROR;
	
	//如果长度超过，则要重新分配空间
	
	if(L.length>=L.listsize)
	
			newbase = (ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
	
	if(!newbase)
		exit(OVERFLOW);
		
	//新的基地址
	
	L.elem=newbase;
	
	//容量新增
	
	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;
	
	return OK;
	
}


5、线性表删除操作：

算法时间复杂度:O(ListLength(L))

Status ListDelete_Sq(SqList &L,int i,ElemType &e){
	
	//判断删除元素的位置是否合法
	
	if((i<1)||(i>L.length))
		return ERROR;
	
	//被删除元素的地址
	
	p=&(L.elem[i-1]);
	
	//被删除元素的值赋予e
	
	e = *p;
	
	//表尾元素的位置
	
	q = L.elem + L.length-1;
	
	//把元素值赋予前一个元素
	
	for(++p;p<q;++p)
		*(p-1) = *p;
		
	//长度减1
	
	--L.length;
	
	return OK;
	
}


6.合并

时间复杂度O(La.length+Lb.length)

void MergeList(SqList La,SqList Lb,SqList &Lc){
	
	pa = La.elem;pb=Lb.elem;
	
	//创建一个新的顺序表
	
	Lc.listsize = La.listsize + Lb.listsize;
	
	pc = Lc.elem = (ElemType *)malloc(Lc.listsize*sizeof(ElemType))
	
	if(!Lc.elem)
		exit(OVERFLOW);
		
	//pa_last指示La表最后一个元素
	
	pa_last = La.elem + La.length-1;
	
	//pa_last指示Lb表最后一个元素
	
	pb_last = Lb.elem + Lb.length-1;
	
	while(pa <= pa_last && pb <= pb_last)
	{
		if(*pa<=*pb)
			*pc++ = *pa++;
			
		else
			*pc++ = *pb++;
	}
	
	while(pa<=pa_last)
		*pc++ = **pa++;
		
	while(pb <= pb_last)
		*pc++ = *pb++;	
}

#### Installation

1.  xxxx
2.  xxxx
3.  xxxx

#### Instructions

1.  xxxx
2.  xxxx
3.  xxxx

#### Contribution

1.  Fork the repository
2.  Create Feat_xxx branch
3.  Commit your code
4.  Create Pull Request


#### Gitee Feature

1.  You can use Readme\_XXX.md to support different languages, such as Readme\_en.md, Readme\_zh.md
2.  Gitee blog [blog.gitee.com](https://blog.gitee.com)
3.  Explore open source project [https://gitee.com/explore](https://gitee.com/explore)
4.  The most valuable open source project [GVP](https://gitee.com/gvp)
5.  The manual of Gitee [https://gitee.com/help](https://gitee.com/help)
6.  The most popular members  [https://gitee.com/gitee-stars/](https://gitee.com/gitee-stars/)