slides12

データ構造とアルゴリズム
第12回リスト構造（２）
静岡大学工学部
安藤和敏
2011.07.01
目次
1. 変数とメモリ（基本の確認）
2. リスト構造（前回の復習,TraverseList
も）
3. リストに対する挿入と削除の操作
4. 実習
目次
1. 変数とメモリ（基本の確認）
2. リスト構造（前回の復習,TraverseList
も）
3. リストに対する挿入と削除の操作
4. 実習
コンピュータのメモリのイメージ
アドレス
内容
0
1
2
3
4
5
6
7
175
．
．
．
安藤
浜松
2004
．
．
．
変数とメモリ
int x;
と宣言することによ
って、xという名前が
付けられた4バイト
分のメモリ領域が確
保される。
確保されるバイト数
はその変数の型に
依存する。p.18の表
2.3を見よ。
アドレス
0
1
2
3
4
5:x:
6
7
内容
175
安藤
浜松
2004
．
．以降は、この確保されたメモ
と言う名前
．リ領域の内容をx．
．
．で参照できるようになる。
ポインタとメモリ（教科書p.143-144）
int x;
int *p=&x;
アドレス
内容
0
1:p:
2
3
4
5
6
7:x:
175
7
安藤
浜松
2004
ポインタ変数 pの
内容=7
xの宣言によっ
て確保されたメ
モリ領域
ポインタとメモリの関係の図示
int x;
int *p=&x;
アドレス
p:
x:
内容
以降では、前
ページのよう
な状況を図示
するために、
このような矢
線を用いて表
現する。
構造体ポインタとメモリ
struct COMPLEX a={1,-2};
struct COMPLEX *p=&a;
アドレス
0
1
2
3:p:
4
5:a:
7
8
内容
ポインタ変数 pの
内容=5
5
(real) 1
(img) -2
aの宣言によっ
て確保されたメ
モリ領域
構造体ポインタからのメンバの参照
struct COMPLEX a={1,-2};
struct COMPLEX *p=&a;
メモリの内容
p:
a:
(real) 1
(img) -2
構造体ポインタ
pを介してaのメ
ンバrealを参照
するときには、
p->real,
p->img
目次
1. 変数とメモリ（基本の確認）
2. リスト構造（前回の復習,TraverseList
も）
3. リストに対する挿入と削除の操作
4. 実習
目次
1. 変数とメモリ（基本の確認）
2. リスト構造（前回の復習,TraverseList
も）
3. リストに対する挿入と削除の操作
4. 実習
リストに対する挿入: Insert
リストが与えられたときに、ポインタ p が指し示すセ
ルの次に、整数 x が入ったセルを挿入する。
p
root
10
8
4
23
4
23
p
root
10
8
x
関数 Insert の説明: p!=NULLのとき
void Insert(int x, struct CELL *p) {
struct CELL *newcell;
newcell = (struct CELL *)
malloc(sizeof(struct CELL));
newcell->data = x;
if (p != NULL) {
newcell->next = p->next;
p->next = newcell;
p
} else { // p == NULL
newcell->next = root;
8
root = newcell;
}
}
newcell
4
x
関数 Insert の説明: p==NULLのとき
void Insert(int x, struct CELL *p) {
struct CELL *newcell;
newcell = (struct CELL *)
malloc(sizeof(struct CELL));
newcell->data = x;
p==NULL
root
10
if (p != NULL) {
newcell->next = p->next;
p->next = newcell;
newcell
} else {
newcell->next = root;
root = newcell;
}
}
8
x
リストに対する削除操作: Delete
リスト構造が与えられたときに、ポインタ p の指し示
すセルの次のセルを削除する。
p
root
root
10
8
10
8
4
23
23
関数 Delete の説明: p!=NULL の場合
void Delete(struct CELL *p) {
struct CELL *temp;
if (root == NULL)
printf("Error: List is empty.\n");
temp
p
if (p == NULL) {
temp = root;
8
4
root = root->next;
free(temp);
} else if (p->next != NULL) {
temp = p->next;
p->next = p->next->next;
free(temp);
}
}
23
関数 Delete の説明: p==NULL の場合
void Delete(struct CELL *p) {
struct CELL *temp;
if (root == NULL)
printf("Error: List is empty.\n");
if (p == NULL) {
temp = root;
root = root->next;
free(temp);
} else ifp==NULL
(p->next !=temp
NULL) {
temp = p->next;
p->next = p->next->next;
10
8
free(temp);
root
}
}
4
目次
1. 変数とメモリ（基本の確認）
2. リスト構造（前回の復習,TraverseList
も）
3. リストに対する挿入と削除の操作
4. 実習

Download Report