计算机数据结构代码题----Day02

计算机数据结构代码题----Day02

顺序表代码题

题目01

从顺序表中删除其数值在给定数值为s与t之间，包含(s和t)，要求（s<t）的所有元素，如果s或t的顺序不合理或者顺序表为空，则显示出错误信息。

1、算法图解
如下图

思路：

1. 扫描顺序表，将S->t的数进行搜索，
2. 扫描到该范围内进行记录数K+1，
3. 若不是在s到t之间范围的数，那么就要进行前移动k个单位长度，与上一篇的删除数据进行设计。

实现步骤
1、核心代码：

	int k = 0;
	while(i<L.length){
		if(L.data[i] >= s  && L.data[i] <= t){//对s与t之间的数据范围进行扫描
			//若在当前范围内进行记录数的+1
			k++;
		}else{//若不在s到t之间的范围内
			//前移
			L.data[i-k] = L.data[i];
			i++;
		}

	}
1
2
3
4
5
6
7
8
9
10
11
12

2、完整框架代码：
设置布尔类型作为返回值类型

/*
 *从顺序表中删除其数值在给定数值为s与t之间，
 *包含(s和t)，要求（s<t）的所有元素，
 *如果s或t的顺序不合理或者顺序表为空
 *则显示出错误信息
 */
//由于要对顺序表l进行删除操作，必须要添加&符号
boolean Del_SToTRange(Sqlist &L , ElemType s,ElemType t){
	//进行合法性判断
	if(s>=t || L.length == 0){
		return false;
	}
	//进行查询操作
	int k = 0;
	while(i<L.length){
		if(L.data[i] >= s && L.data[i] <= t){
			k++;//在该范围内进行记录数+1
		}else{
			L.data[i-k] = L.data[i];//前移K个单位
			i++;//往后继续进行遍历顺序表
		}
	}
	L.length = L.length - K;//统计顺序表长度
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

题目02

从有序顺序表中删除所有值重复的元素，使表中所有的元素的值均不同。
分析

1、算法思路图解

思路

1. 为保证扫描到相同位置的元素，设置两个指针i和j
2. i指向第一个元素，作为“覆盖指针”
3. j指向与i相邻的元素进行操作扫描元素
4. 其实现的流程图为下图
   
   其实现的核心代码如下：

for(int i = 0,j=1;j<length;j++){//以j为操作指针进行遍历
	if(L.data[i] != L.data[j]){//i与j元素不相等
		//覆盖
		//首先要使i进行+1
		i++;
		L.data[i] = L.data[j];
	}
	//这里由于拥有for循环默认执行j++；
	//在i与j指向元素相等时进行j+1
}
1
2
3
4
5
6
7
8
9
10

代码的执行流程
这里以下图所示，举出刚开始i=0，j=1的情况下的图解

第二个例子
取i=1，j=2往后到j=3的执行过程：

1. 当i=1，j=2这里的i与j所指向的元素相等
2. 执行j++；
3. j = 3;
4. 由于j所指向的元素与i元素不等
5. 进行覆盖
6. i++ = 2；
7. 现在2位置的数为3
8. 总的前面三个位置的数为123

完整代码如下

/*
 *从有序顺序表中删除所有值重复的元素，
 *使表中所有的元素的值均不同。
 */
//由于要对顺序表l进行删除操作，必须要添加&符号
boolean Del_Same(Sqlist &L){
	//合法性判断
	if(L.length == 0){
		return false;
	}
	for(int i = 0,j=1;j<length;j++){
		if(L.data[i] != L.data[j]){
			i++;
			L.data[i] == L.data[j];
		}
	}
	L.length = i+1;
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

题目03

已知在一个一维数组A【m+n】中依次存放两个线性表，(a1,a2,a3…am)和(b1,b2,b3…bn)，试着编写一个函数，将数组中两个顺序表的位置互换，即实现数组的位置为(b1,b2,b3…bn)((a1,a2,a3…am))

算法思路图解

根据上图的实现步骤，核心就在于如何完成逆置
这里采用上一篇文章的逆置方式，下面是连接
数据结果代码题day01

核心代码如下：

//转置函数
//这里的from代表左节点，to代表右结点
void Reverse(int[] A,int from,int to){
	int temp;//开辟一个临时存储交换数值
	//为方便置换，采用中间位置进行分割，即(to-from+1)/2位置
	for(int i = 0;i<(to-from+1)/2;i++){
		temp = L.data[from+i];//交换操作
		L.data[from+i] = L.data[to-i];
		L.data[to-i] = temp;
	}
}
1
2
3
4
5
6
7
8
9
10
11

完整代码如下：

/*
 *已知在一个一维数组A【m+n】中依次存放两个线性表，
 *(a1,a2,a3.....am)和(b1,b2,b3..bn)，试着编写一个函数，
 *将数组中两个顺序表的位置互换，
 *即实现数组的位置为(b1,b2,b3..bn)((a1,a2,a3.....am))
 */
//转置函数
//这里的from代表左节点，to代表右结点
void Reverse(int[] A,int from,int to){
	int temp;//开辟一个临时存储交换数值
	//为方便置换，采用中间位置进行分割，即(to-from+1)/2位置
	for(int i = 0;i<(to-from+1)/2;i++){
		temp = L.data[from+i];//交换操作
		L.data[from+i] = L.data[to-i];
		L.data[to-i] = temp;
	}
}
//核心函数
void Exchange(int[] A,int m,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
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

注：

个人代码问题或需要程序编写辅导服务等问题请加闲鱼【代码无bug】
或点击下面链接跳转闲鱼进行咨询

闲鱼链接