單鏈表的基本操作
第1關(guān)：?jiǎn)捂湵淼牟迦氩僮?/h3>
任務(wù)描述
本關(guān)任務(wù)：編寫(xiě)單鏈表的初始化、插入、遍歷三個(gè)操作函數(shù)。
相關(guān)知識(shí)
鏈表是線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的別稱(chēng)，特點(diǎn)是以“指針”指示后繼元素，因此線(xiàn)性表的元素可以存儲(chǔ)在存儲(chǔ)器中任意一組存儲(chǔ)單元中。
每個(gè)結(jié)點(diǎn)只有一個(gè)指針域的鏈表稱(chēng)為單鏈表。
因此單鏈表的一個(gè)存儲(chǔ)結(jié)點(diǎn)包含兩個(gè)部分，結(jié)點(diǎn)的形式如下：
data：為數(shù)據(jù)域，用于存儲(chǔ)線(xiàn)性表的一個(gè)數(shù)據(jù)元素，也就是說(shuō)在單鏈表中一個(gè)結(jié)點(diǎn)存放一個(gè)數(shù)據(jù)元素。 next：為指針域或鏈域，用于存放一個(gè)指針，該指針指向后繼元素對(duì)應(yīng)的結(jié)點(diǎn)，也就是說(shuō)單鏈表中結(jié)點(diǎn)的指針用于表示后繼關(guān)系。
單鏈表結(jié)點(diǎn)類(lèi)型定義如下：
typedef struct LNode // 結(jié)點(diǎn)類(lèi)型定義
{
ElemType data; //數(shù)據(jù)域
struct LNode *next; //指針域
}LNode,*LinkList; // LinkList為結(jié)構(gòu)指針類(lèi)型單鏈表中數(shù)據(jù)類(lèi)型ElemType可以多種多樣，但是在編程實(shí)現(xiàn)算法時(shí)針對(duì)不同數(shù)據(jù)類(lèi)型，每類(lèi)數(shù)據(jù)元素的輸入輸出是有區(qū)別的，單鏈表的基本操作算法要在計(jì)算機(jī)上執(zhí)行，須針對(duì)ElemType類(lèi)型數(shù)據(jù)編寫(xiě)輸入、輸出、比較等函數(shù)：
void input(ElemType &s);
void output(ElemType s);
int equals(ElemType a,ElemType b);一般情況下使用鏈表只關(guān)心鏈表中結(jié)點(diǎn)之間的邏輯關(guān)系，并不關(guān)心鏈表的每個(gè)結(jié)點(diǎn)的實(shí)際存儲(chǔ)位置，通常用箭頭來(lái)表示鏈域中的指針，鏈表的邏輯結(jié)構(gòu)可以直觀的畫(huà)成用箭頭鏈接起來(lái)的結(jié)點(diǎn)序列。
單鏈表的邏輯示意圖如下：
用單鏈表作存儲(chǔ)結(jié)構(gòu)時(shí)，對(duì)于鏈表的各種操作必須從頭指針開(kāi)始。這里討論的單鏈表除特別指出外均指帶頭結(jié)點(diǎn)的單鏈表。
首先討論如何進(jìn)行單鏈表的初始化操作。
單鏈表的初始化操作
有時(shí)為了操作的方便，還可以在單鏈表的第一個(gè)結(jié)點(diǎn)之前附設(shè)一個(gè)頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的數(shù)據(jù)域可以什么都不存儲(chǔ)，如果線(xiàn)性表為空表，則頭結(jié)點(diǎn)的指針域?yàn)椤翱铡?，空的單鏈表邏輯示意圖如下：
帶頭結(jié)點(diǎn)的單鏈表具有以下兩個(gè)優(yōu)點(diǎn)：
由于起始結(jié)點(diǎn)的位置被存放在頭結(jié)點(diǎn)的指針域中，所以在單鏈表的第一個(gè)位置上的操作與表中的其它位置上操作一致，無(wú)須進(jìn)行特殊處理；
無(wú)論單鏈表是否為空，其頭指針都是指向頭結(jié)點(diǎn)的非空指針（空表中頭結(jié)點(diǎn)的指針域空），因此空表和非空表的處理也就統(tǒng)一了。
構(gòu)建一個(gè)空的單鏈表
void InitList( LinkList &L)
{
// 操作結(jié)果：構(gòu)造一個(gè)空的單鏈表L
L=(LinkList)malloc(sizeof(LNode));
// 申請(qǐng)分配頭結(jié)點(diǎn)，并使L指向此頭結(jié)點(diǎn)
if(!L)
// 存儲(chǔ)分配失敗
return ;
L->next=NULL;
// 頭結(jié)點(diǎn)的指針域?yàn)榭?}查找單鏈表中第i個(gè)數(shù)據(jù)元素值的操作
在單鏈表中，由于每個(gè)結(jié)點(diǎn)的存儲(chǔ)位置都放在其前一結(jié)點(diǎn)的next域中，所以即使知道被訪(fǎng)問(wèn)結(jié)點(diǎn)的序號(hào)i，也不能像順序表那樣直接按序號(hào)i隨機(jī)訪(fǎng)問(wèn)一維數(shù)組中相應(yīng)元素，而只能從鏈表的頭指針出發(fā)，順著指針域next逐個(gè)結(jié)點(diǎn)往下搜索，直至搜索到第i個(gè)結(jié)點(diǎn)為止。
從單鏈表的頭指針L出發(fā)，從頭結(jié)點(diǎn)開(kāi)始順著指針域向后查找。在查找過(guò)程中，頭指針L保持不變，用指針p來(lái)遍歷單鏈表，初始指向頭結(jié)點(diǎn)，用整型變量j做記數(shù)器，j初值為0，當(dāng)指針p掃描下一個(gè)結(jié)點(diǎn)時(shí)，計(jì)數(shù)器j相應(yīng)地加1，如果跳出循環(huán)后j=i，指針p所指的結(jié)點(diǎn)就是要找的第i個(gè)結(jié)點(diǎn)；如果跳出循環(huán)后指針p的值為NULL或j≠i，則表示此單鏈表沒(méi)有第i個(gè)結(jié)點(diǎn)。
int j = 0;
// j為計(jì)數(shù)器
LinkList p = L; // p指向單鏈表L的頭結(jié)點(diǎn)
while ( p && j<i ) // 順指針向后查找，直到p指向第i個(gè)元素或p為空
{
p=p->next;
j++;
}
if ( !p || j>i ) // 第i個(gè)元素不存在，否則p指向第i個(gè)結(jié)點(diǎn)
return ;單鏈表的插入操作
要在帶頭結(jié)點(diǎn)的單鏈表L中第i個(gè)數(shù)據(jù)元素之前插入一個(gè)數(shù)據(jù)元素e，首先在單鏈表中找到第i-1個(gè)結(jié)點(diǎn)并由指針p指示，然后創(chuàng)建一個(gè)以e為值的新結(jié)點(diǎn)s，將其插入到p指向的結(jié)點(diǎn)之后。
int j=0;
LinkList p=L,s;
while( p && j<i-1 ) // p指向第i-1個(gè)結(jié)點(diǎn)
{
p=p->next;
j++;
}
if(!p || j>i-1) // i小于1或者大于表長(zhǎng)
return ;
s=(LinkList)malloc(sizeof(LNode)); // s指向新生成的結(jié)點(diǎn)
s->data=e; // 將e存入新結(jié)點(diǎn)的數(shù)據(jù)域
s->next=p->next; // ①新結(jié)點(diǎn)s的指針域指向第i個(gè)結(jié)點(diǎn)
p->next=s; // ②第i-1個(gè)結(jié)點(diǎn)的指針域指向新生成的結(jié)點(diǎn)s注意：插入操作的①和②執(zhí)行順序不能顛倒。
說(shuō)明：當(dāng)單鏈表中有n個(gè)結(jié)點(diǎn)時(shí)，則插入操作的插入位置有n+1個(gè)，即1≤i≤n+1。當(dāng)i=n+1時(shí)，則認(rèn)為是在單鏈表的尾部插入一個(gè)結(jié)點(diǎn)。 算法的時(shí)間主要耗費(fèi)在查找操作上，故時(shí)間復(fù)雜度為O(n)。
可以通過(guò)調(diào)用基本運(yùn)算算法來(lái)創(chuàng)建單鏈表，其過(guò)程是先初始化一個(gè)單鏈表，然后向其中一個(gè)一個(gè)地插入元素。
單鏈表的遍歷操作
由于單鏈表中每個(gè)結(jié)點(diǎn)的存儲(chǔ)地址是存放在其前趨結(jié)點(diǎn)的指針域中的，而第一個(gè)結(jié)點(diǎn)無(wú)前趨，頭指針L指向第一個(gè)結(jié)點(diǎn)，對(duì)于整個(gè)單鏈表的讀取必須從頭指針開(kāi)始，同時(shí)，由于單鏈表中最后一個(gè)結(jié)點(diǎn)的指針域?yàn)椤翱铡保∟ULL），沒(méi)有直接后繼元素，對(duì)于整個(gè)單鏈表的讀取必須在尾結(jié)點(diǎn)結(jié)束。函數(shù)定義如下：
LinkList p=L->next; //p指向單鏈表第一個(gè)結(jié)點(diǎn)
while( p )
{
vi( p->data );
p = p->next;
}在執(zhí)行遍歷函數(shù)時(shí)，用函數(shù)指針vi來(lái)實(shí)現(xiàn)對(duì)output()函數(shù)的調(diào)用。
編程要求
根據(jù)提示，在右側(cè)編輯器 Begin-End 區(qū)間補(bǔ)充代碼，完成單鏈表的初始化操作，遍歷操作及插入操作三個(gè)子函數(shù)的定義，具體要求如下：
void InitList(LinkList &L);//構(gòu)造一個(gè)空的單鏈表L
int ListInsert(LinkList &L,int i,ElemType e) ;//在單鏈表L中第i個(gè)位置之前插入新的數(shù)據(jù)元素
void ListTraverse(LinkList L,void(*vi)(ElemType));// 依次調(diào)用函數(shù)vi()輸出單鏈表L的每個(gè)數(shù)據(jù)元素
測(cè)試說(shuō)明
平臺(tái)會(huì)對(duì)你編寫(xiě)的代碼進(jìn)行測(cè)試：
測(cè)試輸入： 5 12 47 5 8 69 1 99 預(yù)期輸出： 插入成功，插入后單鏈表如下： 99 12 47 5 8 69
測(cè)試輸入： 5 12 47 5 8 69 7 99 預(yù)期輸出： 插入位置不合法，插入失?。?/p>
輸入說(shuō)明 第一行輸入單鏈表的數(shù)據(jù)元素的個(gè)數(shù)M； 第二行輸入單鏈表M個(gè)整數(shù)； 第三行輸入要插入元素的位置； 第四行輸入要插入的數(shù)據(jù)元素的值。
輸出說(shuō)明 第一行輸出插入是否成功的提示信息； 如果插入成功，第二行輸出插入元素后的單鏈表所有元素；如果插入失敗，則不輸出第二行。
開(kāi)始你的任務(wù)吧，祝你成功！文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-843653.html
實(shí)例代碼
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;
/* 定義ElemType為int類(lèi)型 */
typedef int ElemType;
void input(ElemType &s);
void output(ElemType s);
int equals(ElemType a,ElemType b);
/* 單鏈表類(lèi)型定義 */
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
void InitList(LinkList &L);
int ListInsert(LinkList &L,int i,int e) ;
void ListTraverse(LinkList L,void(*vi)(ElemType));
int main() //main() function
{
LinkList A;
ElemType e;
InitList(A);
int n,i;
// cout<<"Please input the list number ";
cin>>n;
for(i=1;i<=n;i++)
{
cin>>e;
ListInsert(A, i, e);
}
//cout<<"請(qǐng)輸入插入的位置："<<endl;
cin>>i;
//cout<<"請(qǐng)輸入插入的值："<<endl;
input(e);
if( ListInsert(A,i,e) )
{
cout<<"插入成功，插入后單鏈表如下："<<endl;
ListTraverse(A,output) ;
}
else
cout<<"插入位置不合法，插入失敗！"<<endl;
return 0;
}
/*****ElemType類(lèi)型元素的基本操作*****/
void input(ElemType &s)
{
cin>>s;
}
void output(ElemType s)
{
cout<<s<<" ";
}
int equals(ElemType a,ElemType b)
{
if(a==b)
return 1;
else
return 0;
}
/*****單鏈表的基本操作*****/
void InitList(LinkList &L)
{
// 操作結(jié)果：構(gòu)造一個(gè)空的單鏈表L
/********** Begin **********/
L=(LinkList)malloc(sizeof(LNode)); // 申請(qǐng)分配頭結(jié)點(diǎn)，并使L指向此頭結(jié)點(diǎn)
L->next=NULL;
/********** End **********/
}
int ListInsert(LinkList &L,int i,int e)
{
int j=0;
LinkList p=L,s;
while( p && j<i-1 )
{
p=p->next;
j++;
}
if(!p || j>i-1)
return 0;
s=(LinkList)malloc(sizeof(LNode));
s->data=e;
s->next=p->next;
p->next=s;
}
void ListTraverse(LinkList L,void(*vi)(ElemType))
{
LinkList p=L->next;
while( p )
{
vi( p->data );
p = p->next;
}
}第2關(guān)：?jiǎn)捂湵淼膭h除操作
任務(wù)描述
本關(guān)任務(wù)：編寫(xiě)單鏈表的刪除操作函數(shù)。
相關(guān)知識(shí)
要在帶頭結(jié)點(diǎn)的單鏈表L中刪除第i個(gè)結(jié)點(diǎn)，則同樣要先找到第i-1個(gè)結(jié)點(diǎn)，使p指向第i-1個(gè)結(jié)點(diǎn)，使q指向第i個(gè)結(jié)點(diǎn)，然后令第i-1個(gè)結(jié)點(diǎn)的指針域指向第i+1個(gè)結(jié)點(diǎn)，而后刪除q指向的第i個(gè)結(jié)點(diǎn)并釋放結(jié)點(diǎn)空間。
設(shè)單鏈表的長(zhǎng)度為n，則刪去第i個(gè)結(jié)點(diǎn)僅當(dāng)1≦i≦n時(shí)是合法的。
注意，當(dāng)i=n+1時(shí)，雖然被刪結(jié)點(diǎn)不存在，但其前趨結(jié)點(diǎn)卻存在，即p指向最后一個(gè)結(jié)點(diǎn)。因此只有在p->next != NULL時(shí)，才能進(jìn)行刪除結(jié)點(diǎn)的操作。
刪除算法的時(shí)間復(fù)雜度也是O(n)。
鏈表上實(shí)現(xiàn)的插入和刪除運(yùn)算，無(wú)須移動(dòng)結(jié)點(diǎn)，僅需修改指針。
編程要求
根據(jù)提示，在右側(cè)編輯器 Begin-End 區(qū)間補(bǔ)充代碼，完成單鏈表的刪除操作函數(shù)的定義，具體要求如下：
int ListDelete(LinkList L,int i,ElemType &e);// 在單鏈表L中刪除第i個(gè)元素，并由e返回其值
測(cè)試說(shuō)明
平臺(tái)會(huì)對(duì)你編寫(xiě)的代碼進(jìn)行測(cè)試：
測(cè)試輸入： 5 12 47 5 8 69 1 預(yù)期輸出： 刪除成功，刪除后單鏈表如下： 47 5 8 69 刪除元素的值：12
測(cè)試輸入： 5 12 47 5 8 69 6 預(yù)期輸出： 刪除位置不合法，刪除失??！
輸入說(shuō)明 第一行輸入單鏈表的長(zhǎng)度M； 第二行輸入單鏈表的M個(gè)整數(shù)； 第三行輸入要?jiǎng)h除元素的位置；
輸出說(shuō)明 第一行輸出刪除是否成功的提示信息； 如果刪除成功，第二行輸出刪除元素后的單鏈表；第三行輸出刪除的數(shù)據(jù)元素；如果刪除位置不合法，不輸出第二行和第三行。
開(kāi)始你的任務(wù)吧，祝你成功！
代碼示例
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;
/* 定義ElemType為int類(lèi)型 */
typedef int ElemType;
void input(ElemType &s);
void output(ElemType s);
int equals(ElemType a,ElemType b);
/* 單鏈表類(lèi)型定義 */
typedef struct LNnode
{
ElemType data;
struct LNnode *next;
}LNnode,*LinkList;
void InitList(LinkList &L);
int ListInsert(LinkList &L,int i,int e) ;
int ListDelete(LinkList L,int i,ElemType &e);
void ListTraverse(LinkList L,void(*vi)(ElemType));
int main() //main() function
{
LinkList A;
ElemType e;
InitList(A);
int n,i;
// cout<<"Please input the list number ";
cin>>n;
for(i=1;i<=n;i++)
{
cin>>e;
ListInsert(A, i, e);
}
//cout<<"請(qǐng)輸入刪除的位置："<<endl;
cin>>i;
if( ListDelete(A,i,e) )
{
cout<<"刪除成功，刪除后單鏈表如下："<<endl;
ListTraverse(A,output) ;
cout<<"刪除元素的值：";
output(e);
cout<<endl;
}
else
cout<<"刪除位置不合法，刪除失?。?<<endl;
}
/*****ElemType類(lèi)型元素的基本操作*****/
void input(ElemType &s)
{
cin>>s;
}
void output(ElemType s)
{
cout<<s<<" ";
}
int equals(ElemType a,ElemType b)
{
if(a==b)
return 1;
else
return 0;
}
/*****單鏈表的基本操作*****/
void InitList(LinkList &L)
{ // 構(gòu)造一個(gè)空的單鏈表L
L=(LinkList)malloc(sizeof(LNnode)); // 產(chǎn)生頭結(jié)點(diǎn)，并使L指向此頭結(jié)點(diǎn)
if(!L) // 存儲(chǔ)分配失敗
return ;
L->next=NULL; // 指針域?yàn)榭?
}
int ListInsert(LinkList &L,int i,ElemType e)
{ // 在帶頭結(jié)點(diǎn)的單鏈線(xiàn)性表L的第i個(gè)元素之前插入元素e
LinkList p,s;
p = L;
int j = 0;
while (p && j < i-1) { // 尋找第i-1個(gè)結(jié)點(diǎn)
p = p->next;
++j;
}
if (!p || j > i-1)
return 0; // i小于1或者大于表長(zhǎng)
s = (LinkList)malloc(sizeof(LNnode)); // 生成新結(jié)點(diǎn)
s->data = e; s->next = p->next; // 插入L中
p->next = s;
return 1;
}
void ListTraverse(LinkList L,void(*vi)(ElemType))
{ // 調(diào)用函數(shù)vi()依次輸出單鏈表L的每個(gè)數(shù)據(jù)元素
LinkList p=L->next;
while(p)
{
vi(p->data);
p=p->next;
}
printf("\n");
}
int ListDelete(LinkList L,int i,ElemType &e) // 算法2.10。不改變L
{
// 在帶頭結(jié)點(diǎn)的單鏈線(xiàn)性表L中，刪除第i個(gè)元素，并由e返回其值
/********** Begin **********/
int j=0;
LinkList p=L,r;
while(p->next && j<i-1)
{
p=p->next;
j++;
}
// i > 表長(zhǎng) || i <= 0
if(!p->next || j > i - 1) return 0;
r=p->next;
p->next=r->next;
e=r->data;
free(r);
return 1;
/********** End **********/
}第3關(guān)：?jiǎn)捂湵淼陌凑招蛱?hào)查找值操作
任務(wù)描述
本關(guān)任務(wù)：編寫(xiě)單鏈表按照序號(hào)i查找數(shù)據(jù)元素值操作函數(shù)。
相關(guān)知識(shí)
在單鏈表中，由于每個(gè)結(jié)點(diǎn)的存儲(chǔ)位置都放在其前一結(jié)點(diǎn)的next域中，所以即使知道被訪(fǎng)問(wèn)結(jié)點(diǎn)的序號(hào)i，也不能像順序表那樣直接按序號(hào)i隨機(jī)訪(fǎng)問(wèn)一維數(shù)組中相應(yīng)元素。
設(shè)帶頭結(jié)點(diǎn)的單鏈表的長(zhǎng)度為n，要查找表中第i個(gè)結(jié)點(diǎn)，則需要從單鏈表的頭指針L出發(fā)，從頭結(jié)點(diǎn)開(kāi)始順著指針域向后查找。
在查找過(guò)程中，頭指針L保持不變，用指針p來(lái)遍歷單鏈表，初值指向頭結(jié)點(diǎn)，用整型變量j做記數(shù)器，j初值為0，當(dāng)指針p掃描下一個(gè)結(jié)點(diǎn)時(shí)，計(jì)數(shù)器j相應(yīng)地加1。當(dāng)j=i時(shí)，指針p所指的結(jié)點(diǎn)就是要找的第i個(gè)結(jié)點(diǎn)；而當(dāng)指針p的值為NULL或j≠i時(shí)，則表示找不到第i個(gè)結(jié)點(diǎn)。
編程要求
根據(jù)提示，在右側(cè)編輯器 Begin-End 區(qū)間補(bǔ)充代碼，完成單鏈表按照序號(hào)i查找數(shù)據(jù)元素值操作函數(shù)的定義，具體要求如下：
int GetElem(LinkList L,int i,ElemType &e);//當(dāng)單鏈表L的的第i個(gè)元素存在時(shí)，其值賦給e并返回1，否則返回0
測(cè)試說(shuō)明
平臺(tái)會(huì)對(duì)你編寫(xiě)的代碼進(jìn)行測(cè)試：
測(cè)試輸入： 10 12 47 5 8 6 92 45 63 75 38 8
預(yù)期輸出： 查找成功！ 第8個(gè)元素的值： 63
測(cè)試輸入： 10 12 47 5 8 6 92 45 63 75 38 11
預(yù)期輸出： 查找失?。?/p>
輸入說(shuō)明 第一行輸入單鏈表的長(zhǎng)度M； 第二行輸入單鏈表的M個(gè)整數(shù)； 第三行輸入要查找的序號(hào)。
輸出說(shuō)明 第一行輸出按照序號(hào)查找是否成功的提示信息； 如果查找成功，輸出查找的數(shù)據(jù)元素的值；如果查找失敗，則不輸出。
開(kāi)始你的任務(wù)吧，祝你成功！
代碼示例
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;
/* 定義ElemType為int類(lèi)型 */
typedef int ElemType;
void input(ElemType &s);
void output(ElemType s);
int equals(ElemType a,ElemType b);
/* 單鏈表類(lèi)型定義 */
typedef struct LNnode
{
ElemType data;
struct LNnode *next;
}LNnode,*LinkList;
void InitList(LinkList &L);
int ListInsert(LinkList &L,int i,int e) ;
void ListTraverse(LinkList L,void(*vi)(ElemType));
int GetElem(LinkList L,int i,ElemType &e) ;
int main() //main() function
{
LinkList A;
ElemType e;
InitList(A);
int n,i;
// cout<<"Please input the list number ";
cin>>n;
for(i=1;i<=n;i++)
{
cin>>e;
ListInsert(A, i, e);
}
//cout<<"請(qǐng)輸入查找的序號(hào)："<<endl;
cin>>i;
if( GetElem(A,i,e) )
{
cout<<"查找成功！"<<endl;
cout<<"第"<<i<<"個(gè)元素的值："<<endl;
output(e);
cout<<endl;
}
else
cout<<"查找失敗！"<<endl;
}
/*****ElemType類(lèi)型元素的基本操作*****/
void input(ElemType &s)
{
cin>>s;
}
void output(ElemType s)
{
cout<<s<<" ";
}
int equals(ElemType a,ElemType b)
{
if(a==b)
return 1;
else
return 0;
}
/*****單鏈表的基本操作*****/
void InitList(LinkList &L)
{ // 操作結(jié)果：構(gòu)造一個(gè)空的單鏈表L
L=(LinkList)malloc(sizeof(LNnode)); // 產(chǎn)生頭結(jié)點(diǎn)，并使L指向此頭結(jié)點(diǎn)
if(!L) // 存儲(chǔ)分配失敗
return ;
L->next=NULL; // 指針域?yàn)榭?
}
int ListInsert(LinkList &L,int i,ElemType e)
{ // 在帶頭結(jié)點(diǎn)的單鏈線(xiàn)性表L的第i個(gè)元素之前插入元素e
LinkList p,s;
p = L;
int j = 0;
while (p && j < i-1) { // 尋找第i-1個(gè)結(jié)點(diǎn)
p = p->next;
++j;
}
if (!p || j > i-1)
return 0; // i小于1或者大于表長(zhǎng)
s = (LinkList)malloc(sizeof(LNnode)); // 生成新結(jié)點(diǎn)
s->data = e; s->next = p->next; // 插入L中
p->next = s;
return 1;
}
void ListTraverse(LinkList L,void(*vi)(ElemType))
{ // 初始條件：?jiǎn)捂湵鞮已存在。
//操作結(jié)果：依次對(duì)L的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)vi()
LinkList p=L->next;
while(p)
{
vi(p->data);
p=p->next;
}
printf("\n");
}
int GetElem(LinkList L,int i,ElemType &e)
{
// L為帶頭結(jié)點(diǎn)的單鏈表的頭指針。當(dāng)?shù)趇個(gè)元素存在時(shí)，其值賦給e并返回1，否則返回0
/********** Begin **********/
int j=1;
LinkList p=L->next;
while(p && j<i)
{
p=p->next;
j++;
}
if(!p || j>i)
return 0;
e=p->data;
return 1;
/********** End **********/
}第4關(guān)：?jiǎn)捂湵淼陌凑罩挡檎医Y(jié)點(diǎn)位序的操作
任務(wù)描述
本關(guān)任務(wù)：編寫(xiě)單鏈表的按照值查找結(jié)點(diǎn)位序的操作函數(shù)。
相關(guān)知識(shí)
在單鏈表中查找是否有結(jié)點(diǎn)值等于e的結(jié)點(diǎn)，若有的話(huà)，則返回首次找到的其值為e的結(jié)點(diǎn)的位序，否則返回0，表示單鏈表中沒(méi)有值等于e的結(jié)點(diǎn)。
查找過(guò)程從單鏈表的頭指針指向的頭結(jié)點(diǎn)出發(fā)，順著指針域逐個(gè)將結(jié)點(diǎn)的值和給定值e作比較。
在算法實(shí)現(xiàn)時(shí)，應(yīng)根據(jù)單鏈表數(shù)據(jù)元素的類(lèi)型ElemType編寫(xiě)判斷兩個(gè)數(shù)據(jù)元素是否相等的比較函數(shù)equals()，如果相等equals()返回1，否則返回0。
編程要求
根據(jù)提示，在右側(cè)編輯器 Begin-End 區(qū)間補(bǔ)充代碼，完成在單鏈表中查找值為e的結(jié)點(diǎn)位序函數(shù)的定義，具體要求如下：
int LocateElem(LinkList L,ElemType e,int (*equal)(ElemType,ElemType) );//在單鏈表L中查找，返回L中第1個(gè)與e滿(mǎn)足關(guān)系equal()的數(shù)據(jù)元素的位序否則為0。
測(cè)試說(shuō)明
平臺(tái)會(huì)對(duì)你編寫(xiě)的代碼進(jìn)行測(cè)試：
測(cè)試輸入： 10 12 47 5 8 6 92 45 63 75 38 92
預(yù)期輸出： 查找成功！ 92 是單鏈表第6個(gè)元素
測(cè)試輸入： 10 12 47 5 8 6 92 45 63 75 38 93
預(yù)期輸出： 查找失敗！
輸入說(shuō)明 第一行輸入單鏈表的長(zhǎng)度M； 第二行輸入單鏈表的M個(gè)整數(shù)； 第三行輸入要查找的數(shù)據(jù)元素的值。
輸出說(shuō)明 第一行輸出按照值查找是否成功的提示信息； 如果查找成功，第二行輸出查找元素的邏輯序號(hào)；如果查找失敗，則不輸出。
開(kāi)始你的任務(wù)吧，祝你成功！
代碼示例
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;
/* 定義ElemType為int類(lèi)型 */
typedef int ElemType;
void input(ElemType &s);
void output(ElemType s);
int equals(ElemType a,ElemType b);
/* 單鏈表類(lèi)型定義 */
typedef struct LNnode
{
ElemType data;
struct LNnode *next;
}LNnode,*LinkList;
void InitList(LinkList &L);
int ListInsert(LinkList &L,int i,int e) ;
void ListTraverse(LinkList L,void(*vi)(ElemType));
int LocateElem(LinkList L,ElemType e,int(*compare)(ElemType,ElemType));
int main() //main() function
{
LinkList A;
ElemType e;
InitList(A);
int n,i;
// cout<<"Please input the list number ";
cin>>n;
for(i=1;i<=n;i++)
{
cin>>e;
ListInsert(A, i, e);
}
//cout<<"請(qǐng)輸入查找的元素："<<endl;
cin>>e;
i=LocateElem(A,e,equals);
if( i )
{
cout<<"查找成功！"<<endl;
output(e);
cout<<"是單鏈表第"<<i<<"個(gè)元素"<<endl;
}
else
cout<<"查找失??！"<<endl;
}
/*****ElemType類(lèi)型元素的基本操作*****/
void input(ElemType &s)
{
cin>>s;
}
void output(ElemType s)
{
cout<<s<<" ";
}
int equals(ElemType a,ElemType b)
{
if(a==b)
return 1;
else
return 0;
}
/*****單鏈表的基本操作*****/
void InitList(LinkList &L)
{ // 操作結(jié)果：構(gòu)造一個(gè)空的單鏈表L
L=(LinkList)malloc(sizeof(LNnode)); // 產(chǎn)生頭結(jié)點(diǎn)，并使L指向此頭結(jié)點(diǎn)
if(!L) // 存儲(chǔ)分配失敗
return ;
L->next=NULL; // 指針域?yàn)榭?
}
int ListInsert(LinkList &L,int i,ElemType e)
{ // 在帶頭結(jié)點(diǎn)的單鏈線(xiàn)性表L的第i個(gè)元素之前插入元素e
LinkList p,s;
p = L;
int j = 0;
while (p && j < i-1) { // 尋找第i-1個(gè)結(jié)點(diǎn)
p = p->next;
++j;
}
if (!p || j > i-1)
return 0; // i小于1或者大于表長(zhǎng)
s = (LinkList)malloc(sizeof(LNnode)); // 生成新結(jié)點(diǎn)
s->data = e;
s->next = p->next; // 插入L中
p->next = s;
return 1;
}
void ListTraverse(LinkList L,void(*vi)(ElemType))
{ // 初始條件：?jiǎn)捂湵鞮已存在。
//操作結(jié)果：依次對(duì)L的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)vi()
LinkList p=L->next;
while(p)
{
vi(p->data);
p=p->next;
}
printf("\n");
}
int LocateElem(LinkList L,ElemType e,int (*equal)(ElemType,ElemType))
{
// 初始條件: 單鏈表L已存在，equal()是數(shù)據(jù)元素判定函數(shù)(滿(mǎn)足為1，否則為0)
// 操作結(jié)果: 返回L中第1個(gè)與e滿(mǎn)足關(guān)系equal()的數(shù)據(jù)元素的位序，若這樣的數(shù)據(jù)元素不存在，則返回值為0
/********** Begin **********/
int j=0;
LinkList p=L->next;
while(p)
{
j++;
if(equal(p->data,e))
return j;
p=p->next;
}
return 0;
/********** End **********/
}第5關(guān)：?jiǎn)捂湵淼哪嬷貌僮?/h3>
任務(wù)描述
本關(guān)任務(wù)：編寫(xiě)單鏈表的逆置操作函數(shù)。
相關(guān)知識(shí)
單鏈表的就地逆置，就是要求算法不引入額外的存儲(chǔ)空間。
先將單鏈表L拆分成兩部分，一部分是只有頭結(jié)點(diǎn)L的空表，另一部分是由p指向第一個(gè)數(shù)據(jù)結(jié)點(diǎn)的單鏈表。
然后遍歷p，將p所指結(jié)點(diǎn)逐一采用頭插法插入到L單鏈表中，由于頭插法的特點(diǎn)是建成的單鏈表結(jié)點(diǎn)次序與插入次序正好相反，從而達(dá)到結(jié)點(diǎn)逆置的目的。
單鏈表逆置與順序表逆置的算法思想不同，是因?yàn)閿?shù)據(jù)的存儲(chǔ)結(jié)構(gòu)不同產(chǎn)生的。
編程要求
根據(jù)提示，在右側(cè)編輯器 Begin-End 區(qū)間補(bǔ)充代碼，完成單鏈表的逆置化操作函數(shù)的定義，具體要求如下：
void reverse(LinkList &L); //鏈表的就地逆置
測(cè)試說(shuō)明
平臺(tái)會(huì)對(duì)你編寫(xiě)的代碼進(jìn)行測(cè)試：
測(cè)試輸入： 10 12 47 5 8 6 92 45 63 75 38
預(yù)期輸出： 逆置單鏈表： 38 75 63 45 92 6 8 5 47 12
輸入說(shuō)明 第一行輸入單鏈表的長(zhǎng)度M； 第二行輸入單鏈表的M個(gè)整數(shù)；
輸出說(shuō)明 第一行輸出提示信息； 第二行輸出逆置后的單鏈表。
開(kāi)始你的任務(wù)吧，祝你成功！
代碼示例
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;
/* 定義ElemType為int類(lèi)型 */
typedef int ElemType;
void input(ElemType &s);
void output(ElemType s);
int equals(ElemType a,ElemType b);
/* 單鏈表類(lèi)型定義 */
typedef struct LNnode
{
ElemType data;
struct LNnode *next;
}LNnode,*LinkList;
void InitList(LinkList &L);
int ListInsert(LinkList &L,int i,int e) ;
void ListTraverse(LinkList L,void(*vi)(ElemType));
void reverse (LinkList L);
int main() //main() function
{
LinkList A;
ElemType e;
InitList(A);
int n,i;
// cout<<"Please input the list number ";
cin>>n;
for(i=1;i<=n;i++)
{
cin>>e;
ListInsert(A, i, e);
}
cout<<"逆置單鏈表："<<endl;
reverse(A);
ListTraverse(A,output) ;
}
/*****ElemType類(lèi)型元素的基本操作*****/
void input(ElemType &s)
{
cin>>s;
}
void output(ElemType s)
{
cout<<s<<" ";
}
int equals(ElemType a,ElemType b)
{
if(a==b)
return 1;
else
return 0;
}
/*****單鏈表的基本操作*****/
void InitList(LinkList &L)
{ // 操作結(jié)果：構(gòu)造一個(gè)空的單鏈表L
L=(LinkList)malloc(sizeof(LNnode)); // 產(chǎn)生頭結(jié)點(diǎn)，并使L指向此頭結(jié)點(diǎn)
if(!L) // 存儲(chǔ)分配失敗
return ;
L->next=NULL; // 指針域?yàn)榭?
}
int ListInsert(LinkList &L,int i,ElemType e)
{ // 在帶頭結(jié)點(diǎn)的單鏈線(xiàn)性表L的第i個(gè)元素之前插入元素e
LinkList p,s;
p = L;
int j = 0;
while (p && j < i-1) { // 尋找第i-1個(gè)結(jié)點(diǎn)
p = p->next;
++j;
}
if (!p || j > i-1)
return 0; // i小于1或者大于表長(zhǎng)
s = (LinkList)malloc(sizeof(LNnode)); // 生成新結(jié)點(diǎn)
s->data = e; s->next = p->next; // 插入L中
p->next = s;
return 1;
}
void ListTraverse(LinkList L,void(*vi)(ElemType))
{ // 初始條件：?jiǎn)捂湵鞮已存在。
//操作結(jié)果：依次對(duì)L的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)vi()
LinkList p=L->next;
while(p)
{
vi(p->data);
p=p->next;
}
printf("\n");
}
void reverse (LinkList L)
{
//逆置L指針?biāo)赶虻膯捂湵? /********** Begin **********/
LinkList n,m;
n=L->next;
L->next=NULL;
while(n != NULL){
m=n;
n=n->next;
m->next=L->next;
L->next=m;
}
/********** End **********/
}第6關(guān)：兩個(gè)有序單鏈表的合并操作
任務(wù)描述
本關(guān)任務(wù)：分別輸入兩個(gè)有序的整數(shù)序列（分別包含M和N個(gè)數(shù)據(jù)），建立兩個(gè)有序的單鏈表，將這兩個(gè)有序單鏈表合并成為一個(gè)大的有序單鏈表。要求合并后的單鏈表仍使用原來(lái)兩個(gè)鏈表的存儲(chǔ)空間，不另外占用其他的存儲(chǔ)空間。
相關(guān)知識(shí)
已知單鏈線(xiàn)性表La和Lb的元素按值非遞減排列，編寫(xiě)函數(shù)將兩個(gè)有序單鏈表La和Lb歸并得到新的單鏈表Lc，Lc的元素也按值非遞減排列，歸并后La和Lb表不再存在。
算法思想：
用pa遍歷La的數(shù)據(jù)結(jié)點(diǎn)，pb遍歷Lb的數(shù)據(jù)結(jié)點(diǎn)。
將La頭結(jié)點(diǎn)用作新單鏈表Lc的頭結(jié)點(diǎn)，讓pc始終指向Lc的尾結(jié)點(diǎn)（初始時(shí)指向Lc）。
當(dāng)pa和pb均不為空時(shí)循環(huán)：比較pa與pb之data域值，將較小者鏈到pc之后。
如此重復(fù)直到La或Lb為空，再將余下的鏈表鏈接到pc之后。
編程要求
根據(jù)提示，在右側(cè)編輯器 Begin-End 區(qū)間補(bǔ)充代碼，完成兩個(gè)有序單鏈表的合并操作函數(shù)的定義，具體要求如下：
void MergeList(LinkList &La, LinkList &Lb, LinkList &Lc) ; // 歸并有序單鏈表La和Lb得到新的單鏈線(xiàn)性表Lc，Lc的元素也按值非遞減排列
測(cè)試說(shuō)明
平臺(tái)會(huì)對(duì)你編寫(xiě)的代碼進(jìn)行測(cè)試：
測(cè)試輸入： 5 10 15 20 25 30 6 12 22 32 42 52 62
輸入說(shuō)明 第一行輸入有序表A的長(zhǎng)度M； 第二行依次輸入有序表A的M個(gè)有序的整數(shù)； 第三行輸入有序表B的長(zhǎng)度N； 第四行依次輸入有序表B的N個(gè)有序的整數(shù)。
預(yù)期輸出： 合并兩個(gè)有序單鏈表： 10 12 15 20 22 25 30 32 42 52 62文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-843653.html
輸出說(shuō)明 第一行輸出提示信息； 第二行輸出合并后的有序單鏈表所包含的M+N個(gè)有序的整數(shù)。
開(kāi)始你的任務(wù)吧，祝你成功！
代碼示例
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;
/* 定義ElemType為int類(lèi)型 */
typedef int ElemType;
void input(ElemType &s);
void output(ElemType s);
int equals(ElemType a,ElemType b);
/* 單鏈表類(lèi)型定義 */
typedef struct LNnode
{
ElemType data;
struct LNnode *next;
}LNnode,*LinkList;
void InitList(LinkList &L);
int ListInsert(LinkList &L,int i,int e) ;
void ListTraverse(LinkList L,void(*vi)(ElemType));
void MergeList(LinkList &La, LinkList &Lb, LinkList &Lc);
int main() //main() function
{
LinkList A,B,C;
ElemType e;
InitList(A);
InitList(B);
int n,i;
// cout<<"Please input the list number ";
cin>>n;
for(i=1;i<=n;i++)
{
cin>>e;
ListInsert(A, i, e);
}
cin>>n;
for(i=1;i<=n;i++)
{
cin>>e;
ListInsert(B, i, e);
}
cout<<"合并兩個(gè)有序單鏈表："<<endl;
MergeList(A,B,C);
ListTraverse(C,output) ;
}
/*****ElemType類(lèi)型元素的基本操作*****/
void input(ElemType &s)
{
cin>>s;
}
void output(ElemType s)
{
cout<<s<<" ";
}
int equals(ElemType a,ElemType b)
{
if(a==b)
return 1;
else
return 0;
}
/*****單鏈表的基本操作*****/
void InitList(LinkList &L)
{ // 操作結(jié)果：構(gòu)造一個(gè)空的單鏈表L
L=(LinkList)malloc(sizeof(LNnode)); // 產(chǎn)生頭結(jié)點(diǎn)，并使L指向此頭結(jié)點(diǎn)
if(!L) // 存儲(chǔ)分配失敗
return ;
L->next=NULL; // 指針域?yàn)榭?
}
int ListInsert(LinkList &L,int i,ElemType e)
{ // 在帶頭結(jié)點(diǎn)的單鏈線(xiàn)性表L的第i個(gè)元素之前插入元素e
LinkList p,s;
p = L;
int j = 0;
while (p && j < i-1) { // 尋找第i-1個(gè)結(jié)點(diǎn)
p = p->next;
++j;
}
if (!p || j > i-1)
return 0; // i小于1或者大于表長(zhǎng)
s = (LinkList)malloc(sizeof(LNnode)); // 生成新結(jié)點(diǎn)
s->data = e; s->next = p->next; // 插入L中
p->next = s;
return 1;
}
void ListTraverse(LinkList L,void(*vi)(ElemType))
{ // 初始條件：?jiǎn)捂湵鞮已存在。
//操作結(jié)果：依次對(duì)L的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)vi()
LinkList p=L->next;
while(p)
{
vi(p->data);
p=p->next;
}
printf("\n");
}
void MergeList(LinkList &La, LinkList &Lb, LinkList &Lc)
{
// 已知單鏈線(xiàn)性表La和Lb的元素按值非遞減排列。
// 歸并La和Lb得到新的單鏈線(xiàn)性表Lc，Lc的元素也按值非遞減排列。
/********** Begin **********/
LinkList a,b,c;
a=La->next;
b=Lb->next;
Lc=La;
c=Lc;
while(a && b)
{
if(a->data <= b->data)
{
c->next=a;
c=a;
a=a->next;
}
else
{
c->next=b;
c=b;
b=b->next;
}
}
c->next=a?a:b;
free(Lb);
/********** End **********/
}
到了這里，關(guān)于【頭歌】單鏈表的基本操作的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
