《线性表-静态顺序表的实现.ppt》由会员分享，可在线阅读，更多相关《线性表-静态顺序表的实现.ppt（28页珍藏版）》请在金锄头文库上搜索。
1、第二章 线性表-静态顺序表 提纲1、从静态数组谈起2、静态顺序表的结构基于静态数组的顺序表3、静态顺序表的初始化操作4、静态顺序表的插入操作在表尾插入在表头插入在下标为i的位置插入5、静态顺序表的删除操作删除表尾删除表头删除第i个位置的元素6、静态顺序表的遍历操作1、从静态数组谈起(1)静态数组的C或者C+定义 类型名 数组名常数或者常量; float elem1000;(2)一个题目：从键盘输入一系列整数，最后一个整数为9999，将这些数据存入到一个数组中。然后遍历数组，将所有数据输出到屏幕上。1、从静态数组谈起(2)一个题目：从键盘输入一系列整数，最后一个整数为9999，将这些数据存入到一
2、个数组中。然后遍历数组，将所有数据输出到屏幕上。分析：1）到底输入了多少个整数，在没有遇到9999之前都无法判断，所以只有使用一个比较大的静态数组。最坏情况是：一旦这个选定大小的静态数组不能满足需求，程序就得不出正确结果。我们假定定义一个大小为1000的整型数组；2）数组大小为1000，也许你输入的整数的个数少于1000个，那么如何记录你到底输入了多少个数据呢，可以用整型变量length来指示数据的个数，初值为0，每输入一个整数，只要它的值不是9999，就存入数组，然后，length+(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;(2)一个题目：从键盘输入一系列整数，最后一个整数为9999，将这些数据存入到一个数组中。然后遍历数组，将所有数据输出到屏幕上。#include s
4、tdafx.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成对出现的，二者其实是配合使用的。#include stdafx.h#includeusing namespace std;int mai
5、n(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;SL.len
6、gth=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;我们称结构体：struct StaticListint elem1000;int length;为静态顺序表。现在要求写一个函数，int push_back(StaticList &L, int x)/功能是：在静态顺序表L的表尾插入一个元素x。如果插入失败返回-1，否则返回1.然后重新写刚才的程序。#include st
7、dafx.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;if(x=99
8、99)break;elsepush_back(SL,x);for(int i=0;i=SL.length-1;i+)coutSL.elemi ;coutendl;return 0;#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.length=x;
9、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相似。因此我们的程序可以再次改进#include stdafx.h#includeusing namespace std;#define L
10、ISTSIZE 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.length=x;
11、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;#include stdafx.h#includeusing namespace std;#define LISTSIZE 1000 /注意#define语句后面不需要有分号“；”结尾struct StaticListint elemLISTSIZE;int length;int listsize;vo
12、id 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 ;coutx;if(x=9
13、999)break;elsepush_back(SL,x); print(SL);return 0;代码量没有减少，但是程序的脉络却更加清晰了。这就是程序模块化的力量！2、静态顺序表的结构基于静态数组的顺序表1、从前面的例子可以看出，对静态数组适当包装（封装、改头换面），可以写成下面的形式：typedef int ElemType#define LISTSIZE 1000 /注意#define语句后面不需要有分号“；”结尾struct StaticList ElemType elemLISTSIZE;/存储数组的空间 int listsize; /用来记录数组占据的空间大小 int lengt
14、h;/用来记录数组中实际存在元素的个数;我给她取个名字“静态顺序表”2、写成这样的结构形式有很多好处：结构更紧凑；程序脉络更清晰；程序模块化更容易2、静态顺序表的结构基于静态数组的顺序表1、从前面的例子可以看出，对静态数组适当包装（封装、改头换面），可以写成下面的形式：typedef int ElemType;#define LISTSIZE 1000 /注意#define语句后面不需要有分号“；”结尾struct StaticList ElemType elemLISTSIZE;/存储数组的空间 int listsize; /用来记录数组占据的空间大小 int length;/用来记录数组中
15、实际存在元素的个数;我给她取个名字“静态顺序表”2、写成这样的结构形式有很多好处：结构更紧凑；程序脉络更清晰；程序模块化更容易注意：1、为方便调试，此处是以整型（int）为例来描述静态顺序表；2、如果你想存储、处理其他类型数据，只需改变int为其他类型即可。3、例如 typedef char ElemType;4、再例如：Struct student_informationchar No20;/学号 char Name20;/姓名；;typedef student_information ElemType;本次课提纲1、从静态数组谈起2、静态顺序表的结构基于静态数组的顺序表3、静态顺序表的初始
16、化操作4、静态顺序表的插入操作在表尾插入在表头插入在下标为i的位置插入5、静态顺序表的删除操作删除表尾删除表头删除第i个位置的元素6、静态顺序表的遍历操作3、静态顺序表的初始化操作(1)、静态顺序表的结构形式#include stdafx.h#includeusing namespace std;#define LISTSIZE 1000 /注意#define语句后面不需要有分号“；”结尾struct StaticListint elemLISTSIZE;/存储数组的空间 int listsize; /用来记录数组占据的空间大小 int length;/用来记录数组中实际存在元素的个数;(2)
17、、void InitList_StaticList(StaticList &L)/初始化操作 initialize listL.length=0;L.listsize=LISTSIZE;初始化操作就是为静态顺序表中的变量赋初值。本次课提纲1、从静态数组谈起2、静态顺序表的结构基于静态数组的顺序表3、静态顺序表的初始化操作4、静态顺序表的插入操作在表尾插入在表头插入在下标为i的位置插入5、静态顺序表的删除操作删除表尾删除表头删除第i个位置的元素6、静态顺序表的遍历操作4、静态顺序表的插入操作静态顺序表的结构形式#define LISTSIZE 1000 /注意#define语句后面不需要有分号“
18、；”结尾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;4、静态顺序表的插入操作静态顺序表的结构形式#define LISTSIZ
19、E 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.length-1;i=0;i-) /下标0,length
20、-1的元素逐个后移 L.elemi+1=L.elemi; L.elem0=e; L.length+; return 1; 4、静态顺序表的插入操作静态顺序表的结构形式#define LISTSIZE 1000 /注意#define语句后面不需要有分号“；”结尾struct StaticListint elemLISTSIZE;/存储数组的空间 int listsize; /用来记录数组占据的空间大小 int length;/用来记录数组中实际存在元素的个数;(4)、在下标为i的位置插入int insert(StaticList &L,int i,ElemType e)/在表中下标为i的位置插入
21、数据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;本次课提纲1、从静态数组谈起2、静态顺序表的结构基于静态数组的顺序表3、静态顺序表的初始化操作4、静态顺序表的插入操作在表尾插入在表头插入在下标为i的位置插入5、静态顺序表的删除操作删除表尾删除表头删除第i个位置的元素6、静态顺序表的遍历操作5、静态顺序表的删除
22、操作静态顺序表的结构形式#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.length-;return 1;5、静态顺序表的删除操作静态顺序表的结构形
23、式#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.length-1;i+)L.elemi-1=L.elemi;L.len
24、gth-;return 1;5、静态顺序表的删除操作静态顺序表的结构形式#define LISTSIZE 1000 /注意#define语句后面不需要有分号“；”结尾struct StaticListint elemLISTSIZE;/存储数组的空间 int listsize; /用来记录数组占据的空间大小 int length;/用来记录数组中实际存在元素的个数;(3)、删除表中下标为i处的元素int DeleteAny(StaticList &L,int i)/删除表中下标为i处的元素if(L.length=0)/如果顺序表为空（没有元素可删），返回-1，表示删除失败return -1;e
25、lsefor(int j=i+1;j=L.length-1;j+)/下标i+1,length-1的元素逐个前移L.elemj-1=L.elemj;L.length-;return 1;本次课提纲1、从静态数组谈起2、静态顺序表的结构基于静态数组的顺序表3、静态顺序表的初始化操作4、静态顺序表的插入操作在表尾插入在表头插入在下标为i的位置插入5、静态顺序表的删除操作删除表尾删除表头删除第i个位置的元素6、静态顺序表的遍历操作6、静态顺序表的遍历操作静态顺序表的结构形式#define LISTSIZE 1000 /注意#define语句后面不需要有分号“；”结尾struct StaticListi
26、nt elemLISTSIZE;/存储数组的空间 int listsize; /用来记录数组占据的空间大小 int length;/用来记录数组中实际存在元素的个数;(1)、静态顺序表的遍历操作void print(StaticList &L)for(int i=0;i=L.length-1;i+)coutL.elemi ;coutendl;测试案例int main(int argc, char* argv)StaticList L;InitList_StaticList(L);push_back(L,4);push_back(L,6);push_back(L,8);print(L);push_head(L,3);push_head(L,2);push_head(L,1);print(L);insert(L,4,5);print(L);insert(L,6,7);print(L);pop_back(L);print(L);pop_head(L);print(L);DeleteAny(L,3);print(L); return 0;
