線形リストの途中に新たな要素を指定要素の前に追加します。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 | // 線形リストの作成#include <stdio.h>#include <stdlib.h>struct list { int key; struct list *next;};struct list *get_list(void);void print_list(struct list *p);int get_data(void);void insert_before(struct list *x, struct list *p);#define EOD -1/* 初期データリスト */int a[ ] = { 1, 2, 3, 4, 5, 6, EOD }; int main( ){ struct list *listptr, *new; listptr = get_list( ); print_list( listptr ); new = (struct list *)malloc(sizeof(struct list)); new->key = 888; new->next = NULL; insert_before( new, listptr->next->next ); print_list( listptr ); return 0;}/* 入力データが空になるまでリストを作成 */struct list *get_list( void ) { int d; struct list *p,*newp; p = NULL; // リストの先頭項目を終端するNULLを入れる while( ( d = get_data( ) ) != EOD) {// 一項目分の記憶領域を確保し，その領域へのポインタを返す// (struct list *)はmallocの返すデータの型をlist構造体型の情報にキャスト(変換) newp = (struct list *)malloc(sizeof(struct list)); newp->key = d; // mallocで取得した一項目分の記憶領域にデータを書き込む newp->next = p; // pに保管していた一つ前の項目のアドレス(最初はNULL)をnextアドレスとして書込む p = newp; // 現記憶領域へのポインタをpに保管 print_list( p ); } return p; // この時点で、pはリストの最終項目へのポインア(のアドレス)}/* データ取得 */int get_data(void) { static int i=0; return a[i++];}/* リストの印刷 */void print_list(struct list *p) { while (p != NULL) { printf("<%d> [%0x %0x] ", p->key, p, p->next); p = p->next; } printf("\n");}/* リストへの挿入: 指定要素の直前 *//* pで示される構造体の前にxで示される構造体を挿入 */void insert_before(struct list *x, struct list *p) { struct list tmp; printf("<Insert [%0x] before [%0x]>\n", x, p); printf("<p key=%d next=%0x>\n", p->key, p->next); printf("<x key=%d next=%0x>\n", x->key, x->next); tmp = *x; printf("<tmp [%0x] key=%d next=%0x>\n", tmp, tmp.key, tmp.next); *x = *p; printf("<x [%0x] key=%d next=%0x>\n", x, x->key, x->next); *p = tmp; printf("<p [%0x] key=%d next=%0x>\n", p, p->key, p->next); p->next = x; printf("<p [%0x] key=%d next=%0x>\n", p, p->key, p->next);} |
実行結果は
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | C:\TDM-GCC-64\work>linklistInsertBackword<1> [9b1390 0]<2> [9b74f0 9b1390] <1> [9b1390 0]<3> [9b7510 9b74f0] <2> [9b74f0 9b1390] <1> [9b1390 0]<4> [9b7530 9b7510] <3> [9b7510 9b74f0] <2> [9b74f0 9b1390] <1> [9b1390 0]<5> [9b7550 9b7530] <4> [9b7530 9b7510] <3> [9b7510 9b74f0] <2> [9b74f0 9b1390] <1> [9b1390 0]<6> [9b7570 9b7550] <5> [9b7550 9b7530] <4> [9b7530 9b7510] <3> [9b7510 9b74f0] <2> [9b74f0 9b1390] <1> [9b1390 0]<6> [9b7570 9b7550] <5> [9b7550 9b7530] <4> [9b7530 9b7510] <3> [9b7510 9b74f0] <2> [9b74f0 9b1390] <1> [9b1390 0]<Insert [9b7590] before [9b7530]><p key=4 next=9b7510><x key=888 next=0><tmp [62fdf0] key=888 next=0><x [9b7590] key=4 next=9b7510><p [9b7530] key=888 next=0><p [9b7530] key=888 next=9b7590><6> [9b7570 9b7550] <5> [9b7550 9b7530] <888> [9b7530 9b7590] <4> [9b7590 9b7510] <3> [9b7510 9b74f0] <2> [9b74f0 9b1390] <1> [9b1390 0] |
挿入処理の本体は
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | void insert_before(struct list *x, struct list *p) { struct list tmp; tmp = *x; //step1 printf("<tmp [%0x] key=%d next=%0x>\n", tmp, tmp.key, tmp.next); *x = *p; //step2 printf("<x [%0x] key=%d next=%0x>\n", x, x->key, x->next); *p = tmp; //step3 printf("<p [%0x] key=%d next=%0x>\n", p, p->key, p->next); p->next = x; //step4 printf("<p [%0x] key=%d next=%0x>\n", p, p->key, p->next);} |
実行イメージは
