順序表 題目一: 題目分析: 該題目需要先對順序表進行遍歷至元素x正確插入位置,再對順序表完成插入操作。因此涉及到for迴圈與if語句的使用 代碼實現 /******************************************************************** * * ...
順序表
題目一:
題目分析:
該題目需要先對順序表進行遍歷至元素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;
}