前回と同様のリストを利用する
スタックを実装する
配列による実装では配列とtop変数を使った
今回はスタックトップをheadとする
graph TD A[head]-->B[data3] B-->C[data2] C-->D[data1] E((push))-->B B-->F((pop))
typedef struct node *stack;
//stackはポインタ
void initstack(stack *s){
*s=initlist();
}
int stackempty(stack s){
return s->next==NULL;
}
void push(stack s, elementtype x){
insert(s,x)
}
elementtype pop(stack s){
elementtype retval;
if ( stackempty (s)){
printf (“underflow¥n”);
exit(1);
} else {
retval = s -> next -> element;
delete(s);
return retval;
}
}
int main(void){
stack s;
initstack(&s);
push(s,'a');
push(s,'b');
while(!stackempty(s)){
printf("%c",pop(s));
}
printf("\n");
return 0;
}headノードがない場合はめんどくさい
キューの実装
graph TD A[(front)]-->B[head] B-->C[data1] C-->D[data2] D-->E[data3] F((rear))-->E
typedef struct node *link;
struct queue{
link font,rear;
};
void initqueue(struct queue *q){
q->front=initlist;
q->rear=q->front;
}
int queueempty(struct queue q){
return q.front->next==NULL;
}
void enqueue(struct queue *q, elementtype x){
insert(q->rear,x);
q->rear=q->rear->next;
}
elementtype dequeue(struct queue *q){
elementtype retval; /* 返り値保存用 */
if(queueempty(*q)){
printf(“underflow¥n”);
exit(1);
} else {
retval = q -> front -> next -> element; /* 値取得 */
delete(q->front); /* 削除 */
if(queueempty(*q)){
q->rear = q->front;
}
return retval;
}
}リストを用いた問題
- 画面出力
- 探索
- 複製
- 整列しながらの挿入
- 逆転
など
画面出力
void print(link p){
while (p->next!=NULL){//最初にnextを読み飛ばしてheadを飛ばす
printf("%c",p->next->element);
p=p->next
}
printf("\n");
}探索
typedef struct node *link;
int search(link p,elementtypex){
int found= 0;
while (!found&&p->next!=NULL){
p=p->next;
found=(p->element==x);
}
return found;
}フラグ変数のないパターンでもOK
複製
link copy(link src){
link dst, p;
dst=initlist();
p=dst;
while(src->next!=NULL){
insert(p,src->next->element);
p=p->next;
src=src->next;
}
return dst;
}整列しながらの挿入
リストの要素は予め整列（昇順）しているという前提で、新しい要素を正しい位置に挿入する
graph TD subgraph 整列済みリスト H[head] --> N1[1] N1 --> N3[3] N3 --> N5[5] N5 --> N7[7] N7 --> N9[9] N9 --> N11[11] end X[6 を挿入] -.->|"5と7の間を見つけて挿入"| N5
6より小さいかどうかを左端から順に比較し、「6より大きくなる瞬間」の直前に挿入する
void order(link p, elementtype x){ /* pは昇順が前提 */
int found = 0;
while(!found && p->next != NULL){
if(x < p->next->element){ /* 次がxより大きい時 */
found = 1; /* pに挿入 */
} else {
p = p->next; /* pを更新 */
}
}
insert(p, x);
}p->nextの値と大小比較し、xのほうが小さい場合はpの次に挿入する。末尾まで大きい場合は末尾に挿入される
逆転
与えられたリストを逆順にする。
方法1：取得&削除して新しいリストへ挿入
既存リストの先頭から順に取得&削除し、新しいリストの先頭（headの次）へ順に挿入する。headへのinsert/deleteはスタックと同じように機能し、LIFO（Last-In First-Out）で逆順になる。
graph LR subgraph 元リスト src SH[head] --> S1[1] S1 --> S3[3] S3 --> S5[5] S5 --> S7[7] S7 --> S9[9] S9 --> S11[11] end subgraph 逆転後 dst DH[head] --> D11[11] D11 --> D9[9] D9 --> D7[7] D7 --> D5[5] D5 --> D3[3] D3 --> D1[1] end SH -->|"取得&削除"| S1 S1 -->|"insert"| DH
link reverse(link src){
link dst;
dst = initlist();
while(src->next != NULL){
insert(dst, src->next->element);
delete(src);
}
return dst;
}方法2：リンクをつなぎ替える（ノードはそのままで）
ノードを複製せず、nextリンクを逆向きにつなぎ替える実装。注目ノードのnextを1つ前のノードに向けるが、元のnextを見失わないよう3つのポインタ（keep, oldp, p）で管理する
graph TD subgraph 初期状態 H[head] --> A[L] A --> B[I] B --> C[S] C --> D[T] D --> E[NULL] end subgraph 逆転後 H2[head] --> D2[T] D2 --> C2[S] C2 --> B2[I] B2 --> A2[L] A2 --> E2[NULL] end
各ポインタの役割：
keep：1つ前のノード（逆向きリンクの先）oldp：注目ノード（リンクを書き換える対象）p：次のノード（次ループの注目候補）
link reverse2(link p){
link head, oldp, keep;
head = p; oldp = NULL; p = p->next;
while(p != NULL){
keep = oldp;
oldp = p;
p = p->next;
oldp->next = keep;
}
head->next = oldp;
return head;
}whileループでは keep←oldp←p と1つずつ右にずれながら、oldp->nextをkeep（前のノード）に向ける。whileを抜けた時点でoldpが最後尾なので、head->nextにoldpを繋げる。