1 //解法一：带尾节点的双向链表
  2 #include<stdio.h>
  3 #include<stdlib.h>
  4 #include<malloc.h>
  5 //using namespace std;
  6 //输入数据，从尾节点，用prior指针向左移K-1位
  7 //注意：遇到头结点，即为不存在，输出NULL
  8 
  9 #define OK 1
 10 #define ERROR 0
 11 //#define
 12 typedef int ElemType;
 13 typedef int Status;
 14 
 15 typedef struct DuLNode
 16 {
 17     ElemType data;
 18     DuLNode *prior;//前驱
 19     DuLNode *next;//后继
 20 }DuLNode,*DuLink;
 21 
 22 typedef struct
 23 {
 24     DuLink head;//头指针
 25     DuLink tail;//尾指针
 26     int length;
 27 }DuLinkList;//它是结构体类型
 28 
 29 Status Create_DuL_ht(DuLinkList &L)//摸索
 30 {
 31     L.head=(DuLNode*)malloc(sizeof(DuLNode));
 32     L.head->next=NULL;
 33     L.head->prior=NULL;
 34     L.tail=L.head;//应该是这么初始化吧
 35     L.length=0;
 36 
 37     DuLNode *cur=(DuLNode*)malloc(sizeof(DuLNode));//开新节点
 38     cur->next=L.head;//指向头结点
 39     scanf("%d",&cur->data);
 40     while(cur->data>=0)
 41     {
 42         cur->next=L.head;
 43         L.tail->next=cur;
 44         cur->prior=L.tail;
 45         L.tail=cur;
 46         L.head->prior=L.tail;
 47         ++L.length;
 48 
 49         cur=(DuLNode*)malloc(sizeof(DuLNode));
 50         cur->next=L.head;
 51         scanf("%d",&cur->data);
 52 
 53     }
 54 
 55     return OK;
 56 
 57 }
 58 
 59 
 60 Status CountBack_k(DuLinkList &L,int k)
 61 {//用计数器从tail往前找，只要没遇到倒数第k项且没遇到头结点，就前移；
 62     if(k>L.length)
 63     {
 64         printf("NULL");
 65         return OK;
 66     }
 67     DuLNode *p;
 68     if(k<L.length/2)
 69     {
 70      int i=1;
 71      p=L.tail;
 72      while(p!=L.head&&i<k)
 73      {
 74          p=p->prior;
 75          ++i;
 76      }
 77 
 78     }
 79     else
 80     {
 81         int i=1;
 82         p=L.head->next;
 83         k=L.length-k+1;
 84         while(p!=L.head&&i<k)
 85         {
 86             p=p->next;
 87             ++i;
 88         }
 89     }
 90 
 91      printf("%d",p->data);
 92 
 93      return OK;
 94 
 95 } 
 96 
 97 
 98 int main()
 99 {
100     DuLinkList L;
101     int k;
102     scanf("%d",&k);
103     Create_DuL_ht(L);
104     //printf("%d",L.tail->prior->data);//创建函数没有错误
105     CountBack_k(L,k);
106     
107 
108     return 0;
109 }//

 1 /*
 2 //解法二，普通单链表
 3 #include<stdio.h>
 4 #include<stdlib.h>
 5 #include<malloc.h>
 6 #define OK 1
 7 #define ERROR 0
 8 //#define
 9 typedef int ElemType;
10 typedef int Status;
11 
12 typedef struct LNode
13 {
14     ElemType data;
15     LNode *next;
16 }LNode,*LinkList;
17 
18 Status Creat_L(LinkList &L)
19 {
20     L=(LNode*)malloc(sizeof(LNode));
21     L->next=NULL;
22 
23     LNode *rear,*cur;
24     rear=L;
25     cur=(LNode*)malloc(sizeof(LNode));
26     scanf("%d",&cur->data);//cin>>cur->data;
27     cur->next=NULL;
28 
29     while(cur->data!=-1)
30     {
31         rear->next=cur;
32         rear=cur;
33 
34         cur=(LNode*)malloc(sizeof(LNode));
35         scanf("%d",&cur->data);
36         cur->next=NULL;
37 
38     }
39 
40     return OK;
41 }
42 
43 Status CountBack_k(LinkList &L,int k)
44 {
45     LNode *p,*q;
46     p=L->next;
47     q=NULL;
48     int i=0;
49     while(p)
50     {
51         p=p->next;
52         i++;
53         if(i==k)
54         q=L->next;
55         if(i>k)
56         q=q->next;
57 
58     }
59 
60     if(q)
61     printf("%d",q->data);//cout<<q->data;
62     else
63     printf("NULL");//cout<<"NULL";
64 
65 }
66 
67 int main()
68 {
69     LinkList L;
70     int k;
71     scanf("%d",&k);//cin>>k;
72     Creat_L(L);
73     //cout<<L->next->next->data;输入函数没问题
74     CountBack_k(L,k);
75 }//
76 */