在单链表中反向搜索 [英] Reverse search in a singly-linked list
问题描述
有没有人知道最快的方法是从它的尾部搜索
单链表中的值。我的头脑是什么？
我说的是一个非圆形的单链表，即头部和尾部
没有连接。 />
当然，递归函数aproach遍历列表是一种方法。但是，
取决于列表大小，它可能会非常快地超出堆栈。
-sekhar
Hi,
Does anybody know what the fastest way is to "search for a value in a
singly-linked list from its tail" as oposed to its head?
I am talking about a non-circular singly-linked list, i.e., head and tail
are not connected.
Of course, recursive function aproach to traverse the list is one way. But,
depending upon the list size, it could overrun the stack pretty fast.
-sekhar
推荐答案
＃当然，递归函数aproach遍历列表是一种方法。但是，
＃取决于列表大小，它可能会非常快地超出堆栈。
您的堆栈太小。
如果你想要一个迭代解决方案，反转列表，搜索，再次反转它。
时间是列表大小的线性，这与搜索相同
一个未排序的集合。
#define List（Type，eq）\
typedef struct List ## Type {Type value; struct List ## Type link;} List ## Type; \
int searchList ## Type（List ## Type * list，Type value）{\
int i;列表##类型* p; for（i = 0，p = list; p; p = p-> link，i ++）\
if（eq（p-> value，value））return i; \
返回-1;} \
列表##类型* reverseList ##类型（列表##类型列表）{\
List ## Type * p，* c，* n; for（p = 0，c = list; c; p = c，c = n）\
{n = c-> link; c-> link = p;} \
返回p;} \
int reversesearchList ## Type（List ## Type * list，Type value）{ \
列表##类型* r =反向列表##类型（列表）; \
int n = searchList ## Type（r，Type value）;
reverseList ## Type（r）; \
返回n;}
-
Derk Gwen http://derkgwen.250free.com/html/index.html
什么样的便利店你在这里跑吗？
# Of course, recursive function aproach to traverse the list is one way. But,
# depending upon the list size, it could overrun the stack pretty fast.
Your stack is too small.
If you want an iterative solution, reverse the list, search, reverse it again.
The time is linear in the size of the list, which is the same for searching
an unsorted set.
#define List(Type,eq) \
typedef struct List##Type {Type value; struct List##Type link;} List##Type; \
int searchList##Type(List##Type *list,Type value) { \
int i; List##Type *p; for (i=0,p=list; p; p=p->link,i++) \
if (eq(p->value,value)) return i; \
return -1;} \
List##Type *reverseList##Type(List##Type list) { \
List##Type *p,*c,*n; for (p=0,c=list; c; p=c,c=n) \
{n = c->link; c->link = p;} \
return p;} \
int reversesearchList##Type(List##Type *list,Type value) { \
List##Type *r = reverseList##Type(list); \
int n = searchList##Type(r,Type value);
reverseList##Type(r); \
return n;}
--
Derk Gwen http://derkgwen.250free.com/html/index.html
What kind of convenience store do you run here?
2003年12月23日星期二21:24:38 -0500，RAJASEKHAR KONDABALA写道：
On Tue, 23 Dec 2003 21:24:38 -0500, RAJASEKHAR KONDABALA wrote:
有谁知道最快的方法是从它的尾部搜索单链表中的值。选择它的头？
Hi,
Does anybody know what the fastest way is to "search for a value in a
singly-linked list from its tail" as oposed to its head?
使用带有函数的for循环，该函数可以通过索引从
数组中检索元素。当然，这将类似于O（n * log n）
操作。将列表首先转换为数组会快得多快，因为快速索引会将列表转换为数组。更好的是，不要使用单一链表。使用
a双重链表。
Mike
Use a for loop with a function that can retrieve an element from the
array by index. Of course this will be something like an O(n*log n)
operation. It would be much faster to convert the list to an array first
for fast indexing. Better still, don''t use a singularly linked list. Use
a doubly linked list.
Mike
RAJASEKHAR KONDABALA< se **** **@verizon.net>这样说：
RAJASEKHAR KONDABALA <se******@verizon.net> spoke thus:
是否有人知道最快的方法是从其尾部搜索单链表中的值。如何选择它的头？
Does anybody know what the fastest way is to "search for a value in a
singly-linked list from its tail" as oposed to its head?
（以下欢迎文本最初由Ben Pfaff撰写）
你的问题在外面comp.lang.c的域名，它讨论了
只有标准的C编程语言，包括标准的C
库。与人们期望的很多
相比，这是一个非常狭窄的话题。
为了您的方便，下面的列表包含的主题不是
on-topic for comp.lang.c，并建议您浏览新闻组
如果您对这些主题有疑问。在发布到任何这些新闻组之前，请务必遵守正确的
网络礼节。特别是，你应该阅读小组的章程和常见问题，如果有的话（常见问题是
来自 www.faqs.org 和其他来源）。如果那些人没有回答你的问题，那么你应该浏览至少两周
的近期文章，以确保你的问题还没有。
已被回答。
*特定于操作系统的问题，例如如何清除屏幕，
访问网络，列出目录中的文件，或者阅读
管道子进程的输出。这些问题应该是针对特定于操作系统的新闻组，例如
comp.os.ms-windows.programmer.misc，comp.unix.programmer或者
comp.os.linux.development.apps。
*编译器特有的问题，例如安装问题和
标题的位置文件。在
编译器特定的新闻组中询问这些，例如gnu.gcc.help或
comp.os.ms-windows.programmer.misc。有关编写
编译器的问题在comp.compilers中是合适的。
*特定于处理器的问题，例如关于
汇编的问题和机器代码。 x86问题适用于
comp.lang.asm.x86，嵌入式系统处理器问题可能适用于comp.arch.embedded中的
。
*特定于ABI的问题，例如如何将汇编
代码连接到C.这些问题都是处理器和
特定于操作系统的问题，通常应该是在特定操作系统中询问
新闻组。
*算法，除了有关
算法的C实现的问题。 如何在C中实现算法X？关于算法的C实现不是一个问题，它是一个
的源代码请求。新闻组comp.programming和
comp.theory可能是合适的。
*使C与其他语言互操作。对于这种互操作，C没有
设施。这些问题应该直接指向系统或编译器特定的新闻组。 C ++
具有与C互操作的功能，因此请考虑
comp.lang.c ++来解决这些问题。
* C标准，而不是标准C.关于
的问题C标准最好在comp.std.c中询问。
* C ++。请不要将有关C ++
的问题发布或交叉发布到comp.lang.c.在C ++新闻组中询问C ++问题，例如comp.lang.c ++或comp.lang.c ++。版本的
。
*测试帖子。请在一个用于测试的新闻组中进行测试，
，例如alt.test。
news.groups.questions是一个讨论适当的好地方
给定主题的新闻组。
-
Christopher Benson-Manica |我*应该*知道我在说什么 - 如果我
ataru（at）cyberspace.org |不，我需要知道。火焰欢迎。
(The below welcome text was originally written by Ben Pfaff)
Your question is outside the domain of comp.lang.c, which discusses
only the standard C programming language, including the standard C
library. This is a remarkably narrow topic compared to what many
people expect.
For your convenience, the list below contains topics that are not
on-topic for comp.lang.c, and suggests newsgroups for you to explore
if you have questions about these topics. Please do observe proper
netiquette before posting to any of these newsgroups. In particular,
you should read the group''s charter and FAQ, if any (FAQs are
available from www.faqs.org and other sources). If those fail to
answer your question then you should browse through at least two weeks
of recent articles to make sure that your question has not already
been answered.
* OS-specific questions, such as how to clear the screen,
access the network, list the files in a directory, or read
"piped" output from a subprocess. These questions should be
directed to OS-specific newsgroups, such as
comp.os.ms-windows.programmer.misc, comp.unix.programmer, or
comp.os.linux.development.apps.
* Compiler-specific questions, such as installation issues and
locations of header files. Ask about these in
compiler-specific newsgroups, such as gnu.gcc.help or
comp.os.ms-windows.programmer.misc. Questions about writing
compilers are appropriate in comp.compilers.
* Processor-specific questions, such as questions about
assembly and machine code. x86 questions are appropriate in
comp.lang.asm.x86, embedded system processor questions may
be appropriate in comp.arch.embedded.
* ABI-specific questions, such as how to interface assembly
code to C. These questions are both processor- and
OS-specific and should typically be asked in OS-specific
newsgroups.
* Algorithms, except questions about C implementations of
algorithms. "How do I implement algorithm X in C?" is not a
question about a C implementation of an algorithm, it is a
request for source code. Newsgroups comp.programming and
comp.theory may be appropriate.
* Making C interoperate with other languages. C has no
facilities for such interoperation. These questions should
be directed to system- or compiler-specific newsgroups. C++
has features for interoperating with C, so consider
comp.lang.c++ for such questions.
* The C standard, as opposed to standard C. Questions about
the C standard are best asked in comp.std.c.
* C++. Please do not post or cross-post questions about C++
to comp.lang.c. Ask C++ questions in C++ newsgroups, such
as comp.lang.c++ or comp.lang.c++.moderated.
* Test posts. Please test in a newsgroup meant for testing,
such as alt.test.
news.groups.questions is a good place to ask about the appropriate
newsgroup for a given topic.
--
Christopher Benson-Manica | I *should* know what I''m talking about - if I
ataru(at)cyberspace.org | don''t, I need to know. Flames welcome.
这篇关于在单链表中反向搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
