.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

博客園


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

更多相關文章
  • 伺服器數量過多,每次採用ip+埠 輸入密碼的方式登錄比較繁瑣,就採用了免密碼和埠登錄。 普通登錄方式: ssh p 27479 [email protected] 更換免密碼登錄: 本地操作: 本地的公鑰位置: ~/.ssh/id_rsa.pub ~/.ssh目錄下創建一個config文件, ...
  • 廣告檢索服務 功能介紹 媒體方(手機APP打開的展示廣告,走在路上看到的大屏幕廣告等等) 請求數據對象實現 從上圖我們可以看出,在媒體方向我們的廣告檢索系統發起請求的時候,請求中會有很多的請求參數信息,他們分為了三個部分,我們來編碼封裝這幾個參數對象信息以及我們請求本身的信息。Let's code. ...
  • Filter 過濾器 概念:當訪問伺服器的某些資源時,過濾器可以將請求先進行攔截,在完成了一定的特殊功能後,可以讓此請求繼續執行。 一. 實現步驟 1、實現Filter介面 2、重寫方法 3、配置web.xml 二. 過濾器的url配置 完全匹配:攔截指定資源 擴展名匹配: .擴展名,攔截指定尾碼的 ...
  • xl_echo編輯整理,歡迎轉載,轉載請聲明文章來源。歡迎添加echo微信(微信號:t2421499075)交流學習。 百戰不敗,依不自稱常勝,百敗不頹,依能奮力前行。——這才是真正的堪稱強大!! 參考文章列表: "Java併發編程:Synchronized底層優化(偏向鎖、輕量級鎖)" "輕量級鎖 ...
  • 以連接mysql資料庫為例 一 安裝組件 Microsoft.EntityFrameworkCore Microsoft.EntityFrameworkCore.Relational Microsoft.EntityFrameworkCore.Tools MySqlConnector Pomelo. ...
  • 1.業務場景:用戶登錄,收到消息通知,審批業務,根據配置的流程繼續流轉,最終審核發送回給申請人(終審同意結束,終審不同意申請人可以繼續修改提交)。 2.思路過程: 3..資料庫設計: 4.代碼過程: ...
  • 上接(abp(net core)+easyui+efcore實現倉儲管理系統——使用 WEBAPI實現CURD (十二)),在這一篇文章中我們創建視圖模型、列表視圖、添加菜單。 ...
  • 1.前言 ASP.NET Core應用程式可以配置和啟動主機(Host)。主機負責應用程式啟動和生命周期管理。通用主機用於無法處理HTTP請求的應用程式。通用主機的用途是將HTTP管道從Web主機API中分離出來,從而啟用更多的主機方案。 基於通用主機的消息、後臺任務和其他非HTTP工作負載可從橫切 ...
一周排行
  • 背景 習慣使用markdown的人應該都知道Typora這個神器,它非常簡潔高效。雖然博客園的線上markdown編輯器也不錯,但畢竟是網頁版,每次寫東西需要登錄系統-進後臺-找到文章-編輯-保存草稿。。。非常難受。。。 但是使用Typora來寫的話,文章圖片又是個問題,本地寫完粘貼到網站上,圖片全 ...
  • 案例:修改預設線程個數 1.NameValueCollection System.Collections.Specialized.NameValueCollection collection = new System.Collections.Specialized.NameValueCollecti ...
  • // from https://stackoverflow.com/questions/35381238/how-to-use-custom-fonts-in-emgucv string text = "塗聚文(Geovin Du)"; // 下麵定義一個矩形區域 int rectWidth = t ...
  • 場景 ASP.NET中新建Web網站並部署到IIS上(詳細圖文教程): https://blog.csdn.net/BADAO_LIUMANG_QIZHI/article/details/107199747 前面講過將ASP.NET的項目部署到本機的IIS上。 但是如果將其部署到伺服器上Window ...
  • 在不同的區域中使用Convert.ToDouble可能會產生問題。 string str = "20.0"; double val = Convert.ToDouble(str); 比如在某些區域語言中得到的結果是200,如: Thread.CurrentThread.CurrentCulture ...
  • 1、前言 ​ 不知道你是否對.NET裡面的定時器產生過一些疑問,以下是武小棧個人的一些總結。 2、官方介紹 在.NET的框架之內定時器有四種,先看一下微軟官方對他們各自特點介紹: System.Timers.Timer,它將觸發事件,並定期在一個或多個事件接收器中執行代碼。 類旨在用作多線程環境中基 ...
  • 筆試考試系統需求分析 1. 引言 1.1編寫目的 項目需求分析目的是使用戶和軟體開發者雙方對項目開發目標有一個共同的理解,便於對軟體開發各個過程的控制與管理,通過對項目開發目標的描述,使開發人員能夠正確理解用戶需求,明確該系統應具有的功能。性能與界面要求。 需求分析作為項目開放的基礎和依據,其預期讀 ...
  • 使用Topshelf部署.net core windows服務 首先新建一個.net core的模板worker程式 過程 略 打開Program.cs namespace TopshelfDemo { public class Program { public static void Main(s ...
  • xaml裡面使用很簡單 xmlns:i="http://schemas.microsoft.com/xaml/behaviors" <i:Interaction.Behaviors> <i:MouseDragElementBehavior/> </i:Interaction.Behaviors> 後 ...
  • Application Insignhts是微軟開發的一套監控程式。他可以對線上的應用程式進行全方位的監控,比如監控每秒的請求數,失敗的請求,追蹤異常,對每個請求進行監控,從http的耗時,到SQL查詢的耗時,完完整整的被記錄下來。當對程式進行優化跟排錯時非常好使。它原來是visualstudio ...