數據結構與演算法:線性表——刪除重覆元素

来源:https://www.cnblogs.com/1000sakura/archive/2018/09/24/9696699.html
-Advertisement-
Play Games

線性表是一種隨機存取的結構,和鏈表不同,鏈表順序存取的結構。但是,線性表是一種順序存儲的結構,而鏈表是鏈式存儲結構。兩者都是線性的,但區別不同。 進入主題: 1.假如有一串數據元素,要求刪除其中的重覆元素。 首先想到的是用兩層迴圈,第一層從第一個元素開始,第二層從第一層元素的下一個元素開始。 就是假 ...


線性表是一種隨機存取的結構,和鏈表不同,鏈表順序存取的結構。但是,線性表是一種順序存儲的結構,而鏈表是鏈式存儲結構。兩者都是線性的,但區別不同。

 

進入主題:

1.假如有一串數據元素,要求刪除其中的重覆元素。

首先想到的是用兩層迴圈,第一層從第一個元素開始,第二層從第一層元素的下一個元素開始。

就是假如第一層是ai元素,則第二層就為ai+1元素。

函數實現:

void Purge1(ElemType A[],int &n){//ElemType表示任意數據類型,以後不再說明//n為線性表的長度

  int i=0,j;

  while(i<n){

    j=i+1;

    while(j<n){

      if(A[j]==A[i])

        Deletelist(A,n,j+1);//具體函數實現最後給出

      else

        j++;

    }

    i++;

  }

}

2.如果這些元素是按遞增排列,且數據量很大的話,使用上面的演算法就會造成時間上的浪費。

那要怎麼優化呢?

函數實現:

void Purge2(int *A, int &n) {
  int i = 0, k = 0;//k是重覆的次數
  for (i = 0; i < n - 1; i++)
    if (A[i] != A[i + 1])
      A[i-k+1] = A[i + 1];
    else
      k++;
  n = n - k;
}

經過小規模的測試沒有發現問題。若有有問題可以提出。

經過兩函數的分析,可以看出第一個函數使用的是兩層迴圈,而第二個函數只使用了一層迴圈達到了效果。

避免了不必要的時間浪費。

 

附上Deletelist函數:

void Deletelist(int *A, int &n, int i) {
  int j;
  if (i<1 || i>n)//這條可以無視
    cout << "超出範圍!";
  for (j = i; j < n; j++)
    A[j - 1] = A[j];
  n--;
}

 

碎碎念:本人學生,第一次寫隨筆,也不清楚下次會在什麼時候寫。如果有什麼需要改進的地方,請務必提出來,我在此謝過。


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

-Advertisement-
Play Games
更多相關文章
  • 在上一篇《你真的懂ReentrantReadWriteLock嗎?》中我給大家留了一個引子,一個更高效同時可以避免寫饑餓的讀寫鎖 StampedLock。StampedLock實現了不僅多個讀不互相阻塞,同時在讀操作時不會阻塞寫操作。 為什麼StampedLock這麼神奇?能夠達到這種效果,它的核心 ...
  • Java集合框架中的List與Set 為列表,中在列表中的對象是由順序的排序的,並且是有重覆的對象。 簡單為:有序,有重覆。 為集合,在集合中的對象是不按照順序排列的,並且是沒有重覆的對象的。 簡單為:無序,無重覆。 為無序集合,無序無重覆; 為有序集合,有序有重覆; 案例 知識點 返回迭代的下一個 ...
  • %還是format 1、皇城PK Python中格式化字元串目前有兩種陣營:%和format,我們應該選擇哪種呢? 自從Python2.6引入了format這個格式化字元串的方法之後,我認為%還是format這根本就不算個問題。不信你往下看。 上面的代碼很明顯會拋出一個如下的TypeError: T ...
  • 閑來無事,買了一個雲伺服器來玩玩。想要做的第一件事情就是搭建web項目,查詢了網上的資料得知,部署web項目的步驟是 (1)配置java環境(這裡選擇的是jdk1.8) (2)配置tomcat伺服器(這裡選擇的是tomcat7) (3)上傳web項目 (4)訪問web項目 那麼就開始我們的第一步和第 ...
  • 隨著微處理機技術的發展,人們只需花幾百美元就能買到一個CPU晶元,這個晶元每秒鐘執行的指令比80年代最大的大型機的處理機每秒鐘所執行的指令還多。如果你願意付出兩倍的價錢,將得到同樣的CPU,但它卻以更高的時鐘速率運行。因此,最節約成本的辦法通常是在一個系統中使用集中在一起的大量的廉價CPU。所以,傾... ...
  • 在我們的應用程式中日誌是不可缺少的部分,在Apache中由一個功能無比強大的日誌組件,它提供了方便的日誌記錄,這個開源的項目就是我們慣用的Log4j,jar包我麽們一顆取Apache官網下載最新版本的。log4j下載地址 一.入門篇 1.打開我們的Eclipse新建一個Java項目並且導入Log4j ...
  • 在開源文件大行其道的今天,基於java種種解決方案和框架紛繪踏至而來,猶如浩瀚如海,看不完也學不盡。在採用這些解決方案和框架進行項目開發時,往往會出現當程式卡殼時,既無異常提示信息亦沒有與之對應的日誌輸出的局面。每每出現這樣的困境時,往往只能通過打斷點來一步一步調試跟蹤來解決。更有甚者,基於某一底層... ...
  • 題目介紹:現在輸入一組數據,寫入學生的考試分數。已知學生數為N,學生編號為1到N,且0<N<=30000,每個學生都有一個分數;操作數為M且0<M<5000。輸入第一行為N M,接下來是1行N列數據代表學生的初試分數,接下來是M行操作數據。已知操作有兩種,分為Q和U。一次操作的格式為 C A B,當 ...
