.NET Core 數據結構與演算法 1-1

来源:https://www.cnblogs.com/WarrenRyan/archive/2019/08/12/11340496.html

.NET Core 數據結構與演算法 1 1 本節內容為順序表 簡介 線性表是簡單、基本、常用的數據結構。線性表是線性結構的抽象 (Abstract),線性結構的特點是結構中的數據元素之間存在一對一的線性關係。這 種一對一的關係指的是數據元素之間的位置關係,即: 除第一個位置的數據元素外,其它數據元素 ...


.NET Core 數據結構與演算法 1-1

本節內容為順序表

簡介

線性表是簡單、基本、常用的數據結構。線性表是線性結構的抽象 (Abstract),線性結構的特點是結構中的數據元素之間存在一對一的線性關係。這 種一對一的關係指的是數據元素之間的位置關係,即:

  • 除第一個位置的數據元素外,其它數據元素位置的前面都只有一個數據元素;
  • 除後一個位置的數據元素外,其它數據元素位置的後面都只有一個元素。也就是說,數據元素是 一個接一個的排列。因此,可以把線性表想象為一種數據元素序列的數據結構。

本節我們對線性表中的順序表進行一個講解。

保存線性表簡單、自然的方式,就是把表中的元素一個接一個地放進順序的存儲單元,這就是線性表的順序存儲(Sequence Storage)。線性表的順序存儲是指在記憶體中用一塊地址連續的空間依次存放線性表的數據元素, 用這種方式存儲的線性表叫順序表(Sequence List)。說的明確一些也就是說,順序表就是我們所接觸過的數組。

線性表介面IListDS<T>

我們首先對我們會涉及到的函數進行一次封裝,打包進線性表的介面中

interface IListDS<T>
{
    int GetLength();//求長度,我們也可以通過屬性進行操作
    void Clear();//清空操作 
    bool IsEmpty();//判斷線性表是否為空          
    void Append(T item);//向後追加操作
    void Insert(T item, int i);//插入操作          
    T Delete(int i);//刪除操作          
    T GetElem(int i);//取表元         
}

對於C語言,我們很多需要使用函數進行操作,但是在C#中,我們有索引器,屬性等一系列語法糖,因此我們在後面操作的時候會把這些都展示給你們看。

事實上在我們之前的C#初級教程中的綜合練習,就是關於我們的線性表操作,你可以返回去參考你的代碼。

順序表類SeqList<T>

為了方便起見,我們在此處不做可變長度的線性表,如果需要使用可變長度,這裡有那麼一種思路供讀者思考:定義一個欄位為容量(Cap),一個為長度(len),長度是以及存儲的空間大小,容量是總空間,如果長度和容量相等的時候,證明我們的表已經滿了,那麼就向後追加空的數組即可。

不過在這裡我們不討論這種,我們僅僅使用定長的就足夠展示了

