C 和 C++ 支持 4 種基本數據類型（整型、浮點型、字符型、布爾型）和 3 種復合型數據類型（數組、指針、結構）。復合類型的數據對于數據結構至關重要，因為從某種程度上來說數據量的多少和數據結構的好壞決定了程序的復雜程度和程序結構的好壞。而數據結構基本可以抽象成數據對象之間的聯系，其中，結構適合描述數據對象，指針適合描述數據對象之間的聯系，數組適合描述同類型對象之間的特殊聯系（有序連續存放）。數據結構一般分為線性結構和非線性結構。
本實訓項目的主要目標是通過構建線性表來學習和掌握 C 和 C++ 中使用結構和指針構建復雜數據結構的方法。主要內容包括順序、逆序以及排序構建線性表，查找指定元素，刪除指定結點，求線性表的長度，棧，隊列和集合。

總共包括以下關卡。

第1關順序構建線性表

本關任務：按照數據輸入的順序構建一個線性表。即如果輸入的3個結點數據分別為1、2、3，則構建的線性表包含3個結點，且從前往后的結點數據分別為1、2、3。
為了完成本關卡任務，你需要掌握：

線性表的特性；
線性表的一般操作；
線性表的表示方法。
線性表（linear list）是一種數據結構，是由 n 個具有相同特性的數據元素構成的序列。

線性表中元素的個數 n 即為線性表的長度，當 n = 0 時稱為空表。線性表的相鄰元素之間存在著序偶關系。

如用（ a[0] ，…… ，a[i-1] ，a[i] ，a[i+1] ，…… ，a[n-1] ）表示一個線性表，則稱 a[i-1] 是 a[i] 的前驅，a[i+1] 是 a[i] 的后繼。

線性表的特性

線性表中必存在唯一的一個“第一元素”；

線性表中必存在唯一的一個“最后元素” ；

除最后一個元素之外，均有唯一的后繼；

除第一個元素之外，均有唯一的前驅。

線性表的一般操作

將線性表變為空表；

返回線性表的長度，即表中元素個數；

獲取線性表某位置的元素；

定位某個元素在線性表中的位置；

在線性表中插入一個元素；

刪除某個元素；

判斷線性表是否為空；

遍歷輸出線性表的所有元素；

線性表排序。
線性表可以用鏈表來實現。鏈表是通過指針鏈接在一起的一組數據項（結點）。

鏈表的每個結點都是同類型的結構，該結構中一般包含兩類信息：

數據域，存儲業務相關的數據（如財務系統的數據域為財務信息，車輛管理系統的業務信息為車輛信息）；

指針域，用于構建結點的鏈接關系。單鏈表的實現只需要一個指針。

由于數據域跟線性表的構建無關（靠指針域就夠了），所以本關所有程序的實現中線性表的數據域都只有一個整數。

單鏈表的形式如下：

如上圖所示，該單鏈表共包含了4個結點，4個結點的數據域分別是28、52、2、96。每個結點還包含一個指針，指向下一個結點。最后一個結點的指針域置為“NULL”，表示后面沒有結點了。

第一個結點的地址存放在一個指針變量 head 中（ head 指向鏈表第一個結點， head 本身不是一個結點）。訪問該單鏈表只需要知道 head 的值就可以了，因為通過 head 可以訪問到第一個結點，通過第一個結點的指針域可以訪問第二個結點 …… 直到訪問鏈表中所有的結點。
要實現上述鏈表，只需要定義如下結構：

// 定義結點結構
struct node
{int data;     // 數據域node * next;     // 指針域，指向下一個結點
};

如下程序可以構建上述圖中鏈表（其中：每個結點都是 node 類型的一個結構變量，head 則是node*類型的指針）：

node a, b, c, d, *head;
head = &a;     // 讓 head 指針指向結點 a
a.data = 28;     // 給 a 的數據域賦值
a.next = &b;     // 讓 a 的指針域指向結點 b
b.data = 52;  b.next = &c;     // 給 b 的數據域賦值，并讓 b 的指針域指向結點 c
c.data = 2;  c.next = &d;     // 給 c 的數據域賦值，并讓 c 的指針域指向結點 d
d.data = 96;  d.next = NULL;     // 給 d 的數據域賦值，并將 d 的指針域置為 NULL，表示后面沒有節點。

很顯然，這樣寫程序比較麻煩，而且在不知道有多少結點的情況下也根本無法處理。怎么可以解決這個問題呢？

