학교 시험문제인데요~ 화가 날려고 그래요. 링크리스트 문젝인데

ins878의 이미지

이 문제는 이프레스에서 발간한 자료구조 책의 문제입니다.(오용철 님)이 쓰신거구요~ 아래 이 문제가 시험에 나온다고 하는데~ 풀어보면 풀어 볼 수록 씅질만 나고, 도저히 해독이 안됩니다. 이 문제가 가능한 문제인지~ 고수님들 한번 바주세요

문제 : 다음과 같은 코드가 주어졌을 때 다음 함수를 호출한 후의 결과를 써라.

(void)zap (&head, head); 

struct node 
{ 
	int data; 
	struct node *next; 
}; 

void zaptest() 
{ 
	struct node *head, a1, a2, a3, a4; 
	head = &a1; 
	a1.data = 1; 
	a2.data = 2; 
	a3.data = 3; 
	a4.data = 4; 
	(void)zap(&head, head); 
} 

zap()은 다음과 같이 정의한다.

struct node *zap(struct node **head, struct node *ptr) 
{ 
	struct node *tmp; 

	if(ptr->next == NULL) 
	{ 
		*head = ptr; 
	} 
	else 
	{ 
		tmp = zap(head, ptr->next); 
		tmp->next = ptr; 
		ptr->next = NULL; 
	} 
	return(ptr); 
} 

이것이 문제인데요~ 제가 교수님 이상합니다. (void)zap() 함수는 리턴값이 없고, zap()도 함수가 아니고, 구조체인데요~ 라고 했더니, 리턴값이 있으면 받고 없으면 안받으면 된다고 하더군요~. 제가 봤을 때는 링크리스트를 재귀호출을 사용하여 구현한 것 같은데~ 이 소스코드를 보고는 도저히 결과값이 무엇이 나올지 판단이 되질 않습니다. 제가 판단했을땐 오류만 무지하게 나오는 것 같은데, 답은 없고~ 휴~ 이 소스코드가 뭘 의미하는지, 결과 값이 무엇인지~ 고수님들 해결 부탁드립니다.~ (T.T 머리에서 스팀 열이 점점 가열되고 있습니다.)

dragonkun의 이미지

Quote:
리턴값이 없고, zap()도 함수가 아니고, 구조체인데요~ 라고 했더니,

고수는 아니지만 제 생각엔....;
struct node *zap(struct node **head, struct node *ptr)
zap()은 리턴 타입이 struct node* 인 함수입니다만..;;
Quote:
제가 판단했을땐 오류만 무지하게 나오는 것 같은데

문법상으로 아무런 하자는 없어보입니다..;
짧은 소견으로는..
1) 아무일도 일어나지 않는다..
2) 런타임 에러(세그멘테이션 폴트)가 일어난다..
중 하나일 듯 합니다만..;
struct node *head만 했을때..
next 멤버에 NULL이 들어가면 1번.
쓰레기 값이 들어가 있으면 2번..일 듯 하군요..
왠지 2번의 상황이지 않을까 싶군요..

Emerging the World!

bw001730의 이미지

재귀루프돌면서
첫번째는 if문에 걸릴테고
나머지는 else 문에 걸리겠죠
문제 업어보이는데요

(void)zap (&head, head);

이부분은..저도 썬사의 매뉴얼에 있는 소스에
이런식으로 많이 나와있어서 어디선가 찾아보았는데요
제가 어디서 줏어듣기로.. 이렇습니다.
zap() 함수가 리턴할때 리턴값을 어딘가에 저장을 할 것입니다.
kkk = zap() ;
이런식의 호출은 저장된 리턴값을 얻게 되겠지만
그냥 zap() 라고만 호출하면 저장된 리턴값은 버려지게 됩니다.
연산의 낭비죠..
근데 (void)zap() 하면 컴파일러에게
리턴값을 저장하지 않아도 된다고 알려주는 것이죠..

썬사에서 이렇게 된 예제함수들이 많드라구요..

오래전에 읽어서 잘 기억이 안나는데
더 자세히 아시는 분들 리플좀~~

cdpark의 이미지

a1.next = &a2;
a2.next = &a3;
a3.next = &a4;
a4.next = NULL;

정도만 문제에 추가되어 있다면 zap은 linked list를 "뒤집는" 함수로 보이네요.

