ポインタの復習
メモリのアドレスを使えるようにする
レジスタを隠蔽してアセンブリを多少扱いやすくするようなイメージのほうが近いのかも？
mallocや配列のサイズを調べるのにはsizeofが便利
ポインタに対してsizeofしても配列のサイズがわからないことには注意
リスト
抽象的な概念としては、一定の型を持つデータを持つデータを1列に並べたもの
graph LR A[head]--リンク-->B(L)-->C(I)-->D(S)-->E(T)
ノードをリンクで連結したlinked listを利用する
利点
- 任意の場所でのデータの挿入・削除が簡単
- 並べ替えも簡単
配列の場合なら全要素を移動させる必要がある為面倒
要素を削除するなら直前のリンクを書き換えればいい
並べ替えも一部のリンクを書き換えればいい
Cによる実装
配列によってリストを実装するのは大変なので、ノードを実装する
ノードに必要なのは
- 保持するデータ
- 次へのリンク
struct node{
elementtype element;
struct node *next;
}こんな感じでいい
headはデータを持たないノード、末尾にはnullポインタを代入
リスト自体はheadへのポインタとして扱う
リストの実装
initlist()
struct node *initlist(void){
struct node *n;
n=(struct node*)malloc(sizeof(struct node));
n->next=NULL;
return n;
}mallocしないと関数が終了した時点で内容が消滅してしまう
insert()
挿入場所と保持する値を指定する
void insert(struct node *p, elementtype x){
struct node *n;
n = ( struct node * ) malloc ( sizeof ( struct node ) );
n -> element = x;
n -> next = p->next;
p -> next = n;
}先に後ろを繋ぎ変えないと後ろ側が迷子になってしまう
delete()
削除するためにはリンクの直前のノードの情報が必要
void delete(struct node *p){
if(p->next!=NULL){
p->next=p->next->next;
}
}使用例
typedef char elementtype;
int main(void){
struct node *list;
list =initlist();
insert(list,'a');
insert(list,'b');
}その他として、末尾を先頭やheadに連結した循環リストやnodeに前のポインタも持たせる両方向リストもある