一周排行
    -Advertisement-
    Play Games
  • Timer是什麼 Timer 是一種用於創建定期粒度行為的機制。 與標準的 .NET System.Threading.Timer 類相似,Orleans 的 Timer 允許在一段時間後執行特定的操作,或者在特定的時間間隔內重覆執行操作。 它在分散式系統中具有重要作用,特別是在處理需要周期性執行的 ...
  • 前言 相信很多做WPF開發的小伙伴都遇到過表格類的需求,雖然現有的Grid控制項也能實現,但是使用起來的體驗感並不好,比如要實現一個Excel中的表格效果,估計你能想到的第一個方法就是套Border控制項,用這種方法你需要控制每個Border的邊框,並且在一堆Bordr中找到Grid.Row,Grid. ...
  • .NET C#程式啟動閃退,目錄導致的問題 這是第2次踩這個坑了,很小的編程細節,容易忽略,所以寫個博客,分享給大家。 1.第一次坑:是windows 系統把程式運行成服務,找不到配置文件,原因是以服務運行它的工作目錄是在C:\Windows\System32 2.本次坑:WPF桌面程式通過註冊表設 ...
  • 在分散式系統中,數據的持久化是至關重要的一環。 Orleans 7 引入了強大的持久化功能,使得在分散式環境下管理數據變得更加輕鬆和可靠。 本文將介紹什麼是 Orleans 7 的持久化,如何設置它以及相應的代碼示例。 什麼是 Orleans 7 的持久化? Orleans 7 的持久化是指將 Or ...
  • 前言 .NET Feature Management 是一個用於管理應用程式功能的庫,它可以幫助開發人員在應用程式中輕鬆地添加、移除和管理功能。使用 Feature Management,開發人員可以根據不同用戶、環境或其他條件來動態地控制應用程式中的功能。這使得開發人員可以更靈活地管理應用程式的功 ...
  • 在 WPF 應用程式中,拖放操作是實現用戶交互的重要組成部分。通過拖放操作,用戶可以輕鬆地將數據從一個位置移動到另一個位置,或者將控制項從一個容器移動到另一個容器。然而,WPF 中預設的拖放操作可能並不是那麼好用。為瞭解決這個問題,我們可以自定義一個 Panel 來實現更簡單的拖拽操作。 自定義 Pa ...
  • 在實際使用中,由於涉及到不同編程語言之間互相調用,導致C++ 中的OpenCV與C#中的OpenCvSharp 圖像數據在不同編程語言之間難以有效傳遞。在本文中我們將結合OpenCvSharp源碼實現原理,探究兩種數據之間的通信方式。 ...
  • 一、前言 這是一篇搭建許可權管理系統的系列文章。 隨著網路的發展,信息安全對應任何企業來說都越發的重要,而本系列文章將和大家一起一步一步搭建一個全新的許可權管理系統。 說明:由於搭建一個全新的項目過於繁瑣,所有作者將挑選核心代碼和核心思路進行分享。 二、技術選擇 三、開始設計 1、自主搭建vue前端和. ...
  • Csharper中的表達式樹 這節課來瞭解一下表示式樹是什麼? 在C#中,表達式樹是一種數據結構,它可以表示一些代碼塊,如Lambda表達式或查詢表達式。表達式樹使你能夠查看和操作數據,就像你可以查看和操作代碼一樣。它們通常用於創建動態查詢和解析表達式。 一、認識表達式樹 為什麼要這樣說?它和委托有 ...
  • 在使用Django等框架來操作MySQL時,實際上底層還是通過Python來操作的,首先需要安裝一個驅動程式,在Python3中,驅動程式有多種選擇,比如有pymysql以及mysqlclient等。使用pip命令安裝mysqlclient失敗應如何解決? 安裝的python版本說明 機器同時安裝了 ...