ins878 님의 의문사항은.. C 언어 문법책을 읽어보면 답이 나옵니다. :(

vuccell의 이미지

typedef u_int (unsigned int);
typedef struct tagA
{
    int a;
} CA;

위의 두코드 모두 보셨을것입니다.
typedef이란 alias개념인데요... 두번째는 { }로 묶인것까지를 CA로 alias한것이죠...

근데 소스에는 'CA'에 해당하는 것이 없습니다.
이럴때 struct tagA를 그대로 사용할수 있습니다.(tagA만 쓰면 안되고요)

struct node 
{ 
   int data; 
   struct node *next; 
} Cnode; 

Cnode * zap( blah~)

와 같은 것입니다. 교수님께서 좀 한심하게 생각했을듯..(흐.. 죄송)

void형은 return형이 없는것이죠... 즉 어떤것이 리턴값이 모를때 혹은 함수포인터를 쓸때 사용합니다.
지금같은 경우는 return형이 struct node *이니까.. void형이라 해도 마찬가지죠...

이문제는 head가 a1의 번지를 알고 있고, a1의 next는 선언되어 있지 않으니 그냥 a1이 return됨

a1의 next를 a2의번지, a2의 next를 a3의번지 등으로 세팅하고, 돌리면 마지막 놈이 튀어나오죠....

익명 사용자의 이미지

위에 cdpark님 말씀대로 zap은 링크드 리스트를 뒤집는 함수입니다.

잘 이해가 안되시면 직접 종이에 써가면서 손으로 시뮬레이션 해보세요.

저런식으로 재귀를 쓰는 함수같은걸 이해하는 좋은 방법은 먼저

아무래도 코드를 보고 감이 잡히지 않는다면 손으로 직접 시뮬레이션 해보는게 좋겠죠.

그리고 나서 '어떠어떠한 일을 하는 것이다'라고 감이 잡히면

수학적 귀납법을 써서 대충 증명해 보시면 됩니다.

struct node *zap(struct node **head, struct node *ptr) 
{ 
   struct node *tmp; 

   if(ptr->next == NULL) 
   { 
      *head = ptr; 
   } 
   else 
   { 
      tmp = zap(head, ptr->next); 
      tmp->next = ptr; 
      ptr->next = NULL; 
   } 
   return(ptr); 
} 

"위 코드는 리스트를 뒤집는 일을 하여 *head는 그 뒤집힌 리스트의 처음을 가리키게 되며 리턴값은 ptr인자값 그대로이다"라는 것은

다음과 같이 증명이 됩니다:

(1) 길이 1짜리 리스트가 ptr로 넘어온 경우
ptr->next가 NULL이 될테니 if문에서 걸려서 *head는 ptr를 가리키게 됨.
리턴값은 ptr

(2) 길이 2이상인 리스트가 ptr로 넘어온 경우
ptr->next가 NULL이 아니므로 else부분이 실행됩니다.
tmp = zap(head,ptr->next)는 위의 가정에 의해
ptr바로 뒤의 리스트는 뒤집히게 되며
*head는 뒤집힌 리스트의 처음을 가리키고
tmp는 함수호출전의 ptr->next값을 가지게 됩니다.
즉 tmp는 원래 리스트에서 ptr의 바로 다음 원소를 가리키죠.
다시 말하면 tmp는 뒤집힌 리스트의 맨 마지막 원소를 가리킵니다.
이제 tmp->next = ptr과 ptr->next = NULL에 의해서
뒤집힌 리스트의 맨 끝에 ptr이 추가됩니다.
리턴값은 역시 ptr입니다.

확신이 서지 않을 때는 위와같이 증명해 보는게 좋습니다.

물론 혼자 이해할 때는 저렇게 주저리주저리 쓸 필요는 없겠죠.

익명 사용자의 이미지

아 그리고 함수호출 앞에 (void)를 붙인 것은

그 리턴값의 타입을 void로 캐스팅하는 것으로

단지 그 함수가 원래는 어떠한 값을 리턴한다는 것을 사용자에게 강조하기 위해서 입니다.

즉 없어도 되고 있어도 되는 거죠.

bw001730의 이미지

단순 가독성을 위해 함수호출앞에 (void)를 붙인다구요? 사실인가요? 내가 잘못알고 있었나 -_-;

익명 사용자의 이미지

Anonymous wrote:
아 그리고 함수호출 앞에 (void)를 붙인 것은

그 리턴값의 타입을 void로 캐스팅하는 것으로

단지 그 함수가 원래는 어떠한 값을 리턴한다는 것을 사용자에게 강조하기 위해서 입니다.

즉 없어도 되고 있어도 되는 거죠.


그렇게 해석할 수도 있겠지만, 리턴되는 값을 무시하겠다는 것을 명시적으로 표현한다는 해석이 더 적절할 것같습니다.
또한 리턴되는 값이 다른 변수에 대입되지 않을 때(즉, lvalue가 없을 때)에 경고를 내는 컴파일러들이 있기 때문이라고 해석해도 되겠구요.
익명 사용자의 이미지

(void)printf("hello world\n"); 이 유형과, 아래...

printf("hello world\n"); 이 유형에 대해서도 고민해 보신적 있습니까?

doldori의 이미지

Anonymous wrote:
(void)printf("hello world\n");
이 유형과, 아래...

printf("hello world\n"); 이 유형에 대해서도 고민해 보신적 있습니까?

Good point! :)
irondog의 이미지

