在php中實現鏈表（php實現鏈表操作）

本文目錄一覽：

• 1、php不支持指針，怎麼實現單向鏈表
• 2、PHP判斷鏈表是否有環
• 3、PHP在伺服器端如何建立鏈表保存用戶信息？
• 4、深入PHP中的HashTable結構詳解
• 5、PHP實現：如何在只給定單鏈表中某個結點的指針的情況下刪除該結點

php不支持指針，怎麼實現單向鏈表

你可以參照java實現的方法,在類里自包含一個類,呵呵

——解決方案——————–

PHP判斷鏈表是否有環

判斷是否帶環：用快慢指針。快指針每走兩步，慢指針走一步，如果兩者在某個點處相。

遇，則鏈錶帶環。

下邊給出函數的實現代碼：

typedef struct LinkNode{    DataType data;    struct LinkNode *next;}LinkNode,*pLinkNode;typedef struct LinkList{    LinkNode *pHead;}LinkList,*pLinkList;pLinkNode isCircle(pLinkList plist){    assert(plist);    if (NULL == plist-pHead)    {        printf(“鏈表為空\n”);        return NULL;    }    pLinkNode fast = plist-pHead;    pLinkNode slow = plist-pHead;    while (fast fast-next)    {        fast = fast-next-next;        slow = slow-next;        if (fast == slow)            return fast;    }    return NULL;}

如果

如果鏈錶帶環，看下邊的圖：

代碼：

pLinkNode firstCrossNode(pLinkList plist){    assert(plist);    if (NULL == plist-pHead)    {        printf(“鏈表是空\n”);        return NULL;    }    pLinkNode ret = isCircle(plist);    if (ret == NULL)    {        printf(“鏈表不帶環\n”);        return NULL;    }    pLinkNode fast = plist-pHead;    pLinkNode slow = ret;    while (fast)    {        fast = fast-next;        slow = slow-next;        if (fast == slow)            return fast;    }}

PHP在伺服器端如何建立鏈表保存用戶信息？

你可以以文件的形式保存

也就是用戶上傳了信息，把這些信息生成一個html性質的文件保存到某個目錄文件中，文件以會員ID命名，這個目錄最好是按當天日期命名，如果用戶要讀取的話直接顯示這個文件裡邊的內容就行了。

然後用戶退出後刪除這個文件，有些用戶是直接關瀏覽器的，就不會執行退出刪除文件的操作，這樣會遺留一些文件在目錄中，所以定期清除這個用戶信息目錄下的文件，如果是按照日期命名的，把不是當天的日期目錄刪除就行；

深入PHP中的HashTable結構詳解

深入PHP中的HashTable結構詳解

深入PHP中的HashTable結構詳解

對php內核有一定了解的人應該都知道php的精髓就是HashTable，HashTable在php的實現中無處不在。包括php的數組、什麼全局變數、局部變數的作用域等等，php的hashtable拆開來說就是四部分：

hash函數：用的是time33的散列函數，將一個字元串的key轉換成一個數字

一個C數組：用來儲存桶(buckets)的

兩個雙向的鏈表：第一個雙向鏈表是數組的每個元素（桶bucket）是一個雙向鏈表，這樣做是為了解決hash衝突；第二個雙向鏈表是數組將每一個桶(bucket)連接起來，這裡要連接的也就是第一個雙向鏈表的鏈表頭，這樣做是為了遍歷整個hash表用的,鳥哥有篇blog是講php的foreach的，這裡這樣設計就是給foreach用的==《深入理解PHP之數組(遍歷順序)》

