數(shù)據(jù)結(jié)構(gòu)(Java版)線性表1(順序表)

數(shù)據(jù)結(jié)構(gòu)(Java版)線性表1(順序表)數(shù)據(jù)結(jié)構(gòu)(Java版)線性表1(順序表)全文共14頁，當前為第1頁。線性表

線性表（LinearList）是一種可以在任意位置進行插入和刪除數(shù)據(jù)元素操作的、由n(n>=0）個相同類型數(shù)據(jù)元素a0，a1，…ai，ai+1…an-1組成的一個有限序列。線性表的邏輯結(jié)構(gòu)是線性結(jié)構(gòu)；線性表的存儲結(jié)構(gòu)可以有多種，最常用的兩種是：順序存儲結(jié)構(gòu)和鏈接存儲結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)(Java版)線性表1(順序表)全文共14頁，當前為第2頁。線性表的抽象數(shù)據(jù)類型

抽象數(shù)據(jù)類型(ADT:abstractdatastructure)是一組數(shù)據(jù)以及定義在其上一組操作的集合.

線性表的抽象數(shù)據(jù)類型主要包含兩個方面：即:數(shù)據(jù)集合和該數(shù)據(jù)集合上操作的集合。

數(shù)據(jù)結(jié)構(gòu)(Java版)線性表1(順序表)全文共14頁，當前為第3頁。線性表的數(shù)據(jù)集合

線性表的數(shù)據(jù)元素集合可以表示為序列a0，a1，…ai，ai+1…an-1,每個數(shù)據(jù)元素可以是任意類型的。

在Java中，可以用類定義數(shù)據(jù)元素的數(shù)據(jù)類型。數(shù)據(jù)結(jié)構(gòu)(Java版)線性表1(順序表)全文共14頁，當前為第4頁。線性表的操作集合

線性表的操作集合用來說明線性表所需要實現(xiàn)的功能，其基本操作大致如下：添加數(shù)據(jù)元素：在線性表的末尾添加一個數(shù)據(jù)元素。插入數(shù)據(jù)元素：在線性表第i個元素前插入一個數(shù)據(jù)元素。刪除數(shù)據(jù)元素：刪除線性表中第i個數(shù)據(jù)元素。獲取數(shù)據(jù)元素：獲取線性表中第i個數(shù)據(jù)元素。遍歷線性表：從第一個元素開始，逐個訪問線性表中的每個數(shù)據(jù)元素。獲取當前線性表中的元素個數(shù)。求當前線性表中的元素個數(shù)。判斷線性表是否為空。判斷當前線性表中是否還有元素。在Java中，可以用接口或抽象類來定義線性表的操作集合。數(shù)據(jù)結(jié)構(gòu)(Java版)線性表1(順序表)全文共14頁，當前為第5頁。順序表

使用順序結(jié)構(gòu)存儲數(shù)據(jù)的線性表稱為順序表.數(shù)據(jù)結(jié)構(gòu)(Java版)線性表1(順序表)全文共14頁，當前為第6頁。順序表的設(shè)計與實現(xiàn)步驟

在確定了數(shù)據(jù)的存儲結(jié)構(gòu)以后,按下面步驟設(shè)計順序表.數(shù)據(jù)元素定義--------類數(shù)據(jù)操作定義--------抽象類或接口實現(xiàn)順序表-----一個實現(xiàn)數(shù)據(jù)操作的類數(shù)據(jù)結(jié)構(gòu)(Java版)線性表1(順序表)全文共14頁，當前為第7頁。使用順序表

項目實踐：例題2-1,用順序表實現(xiàn)學生成績信息管理程序.程序運行主界面見上圖.該程序文件名為ArrStudent.java,包含下面3個類1個接口.

StudScore類,定義數(shù)據(jù)元素(學生)StudOperation接口,定義數(shù)據(jù)操作

ArrStudent類,順序表

ArrStudentUser類,完成學生成績管理程序數(shù)據(jù)結(jié)構(gòu)(Java版)線性表1(順序表)全文共14頁，當前為第8頁。

修改完善例題2-1的學生成績管理程序。修改接口StudOPeration，為程序添加操作如下：獲取學生記錄個數(shù)根據(jù)學生姓名查詢學生信息根據(jù)學生姓名刪除學生的信息在指定位置處插入學生的信息修改順序表類ArrStudent，實現(xiàn)上述操作。修改類ArrStudentUser，完成上述功能的使用。

實戰(zhàn)演練

數(shù)據(jù)結(jié)構(gòu)(Java版)線性表1(順序表)全文共14頁，當前為第9頁。Java類庫中的順序表

Java類庫中的java.util.ArrayList類實現(xiàn)了順序表的功能,其中常用的構(gòu)造器和方法如下:publicArraylist(intinitialcapacity)//創(chuàng)建指定容量的順序表publicbooleanadd(Objectobj)//在表尾添加一個元素publicbooleanremove(Objectobj)//刪除表尾元素publicObjectremove(intindex)//刪除指定位置的元素publicObjectget(intindex)//獲取指定位置的元素publicintindexOf(Objectobj)//獲取某個元素的位置數(shù)據(jù)結(jié)構(gòu)(Java版)線性表1(順序表)全文共14頁，當前為第10頁。實戰(zhàn)演練使用java.util.ArrayList完成學生成績管理程序.數(shù)據(jù)結(jié)構(gòu)(Java版)線性表1(順序表)全文共14頁，當前為第11頁。使用java類庫中順序表java.util.ArrayList設(shè)計程序的步驟導入順序表類java.util.ArrayList定義數(shù)據(jù)元素使用順序表數(shù)據(jù)結(jié)構(gòu)(Java版)線性表1(順序表)全文共14頁，當前為第12頁。順序表的效率分析順序表支持隨機讀取，順序表讀取數(shù)據(jù)元素操作的時間復(fù)雜度為O(1)。在順序表中插入和刪除一個數(shù)據(jù)元素的時間復(fù)雜度為O(n)。順序表的主要優(yōu)點是支持隨機讀取，以及內(nèi)存空間利用率高。順序表的主要缺點是需要預(yù)先給出表中數(shù)據(jù)元素的個數(shù)，而這個很難準確做到。另外，順序表在進行