顺序表和链表的练习题

2024-04-22 22:02 由飞子的唠唠叨发表于 #操作系统

顺序表

题目一：

题目分析：

该题目需要先对顺序表进行遍历至元素x正确插入位置，再对顺序表完成插入操作。因此涉及到for循环与if语句的使用

代码实现

/********************************************************************
*
*	name	 :	SequenceList_insert
*	function :  实现插入元素x，并保持链表的递增顺序
*	argument :  
*				@*L 顺序表首元素地址
				@x  插入元素值
*				
*	retval	 :  none
*	author	 :  [email protected]
*	date	 :  2024/04/22
* 	note	 :  none
* 	
* *****************************************************************/
void SequenceList_Insert(SeqList_t *L,int x)
{
	//定义一个变量用于存储正确位置的下标
	int temp = -1;
	//对顺序表内元素与x进行大概判断
	if( x > L[last / 2])
	{
		for (int i = (last / 2) + 1; i <= last;i++)
		{
			if(x < L[i])
			{
				temp = i;
				break;
			}
		}
		//将插入位置后的后继元素后移
		for (int i = last; i >= temp;i--)
		{
			L[i + 1] = L[i];
		}

		//插入x
		L[temp] = x;
	}	
	else
	{
		//遍历查找x元素插入位置
		for (int i = 0; i <= (last / 2);i++)
		{
			if(x < L[i])
			{
				temp = i;
				break;
			}
		}
		//将插入位置后的后继元素后移
		for (int i = last; i >= temp;i--)
		{
			L[i + 1] = L[i];
		}

		//插入x
		L[temp] = x;
	}

题目二：

题目分析

该题目需要对顺序表制定元素删除，并且还需要返回值。所以定义的函数接口不能为void类型，使用for循环对p后继顺序表元素进行遍历前移，且考虑可能出现删除失败的原因

代码实现

/********************************************************************
*
*	name	 :	SequenceList_Del
*	function :  实现删除顺序表指定位置元素
*	argument :  
*				@*L 顺序表首元素地址
				@p  指定位置p
*				
*	retval	 :  none
*	author	 :  [email protected]
*	date	 :  2024/04/22
* 	note	 :  none
* 	
* *****************************************************************/
int SequenceList_Del(SeqList_t *L, int p)
{
	//排除p错误情况
	if(p < 0 || p> length -1)
		return 0;

	//将被删除位置p的元素赋值给e
	int e;
	L[p] = e;
	//对位置p的后继元素进行
	for (int i = p; i <= last; i++)
	{
		L[i] = L[i + 1];
	}
	//将最后顺序表最后元素清零且last减少1
	L[last] = 0;
	last--;
	return 1;
}

链表

题目一：

题目分析：

该题目涉及到单向链表的遍历与删除。首先，定义一个结构体指针变量，用于在遍历时存储最小值节点的直接前驱节点的地址；其次，需要对最小值节点位置进行判断，排除掉该节点为尾节点的情况；最后，利用该指针变量完成目标节点的删除操作

代码实现

/********************************************************************
*
*	name	 :	LkList_MinDle
*	function :  实现删除单向链表的最小值节点
*	argument :  
*				@*L 单向链表头结点
*				
*	retval	 :  none
*	author	 :  [email protected]
*	date	 :  2024/04/22
* 	note	 :  none
* 	
* *****************************************************************/
void LkList_MinDle(LkList_t*L) //假设单向链表结构体类型为 LkList_t
{
	//定义个结构体指针变量p1指向头结点L ，p2为循环指针变量,p3为循环变量的前驱节点
	LkList_t *p1 = L;
	LkList_t *p2 = NULL;
	LkList_t *p3 = L;

	//定义一个变量用于存储数据最小值,假设数据类型为int
	int Data_Min = p2->data;

	//遍历出最小值节点的位置,循环中止条件，即循环至尾结点
	for (p2 = L->next ; p2 != NULL;p2 = p2->next)
	{
		//判断是否为最小值节点
		if((p2->data) > (p2->next->data))
		{
			Data_Min = p2->next->data;
			p1 = p2;    //将p1变为最小值节点的直接前驱节点
		}
		p3 = p3->next;  //p3为p2的直接前驱节点
	}

	//判断最小值节点是否为尾节点,此时的p2为链表尾节点
	if( Data_Min > p2->data )
	{
		//先连接
		p3->next = NULL;
		//再删除
		free(p2);
		return; 		//结束该函数
	}

	//排除最小值节点为尾节点后,将最小值节点备份至p2
	p2 = p1->next;
	p1->next = p1->next->next;
	p2->next = NULL;
	
	//释放掉p2
	free(p2);
    
	return; //正常退出函数
}

题目二:

代码分析：

对题目要求分析可得，[p1和 p2之间节点个数差 = k],其中p1为题目所求位置节点，p2为链表尾节点，K为题目中所给数,

回答：

1）该算法需要定义两个结构体指针变量p1和p2，其中p2需从单链表头结点遍历至尾结点，p1则需按照[p1和 p2之间节点个数差 = k ]公式调整距离尾结点的个数，随后返回p1节点的data值和1；当链表中无节点时，返回0.

2）首先，定义两个结构体指针变量p1和p2；其次，对链表元素个数进行判断，进行错误情况排除；最终，利用for循环遍历链表，将p1和p2分别表示正确的节点，返回p1的data值和1

3）代码实现：

/********************************************************************
*
*	name	 :	LkList_Reciprocal
*	function :  实现输出单链表的第K个值的data值
*	argument :  
*				@*head 单向链表的头结点
				@k 倒数第几个数
*				
*	retval	 :  调用成功输出倒数第k个节点的data值并且返回1；否则返回0.
*	author	 :  [email protected]
*	date	 :  2024/04/22
* 	note	 :  none
* 	
* *****************************************************************/

//假设data类型为int
int LkList_Reciprocal(LkList_t*head, int k)
{
	LkList_t *p1 = head;
	LkList_t *p2 = head;
	//定义一个整型变量i，进行判断p2位置
	int i = 0;

	//排除错误情况
	if(p2->next == NULL)
	{
		return 0;
	}

	//当p2为尾节点时跳出while循环
	while(p2->next)
	{
		p2 = p2->next;
		i++;
		if(i >= k) //当p1和p2之间节点差为k后，p1和p2需要同时前进遍历
		{
			p1 = p1->next;
		}
	}

	printf("倒数第(k = %d)个节点的data值为:%d\n", k, p1->data);
	return 1;
}