非线性结构的特点在于其逻辑特征允许一个结点元素有多个直接前趋和多个直接后继-CSDN博客

本文链接：https://blog.csdn.net/blog_programb/article/details/145378777

非线性结构的特点在于其逻辑特征允许一个结点元素有多个直接前趋和多个直接后继。这意味着，非线性结构中各个数据元素不再保持在一个简单的线性序列中，而是可以与零个或多个其它数据元素相连接。

常见的非线性结构包括但不限于：

二维数组或多维数组，
广义表，
树形结构如二叉树等，
图结构，

其中多维数组由多个一维数组组成因而不属于单一维度上的线性排列。

对于这些结构来说，根据它们内部节点之间的关联特性，还可以进一步分类为层次结构或是群体结构等形式。

# 示例：创建一棵简单二叉树以展示非线性结构的一部分

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# 构建树
root = TreeNode('A')
root.left = TreeNode('B')
root.right = TreeNode('C')

def print_tree(node, level=0, prefix="Root: "):
    if node is not None:
        print(' ' * (level*4) + prefix + str(node.value))
        if node.left or node.right:
            if node.left:
                print_tree(node.left, level+1, "L--- ")
            else:
                print(' ' * ((level+1)*4) + "L--- None")
            if node.right:
                print_tree(node.right, level+1, "R--- ")
            else:
                print(' ' * ((level+1)*4) + "R--- None")

print_tree(root)

线性结构作为基础的数据组织形式，在不同场景下有着多种典型的数据结构实例：

数组
数组是一系列相同类型的元素连续存储于内存之中形成的集合。对于由26个英文字母组成的英文表{A, B, C, D…Z}而言，这些字母可以被看作是一个固定长度的字符数组。