C 和 C++ 的內存動態分配方法可以很好的解決這個問題。C++ 提供了兩種動態分配內存的方法：

C 語言提供的 malloc 和 free 函數，代碼如下：

node *t = (node *)malloc(sizeof(node));
t->data = 2;
free(t);

sizeof 是一個運算符，sizeof(node)用于計算并返回一個 node 類型變量所占內存空間的大小（字節數）；

malloc(int n)用于申請動態分配 n 個字節大小的數據空間，并返回該空間的首地址；

(node )是類型轉換運算符，malloc 函數返回的地址是void類型，轉換成node類型后賦值給指針變量 t（ t 的類型是node）。

所以上面第一條語句執行后，指針 t 指向一塊動態分配的內存空間，該空間大小為一個 node 類型變量的大小。

第二條語句通過指針 t 訪問該空間（當作 node 變量）的數據域 data，給它賦值為2。free 函數用于釋放 t 指向的動態分配空間（不需要該空間后再釋放）。
C++ 擴展的 new 和 delete 運算符，代碼如下：

node *t = new node;
t->data = 2;
delete t;

那么使用動態內存分配的方法實現上述的單鏈表的代碼如下：

node *head, *t, *p;
t = new node;     // 動態分配一個 node 結點的空間，并讓 t 指向它
head = t;     // 該結點是第一個結點，讓 head 指向它
t->data = 28;     // 給第一個結點的數據域賦值
p = new node;     // 動態分配第二個 node 結點的空間，并讓 p 指向它
t->next = p;     // 修改第一個結點的指針域為第二個結點的地址（第一個結點的指針域指向第二個結點）
p->data = 52;     // 給第二個結點的數據域賦值
t=p;     // 讓 t 指向最后一個結點
p = new node;     // 動態分配第三個 node 結點的空間，并讓 p 指向它（ p 不再指向第二個結點了）
t->next = p;     // 修改第二個結點的指針域為第三個結點的地址（第二個結點的指針域指向第三個結點）
p->data = 2;     // 給第三個結點的數據域賦值
t = p;     // 讓 t 指向最后一個結點
p = new node;     // 動態分配第四個 node 結點的空間，并讓 p 指向它（ p 不再指向第三個結點了）
t->next = p;     // 修改第三個結點的指針域為第四個結點的地址（第三個結點的指針域指向第四個結點）
p->data = 96;     // 給第四個結點的數據域賦值
p->next = NULL;     // 給第四個結點的指針域置為 NULL，表示后面沒有結點了

上述程序語句雖然好像變多了，程序也好像變復雜了，但細讀會發現這段程序可以很方便地改成循環，這樣處理后其實是使得程序更簡單了，并且適用于任意多個結點的情況。

改成循環后，單鏈表里面可能包含0個或多個結點，如果包含多個結點，則下面程序中的語句可以讓指針 t 指向鏈表的最后一個結點，具體代碼如下：

node *t = head; // t 指向第一個結點
// 如果 t->next 不為 NULL，即后面還有結點
while(t->next != NULL)
{
t = t->next; // 把 t 指向結點的指針域（下一個結點地址）賦值給 t，t 指向下一個結點
}
// 循環結束時，t->next 為 NULL，即 t 指向的結點后面沒有結點了。

完整代碼解析

#include "linearList.h"node *insertTail(node *h, node *t)
{// 請在此添加代碼，補全函數insertTail/********** Begin *********/if(h == NULL) // 空鏈表單獨處理{t->next = NULL; // 鏈表尾指針置為NULLreturn t; // 返回第一個結點的地址（即鏈表頭指針）}// 非空鏈表的情況node *p = h;// 讓p指向最后一個結點while(p->next){p = p->next;}p->next = t; // 讓最后一個結點的指針域指向結點tt->next = NULL; // 鏈表尾指針置為NULLreturn h;  // 返回第一個結點的地址（即鏈表頭指針）/********** End **********/
}

第2關逆序構建線性表

相關知識

在介紹如何將一個結點插入到一個鏈表頭部之前，我們先假設該鏈表頭指針為 head，則 head 中存放著鏈表當前頭結點的地址。

如果要將指針變量 t 指向的新結點插入到鏈表頭部，其實只需要將原來的頭結點的地址存入 t 指向結點的指針域（也就是讓 t 指向結點的指針域指向原來的頭結點），然后 t 指向的新結點就成了新的頭結點了。那么，如何將原來的頭結點的地址存入 t 指向結點的指針域？

