概念
順序表(Sequential List) 就是按照順序存儲(chǔ)方式存儲(chǔ)的線性表,該線性表的結(jié)點(diǎn)按照邏輯次序一次存放在計(jì)算機(jī)的一組連續(xù)的存儲(chǔ)單元中.
由于順序表示一次存放的,只要知道了該順序表的首地址及每個(gè)數(shù)據(jù)元素所占用的存儲(chǔ)長(zhǎng)度,那么就很容易計(jì)算出任何一個(gè)數(shù)據(jù)元素
所在的位置.
如下圖:
準(zhǔn)備數(shù)據(jù)
下面我們開(kāi)始順序表的程序設(shè)計(jì),首先需要準(zhǔn)備數(shù)據(jù),也就是準(zhǔn)備在順序表中需要用到的變量及數(shù)據(jù)結(jié)構(gòu)等.代碼如下:
static final int MAXLEN = 100; //定義順序表的最大長(zhǎng)度
class DATA //存儲(chǔ)在數(shù)據(jù)結(jié)點(diǎn)的數(shù)據(jù),可以當(dāng)做學(xué)生
{
String key;
String name;
int age;
}
class SLType //定義順序表結(jié)構(gòu)
{
DATA [] ListData = new DATA[MAXLEN]; //保存順序表的結(jié)構(gòu)數(shù)據(jù)
int ListLen; //順據(jù)表已存結(jié)點(diǎn)的數(shù)量
}
上面的代碼中,定義了順序表的最大長(zhǎng)度MAXLEN,順序表的數(shù)據(jù)元素DATA及順序表的類(lèi)SLType,ListLen為順序表已存結(jié)點(diǎn)的
數(shù)量,即當(dāng)前順序表的長(zhǎng)度,ListData是一個(gè)對(duì)象數(shù)組,用來(lái)存放各個(gè)數(shù)據(jù)結(jié)點(diǎn).
由于我們用java語(yǔ)言中數(shù)組都是從下表0開(kāi)始的,在這里,為了講述和理解的方便,從下標(biāo)1開(kāi)始記錄數(shù)據(jù)結(jié)點(diǎn),下標(biāo)0的位置不用.
初始化順序表
在使用順序表之前,首先要?jiǎng)?chuàng)建一個(gè)空的順序表,這里我們只需要設(shè)置順序表的結(jié)點(diǎn)數(shù)量ListLen為0就可以了
public void SLInit(SLType SL){
SL.ListLen = 0;
}
計(jì)算順序表的長(zhǎng)度
由于ListLen就是代表順序表已存結(jié)點(diǎn)的數(shù)量,所以直接返回它就可以了.
public int SLLength(SLType SL){
return SL.ListLen;
}
插入結(jié)點(diǎn)
插入結(jié)點(diǎn)就是在順序表的第i個(gè)位置插入一個(gè)新的結(jié)點(diǎn),使得其后的所有結(jié)點(diǎn)都向后移動(dòng)一個(gè)位置,也就是編號(hào)依次加1,
線性表的長(zhǎng)度變?yōu)閚+1,插入結(jié)點(diǎn)的難點(diǎn)在于隨后的每個(gè)位置都需要進(jìn)行移動(dòng).
public int Insert(SLType SL,int n,DATA data){
int i;
if(SL.ListLen>=MAXLEN){ //判斷順序表是否已滿(mǎn)
System.out.println("順序表已滿(mǎn)罗洗，不能插入結(jié)點(diǎn)钞馁！\n");
return 0;
}
if(n<1||n>SL.ListLen+1){ //判斷插入符號(hào)是否正確
System.out.println("插入元素序號(hào)錯(cuò)誤周伦，不能插入元素！\n");
return 0;
}
for (int j = SL.ListLen; j>n; j--) { //將順序表中的數(shù)據(jù)向后移動(dòng)
SL.ListData[j+1]=SL.ListData[j];
}
SL.ListData[n]=data; //插入位置
SL.ListLen++;
return 1; //成功插入,返回1
}
在上述代碼中,在程序中首先判斷順序表結(jié)點(diǎn)數(shù)量是否已經(jīng)滿(mǎn)了,以及插入結(jié)點(diǎn)后是否正確,所有條件都滿(mǎn)足后,然后將順序表中數(shù)據(jù)向后移動(dòng)一個(gè)位置,同時(shí)插入結(jié)點(diǎn),并更新結(jié)點(diǎn)的數(shù)量.
追加結(jié)點(diǎn)
追加結(jié)點(diǎn)因?yàn)椴恍枰苿?dòng)數(shù)據(jù),所以事先起來(lái)比較簡(jiǎn)單:
public int SLAdd(SLType SL,DATA data){
if(SL.ListLen >= MAXLEN){ //判斷是否已滿(mǎn)
System.out.println("順序表已滿(mǎn),不能再添加結(jié)點(diǎn)了");
return 0;
}
SL.ListData[++SL.ListLen] = data;
return 1;
}
刪除結(jié)點(diǎn)
刪除結(jié)點(diǎn)即刪除線性表L中第i個(gè)結(jié)點(diǎn),使得其后的所有結(jié)點(diǎn)便后依次減一,刪除一個(gè)結(jié)點(diǎn)之后,線性表L的長(zhǎng)度變?yōu)閚-1,刪除類(lèi)似添加,刪除后需要進(jìn)行大量的數(shù)據(jù)移動(dòng).
public int SLDeleteType(SLType SL,int n){
int i;
if(n<1||n>SL.ListLen+1){ //判斷插入符號(hào)是否正確
System.out.println("刪除元素符號(hào)錯(cuò)誤怔匣！\n");
return 0;
}
for (i = n; i <= SL.ListLen; i++) { //順序表中的元素向前移動(dòng)
SL.ListData[n+1] = SL.ListData[n];
}
SL.ListLen--; //順序表的元素?cái)?shù)量減一
return 1;
}
查找結(jié)點(diǎn)
查找結(jié)點(diǎn)就是根據(jù)線性表L中查找x的結(jié)點(diǎn),并返回該結(jié)點(diǎn)在L中位置,如果沒(méi)有找到該結(jié)點(diǎn),則返回一個(gè)錯(cuò)誤標(biāo)識(shí),根據(jù)x的不同,
有兩種方式來(lái)查找,一種是x是結(jié)點(diǎn)位置,直接同x返回該結(jié)點(diǎn)的數(shù)據(jù),如果x是關(guān)鍵字,則通過(guò)比對(duì)關(guān)鍵字,然后返回x的位置.
1.按照序號(hào)查找結(jié)點(diǎn)
public DATA SLFindByNum(SLType SL,int n){ //根據(jù)序號(hào)返回?cái)?shù)據(jù)元素
if(n<1||n>SL.ListLen+1){
System.out.println("查找符號(hào)錯(cuò)誤！\n");
return null;
}
return SL.ListData[n];
}
2.按照關(guān)鍵字查找結(jié)點(diǎn)
public int SLFindByCout(SLType SL,String key){ //按照關(guān)鍵字查找元素
int j;
for (j = 1; j < SL.ListLen; j++) {
if(SL.ListData[j].key.compareTo(key)==0){
return j;
}
}
return 0;
}
下面是所有代碼:
package SequentialList;
public class SLType {
static final int MAXLEN = 100;
//定義順序表結(jié)構(gòu)
DATA [] ListData = new DATA[MAXLEN+1];//保存順序表的結(jié)構(gòu)數(shù)組
int ListLen; //順序表已存節(jié)點(diǎn)的數(shù)量
/**
* 初始化順序表
* @param SL
*/
public void SLInit(SLType SL){
SL.ListLen=0;//初始化空表
}
/**
* 返回順序表的元素?cái)?shù)量
*/
public int SLLength(SLType SL){
return SL.ListLen;
}
/**
* 插入結(jié)點(diǎn)
* 插入結(jié)點(diǎn)就是在線性表的第i個(gè)位置插入一個(gè)新的結(jié)點(diǎn),使得其后的結(jié)點(diǎn)編號(hào)依次加1,這時(shí),插入一個(gè)結(jié)點(diǎn)后,線性表的長(zhǎng)度L將變?yōu)? * n+1,插入結(jié)點(diǎn)的難點(diǎn)在于隨后的每個(gè)結(jié)點(diǎn)的數(shù)據(jù)都要向后移動(dòng)
* @return
*/
public int Insert(SLType SL,int n,DATA data){
int i;
if(SL.ListLen>=MAXLEN){ //判斷順序表是否已滿(mǎn)
System.out.println("順序表已滿(mǎn)绊茧，不能插入結(jié)點(diǎn)跌帐！\n");
return 0;
}
if(n<1||n>SL.ListLen+1){ //判斷插入符號(hào)是否正確
System.out.println("插入元素序號(hào)錯(cuò)誤，不能插入元素翎冲！\n");
return 0;
}
for (int j = SL.ListLen; j>n; j--) { //將順序表中的數(shù)據(jù)向后移動(dòng)
SL.ListData[j+1]=SL.ListData[j];
}
SL.ListData[n]=data; //插入位置
SL.ListLen++;
return 1; //成功插入,返回1
}
/**
* 增加元素到順序表尾部
* @param SL
* @param data
* @return
*/
public int SLAdd(SLType SL,DATA data){
if(SL.ListLen >= MAXLEN){ //判斷是否已滿(mǎn)
System.out.println("順序表已滿(mǎn),不能再添加結(jié)點(diǎn)了");
return 0;
}
SL.ListData[++SL.ListLen] = data;
return 1;
}
/**
* 刪除順序表中的數(shù)據(jù)元素
* 順序表刪掉第i個(gè)結(jié)點(diǎn),那么之后的所有結(jié)點(diǎn)的位置都需要向前移動(dòng)一個(gè)位置
* @return
*/
public int SLDeleteType(SLType SL,int n){
int i;
if(n<1||n>SL.ListLen+1){ //判斷插入符號(hào)是否正確
System.out.println("刪除元素符號(hào)錯(cuò)誤垂睬！\n");
return 0;
}
for (i = n; i < =SL.ListLen; i++) { //順序表中的元素向前移動(dòng)
SL.ListData[n+1] = SL.ListData[n];
}
SL.ListLen--; //順序表的元素?cái)?shù)量減一
return 1;
}
/**
* 按照序號(hào)查找結(jié)點(diǎn)
* @return
*/
public DATA SLFindByNum(SLType SL,int n){ //根據(jù)序號(hào)返回?cái)?shù)據(jù)元素
if(n<1||n>SL.ListLen+1){
System.out.println("查找符號(hào)錯(cuò)誤！\n");
return null;
}
return SL.ListData[n];
}
/**
* 按照關(guān)鍵字查找結(jié)點(diǎn) 返回結(jié)點(diǎn)序號(hào)
* @return
*/
public int SLFindByCout(SLType SL,String key){ //按照關(guān)鍵字查找元素
int j;
for (j = 1; j <= SL.ListLen; j++) {
if(SL.ListData[j].key.compareTo(key)==0){
return j;
}
}
return 0;
}
/**
* 返回所有結(jié)點(diǎn)
* @return
*/
public int SLAll(SLType SL){
int i;
for(i =1;i<=SL.ListLen;i++){
System.out.printf("(%s,%s,%d)\n",SL.ListData[i].key,SL.ListData[i].name,SL.ListData[i].age);
}
return i;
}
}
上面就是順序表的java代碼實(shí)現(xiàn).
原來(lái)你是這樣的數(shù)據(jù)結(jié)構(gòu)之鏈表結(jié)構(gòu)
