求单链表倒数第k个结点

liwenhao96

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

仰望天上的光

1. /*
   
2. 输入一个字符序列，生成带头结点的单链表，输入0表示结束，例如输入1230，则生成的单链表为->|  | -> | 1 | -> | 2 | -> | 3 |。输出该链表中倒数第k个结点的值。
   
3. 例如，输入：12548632102
   
4. 输出：2
   
5. */
   
6. 
   
7. #include <stdio.h>
   
8. #include <stdlib.h>
   
9. 
   
10. struct Node {
    
11.         char data;
    
12.         struct Node* next;
    
13. };
    
14. struct Node* create_node( char d, struct Node* n );
    
15. 
    
16. struct List {
    
17.         struct Node* pHead;
    
18.         struct Node* pTail;
    
19.         int to_be_found_in_reverse;
    
20. };
    
21. void init_and_input( struct List* plist );
    
22. void output_and_destroy( struct List* pList );
    
23. void init( struct List* plist );
    
24. void destroy( struct List* plist );
    
25. void show( const struct List* pList );
    
26. 
    
27. int main() {
    
28.         struct List list;
    
29.         init_and_input( &list );
    
30.         //show( &list );
    
31.         output_and_destroy( &list );
    
32. }
    
33. 
    
34. void init_and_input( struct List* plist ) {
    
35.         char tmp;
    
36.         init( plist );
    
37.         while( (tmp = getchar()) != '0' ) {
    
38.                 plist->pTail->next = create_node( tmp, NULL );
    
39.                 plist->pTail = plist->pTail->next;
    
40.         }
    
41.         scanf("%d",&plist->to_be_found_in_reverse);
    
42. }
    
43. 
    
44. struct Node* create_node( char d, struct Node* n ) {
    
45.         struct Node* result;
    
46.         result = (struct Node*)malloc( sizeof( struct Node ) );
    
47.         result->data = d;
    
48.         result->next = n;
    
49.         return result;
    
50. }
    
51. 
    
52. void show( const struct List* pList ) {
    
53.         const struct Node* p;
    
54.         for( p = pList->pHead->next; p; p=p->next ) {
    
55.                 printf("%c",p->data);
    
56.         }
    
57.         printf("\n");
    
58. }
    
59. 
    
60. void output_and_destroy( struct List* pList ) {
    
61.         const struct Node* p;
    
62.         int total_step = 0;
    
63.         int step;//正数的步数
    
64.         int i;
    
65.         for( p = pList->pHead->next; p; p=p->next ) {
    
66.                 ++total_step;
    
67.         }
    
68.         step = total_step - pList->to_be_found_in_reverse;
    
69.         for( p = pList->pHead->next,i=0; i<step; p=p->next,++i );
    
70.         printf("%c\n",p->data);
    
71.         destroy( pList );
    
72. }
    
73. 
    
74. void init( struct List* plist ) {
    
75.         plist->pHead = create_node( 0, NULL );
    
76.         plist->pTail = plist->pHead;
    
77. }
    
78. 
    
79. void destroy( struct List* plist ) {
    
80.         struct List* tmp;
    
81.         while( plist->pHead ) {
    
82.                 tmp = plist->pHead;
    
83.                 plist->pHead = plist->pHead->next;
    
84.                 free( tmp );
    
85.         }
    
86. }

复制代码

梦醒尸还魂↘___

又是个要交作业的，

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;


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