數據結構與演算法(二) 線性表一

来源:https://www.cnblogs.com/haohuihai/archive/2020/06/28/13199394.html

線性表: 定義:由零個或多個數據元素組成的有限序列。 首先他是一個序列,也就是說元素之間是有先來後到 若元素存在多個,則第一個元素無前驅,最後一個元素無後繼,其他元素有且只有一個前驅和後繼 另外,線性表強調是有限的。 數學語言的定義: 若將線性表記為(a1,...,ai-1,ai,ai+1,...a ...


線性表:

定義:由零個或多個數據元素組成的有限序列。

  • 首先他是一個序列,也就是說元素之間是有先來後到
  • 若元素存在多個,則第一個元素無前驅,最後一個元素無後繼,其他元素有且只有一個前驅和後繼
  • 另外,線性表強調是有限的。

數學語言的定義:

若將線性表記為(a1,...,ai-1,ai,ai+1,...an),則表中ai-1領先於ai,ai領先於ai+1,稱ai-1是ai的直接前驅元素,ai+1是ai的直接後繼元素。

所以線性表元素的個數n定義線性表的長度,當n=0是,則稱為空表

例如:公司的組織架構是否屬於線性關係?  否

抽象數據類型:

數據類型:是指一組性質相同的值的集合及定義在此集合上的一些操作的總稱。

例如很多編程語言的整型,浮點型,字元型這些指的就是數據類型。

例如在C語言中,按照取值的不同,數據類型可以分為兩類:

原子類型:不可以在分解的基本類型,例如整型、浮點型、字元型等。

結構類型:由若幹個類型組合而成的,是可以在分解的,例如整型是由若幹個整型數據組成的

抽象:是指抽取的事務具有普遍性的本質。他要求抽出問題的特征而忽略非本質的細節,是對具體事物的一個概括,抽象是一種思考問題的方式,它隱藏了繁雜的細節。

我們對已有的數據類型進行抽象,就有了抽象數據類型。

抽象數據類型是指一個數學模型及定義在該模型上的一組操作。抽象數據類型的定義僅僅取決於它的一組邏輯特性,而與其在電腦內部如何表示和實現無關。

例如:1+1=2,在不同CPU的處理上可能不一樣,但由於其定義的數學特性相同,所以在電腦編程者來看,他們都是相同的。

 "抽象"的意義在於數據類型的數學抽象特性。

而且,抽象數據類型不僅僅是指那些已經定義並實現的數據類型,還可以是電腦編程者在設計軟體程式時自己定義的數據類型。

 抽象數據類型的標準格式:

ADT 抽象數據類型名

Data

  數據元素之間邏輯關係的定義

Operation

  操作

endADT 

 線性表的抽象數據類型

線性表的抽象數據類型定義:

ADT 線性表(List)

Data

線性表的數據對象集合為{a1,a2,...,an},每個元素的類型均為DataType。其中,除第一個元素a1外,每一個

元素有且只有一個直接前驅元素,除了最後一個元素an之外,每一個元素有且只有一個直接後繼元素。

數據元素之間的關係是一對一的關係

 Operation

 InitList(*L):初始化操作,建立一個空的線性表L。

ListEmpty(L):判斷線性表是否為空表,若線性表為空,返回true,否則返回false。

ClearList(*L):將線性表清空。

GetElem(L,i,*e):將線性表L中的第i個位置元素值返回給e。

LocateElem(L,e):線上性表L中查找與給定值e相等的元素,如果查考成功,返回該元素在表中序號表示成功;否則,返回0表示失敗。

ListInsert(*L,i,e):線上性表L中第i個位置插入新元素e。

ListDelete(*L,i,*e):刪除線性表L中第i個位置元素,並用e返回其值。

ListLength(L):返回線性表L的元素個數。

endADT‘

對於不同的應用,線性表的基本操作是不同的,上述操作時最基本的,對於實際問題中涉及的關於線性表的更複雜操作,完全可以用這些基本操作的組合來實現

 例如集合A{A,C,D},集合B{A,C,W},

 其實仔細思考一下,我們只需要迴圈遍歷集合B中的每個元素,判斷當前元素是否在A中,若不存在,則插入A中即可。

需要的基本操作組合:ListLength(L);GetElem(L,i,*e);LocateElem(L,e);ListInsert(*L,i,e);

//La表示A集合,Lb表示B集合

void unionL(List *La,list Lb)

{

  int La_len,Lb_len,i;

  ElemType e;

  La_len=ListLength(*La);

  Lb_len=ListLength(Lb);

  for(i=1;i<Lb_len;i++)
  {
    GetElem(Lb,i,&e);
    if(!LocateElem(*La,e))
    {
      ListInsert(La,++La_len,e);
    }
  }
}

我們可以想象,線性表有兩種物理存儲結構:順序存儲結構和鏈式存儲結構

線性表的順序存儲結構,指的是用一段地址連續的存儲單元依次存儲線性表的數據元素

線性表(a1,a2,...,an)的順序存儲如下:

a1 a2 a3 a4 ... ai-1 ai ai+1 ... an

 

 

線性表順序存儲結構代碼:

#define MAXSIZE 20

typedef int ElemType;

typedef struct

{

  ElemType data[MAXSIZE];

  int length;//線性表當前的長度

} SqList;

這裡我們封裝了一個結構,事實上就是對數組進行封裝,增加當前長度的變數。

 總結:順序存儲結構封裝需要三個屬性:

  • 存儲空間的起始位置,數組data,它的存儲位置就是線性表存儲空間的存儲位置。
  • 線性表的最大存儲容量:數組長度MAXSIZE.
  • 線性表的當前長度:length.

註意:數組的長度與線性表的當前長度需要區分:數組的長度是存放線性表的存儲空間的總長度,一般初始化後不變。而線性表的當前長度是線性表中元素的個數,是會發生變化的。

地址計算方法:

數組是從0開始計算,而線性表是從1開始

 假設ElemType占用的是c個存儲單元(位元組),那麼線性表中第i+1個數據元素和第i個數據元素的存儲關係是(LOC表示獲得存儲位置的函數):LOC(ai+1)=LOC(ai)+c

 所以對於第i個數據元素ai的存儲位置可以由a1推算得出:LOC(ai)=LOC(a1)+(i-1)*c

元素 a1 a2 ... ai-1 ai ... an 空閑空間
下標 0 1 ... i-2 i-1 ... n-1  

 

 

 

 根據這個公式,我們可以計算出線性表中任意位置的地址,不管它是第一個還是最後一個,都是相同的時間,那麼它的存儲時間性能當然就為O(1),我們通常稱為隨機存儲結構。

例如:實現GetElem的具體操作,即將線性表L中的第i個位置元素值返回,註意返回類型Status是一個整型

#define OK 1

#define ERROR 0

#define TRUE 1

#define FALSE 0

typedef int Status;

//Status是函數的類型,其值是函數結果的狀態代碼,如OK等。

//初始條件:順序線性標L已經存在,1<=i<=ListLength(L)

//操作結果:用e返回L中第i個數據元素的值。

Status GetElem(SqList L,int i,ElemType *e)

{

  if(L.length==0||i<1||i>L.length)

  {

    return ERROR;

  }

  *e=L.data[i-1];

return OK;

}

 插入操作:

線性表的順序存儲結構具有隨機存儲結構的特點,時間複雜度為O(1)。

如果要實現ListInsert(*L,i,e),既線上性表L中的第i個位置插入新元素e,代碼如何實現。

 實現插入操作的思路:

  • 如果插入位置不合理,拋出異常;
  • 如果線性表的長度大於等於數組長度則拋出異常或動態增加數組容量;
  • 從最後一個元素開始向前遍歷到第i個位置,分別將他們都向後移動一個位置;
  • 將要插入的元素填入第i個位置;
  • 線性表長度+1;
/*初始條件:順序線性表L已存在,1<=i<=ListLength(L),*/

/*操作結果:在L中第i個位置之前插入新的數據元素e,L長度+1*/

Status ListInsert (SqList *L,int i,ElemType e)

{

  int l;

  if(L->length==MAXSIZE)//順序線性表已滿

  {

  return ERROR;

  }

  if(i<1||i>L->length+1)//當i不在範圍內時

  {

  return ERROR;

  }

  if(i<=L-<length)//若插入數據位置不在表尾

  {

//若要插入數據,則向後移動一位

    for(k=L->length-1;k>=i-1;k--)
    {

     L->data[k+1]=L->data[k];

    }
  }

L->data[i-1]=e;

L->length++;

return OK;

}

上海華頌商旅汽車租賃服務有限公司


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

更多相關文章
  • 前言 互聯網大廠新入職員工各職級薪資對應表(技術線)~ 最新阿裡、騰訊、華為、位元組跳動等大廠的薪資和職級對比 上面的表格不排除有很極端的收入情況,但至少能囊括一部分同職級的收入。這個表是“技術線”新入職員工的職級和薪資情況,非技術線(如產品、運營、銷售等)以及老員工的情況會和圖中的範圍有所出入。以校 ...
  • 1.手寫實現ArrayList: 2.手寫實現LinkedList: ...
  • 第一步,下載安裝git 打開 [git官網] https://git-scm.com/,下載git對應操作系統的版本。 所有東西下載慢的話就可以去找鏡像!官網下載太慢,我們可以使用淘寶鏡像下載:http://npm.taobao.org/mirrors/git-for-windows/下載對應的版本 ...
  • import pandas a=pandas.DataFrame({'Country': ['China,US', 'Japan,EU', 'UK,Australia', 'Singapore,Netherland'], 'Number': [100, 150, 120, 90], 'Value': ...
  • 最近也有很多人來向小編"請教",他們大都是一些剛入門的新手,還不瞭解這個行業,也不知道從何學起,開始的時候非常迷茫,實在是每天回覆很多人也很麻煩,所以在這裡小編總結一些基礎課程: 基礎階段 首先是基礎階段,在基礎階段,我們必須掌握Java基礎,Mysql資料庫,Oracle資料庫,JDBC,Linu ...
  • JAVA中繼承和多態的理解 繼承的概念 繼承是java面向對象編程技術的一塊基石,因為它允許創建分等級層次的類。 繼承就是子類繼承父類的特征和行為,使得子類對象(實例)具有父類的實例域和方法,或子類從父類繼承方法,使得子類具有父類相同的行為。 類的繼承格式 在Java中通過extends關鍵字可以申 ...
  • 學習記錄1--Springboot的Maven自定義打包 在以往的開發中,Springboot應用預設打成一個jar,雖然方便但是會有很多問題,比如不方便修改配置文件,修改一個處代碼就要更新整包等等,而maven中也有這樣的插件可以給我們提供幫助 複製引用依賴插件 <plugin> <groupId ...
  • 切片 import numpy as np # 使用切片參數start:stop:step來進行切片操作 a_array=np.arange(10) print(a_array,'\n') b_array=a_array[1:10:2] print(b_array,'\n') c_array=a_a ...
一周排行
  • C#6.0新特性 C#7.0新特性 C#8.0新特性 ...
  • out變數 可以直接在方法中使用out申明變數 int.TryParse("123", out var result); 元組 元組的申明 var alphaBetaStart = (alpha: "a", beta: "b"); Console.WriteLine($"{alphaBetaStar ...
  • 在我們的項目中,通常會把數據存儲到關係型資料庫中,比如Oracle,SQL Server,Mysql等,但是關係型資料庫對於併發的支持並不是很強大,這樣就會造成系統的性能不佳,而且存儲的數據多為結構化數據,對於非結構數據(比如文本)和半結構化數據(比如JSon) 就顯得不夠靈活,而非關係型資料庫則很 ...
  • 這幾天終於弄懂了async和await的模式,也搞明白了一直在心裡面積壓著的許多問題,所以寫一篇博客來和大家分享一下。 關於非同步機制我認為只要記住的以下幾點,就可以弄明白了: 1.我認為async和awwait兩個修飾符中最關鍵的是await,async是由於方法中包含await修飾符之後才在方法定 ...
  • 實現WCF的步驟如下: 設計服務協議 實現服務協議 配置服務 托管服務 生成客戶端(這步可有可無) 設計或定義服務協議要麼使用介面,要麼使用類。建議介面,使用介面好處一堆例如修改介面的實現,但是服務協定有無需改變。 設計服務協議,介面上使用 ServiceContractAttribute ,方法上 ...
  • 什麼鬼,我的CPF快寫好了,你居然也要搞跨平臺UI框架?什麼Maui? 之前怎麼不早說要搞跨平臺UI框架呢?看到谷歌搞flutter眼紅了?明年年底發佈?又搞這種追別人屁股的爛事情。 什麼MVU模式?模仿Dart?用C#代碼直接寫UI的模式和我的CPF很像啊。 當初我考慮過XML,Json來描述UI ...
  • 寫在前面 Docker作為開源的應用容器引擎,可以讓我們很輕鬆的構建一個輕量級、易移植的容器,通過Docker方式進行持續交付、測試和部署,都是極為方便的,並且對於我們開發來說,最直觀的優點還是解決了日常開發中的環境配置與部署環境配置上的差異所帶來的種種疑難雜症,從此推脫產品的措辭也少了——“我電腦 ...
  • 一、前言 回顧:認證授權方案之授權初識 從上一節中,我們在對授權系統已經有了初步的認識和使用,可以發現,asp.net core為我們提供的授權策略是一個非常強大豐富且靈活的認證授權方案,能夠滿足大部分的授權場景。 在ConfigureServices中配置服務:將授權服務添加到容器 public ...
  • 項目背景: 工作之餘兼職一家公司(方向是工業4.0)給做IM系統,主要功能包括:文字、 圖片、文件傳輸、遠程協助、視頻語音等等。這些功能都是基於群會話, 比如工廠操作工人遇到問題,請求遠程專家,這個初級專家不能解決問題,會邀請一個高級專家進來解決。開發過程中主要遇到的問題是視頻和語音這一塊,像其他的... ...
  • 基礎概念 Microsoft中間語言(MSIL),也成為通用中間語言(CIL),是一組與平臺無關的指令,由特定於語言的編譯器從源代碼生成。MSIL是獨立於平臺的,因此,他可以在任何公共語言基礎架構支持特定的環境上執行。 通過JIT編譯器將MSIL轉換為特定電腦環境的特定機器代碼。這是在執行MSIL ...