| カーソル版の線形リストに対して、すべての重複ノード（番号と氏名の両方が一致するノード）を削除する以下の関数を作成せよ。 void Purge (List *list); ※ 本問は、前節の内容に関する演習問題である。 |
/* 演習9-4 カーソルを用いた線形リストの実現例 */ #include <stdio.h> #include <stdlib.h> #include <string.h> #define NO 1 /* 番号（入力・探索用）*/ #define NAME 2 /* 氏名（入力・探索用）*/ #define Null -1 /* 空カーソル */ /*--- メニュー ---*/ typedef enum { Term, InsFront, InsRear, RmvFront, RmvRear, PrintCrnt, RmvCrnt, SrchNo, SrchName, PrintAll, Clear, Prg } Menu; /*--- 会員データ ---*/ typedef struct { int no; /* 番号 */ char name[10]; /* 氏名 */ } Data; typedef int Index; /* カーソル型 */ /*--- ノード ---*/ typedef struct { Data data; /* データ */ Index next; /* 後続ノード */ Index Dnext; /* フリーリストの後続ノード */ } Node; /*--- 線形リスト ---*/ typedef struct { Node *n; /* リスト本体（配列） */ Index head; /* 先頭ノード */ Index max; /* 利用中の末尾レコード */ Index deleted; /* フリーリストの先頭ノード */ Index crnt; /* 着目ノード */ } List; /*--- データの番号が一致するか（探索用関数） ---*/ int NoEqual(Data x, Data y) { return (x.no == y.no); } /*--- データの氏名が一致するか（探索用関数） ---*/ int NameEqual(Data x, Data y) { return (strcmp(x.name, y.name) == 0); } /*--- ノードの各メンバに値を設定 ----*/ void SetNode(Node *n, Data x, Index next) { n->data = x; /* 番号 */ n->next = next; /* 氏名 */ } /*--- 線形リストを初期化（最大要素数はsize） ---*/ void InitList(List *list, int size) { list->n = (Node *)calloc(size, sizeof(Node)); list->head = Null; /* 先頭ノード */ list->crnt = Null; /* 着目ノード */ list->max = Null; list->deleted = Null; } /*--- 挿入するレコードのインデックスを求める ---*/ Index GetIndex(List *list) { if (list->deleted == Null) /* 削除レコードがない場合 */ return (++(list->max)); else { Index rec = list->deleted; list->deleted = list->n[rec].Dnext; return (rec); } } /*--- 指定したレコードを削除リストに登録する ---*/ void DeleteIndex(List *list, Index idx) { if (list->deleted == Null) { /* 削除レコードがない場合 */ list->deleted = idx; list->n[idx].Dnext = Null; } else { Index ptr = list->deleted; list->deleted = idx; list->n[idx].Dnext = ptr; } } /*--- 先頭にノードを挿入 ---*/ void InsertFront(List *list, Data x) { Index ptr = list->head; list->head = list->crnt = GetIndex(list); SetNode(&list->n[list->head], x, ptr); } /*--- 末尾にノードを挿入 ---*/ void InsertRear(List *list, Data x) { if (list->head == Null) /* 空であれば */ InsertFront(list, x); /* 先頭に挿入 */ else { Index ptr = list->head; while (list->n[ptr].next != Null) ptr = list->n[ptr].next; list->n[ptr].next = list->crnt = GetIndex(list); SetNode(&list->n[list->n[ptr].next], x, Null); } } /*--- 先頭ノードを削除 ---*/ void RemoveFront(List *list) { if (list->head != Null) { Index ptr = list->n[list->head].next; DeleteIndex(list, list->head); list->head = list->crnt = ptr; } } /*--- 末尾ノードを削除 ---*/ void RemoveRear(List *list) { if (list->head != Null) { if (list->n[list->head].next == Null) /* ノードが一つだけであれば */ RemoveFront(list); /* 先頭ノードを削除 */ else { Index ptr = list->head; Index pre; while (list->n[ptr].next != Null) { pre = ptr; ptr = list->n[ptr].next; } list->n[pre].next = Null; DeleteIndex(list, ptr); list->crnt = pre; } } } /*--- 着目ノードを削除 ---*/ void RemoveCrnt(List *list) { if (list->head != Null) { if (list->crnt == list->head) /* 先頭ノードに着目していれば */ RemoveFront(list); /* 先頭ノードを削除 */ else { Index ptr = list->head; while (list->n[ptr].next != list->crnt) ptr = list->n[ptr].next; list->n[ptr].next = list->n[list->crnt].next; DeleteIndex(list, list->crnt); list->crnt = ptr; } } } /*--- 重複ノードを削除 ---*/ void Purge(List *list) { Index ptr = list->head; while (ptr != Null) { Index ptr2 = ptr; Index pre = ptr; while (list->n[ptr2].next != Null) { ptr2 = list->n[pre].next; if (list->n[ptr].data.no == list->n[ptr2].data.no && !strcmp(list->n[ptr].data.name, list->n[ptr2].data.name)) { list->n[pre].next = list->n[ptr2].next; DeleteIndex(list, ptr2); } else { pre = ptr2; } } ptr = list->n[ptr].next; } list->crnt = list->head; } /*--- 全ノードを削除 ---*/ void ClearList(List *list) { while (list->head != Null) /* 空になるまで */ RemoveFront(list); /* 先頭ノードを削除 */ list->crnt = Null; } /*--- 関数equalによってxと一致するノードを探索 ---*/ Index SearchNode(List *list, Data x, int equal(Data x, Data y)) { Index ptr = list->head; while (ptr != Null) { if (equal(list->n[ptr].data, x)) { list->crnt = ptr; return (ptr); /* 探索成功 */ } ptr = list->n[ptr].next; } return (Null); /* 探索失敗 */ } /*--- 線形リストの使用を終了 ---*/ void TermList(List *list) { ClearList(list); /* 全ノードを削除 */ free(list->n); } /*--- データの番号と氏名を表示 ---*/ void PrintData(Data x) { printf("番号：%d 氏名：%s\n", x.no, x.name); } /*--- 着目ノードのデータを表示 ---*/ void PrintCrntNode(const List *list) { if (list->crnt == Null) puts("着目要素はありません。"); else PrintData(list->n[list->crnt].data); } /*--- 全ノードのデータを表示 ---*/ void PrintList(const List *list) { if (list->head == Null) puts("ノードがありません。"); else { Index ptr = list->head; puts("【一覧表】"); while (ptr != Null) { PrintData(list->n[ptr].data); ptr = list->n[ptr].next; /* 後続ノード */ } } } /*--- データの入力 ---*/ Data Read(const char *message, int sw) { Data temp; printf("%sするデータを入力してください。\n", message); if (sw & NO) { printf("番号："); scanf("%d", &temp.no); } if (sw & NAME) { printf("名前："); scanf("%s", temp.name); } return (temp); } /*--- メニュー選択 ---*/ Menu SelectMenu(void) { int i, ch; char *mstring[] = { "先頭にノードを挿入", "末尾にノードを挿入", "先頭のノードを削除", "末尾のノードを削除", "着目ノードを表示", "着目ノードを削除", "番号で探索", "氏名で探索", "全ノードを表示", "全ノードを削除", "重複ノードを削除" }; do { for (i = Term; i < Prg; i++) { printf("(%2d) %-18.18s ", i + 1, mstring[i]); if ((i % 3) == 2) putchar('\n'); } printf("( 0) 終了 ："); scanf("%d", &ch); } while (ch < Term || ch > Prg); return ((Menu)ch); } /*--- メイン ---*/ int main(void) { Menu menu; List list; InitList(&list, 100); /* 線形リストの初期化 */ do { Data x; switch (menu = SelectMenu()) { case InsFront : x = Read("先頭に挿入", NO | NAME); InsertFront(&list, x); break; case InsRear : x = Read("末尾に挿入", NO | NAME); InsertRear(&list, x); break; case RmvFront : RemoveFront(&list); break; case RmvRear : RemoveRear(&list); break; case PrintCrnt : PrintCrntNode(&list); break; case RmvCrnt : RemoveCrnt(&list); break; case SrchNo : x = Read("探索", NO); if (SearchNode(&list, x, NoEqual) != Null) PrintCrntNode(&list); break; case SrchName : x = Read("探索", NAME); if (SearchNode(&list, x, NameEqual) != Null) PrintCrntNode(&list); break; case PrintAll : PrintList(&list); break; case Clear : ClearList(&list); break; case Prg : Purge(&list); break; } } while (menu != Term); TermList(&list); /* 線形リストの後始末 */ return (0); }
