1. 設計思路

本項目的實質是完成對考生信息的建立、查找、插入、修改、刪除等功能，可以首先定義項目的數據結構，然后將每個功能寫成一個函數來完成對數據的操作，最后完成主函數以驗證各個函數功能并得出運行結果。

2. 數據結構

本項目的數據是一組考生信息，每條考生信息由準考證號、姓名、性別、年齡、報考類別等信息組成，這組考生信息具有相同特性，屬于同一數據對象，相鄰數據元素之間存在序偶關系。由此可以看出，這些數據也具有線性表中數據元素的性質，所以該系統的數據可以采用線性表來存儲。
?

從上一節的例子中可見，線性表的順序存儲結構的特點是邏輯關系相鄰的兩個元素在物理位置上也相鄰，因此可以隨機存儲表中任一元素，它的存儲位置可用一個簡單、直觀的公式來表示。然而，從另一個方面來看，這個特點也鑄成了這種存儲結構的弱點：在做插入或刪除操作時，需要移動大量元素。
?

為克服這一缺點，我們引入另一種存儲形式――鏈式存儲。鏈式存儲是線性表的另一種表示方法，由于它不要求邏輯上相鄰的元素在物理位置上也相鄰，因此它沒有順序存儲結構的弱點，但同時也失去了順序表可隨機存取的特點。
?

鏈式存儲的優點是插入或刪除元素時很方便，使用靈活。缺點是存儲密度小，存儲空間利用率低。事實上，鏈表插入、刪除運算的快捷是以空間代價來換取時間。
?

順序表適宜于做查找這樣的靜態操作；鏈表宜于做插入、刪除這樣的動態操作。

• 若線性表的長度變化不大，且其主要操作是查找，則采用順序表；
• 若線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表；

本項目主要進行插入、刪除、修改等操作，所以采用鏈式存儲結構比較適合。用結構體類型定義每個考生信息，故該單鏈表中的每個結點的結構可描述為：

// 單鏈表中單個結點的完整數據結構定義
typedef struct LNodeTag
{Student stu;    // 值域LNodeTag *next;    // 指針域
}LNode;

假設 L 為 LNode* 型變量，則 L為單鏈表的頭指針，它指向表中的第一個結點。若 L 為空 L=NULL，則表示的線性表為空表，其長度 n 為 0。

有時我們在單鏈表的第一個結點之前設置一個結點，稱之為頭結點，頭結點的數據域可以不存儲任何信息，也可以存儲線性表的長度等類附加信息，頭結點的指針域存儲指向第一個結點的指針（即第一個元素結點的存儲位置），如圖 2.7a 所示，此時單鏈表的頭指針指向頭結點。
?
若線性表為空表，則頭結點的指針域為空，如圖 2.7b 所示。

根據這里的分析不難發現，鏈表在新增、刪除數據都比較容易，可以在 O(1) 的時間復雜度內完成。但對于查找，不管是按照位置的查找還是按照數值條件的查找，都需要對全部數據進行遍歷。這顯然就是 O(n) 的時間復雜度。

雖然鏈表在新增和刪除數據上有優勢，但仔細思考就會發現，這個優勢并不實用。這主要是因為，在新增數據時，通常會伴隨一個查找的動作。例如，在第五個結點后，新增一個新的數據結點，那么執行的操作就包含兩個步驟：

• 查找第五個結點；

• 再新增一個數據結點;

整體的復雜度就是 O(n) + O(1)

2.1 創建空鏈表

使用下面代碼創建一個僅有頭結點的單鏈表（空單鏈表）

LinkList::LinkList()
{head = new LNode;   // 產生頭結點,并使 head 頭指針 指向此頭結點head->next = NULL;  // 指針域為空std::cout << "constructor done" << std::endl;
}

創建結果見下圖

2.2 銷毀鏈表

銷毀單鏈表

LinkList::~LinkList()
{LNode *q;while (head){q = head->next;delete head;head = q;}std::cout << "destructor done" << std::endl;
}

銷毀結果見下圖：

2.3 插入元素

要在第 i 個位置插入一個新的結點, 則需要先找到第 i-1 個結點,如下圖

2.4 刪除結點

同樣要在第 i 個位置刪除一個結點, 則需要先找到第 i-1 個結點,如下圖

3. 程序清單

project.h

#include <iostream>
#include <string>// 單鏈表中結點的值域數據結構定義
typedef struct StudentTag
{std::string id;std::string name;std::string gender;int age;// 結構體初始化StudentTag(std::string i="", std::string n="", std::string g="", int a=0) {id = i;name = n;gender = g;age = a;}
}Student;// 單鏈表中單個結點的完整數據結構定義
typedef struct LNode
{Student stu;    // 值域LNode *next;    // 指針域
}LNode;class LinkList
{
public:LinkList();~LinkList();void init_list();void clear_list();bool is_empty();int print_list();int get_list_length();int get_element(int i, Student &data);  //  返回單鏈表中指定序號的結點值bool search_element(Student data);       //  從單鏈表中查找元素int insert_element(int i, const Student data);int delete_element(int i, Student &data);int update_element(const Student data);private:LNode *head;
};

