二级指针在链表中的应用

谁践踏了优雅 2023-01-12 04:20 68阅读 0赞

重读了两本书：Stephen A.Maguire的《**编程精粹：Microsoft编写优质无错C程序秘诀**》和David R. Hanson的《**C语言接口与实现：创建可重用软件的技术**》。两本书都有对链表的操作。

假设有如图所示的链表，链表节点的`pb`成员指向一个缓冲块，删除节点函数根据缓冲块的首地址，找到节点并删除节点:  
![链表举例][20210127212545217.png_pic_center]

《编程精粹》使用一个变量`pbiPrev`来保存前一个节点位置，并且要处理删除的是第一个节点A这种边界条件：

void FreeBlockInfo(byte *pbToFree)
    {
        
    	blockinfo *pbi, *pbiPrev;
    	
        pbiPrev = NULL;
    	for(pbi = pbiHead; pbi != NULL; pbi = pbi->pbiNext)
    	{
        
    		if(fPtrEqual(pbi->pb, pbToFree)
    		{
        
    			if(pbiPrev == NULL)
    				pbiHead = pbi->pbiHead;
    			else
    				pbiPrev->pbiNext = pbi->pbiNext;
    			break;
    		}
    		pbiPrev = pbi;
    	}
    	
    	/*如果pbi是NULL, 说明参数pbToFree非法*/
    	ASSERT(pbi != NULL);
    	
    	/*在释放前破坏掉要释放内存中的内容*/
    	memset(pbi, bGarbage, sizeof(blockinfo));
    	free(pbi);
    }

《C语言接口与实现》使用了二级指针，可以很巧妙的省掉变量`pbiPrev`以及边界判断：

void FreeBlockInfo(byte *pbToFree)
    {
        
        blockinfo **ppbi, *pbiFind;
        
        pbiFind = NULL;
        for(ppbi = &pbiHead; *ppbi != NULL; ppbi = &(*ppbi)->pbiNext)
        {
        
            if(fPtrEqual((*ppbi)->pb, pbToFree)
    		{
        
                pbiFind = *ppbi;
                *ppbi = (*ppbi)->pbiNext;
                break;
            }
        }
        
        /*如果pbiFind是NULL, 说明参数pbToFree非法*/
    	ASSERT(pbiFind != NULL);
    	
    	/*在释放前破坏掉要释放内存中的内容*/
    	memset(pbiFind, bGarbage, sizeof(blockinfo));
    	free(pbiFind);
    }

[20210127212545217.png_pic_center]: /images/20221119/b629e6ea25334806939ead4ed309a530.png