使用遞歸方法拼接層級樹

来源:http://www.cnblogs.com/ms27946/archive/2016/08/19/5787261.html
-Advertisement-
Play Games

遞歸演算法這個是非常常見的一個演算法,也是大多數人都會用的,因為它足夠簡單,通俗易懂!在遍歷城市,樹等大腦里反應出來的第一方法大多就屬於這個了 遞歸容易使用,但是也容易用壞,我想"記憶體溢出"這個估計是每個人用遞歸都會碰到的bug,我為什麼還是要寫這方面的知識呢,那是因為文章的最後我有一個問題要問 首先我 ...


遞歸演算法這個是非常常見的一個演算法,也是大多數人都會用的,因為它足夠簡單,通俗易懂!在遍歷城市,樹等大腦里反應出來的第一方法大多就屬於這個了

遞歸容易使用,但是也容易用壞,我想"記憶體溢出"這個估計是每個人用遞歸都會碰到的bug,我為什麼還是要寫這方面的知識呢,那是因為文章的最後我有一個問題要問

首先我先展示我之前寫的一段遞歸拼接層級樹的代碼:

private string ParentColumns(List<Cy_Column> columns, int id)
{
      using (msdb)
      {
           var parents = columns.Where(p => p.parentid == id).ToList();
           StringBuilder sb = new StringBuilder();
           if (parents.Count > 0)
           {
                parents.ForEach(item =>
                {
                        sb.AppendFormat("<tr class=\"text-c\"><td><input type =\"checkbox\" name =\"\" value=\"\" ></td><td>{0}</td><td>{1}</td><td class=\"text-l\">{2}</td><td class=\"f-14\"><a title=\"編輯\" href=\"javascript:;\" onclick=\"system_category_edit('欄目編輯', 'http://localhost:40043/AdminManage/Content/SystemColumnsEdit', '1', '700', '480')\" style=\"text-decoration:none\"><i class=\"Hui-iconfont\">&#xe6df;</i></a> <a title=\"刪除\" href=\"javascript:;\" onclick=\" article_category_del(this, '1' )\" class=\"ml-5\" style=\"text-decoration:none\"><i class=\"Hui-iconfont\">&#xe6e2;</i></a></td></tr>", item.cl_id, item.cl_px, item.cl_name);
                        sb.Append(ChildColumns(columns, item.cl_id, 2));
                  });
                  //釋放記憶體
                  parents = null;
           }
           return sb.ToString();
       }
}
private string ChildColumns(List<Cy_Column> columns, int cl_id, int sub)
        {
            var childs = columns.Where(p => p.parentid == cl_id).ToList();
            StringBuilder sb = new StringBuilder();
            if (childs.Count > 0)
            {
                string substag = "";
                for (int i = 0; i < sub; i++)
                {
                    substag += "";
                }
                childs.ForEach(item =>
                {
                    sb.AppendFormat("<tr class=\"text-c\"><td><input type =\"checkbox\" name =\"\" value=\"\" ></td><td>{0}</td><td>{1}</td><td class=\"text-l\">{3}{2}</td><td class=\"f-14\"><a title=\"編輯\" href=\"javascript:;\" onclick=\"system_category_edit('欄目編輯', '/AdminManage/Content/SystemColumnsEdit', '1', '700', '480')\" style=\"text-decoration:none\"><i class=\"Hui-iconfont\">&#xe6df;</i></a> <a title=\"刪除\" href=\"javascript:;\" onclick=\" article_category_del(this, '1' )\" class=\"ml-5\" style=\"text-decoration:none\"><i class=\"Hui-iconfont\">&#xe6e2;</i></a></td></tr>", item.cl_id, item.cl_px, item.cl_name, substag);
                    sb.Append(ChildColumns(columns, item.cl_id, 2 * sub));
                });
                childs = null;
            }
            return sb.ToString();
        }

這代碼是我修複過的,之前報記憶體溢出的代碼我就不貼了,無非就是我引用了靜態變數list以及StringBuilder類,所以遞歸的時候,記憶體得不到有效釋放,最後就瀑黃頁了。

那麼這個bug的本質我說一下:因為線程在運行函數,都會分配一定的記憶體(棧空間)給它,如方法的參數,變數,返回值等!而這個方法又在不斷的調用自身,所以深度大了,其記憶體又得不到釋放,就超出異常了!所以我這裡用靜態變數就顯得“助紂為虐”了

那麼,問題就來了,如果根據老趙的尾遞歸與Continuation一問中的描述,那我也可以改造成堆記憶體不造成影響的“尾遞歸”形式,我只要用accStr來記錄上一次累加的字元串當作參數傳遞,於是就有了下麵這段異常難看的代碼

