注：筆記截圖均來自王卓數(shù)據(jù)結(jié)構(gòu)教學視頻
線性表的定義和特點
線性表是具有相同特性的數(shù)據(jù)元素的一個有限序列
同一線性表中的元素必定具有相同特性，數(shù)據(jù)元素間的關(guān)系是線性關(guān)系。
線性表的邏輯特征
稀疏多項式的運算
順序存儲結(jié)構(gòu)存在的問題
1、存儲空間分配不靈活
2、運算的空間復雜度高
引出鏈式存儲結(jié)構(gòu)：
小結(jié)
1、線性表中數(shù)據(jù)元素的類型可以為簡單類型，也可以為復雜類型。
2、許多實際應用問題所涉的基本操作有很大相似性，不應為每個具體應用單獨編寫一個程序。
3、從具體應用中抽象出共性的邏輯結(jié)構(gòu)和基本操作（抽象數(shù)據(jù)類型），然后實現(xiàn)其存儲結(jié)構(gòu)和基本操作。
線性表的類型定義
抽象數(shù)據(jù)類型線性表的定義如下：
基本操作
線性表的順序表示和實現(xiàn)
在計算機內(nèi)，線性表有兩種基本的存儲結(jié)構(gòu)：
順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。
線性表的順序存儲表示
線性表的順序表示又稱為順序存儲結(jié)構(gòu)或順序映像。
順序存儲定義：把邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元中的存儲結(jié)構(gòu)。
線性表的第1個數(shù)據(jù)元素a1的存儲位置，稱作線性表的起始位置或基地址。
多項式的順序存儲結(jié)構(gòu)類型定義
圖書表的順序存儲結(jié)構(gòu)類型定義
線性表的順序存儲表示
順序表基本操作的實現(xiàn)
以下根據(jù)教學視頻用C++實現(xiàn)：
BOOK對象和HOME對象的建立：
class Book
{
public:
string Name;
};
class Home
{
public:
Home();
~Home();
void ClearBook();
int ShowBookAmount();
void addBook();
void showBook();
Book* bookarr;
int length;
int Maxlength;
};
Home::Home()
{
cout << "Home構(gòu)造函數(shù)執(zhí)行" << endl;
length = 0;//此處應該是從數(shù)據(jù)庫讀取數(shù)據(jù)，但本次案例不考慮數(shù)據(jù)庫，因此直接初始化成0
int Maxlength = 6;
while (length>Maxlength)
{
Maxlength += 3;//因為是動態(tài)存儲，這里表示如果初始的Book數(shù)量超過了Maxlength，則增加Maxlength直到不再超過
}
bookarr = new Book[Maxlength];
cout << "Home構(gòu)造函數(shù)為Book建了空間數(shù)："<< Maxlength << endl;
}
Home::~Home()
{
cout << "Home析構(gòu)函數(shù)執(zhí)行" << endl;
if (bookarr != NULL)
{
delete[] bookarr;
}
}
void Home::ClearBook()
{
length = 0;
}
int Home::ShowBookAmount()
{
return length;
}
因為老師只實現(xiàn)了幾個典型的函數(shù)后就沒有講解，因此這里也不做過多的設計。
實現(xiàn)功能輸出如下：
源代碼：
/*`cin.ignore(numeric_limits<streamsize>::max(), '\n')`用于清除輸入緩沖區(qū)中的字符，直到遇到換行符為止。
具體解釋如下：
1.cin.ignore(numeric_limits<streamsize>::max(), '\n')`表示使用`cin.ignore()`函數(shù)來忽略輸入緩沖區(qū)中的字符。
2.numeric_limits<streamsize>::max()`表示在忽略字符的數(shù)量上沒有限制，可以忽略輸入緩沖區(qū)中的所有字符。
3.'\n'`是指定要忽略的字符，即換行符。
通常，在用戶輸入不正確的內(nèi)容后，我們需要清除輸入緩沖區(qū)中的殘留字符，以避免對后續(xù)輸入產(chǎn)生干擾。
使用這行代碼可以確保輸入緩沖區(qū)中的所有無效字符都被忽略直到遇到換行符為止。這樣，程序可以繼續(xù)等待用戶的新輸入。*/
#include<iostream>
using namespace std;
#include<string>
class Book
{
public:
string Name;
};
class Home
{
public:
Home();
~Home();
void ClearBook();
int ShowBookAmount();
void addBook();
void showBook();
Book* bookarr;
int length;
int Maxlength;
};
Home::Home()
{
cout << "Home構(gòu)造函數(shù)執(zhí)行" << endl;
length = 0;//此處應該是從數(shù)據(jù)庫讀取數(shù)據(jù)，但本次案例不考慮數(shù)據(jù)庫，因此直接初始化成0
Maxlength = 6;
while (length>Maxlength)
{
Maxlength += 3;//因為是動態(tài)存儲，這里表示如果初始的Book數(shù)量超過了Maxlength，則增加Maxlength直到不再超過
}
bookarr = new Book[Maxlength];
cout << "Home構(gòu)造函數(shù)為Book建了空間數(shù)："<< Maxlength << endl;
}
Home::~Home()
{
cout << "Home析構(gòu)函數(shù)執(zhí)行" << endl;
if (bookarr != NULL)
{
delete[] bookarr;
}
}
void Home::ClearBook()
{
length = 0;
}
int Home::ShowBookAmount()
{
return length;
}
void Home::addBook()
{
string bname;
cout << "請輸入書名：" << endl;
cin >> bname;
if (length >= Maxlength)
{
Maxlength += 3;
cout << "書庫已滿……進行擴容->Maxlength將擴容至：" << Maxlength << endl;
Book* temp = new Book[Maxlength];
for (int i = 0; i < length; ++i)
{
temp[i] = bookarr[i];
}
if (bookarr != NULL)
{
cout << "delete[] bookarr" << endl;
delete[] bookarr;
}
cout << "new Book[Maxlength]" << endl;
bookarr = new Book[Maxlength];
for (int i = 0; i < length; ++i)
{
bookarr[i] = temp[i];
}
if (temp != NULL)
{
cout << "delete[] temp" << endl;
delete[] temp;
}
length += 1;
bookarr[length - 1].Name = bname;
}
else
{
length += 1;
bookarr[length - 1].Name = bname;
}
}
void Home::showBook()
{
for (int i = 0; i < length; ++i)
{
cout << "圖書" << (i + 1) << " :" << bookarr[i].Name << endl;
}
}
void showTable()
{
cout << "*************************************************" << endl;
cout << "********** 圖 書 管 理 系 統(tǒng) **********" << endl;
cout << "*************************************************" << endl;
cout << "********** 1、查詢數(shù)量 2、清空書庫 **********" << endl;
cout << "********** 3、添加書籍 4、顯示書籍 **********" << endl;
cout << "********** 5、待定待定 6、待定待定 **********" << endl;
cout << "********** 7、刷新屏幕 0、退出系統(tǒng) **********" << endl;
cout << "*************************************************" << endl;
}
int main()
{
showTable();
Home home;
int pushnum;
int bookamount;
do {
int availableChars = (int)cin.rdbuf()->in_avail();
if (availableChars)
{
cin.ignore(numeric_limits<streamsize>::max(), '\n');
}
cout << "請輸入您要進行的操作>=" << endl;
cin >> pushnum;
if (cin.fail()) {
cout << "您輸入的不是一個整數(shù)，請重新輸入：" << endl;
cin.clear();
cin.ignore(numeric_limits<streamsize>::max(), '\n');
continue;
}
if (pushnum < 0 || pushnum>7)
{
cout << "您輸入數(shù)字不合要求：" << pushnum << endl;
continue;
}
switch (pushnum)
{
case 1:
bookamount = home.ShowBookAmount();
cout << "當前書庫書籍數(shù)量為：" << bookamount << endl;
break;
case 2:
cout << "執(zhí)行清空書庫操作……" << endl;
home.ClearBook();
break;
case 3:
cout << "執(zhí)行添加書籍操作……" << endl;
home.addBook();
break;
case 4:
cout << "執(zhí)行顯示書籍操作……" << endl;
home.showBook();
break;
case 5:
break;
case 6:
break;
case 7:
system("cls");
showTable();
break;
default:
break;
}
} while (pushnum);
cout << "歡迎下次使用，再見……" << endl;
return 0;
}
順序表基本操作的實現(xiàn)
順序表上的查找操作
順序表的查找算法分析：
順序表插入算法的平均時間復雜度為O(n)。
順序表的刪除
順序表刪除算法的平均時間復雜度為O(n)。
順序表（線性表的順序存儲結(jié)構(gòu)）的特點
文章來源：http://www.zghlxwxcb.cn/news/detail-554364.html
順序表優(yōu)缺點
文章來源地址http://www.zghlxwxcb.cn/news/detail-554364.html
到了這里，關(guān)于第一百零五天學習記錄：數(shù)據(jù)結(jié)構(gòu)與算法基礎：順序表（王卓教學視頻）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