class SeqList<T>:IListDS<T>
{
    private int length;//長度
    private int size;
    private int lastIndex;//最後一個元素的索引
    private T[] data;  
    public int Length{get{return lastIndex+1;}}
    //初始化
    public SeqList<T>(int size)
    {
        this.data = new T[size];
        this.lastIndex = -1;
        this.size = size;
    }
    //清除內部元素
    public void Clear()
    {
        this.data = new T[this.size];
        lastIndex = -1;
    }
    //判斷是否為空,只需要判斷最後一個元素的索引是否為-1即可
    public bool IsEmpty()
    {
        return lastIndex==-1?true:false;
    }
    //獲取長度
    public int GetLength()
    {
        return lastIndex + 1;
    }
    //是否已滿
    public bool IsFull()
    {
        return size == lastIndex+1?true:false;
    }
    //向後追加
    public void Append(T item)
    {
        //只需要判斷是否已滿即可
        if(!IsFull())
        {
            data[lastIndex++] = item;
        }
        else
        {
            Console.WriteLine("It is Full");
        }
    }
    //在指定位置插入,index指代位置而不是索引
    public void Insert(T item,int index)
    {
        //首先判斷是否已滿        
        if(IsFull())
        {
            Console.WriteLine("It is Full");
            return;
        }
        if(index<1||index>lastIndex+2)
        {
            Console.WriteLine("error");
            return;
        }
        //最後一位插入
        if (i == last +2)
        {      
            data[i-1] = item; 
        }
        else
        {
            //元素移動
            for (int j = lastIndex; j>= i-1; --j)
            {                     
                data[j + 1] = data[j];                
            }
            data[i-1] = item; 
        }
        lastIndex++;
    }
    public T Delete(int i)         
    {             
        T tmp = default(T); 
 
            //判斷表是否為空             
            if (IsEmpty())             
            {                 
                Console.WriteLine("List is empty");      return tmp;             
            } 
 
            //判斷刪除的位置是否正確             
            // i小於1表示刪除第1個位置之前的元素,
            // i大於last+1表示刪除後一個元素後面的第1個位置的元素。             
            if (i < 1 || i > lastIndex+1)             
            {                 
                Console.WriteLine( "Position is error!");return tmp; 
            } 
            //刪除的是後一個元素             
            if (i == lastIndex+1)             
            {                 
                tmp = data[last--];   
            }  
            //刪除的不是後一個元素
            else               
            {                
                //元素移動                 
                tmp = data[i-1];                 
                for (int j = i; j <= lastIndex; ++j)
                {                     
                    data[j] = data[j + 1];      
                }             
            } 
            //修改表長             
            --lastIndex;             
            return tmp;     
        }
        public T GetElem(int i)
        {
            if(i<1||lastIndex==-1)
            {
                Console.WriteLine("error");
                return;
            }
            return this.data[i-1];
        }
}

在上述代碼中,我們分析一下刪除和插入的操作

演算法的時間複雜度分析:順序表上的刪除操作與插入操作一樣,時間主要消 耗在數據的移動上在第i個位置刪除一個元素,從ai+1到an都要向前移動一個位置,共需要移動n-i個元素,而i的取值範圍為 1≤i≤n,當i等於 1 時,需要移動 的元素個數多,為n-1 個;當i為n時,不需要移動元素。設在第i個位置做刪除 的概率為pi,則平均移動數據元素的次數為(n-1)/2。這說明在順序表上做刪除操 作平均需要移動表中一半的數據元素,所以,刪除操作的時間複雜度為O(n)。

一些額外操作

我們以倒轉為例,事實上我們倒轉的時候,只需要將第一個和最後一個,第二個和倒數第二個以此類推進行交換即可

public void ReversSeqList(SeqList<int> L)         
{             
    int tmp = 0;             
    int len = L.GetLength();             
    for (int i = 0; i<= len/2; ++i)             
    {                 
        tmp = L[i];                 
        L[i] = L[len - i];                 
        L[len - i] = tmp;             
    }     
}

各位可以嘗試一下生成不含重覆值順序表和合併順序表並有序的排列演算法,這裡給出一些思路。

  • 去重:先把順序表 La 的第 1 個元素賦給順序表 Lb,然後從順序表 La 的第 2 個元素起,每一個元素與順序表 Lb 中的每一個元素進行比較,如果不相 同,則把該元素附加到順序表 Lb 的末尾。
  • 合併排序:依次掃描 La 和 Lb 的數據元素,比較 La 和 Lb 當前數據元素的 值,將較小值的數據元素賦給 Lc,如此直到一個順序表被掃描完,然後將未完 的那個順序表中餘下的數據元素賦給 Lc 即可。Lc 的容量要能夠容納 La 和 Lb 兩個表相加的長度。

Github

BiliBili主頁

WarrenRyan's Blog

博客園


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

