链式线性表——课上练

链式线性表是一种常见的数据结构，它通过指针将数据元素连接在一起，形成一个链式结构。链式线性表有以下几个特点和功能：
1. 可扩展：链式线性表可以在中间或尾部新增记录，只需要修改相应节点的指针即可。
2. 可删除数据：链式线性表可以删除指定学号的数据，只需调整相应节点的指针即可。
3. 可统计：链式线性表可以统计记录数量、平均成绩、最低成绩和最高成绩。每次增加或删除数据后，可以重新统计这些信息。
4. 可查询：链式线性表可以查询某个学号对应的相关信息，只需遍历链表找到对应节点即可。

相关问题

二叉树——课上练（链式存储结构）

二叉树的链式存储结构是通过定义一个含有数据和指向左右子节点的指针的结构体来实现的。每个结点都包含一个数据项和两个指针，分别指向其左子节点和右子节点。采用链式存储结构的优点是可以灵活地插入、删除和修改节点，但相应的缺点是需要更多的存储空间和额外的指针操作。

在建立二叉树时，可以按照先序遍历的顺序输入节点序列，并采用递归方式进行建立。例如，按照先序输入的节点序列为：a b c # # # d e # f # # g # #。其中，#表示空节点。通过递归方式建立二叉树可以保证节点的插入顺序与先序输入的顺序一致。

关于二叉树的一些特性和存储方式，还有以下几点：
1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1)个节点。
2. 若规定只有根节点的二叉树的深度为1，则深度为K的二叉树的最大节点数是2^k-1。
3. 对任何一棵二叉树，如果其叶节点个数为n0，度为2的非叶节点个数为n2，则有n0 = n2 + 1。
4. 具有n个节点的完全二叉树的深度k为log2(n+1)向上取整。

链式线性表的倒数

链式线性表的倒数是指从链表的末尾开始数，倒数第一个元素为链表的最后一个元素，倒数第二个元素为链表的倒数第二个元素，以此类推。

要求链式线性表的倒数第k个元素，可以使用双指针法。首先让第一个指针从链表的头节点开始向后移动k-1个节点，然后再让第二个指针从链表的头节点开始向后移动，直到第一个指针指向链表的尾节点。此时，第二个指针所指向的节点就是倒数第k个节点。

具体实现可以参考以下代码：

def find_kth_from_end(head, k):
    if not head or k <= 0:
        return None
    
    p1 = p2 = head
    for i in range(k - 1):
        if not p1.next:
            return None
        p1 = p1.next
    
    while p1.next:
        p1 = p1.next
        p2 = p2.next
    
    return p2

其中，head为链表的头节点，k为要查找的倒数第k个元素的位置。如果链表为空或者k小于等于0，则直接返回None。否则，我们使用双指针法找到倒数第k个节点，并返回该节点。