1、第二章 線性表-靜態順序表 1提綱1、從靜態數組談起2、靜態順序表的結構基于靜態數組的順序表3、靜態順序表的初始化操作4、靜態順序表的插入操作在表尾插入在表頭插入在下標為i的位置插入5、靜態順序表的刪除操作刪除表尾刪除表頭刪除第i個位置的元素6、靜態順序表的遍歷操作21、從靜態數組談起(1)靜態數組的C或者C+定義 類型名 數組名常數或者常量; float elem1000;(2)一個題目：從鍵盤輸入一系列整數，最后一個整數為9999，將這些數據存入到一個數組中。然后遍歷數組，將所有數據輸出到屏幕上。31、從靜態數組談起(2)一個題目：從鍵盤輸入一系列整數，最后一個整數為9999，將這些數據存

2、入到一個數組中。然后遍歷數組，將所有數據輸出到屏幕上。分析：1）到底輸入了多少個整數，在沒有遇到9999之前都無法判斷，所以只有使用一個比較大的靜態數組。最壞情況是：一旦這個選定大小的靜態數組不能滿足需求，程序就得不出正確結果。我們假定定義一個大小為1000的整型數組；2）數組大小為1000，也許你輸入的整數的個數少于1000個，那么如何記錄你到底輸入了多少個數據呢，可以用整型變量length來指示數據的個數，初值為0，每輸入一個整數，只要它的值不是9999，就存入數組，然后，length+4(2)一個題目：從鍵盤輸入一系列整數，最后一個整數為9999，將這些數據存入到一個數組中。然后遍歷數組

3、，將所有數據輸出到屏幕上。#include stdafx.h#includeusing namespace std;int main(int argc, char* argv)int elem1000;int length=0;while(1)int x;cinx;if(x=9999)break;else elemlength=x;length+;for(int i=0;i=length-1;i+)coutelemi ;coutendl;return 0;5(2)一個題目：從鍵盤輸入一系列整數，最后一個整數為9999，將這些數據存入到一個數組中。然后遍歷數組，將所有數據輸出到屏幕上。#incl

4、ude stdafx.h#includeusing namespace std;int main(int argc, char* argv)int elem1000;int length=0;while(1)int x;cinx;if(x=9999)break;else elemlength=x;length+;for(int i=0;i=length-1;i+)coutelemi ;coutendl;return 0;從這個例子可以看出，數組elem是和length成對出現的，二者其實是配合使用的。6#include stdafx.h#includeusing namespace std;i

5、nt main(int argc, char* argv)int elem1000;int length=0;while(1)int x;cinx;if(x=9999)break;elseelemlength=x;length+;for(int i=0;i=length-1;i+)coutelemi ;coutendl;return 0;#include stdafx.h#includeusing namespace std;struct StaticListint elem1000;int length;int main(int argc, char* argv)StaticList SL;

6、SL.length=0;while(1)int x;cinx;if(x=9999)break;elseSL.elemSL.length=x;SL.length+;for(int i=0;i=SL.length-1;i+) coutSL.elemi ; coutendl;return 0;7我們稱結構體：struct StaticListint elem1000;int length;為靜態順序表。現在要求寫一個函數，int push_back(StaticList &L, int x)/功能是：在靜態順序表L的表尾插入一個元素x。如果插入失敗返回-1，否則返回1.然后重新寫剛才的程序。8#in

7、clude stdafx.h#includeusing namespace std;struct StaticListint elem1000;int length;int push_back(StaticList &L, int x)/功能是：在靜態順序表L的表尾插入一個元素x。如果插入失敗返回-1，否則返回1.if(L.length=1000) return -1;elseL.elemL.length=x;L.length+;return 1;int main(int argc, char* argv)StaticList SL;SL.length=0;while(1)int x;cinx

8、;if(x=9999)break;elsepush_back(SL,x);for(int i=0;i=SL.length-1;i+)coutSL.elemi ;coutendl;return 0;9#include stdafx.h#includeusing namespace std;struct StaticListint elem1000;int length;int push_back(StaticList &L, int x)/功能是：在靜態順序表L的表尾插入一個元素x。如果插入失敗返回-1，否則返回1.if(L.length=1000) return -1;elseL.elemL.