更多相關文章
  • RBAC許可權框架(Role-Based Access Control)基於角色的許可權訪問控制的框架,通過用戶-角色-許可權的關聯,非常方便的進行許可權管理,在這裡不再說明什麼是RBAC,請自行百度. 謝謝大家的捧場,如文章中有錯誤或者,請聯繫我或者給我發郵件[email protected],修正後 ...
  • 訪問修飾符 訪問修飾符 C# 中常用的有 private、public、protected、internal 4個訪問修飾符。 private:私有訪問是允許的最低訪問級別,私有成員只有在聲明它們的類和結構中才可以訪問。 public:公共訪問是允許的最高訪問級別,對訪問公共成員沒有限制。 prot ...
  • using System; namespace Application { class JianDanGongChang { static void Main(string[] args) { Factory factory=new Factory(); DianNao diannao=factor... ...
  • 項目中經常會格式化數據,轉換數字的使用情況比較多,記錄一下數字轉換的方法! 如果需要轉換為繁體中文,將數組裡的漢字換成繁體中文即可。 1.阿拉伯數字轉換為中文數字 2.中文數字轉換為阿拉伯數字 ...
  • 目錄 "簡介" "產生背景" "使用方式" "TcpSocket" "WebSocket" "UdpSocket" "結尾" 簡介 DotNettySocket是一個.NET跨平臺Socket框架(支持.NET4.5+及.NET Standard2.0+),同時支持TcpSocket、WebSock ...
一周排行
  • 一、背景 代碼實例:https://gitee.com/D_C_L/CurtainEtcAOP.git我們實際系統中有很多操作,是不管做多少次,都應該產生一樣的效果或返回一樣的結果。 例如: 1. 前端重覆提交選中的數據,應該後臺只產生對應這個數據的一個反應結果。 2. 我們發起一筆付款請求,應該只 ...
  • 關鍵字:流程未來節點處理人 工作流快速開發平臺 工作流流設計 業務流程管理 asp.net 開源工作流 業務背景:一個流程在啟動起來後,是可以對一些節點計算出來處理人是誰,流程的走向。對於另外一些節點處理人有可能需要相關的人員調整的。在一些審批的環境下,需要把能夠計算出來的節點處理人在發起時計算出來... ...
  • 簡述 我們做軟體工作的雖然每天都離不開網路,可網路協議細節卻不是每個人都會接觸和深入瞭解。我今天就來和大家一起學習下Socket,並寫一個簡單的聊天程式。 一些基礎類 首先我們每天打開瀏覽器訪問網頁信息都是使用的HTTP/HTTPS協議,而HTTP是通過的TCP建立的連接。TCP底層又是通過的Soc ...
  • 點這裡進入ABP進階教程目錄 在功能按鈕區增加一個自定義按鈕 - Add(創建課程) 添加按鈕 打開展示層(即JD.CRS.Web.Mvc)的\wwwroot\view-resources\Views\Course\Index.js //用以存放Course查詢相關腳本 自帶按鈕已有五個我們再添加一 ...
  • 點這裡進入ABP進階教程目錄 我們嘗試在新增/編輯界面增加一個下拉框用來代替輸入框編輯Status 添加實體 打開領域層(即JD.CRS.Core)的Entitys目錄 //用以存放實體對象添加一個類StatusCode.cs //狀態信息 更新模型 更新查詢視圖模型 打開展示層(即JD.CRS.W ...
  • 在項目視圖中,找到-》輸出 視窗,在視窗中選擇ASP.NET Core Web伺服器,調試項目即可看到執行的sql語句 ...
  • 前言: 通過Fiddler抓取瀏覽器請求數據,相信大家已經都會用了,我們知道Fiddler是通過在本機計算器添加一個預設的代理伺服器來實現的抓包數據的,埠號為:8888。 其實當我們打開Fiddler的設置也可以看到: 然後查看本地計算器的網路代理設置: 基於上面的原理,Fiddler就實現了經過 ...
  • 場景 Winform控制項-DevExpress18下載安裝註冊以及在VS中使用: https://blog.csdn.net/BADAO_LIUMANG_QIZHI/article/details/100061243 在上面已經實現DevExpress的安裝之後,拖拽一個TreeList,然後怎樣給 ...
  • 場景 Winform控制項-DevExpress18下載安裝註冊以及在VS中使用: https://blog.csdn.net/BADAO_LIUMANG_QIZHI/article/details/100061243 DevExpress的TreeList怎樣設置數據源,從實例入手: https:/ ...
  • 場景 在開發中,經常會有一些全局作用域的常量、欄位、屬性、方法等。 需要將這些設置為全局作用域保存且其實例唯一。 註: 博客主頁: https://blog.csdn.net/badao_liumang_qizhi 關註公眾號 霸道的程式猿 獲取編程相關電子書、教程推送與免費下載。 實現 首先新建一 ...
x