C言語で連結リストを実装してみました。
＜list.h＞
#ifndef LIST_H
#define LIST_H
#ifdef LIST_C
#define LIST_EXTERN extern
#else
#define LIST_EXTERN
#endif
/**
* @file list.h
* @brief 連結リスト
*/
// インクルードヘッダ
#include ＜stddef.h＞
/// 連結リストディスクリプタ構造体
typedef struct listDsc TListDsc;
/*
list_Create - 連結リスト生成 -
*/
/**
* 連結リストを生成,初期化し,連結リストディスクリプタを返却する.
* @param [in] sz 要素1つあたりのバイト数
* @retval 連結リストディスクリプタへのポインタ.生成失敗時はNULL.
* @attention 連結リストを使用する前に本関数を呼び出す必要がある.
*/
LIST_EXTERN TListDsc *list_Create(size_t sz);
/*
list_Destroy - 連結リスト破棄 -
*/
/**
* 連結リストで使用したメモリを解放し,連結リストを破棄する.
* @param [in] lst 破棄する連結リストのディスクリプタ
* @retval なし.
* @attention 連結リストの使用が終了したら本関数で破棄を行うこと.
*/
LIST_EXTERN void list_Destroy(TListDsc *lst);
/*
list_PushFront - 要素追加処理(先頭) -
*/
/**
* 連結リストの先頭に要素を追加する.
* @param [in] lst 操作対象連結リストのディスクリプタ
* @param [in] itm 追加要素
* @retval 0以外:成功 0:失敗.
* @attention 特になし.
*/
LIST_EXTERN int list_PushFront(TListDsc * restrict lst, void const * restrict itm);
/*
list_PushBack - 要素追加処理(末尾) -
*/
/**
* 連結リストの末尾に要素を追加する.
* @param [in] lst 操作対象連結リストのディスクリプタ
* @param [in] itm 追加要素
* @retval 0以外:成功 0:失敗.
* @attention 特になし.
*/
LIST_EXTERN int list_PushBack(TListDsc * restrict lst, void const * restrict itm);
/*
list_PopFront - 要素削除処理(先頭) -
*/
/**
* 連結リストの先頭から要素を削除する.
* @param [in] lst 操作対象連結リストのディスクリプタ
* @param [out] itm 削除要素格納領域
* @retval 0以外:成功 0:失敗.
* @attention リストが空の場合は0を返す.
*/
LIST_EXTERN int list_PopFront(TListDsc * restrict lst, void * restrict itm);
/*
list_PopBack - 要素削除処理(末尾) -
*/
/**
* 連結リストの先頭から要素を削除する.
* @param [in] lst 操作対象連結リストのディスクリプタ
* @param [out] itm 削除要素格納領域
* @retval 0以外:成功 0:失敗.
* @attention リストが空の場合は0を返す.
*/
LIST_EXTERN int list_PopBack(TListDsc * restrict lst, void * restrict itm);
/*
list_Front - 先頭要素取得処理 -
*/
/**
* 連結リストの先頭要素を返す.
* @param [in] lst 操作対象連結リストのディスクリプタ
* @param [out] itm 要素格納領域
* @retval 0以外:成功 0:失敗.
* @attention 連結リストが空の場合は0を返す.
* @attention 本関数をコールしても,先頭要素は連結リスト上に存在したままである.
*/
LIST_EXTERN int list_Front(TListDsc const * restrict lst, void * restrict itm);
/*
list_Back - 末尾要素取得処理 -
*/
/**
* 連結リストの末尾要素を返す.
* @param [in] lst 操作対象連結リストのディスクリプタ
* @param [out] itm 要素格納領域
* @retval 0以外:成功 0:失敗.
* @attention 連結リストが空の場合は0を返す.
* @attention 本関数をコールしても,末尾要素は連結リスト上に存在したままである.
*/
LIST_EXTERN int list_Back(TListDsc const * restrict lst, void * restrict itm);
/*
list_Size - 登録要素数取得処理 -
*/
/**
* 連結リストに登録されている要素の数を返す.
* @param [in] lst 操作対象連結リストのディスクリプタ
* @retval 連結リストに積まれている要素数.
* @attention 特になし.
*/
LIST_EXTERN unsigned int list_Size(TListDsc const *lst);
/*
list_Empty - 空判定処理 -
*/
/**
* 連結リストが空かどうかを判定する.
* @param [in] lst 操作対象連結リストのディスクリプタ
* @retval 1:空 0:空ではない.
* @attention 特になし.
*/
LIST_EXTERN int list_Empty(TListDsc const *lst);
/*
list_Erase - 要素削除処理 -
*/
/**
* 連結リストから指定位置の要素を削除する.
* @param [in] lst 操作対象連結リストのディスクリプタ
* @param [in] pos 削除位置
* @retval 0以外:成功 0:失敗.
* @attention 特になし.
*/
LIST_EXTERN int list_Erase(TListDsc *lst, unsigned int pos);
/*
list_Clear - 全要素削除処理 -
*/
/**
* 連結リストから全ての要素を削除する.
* @param [in] lst 操作対象連結リストのディスクリプタ
* @retval 0以外:成功 0:失敗.
* @attention 特になし.
*/
LIST_EXTERN int list_Clear(TListDsc *lst);
/*
list_Insert - 要素挿入処理 -
*/
/**
* 連結リストの指定位置に要素を挿入する.
* @param [in] lst 操作対象連結リストのディスクリプタ
* @param [in] pos 挿入位置
* @retval 0以外:成功 0:失敗.
* @attention 指定位置が0ならば先頭に追加される.
*/
LIST_EXTERN int list_Insert(TListDsc * restrict lst, void * restrict itm, unsigned int pos);
/*
list_Get - 要素取得処理 -
*/
/**
* 連結リストの指定位置の要素を返す.
* @param [in] lst 操作対象連結リストのディスクリプタ
* @param [in] pos 取得位置
* @param [out] itm 要素格納領域
* @retval 0以外:成功 0:失敗.
* @attention 本関数をコールしても,指定位置要素はリスト上に存在したままである.
*/
LIST_EXTERN int list_Get(TListDsc const * restrict lst, unsigned int pos, void * restrict itm);
/*
list_MoveFront - カーソル位置移動処理(先頭) -
*/
/**
* 連結リストのカーソル位置を先頭に設定する.
* @param [in] lst 操作対象連結リストのディスクリプタ
* @retval なし.
* @attention 特になし.
*/
LIST_EXTERN void list_MoveFront(TListDsc *lst);
/*
list_MoveBack - カーソル位置移動処理(末尾) -
*/
/**
* 連結リストのカーソル位置を末尾に設定する.
* @param [in] lst 操作対象連結リストのディスクリプタ
* @retval なし.
* @attention 特になし.
*/
LIST_EXTERN void list_MoveBack(TListDsc *lst);
/*
list_MoveNext - カーソル位置移動処理(末尾方向) -
*/
/**
* 連結リストのカーソル位置を末尾方向へ1要素分移動する.
* @param [in] lst 操作対象連結リストのディスクリプタ
* @retval 0以外:成功 0:失敗.
* @attention カーソル位置が既に末尾要素を指していたら0を返す.
*/
LIST_EXTERN int list_MoveNext(TListDsc *lst);
/*
list_MovePrev - カーソル位置移動処理(先頭方向) -
*/
/**
* 連結リストのカーソル位置を先頭方向へ1要素分移動する.
* @param [in] lst 操作対象連結リストのディスクリプタ
* @retval 0以外:成功 0:失敗.
* @attention カーソル位置が既に先頭要素を指していたら0を返す.
*/
LIST_EXTERN int list_MovePrev(TListDsc *lst);
/*
list_GetCurrent - カーソル位置要素取得処理 -
*/
/**
* 連結リストのカーソル位置の要素を返す.
* @param [in] lst 操作対象連結リストのディスクリプタ
* @param [out] itm 要素格納領域
* @retval 0以外:成功 0:失敗.
* @attention 連結リストが空の場合,0を返す.
*/
LIST_EXTERN int list_GetCurrent(TListDsc const * restrict lst, void * restrict itm);
/*
list_InsertAtCurrent - カーソル位置要素挿入処理 -
*/
/**
* 連結リストのカーソル位置に要素を挿入する.
* @param [in] lst 操作対象連結リストのディスクリプタ
* @param [in] itm 挿入要素
* @retval 0以外:成功 0:失敗.
* @attention 挿入前にカーソルが指していた要素は挿入後,挿入要素の次の要素となる.
*/
LIST_EXTERN int list_InsertAtCurrent(TListDsc * restrict lst, void * restrict itm);
/*
list_EraseCurrent - カーソル位置要素削除処理 -
*/
/**
* 連結リストのカーソル位置の要素を削除する.
* @param [in] lst 操作対象連結リストのディスクリプタ
* @retval 0以外:成功 0:失敗.
* @attention 削除後のカーソル位置の要素は＜br＞
* 削除前のカーソル位置の次の要素となる(前詰めされる).
* ただし,カーソル位置が末尾要素であった場合は＜br＞
* 削除前のカーソル位置の前の要素となる.
*/
LIST_EXTERN int list_EraseCurrent(TListDsc *lst);
#endif // LIST_H
＜list.c＞
#define LIST_C
/**
* @file list.c
* @brief 連結リスト
*/
// インクルードヘッダ
#include ＜stdlib.h＞
#include ＜stddef.h＞
#include ＜string.h＞
#include "list.h"
// 連結リスト要素連結情報構造体
typedef struct listItemLinkInf TListItemLinkInf;
struct listItemLinkInf {
TListItemLinkInf *next;
TListItemLinkInf *prev;
void *item;
};
// 連結リストディスクリプタ構造体
struct listDsc {
size_t size; // 1要素あたりのバイト数
TListItemLinkInf *front; // 先頭要素連結情報へのポインタ
TListItemLinkInf *back; // 末尾要素連結情報へのポインタ
TListItemLinkInf *current; // カーソル位置の要素連結情報へのポインタ
unsigned int num; // 連結リストに登録された要素数
TListItemLinkInf *empty; // 空き要素リンク(現在使われていない要素のリンク)
};
// プロトタイプ宣言
static TListItemLinkInf *list_PopEmpty(TListDsc *lst);
static void list_PushEmpty(TListDsc *lst, TListItemLinkInf *inf);
static int list_InsertAtListItemLinkInf(TListDsc * restrict lst, void const * restrict itm, TListItemLinkInf * restrict inf);
static int list_EraseListItemLinkInf(TListDsc * restrict lst, TListItemLinkInf * restrict inf);
static TListItemLinkInf *list_SearchListItemLinkInf(TListDsc const *lst, unsigned int pos);
/*
list_Create - 連結リスト生成 -
*/
TListDsc *list_Create(size_t sz)
{
TListDsc *lst; // 返却用ディスクリプタ
// ディスクリプタ用のメモリを取得する
// 失敗ならNULLを返す
if ((lst = malloc(sizeof(TListDsc))) == NULL) {
return NULL;
}
// ディクスリプタの各メンバを初期化する
lst-＞size = sz;
lst-＞num= 0;
lst-＞front = NULL;
lst-＞back = NULL;
lst-＞current = NULL;
lst-＞empty = NULL;
// ディスクリプタを返却する
return lst;
}
/*
list_Destroy - 連結リスト破棄 -
*/
void list_Destroy(TListDsc *lst)
{
TListItemLinkInf *inf;
TListItemLinkInf *next;
// 登録されている要素を解放する
inf = lst-＞front;
while(inf != NULL) {
free(inf-＞item);
next = inf-＞next;
free(inf);
inf = next;
}
// 空き要素を解放する
inf = lst-＞empty;
while(inf != NULL) {
free(inf-＞item);
next = inf-＞next;
free(inf);
inf = next;
}
}
/*
list_PushFront - 要素追加処理(先頭) -
*/
int list_PushFront(TListDsc * restrict lst, void const * restrict itm)
{
return list_InsertAtListItemLinkInf(lst, itm, lst-＞front);
}
/*
list_PushBack - 要素追加処理(末尾) -
*/
int list_PushBack(TListDsc * restrict lst, void const * restrict itm)
{
TListItemLinkInf *inf;
// 空き要素を取得する
if ((inf = list_PopEmpty(lst)) == NULL) {
return 0;
}
// 取得した空き要素に追加対象要素をコピーする
memcpy(inf-＞item, itm, lst-＞size);
// 連結リストの末尾に追加分の要素連結情報を追加する
inf-＞prev = lst-＞back;
inf-＞next = NULL;
if (lst-＞back == NULL) {
lst-＞front = inf;
lst-＞current = inf; // 最初の登録なのでカーソル位置として設定
} else {
lst-＞back-＞next = inf;
}
lst-＞back = inf;
// 要素数をインクリメント
lst-＞num++;
return 1;
}
/*
list_PopFront - 要素削除処理(先頭) -
*/
int list_PopFront(TListDsc * restrict lst, void * restrict itm)
{
// リストが空なら0を返す
if (lst-＞front == NULL) {
return 0;
}
// 先頭要素を出力領域にコピー
memcpy(itm, lst-＞front-＞item, lst-＞size);
// 先頭要素を削除
return list_EraseListItemLinkInf(lst, lst-＞front);
}
/*
list_PopBack - 要素削除処理(末尾) -
*/
int list_PopBack(TListDsc * restrict lst, void * restrict itm)
{
// リストが空なら0を返す
if (lst-＞back == NULL) {
return 0;
}
// 末尾要素を出力領域にコピー
memcpy(itm, lst-＞back-＞item, lst-＞size);
// 末尾要素を削除
return list_EraseListItemLinkInf(lst, lst-＞back);
}
/*
list_Front - 先頭要素取得処理 -
*/
int list_Front(TListDsc const * restrict lst, void * restrict itm)
{
// リストが空なら0を返す
if (lst-＞front == NULL) {
return 0;
}
// 先頭要素を出力領域にコピー
memcpy(itm, lst-＞front-＞item, lst-＞size);
return 1;
}
/*
list_Back - 末尾要素取得処理 -
*/
int list_Back(TListDsc const * restrict lst, void * restrict itm)
{
// リストが空なら0を返す
if (lst-＞back == NULL) {
return 0;
}
// 末尾要素を出力領域にコピー
memcpy(itm, lst-＞back-＞item, lst-＞size);
return 1;
}
/*
list_Size - 登録要素数取得処理 -
*/
unsigned int list_Size(TListDsc const *lst)
{
return lst-＞num;
}
/*
list_Empty - 空判定処理 -
*/
int list_Empty(TListDsc const *lst)
{
return lst-＞num == 0 ? 1 : 0;
}
/*
list_Erase - 要素削除処理 -
*/
int list_Erase(TListDsc *lst, unsigned int pos)
{
TListItemLinkInf *inf;
// 削除対象要素を検索
inf = list_SearchListItemLinkInf(lst, pos);
// 検索した要素を削除
return list_EraseListItemLinkInf(lst, inf);
}
/*
list_Clear - 全要素削除処理 -
*/
int list_Clear(TListDsc *lst)
{
// リストが空なら何もせずリターン
if (lst-＞num == 0) {
return 1;
}
// 全要素を空き要素リンクへ移動する
lst-＞back-＞next = lst-＞empty;
lst-＞empty = lst-＞front;
lst-＞front = NULL;
lst-＞back = NULL;
lst-＞current = NULL;
lst-＞num = 0;
return 1;
}
/*
list_Insert - 要素挿入処理 -
*/
int list_Insert(TListDsc * restrict lst, void * restrict itm, unsigned int pos)
{
TListItemLinkInf *inf;
// 指定位置が末尾要素の次を指していたら末尾に追加してリターン
if (lst-＞num == pos) {
return list_PushBack(lst, itm);
}
// 追加位置を検索
inf = list_SearchListItemLinkInf(lst, pos);
// 追加位置要素がなければ0を返す
if (inf == NULL) {
return 0;
}
return list_InsertAtListItemLinkInf(lst, itm, inf);
}
/*
list_Get - 要素取得処理 -
*/
int list_Get(TListDsc const * restrict lst, unsigned int pos, void * restrict itm)
{
TListItemLinkInf *inf;
// 取得位置を検索
inf = list_SearchListItemLinkInf(lst, pos);
// 追加位置要素がなければ0を返す
if (inf == NULL) {
return 0;
}
// 取得位置の要素を出力領域にコピー
memcpy(itm, inf-＞item, lst-＞size);
return 1;
}
/*
list_MoveFront - カーソル位置移動処理(先頭) -
*/
void list_MoveFront(TListDsc *lst)
{
lst-＞current = lst-＞front;
}
/*
list_MoveBack - カーソル位置移動処理(末尾) -
*/
void list_MoveBack(TListDsc *lst)
{
lst-＞current = lst-＞back;
}
/*
list_MoveNext - カーソル位置移動処理(末尾方向) -
*/
int list_MoveNext(TListDsc *lst)
{
// 登録要素なしなら0をリターン
if (lst-＞current == NULL) {
return 0;
}
// カーソル位置の次がなければ0をリターン
if (lst-＞current-＞next == NULL) {
return 0;
}
// カーソル位置を移動
lst-＞current = lst-＞current-＞next;
return 1;
}
/*
list_MovePrev - カーソル位置移動処理(先頭方向) -
*/
int list_MovePrev(TListDsc *lst)
{
// 登録要素なしなら0をリターン
if (lst-＞current == NULL) {
return 0;
}
// カーソル位置の前がなければ0をリターン
if (lst-＞current-＞prev == NULL) {
return 0;
}
// カーソル位置を移動
lst-＞current = lst-＞current-＞prev;
return 1;
}
/*
list_GetCurrent - カーソル位置要素取得処理 -
*/
int list_GetCurrent(TListDsc const * restrict lst, void * restrict itm)
{
// 登録要素なしなら0をリターン
if (lst-＞current == NULL) {
return 0;
}
// カーソル位置の要素を出力領域にコピー
memcpy(itm, lst-＞current-＞item, lst-＞size);
return 1;
}
/*
list_InsertAtCurrent - カーソル位置要素挿入処理 -
*/
int list_InsertAtCurrent(TListDsc * restrict lst, void * restrict itm)
{
return list_InsertAtListItemLinkInf(lst, itm, lst-＞current);
}
/*
list_EraseCurrent - カーソル位置要素削除処理 -
*/
int list_EraseCurrent(TListDsc *lst)
{
return list_EraseListItemLinkInf(lst, lst-＞current);
}
/*
list_PopEmpty - 空き要素取得処理 -
*/
static TListItemLinkInf *list_PopEmpty(TListDsc *lst)
{
TListItemLinkInf *inf;
if (lst-＞empty != NULL) {
inf = lst-＞empty;
lst-＞empty = lst-＞empty-＞next;
} else {
inf = malloc(sizeof(TListItemLinkInf));
if (inf == NULL) {
return NULL;
}
inf-＞item = malloc(lst-＞size);
if (inf-＞item == NULL) {
free(inf);
return NULL;
}
}
return inf;
}
/*
list_PushEmpty - 空き要素登録処理 -
*/
static void list_PushEmpty(TListDsc *lst, TListItemLinkInf *inf)
{
inf-＞next = lst-＞empty;
lst-＞empty = inf;
}
/*
list_InsertAtListItemLinkInf - 要素挿入処理(要素連結情報指定) -
*/
static int list_InsertAtListItemLinkInf(TListDsc * restrict lst, void const * restrict itm, TListItemLinkInf * restrict inf)
{
TListItemLinkInf *nw;
// 空き要素を取得する
if ((nw = list_PopEmpty(lst)) == NULL) {
return 0;
}
// 取得した空き要素に追加対象要素をコピーする
memcpy(nw-＞item, itm, lst-＞size);
// その新要素をリストに挿入
nw-＞next = inf;
if (inf != NULL) {
nw-＞prev = inf-＞prev;
if (inf-＞prev != NULL) {
inf-＞prev-＞next = nw;
} else {
lst-＞front = nw;
}
inf-＞prev = nw;
} else {
nw-＞prev = NULL;
lst-＞front = nw;
lst-＞back = nw;
lst-＞current = inf; // 最初の登録なのでカーソル位置として設定
}
// 登録要素数をインクリメント
lst-＞num++;
return 1;
}
/*
list_EraseListItemLinkInf - 要素削除処理(要素連結情報指定) -
*/
static int list_EraseListItemLinkInf(TListDsc * restrict lst, TListItemLinkInf * restrict inf)
{
// 指定された要素連結情報がNULLなら0を返す
if (inf == NULL) {
return 0;
}
// カーソル位置の要素がなくなるならクリアする
if (inf == lst-＞current) {
lst-＞current = inf-＞next;
}
// 削除対象要素をリストから外す
if (inf-＞prev != NULL) {
inf-＞prev-＞next = inf-＞next;
} else {
lst-＞front = inf-＞next;
}
if (inf-＞next != NULL) {
inf-＞next-＞prev = inf-＞prev;
} else {
lst-＞back = inf-＞prev;
}
lst-＞num--;
// 削除対象要素を空き要素リンクに登録
list_PushEmpty(lst, inf);
return 1;
}
/*
list_SearchListItemLinkInf - 要素連結情報検索処理 -
*/
static TListItemLinkInf *list_SearchListItemLinkInf(TListDsc const *lst, unsigned int pos)
{
TListItemLinkInf *inf;
unsigned int i;
// リストが空ならNULLをリターン
if (lst-＞num == 0) {
return NULL;
}
// 要素連結情報を検索
i = 0;
inf = lst-＞front;
while (i != pos) {
inf = inf-＞next;
if (inf == NULL) {
return NULL;
}
i++;
}
return inf;
}
英大文字小文字の区別なしで文字列を比較する関数strcasecmp()をC言語でつくってみました。
/*
strcasecmp - 文字列比較(英大文字小文字区別なし) -
*/
/**
* 英大文字小文字の区別なしで文字列を比較する.
* @param [in] s1 比較対象文字列1
* @param [in] s2 比較対象文字列2
* @retval 一致なら0,s1が大なら正,s2が大なら負
* @attention 特になし.
*/
int strcasecmp(const char *s1, const char *s2)
{
const unsigned char *a1= (const unsigned char *)s1;
const unsigned char *a2= (const unsigned char *)s2;
int c1;
int c2;
while (1) {
c1 = tolower(*a1++);
c2 = tolower(*a2++);
if (c1 != c2) { break; }
if (c1 == '\0') { return 0; }
}
return c1 - c2;
}
プログラミングにおいて、関数名や変数名等を決める時に名称が長くなりすぎるときがあります。そういった時に単語を省略するのですが、その省略形のよく使われるものの一覧をつくってみました。
省略するときのパターンとしては、1) 先頭部分を使用し、残りを省略する、2) 先頭以外の母音を省略する、の2パターンが多いですね。
address : addr
animation : ani
answer : ans
application : app
argument : arg
attribute : attr
back : bak
binary : bin
buffer : buf, buff
button : btn
check : chk
command : cmd
communication : com
compare : cmp
configuration : conf
control : ctl, ctrl
convert : conv
counter : cnt
current : crnt
data : dat
database : db
debug : dbg
define : def
delete : del
destination : dst
dialog : dlg
direction : dir
directory : dir
document : doc
double : dbl
driver : drv
environment : env
error : err
flag : flg
for : 4
function : fnc, func
image : img
index : idx
information : inf, info
integer : int
interface : if
item : itm
iterator : it, ite, iter
label : lbl
language : lang
length : len
library : lib
list : lst
manager : mgr, mng, mngr
memory : mem
message : msg
minute : min
number : no, num
object : obj
option : opt
package : pkg
picture : pic, pict
point : pt
pointer : ptr
position : pos, posi
preference : pref
previous : prev
program : prg
ramdom : rnd, rand
receive : rcv
reference : ref
request : req
result : rslt
return : ret
save : sv
second : sec
send : snd
sequence : seq
size : sz
source : src
stack : stk, stck
string : str
system : sys
table : tbl
temporary : tmp, temp
text : txt
to : 2
user : usr
utility : util
value : val
window : wnd
work : wk