project.cpp

#include "project.h"LinkList::LinkList()
{head = new LNode;   // 產生頭結點,并使 head 指向此頭結點head->next = NULL;  // 指針域為空std::cout << "constructor done" << std::endl;
}LinkList::~LinkList()
{LNode *q;while (head){q = head->next;delete head;head = q;}std::cout << "destructor done" << std::endl;
}void LinkList::clear_list()
{std::cout << "clear_list start" << std::endl;LNode *q;LNode *p = head->next;  // p 指向第一個結點while (p)   // 循環到表尾{q = p->next;delete p;p = q;}head->next = NULL;  // 頭結點指針域為空std::cout << "clear_list done" << std::endl;
}bool LinkList::is_empty()
{if(head->next){return false;}else{return true;}// return head->next ? false : true;
}int LinkList::print_list()
{LNode *p = head->next;int length = get_list_length();if(length == 0){std::cout << "list length is 0" << std::endl; return 0;}while (p){std::cout   << "id:" << p->stu.id << " "<< "name:" << p->stu.name << " "<< "age:" << p->stu.age << " "<< "gender:" << p->stu.gender << " "<< std::endl;p = p->next;}return 0;
}int LinkList::get_list_length()
{int length = 0;LNode *p = head->next;while (p){   length += 1;p = p->next;}return length;
}int LinkList::get_element(int i, Student &data)
{int k = 1;LNode *p = head->next;while (p){   if(k++ == i){data = p->stu;return 0;}p = p->next;}return 1;// 如果函數返回的是獲取到的結構體值，則使用 return head->data;
}bool LinkList::search_element(Student data)
{LNode *p = head->next;while (p){   // 只要學生的學號相等就認為這兩個結構體相等if(data.id == p->stu.id){return true;}p = p->next;}return false;
}int LinkList::insert_element(int i, Student data)
{int k = 1;// 找到要插入的第 i 個元素的前一個位置，并讓 p 指向該結點LNode *p = head;while(p->next && k < i)   {p = p->next;k++;}// 新建一個結點用于存儲要輸入的數據 dataLNode *q = new LNode;q->stu = data;q->next = NULL;// 將新數據插入到鏈表中 q->next = p->next;p->next = q;return 0;
}int LinkList::delete_element(int i, Student &data)
{int k = 1;int length = get_list_length();if(is_empty() || i < 1 || i > length){std::cout << "要刪除的元素位置不合理" << std::endl;return -1;}// 找到要刪除的第 i 個元素的前一個位置，并讓 p 指向該結點LNode *p = head;while(p->next && k < i)   {p = p->next;k++;}if(!(p->next) || k > i){return -1;}// 將要刪除的數據賦值給 data/*data = p->next->stu;// 刪除對應的結點delete p->next;p->next = p->next->next;return 0;*/LNode *q;q = p->next;data = q->stu;// 刪除對應的結點delete p->next;p->next = q->next;return 0;
}int LinkList::update_element(Student data)
{// 找到要更新的元素,假設要修改數據的 data.id 與鏈表中的 p->stu.id 相等LNode *p = head;while(p->next)   {p = p->next;if(p->stu.id == data.id){p->stu.name = data.name;p->stu.age = data.age;p->stu.gender = data.gender;}}return 0;
}

main.cpp

#include "project.cpp"int main()
{LinkList L;Student sa("001", "A", "male", 18);L.insert_element(1, sa);Student sb("002", "B", "male", 19);L.insert_element(2, sb);Student sc("003", "C", "male", 20);L.insert_element(3, sc);std::cout << "插入元素之后的結果" << std::endl;L.print_list();// L.clear_list();// L.print_list();bool is_empty = L.is_empty();std::cout << "is_empty: " << is_empty << std::endl;     std::cout << "length: " << L.get_list_length() << std::endl;  Student s;L.get_element(3, s);std::cout << "第 3 個元素為 "  << "id:" << s.id << " "<< "name:" << s.name << " "<< "age:" << s.age << " "<< "gender:" << s.gender << " "<< std::endl;Student sd("004", "D", "female", 21);L.insert_element(4, sd);std::cout << "插入元素之后的結果" << std::endl;L.print_list();Student se;L.delete_element(4, se);std::cout << "要刪除的元素為 "  << "id:" << se.id << " "<< "name:" << se.name << " "<< "age:" << se.age << " "<< "gender:" << se.gender << " "<< std::endl;std::cout << "刪除元素之后的結果" << std::endl;L.print_list();Student sf("001", "A", "male", 20);std::cout << "要更改的元素為 "  << "id:" << sf.id << " "<< "name:" << sf.name << " "<< "age:" << sf.age << " "<< "gender:" << sf.gender << " "<< std::endl;L.update_element(sf);std::cout << "更新元素之后的結果" << std::endl;L.print_list();
}

總結

以上是生活随笔為你收集整理的数据结构（05）— 线性单链表实战的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。