目錄
一.線性表
二.順序表
1.概念及結構
2.順序表的實作
列印順序表
獲取順序表的有效長度
在pos位置新增元素
判斷是否包含某個元素
查找某個元素對應的位置
獲取/查找pos位置的元素
給pos位置的元素設為value
洗掉第一次出現的關鍵字key
清空順序表
3.順序表的優、缺點
三.順序表的實作代碼匯總
一.線性表
線性表（ linear list ） 是 n 個具有相同特性的資料元素的有限序列， 線性表是一種在實際中廣泛使用的資料結構，常見 的線性表：順序表、鏈表、堆疊、佇列、字串...
線性表在邏輯上是線性結構，也就說是連續的一條直線，但是在物理結構上并不一定是連續的，線性表在物理上存盤 時，通常以陣列和鏈式結構的形式存盤，
二.順序表
1.概念及結構
順序表是用一段 物理地址連續 的存盤單元依次存盤資料元素的線性結構，一般情況下采用陣列存盤，在陣列上完成資料的增刪查改，
而順序表一般可以分為兩類：靜態順序表、動態順序表
2.順序表的實作
首先我們將順序表的成員屬性以及建構式寫好，接下來實作具體介面
public class MyArrayList {
public int[] elem;
public int usedSize;//有效的資料個數，默認值為0
public MyArrayList() {//初始化一個陣列，容量為5
this.elem = new int[5];
}
}列印順序表
只需要遍歷完陣列，然后將其列印出來即可
具體的代碼實作：
// 列印順序表
public void display() {
for (int i = 0; i <this.usedSize ; i++) {
System.out.print(elem[i]+" ");
}
System.out.println();
}獲取順序表的有效長度
有效長度就是已經用過的元素，回傳usedSize即可
具體的代碼實作：
// 獲取順序表的有效資料長度
public int size() {
return usedSize;
}在pos位置新增元素
具體的操作分為四步：
1、判斷pos位置是否合法，即pos既不能小于0，也不能大于有效資料個數
2、判斷順序表是否已滿，如果滿了，需要Arrays.CopyOf()進行擴容
3、將pos后的元素依次后移，即 elem[i+1]=elem[i]
4、將目標元素data放入pos下標對應位置，即elem[pos]=data
具體的代碼實作：
// 在 pos 位置新增元素
public void add(int pos, int data) {
//1.判斷pos位置是否合法
if (pos<0 || pos>usedSize){
System.out.println("pos位置不合法");
return;
}
//2.判斷usedSize是否已滿
if (isFull()){
this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
}
//3.開始挪資料,并且給pos位置賦值
for (int i = usedSize-1; i >= pos ; i--) {
elem[i+1]=elem[i];//把i下標的值給i+1
}
this.elem[pos]=data;
this.usedSize++;//說明存放成功
}
public boolean isFull(){
return this.usedSize == this.elem.length;
}
判斷是否包含某個元素
只需要傳入需要查找的元素toFind，然后遍歷查找即可
具體的代碼實作：
// 判定是否包含某個元素
public boolean contains(int toFind) {
for (int i = 0; i <this.usedSize ; i++) {
if (this.elem[i]==toFind)
return true;
}
return false;
}查找某個元素對應的位置
跟上一個操作一樣，使用遍歷查找到元素后，回傳其下標即可
具體的代碼實作：
// 查找某個元素對應的位置
public int search(int toFind) {
for (int i = 0; i < this.usedSize; i++) {
if (this.elem[i]==toFind)
return i;//找到了回傳i下標
}
return -1; //找不到回傳-1，因為陣列沒有負數下標
}獲取/查找pos位置的元素
凡是傳入pos位置，我們都需要判斷pos是否合法，也要查看順序表是否為空，如果合法且不為空直接回傳該下標對應的元素即可
具體的代碼實作：
// 獲取 pos 位置的元素
public int getPos(int pos) {
if (pos<0 || pos>this.usedSize){
System.out.println("pos位置不合法");
return -1;//說明pos位置不合法
}
if(isEmpty()){
System.out.println("順序表為空");
return -1;
}
return this.elem[pos];//回傳pos位置的值
}
public boolean isEmpty(){
return this.usedSize==0;
}
給pos位置的元素設為value
依然先判斷pos位置是否合法，再判斷順序表是否為空，如果合法且不為空，則將value賦值給pos下標對應的元素
具體的代碼實作：
// 給 pos 位置的元素設為/更新為 value
public void setPos(int pos, int value) {
//還是要先判斷pos位置的合法性
if (pos<0 || pos>usedSize){
System.out.println("pos位置不合法");
return;
}
if(isEmpty()){
System.out.println("順序表為空");
return ;
}
this.elem[pos] = value;//將pos位置的元素更新為value
}
洗掉第一次出現的關鍵字key
具體步驟如下：
1、判斷順序表是否為空(除了增加元素是判斷順序表是否已滿，其他的都是判斷是否為空)
2、呼叫我們上邊寫的search函式，看是否存在該元素
3、如果存在，則從該元素起，將后面的元素往前挪，將要洗掉的元素覆寫
具體的代碼實作如下：
//洗掉第一次出現的關鍵字key
public void remove(int toRemove) {
if (isEmpty()){
System.out.println("順序表為空");
return;
}
int index = search(toRemove);
if (index==-1) {
System.out.println("沒有你要洗掉的數字");
return;
}
for (int i = index; i < usedSize-1; i++) {
this.elem[i]=this.elem[i+1];
}
this.usedSize--;
//this.elem[usedSize]=null; 如果陣列當中是參考型別，則要將其置為空
}清空順序表
清空順序表，只需要把有效長度置于0即可
具體的代碼實作：
// 清空順序表
public void clear() {
this.usedSize = 0;
}3.順序表的優、缺點
優點：由于順序表是物理和邏輯上都連續的，可以快速查找到當前資料，時間復雜度為O(1)
缺點：
1、洗掉和插入資料的時候，都需要移動資料，時間復雜度為O(N)
2、擴容也是問題，增容一般是呈2倍的增長，勢必會有一定的空間浪費，例如當前容量為100，滿了以后增容到200，我們再繼續插入5個資料，無后續資料插入，那么就浪費了95個資料空間
那么順序表的缺點怎么才能解決呢？鏈表很好的解決了順序表的缺點，隨用隨取，需要空間的時候就new一個結點，需要注意的是，鏈表是物理上不連續，而邏輯上連續，
三.順序表的實作代碼匯總
public class MyArrayList {
public int[] elem;
public int usedSize;
public MyArrayList() {
this.elem = new int[5];
}
// 列印順序表
public void display() {
for (int i = 0; i <this.usedSize ; i++) {
System.out.print(elem[i]+" ");
}
System.out.println();
}
// 獲取順序表的有效資料長度
public int size() {
return usedSize;
}
// 在 pos 位置新增元素
public void add(int pos, int data) {
//1.判斷pos位置是否合法
if (pos<0 || pos>usedSize){
System.out.println("pos位置不合法");
return;
}
//2.判斷usedSize是否已滿
if (isFull()){
this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
}
//3.開始挪資料,并且給pos位置賦值
for (int i = usedSize-1; i >= pos ; i--) {
elem[i+1]=elem[i];//把i下標的值給i+1
}
this.elem[pos]=data;
this.usedSize++;//說明存放成功
}
public boolean isFull(){
return this.usedSize == this.elem.length;
}
// 判定是否包含某個元素
public boolean contains(int toFind) {
for (int i = 0; i <this.usedSize ; i++) {
if (this.elem[i]==toFind)
return true;
}
return false;
}
// 查找某個元素對應的位置
public int search(int toFind) {
for (int i = 0; i < this.usedSize; i++) {
if (this.elem[i]==toFind)
return i;//找到了回傳i下標
}
return -1; //找不到回傳-1，因為陣列沒有負數下標
}
// 獲取 pos 位置的元素
public int getPos(int pos) {
if (pos<0 || pos>this.usedSize){
System.out.println("pos位置不合法");
return -1;//說明pos位置不合法
}
if(isEmpty()){
System.out.println("順序表為空");
return -1;
}
return this.elem[pos];//回傳pos位置的值
}
public boolean isEmpty(){
return this.usedSize==0;
}
// 給 pos 位置的元素設為/更新為 value
public void setPos(int pos, int value) {
//還是要先判斷pos位置的合法性
if (pos<0 || pos>usedSize){
System.out.println("pos位置不合法");
return;
}
if(isEmpty()){
System.out.println("順序表為空");
return ;
}
this.elem[pos] = value;//將pos位置的元素更新為value
}
//洗掉第一次出現的關鍵字key
public void remove(int toRemove) {
if (isEmpty()){
System.out.println("順序表為空");
return;
}
int index = search(toRemove);
if (index==-1) {
System.out.println("沒有你要洗掉的數字");
return;
}
for (int i = index; i < usedSize-1; i++) {
this.elem[i]=this.elem[i+1];
}
this.usedSize--;
//this.elem[usedSize]=null; 如果陣列當中是參考型別，則要將其置為空
}
// 清空順序表
public void clear() {
this.usedSize = 0;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/413385.html
標籤：java
上一篇：資料結構java版之堆疊