順序表
1.定義:用一組位址連續的存儲單元依次存儲線性表的資料元素的表。
由上圖可以看出元素位址滿足以下關系：
2.類型定義
以圖書資料舉例，其類型定義如下：
#define MAXSIZE 100 //最大長度
typedef struct
{
char no[]; //圖書ISBN
char name[]; //圖書名字
float price; //圖書價格
}Book; //圖書結構類型
typedef struct
{
Book *elem; //基位址
int length; //圖書個數
}SqList; //圖書表結構類型
3.順序表操作
3.1初始化
【步驟】
①為L配置設定一個預定義大小的數組空間，elem指向這段空間的基位址。
②将表的長度置為0。
Status InitList(SqList &L)
{
L.elem = new ElemType[MAXSIZE];
if(!L.elem) exit(OVERFLOW);
L.length = ;
return OK;
}
3.2取值
【步驟】
①判斷i值合不合理。
②将第i個元素即L.elem[i-1]賦給e。
Status GetElem(SqList L,int i,ElemType &e)
{
if(i< || i>L.length) return ERROR;
e = L.elem[i-];
return OK;
}
3.3查找
【步驟】
①從第一個元素開始,依次比較，若相等傳回i+1,若比較到最後也沒有找到則查找失敗，傳回0。
Status LocateElem(SqList L,ElemType e)
{
for(i=;i<L.length;i++)
if(L.elem[i] == e) return i+;
return ;
}
查找平均時間複雜度O(n)
3.4插入
【步驟】
①判斷插入位置是否合法。
②判斷存儲空間是否已滿。
③從後往前從第n至i依次往移動，空出第i各位置。
④将元素插入第i個位置。
Status ListInsert(SqList &L,int i;ELemType e)
{
if((i<) || (i>L.length+)) return ERROR;
if(L.length == MAXSIZE) return ERROR;
for(j=L.length-;j>=i-;j--)
L.elem[j+] = L.elem[j];
L.elem[i-] = e;
++L.length;
return OK;
}
平均時間複雜度O(n)
3.5删除
【步驟】
①判斷i是否合法。
②将第i+1個至n依次前移。
③表長減1。
Status ListDelete(SqList &L, int i)
{
if(i< || i>L.length) retrun ERROR;
for(j=i;j<Length-;j++)
L.elem[j-]=L.elem[j];
--L.length;
return OK;
}
平均時間複雜度O(n)
3.6銷毀線性表L
void DestroyList(SqList &L)
{
if (L.elem) delete[]L.elem; //釋放存儲空間
}
3.7清空線性表
void ClearList(SqList &L)
{
L.length=; //将線性表的長度置為0
}
4.完整代碼
#include<iostream>
#include<fstream>
#include<string>
#include<iomanip>
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status; //Status 是函數傳回值類型，其值是函數結果狀态代碼。
typedef int ElemType; //ElemType 為可定義的資料類型，此設為int類型
#define MAXSIZE 100 //順序表可能達到的最大長度
struct Book {
string id;//ISBN
string name;//書名
double price;//定價
};
typedef struct {
Book *elem; //存儲空間的基位址
int length; //目前長度
} SqList;
Status InitList_Sq(SqList &L) { //算法2.1 順序表的初始化
//構造一個空的順序表L
L.elem = new Book[MAXSIZE]; //為順序表配置設定一個大小為MAXSIZE的數組空間
if (!L.elem)
exit(OVERFLOW); //存儲配置設定失敗退出
L.length = ; //空表長度為0
return OK;
}
Status GetElem(SqList L, int i, Book &e) {//算法2.2 順序表的取值
if (i < || i > L.length)
return ERROR; //判斷i值是否合理，若不合理，傳回ERROR
e = L.elem[i - ]; //elem[i-1]單元存儲第i個資料元素
return OK;
}
int LocateElem_Sq(SqList L, double e) { //算法2.3 順序表的查找
//順序表的查找
for (int i = ; i < L.length; i++)
if (L.elem[i].price == e)
return i + ;//查找成功，傳回序号i+1
return ;//查找失敗，傳回0
}
Status ListInsert_Sq(SqList &L, int i, Book e) { //算法2.4 順序表的插入
//在順序表L中第i個位置之前插入新的元素e
//i值的合法範圍是1<=i<=L.length+1
if ((i < ) || (i > L.length + ))
return ERROR; //i值不合法
if (L.length == MAXSIZE)
return ERROR; //目前存儲空間已滿
for (int j = L.length - ; j >= i - ; j--)
L.elem[j + ] = L.elem[j]; //插入位置及之後的元素後移
L.elem[i - ] = e; //将新元素e放入第i個位置
++L.length; //表長增1
return OK;
}
Status ListDelete_Sq(SqList &L, int i) { //算法2.5 順序表的删除
//在順序表L中删除第i個元素，并用e傳回其值
//i值的合法範圍是1<=i<=L.length
if ((i < ) || (i > L.length))
return ERROR; //i值不合法
for (int j = i; j <= L.length; j++)
L.elem[j - ] = L.elem[j]; //被删除元素之後的元素前移
--L.length; //表長減1
return OK;
}
int main() {
SqList L;
int i = , temp, a, c, choose;
double price;
Book e;
string head_1, head_2, head_3;
cout << "1. 建立\n";
cout << "2. 輸入\n";
cout << "3. 取值\n";
cout << "4. 查找\n";
cout << "5. 插入\n";
cout << "6. 删除\n";
cout << "7. 輸出\n";
cout << "0. 退出\n\n";
choose = -;
while (choose != ) {
cout << "請選擇:";
cin >> choose;
switch (choose) {
case ://建立順序表
if (InitList_Sq(L))
cout << "成功建立順序表\n\n";
else
cout << "順序表建立失敗\n\n";
break;
case : {//順序表資訊輸入
i = ;
L.elem = new Book[MAXSIZE];
if (!L.elem)
exit(OVERFLOW);
L.length = ;
fstream file;
file.open("book.txt");
if (!file) {
cout << "錯誤！未找到檔案！" << endl;
exit(ERROR);
}
file >> head_1 >> head_2 >> head_3;
while (!file.eof()) {
file >> L.elem[i].id >> L.elem[i].name >> L.elem[i].price;
i++;
}
cout << "輸入 book.txt 資訊完畢\n\n";
L.length = i;
file.close();
}
break;
case ://順序表的取值
cout << "請輸入一個位置用來取值：\n";
cin >> i;
temp = GetElem(L, i, e);
if (temp != ) {
cout << "查找成功\n";
cout << "第" << i << "本圖書的資訊是：\n";
cout << left << setw() << e.id << "\t" << left << setw()
<< e.name << "\t" << left << setw() << e.price << endl
<< endl;
} else
cout << "查找失敗！位置超出範圍\n\n";
break;
case : //順序表的查找
cout << "請輸入所要查找價格:";
cin >> price;
temp = LocateElem_Sq(L, price);
if (temp != ) {
cout << "查找成功\n";
cout << "該價格對應的書名為：" << L.elem[temp - ].name << endl << endl;
} else
cout << "查找失敗！沒有這個價格對應的書籍\n\n";
break;
case : //順序表的插入
cout << "請輸入插入的位置和書本資訊，包括：編号 書名 價格（用空格隔開）:";
cin >> a;
cin >> e.id >> e.name >> e.price; //輸入a和b，a代表插入的位置，b代表插入的數值（書本資訊）
if (ListInsert_Sq(L, a, e))
cout << "插入成功.\n\n";
else
cout << "插入失敗.\n\n";
break;
case : //順序表的删除
cout << "請輸入所要删除的書籍的位置:";
cin >> c;
if (ListDelete_Sq(L, c))
cout << "删除成功.\n\n";
else
cout << "删除失敗.\n\n";
break;
case : //順序表的輸出
cout << "目前圖書系統資訊（順序表）讀出:\n";
for (i = ; i < L.length; i++)
cout << left << setw() << L.elem[i].id << "\t" << left
<< setw() << L.elem[i].name << "\t" << left
<< setw() << L.elem[i].price << endl;
cout << endl;
break;
}
}
return ;
}
5.順序表的優缺點