Memmove v / s链接列表实施 [英] Memmove v/s Linked list Implementation
问题描述
你好我的朋友们，这是我第一次在
新闻组中发帖。这是我的问题陈述：
我和我的朋友决定使用我们自己的
样式解决编程问题，然后决定哪一个是最好的。问题是：
"从给定的
字符串中删除所有出现的字符（不区分大小写）"
例如。
i / p：她将是一个无大量的公主
o / p：他将是一个男性王子（所有''s'被删除了）
我的朋友通过创建所有
字符的链接列表来实现解决方案，其中每个节点都包含一个字符！这是他的代码：
#include< stdio.h>
#include< iostream>
#include< conio.h>
使用命名空间std;
typedef struct charNode
{
char ch ;
charNode * nxt;
charNode（char ch1 = 0）{
nxt = NULL;
ch = ch1;
}
} cn;
int main（）
{
cn * head = NULL，* temp，* node;
char ch1 =''e''，ch2; // ch1用于保存
消除和ch2临时存储char
cout<< 输入字符串 ;
head = new cn（）;
node = head;
ch2 = cin.get（）;
while（ch2！= 10）{//这个while循环用于创建SLL
temp = new cn（ch2）;
node-> nxt = temp;
node = node-> nxt;
ch2 = cin.get（）;
}
node = head; //删除不需要的字符...这个由b1给出的
字符
while（node-> nxt！= NULL）{
if（node-> nxt-> ch == ch1）{
temp = node-> nxt;
if（temp-> nxt == NULL）
node-> nxt = NULL;
else
node-> nxt = node-> nxt-> nxt ;
删除临时;
}
其他
node = node-> nxt;
}
node = head; //显示元素！
while（node -nxt！= NULL）{
cout<< node-> ch;
node = node-> nxt;
}
cout<< node-> ch;
getchar（）;
返回0;
}
然而我使用memmove实现了解决方案，即转移
整个字符串当遇到要消除的角色时。这里
是我的努力：
#include< stdio.h>
#include< string.h> < br $>
const char chUpper =''S'';
const char chLower ='s'';
void remove_s（ char tmp []）
{
while（* tmp！=''\'''）
{
if（* tmp == chLower || * tmp == chUpper）
{
memmove（tmp，tmp + 1，& tmp [strlen（tmp） ）] - tmp）;
}
其他
{
tmp ++;
}
}
}
int main（）
{
char str [] =" Asser是一个asser，只有asser，所以是
solemsn" ;
printf（" \ n旧字符串：％s"，str）;
remove_s（str）;
printf（" ; \ n新字符串：％s"，str）;
getchar（）;
return（0）;
}
现在的问题是，我们无法决定哪一段代码更加昂贵，而且会开始给出问题。长度
的字符串增加.....
您的专家观点或任何其他有效的实施表示赞赏。
另外如果你能指出我的问题区域
或他的代码那将是非常好的....
再次感谢...
ge ************** @ gmail.com 写道：
你好我的朋友，这是我第一次在
新闻组中发帖。这是我的问题陈述：
我和我的朋友决定使用我们自己的
样式解决编程问题，然后决定哪一个是最好的。问题是：
"从给定的
字符串中删除所有出现的字符（不区分大小写）"
例如。
i / p：她将是一个无大量的公主
o / p：他将是一个男性王子（所有''s'被删除了）
我的朋友通过创建所有
字符的链接列表来实现解决方案，其中每个节点都包含一个字符！这是他的代码：
#include< stdio.h>
#include< iostream>
#include< conio.h>
using namespace std;
请将C ++代码发布到comp.lang.c ++。另请阅读此论坛的常见问题解答
来自c-faq.com的
。
现在的问题是，我们无法进入决定哪一段代码更多
计算成本昂贵，并且随着字符串长度的增加而开始出现问题.....
这两种方法对于规范来说都有点过分，因为你已经说明了上面所说的
。
ge ************** @ gmail.com 写道：
你好我的朋友们，这是我第一次在
新闻组中发帖。
你选错了。你的程序是用C ++编写的，但你发布到comp.lang.c的是
。此外，你真的有一个
算法问题，但comp.lang.c与算法无关。
我和我的朋友决定用我们自己的
样式解决编程问题，然后决定哪一个是最好的。问题是：
"从给定的
字符串中删除所有出现的字符（不区分大小写）"
例如。
i / p：她将是一个无大量的公主
o / p：他将是一个男性王子（所有''s'被删除了）
我的朋友通过创建所有
字符的链接列表来实现解决方案，其中每个节点都包含一个字符！这是他的代码：
[...]
我使用memmove实现了解决方案，即在遇到要删除的字符时移动
整个字符串。这里
是我的努力：
[...]
现在的问题是，我们不能决定哪一段代码更加昂贵，并且随着字符串的长度增加而开始出现问题。 ....
链表解决方案可能需要O（N）时间和空间，但移动
其余的字符串对于每个s而言，遇到了
需要O（N ** 2）时间和O（N）空间。
这是一个更好的解决方案（虽然我还没有测试过它）：
/ *删除所有s STRING中的字符，就地。 * /
void
remove_s（char * string）
{
char * p = string;
do {
if（* string！=''s''）
* p ++ = * string;
} while（* string ++！=''\ 0''）;
}
-
大笔资金倾向解决我可能遇到的任何顾忌。
- Stephan Wilms
> Santosh写道：
请将C ++代码发布到comp.lang.c ++。另请阅读c-faq.com的这个小组的常见问题解答
。
但是因为我的计划在CI中认为这将是一个更好的地方。
你不觉得如果我发布了comp.langauge.c ++组，他们
对我说同样的事情，因为我在C中的代码和我的朋友在
C ++？
Ben Pfaff写道：
你选错了。你的程序是用C ++编写的，但你发布到comp.lang.c的是
。此外，你真的有一个
算法问题，但comp.lang.c与算法无关。
有没有算法新闻组？顺便说一句，我的代码是在C和我的朋友们用C ++编写的
。
链表解决方案可能需要O（N）时间和空间，但是为了每个s而移动
字符串的其余部分。遇到
需要O（N ** 2）时间和O（N）空间。
所以我想这意味着memmove毕竟比
链接列表更昂贵...但我认为memmove在C中实现了
汇编并且移动原始数据块的速度和它在C中获得的价格一样快？
Hello there my friends, this is my first attempt at posting in a
newsgroup. Here is my problem statement:
Me and my friend decided to solve a programming problem with our own
styles and then decide which one is the best. The problem being:
"Remove all occurrences of a character (case insensitive) from a given
string"
eg.
i/p: She will be a massless princess
o/p: he will be a male prince (all occurances of ''s'' removed)
My friend implemented the solution by creating a Linked List of all the
character in which each node holds one character !!! Here is his code:
#include<stdio.h>
# include <iostream>
# include <conio.h>
using namespace std;
typedef struct charNode
{
char ch;
charNode* nxt;
charNode(char ch1 = 0){
nxt = NULL;
ch = ch1;
}
}cn;
int main()
{
cn* head = NULL,* temp, *node;
char ch1 = ''e'', ch2;// ch1 is to hold the char that is to be
elimintated and ch2 to temp store the char
cout<< "enter string " ;
head = new cn ();
node = head;
ch2 = cin.get();
while ( ch2 != 10) { // this while loop for creating SLL
temp = new cn(ch2) ;
node->nxt = temp;
node = node->nxt;
ch2 = cin.get();
}
node = head; // for removal of unwanted character ... this
character given by ch1
while (node->nxt != NULL) {
if ( node->nxt->ch == ch1 ) {
temp = node->nxt;
if( temp->nxt == NULL )
node->nxt = NULL;
else
node->nxt = node->nxt->nxt;
delete temp;
}
else
node = node->nxt;
}
node = head; // display the elements !
while ( node -nxt != NULL ) {
cout<<node->ch;
node = node->nxt;
}
cout<<node->ch;
getchar();
return 0;
}
Whereas I implemented the solution using memmove, ie shifting the
entire string when the character to be eliminated is encountered. Here
is my effort:
#include <stdio.h>
#include <string.h>
const char chUpper = ''S'' ;
const char chLower = ''s'' ;
void remove_s( char tmp[] )
{
while( *tmp != ''\0'' )
{
if( *tmp == chLower || *tmp == chUpper )
{
memmove( tmp, tmp + 1, &tmp[strlen( tmp )] - tmp ) ;
}
else
{
tmp++ ;
}
}
}
int main( )
{
char str[] = " Asser is an asser and nothing but asser, so be
solemsn " ;
printf( "\nThe old string: %s", str ) ;
remove_s( str ) ;
printf( "\nThe new string: %s", str ) ;
getchar( ) ;
return (0);
}
Now the problem is, we can''t get to decide which piece of code is more
computationally expensive and would start giving problems as the length
of the string increases.....
Your expert views or any other efficient implementation is appreciated.
Also it would be really nice if you could point out the problem areas
in mine or his code....
Thanks again...
ge**************@gmail.com wrote:Hello there my friends, this is my first attempt at posting in a
newsgroup. Here is my problem statement:
Me and my friend decided to solve a programming problem with our own
styles and then decide which one is the best. The problem being:
"Remove all occurrences of a character (case insensitive) from a given
string"
eg.
i/p: She will be a massless princess
o/p: he will be a male prince (all occurances of ''s'' removed)
My friend implemented the solution by creating a Linked List of all the
character in which each node holds one character !!! Here is his code:
#include<stdio.h>
# include <iostream>
# include <conio.h>
using namespace std;Please post C++ code to comp.lang.c++. Also read the FAQ for this group
from c-faq.com.
Now the problem is, we can''t get to decide which piece of code is more
computationally expensive and would start giving problems as the length
of the string increases.....Both methods are arguably overkill for the specification as you''ve
stated above.
ge**************@gmail.com writes:
Hello there my friends, this is my first attempt at posting in a
newsgroup.You picked the wrong one. Your programs are written in C++, but
you posted to comp.lang.c. Furthermore, you really have an
algorithms question, but comp.lang.c is not about algorithms.
Me and my friend decided to solve a programming problem with our own
styles and then decide which one is the best. The problem being:
"Remove all occurrences of a character (case insensitive) from a given
string"
eg.
i/p: She will be a massless princess
o/p: he will be a male prince (all occurances of ''s'' removed)
My friend implemented the solution by creating a Linked List of all the
character in which each node holds one character !!! Here is his code:[...]
Whereas I implemented the solution using memmove, ie shifting the
entire string when the character to be eliminated is encountered. Here
is my effort:[...]
Now the problem is, we can''t get to decide which piece of code is more
computationally expensive and would start giving problems as the length
of the string increases.....A linked list solution could take O(N) time and space, but moving
the entire rest of the string around for each "s" encountered
takes O(N**2) time and O(N) space.
Here is a better solution (although I haven''t tested it):
/* Remove all the "s" characters from STRING, in-place. */
void
remove_s (char *string)
{
char *p = string;
do {
if (*string != ''s'')
*p++ = *string;
} while (*string++ != ''\0'');
}
--
"Large amounts of money tend to quench any scruples I might be having."
-- Stephan Wilms
>Santosh wrote:Please post C++ code to comp.lang.c++. Also read the FAQ for this group
from c-faq.com.But since my program was in C I thought this would be a better place.
Don''t you think that if I posted in the comp.langauge.c++ group, they
would say the same thing to me since my code in in C and my friends in
C++ ?
Ben Pfaff wrote:You picked the wrong one. Your programs are written in C++, but
you posted to comp.lang.c. Furthermore, you really have an
algorithms question, but comp.lang.c is not about algorithms.Is there any algorithms newsgroup ? BTW my code is in C and my friends
in C++.
A linked list solution could take O(N) time and space, but moving
the entire rest of the string around for each "s" encountered
takes O(N**2) time and O(N) space.So I guess it means that the memmove is after all more expensive than
the Linked List one...But I thought the memmove in C was implemented in
Assembly and moving around chunks of raw data would be as fast as it
got in C ?
这篇关于Memmove v / s链接列表实施的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
