閱讀46 返回首頁    go iPhone_iPad_Mac_apple

一步一步寫算法（之單向鏈表）


#include <stdio.h>
#include <malloc.h>

typedef struct node{
	int data;//數據域
	struct node * next;//指針域
}Node;

int main()
{
	Node *pLinkNode=NULL;

	pLinkNode = (Node*)malloc(sizeof(Node));  
      
    pLinkNode->data = 2;  
    pLinkNode->next = NULL;

	printf("%d\n",pLinkNode->data);
	
	return 0;
}

一步一步寫算法（之單向鏈表）


  有的時候，處於內存中的數據並不是連續的。那麼這時候，我們就需要在數據結構中添加一個屬性，這個屬性會記錄下麵一個數據的地址。有了這個地址之後，所有的數據就像一條鏈子一樣串起來了，那麼這個地址屬性就起到了穿線連結的作用。

    相比較普通的線性結構，鏈表結構的優勢是什麼呢？我們可以總結一下：

    （1）單個節點創建非常方便，普通的線性內存通常在創建的時候就需要設定數據的大小

    （2）節點的刪除非常方便，不需要像線性結構那樣移動剩下的數據

    （3）節點的訪問方便，可以通過循環或者遞歸的方法訪問到任意數據，但是平均的訪問效率低於線性表

    那麼在實際應用中，鏈表是怎麼設計的呢？我們可以以int數據類型作為基礎，設計一個簡單的int鏈表：

    （1）設計鏈表的數據結構

  1. typedef struct _LINK_NODE  
  2. {  
  3.     int data;  
  4.     struct _LINK_NODE* next;  
  5. }LINK_NODE;  

    （2）創建鏈表

  1. LINK_NODE* alloca_node(int value)  
  2. {  
  3.     LINK_NODE* pLinkNode = NULL;  
  4.     pLinkNode = (LINK_NODE*)malloc(sizeof(LINK_NODE));  
  5.       
  6.     pLinkNode->data = value;  
  7.     pLinkNode->next = NULL;  
  8.     return pLinkNode;  
  9. }  

    （3）刪除鏈表

  1. void delete_node(LINK_NODE** pNode)  
  2. {  
  3.     LINK_NODE** pNext;  
  4.     if(NULL == pNode || NULL == *pNode)  
  5.         return ;  
  6.           
  7.     pNext = &(*pNode)->next;  
  8.     free(*pNode);  
  9.     delete_node(pNext);   
  10. }  
    （4）鏈表插入數據

  1. STATUS _add_data(LINK_NODE** pNode, LINK_NODE* pDataNode)  
  2. {  
  3.     if(NULL == *pNode){  
  4.         *pNode = pDataNode;  
  5.         return TRUE;  
  6.     }  
  7.       
  8.     return _add_data(&(*pNode)->next, pDataNode);  
  9. }  
  10.   
  11. STATUS add_data(const LINK_NODE** pNode, int value)  
  12. {  
  13.     LINK_NODE* pDataNode;  
  14.     if(NULL == *pNode)  
  15.         return FALSE;  
  16.           
  17.     pDataNode = alloca_node(value);  
  18.     assert(NULL != pDataNode);  
  19.     return _add_data((LINK_NODE**)pNode, pDataNode);  
  20. }  
    （5）刪除數據

  1. STATUS _delete_data(LINK_NODE** pNode, int value)  
  2. {  
  3.     LINK_NODE* pLinkNode;  
  4.     if(NULL == (*pNode)->next)  
  5.         return FALSE;  
  6.       
  7.     pLinkNode = (*pNode)->next;  
  8.     if(value == pLinkNode->data){  
  9.         (*pNode)->next = pLinkNode->next;  
  10.         free(pLinkNode);  
  11.         return TRUE;  
  12.     }else{  
  13.         return _delete_data(&(*pNode)->next, value);  
  14.     }  
  15. }  
  16.   
  17. STATUS delete_data(LINK_NODE** pNode, int value)  
  18. {  
  19.     LINK_NODE* pLinkNode;  
  20.     if(NULL == pNode || NULL == *pNode)  
  21.         return FALSE;  
  22.   
  23.     if(value == (*pNode)->data){  
  24.         pLinkNode = *pNode;  
  25.         *pNode = pLinkNode->next;  
  26.         free(pLinkNode);  
  27.         return TRUE;  
  28.     }         
  29.       
  30.     return _delete_data(pNode, value);  
  31. }  

    （6）查找數據

  1. LINK_NODE* find_data(const LINK_NODE* pLinkNode, int value)  
  2. {  
  3.     if(NULL == pLinkNode)  
  4.         return NULL;  
  5.       
  6.     if(value == pLinkNode->data)  
  7.         return (LINK_NODE*)pLinkNode;  
  8.       
  9.     return find_data(pLinkNode->next, value);  
  10. }  
    （7）打印數據

  1. void print_node(const LINK_NODE* pLinkNode)  
  2. {  
  3.     if(pLinkNode){  
  4.         printf("%d\n", pLinkNode->data);  
  5.         print_node(pLinkNode->next);  
  6.     }  
  7. }  
    （8）統計數據

  1. int count_node(const LINK_NODE* pLinkNode)  
  2. {  
  3.     if(NULL == pLinkNode)  
  4.         return 0;  
  5.           
  6.     return 1 + count_node(pLinkNode->next);  
  7. }  

最後更新：2017-04-03 12:53:45

  上一篇：go 軟件工程---軟件需求分析
  下一篇：go HI3531的DDR3配置流程