定义一个单链表的存储结构，然后编写一个算法，单链表不带头结点统计单链表中值为x的结点个数。

定义一个单链表的存储结构，然后编写一个算法，单链表不带头结点统计单链表中值为x的结点个数。

#include<stdio.h>
#include<stdlib.h>

// 定义单链表结构体
struct Node{
    int data;
    struct Node* next;
};

// 统计单链表中值为x的节点个数
int countX(struct Node* head, int x){
    int count = 0;
    struct Node* cur = head;
    while(cur != NULL){
        if(cur->data == x){
            count++;
        }
        cur = cur->next;
    }
    return count;
}

int main(){
    // 创建一个单链表 1 -> 2 -> 3 -> 4 -> 5
    struct Node* head = malloc(sizeof(struct Node));
    head->data = 1;
    head->next = NULL;

    struct Node* node1 = malloc(sizeof(struct Node));
    node1->data = 2;
    node1->next = NULL;
    head->next = node1;

    struct Node* node2 = malloc(sizeof(struct Node));
    node2->data = 3;
    node2->next = NULL;
    node1->next = node2;

    struct Node* node3 = malloc(sizeof(struct Node));
    node3->data = 4;
    node3->next = NULL;
    node2->next = node3;

    struct Node* node4 = malloc(sizeof(struct Node));
    node4->data = 5;
    node4->next = NULL;
    node3->next = node4;

    // 调用统计算法统计单链表中值为3的节点个数
    int count = countX(head, 3);
    printf("The count of nodes which have the value of 3 in the linked list is: %d\n", count);

    // 释放动态内存
    free(node4);
    free(node3);
    free(node2);
    free(node1);
    free(head);

    return 0;
}

注：由于算法需要遍历单链表，因此需要将头结点指向真实的第一个节点，也就是不使用带头结点的单链表。

供参考：

#include <stdio.h>
#include <stdlib.h>
typedef struct node{
    int  data;
    struct node* next;
}Node, *List;
void createlist(List* L, int *a, int n)
{
    int i;
    List pL = NULL, pt = NULL;
    for (i = 0; i < n; i++)
    {
        pt = (List)malloc(sizeof(Node));
        pt->next = NULL;
        pt->data = a[i];
        if (!(*L))
            (*L) = pt;
        else
            pL->next = pt;
        pL = pt;
    }
}
void printlist(List L)
{
    List p = L;
    while(p){
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}
int count_x(List L, int x)
{
    List p = L;
    int  cnt = 0;
    while (p){
        if (p->data == x) cnt++;
        p = p->next;
    }
    return cnt;
}

int main()
{
    int a[]={2,3,5,1,7,9,5,10,4},x;
    List L = NULL;

    createlist(&L, a, sizeof(a)/sizeof(a[0]));//创建链表
    printlist(L);                             //输出链表

    x = 5;
    printf("x=%d:%d", x, count_x(L, x)); //输出结点值为x=5的结点个数

    return 0;
}

#include <iostream>

template<typename T>
struct LinkNode {                                            //链表结点的定义
    T data;                                                    //数据域
    LinkNode<T>* link;                                        //链指针域
    LinkNode(LinkNode<T>* ptr = nullptr) { link = ptr; }    //仅初始化指针成员的构造函数
    LinkNode(const T& item, LinkNode<T>* ptr = nullptr)        //初始化数据与指针成员的构造函数
    {
        data = item;
        link = ptr;
    }
};

template<typename T>
class List 
{
public:
    List() { first = nullptr; }                                //构造函数
    ~List() { makeEmpty(); }                                //析构函数
    void makeEmpty()                                        //将链表置为空表
    {
        //将链表置为空表
        LinkNode<T>* q;
        while (first != nullptr)                            //当链不空时，删去链中所有结点
        {
            q = first;
            first = first->link;                            //保存被删结点，从链上摘下该节点
            delete q;                                        //删除
        }
    }
    void insert(const T& value)                                //（头插法）插入结点
    {
        LinkNode<T>* node = new LinkNode<T>(value);
        node->link = first;
        first = node;
    }
    void output()                                            //输出
    {
        //单链表的输出函数：将单链表中所有数据按逻辑顺序输出到屏幕上。
        std::cout << "链表中的元素为：" << std::endl;
        LinkNode<T>* current = first;
        while (current != nullptr)
        {
            std::cout << current->data << " ";
            current = current->link;
        }
        std::cout << std::endl;
    }
    unsigned countValue(const T& value)
    {
        unsigned count = 0;
        LinkNode<T>* current = first;
        while (current != nullptr)
        {
            if (current->data == value)
                count++;
            current = current->link;
        }
        return count;
    }
private:
    LinkNode<T>* first;                                        //链表的头指针
};

int main()
{
    List<int> list;

    for (int i = 0; i < 10; i++)
    {
        list.insert(i % 3);
    }
    
    list.output();
    std::cout << "list.countValue(0) = " << list.countValue(0) << std::endl;
    std::cout << "list.countValue(1) = " << list.countValue(1) << std::endl;
    std::cout << "list.countValue(2) = " << list.countValue(2) << std::endl;    

    system("pause");
    return 0;
}