t 指向結點的指針域可以用t->next訪問，原來頭結點的地址在 head 中，所以下面的語句可以實現這個功能：

t->next = head;

又由于新結點（ t 指向的結點）是新的頭結點，其地址必須存入頭指針 head 中，而 t 指向結點的地址存放在指針變量 t 中，所以下面的語句可以實現這個功能：
head = t;

完整代碼解析

#include "linearList.h"node * insertHead(node *h, node *t)
{// 請在此添加代碼，補全函數insertHead/********** Begin *********/t->next = h->next;h->next=t;return t;/********** End **********/
}

第3關排序構建線性表

本關任務：補全 insertSort 函數，實現將一個結點按結點數據 data 從小到大的順序插入到一個有序鏈表中。根據插入結點 data 的大小，插入點可能是鏈表頭、尾或者中間某個位置。
為了完成本關卡，你需要掌握：

如何找到插入點；
如何插入結點。
以上兩點也是實現本關任務的兩個關鍵步驟。
插入點的定位可以使用兩個指針（ p 和 q ），定位步驟如下圖所示：

上圖中鏈表有4個結點，則共有5個可能的插入點。

用兩個指針首先定位第一個插入點（ step1 ，p 為 NULL ，q 指向第一個結點），如果插入結點的 data 小于 q 指向結點的 data ，則就是該插入點（兩個指針指向的結點之間），否則兩個指針一起往后移動（ step2 ）；定位第二個插入點，判斷條件依然是插入結點的 data 是否小于 q 指向的結點的 data，是則就是該插入點，否則兩個指針往后平移（ step3 ）；定位第三個插入點，…… ，直到最后當 q 指針為“NULL”時，說明插入結點的 data 比鏈表中所有數據都大，則插入點應該是鏈尾（第五個插入點）。插入點的定位操作可以很容易地用循環實現。

定位好插入點后，當 p 為“NULL”時，插入點是鏈表頭部；當 q 為“NULL”時，插入點是鏈表尾部；否則，插入點為 p 和 q 指向的兩個結點之間。
上述定位好插入點后，接下來是插入結點。對于頭部插入和尾部插入的內容前兩關已做過介紹，本關只介紹中間插入的情況，即將 t 指向的結點插入到 p 和 q 指向的兩個結點之間。

這種情況只需要讓 p 指向結點的指針域指向 t 指向的結點， t 指向結點的指針域指向 q 指向的結點即可。具體參見下面代碼：

p->next = t;
t->next = q;

完整代碼解析

#include "linearList.h"node * insertSort(node *h, node *t)
{// 請在此添加代碼，補全函數insertSort/********** Begin *********/node *p = NULL, *q = h;  // 定位第一個插入點：鏈首// 查找插入點while(q && q->data < t->data){// 兩個指針并行后移p = q;q = q->next;}// 插入鏈首if(p == NULL){t->next = h;return t;}// 插入鏈尾if(q == NULL){p->next = t;t->next = NULL;}// 插入p、q之間t->next = q;p->next = t;return h;/********** End **********/
}

第4關查找元素

本關任務：補全 search 函數，實現在一個鏈表中搜索包含指定數據的結點。如果鏈表中有多個結點包含該數據，則返回第一個。

相關知識
遍歷列表元素
在線性表中查找特定元素是線性表的常用操作之一。由于鏈表結點都是動態內存分配得到的，在內存中不是連續存儲，沒法使用二分法之類的算法來實現信息檢索，但可以使用順序查找的方法。

順序查找需要遍歷整個鏈表，逐個檢查每個結點是否滿足條件。下面 printList 函數則可以遍歷鏈表元素。

