线性表---顺序表示(day1

#define MaxSize 50
typedef struct{
	ElemType data[MaxSize];
	int length;
}SqList; 
1
2
3
4
5

1)插入

//在第i个位置上插入值x 
bool Insert(SqList L,int i,int x){
	if(i < 1 || i > L.length + 1) return false;
	if(L.length >= MaxSize) return false; 
	for(int j = L.length; j >= i; j --)
		L.data[j] = L.data[j - 1];
	L.data[i-1] = x;
	L.length++;//不要忘记，长度+1 
	return 	true;
} 
1
2
3
4
5
6
7
8
9
10

2)删除

//删除第i个位置上的值，并把值引用给x 
bool Del(SqlList L,int i,int &x){
	if(i < 1 || i > L.length) return false;
	x = L.data[i-1];
	for(int j = i; j < L.length; j ++)
		L.data[j-1]=L.data[j];
	L.length--;
	return true;
} 
1
2
3
4
5
6
7
8
9

3)查找

//找到值为x的元素的下标 
bool FindPos(SqlList L,int x){
	for(int i = 0; i < L.length; i ++ )
		if(L.data[i] == x)
			return i+1;
	return 0;//False
} 
1
2
3
4
5
6
7

4)逆置

//双指针 
void Reverse(SqlList L){
	for(int i = 0,j = L.length-1; i < j; i ++,j --)
		swap(L.data[i],L.data[j]);
}
1
2
3
4
5

5)删除所有值为x的元素

//重新设置一个下标k，同时遍历数组
//若不为x，就加进去 
void Del_x(SqlList L){
	int k=0;
	for(int i = 0; i < L.length; i ++)
		if(L.data[i] != x)
			L.data[k++]=L.data[i];
	L.length=k;
} 
1
2
3
4
5
6
7
8
9

6)删除区间[s,t]的所有元素

//跟5差不多，用下标判断
bool Del_st(SqlList L){
	if(s > t || L.length==0) return false;
	int k=0;
	for(int i = 0; i < L.length; i ++)
		if(i < s || i > t)
			L.data[k++]=L.data[i];
	return true;		
} 
1
2
3
4
5
6
7
8
9

7)有序顺序表，删除重复元素

void Del_Same(SqlList L){
	if(L.length==0) reutnr false;
	int k = 0;
	for(int i = 1; i < L.length; i ++){
		if(L.data[k]!=L.data[i])
			L.data[++k] = L.data[i];
	}
	L.length=k+1;
	return true;
} 
1
2
3
4
5
6
7
8
9
10

8)有序顺序表，合并

void Merge(int A[],int B[],int n,int m){
	int i = 0,j = 0,k = 0,mc=n+m;
	int C[mc];
	while(i < n && j < m){
		if(A[i] <= B[j])
			C[k++]=A[i++];
		else
			C[k++]=B[j++];
	}
	while(i < n) C[k++] = A[i++];
	while(j < m) C[k++] = B[j++];
} 
1
2
3
4
5
6
7
8
9
10
11
12

9)有序顺序表，查找值x

//无脑二分 
bool Binary_Search(int A[],int n,int x){
	int l = 0,r = n-1;
	while(l < r){
		int mid = (l+r)/2;
		if(A[mid] < x) r = mid;
		else l = mid+1;
	}
	if(A[l] != x) return false;
	return true; 
}
1
2
3
4
5
6
7
8
9
10
11

10)改变局部数组，ab->ba,a:[1,m],b:[1:n]

//整体左移m个位置或者右移n个位置 
void Converse(int A[],int n){
	Reverse(A,0,m-1);
	Reverse(A,m,m+n-1);
	Reverse(A,0,m+n-1);
} 
1
2
3
4
5
6

---

转自：数组、链表、树代码题总结——一休