数据结构与C++

数据结构与C++ 知识量:9 - 32 - 91

4.3 串的链式存储><

串的链式存储结构- 4.3.1 -

链式存储结构是线性表的一种存储方式,它使用链表来存储数据元素。对于串(字符串)的链式存储结构,每个结点可以存放一个字符,也可以存放多个字符。具体来说,每个结点可以表示为一个字符型变量或者一个字符数组。

在链式存储结构中,每个结点除了存储字符外,还需要存储指向下一个结点的指针。这样,通过指针可以依次访问链表中的所有结点,从而实现对整个串的访问和操作。

下面是一个简单的C++示例,演示了如何使用链表来存储串值:

#include <iostream>  
#include <string>  
  
using namespace std;  
  
// 定义链表结点的结构体  
struct Node {  
    char data;           // 结点中存储的字符  
    Node* next;           // 指向下一个结点的指针  
};  
  
// 创建新结点  
Node* createNode(char data) {  
    Node* newNode = new Node();  
    if (!newNode) {  
        cout << "Memory error\n";  
        return nullptr;  
    }  
    newNode->data = data;  
    newNode->next = nullptr;  
    return newNode;  
}  
  
// 在链表末尾添加新结点  
void appendNode(Node** head, char data) {  
    Node* newNode = createNode(data);  
    if (*head == nullptr) {  
        *head = newNode;  
        return;  
    }  
    Node* last = *head;  
    while (last->next != nullptr) {  
        last = last->next;  
    }  
    last->next = newNode;  
}  
  
// 打印链表中的所有结点值  
void printList(Node* head) {  
    while (head != nullptr) {  
        cout << head->data << " ";  
        head = head->next;  
    }  
    cout << endl;  
}  
  
int main() {  
    Node* head = nullptr;  // 链表的头结点指针,初始为空  
    char str[] = "Hello, world!";  // 要存储的字符串  
    int length = strlen(str);  // 字符串长度  
    for (int i = 0; i < length; i++) {  
        appendNode(&head, str[i]);  // 将每个字符添加到链表末尾  
    }  
    printList(head);  // 打印链表中的所有结点值  
    return 0;  
}

在这个示例中,首先定义了一个Node结构体来表示链表中的结点,每个结点包含一个字符data和一个指向下一个结点的指针next。然后,实现了三个函数:createNode用于创建新结点,appendNode用于在链表末尾添加新结点,printList用于打印链表中的所有结点值。在main函数中,使用这些函数来将字符串"Hello, world!"中的每个字符依次添加到链表中,并打印出链表中的所有结点值。