char alphabetArray[] = {'A','B','C','D','E','F','G','H','I','J','K','L','M',
                        'N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};

链表
链表是由一系列节点组成的一种线性数据结构，每个节点包含两部分信息：一部分用来存放实体本身的数据域；另一部分则用于指向下一个节点地址指针域。

struct ListNode {
    int val;
    struct ListNode *next;
};
// 创建一个简单的单向链表并插入几个数值
ListNode* head = NULL; // 初始化为空链表
for(int i=0;i<3;++i){
    ListNode* newNode=(ListNode*)malloc(sizeof(ListNode));
    newNode->val=i+1;
    newNode->next=head;
    head=newNode;
}

这两种线性结构各自具备独特优势与劣势，并适用于不同类型的应用场合。

数组和链表作为两种基本的数据结构，在不同编程语言中有相似的特点但应用于不同的场景。

逻辑结构与内存布局
PHP中的数组是一种线性数据结构，所有元素在内存中是连续存储的。这使得通过索引能够快速访问任意位置上的元素。相比之下，链表由一系列节点组成，每个节点包含数据部分以及一个指向下一个节点的链接。
操作的时间复杂度
链表在执行插入和删除操作时表现出O(1)的时间复杂度优势，因为这些动作仅涉及更改指针而不必移动其他元素的位置；然而，在进行随机访问时，则需从头部开始逐一遍历直至找到目标项，导致平均情况下达到O(n)的时间消耗。
应用场景的选择
对于那些经常变动长度并且需要高效地完成增删任务的应用来说，比如实现栈或是队列，链表通常是更好的选择。而对于规模已知且要求迅速定位特定成员的情形——例如处理矩阵运算或管理定长记录集合——则应该优先考虑采用数组形式。

# 示例：Python代码片段展示如何创建简单的单向链表并添加新节点

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

head = Node('first')
second = Node('second')
third = Node('third')

head.next = second
second.next = third


# 创建一个简单的一维数组用于对比
array_example = ['first', 'second', 'third']

在特定场景下，链表相较于数组展现出独特的优势：

数据频繁插入与删除的操作环境

当面对需要大量动态调整长度的任务时，如栈和队列以外的二叉树以及图结构中，链表更为适用。因为这些场合要求灵活地增加或移除元素而不需要重新分配连续内存空间。

处理非常大的数据集且预先未知其大小的应用程序

如果应用无法预估所需存储的数据数量，则选择不依赖固定容量特性的链表可以避免因过度预留而导致浪费资源或者由于不足引起溢出错误等问题。

实现复杂逻辑判断任务

对于某些特殊问题，例如检测单向链表里是否存在循环（即环），利用节点之间的指针关系来设计解决方案就显得格外高效简洁。

# 示例：定义一个简单的链表结点类以帮助理解如何构建用于上述情况下的链表
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

广义表作为一种数据结构，具有复杂性和灵活性。下面具体说明：

多层结构
广义表的元素不仅可以是单一的原子还可以是子表，并且这些子表同样可以嵌套更多层次的子表，形成一个多层级的数据组织形式。
共享特性
当某个广义表作为另一个广义表的一部分时，可以直接通过名字来引用前者而不必重复定义其全部内容，实现了不同广义表之间的资源共享。
递归性质
部分广义表具备自包含的特点，即自身能够成为自己成员之一的部分组成。

关于广义表的基本概念还包括：

深度指的是最深一层括号的数量；
长度是指处于最高级别的直接成员数量；
对于特定实例，比如H=((a,b),(c,(d,e)))来说，因为存在三层嵌套关系故深度为3；而在顶层仅含有两个主要组成部分(a,b)以及(c,(d,e))因此长度等于2.

表头与表尾的概念也非常重要，
对于任意一个非空广义表而言，总是能区分出唯一的头部（可能是单独的对象或者是更小规模的广义表），其余剩下的整体则构成尾巴并且只能由其他广义表构成而非单纯元素.
对于特殊情况下的空表，
如果遇到完全没有内部成分的情况，则称作"空表", 如示例中提到的形式如 E=() 或者稍微复杂的版本像 F=(()), 其特征在于无法从中提取有效的首部信息，但后者仍可进一步分解得到一对空集作为各自的head和tail属性值.

广义表适用于多种复杂数据处理场景：

模式匹配在处理广义表时非常有用，允许以简洁且可读的方式提取所需的信息，也可以用于执行更复杂的操作，如更新或转换广义表。
表示嵌套表达式、树结构和多层嵌套数据等实际场景中广泛应用了广义表。这些应用不仅限于理论层面，在实现过程中针对可能出现的内存管理、递归效率、栈溢出等问题有对应的优化策略和解决方案。
当需要表示复杂数据和多层次信息的时候，广义表作为一种非常有用的数据结构能够满足这类需求；不过对于简单数据处理任务来说，则未必必要采用广义表。

// 示例代码展示如何定义一个简单的广义表节点（来自参考资料）
struct GList {
    bool isAtom; // 标记是不是原子项
    union {      // 节点可以是原子或者是子列表
        int atom;
        struct Node* sublist;
    } data;
};

关于广义表的优势，主要体现在以下几点：

复杂数据结构的支持

广义表不仅支持简单的线性数据组织方式，还能够表达复杂的层次化关系。通过不断复制表头和表尾的过程构建新的广义表实例。

然而，需要注意的是提供的参考资料并未直接提及广义表相对于其他特定数据结构如链式队列、顺序表或栈的具体优势对比信息。为了更准确地理解广义表相较于其他数据结构的优点，通常可以从理论上补充说明如下方面（此部分非引用原文）：

灵活性与扩展能力
广义表允许嵌套子表作为元素，这意味着可以在同一个表格内部创建多层结构，从而使得这种类型的列表非常适合用于表示树形或其他复杂的数据层级关系。
数据抽象度高
由于广义表可以容纳不同类型甚至不同种类的数据项（包括但不限于基本数值、字符以及其它形式的广义表），所以对于某些应用场景来说，它能提供更高的数据抽象级别。

广义表的概念基于递归定义，即一个广义表可以是空表，也可以是由一个元素（可以是原子或另一个广义表）和一个广义表构成。

对于广义表的具体实例化：

创建一个名为 LS 的广义表：LS = {1,{1,2,3}}, 这里广义表 LS 包含了一个原子 1 和子表 {1,2,3}。
可以构建如下的不同类型的广义表：
- A = (): 定义为空表
- B = (e): 构建只含有单一原子 e 的广义表
- C = (a,(b,c,d)): 组成包括原子 a 和子表 (b,c,d) 的广义表

关于两个看似相似但实际上不同的情况需要注意区分，
例如 A = () 表示的是真正的空表；而 A = (()) 则表示包含有一个空表作为其唯一成员的非空广义表。

为了在C++中实现上述概念的广义表，需要构造特定的数据结构来描述节点类型，并编写适当的操作以便管理和访问这些广义表的内容

为了实现广义表的基本操作，通常会涉及到创建、插入元素、删除元素以及遍历等动作。下面展示的是如何利用命令式编程语言如C来进行这些操作。

定义广义表结构与基本运算：

typedef struct GList {
    char data;
    struct GList *hp; // 指向子表头结点的指针域
    struct GList *tp; // 指向直接后继节点的指针域
} GLNode, *GList;

// 创建空广义表L
void CreateGList(GList &L) {
    L = (GLNode *)malloc(sizeof(GLNode));
    L->hp = NULL;
    L->tp = NULL;
}

插入新元素到指定位置之前:

bool InsertElemPrior(GList &L, const char elem, const char target) {
    if (!L || !elem)
        return false;
    
    GLNode* p = L;
    while(p && p->data != target){
        p = p -> tp;
    }
    if(!p) 
        return false;

    GLNode* newNode = (GLNode*)malloc(sizeof(GLNode));
    newNode->data = elem;
    newNode->tp = p;
    newNode->hp = p->hp;
    p->hp = newNode;

    return true;
}