9、length=x;L.length+;return 1;int main(int argc, char* argv)StaticList SL;SL.length=0;while(1)int x;cinx;if(x=9999)break;elsepush_back(SL,x);for(int i=0;i=SL.length-1;i+)coutSL.elemi ;coutendl;return 0;在程序中頻繁地使用常數不是一種好的習慣，其缺點和頻繁使用3.14而不是常量PI相似。因此我們的程序可以再次改進10#include stdafx.h#includeusing namespace st

10、d;#define LISTSIZE 1000 /注意#define語句后面不需要有分號“；”結尾struct StaticListint elemLISTSIZE;int length;int listsize;void InitList_StaticList(StaticList &L)L.length=0; L.listsize=LISTSIZE; int push_back(StaticList &L, int x)/功能是：在靜態順序表L的表尾插入一個元素x。如果插入失敗返回-1，否則返回1.if(L.length=L.listsize) return -1;else L.elemL

11、.length=x; L.length+; return 1;void print(StaticList &L)for(int i=0;i=L.length-1;i+)coutL.elemi ;coutx;if(x=9999)break;elsepush_back(SL,x); print(SL);return 0;11#include stdafx.h#includeusing namespace std;#define LISTSIZE 1000 /注意#define語句后面不需要有分號“；”結尾struct StaticListint elemLISTSIZE;int length;in

12、t listsize;void InitList_StaticList(StaticList &L)L.length=0; L.listsize=LISTSIZE; int push_back(StaticList &L, int x)/功能是：在靜態順序表L的表尾插入一個元素x。如果插入失敗返回-1，否則返回1.if(L.length=L.listsize) return -1;else L.elemL.length=x; L.length+; return 1;void print(StaticList &L)for(int i=0;i=L.length-1;i+)coutL.elemi

13、;coutx;if(x=9999)break;elsepush_back(SL,x); print(SL);return 0;代碼量沒有減少，但是程序的脈絡卻更加清晰了。這就是程序模塊化的力量！122、靜態順序表的結構基于靜態數組的順序表1、從前面的例子可以看出，對靜態數組適當包裝（封裝、改頭換面），可以寫成下面的形式：typedef int ElemType#define LISTSIZE 1000 /注意#define語句后面不需要有分號“；”結尾struct StaticList ElemType elemLISTSIZE;/存儲數組的空間 int listsize; /用來記錄數組占據

14、的空間大小 int length;/用來記錄數組中實際存在元素的個數;我給她取個名字“靜態順序表”2、寫成這樣的結構形式有很多好處：結構更緊湊；程序脈絡更清晰；程序模塊化更容易132、靜態順序表的結構基于靜態數組的順序表1、從前面的例子可以看出，對靜態數組適當包裝（封裝、改頭換面），可以寫成下面的形式：typedef int ElemType;#define LISTSIZE 1000 /注意#define語句后面不需要有分號“；”結尾struct StaticList ElemType elemLISTSIZE;/存儲數組的空間 int listsize; /用來記錄數組占據的空間大小 in

15、t length;/用來記錄數組中實際存在元素的個數;我給她取個名字“靜態順序表”2、寫成這樣的結構形式有很多好處：結構更緊湊；程序脈絡更清晰；程序模塊化更容易注意：1、為方便調試，此處是以整型（int）為例來描述靜態順序表；2、如果你想存儲、處理其他類型數據，只需改變int為其他類型即可。3、例如 typedef char ElemType;4、再例如：Struct student_informationchar No20;/學號 char Name20;/姓名；;typedef student_information ElemType;14本次課提綱1、從靜態數組談起2、靜態順序表的結構基

16、于靜態數組的順序表3、靜態順序表的初始化操作4、靜態順序表的插入操作在表尾插入在表頭插入在下標為i的位置插入5、靜態順序表的刪除操作刪除表尾刪除表頭刪除第i個位置的元素6、靜態順序表的遍歷操作153、靜態順序表的初始化操作(1)、靜態順序表的結構形式#include stdafx.h#includeusing namespace std;#define LISTSIZE 1000 /注意#define語句后面不需要有分號“；”結尾struct StaticListint elemLISTSIZE;/存儲數組的空間 int listsize; /用來記錄數組占據的空間大小 int length;