// 函數printList：輸出鏈表，每個數據之間用一個空格隔開
// 參數：h-鏈表頭指針
void printList(node *h)
{cout << "List:";while(h){    // h 為真，即 h 指向的結點存在，則輸出該結點的數據cout << " " << h->data;     // 輸出結點數據h=h->next;     // 將該結點的指針域賦值給 h，h 就指向了下一個結點}cout << endl; // 輸出換行符
}

完整代碼解析

#include "linearList.h"node * search(node * h, int num)
{// 請在此添加代碼，補全函數search/********** Begin *********/while(h){// h為真，即h指向的結點存在if(h->data == num){return h;} h = h->next;  // 將該結點的指針域賦值給h，h就指向了下一個結點}return NULL; // 沒找到包含num的結點/********** End **********/
}

第5關刪除指定位置的結點

本關任務：補全 delAt 函數，實現根據指定位置刪除鏈表中對應的結點。
線性表的結點是有序號的，包含 n 個結點的線性表從鏈頭到鏈尾的結點序號分別為0、1、…… 、n?1。刪除線性表指定位置的操作也是常用的功能。

結點的刪除可以根據結點位置的不同分為三種情況：刪除鏈首結點、刪除鏈尾結點、刪除中間結點。

回答以下幾個問題，解決本關問題就不難了：

刪除鏈首結點后，原來序號為1的結點成為新的鏈首結點，鏈表頭指針也應該存儲該結點的地址，該結點的地址原來存放在哪？

刪除鏈尾結點后，原來序號為n?2的結點成為新的鏈尾結點，該結點的指針域也應該置為“NULL”，表示鏈表的結束。怎么訪問序號為n?2的結點的指針域？

刪除中間結點只需要將其前面結點的指針域修改為其后面結點的地址即可。例如刪除序號為i的結點，需要將序號為i?1的結點的指針域修改為序號為i+1的結點地址。怎么訪問序號為i?1的結點的指針域？序號為i+1的結點地址存放在哪？

完整代碼解析

#include "linearList.h"node * delAt(node * h, int i)
{// 請在此添加代碼，補全函數delAt/********** Begin *********/
if(h==NULL){return h;
}
if(i==0){node *temp=h;h=h->next;free(temp);return h;
}
node *current=h;
int count=0;
while(current->next!=NULL&&count<i-1){current=current->next;count++;
}
if(current->next==NULL){return h;
}
node *temp=current->next;
current->next=current->next->next;
if(temp->next==NULL){current->next=NULL;
}
free(temp);
return h;/********** End **********/
}

第6關刪除包含特定數據的結點

本關任務：補全 delHas 函數，實現刪除鏈表中包含特定數據的結點，如果有多個這樣的結點，只刪除第一個。

刪除鏈表的結點時，有時候不知道結點在哪，只知道結點數據的特征，如刪除成績低于60的學生結點、刪除學號為20160903的學生等。

提示程序是可以湊出來的，之前已經完成了一些函數，有些函數的功能這里可以借鑒。例如 delAt 可以刪除某個序號的結點，本關可以先搜索鏈表，查找包含數據 n 的第一個結點的序號，找到了則調用 delAt 函數刪除它。

也可以用另外一種方法，結合 search 函數和 delAt 函數的部分功能，使用指針對要刪除的結點進行定位，定位后根據結點位置（指針信息可以反映出要刪除的結點在鏈首、鏈中或者鏈尾），然后直接刪除。

完整代碼解析

#include "linearList.h"node * delHas(node * h, int n)
{// 請在此添加代碼，補全函數delHas/********** Begin *********/
node *p=NULL;
node *c=h;
while(c!=NULL){if(c->data==n){if(p==NULL){h=c->next;}else{p->next=c->next;}free(c);break;}p=c;c=c->next;
}
return h;/********** End **********/
}

第7關線性表長度

本關任務：編寫 listLength 函數來求線性表的長度。

溫馨提示：建議在開始你的任務前，先仔細閱讀右側“文件目錄”下提供的 step7/linearList.h 和 step7/test.cpp 兩個文件，對整個程序有一個全面的了解，再動手完成任務！

完整代碼解析

#include "linearList.h"int listLength(node * h)
{// 請在此添加代碼，補全函數listLength/********** Begin *********/
int c=0;
node *p=h;
while(p!=NULL){c++;p=p->next;
}
return c;/********** End **********/
}

第8關線性表應用一：棧

本關任務：用前面已經實現的線性表來實現一個整數棧（棧里的數據是整數）。共需要補全三個函數（也是棧的基本功能）：判斷棧空的 empty 函數、壓棧的 push 函數和彈棧的 pop 函數。

棧（ stack ）又名堆棧，是一種功能受限的線性表，具有先進后出的特性。

其限制為僅允許在線性表的一端進行插入和刪除運算。這一端被稱為棧頂，相對地，把另一端稱為棧底。

向一個棧插入新元素又稱作進棧、入棧或壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；

從一個棧刪除元素又稱作出棧、彈棧或退棧，它是把棧頂元素刪除掉，使其下面的元素成為新的棧頂元素。

接下來首先聲明結構類型：

// 定義結點結構
struct node
{int data;     // 數據域node * next;     // 指針域，指向下一個結點
};
typedef node * intStack;  // 定義類型別名，intStack 即相當于 node*

定義 intStack 是為了使程序的可讀性更好一些。因為本關是用線性表實現棧，而訪問一個線性表其實只需要一個鏈表頭指針就可以了，intStack 實際上就是node*類型，所以后面可以這樣聲明棧 sk ：

intStack sk = NULL;     // 聲明棧 sk，并初始化為空棧（空線性表）

實際上 sk 就是一個node*類型的指針，用它可以訪問一個線性表，也就可以看成一個棧了。

完整代碼解析

#include "mstack.h"
// 函數empty：判斷棧sk是否為空
// 參數：sk-棧
// 返回值：true-sk為空，false-sk不為空
bool empty(intStack sk)
{// 請在此添加代碼，補全函數empty/********** Begin *********/return sk == NULL;/********** End **********/
}
// 函數pop：彈棧
// 參數：sk-棧，傳引用，彈棧可能會改變sk的值
// 返回值：彈棧的彈出的整數，如果棧空，返回-1
int pop(intStack &sk)
{// 請在此添加代碼，補全函數pop/********** Begin *********/if (sk == NULL) {return -1;}int value = sk->data;intStack temp = sk;sk = sk->next;delete temp;return value;/********** End **********/
}
// 函數push：壓棧，將整數n壓入棧sk中
// 參數：sk-棧，傳引用，壓棧會改變sk的值，n-要壓棧的整數
// 返回值：無，采用鏈表實現棧，只要還有內存，壓棧都會成功
void push(intStack &sk, int n)
{// 請在此添加代碼，補全函數push/********** Begin *********/intStack newNode = new node;newNode->data = n;newNode->next = sk;sk = newNode;/********** End **********/
}

第9關線性表應用二：隊列

本關任務：用前面已經實現的線性表來實現一個整數隊列（隊列里的數據是整數）。共需要補全三個函數（也是隊列的基本功能）：判斷隊列空的 queueEmpty 函數、入列的 enQueue 函數和出列的 deQueue 函數。
隊列是一種功能受限的線性表，具有先進先出的特性。隊列僅允許從一頭出列（這一頭稱為隊列頭），從另外一頭入列（隊列尾）。

入列操作是將結點插入到隊列尾（該結點稱為新的隊列尾）；

出列操作是從隊列頭刪除頭結點，并獲取刪除節點的數據（原頭結點的后繼結點為新的頭結點）。

接下來首先聲明結構類型：

// 定義結點結構
struct node
{int data;     // 數據域node * next;     // 指針域，指向下一個結點
};
typedef node * intQueue;  // 定義類型別名，intQueue 即相當于 node*

定義 intQueue 是為了使程序的可讀性更好一些。因為本關是用線性表實現隊列，而訪問一個線性表其實只需要一個鏈表頭指針就可以了，intQueue 實際上就是node*類型，所以后面可以這樣聲明隊列 iq ：

intQueue iq = NULL;  // 聲明隊列 iq，并初始化為空隊列（空線性表）

實際上 iq 就是一個node*類型的指針，用它可以訪問一個線性表，也就可以看成一個隊列。

完整代碼解析

#include "mqueue.h"// 函數queueEmpty：判斷隊列iq是否為空
// 參數：iq-整數隊列
// 返回值：true-隊列iq為空，false-iq不為空
bool queueEmpty(intQueue iq)
{// 請在此添加代碼，補全函數queueEmpty/********** Begin *********/ return iq == NULL;/********** End **********/
}
// 函數enQueue：將整數num入列到iq
// 參數：iq-整數隊列，傳引用，入列有可能改變隊列頭指針，num-入列的整數
// 返回值：無，只要還有內存，入列總會成功
void enQueue(intQueue &iq, int num)
{// 請在此添加代碼，補全函數enQueue/********** Begin *********/intQueue newNode = new node;newNode->data = num;newNode->next = NULL;if (iq == NULL) {iq = newNode;} else {intQueue tail = iq;while (tail->next != NULL) {tail = tail->next;}tail->next = newNode;}/********** End **********/
}
// 函數deQueue：出列
// 參數：iq-整數隊列，傳引用，出列有可能改變隊列頭指針
// 返回值：出列結點的數據，如果隊列為空，返回-1
int deQueue(intQueue &iq)
{// 請在此添加代碼，補全函數deQueue/********** Begin *********/if (iq == NULL) {return -1;}int value = iq->data;intQueue temp = iq;iq = iq->next;delete temp;return value;/********** End **********/
}

第10關線性表應用三：集合

本關任務：使用線性表實現集合的表示及操作。具體需要補全三個函數：計算集合并集的 unionSet 函數、計算集合交集的 intersection 函數和向集合中添加元素的 addElement 函數。

集合是數學中一個基本概念，它是集合論的研究對象。樸素集合論中，集合的定義就是“一堆東西”，集合里的“東西”，稱為元素。

下面介紹幾個集合的知識點：

集合中的元素是無序的，對于任意的集合S1和S2，S1=S2當且僅當對于任意的對象a，都有若a∈S1，則a∈S2；若a∈S2，則a∈S1；

集合中的元素互不相同，空集合是沒有任何元素的集合；

集合的并集定義為：A∪B=x∣x∈A或x∈B。例如，A={1，3，5}，B={1，2，5} ，則A∪B= {1，2，3，5} ；

集合的交集定義為：A∩B=x∣x∈A且x∈B。例如， A= {1，3，5}，B={1，2，5} ，則A∩B= {1，5} 。

接下來首先聲明結構類型：

// 定義結點結構
struct node
{int data;     // 數據域node * next;     // 指針域，指向下一個結點
};
typedef node * intSet;     // 定義類型別名，intSet 即相當于 node*

上述結構類型的聲明中定義 intSet 是為了使程序的可讀性更好一些。因為本關是用線性表實現集合，而訪問一個線性表其實只需要一個鏈表頭指針就可以了， intSet 實際上就是node*類型，所以后面可以這樣聲明集合 a ：

intSet a=NULL;     // 聲明集合 a，并初始化為空集合（空線性表）

在右側編輯器中的Begin-End之間補充代碼，完成 unionSet、intersection 、addElement 三個函數，以實現集合的三個功能。具體要求如下：

函數 unionSet 計算并返回集合 a 和 b 的并集。參數 a 和 b 是兩個集合，返回值為 a 和 b 的并集。

函數 intersection 計算并返回集合 a 和 b 的交集。參數 a 和 b 是兩個集合，返回值為 a 和 b 的交集。

函數 addElement 將元素 num 加入到集合 is 中，如果 is 中已經存在 num 了，則不需要加入，不存在則加入。參數 is 是一個集合，num 是要加入到 is 中的元素。

溫馨提示：可以使用線性表已有的功能來實現這些函數。具體提供的函數請從“文件目錄”中查看step10/LinearList.cpp、step10/LinearList.h、step10/mset.h和step10/test.cpp。

完整代碼解析

#include "mset.h"// 函數unionSet：求集合a和b的并集
// 參數：a-集合，b-集合
// 返回值：集合（集合a和b的并集）
intSet unionSet(intSet a, intSet b)
{// 請在此添加代碼，補全函數unionSet/********** Begin *********/intSet result = NULL;intSet current = a;// 將集合a中的元素添加到結果集合中while (current != NULL) {addElement(result, current->data);current = current->next;}current = b;// 將集合b中的元素添加到結果集合中while (current != NULL) {addElement(result, current->data);current = current->next;}return result;/********** End **********/
}
// 函數intersection：求集合a和b的交集
// 參數：a-集合，b-集合
// 返回值：集合（集合a和b的交集）
intSet intersection(intSet a, intSet b)
{// 請在此添加代碼，補全函數intersection/********** Begin *********/
intSet result = NULL;intSet currentA = a;// 遍歷集合a，檢查元素是否也在集合b中while (currentA != NULL) {intSet currentB = b;bool found = false;while (currentB != NULL) {if (currentA->data == currentB->data) {found = true;break;}currentB = currentB->next;}if (found) {addElement(result, currentA->data);}currentA = currentA->next;}return result;/********** End **********/
}
// 函數addElement：在集合is中增加元素num
// 參數：is-集合，num-要增加的元素
// 返回值：無
void addElement(intSet &is, int num)
{// 請在此添加代碼，補全函數addElement/********** Begin *********/intSet current = is;bool exists = false;// 檢查元素是否已存在于集合中while (current != NULL) {if (current->data == num) {exists = true;break;}current = current->next;}// 如果元素不存在，則添加到集合中if (!exists) {intSet newNode = new node;newNode->data = num;newNode->next = is;is = newNode;}/********** End **********/
}