| p が指すノードの直前にノードを挿入する関数 void InsertBefore (Dlist *list , Dnode *p , Data x ); を作成せよ。 |
/* 演習9-7 循環・重連結リストの実現例 */ #include <stdio.h> #include <stdlib.h> #include <string.h> #define NO 1 /* 番号（入力・探索用）*/ #define NAME 2 /* 氏名（入力・探索用）*/ /*--- メニュー ---*/ typedef enum { Term, InsFront, InsRear, RmvFront, RmvRear, PrintCrnt, InsCBefore, InsCAfter, RmvCrnt, SrchNo, SrchName, PrintAll, Clear } Menu; /*--- 会員データ ---*/ typedef struct { int no; /* 番号 */ char name[10]; /* 氏名 */ } Data; /*--- ノード ---*/ typedef struct __node { Data data; /* データ */ struct __node *prev; /* 先行ノードへのポインタ */ struct __node *next; /* 後続ノードへのポインタ */ } Dnode; /*--- 循環・重連結リスト ---*/ typedef struct { Dnode *head; /* 先頭ダミーノードへのポインタ */ Dnode *crnt; /* 着目ノードへのポインタ */ } Dlist; /*--- 一つのノードを動的に確保 ---*/ Dnode *AllocDnode(void) { return ((Dnode *)calloc(1, sizeof(Dnode))); } /*--- リストを初期化 ---*/ void InitDlist(Dlist *list) { Dnode *dummyNode = AllocDnode(); /* ダミーノードを生成 */ list->head = list->crnt = dummyNode; dummyNode->prev = dummyNode->next = dummyNode; } /*--- ノードの各メンバに値を設定 ----*/ void SetDnode(Dnode *n, Data x, Dnode *prev, Dnode *next) { n->data = x; /* データ */ n->prev = prev; /* 先行ノードへのポインタ */ n->next = next; /* 後続ノードへのポインタ */ } /*--- リストは空か ---*/ int isEmptyDlist(Dlist *list) { return ((list->head)->next == list->head); } /*--- データの番号が一致するか（探索用関数） ---*/ int NoEqual(Data x, Data y) { return (x.no == y.no); } /*--- データの氏名が一致するか（探索用関数） ---*/ int NameEqual(Data x, Data y) { return (strcmp(x.name, y.name) == 0); } /*--- 関数equalによってxと一致するノードを探索 ---*/ Dnode *SearchNode(Dlist *list, Data x, int equal(Data x, Data y)) { Dnode *ptr = (list->head)->next; while (ptr != list->head) { if (equal(ptr->data, x)) { list->crnt = ptr; return (ptr); /* 探索成功 */ } ptr = ptr->next; } return (NULL); /* 探索失敗 */ } /*--- データの番号と氏名を表示 ---*/ void PrintData(Data x) { printf("番号：%d 氏名：%s\n", x.no, x.name); } /*--- 着目ノードのデータを表示 ---*/ void PrintCrntDnode(Dlist *list) { if (isEmptyDlist(list)) puts("着目要素はありません。"); else PrintData(list->crnt->data); } /*--- 全ノードのデータを表示 ---*/ void PrintDlist(Dlist *list) { if (isEmptyDlist(list)) puts("ノードがありません。"); else { Dnode *ptr = (list->head)->next; puts("【一覧表】"); while (ptr != list->head) { PrintData(ptr->data); ptr = ptr->next; /* 後続ノードに着目 */ } } } /*--- pが指すノードの直後にノードを挿入 ---*/ void InsertAfter(Dlist *list, Dnode *p, Data x) { Dnode *ptr = AllocDnode(); Dnode *nxt = p->next; p->next = (p->next)->prev = ptr; SetDnode(ptr, x, p, nxt); list->crnt = ptr; /* 挿入したノードに着目 */ } /*--- pが指すノードの直前にノードを挿入 ---*/ void InsertBefore(Dlist *list, Dnode *p, Data x) { Dnode *ptr = AllocDnode(); Dnode *prv = p->prev; p->prev = (p->prev)->next = ptr; SetDnode(ptr, x, prv, p); list->crnt = ptr; /* 挿入したノードに着目 */ } /*--- 先頭にノードを挿入 ---*/ void InsertFront(Dlist *list, Data x) { InsertAfter(list, list->head, x); } /*--- 末尾にノードを挿入 ---*/ void InsertRear(Dlist *list, Data x) { InsertAfter(list, (list->head)->prev, x); } /*--- pが指すノードを削除 ---*/ void RemoveNode(Dlist *list, Dnode *p) { (p->prev)->next = p->next; (p->next)->prev = p->prev; list->crnt = p->prev; /* 削除したノードの先行ノードに着目 */ free(p); } /*--- 先頭ノードを削除 ---*/ void RemoveFront(Dlist *list) { if (!isEmptyDlist(list)) RemoveNode(list, (list->head)->next); } /*--- 末尾ノードを削除 ---*/ void RemoveRear(Dlist *list) { if (!isEmptyDlist(list)) RemoveNode(list, (list->head)->prev); } /*--- 着目ノードを削除 ---*/ void RemoveCrnt(Dlist *list) { if (list->crnt != list->head) RemoveNode(list, list->crnt); } /*--- 全ノードを削除 ---*/ void ClearDlist(Dlist *list) { while (!isEmptyDlist(list)) /* 空になるまで */ RemoveFront(list); /* 先頭ノードを削除 */ } /*--- 線形リストの後始末 ---*/ void TermDlist(Dlist *list) { ClearDlist(list); /* 全ノードを削除 */ free(list->head); /* ダミーノードを削除 */ list->head = list->crnt = NULL; } /*--- データの入力 ---*/ 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 < Clear; i++) { printf("(%2d)%-22.22s", i + 1, mstring[i]); if ((i % 3) == 2) putchar('\n'); } printf("( 0) 終了 ："); scanf("%d", &ch); } while (ch < Term || ch > Clear); return ((Menu)ch); } /*--- メイン ---*/ int main(void) { Menu menu; Dlist list; InitDlist(&list); /* リストの初期化 */ 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 : PrintCrntDnode(&list); break; case InsCBefore: x = Read("着目要素の直前に挿入", NO | NAME); InsertBefore(&list, list.crnt, x); break; case InsCAfter : x = Read("着目要素の直前に挿入", NO | NAME); InsertAfter(&list, list.crnt, x); break; case RmvCrnt : RemoveCrnt(&list); break; case SrchNo : x = Read("探索", NO); if (SearchNode(&list, x, NoEqual) != NULL) PrintCrntDnode(&list); break; case SrchName : x = Read("探索", NAME); if (SearchNode(&list, x, NameEqual) != NULL) PrintCrntDnode(&list); break; case PrintAll : PrintDlist(&list); break; case Clear : ClearDlist(&list); break; } } while (menu != Term); TermDlist(&list); /* リストの後始末 */ return (0); }