17、/用來記錄數組中實際存在元素的個數;(2)、void InitList_StaticList(StaticList &L)/初始化操作 initialize listL.length=0;L.listsize=LISTSIZE;初始化操作就是為靜態順序表中的變量賦初值。16本次課提綱1、從靜態數組談起2、靜態順序表的結構基于靜態數組的順序表3、靜態順序表的初始化操作4、靜態順序表的插入操作在表尾插入在表頭插入在下標為i的位置插入5、靜態順序表的刪除操作刪除表尾刪除表頭刪除第i個位置的元素6、靜態順序表的遍歷操作174、靜態順序表的插入操作靜態順序表的結構形式#define LISTSIZE 1

18、000 /注意#define語句后面不需要有分號“；”結尾struct StaticListint elemLISTSIZE;/存儲數組的空間 int listsize; /用來記錄數組占據的空間大小 int length;/用來記錄數組中實際存在元素的個數;(1)、在表尾插入int push_back(StaticList &L,ElemType e)/在表尾插入數據eif(L.length=L.listsize)/如果順序表已滿（沒有多余空間），返回-1，表示插入失敗return -1;elseL.elemL.length=e;L.length+;return 1;184、靜態順序表的插入

19、操作靜態順序表的結構形式#define LISTSIZE 1000 /注意#define語句后面不需要有分號“；”結尾struct StaticListint elemLISTSIZE;/存儲數組的空間 int listsize; /用來記錄數組占據的空間大小 int length;/用來記錄數組中實際存在元素的個數;(3)、在表頭插入int push_head(StaticList &L,ElemType e)/在表頭插入數據e if(L.length=L.listsize) /如果順序表已滿（沒有多余空間），返回-1，表示插入失敗 return -1; else for(int i=L.l

20、ength-1;i=0;i-) /下標0,length-1的元素逐個后移 L.elemi+1=L.elemi; L.elem0=e; L.length+; return 1; 194、靜態順序表的插入操作靜態順序表的結構形式#define LISTSIZE 1000 /注意#define語句后面不需要有分號“；”結尾struct StaticListint elemLISTSIZE;/存儲數組的空間 int listsize; /用來記錄數組占據的空間大小 int length;/用來記錄數組中實際存在元素的個數;(4)、在下標為i的位置插入int insert(StaticList &L,i

21、nt i,ElemType e)/在表中下標為i的位置插入數據eif(L.length=L.listsize)/如果順序表已滿（沒有多余空間），返回-1，表示插入失敗return -1;else for(int j=L.length-1;j=i;j-) /下標0,length-1的元素逐個后移 L.elemj+1=L.elemj; L.elemi=e; L.length+; return 1;20本次課提綱1、從靜態數組談起2、靜態順序表的結構基于靜態數組的順序表3、靜態順序表的初始化操作4、靜態順序表的插入操作在表尾插入在表頭插入在下標為i的位置插入5、靜態順序表的刪除操作刪除表尾刪除表頭刪

22、除第i個位置的元素6、靜態順序表的遍歷操作215、靜態順序表的刪除操作靜態順序表的結構形式#define LISTSIZE 1000 /注意#define語句后面不需要有分號“；”結尾struct StaticListint elemLISTSIZE;/存儲數組的空間 int listsize; /用來記錄數組占據的空間大小 int length;/用來記錄數組中實際存在元素的個數;(1)、刪除表尾元素int pop_back(StaticList &L)/刪除表尾元素if(L.length=0)/如果順序表為空（沒有元素可刪），返回-1，表示刪除失敗return -1;elseL.lengt

23、h-;return 1;225、靜態順序表的刪除操作靜態順序表的結構形式#define LISTSIZE 1000 /注意#define語句后面不需要有分號“；”結尾struct StaticListint elemLISTSIZE;/存儲數組的空間 int listsize; /用來記錄數組占據的空間大小 int length;/用來記錄數組中實際存在元素的個數;(2)、刪除表頭元素int pop_head(StaticList &L)/刪除表頭元素if(L.length=0)/如果順序表為空（沒有元素可刪），返回-1，表示刪除失敗return -1;elsefor(int i=1;i=L.

24、length-1;i+)L.elemi-1=L.elemi;L.length-;return 1;235、靜態順序表的刪除操作靜態順序表的結構形式#define LISTSIZE 1000 /注意#define語句后面不需要有分號“；”結尾struct StaticListint elemLISTSIZE;/存儲數組的空間 int listsize; /用來記錄數組占據的空間大小 int length;/用來記錄數組中實際存在元素的個數;(3)、刪除表中下標為i處的元素int DeleteAny(StaticList &L,int i)/刪除表中下標為i處的元素if(L.length=0)/如果順序表為空（沒有元素可刪），返回