求单链表倒数第k个结点

liwenhao96

输入一个字符序列，生成带头结点的单链表，输入0表示结束，例如输入1230，则生成的单链表为->|  | -> | 1 | -> | 2 | -> | 3 |。输出该链表中倒数第k个结点的值。
例如，输入：12548632102
输出：2

仰望天上的光

/*
输入一个字符序列，生成带头结点的单链表，输入0表示结束，例如输入1230，则生成的单链表为->|  | -> | 1 | -> | 2 | -> | 3 |。输出该链表中倒数第k个结点的值。
 例如，输入：12548632102
 输出：2
*/

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

struct Node {
        char data;
        struct Node* next;
};
struct Node* create_node( char d, struct Node* n );

struct List {
        struct Node* pHead;
        struct Node* pTail;
        int to_be_found_in_reverse;
};
void init_and_input( struct List* plist );
void output_and_destroy( struct List* pList );
void init( struct List* plist );
void destroy( struct List* plist );
void show( const struct List* pList );

int main() {
        struct List list;
        init_and_input( &list );
        //show( &list );
        output_and_destroy( &list );
}

void init_and_input( struct List* plist ) {
        char tmp;
        init( plist );
        while( (tmp = getchar()) != '0' ) {
                plist->pTail->next = create_node( tmp, NULL );
                plist->pTail = plist->pTail->next;
        }
        scanf("%d",&plist->to_be_found_in_reverse);
}

struct Node* create_node( char d, struct Node* n ) {
        struct Node* result;
        result = (struct Node*)malloc( sizeof( struct Node ) );
        result->data = d;
        result->next = n;
        return result;
}

void show( const struct List* pList ) {
        const struct Node* p;
        for( p = pList->pHead->next; p; p=p->next ) {
                printf("%c",p->data);
        }
        printf("\n");
}

void output_and_destroy( struct List* pList ) {
        const struct Node* p;
        int total_step = 0;
        int step;//正数的步数
        int i;
        for( p = pList->pHead->next; p; p=p->next ) {
                ++total_step;
        }
        step = total_step - pList->to_be_found_in_reverse;
        for( p = pList->pHead->next,i=0; i<step; p=p->next,++i );
        printf("%c\n",p->data);
        destroy( pList );
}

void init( struct List* plist ) {
        plist->pHead = create_node( 0, NULL );
        plist->pTail = plist->pHead;
}

void destroy( struct List* plist ) {
        struct List* tmp;
        while( plist->pHead ) {
                tmp = plist->pHead;
                plist->pHead = plist->pHead->next;
                free( tmp );
        }
}

梦醒尸还魂↘___

又是个要交作业的，

epluguo

给你提供个思路，用两个指针。
倒数第N个，那么他们指针的间隔就是N，当某一个先遍历完的时候，在后面的那个再往下走一步就是指向倒数第N个了

青玄

这个，小甲鱼的数据结构与算法里面应该有啊！:lol:

薄人薄情薄往倾

李文浩。。原来你也是大机电的。。。快被这个作业搞疯了:dizzy:

liwenhao96

薄人薄情薄往倾 发表于 2014-4-28 21:29

                               
登录/注册后可看大图

李文浩。。原来你也是大机电的。。。快被这个作业搞疯了

Who are you:sweat:

Prophet

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

struct node
{
        char ch;
        struct node* next;
};
struct list
{
        struct node* head_node;
        int len;


};
struct node* malloc_node(char ch)
{
        struct node* node = malloc(sizeof(struct node));
        node->ch = ch;
        node->next = NULL;
       
        return node;

}
struct list* malloc_list(void )
{
        struct list* l = malloc(sizeof(struct list));
        l->head_node = malloc(sizeof(struct node));
        l->head_node->next = NULL;
        l->len = 0;
        return l;
}
void push_front(struct list* l,char ch)
{
        struct node* node = malloc_node(ch);
        if(l->len==0)
        {
                l->head_node = node;
                l->len++;
                return ;
        }
        node->next = l->head_node->next;
        l->head_node->next = node;
        l->len++;

}
char search(struct list* l ,int k)
{
        struct node* cur = NULL;
        int n = 0;
        if(l->len<k)
        {
                printf("NULL");
                return '\0';
        }
        else
        {
                n = l->len-k+1;
                cur = l->head_node->next;
                while(--n)
                {
                        cur = cur->next;
                }
                return cur->ch;

        }

}
int main()
{
        struct list* l = malloc_list();
        char ch;
        printf("Please input the character: ");
        while(1)
        {
                ch = getchar();
                if(ch == '0')
                        break;
                push_front(l,ch);
        }
        printf("The third character is :");
        ch = search(l,3);        注释倒数第三个字符。
        putchar(ch);
        putchar('\n');
        return 0;


}
好像输出有点出入，自己试着找下原因吧，找到顺便给我说下。