dsal C 中的标头链表

C 中的标头链表

原文：https://www.geeksforgeeks.org/header-linked-list-in-c/

标头节点是在列表的开头的处找到的特殊节点。包含此类节点的列表称为标头链表。当需要除每个节点中的信息以外的其他信息时，这种类型的列表很有用。

例如，假设有一个应用，其中经常计算列表中的项目数。通常，始终会遍历列表以查找列表的长度。然而，如果在另外的报头节点中保持当前长度，则可以容易地获得信息。

标头链表的类型

接地标头链表

这是一个列表，其最后一个节点包含NULL指针。在头部链表中，起始指针始终指向头部节点。 start->next = NULL表示接地标头链表为NULL。在此类型的链表上可能执行的操作是插入，删除和遍历。

循环标头链表

其中最后一个节点指向头节点的列表称为循环链表。链条不指示第一个或最后一个节点。在这种情况下，外部指针提供了引用框架，因为循环链表的最后一个节点不包含NULL指针。对这种类型的链表的可能操作是插入，删除和遍历。

// C program for a Header Linked List 
#include <malloc.h> 
#include <stdio.h> 

// Structure of the list 
struct link { 
    int info; 
    struct link* next; 
}; 

// Empty List 
struct link* start = NULL; 

// Function to create a header linked list 
struct link* create_header_list(int data) 
{ 

    // Create a new node 
    struct link *new_node, *node; 
    new_node = (struct link*) 
        malloc(sizeof(struct link)); 
    new_node->info = data; 
    new_node->next = NULL; 

    // If it is the first node 
    if (start == NULL) { 

        // Initialize the start 
        start = (struct link*) 
            malloc(sizeof(struct link)); 
        start->next = new_node; 
    } 
    else { 

        // Insert the node in the end 
        node = start; 
        while (node->next != NULL) { 
            node = node->next; 
        } 
        node->next = new_node; 
    } 
    return start; 
} 

// Function to display the 
// header linked list 
struct link* display() 
{ 
    struct link* node; 
    node = start; 
    node = node->next; 
    while (node != NULL) { 
        printf("%d ", node->info); 
        node = node->next; 
    } 
    printf("\n"); 
    return start; 
} 

// Driver code 
int main() 
{ 

    // Create the list 
    create_header_list(11); 
    create_header_list(12); 
    create_header_list(13); 

    // Print the list 
    display(); 
    create_header_list(14); 
    create_header_list(15); 

    // Print the list 
    display(); 

    return 0; 
}

输出：

11 12 13 
11 12 13 14 15

标头链表的多项式应用

标头链表经常用于在内存中维护多项式。 头节点用于表示零多项式。
假设我们有

F(x) = 5x^5 – 3x^3 + 2x^2 + x^1 + 10x^0
从F(x)表示的多项式可以清楚地看出，该多项式具有系数和指数两部分，其中x是形式参数 。因此，我们可以说多项式是项的和，每个项都由一个系数和一个指数组成。
计算机实现要求将多项式实现为系数和指数对的列表。这些对中的每对都将构成一个结构，因此多项式将表示为结构列表。
如果要在链表的帮助下表示F(x)，则该表将包含 5 个节点。当我们链接每个节点时，我们得到一个表示多项式F(x)的链表结构。