.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 ...
一周排行
  • 1. RSA加密與解密 -- 使用公鑰加密、私鑰解密 測試: RSATool myRSA = new RSATool(); Dictionary<string, string> dictK = new Dictionary<string, string>(); dictK = myRSA.GetKe ...
  • 前提 入行已經7,8年了,一直想做一套漂亮點的自定義控制項,於是就有了本系列文章。 GitHub:https://github.com/kwwwvagaa/NetWinformControl 碼雲:https://gitee.com/kwwwvagaa/net_winform_custom_contr ...
  • 1. 在WPF怎麼在UI上添加超級鏈接 這篇文章的目的是介紹怎麼在WPF里創建自定義的HyperlinkButton控制項。很神奇的,WPF居然連HyperlinkButton都沒有,不過它提供了另一種方式用於在UI上添加超級鏈接: 如果需要在超級鏈接里放圖片或其它東西,代碼如下: 這真是很怪,為什麼 ...
  • 系統環境: Windows + .Net Framework 4.0 問題描述: C#連接FTP下載文件時,在部分電腦上有異常報錯,在一部分電腦上是正常的;異常報錯的信息:System.InvalidOperationException: The requested FTP command is n ...
  • 話不多說,上圖: 整體項目結構如圖所示,我的設計初衷是基於.netCore + DI + Vue 打造一個適合初學者的簡捷開發框架。 架構模型採用基於RESTful API風格的前後臺分離框架,總體分為五層:表示層(前端UI)、交互層、業務層、數據訪問層、數據存儲層。 項目中用到的技術如下圖所示: ...
  • 前提 入行已經7,8年了,一直想做一套漂亮點的自定義控制項,於是就有了本系列文章。 GitHub:https://github.com/kwwwvagaa/NetWinformControl 碼雲:https://gitee.com/kwwwvagaa/net_winform_custom_contr ...
  • 初學者經常碰到的,即獲取HTML元素集合,迴圈給元素添加事件。在事件響應函數中(event handler)獲取對應的索引。但每次獲取的都是最後一次迴圈的索引。原因是初學者並未理解JavaScript的閉包特性。 1. <!DOCTYPE HTML> 2. <html> 3. <head> 4. < ...
  • 摘要 本文將介紹如何通過VS2019創建Xamarin.Forms應用程式,以及如何進行調試。 前言 本文介紹Xamarin.Froms應用程式的創建和調試。 開發環境 1.Visual Studio 2019 2.Xamarin.Forms 3.6.0.344457 創建 1.打開VS2019,選 ...
  • 本次應用DevExpress和C#語言製作了一個批量添加水印的程式,看界面效果圖: 界面中既可以進行文字水印添加,也可以圖片水印添加,同時還可以對水印的位置進行設置,比較實用! 文字水印的具體添加情況,看圖: 還可以文字的預覽: 整個文字水印的預覽: 同時圖片的水印預覽: 最後顯示下圖片的水印效果: ...
  • 一、Swagger是什麼 Swagger 是一款RESTFUL介面的、基於YAML、JSON語言的文檔線上自動生成、代碼自動生成的工具。 二、如何在項目中加入Swagger Swagger安裝引用 右鍵Web項目依賴項>管理NuGet程式包>在搜索框輸入"Swashbuckle.AspNetCore ...
x