第二十七課：數(shù)據(jù)結(jié)構(gòu)入門 - 數(shù)組與鏈表
學(xué)習(xí)目標(biāo)：
- 理解數(shù)組的基本概念和操作。
- 掌握鏈表的基本結(jié)構(gòu)與特點。
- 學(xué)會在C++中定義和操作數(shù)組和鏈表。
- 了解數(shù)組和鏈表的基本使用場景。
學(xué)習(xí)內(nèi)容：
-
數(shù)組（Array）
- 概念：數(shù)組是一種線性數(shù)據(jù)結(jié)構(gòu)，用一段連續(xù)的內(nèi)存空間來存儲一系列相同類型的元素。
- 參數(shù)用法：
- 索引（Index）：數(shù)組中每個元素的位置，通常從0開始。
- 長度（Length）：數(shù)組中元素的數(shù)量，確定數(shù)組大小的屬性。
- 代碼示例：
#include <iostream> using namespace std; int main() { int arr[5] = {1, 2, 3, 4, 5}; // 聲明并初始化一個整型數(shù)組 // 訪問并打印數(shù)組元素 for (int i = 0; i < 5; i++) { cout << "Element at index " << i << ": " << arr[i] << endl; } return 0; } - 預(yù)計輸出效果：
Element at index 0: 1 Element at index 1: 2 Element at index 2: 3 Element at index 3: 4 Element at index 4: 5 - 使用場景：數(shù)組通常用于存儲固定數(shù)目的元素，適合快速地通過索引查詢元素。
-
鏈表（LinkedList）
- 概念：鏈表是一種線性結(jié)構(gòu)，由一系列不必在內(nèi)存中連續(xù)存儲的元素組成，每個元素均包含數(shù)據(jù)部分和指向下一個元素的指針。
- 參數(shù)用法：
- 節(jié)點（Node）：鏈表中的元素，包含數(shù)據(jù)和指向下一個節(jié)點的指針。
- 頭指針（Head）：指向鏈表的第一個節(jié)點的指針。
- 代碼示例：
#include <iostream> using namespace std; // 定義鏈表節(jié)點結(jié)構(gòu)體 struct Node { int data; Node* next; }; // 打印鏈表函數(shù) void printList(Node* n) { while (n != nullptr) { cout << n->data << " "; n = n->next; } cout << endl; } int main() { Node* head = new Node(); Node* second = new Node(); Node* third = new Node(); head->data = 1; // 賦值 head->next = second; // 指向下一個節(jié)點 second->data = 2; second->next = third; third->data = 3; third->next = nullptr; printList(head); // 打印鏈表 return 0; } - 預(yù)計輸出效果：
1 2 3 - 使用場景：鏈表適合于元素數(shù)量變動較大的情況，便于插入和刪除元素，但訪問特定位置的元素較慢。
鏈表遍歷與插入
-
鏈表的遍歷
- 鏈表的遍歷意味著按照鏈表的指針從頭到尾訪問每個節(jié)點。
- 遍歷通常使用循環(huán)或遞歸來完成。
-
鏈表中的數(shù)據(jù)插入
- 鏈表中的數(shù)據(jù)可以在頭部、尾部或任意給定節(jié)點后插入。
- 插入操作需要更改節(jié)點的指針以維護鏈表的結(jié)構(gòu)。
鏈表的節(jié)點定義示例（C++）：
class ListNode {
public:
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr)};
遍歷鏈表示例（C++）：
void traverseList(ListNode* head) {
ListNode* temp = head;
while(temp != nullptr) {
cout << temp->val << " ";
temp = temp->next;
}
cout << endl;
}
鏈表中數(shù)據(jù)插入示例（C++）：
- 在頭部插入：
ListNode* insertAtHead(ListNode* head, int x) {
ListNode* newNode = new ListNode(x);
newNode->next = head;
head = newNode;
return head;
}
- 在尾部插入：
ListNode* insertAtTail(ListNode* head, int x) {
ListNode* newNode = new ListNode(x);
if(head == nullptr) {
return newNode;
}
ListNode* temp = head;
while(temp->next != nullptr) {
temp = temp->next;
}
temp->next = newNode;
return head;
}
- 在給定節(jié)點后插入：
void insertAfterNode(ListNode* prevNode, int x) {
if(prevNode == nullptr) {
cout << "The given previous node cannot be null." << endl;
return;
}
ListNode* newNode = new ListNode(x);
newNode->next = prevNode->next;
prevNode->next = newNode;
}
練習(xí)題：文章來源：http://www.zghlxwxcb.cn/news/detail-818819.html
- 實現(xiàn)一個單鏈表，并定義一個函數(shù)遍歷此鏈表。
- 寫出一個函數(shù)，在單鏈表的頭部插入一個節(jié)點。
- 寫出一個函數(shù)，在單鏈表的尾部插入一個節(jié)點。
- 寫出一個函數(shù)，在單鏈表的某個節(jié)點后插入一個新節(jié)點。
#include <iostream>
class ListNode {
public:
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr)};
class SinglyLinkedList {
public:
ListNode *head;
SinglyLinkedList() : head(nullptr) // 遍歷鏈表
void traverseList() {
ListNode *temp = head;
while (temp != nullptr) {
std::cout << temp->val << " ";
temp = temp->next;
}
std::cout << std::endl;
}
// 在頭部插入節(jié)點
void insertAtHead(int x) {
ListNode *newNode = new ListNode(x);
newNode->next = head;
head = newNode;
}
// 在尾部插入節(jié)點
void insertAtTail(int x) {
ListNode *newNode = new ListNode(x);
if (head == nullptr) {
head = newNode;
} else {
ListNode *temp = head;
while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = newNode;
}
}
// 在某個節(jié)點后插入新節(jié)點
void insertAfterNode(ListNode *prevNode, int x) {
if (prevNode == nullptr) {
std::cout << "The given previous node cannot be null." << std::endl;
return;
}
ListNode *newNode = new ListNode(x);
newNode->next = prevNode->next;
prevNode->next = newNode;
}
};
int main() {
SinglyLinkedList list;
// 在鏈表頭部插入節(jié)點
list.insertAtHead(5);
list.insertAtHead(3);
list.insertAtHead(1);
// 在鏈表尾部插入節(jié)點
list.insertAtTail(7);
list.insertAtTail(9);
// 遍歷鏈表
list.traverseList();
// 在鏈表中第一個節(jié)點后插入新節(jié)點
list.insertAfterNode(list.head, 2);
// 再次遍歷鏈表
list.traverseList();
return 0;
}
目錄
第二十八課 數(shù)據(jù)結(jié)構(gòu)深入 - 棧和隊列文章來源地址http://www.zghlxwxcb.cn/news/detail-818819.html
到了這里，關(guān)于從0開始學(xué)C++ 第二十七課 數(shù)據(jù)結(jié)構(gòu)入門 - 數(shù)組與鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
