線性表的定義和基本操作
線性表的定義
線性表是具有相同數(shù)據(jù)類型的n(n>=0)個(gè)數(shù)據(jù)元素的有限序列章办。其中n為表長(zhǎng)道偷，當(dāng)n = 0時(shí)該線性表是一個(gè)空表癌瘾。
除了第一個(gè)元素外瓮下，每個(gè)元素有且僅有一個(gè)直接前驅(qū)翰铡。除最后一個(gè)元素外，每個(gè)元素有且僅有一個(gè)直接后繼讽坏。線性有序６А！
線性表的特點(diǎn)如下：
- 表中元素的個(gè)數(shù)有限
- 表中元素具有邏輯上的順序性路呜，在序列中各元素排序有其先后次序迷捧。
- 表中元素都是數(shù)據(jù)元素，每個(gè)元素都是單個(gè)元素
- 表中元素的數(shù)據(jù)類型都相同胀葱，每一個(gè)元素占有相同大小的存儲(chǔ)空間
- 表中元素具有抽象性漠秋。僅討論元素間的邏輯關(guān)系，不考慮元素究竟表示什么內(nèi)容
線性表示是一種邏輯結(jié)構(gòu)抵屿，表示元素之間一對(duì)一相鄰關(guān)系膛堤。順序表和鏈表是指存儲(chǔ)結(jié)構(gòu)，兩者屬于不同層面的概念晌该。
線性表的基本操作
一個(gè)數(shù)據(jù)結(jié)構(gòu)的基本操作是指其最核心最基本的操作肥荔。其他較復(fù)雜的操作可以通過調(diào)用其基本操作來實(shí)現(xiàn)。
線性表基本操作如下：
InitList(&L);//初始化表朝群。構(gòu)造一個(gè)空的線性表
Length(L);//求表長(zhǎng)燕耿。返回線性表的長(zhǎng)度。
LocateElem(L,e);//按值查找操作姜胖。在表中查找具有給定關(guān)鍵字值的元素誉帅。
GetElem(L,i);//按位查找操作。在表中第i個(gè)位置元素的值。
ListInsert(&L,i,e);//插入操作蚜锨。在表中第i個(gè)位置插入指定元素e档插。
ListDelete(&L,i，&e);//刪除操作亚再。刪除表中第i個(gè)位置的元素郭膛，并用e返回刪除元素的值。
PrintList(L);//輸出操作氛悬，按照前后順序輸出線性表L的所有元素值则剃。
Empty(L); //判空操作，若為空返回 True如捅。
DestroyList(L);//銷毀操作棍现，銷毀線性表，并釋放線性表L所占用的內(nèi)存空間镜遣。
需要注意到線性表是邏輯結(jié)構(gòu)而不是存儲(chǔ)結(jié)構(gòu)己肮，線性表的長(zhǎng)度一定是有限的，是由有限個(gè)數(shù)據(jù)元素組成的悲关，數(shù)據(jù)元素是數(shù)據(jù)項(xiàng)組成的谎僻。
線性表的順序表示
順序表的定義
線性表的順序存儲(chǔ)又稱為順序表。用一組連續(xù)的存儲(chǔ)單元坚洽，依次存儲(chǔ)線性表中的數(shù)據(jù)元素戈稿，從而使得邏輯上相鄰的兩個(gè)元素在物理位置上也相鄰西土。特點(diǎn)是：表中元素的邏輯順序和其物理順序相同讶舰。
線性表的存儲(chǔ)類型描述如下
#define MAXSIZE 100 //定義順序表的最大長(zhǎng)度
typedef struct {
ElemType data[MAXSIZE]; //順序表的元素
int length; //順序表當(dāng)前長(zhǎng)度
}SqList；
其中一維數(shù)組可以是靜態(tài)分配需了，也可以是動(dòng)態(tài)分配的跳昼。靜態(tài)分配時(shí)，若空間占滿肋乍，再加入新的數(shù)據(jù)將會(huì)產(chǎn)生溢出鹅颊，導(dǎo)致程序崩潰。
動(dòng)態(tài)分配是指在程序執(zhí)行過程中通過動(dòng)態(tài)存儲(chǔ)分配語句分配內(nèi)存墓造。一旦數(shù)據(jù)空間占滿堪伍，就開辟一塊更大的存儲(chǔ)空間，替換掉原有的觅闽。
動(dòng)態(tài)分配不是鏈?zhǔn)酱鎯?chǔ)帝雇，還是屬于順序存儲(chǔ)結(jié)構(gòu)，物理結(jié)構(gòu)并無變化蛉拙。分配的空間可以在運(yùn)行時(shí)決定尸闸。
順序表最主要的特點(diǎn)是隨機(jī)訪問。可以在O(1)的時(shí)間內(nèi)找到指定元素吮廉。
存儲(chǔ)密度高苞尝，每個(gè)節(jié)點(diǎn)只存儲(chǔ)數(shù)據(jù)元素。
邏輯上相鄰的元素物理上也相鄰宦芦，插入和刪除需要移動(dòng)大量元素宙址。
順序表上基本操作的實(shí)現(xiàn)
- 插入操作,在順序表L的第i個(gè)位置插入元素e，成功返回true踪旷，失敗返回false
bool listInsert(sqList & L,int i,ElemType e) {
if(i<1 || i > L.length + 1) return false;
if(L.length >= maxSize) return false;
for(int j = L.length; j >= i; j--) L.data[j] = L.data[j-1];
L.data[i-1] = e;
L.length ++;
return true;
}
- 刪除操作曼氛，刪除第i個(gè)位置上的元素，成功返回TRUE令野，并將刪除的元素用e返回舀患，失敗返回false
bool listDelete(sqList & L,int i, ElemType &e) {
if(i < 1|| i> L.length) return false;
e = L.data[i-1];
for(int j = i; j < L.length; j++) L.data[j-1] = L.data[j];
L.length --;
return true;
}
- 按值查找，在L中查找元素值為e的元素气破，并返回其位序
int LocateElem(sqList L, ElemType e) {
int i;
for(i = 0; i < L.length ; i++) {
if(L.data[i] == e) return i+1;
}
return 0;//查找失敗
}
Ok聊浅，基礎(chǔ)知識(shí)搞定了，接下來上編程題现使。（線性表為了方便debug低匙，我在這里全部采用STL中的vector）
- 從順序表中刪除具有最小值的元素，并由函數(shù)返回被刪除元素的值碳锈，空出的位置由最后一個(gè)元素填補(bǔ)顽冶，若表為空則顯示出錯(cuò)信息并退出運(yùn)行。
#include <iostream>
#include <cstdio>
#include <vector>
#include <climits>
using namespace std;
//T1
bool deleteMin(vector<int> &v, int &e) {
if (v.size() < 1) return false;
int len = v.size(), pos = 0; e = v[0];
for (int i = 1; i < len; i++) {
if (v[i] < e) {
e = v[i];pos = i;
}
}
v[pos] = v[len - 1];
v.resize(len - 1);
return true;
}
void testT1() {
vector<int> t;
int e = 0;
for (int i = 1; i < 10; i++) t.push_back(i);
deleteMin(t, e);
for (int i = 0; i < t.size(); ++i)
cout << t[i];
cout << endl;
cout << e << endl;
}
int main() {
testT1();
system("pause");
return 0;
}
代碼模板如下售碳，之后將只給出功能函數(shù)和test函數(shù)强重。
- 設(shè)計(jì)一個(gè)高效的算法，將順序表的所有元素逆置贸人，要求空間復(fù)雜度為O(1)
void reverseSqList(vector<int> &v) {
int temp;
int length = v.size() / 2;
for (int i = 0; i < length; i++) {
temp = v[i];
v[i] = v[v.size() - i - 1];
v[v.size() - i - 1] = temp;
}
}
void testT2() {
vector<int> t;
for (int i = 1; i < 10; i++) t.push_back(i);
reverseSqList(t);
for (int i = 0; i < t.size(); ++i)
cout << t[i];
cout << endl;
}
- 長(zhǎng)度為n的順序表L间景，編寫一個(gè)時(shí)間復(fù)雜度O(n) 空間復(fù)雜度O(1)的算法，實(shí)現(xiàn)刪除線性表中所有值為x的元素艺智。
void deleteAllx(vector<int> &v, int x) {
int index = 0, length = v.size();
for (int i = 0; i < length; i++) {
if (v[i] != x) v[index++] = v[i];
}
v.resize(index);
}
void testT3() {
vector<int > t;
t.push_back(1);
for (int i = 1; i < 10; i++) t.push_back(2);
deleteAllx(t, 1);
for (int i = 0; i < t.size(); i++) cout << t[i];
}
- 從有序表中刪除其值在s和t（s<t）之間的所有元素倘要，若s或t不合理或者順序表為空則顯示出錯(cuò)信息并退出運(yùn)行。
bool deleteS2T1(vector<int> &v, int s, int t) {
if (s > t) return false;
if (v.size() == 0) return false;
int length = v.size();
int index = 0;
for (int i = 0; i < length; i++)
if (v[i] < s || v[i] > t) v[index++] = v[i];
v.resize(index);
return true;
}
bool deleteS2T2(vector<int> &v, int s, int t) {
if (s > t) return false;
if (v.size() == 0) return false;
int length = v.size();
int i, j;
for (i = 0; i < length && v[i] < s; i++);
if (i >= length) return false;
//cout << i << endl;
for (j = i; j < length && v[j] <= t; j++);
//cout << j << endl;
for (; j < length; i++, j++) v[i] = v[j];
v.resize(i);
return true;
}
void testT4() {
vector<int> t;
for (int i = 1; i < 10; i++) t.push_back(i);
if(deleteS2T2(t,2,7)) for (int i = 0; i < t.size(); i++) cout << t[i];
else cout << "wrong parm" << endl;
}
- 從有序順序表中刪除所有其值重復(fù)的元素十拣，使表中所有元素的值均不同封拧。
bool deDuplicate(vector<int> &v) {
if (v.size() == 0 ) return false;
int length = v.size();
int i = 0;
for (int j = 1; j < length; j++) {
if (v[i] != v[j]) {
v[++i] = v[j];
}
}
v.resize(i + 1);
}
void testT5() {
vector<int> t;
for (int i = 0; i < 20; i++)
t.push_back(i / 2);
for (int i = 0; i < 20; i++) cout << t[i];
cout << endl;
deDuplicate(t);
int length = t.size();
for (int i = 0; i < length; i++) cout << t[i];
cout << endl;
}
- 將兩個(gè)有序順序表合并成一個(gè)新的有序順序表，并由函數(shù)返回結(jié)果順序表夭问。
vector<int> merge2List(vector<int> v1, vector<int> v2) {
int len1 = v1.size(), len2 = v2.size();
vector<int> temp(len1 + len2);
int i = 0, j = 0, index = 0 ;
while (i < len1 && j < len2){
if (v1[i] < v2[j]) {
temp[index++] = v1[i++];
}
else {
temp[index++] = v2[j++];
}
}
while (i < len1) temp[index++] = v1[i++];
while (j < len2) temp[index++] = v2[j++];
return temp;
}
void testT6() {
vector<int> t1,t2,t3;
for (int i = 0; i < 10; i++) t1.push_back(i * 2);
for (int i = 0; i < 10; i++) t2.push_back(i * 3);
t3 = merge2List(t1, t2);
for (int i = 0; i < t3.size(); i++) cout << t3[i];
}
- 已知在一維數(shù)組A[m+n]中依次存放著兩個(gè)線性表a（長(zhǎng)度為m）泽西，b（長(zhǎng)度為n），寫一個(gè)函數(shù)甲喝，將數(shù)組中的兩個(gè)順序表的位置互換尝苇。
void reverse(int a[], int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
for (int i = 0; i <= mid - left; i++) {
int temp = a[left + i];
a[left + i] = a[right - i];
a[right - i] = temp;
}
}
void Exchange(int a[], int m, int n) {
reverse(a, 0, m + n - 1);
reverse(a, 0, n - 1);
reverse(a, n, m + n - 1);
}
void testT7() {
int a[100];
for (int i = 0; i < 10; i++)
a[i] = i;
Exchange(a, 2, 8);
for (int i = 0; i < 10; i++)
cout << a[i];
}
- 線性表中元素遞增有序且按照順序存儲(chǔ)于計(jì)算機(jī)內(nèi)铛只，要求設(shè)計(jì)一算法完成用最少時(shí)間在表中查找數(shù)值為x的元。若找到將其與后繼元素相交換糠溜，若找不到將其插入表中淳玩，使表中元素仍遞增有序。
void binarySearch(vector<int> &v, int e) {
int low = 0, high = v.size() - 1, mid;
while (low <= high) {
mid = low + (high - low) / 2;
if (v[mid] == e) break;
else if (v[mid] < e) low = mid + 1;
else high = mid - 1;
}
if (v[mid] == e && mid != v.size() - 1) {
int temp = v[mid];
v[mid] = v[mid + 1];
v[mid + 1] = temp;
}
if (low > high) {
int i;
v.resize(v.size()+ 1);
for ( i = v.size() - 2; i > high; i--) v[i + 1] = v[i];
v[i + 1] = e;
}
}
void testT8() {
vector<int> t;
for (int i = 0; i < 10; i++) t.push_back(2*i);
binarySearch(t,11);
int length = t.size();
for (int i = 0; i < length; i++)
{
cout << t[i];
}
}
9.數(shù)組循環(huán)移p位
void reverse(int a[], int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
for (int i = 0; i <= mid - left; i++) {
int temp = a[left + i];
a[left + i] = a[right - i];
a[right - i] = temp;
}
}
void Exchange(int a[], int p, int n) {
reverse(a, 0, p- 1);
reverse(a, p, n - 1);
reverse(a, 0, n - 1);
}
還有兩題待補(bǔ)非竿！
