リストの削除について

質問

以下のようなプログラムを作ったのですが、このプログラムに削除をする関数を加えたいです。
たとえば削除する値２と入力した場合
1 3 7 8 9 15 19 20と表示させたいのですがどのように行えばよいでしょうか？
自分が作った削除の関数だとうまくできませんでした。どうしたらよいのでしょうか？
よろしくお願いします。

#include<stdio.h>
#define NUM 12
typedef struct{
int IntData;
int NextIndex;
} MyList;

void ShowList(MyList data[]);
int DeleteALL(int value,MyList data[]);
int main(void)
{
int i;
int datano=NUM;
int dt[NUM]={1,2,2,3,2,7,8,9,15,19,20,2};
int del=0,temp=0,del=0;
char sentaku[3];

MyList data[NUM];

for(i=0;i<datano;i++){
data[i].IntData=dt[i];
data[i].NextIndex=i+1;
}
data[NUM-1].NextIndex=-1;
ShowList(data);

while(1){
printf("選択(削除=v, 編集終了=q):");
scanf("%s",sentaku);

if(sentaku[0]=='v'){
printf("削除する値:");
scanf("%d",&del);
temp=DeleteALL(del,data)
printf("%d つのノードを削除しました\n",temp);
ShowList(data);
}
else if(sentaku[0]=='q'){
return 0;
}
else{puts("もう一度入力");}

}
}
void ShowList(MyList data[])//表示する関数
{
int i=0;

printf("リスト: ");
while(i!=-1){
printf("%d ",data[i].IntData);
i=data[i].NextIndex;
}
printf("\n");
}
/* 以下自分が作った削除の関数 */
int DeleteALL(int value,MyList data[])
{
int i=0,dn=0,count=1;
while(data[i].NextIndex!=-1){
i=data[i].NextIndex;
dn++;
}
for(i=0;i<dn;i++){
if(value==data[i].IntData){
count++;
data[i-1].NextIndex=data[i].NextIndex;
data[i].NextIndex=-1;
}
return count;
}

回答No.7

asuncion

>>countは削除した数ですので問題はありません。
>とありますが、DeleteALL()関数開始時点ではまだ一つの要素も削除し
>ていないはずですので、いきなり1が入るのは問題ではないでしょう
>か？

そうです。大問題です。
削除した数である以上、初期値は「ゼロ」に決まっていますね。

お礼

ご指摘頂いた通りでした。ありがとうございます。

回答No.6

redfox63

データの持ち方がまずいと思います
削除データをNextIndexを-にする
データの最後に最後を示すダミーのデータを置く
としておいた方がいいように思います

現状の-1を削除データとした場合 先頭のデータ『1』を削除すると
ShowListでは何も表示できなくなります

#5氏の回答にある
data[i-1].NextIndex=data[i].NextIndex
の部分も i-1が -1になってしまい構造体配列以外のデータを書き換えようとします

回答No.5

E-Yu

DeleteALL()関数にバグがあるようです。

まず一点。
int count=1;
>countは削除した数ですので問題はありません。
とありますが、DeleteALL()関数開始時点ではまだ一つの要素も削除していないはずですので、いきなり1が入るのは問題ではないでしょうか？

>while(data[i].NextIndex!=-1){
>i=data[i].NextIndex;
>dn++;
>}
で「data[i].NextIndex != -1」であったとき、最後のdata[i]の数がカウントされていないのではないでしょうか？

そして最後の一点。これは一目見て「ん？これで大丈夫なのか？」と思った点です。
DeleteALL()関数のfor文中の
>data[i-1].NextIndex=data[i].NextIndex;
の部分です。
i-1というのが非常に危険な匂いを醸し出しています。今回のバグの大きな原因はここにあります。

削除要素が2個並んでいた場合、2回目の
>data[i-1].NextIndex=data[i].NextIndex;
で問題が発生します。
リスト上一つ前の要素ではなく、削除した要素を書き換えてしまっているためです。

流れ的にはこんな感じ？
値　　　　　　　　　　１，２，２
次へのインデックス　　１，２、－１
　　　↓　1つ目の２を削除
値　　　　　　　　　　１，２，２
次へのインデックス　　２、２、－１
　　　↓　2つ目の２を削除
値　　　　　　　　　　１，２，２
次へのインデックス　　２、－１、－１

一度DeleteALL()関数実行中に 実行経過を出力してみてはいかがでしょうか？デバッガが使えるのであれば、そちらで確認するのもいいと思います。

お礼

回答ありがとうございます。
私の作った関数だと削除するノードが２つ続いていない場合は問題は無かったのですが（ご指摘頂いたcount以外）
連続した場合に結果がおかしくなってしまいます。

回答No.4

yaemon_2006

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

typedef struct list{
int v;
struct list *next;
} LIST;

int dela(int *a, int n, int m)
{
int i, j;

for(i = j = 0; i < n; i ++){
a[j] = a[i];
if(a[j] != m) j ++;
}
return n - j;
}

void showa(int *a, int n)
{
int i;

for(i = 0; i < n; i ++) printf("%d ", a[i]);
putchar('\n');
}

void freelist(LIST *l)
{
LIST *p;

for(p = l; p; p = l){
l = l->next;
free(p);
}
}

int makelist(LIST **l, int *a, int n)
{
LIST *p;
int i;

*l = NULL;
for(i = 0; i < n; i ++){
if((p = malloc(sizeof(LIST))) == NULL){
freelist(*l);
return 0;
}
p->v = a[i];
p->next = *l;
*l = p;
}
return 1;
}

int dell(LIST **l, int n)
{
LIST h, *p = &h, *q;
int i = 0;

for(h.next = *l; p->next; ){
if(p->next->v == n){
q = p->next;
p->next = p->next->next;
free(q);
i ++;
}
else p = p->next;
}
*l = h.next;
return i;
}

void showl(LIST *l)
{
if(!l) return;
showl(l->next);
printf("%d ", l->v);
}

int main(void)
{
LIST *l;
int a[12] = {1, 2, 2, 3, 2, 7, 8, 9, 15, 19, 20, 2};
int n = 12, m;

/* リスト */
makelist(&l, a, n);
showl(l);
m = dell(&l, 2);
printf("\n%d\n", m);
showl(l);
freelist(l);
putchar('\n');
/* 配列 */
showa(a, n);
m = dela(a, n, 2);
printf("%d\n", m);
showa(a, n - m);
return 0;
}

お礼

回答ありがとうございます。
参考書などを読んでポインタを使えばできるということは分かっているのですが、どうしても配列のみで表現したいのです。
ご回答頂いた関数dellは配列で表すとどのようになるのでしょうか？
よろしくお願いします。

回答No.3

crew21

質問者さんの話は、（本当の意味の）削除ではなく、番号を飛ばして表示するようなものですよね。

だとすると（コンパイルしてないから細かな文法エラーは出るかもしれんがそれは勘弁してもらうとして）

void tobashi2(MyList dat[])
{
for(int i=0; i<NUM; i++ ) {
if(dat[i].IntData != 2 ) {
printf("%d ", dat[i]);
}
}
}
みたいなのでは、ダメなのん？

補足

ご回答ありがとうございます。NextIndexを変えることによってデータを表示させなくするということです。

回答No.2

asuncion

さしあたり、DeleteALL関数で、
　・countの初期値は1でよいでしょうか？
　・dnの値は正しいですか？

補足

countは削除した数ですので問題はありません。
dnの値も11と12とした場合どちらも結果が同じでした。
私自身では
data[i-1].NextIndex=data[i].NextIndex;
data[i].NextIndex=-1;
この部分が何か間違っていることは分かっているのですが、どうした良いのかがわからない状態です。

回答No.1

asuncion

提示されたコードをそのままコンパイルしようとすると、エラーが出ます。
さしあたり、コンパイルエラーが出ないコードを
提示してくださいますか？

補足

すみませんでした。以下のプログラムでコンパイルエラーは出ないはずです。よろしくお願いします。
#include<stdio.h>
#define NUM 12
typedef struct{
int IntData;
int NextIndex;
} MyList;

void ShowList(MyList data[]);
int DeleteALL(int value,MyList data[]);
int main(void)
{
int i;
int datano=NUM;
int dt[NUM]={1,2,2,3,2,7,8,9,15,19,20,2};
int del=0,temp=0;
char sentaku[3];

MyList data[NUM];

for(i=0;i<datano;i++){
data[i].IntData=dt[i];
data[i].NextIndex=i+1;
}
data[NUM-1].NextIndex=-1;
ShowList(data);

while(1){
printf("選択(削除=v, 編集終了=q):");
scanf("%s",sentaku);

if(sentaku[0]=='v'){
printf("削除する値:");
scanf("%d",&del);
temp=DeleteALL(del,data);
printf("%d つのノードを削除しました\n",temp);
ShowList(data);
}
else if(sentaku[0]=='q'){
return 0;
}
else{puts("もう一度入力");}

}
}
void ShowList(MyList data[])//表示する関数
{
int i=0;

printf("リスト: ");
while(i!=-1){
printf("%d ",data[i].IntData);
i=data[i].NextIndex;
}
printf("\n");
}
/* 以下自分が作った削除の関数 */
int DeleteALL(int value,MyList data[])
{
int i=0,dn=0,count=1;
while(data[i].NextIndex!=-1){
i=data[i].NextIndex;
dn++;
}
for(i=0;i<dn;i++){
if(value==data[i].IntData){
count++;
data[i-1].NextIndex=data[i].NextIndex;
data[i].NextIndex=-1;
}}
return count;
}