计算机考研数据结构代码题总结--Day01

在带头节点的单链表L中，删除所有值为X的结点，并释放其空间，假设值为X的节点不唯一，试编写算法实现。

.算法思路

1、图解
.
2、图解含义描述

1. 实现带头节点的单链表的删除指定值的操作。
2. 首先需要定义三个指针，其中pre指向的是头节点，p初始化指向为L头节点的下一个节点，q作为操作指针。如图所示
3. 算法的思想便是对单链表进行遍历
4. 遍历过程中对p指针的数据域进行比对
5. 相等的数据域与X相等，那么便要进行删除操作。

关键操作
1、. 删除操作首先需要将q操作指针指向p；
2、p指向next邻域
3、pre的next邻域指向p；
4、free释放q指针的空间。

核心代码如下：

if (p->data == x )
{
	q = p;
	p = p->next;
	pre->next = p;
	free(q);
}

当然若当前的数据域不等于匹配值X，那么我们需要对其进行往后继续寻找，也就是pre需要指向p，p需要指向它的下一个节点。
操作代码如下：

if (p->data == x )
{
	q = p;
	p = p->next;
	pre->next = p;
	free(q);
}else{//若没有找到X
	pre = p;
	p = p->next;
}

完整解答代码如下：

//这里必须要添加一个&的引用符号，因为要对单链表进行数据的修改操作，
//必须要添加&符号
void Del_X(linkList &L , ElemType X){
	//定义指针节点
	LNode * pre = L;//指向头节点
	LNode * p = L->next;//指向头节点的下一个节点
	LNode * q;//操作节点
	while(p != NULL){
		if(p->data == X){
			//进行删除操作
			q = p;
			p = p->next;//转移指针空间
			pre->next = p;//保证pre链表的连续性
			free(q);//释放单独的q指针删除节点的空间
		}else{
			//没有找到x,继续往下找
			pre = p;
			p = p->next;
		}
	}
}

在长度为n的顺序表L中，编写一个时间复杂度为0(n),空间复杂度为O(1)的算法，该算法删除所有值为X的数据元素

题目分析

1. 时间复杂度为0(n)代表着只能扫描一趟顺序表数组
2. 空间复杂度为0(1)代表着只能开辟常量级个数组空间，也就是不能在申请一个数组。
3. 找到需要查找的数据X
4. 删除相关位置的元素，并向前移动进行操作。

算法思路

1. 算法实现的思想包括进行查找和删除(这里是指移动元素的操作)
2. 设置一个记录数k
3. 每次当顺序表的数据进行匹配X成功时，k便+1
4. 若当前的匹配位置不是X，那么将会对其进行元素进行前移覆盖的方式进行元素的删除操作(移动i-k个单位)。

核心代码如下：

if(L.data[i] == X){
	//若找到了X的数值
	//进行记录+1
	k++;
}else{
	L.data[i-k] = L.data[i];
	i++;//前移后进行下一个位置的查找
}

其完整回答代码如下：

//必须添加&符号，因为要对顺序表进行删除
void Del_X(SqList &L,ElemType X){
	int i = 0;
	while(i < L.length){
		int k = 0;//初始化记录数
		if(L.data[i] == X){
			k++;//添加记录数
		}else{
			L.data[i-k] = L.data[i];
			i++;//继续向后查询
		}
	}
}

设计一个高效算法，将顺序表L的所有元素逆置，要求算法的空间复杂度为0(1)。

题目分析：
1、要求的空间复杂度为0(1)代表只能申请常量的存储空间

算法图解思路

实现思路：

1. 需要对第一个元素与第n个元素进行交换，然后对其进行依次比较进行交换
2. 采用常规循环和递归进行实现。

1、实现代码常规方式

//采用常规的循环方式实现
void Reverse(SqlList &L){
	ElemType tem;//定义一个临时的存储变量
	//
	for (int i = 0; i < L.length/2; i++)
	{
		temp = L.data[i];
		L.data[i] = L.data[L.length-i-1];
		L.data[L.length-i-1] = temp;
	}
}

2、实现代码递归方式

//采用递归方式实现
void ReverseByRecursion(int * A,int low ,int high){
	if(low < high){
		swap(A.low,A.high);
		ReverseByRecursion(A,low+1,high-1);

	}
}
//交换函数
void swap(int a ,int b){
	int temp = a;
	a = b;
	b = temp;
}

将两个有序顺序表合并为一个新的有序表，并返回结果顺序表

算法编写思路分析：

思路：

1. 定义三个指针i指向A，j指向B的第一个元素，k指向C的第一个元素。
2. 如果A的i的数据域小于B的数据域那么添加到C的第一个元素

其完全代码如下：

 //采用bool文件进行设计
 //因为要对C顺序表进行添加操作，需要添加&符号
bool Merge(Sqlist A,Sqlist B, Sqlist &C){
	//进行比较
	if(A.length + B.length > C.MAXSIZE){
		return false;
	}
	int i = 0;
	int j = 0;
	int k = 0;
	//设置循环条件
	while(i