链表-查找结点

 链表好难啊! 理解了尾差法但是却无法写出完整代码.

题目描述

设计函数int  locate (struct node * head,char x);，找到以head为头指针的链表中，数据域的值等于x的结点，并返回该结点的序号(即是第几个结点)。

输入

一行包含#的字符串，将以#前的每个字符为数据域的值创建多个结点，并将这些结点，利用尾插法链接成链表。
#后还有一个字符，表示要在链表中查找数据域值为该字符的结点。

输出

所查找到的结点的序号。如果找不到这样的结点，则输出0。

样例输入

ABCDEF#D

样例输出

4

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct node
{
    char data;
    struct node *next;
};

int locate(struct node * head, char x);
void destroy(struct node* head);
struct node* tailinsert();

main()
{   char c;
    struct node *head;
    head=tailinsert();  
    c=getchar();
    printf("%d",locate(head,c));       
    destroy(head);
}

struct node* tailinsert()
{  
    @@1

    @@1 
    return head;
}


int locate(struct node * head, char x)
{
    struct node  *p=head;
    int i, n = 0;
    while(@#1) //如果链表中还有未扫描过的结点
    {
          @@2

          @@2
    }
    return 0;
}

void destroy(struct node* head)
{   
    struct node *p;
    while(head!=NULL)
    {
        p = head;             //p指向要销毁的结点
        head = head ->next;   //head指向再下一个要销毁的结点
        free(p);               //销毁p指向的结点
    }
}

答案

#include <stdio.h>
#include<string.h>
#include <stdlib.h>
struct node
{
    char data;
    struct node* next;
};

int locate(struct node* head, char x);
void destroy(struct node* head);
struct node* tailinsert();

main()
{
    char c;
    struct node* head;
    head = tailinsert();
    c = getchar();
    printf("%d", locate(head, c));
    destroy(head);
}

struct node* tailinsert()
{
    struct node* head,*p,*q;
    char ch;
    head = NULL;
    q = NULL;
    p = NULL;
    while (ch=getchar(),ch!='#')
    {
        p = (struct node*)malloc(sizeof(struct node));
        p->data = ch;
        p->next = NULL;
        if (head == NULL)
        {
            head = p;
            q = p;
        }
        else
        {
            q->next = p;
            q = p;
        }
    }
    
        return head;
}


int locate(struct node* head, char x)
{
    struct node* p = head;
    int i, n = 0;
    while (p!=NULL) //如果链表中还有未扫描过的结点
    {
        n++;
        if (p->data == x)
            return n;
        p = p->next;
    }
    return 0;
}

void destroy(struct node* head)
{
    struct node* p;
    while (head != NULL)
    {
        p = head;             //p指向要销毁的结点
        head = head->next;   //head指向再下一个要销毁的结点
        free(p);               //销毁p指向的结点
    }
}