線形リスト 途中の挿入と削除

Question

以下の入力による命令が線形リストに反映されるプログラムを作りたいです。

0 :終了
1 :リスト表示
2 num val :リストのnum番目に値valを追加
3 num :リストのnum番目を削除
また、追加と削除に関しては、成功したとき１、失敗したとき０を返すようにする必要があります。

リストの終了（０）、表示（１）、削除（３）はできています。追加が上手くいきません。
追加の命令（2 1 1など）をしたあと、リスト表示を行っても何も表示されませんので、上手く追加ができていないのだと思います。
コードはこちらになります。テンプレートとして用意されたものを使用していますので、私が書いたのはaddNode、deleteNode、showList関数内のみです。今回は追加が上手くいきませんので、addNode関数内のみ見ていただければと思います。
どうぞよろしくお願いいたします。

#include <stdio.h>
#include <stdlib.h>

#define FAIL_RETURN(flg,message) if(!(flg)){printf("%s",message);freeList();exit(1);}

typedef struct LISTNODE {
	int data;
	struct LISTNODE *pNext;
} ListNode;

ListNode rootNode;

int addNode(int num, int val){
	/*write your program.*/
    ListNode *pPrevNode = &rootNode;
    ListNode *pNewNode = (ListNode*)malloc(sizeof(ListNode));
    pNewNode -> data = val;
	pNewNode -> pNext = NULL;

	int Pos=1;
	pPrevNode = pPrevNode -> pNext;
	while(pPrevNode != NULL){
		pPrevNode = pPrevNode -> pNext;
		Pos++;
	}

	pPrevNode = &rootNode;

	if(num <= Pos+1){

    	int pos=1;
    	while(pos<num){
        	pPrevNode = pPrevNode->pNext;
        	pos++;
    }

    	pNewNode -> pNext = pPrevNode->pNext;
    	pPrevNode-> pNext = pNewNode;

		return 1;
	}else
	{
		return 0;
	}
}

int deleteNode(int num){
	/*write your program.*/

	ListNode *nNode = &rootNode;
	int Pos=1;
	nNode = nNode -> pNext;
	while(nNode != NULL){
		nNode = nNode -> pNext;
		Pos++;
	}

	if(num<=Pos){

		Pos=1;
		ListNode *Node = &rootNode;
		/*削除するノードのひとつ前まで進める*/
		while(Pos<num){
			Node = Node->pNext;
			Pos++;
		}


		ListNode *Node2 = &rootNode;
		Pos = 1;
		/*削除するノードまで進める*/
		while(Pos <= num){
			Node2 = Node2->pNext;
			Pos++;
		}

		/*前の要素のpNextに削除される要素のpNextをコピー*/
		Node->pNext = Node2->pNext;

		free(Node2);
		return 1;
	}else
	{
		return 0;
	}
	
	}

void showList(void) {
	/*write your program.*/
    ListNode *Node;
    Node = &rootNode;
	Node = rootNode.pNext;
	if(Node != NULL){
    	if(Node->pNext != NULL){
         printf("%d", Node->data);}
         
    	Node = Node->pNext;
     	while(Node != NULL){
         	printf(" %d", Node->data);
        	Node = Node->pNext;
    	}
    printf("\n");
	}
	
}

void freeList(void) {
	ListNode *currentNode = rootNode.pNext;
	ListNode *tmp;
	
	for (;currentNode != NULL;) {
		tmp = currentNode;
		currentNode = currentNode -> pNext;
		free(tmp);
	}
}


int main(void) {
	int op, num, val;
	char message[256];
	
	rootNode.data = 0;
	rootNode.pNext = NULL;

  
  
  /*addNodeが使えないので確認用
  ListNode node1, node2, node3;
  rootNode.pNext = &node1;
  node1.pNext = &node2;
  node2.pNext = &node3;
  node3.pNext = NULL;
  node1.data = 10;
  node2.data = 20;
  node3.data = 30;*/
	
	while (scanf("%d", &op), op) {
		switch (op) {
			case 1:
				showList();
				break;
			case 2:
				scanf("%d%d", &num, &val);
				sprintf(message, "error in addNode(%d, %d)\n", num, val);
				FAIL_RETURN(addNode(num, val), message)
				break;
			case 3:
				scanf("%d", &num);
				sprintf(message, "error in deleteNode(%d)\n", num);
				FAIL_RETURN(deleteNode(num), message)
				break;
		}
	}
	
	freeList();
	
	return 0;
}