private string ChildColumnsRecursively(List<Cy_Column> columns, int cl_id, int sub,string accStr)
        {
            var childs = columns.Where(p => p.parentid == cl_id).Select(p => new { id = p.cl_id, oid = p.cl_px, name = p.cl_name }).ToList();
            StringBuilder sb = new StringBuilder();
            if (childs.Count > 0)
            {
                string substag = "";
                for (int i = 0; i < sub; i++)
                {
                    substag += "";
                }
                childs.ForEach(item =>
                {
                    sb.AppendFormat("<tr class=\"text-c\"><td><input type =\"checkbox\" name =\"\" value=\"\" ></td><td>{0}</td><td>{1}</td><td class=\"text-l\">{3}{2}</td><td class=\"f-14\"><a title=\"編輯\" href=\"javascript:;\" onclick=\"system_category_edit('欄目編輯', '/AdminManage/Content/SystemColumnsEdit', '1', '700', '480')\" style=\"text-decoration:none\"><i class=\"Hui-iconfont\">&#xe6df;</i></a> <a title=\"刪除\" href=\"javascript:;\" onclick=\" article_category_del(this, '1' )\" class=\"ml-5\" style=\"text-decoration:none\"><i class=\"Hui-iconfont\">&#xe6e2;</i></a></td></tr>", item.id, item.oid, item.name, substag);
                    accStr += ChildColumnsRecursively(columns, item.id, 2 * sub, sb.ToString());
                });
                childs = null;
                sb.Append(accStr);
            }
            return sb.ToString();
        }

這怎麼看怎麼不是尾遞歸,連“偽遞歸”都談不上

我心中的改造形式應該是像下麵這樣的偽代碼:

public string ChildColumnsRecursively(List<Cy_Column> columns,int id,string accStr){
      ...Logic Code
      accStr = values;
      return ChildColumnsRecursively(columns,pid,accStr);
}

看老趙的博客,感覺看懂了,但是我想用到我這個案例上,卻又感覺差點東西,不知道那方面還沒理解到位...先擱這吧,以後再慢慢想解決方案


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 最近做項目的時候 用戶提出要上傳大圖片 一張圖片有可能十幾兆 本來用的第三方的上傳控制項 有限製圖片上傳大小的設置 以前設置的是2M 按照用戶的要求 以為直接將限製圖片上傳大小的設置改下就可以了 但是當上傳大圖片的時 總是異常: 錯誤消息:超過了最大請求長度 解決方案: 錯誤原因:asp.net預設最 ...
  • 一、單元測試是什麼 單元測試(unit testing),是指對軟體中的最小可測試單元進行檢查和驗證。對於單元測試中單元的含義,一般來說,要根據實際情況去判定其具體含義,如C語言中單元指一個函數,C#里單元指一個類,圖形化的軟體中可以指一個視窗或一個菜單等。總的來說,單元就是人為規定的最小的被測功能 ...
  • 第一步,建立一個類庫,並且安裝好EntityFramework框架還有CodingFirstUsingFluentApi安裝包 第二步 : 第三步:配置好你的資料庫連接信息,還有你需要操作的資料庫,在確定之前,要先測試連接一下 最後會依據資料庫中的表生成各個類以及Context的操作入口,避免了你依 ...
  • 在ASP.NET MVC中,儘管我們可以直接在頁面中編寫HTML控制項,並綁定控制項的屬性,但更方便的辦法還是使用HtmlHelper中的輔助方法。在View中,包含一個類型為HtmlHelper的屬性Html,它為我們呈現控制項提供了捷徑。 我們今天主要來討論Html.DropDownList的用法,首 ...
  • 最前面的話:Smobiler是一個在VS環境中使用.Net語言來開發APP的開發平臺,也許比Xamarin更方便 ...
  • 在項目中載入這個dll 之後引用 使用方法具體如下圖: 在這裡需要註意到是項目中對interactivity的引用 : ...
  • 決策樹是一種非常經典的分類器,它的作用原理有點類似於我們玩的猜謎游戲。比如猜一個動物: 問:這個動物是陸生動物嗎? 答:是的。 問:這個動物有鰓嗎? 答:沒有。 這樣的兩個問題順序就有些顛倒,因為一般來說陸生動物是沒有鰓的(記得應該是這樣的,如有錯誤歡迎指正)。所以玩這種游戲,提問的順序很重要,爭取 ...
  • 物聯網涉及到各種設備、各種感測器、各種數據源、各種協議,並且很難統一,那麼就要有一個結構性的框架解決這些問題。SSIO就是根據時代發展的階段和現實實際情況的結合產物。 各種數據信息,如下圖: 解決方案,配合SIO使用: 一、SSIO特點 輕型高性能通信框架,適用於多種應用場,輪詢模式、自控模式、併發 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...