문제를 내다가 만것 같은데요. -.-;;
리스트를 만들려고 *head, a1, a2 ... 를 선언한것 같은데, 로컬 변수이기 때문에 스택에 위치해 있을 것이고
초기화도 안되어 있기 때문에 스트럭처 내부의next변수에 쓰레기 값이 들어 가거든요.

위에서 말씀하신데로 어쩔때는 아무일 없거나 또 어떤 경우에는 한없이 돌다가 엄한 메모리 접근해서 죽어버릴 것 같네요.

pjs0919의 이미지

#include <stdio.h> 

typedef struct tag_node 
{ 
   int data; 
   tag_node *next; 
} node; 
typedef node* ptrnode; 

ptrnode zap(ptrnode, ptrnode); 
void zaptest(void); 

int main(void) 
{ 
   zaptest(); 
      return 0; 
} 


void zaptest(void) 
{ 
   ptrnode head; 
   node a1, a2, a3, a4; 
   head = &a1; 
   a1.data = 1; 
   a1.next = &a2; 

   a2.data = 2; 
   a2.next = &a3; 

   a3.data = 3; 
   a3.next = &a4; 

   a4.data = 4; 
   a4.next = NULL; 

   zap(head, head); 
} 


ptrnode zap(ptrnode head, ptrnode ptr) 
{ 
   ptrnode tmp; 
   if(ptr->next == NULL) 
      head = ptr; 
   else 
   { 
      tmp = zap(head, ptr->next); 

      tmp->next = ptr; 
      ptr->next = NULL; 
   } 
   printf("%d\n",ptr->data); 
   return ptr; 
} 

"이형채"님이 수정하여 주셨습니다.^^;;

처음에 올리신 소스코드도 문제가 있구요, ..내용도 별로 않좋군요

\(´∇`)ノ.大韓兒 朴鐘緖人

ins878의 이미지

저도 이 문제를 보면서~ 분명히 링크리스트를 표현하기 위한 것 같은데, 소스코드를 보고는 도저히 답이 않나왔습니다. 함수를 호출을 하면, a1,a2,a3... 서로가 연결이 되어야 하는데, 이 소스에서는 전혀 연결고리를 찾을 수가 없으니깐요~ 이문제는, 이 소스코드중 잘 못된 곳을 찾아서 고치는 문제가 아닌, 결과값이 무엇이 출력될 것인가 입니다. 그러면, 답은 쓰레기 값인가요? 아니면 함수 마지막에 ptr을 리턴하는 것이기때문에, a1을 넣으면, 그냥 a1의 값인가요? 아니면 오류라고 해야 하는지~ 휴~ T.T
어떻게 이런 문제가 나올 수가 있는지 답답합니다.

익명 사용자의 이미지

Quote:
문제 : 다음과 같은 코드가 주어졌을 때 다음 함수를 호출한 후의 결과를 써라.

몇대의 컴퓨터에서 100번정도 실행한 후 에 결과를 평균해서 보여주심이..

프로그램 계속 죽을것 같은데요 :)

사회생활을 미리시킬려는 것일까요 :)

ins878의 이미지

오늘 학교 시험인데요~ 알고리즘 필기시험요~
이거 답을 오류가 난다고 써야하나~ 아니면, 내 나름데로 수정을 해서 답을써야 하는지~ㅋㅋㅋㅋ
이런 작은 문제까지 신경써주시는 고수님들 정말로 감사드립니다.
저도 열심히해서 고수의 길을 걷도록 노력하겠습니다.
감사합니다.

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.