Answer 1

確認に使用している showList が正常に動作致しません.
テストされた形跡がコメントにありますが,「データが1件の場合」に表示されるかをテストされていません.

#include <stdio.h>
#include <stdlib.h>

typedef struct LISTNODE {
    int data;
    struct LISTNODE *pNext;
} ListNode;

ListNode rootNode;

int addNode(int num, int val){
  /*write your program.*/
  ListNode *node, *pNewNode;
  for(node=&rootNode; node!=NULL; node=node->pNext) {
    if(--num == 0) {
      pNewNode = (ListNode *)malloc(sizeof(ListNode));
      pNewNode->data  = val;
      pNewNode->pNext = node->pNext;
      node->pNext = pNewNode;
      return 1;
    }
  }
  return 0;
}

void showList(void) {
  /*write your program.*/
  ListNode *node;
  printf("showList:");
  for(node=rootNode.pNext; node!=NULL; node=node->pNext) {
    printf(" %d", node->data);
  }
  printf("\n");
}

void freeList(void) {
  ListNode *node, *tmp;
  for(node=rootNode.pNext; node!=NULL; ) {
    tmp = node;
    node = node->pNext;
    free(tmp);
  }
}

int main(void) {
  rootNode.data = 0;
  rootNode.pNext = NULL;

  showList();
  printf("addNode: return=%d\n", addNode(1,10));
  showList();
  printf("addNode: return=%d\n", addNode(1,20));
  showList();
  printf("addNode: return=%d\n", addNode(2,30));
  showList();
  printf("addNode: return=%d\n", addNode(5,40));
  showList();

  freeList();

  return 0;
}

showList:
addNode: return=1
showList: 10
addNode: return=1
showList: 20 10
addNode: return=1
showList: 20 30 10
addNode: return=0
showList: 20 30 10

Comments

[ceb]

お返事が遅くなってしまい申し訳ありません。１０　２０　３０の表示ですっかり合っていると思ってしまいました。テストする際にはいくつか条件を変えて行った方がよいと学ぶことができました。ご回答ありがとうございました。

[jimbe]

なお, ご提示のコードでは addNode が 0 を返す場合に malloc した領域が解放されずに残ってしまいます.
挿入が確定してから malloc するか, 0 を返す前に free するようにしてください.

Answer 2

今回は追加が上手くいきませんので、addNode関数内のみ見ていただければ

showList関数の正しさには自信があるということですか?

01:void showList(void) {
02:  /*write your program.*/
03:  ListNode *Node;
04:  Node = &rootNode;
05:  Node = rootNode.pNext;
06:  if (Node != NULL) {
07:    if (Node->pNext != NULL) {
08:      printf("%d", Node->data);
09:    }
10:
11:    Node = Node->pNext;
12:    while (Node != NULL) {
13:      printf(" %d", Node->data);
14:      Node = Node->pNext;
15:    }
16:    printf("\n");
17:  }
18:}

rootの次に一つ要素がある状態を想定すると
root[data,pNext] - node1:[data,NULL]
という状態。

これでshowListに入ると、
05:でnode1へのポインタがNodeに入りますね。
06:は真ですが、
07:のifの条件式はnode1のpNextを検査してNULLですからdataの表示は行われません。
11:でNodeはnode1のpNextすなわちNULLになって以降スキップ。

つまり、

追加の命令（2 1 1など）をしたあと、リスト表示を行っても何も表示されません

ということになります。
もう一個要素を追加すると以降は表示されます。07:のifが余計ですね。
まぁ、言い出すと06:のifと12:のwhileの条件が同じあたり、工夫のしようがあるんじゃないか、とかも思います。

ここはあっているはず、と思うと間違いを見逃します。
(addListとかdeleteListがあっているかはちゃんとは見ていませんが)

Comments

[ceb]

お返事が遅くなってしまい申し訳ありません。
確認用の１０　２０　３０が表示されたので、すっかり合っていると思い込んでしまっていました。教えていただいたことを確認してみると、たしかに…となりました。とても助かりました。ご回答ありがとうございました。