我這裡不再說hashtable的struct和bucket的`struct了，因為下面的推薦鏈接幾乎都講了，我不覺得我能描述和說的比他們好，每個人的水平不一樣，我就以我現在的技術水平來描述，所以我就只把我整理的一些東西記錄一下

下面是php中hash實現的兩個文件：zend_hash.c zend_hash.h。這兩個文件裡面實現了一堆的api，也引申出了一堆的api，下面是實現出來的api的原型

複製代碼 代碼如下:

ZEND_API ulong zend_hash_func(const char *arKey, uint nKeyLength)

ZEND_API ulong zend_get_hash_value(const char *arKey, uint nKeyLength)

ZEND_API int _zend_hash_init(HashTable *ht, uint nSize, hash_func_t pHashFunction, dtor_func_t pDestructor, zend_bool persistent ZEND_FILE_LINE_DC)

ZEND_API void zend_hash_set_apply_protection(HashTable *ht, zend_bool bApplyProtection)

ZEND_API int _zend_hash_add_or_update(HashTable *ht, const char *arKey, uint nKeyLength, void *pData, uint nDataSize, void **pDest, int flag ZEND_FILE_LINE_DC)

ZEND_API int _zend_hash_quick_add_or_update(HashTable *ht, const char *arKey, uint nKeyLength, ulong h, void *pData, uint nDataSize, void **pDest, int flag ZEND_FILE_LINE_DC)

ZEND_API int _zend_hash_index_update_or_next_(HashTable *ht, ulong h, void *pData, uint nDataSize, void **pDest, int flag ZEND_FILE_LINE_DC)

ZEND_API int zend_hash_rehash(HashTable *ht)

static int zend_hash_do_resize(HashTable *ht)

ZEND_API int zend_hash_del_key_or_index(HashTable *ht, const char *arKey, uint nKeyLength, ulong h, int flag)

ZEND_API void zend_hash_destroy(HashTable *ht)

ZEND_API void zend_hash_clean(HashTable *ht)

static Bucket *zend_hash_apply_r(HashTable *ht, Bucket *p)

ZEND_API void zend_hash_graceful_destroy(HashTable *ht)

ZEND_API void zend_hash_graceful_reverse_destroy(HashTable *ht)

ZEND_API void zend_hash_apply(HashTable *ht, apply_func_t apply_func TSRMLS_DC)

ZEND_API void zend_hash_apply_with_argument(HashTable *ht, apply_func_arg_t apply_func, void *argument TSRMLS_DC)

ZEND_API void zend_hash_apply_with_arguments(HashTable *ht TSRMLS_DC, apply_func_args_t apply_func, int num_args, …)

ZEND_API void zend_hash_reverse_apply(HashTable *ht, apply_func_t apply_func TSRMLS_DC)

ZEND_API void zend_hash_copy(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, void *tmp, uint size)

ZEND_API void _zend_hash_merge(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, void *tmp, uint size, int overwrite ZEND_FILE_LINE_DC)

static zend_bool zend_hash_replace_checker_wrapper(HashTable *target, void *source_data, Bucket *p, void *pParam, merge_checker_func_t merge_checker_func)

ZEND_API void zend_hash_merge_ex(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, uint size, merge_checker_func_t pMergeSource, void *pParam)

ZEND_API int zend_hash_find(const HashTable *ht, const char *arKey, uint nKeyLength, void **pData)

ZEND_API int zend_hash_quick_find(const HashTable *ht, const char *arKey, uint nKeyLength, ulong h, void **pData)

ZEND_API int zend_hash_exists(const HashTable *ht, const char *arKey, uint nKeyLength)

ZEND_API int zend_hash_quick_exists(const HashTable *ht, const char *arKey, uint nKeyLength, ulong h)

ZEND_API int zend_hash_index_find(const HashTable *ht, ulong h, void **pData)

ZEND_API int zend_hash_index_exists(const HashTable *ht, ulong h)

ZEND_API int zend_hash_num_elements(const HashTable *ht)

ZEND_API int zend_hash_get_pointer(const HashTable *ht, HashPointer *ptr)

ZEND_API int zend_hash_set_pointer(HashTable *ht, const HashPointer *ptr)

ZEND_API void zend_hash_internal_pointer_reset_ex(HashTable *ht, HashPosition *pos)

ZEND_API void zend_hash_internal_pointer_end_ex(HashTable *ht, HashPosition *pos)

ZEND_API int zend_hash_move_forward_ex(HashTable *ht, HashPosition *pos)

ZEND_API int zend_hash_move_backwards_ex(HashTable *ht, HashPosition *pos)

ZEND_API int zend_hash_get_current_key_ex(const HashTable *ht, char **str_index, uint *str_length, ulong *num_index, zend_bool duplicate, HashPosition *pos)

ZEND_API int zend_hash_get_current_key_type_ex(HashTable *ht, HashPosition *pos)

ZEND_API int zend_hash_get_current_data_ex(HashTable *ht, void **pData, HashPosition *pos)

ZEND_API int zend_hash_update_current_key_ex(HashTable *ht, int key_type, const char *str_index, uint str_length, ulong num_index, int mode, HashPosition *pos)

ZEND_API int zend_hash_sort(HashTable *ht, sort_func_t sort_func, compare_func_t compar, int renumber TSRMLS_DC)

ZEND_API int zend_hash_compare(HashTable *ht1, HashTable *ht2, compare_func_t compar, zend_bool ordered TSRMLS_DC)

ZEND_API int zend_hash_minmax(const HashTable *ht, compare_func_t compar, int flag, void **pData TSRMLS_DC)

ZEND_API ulong zend_hash_next_free_element(const HashTable *ht)

void zend_hash_display_pListTail(const HashTable *ht)

void zend_hash_display(const HashTable *ht)

;

PHP實現：如何在只給定單鏈表中某個結點的指針的情況下刪除該結點

p是要刪除的結點，q是p的前一個結點 q-next = p-next;//刪除的結點的後一結點的首地址賦值給刪除的結點的前一結點的next p-next-prior = q;//刪除的結點的後一結點的prior指向刪除的結點的前一結點的首地址