求单链表倒数第k个结点
输入一个字符序列，生成带头结点的单链表，输入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 );
}
} 又是个要交作业的， 给你提供个思路，用两个指针。
倒数第N个，那么他们指针的间隔就是N，当某一个先遍历完的时候，在后面的那个再往下走一步就是指向倒数第N个了 这个，小甲鱼的数据结构与算法里面应该有啊！:lol: 李文浩。。原来你也是大机电的。。。快被这个作业搞疯了:dizzy: 薄人薄情薄往倾 发表于 2014-4-28 21:29 static/image/common/back.gif
李文浩。。原来你也是大机电的。。。快被这个作业搞疯了
Who are you:sweat: #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;
}
好像输出有点出入，自己试着找下原因吧，找到顺便给我说下。
页:
[1]