|
リスト構造
あるデータをポインタで結んだデータ構造。リスト構造には以下の3種類がある。
(1)連結リスト…リストに含まれる各要素をポインタによって、つなぎ合わせたデータ。一番最後のデータは次を指すデータがないので、NULLポインタをセットしておく。
(2)双方向リスト…セルは前のデータ・後ろのデータののポインタの両方を持っている。連結リストとは違い、前にも後ろにもデータを辿って行く事ができる。
(3)循環リスト…先頭と末尾を繋いで、輪にする。先頭という概念がない。
データ型は以下の例のような型をしていて、このデータを格納する入れ物を「セル」ともいう。
(セルの書式)
struct cell_t
struct cell_t *next;
int data;
};
先頭のセルは、ポインタにせずオブジェクトとして実体を持たせる事が望ましく、このセルにはデータをセットしないようにする。
struct cell_t g_list;
連結リスト
連結リストを作成するにあたり、必要な手続きは「セルの挿入」・「セルの削除」が必要。セルを挿入する時は、挿入する個所のポインタとそのポインタが指している次のポインタが必要になる。
セルを削除する時も同様に削除セルの前のポインタと削除するセルの次のポインタが必要。
連結リストの例
/*!
******************************************************************************
* \brief 連結リスト
*
******************************************************************************
*/
#include <stdio.h>
#include <malloc.h>
typedef struct _cell_t
{
struct _cell_t *next;
int data;
}cell_t;
extern int setList(cell_t *p, int data);
extern int deleteList(cell_t* p);
extern void allDeleteList(cell_t *p);
cell_t g_cell;//セルの先頭（このセルにはデータを入れない）
int main(int argc, char** argv)
{
g_cell.next = NULL;//先頭のセルの初期化
setList(&g_cell, 0);
setList(g_cell.next, 1);
deleteList(&g_cell);
allDeleteList(&g_cell);
return(0);
}
/*!
******************************************************************************
* \fn int setList(cell_t* p, int data)
* \param *p 挿入したいセルのポインタ（この直後にセルを挿入する）
* \param data データ
* \return -1の時はデータのセットができなかった時、正常時は0を返す
*
******************************************************************************
*/
int
setList(cell_t* p, int data)
{
cell_t *tmp;
tmp = (cell_t*)malloc(sizeof(cell_t));
if(tmp == NULL)
{
return(-1);
}
tmp->next = p->next;
tmp->data = data;
p->next = tmp;
return(0);
}
/*!
******************************************************************************
* \fn int deleteList(cell_t* p)
* \brief 引数で受け取ったセルの次のポインタのデータを削除
* \param *p 削除したいセルを指しているポインタ
* \return -1:エラー 0:正常終了
*
******************************************************************************
*/
int
deleteList(cell_t* p)
{
cell_t *tmp;
if(p->next == NULL)
{
return(-1);
}
tmp = p->next;
p->next = tmp->next;
free(tmp);
return(0);
}
/*!
******************************************************************************
* \fn void allDeleteList(cell_t *p)
* \brief データの全削除
* \param *p 先頭のセルのポインタ
* \return None
*
******************************************************************************
*/
void
allDeleteList(cell_t *p)
{
cell_t *tmp;
while (p->next != NULL)
{
tmp = p->next;
p->next = tmp->next;
free(tmp);
}
}
双方向リスト
双方向リストは前述したように、前と後ろの両方のポインタを保持するデータ構造になるので、以下のような書式となる。
セルの書式
struct cell_t{
struct_cell_t *next;
struct cell_t *back;
int data;
};
双方向リストの例
/*!
******************************************************************************
* \brief 双方向リスト
*
******************************************************************************
*/
#include >stdio.h<
#include >malloc.h<
typedef struct _cell_t
{
struct _cell_t *next;
struct _cell_t *back;
int data;
}cell_t;
extern int setList(cell_t *p, int data);
extern int deleteList(cell_t* p);
extern void allDeleteList(cell_t *p);
cell_t g_cell;
int main(int argc, char** argv)
{
g_cell.next = NULL;//先頭のセルの初期化
g_cell.back = NULL;
setList(&g_cell, 0);
setList(g_cell.next, 1);
deleteList(&g_cell);
allDeleteList(&g_cell);
return(0);
}
/*!
******************************************************************************
* \fn int setList(cell_t* p, int data)
* \param *p 挿入したいセルのポインタ（この直後にセルを挿入する）
* \param data データ
* \return -1の時はデータのセットができなかった時、正常時は0を返す
*
******************************************************************************
*/
int
setList(cell_t* p, int data)
{
cell_t *tmp;
tmp = (cell_t*)malloc(sizeof(cell_t));
if(tmp == NULL)
{
return(-1);
}
//***************************************************************************
// ┌───┐────→ ┌────┐
// │ ｐ │ここに挿入 │p->next │
// └───┘←──── └────┘
//***************************************************************************
tmp->next = p->next;//挿入するセルのnextに前のpのポインタを追加
tmp->back = p; //挿入
tmp->data = data;
p->next = tmp;
return(0);
}
/*!
******************************************************************************
* \fn int deleteList(cell_t* p)
* \brief 引数で受け取ったセルの次のポインタのデータを削除
* \param *p 削除したいセルを指しているポインタ
* \return -1:エラー 0:正常終了
*
******************************************************************************
*/
int
deleteList(cell_t* p)
{
cell_t *tmp;
if(p->next == NULL)
{
return(-1);
}
tmp = p->next;
p->next = tmp->next;
tmp->next->back = p;
free(tmp);
return(0);
}
/*!
******************************************************************************
* \fn void allDeleteList(cell_t *p)
* \brief データの全削除
* \param *p 先頭のセルのポインタ
* \return None
*
******************************************************************************
*/
void
allDeleteList(cell_t *p)
{
cell_t *tmp;
while (p->next != NULL)
{
tmp = p->next;
p->next = tmp->next;
free(tmp);
}
}
循環リスト
循環リストは、セルを円を全て繋げて循環できるリスト構造である。連結リスト・双方向リストと同様に先頭のセルはオブジェクトとし実体を持たせ、データの格納している最後のセルは先頭のセルのポインタを持つ。
循環リストの例
/*!
******************************************************************************
* \brief 循環リスト
*
******************************************************************************
*/
#include >stdio.h<
#include >malloc.h<
typedef struct _cell_t
{
struct _cell_t *next;
int data;
}cell_t;
extern int setList(cell_t *p, int data);
extern int deleteList(cell_t* p);
extern void allDeleteList(cell_t *p);
cell_t g_cell;
int main(int argc, char** argv)
{
g_cell.next = NULL;//先頭のセルの初期化
setList(&g_cell, 0);
setList(g_cell.next, 1);
setList(g_cell.next->next, 2);
deleteList(&g_cell);
allDeleteList(&g_cell);
return(0);
}
/*!
******************************************************************************
* \fn int setList(cell_t* p, int data)
* \param *p 挿入したいセルのポインタ（この直後にセルを挿入する）
* \param data データ
* \return -1の時はデータのセットができなかった時、正常時は0を返す
*
******************************************************************************
*/
int
setList(cell_t* p, int data)
{
cell_t *tmp;
tmp = (cell_t*)malloc(sizeof(cell_t));
if(tmp == NULL)
{
return(-1);
}
//要素が存在した場合
if (p->next != NULL)
{
tmp->next = p->next;
p->next = tmp;
tmp->data = data;
}
else //要素がない場合
{
tmp->next = p;
p->next = tmp;
tmp->data = data;
}
return(0);
}
/*!
******************************************************************************
* \fn int deleteList(cell_t* p)
* \brief 引数で受け取ったセルの次のポインタのデータを削除
* \param *p 削除したいセルを指しているポインタ
* \return -1:エラー 0:正常終了
*
******************************************************************************
*/
int
deleteList(cell_t* p)
{
cell_t *tmp;
if(p->next == NULL)
{
return(-1);
}
tmp = p->next;
p->next = tmp->next;
free(tmp);
return(0);
}
/*!
******************************************************************************
* \fn void allDeleteList(cell_t *head)
* \brief データの全削除
* \param *head 先頭のセルのポインタ
* \return None
*
******************************************************************************
*/
void
allDeleteList(cell_t *head)
{
cell_t *p, *tmp;
for (p = head->next; p != head;)
{
tmp = p;
p = tmp->next;
free(tmp);
}
}
|
