线性表-静态顺序表的实现.ppt
第二章 线性表-静态顺序表,提纲,1、从静态数组谈起2、静态顺序表的结构基于静态数组的顺序表3、静态顺序表的初始化操作4、静态顺序表的插入操作在表尾插入在表头插入在下标为i的位置插入,5、静态顺序表的删除操作删除表尾删除表头删除第i个位置的元素6、静态顺序表的遍历操作,1、从静态数组谈起,(1)静态数组的C或者C+定义 类型名 数组名常数或者常量;float elem1000;(2)一个题目：从键盘输入一系列整数，最后一个整数为9999，将这些数据存入到一个数组中。然后遍历数组，将所有数据输出到屏幕上。,1、从静态数组谈起,(2)一个题目：从键盘输入一系列整数，最后一个整数为9999，将这些数据存入到一个数组中。然后遍历数组，将所有数据输出到屏幕上。分析：1）到底输入了多少个整数，在没有遇到9999之前都无法判断，所以只有使用一个比较大的静态数组。最坏情况是：一旦这个选定大小的静态数组不能满足需求，程序就得不出正确结果。我们假定定义一个大小为1000的整型数组；2）数组大小为1000，也许你输入的整数的个数少于1000个，那么如何记录你到底输入了多少个数据呢，可以用整型变量length来指示数据的个数，初值为0，每输入一个整数，只要它的值不是9999，就存入数组，然后，length+,(2)一个题目：从键盘输入一系列整数，最后一个整数为9999，将这些数据存入到一个数组中。然后遍历数组，将所有数据输出到屏幕上。#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 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成对出现的，二者其实是配合使用的。,#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;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.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;,我们称结构体：struct StaticListint elem1000;int length;为静态顺序表。现在要求写一个函数，int push_back(StaticList&L,int x)/功能是：在静态顺序表L的表尾插入一个元素x。如果插入失败返回-1，否则返回1.然后重新写刚才的程序。,#include stdafx.h#includeusing namespace std;struct StaticListint elem1000;int length;int push_back(StaticList,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;,#include stdafx.h#includeusing namespace std;struct StaticListint elem1000;int length;int push_back(StaticList,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 LISTSIZE 1000/注意#define语句后面不需要有分号“；”结尾struct StaticListint elemLISTSIZE;int length;int listsize;void InitList_StaticList(StaticList,void print(StaticList,#include stdafx.h#includeusing namespace std;#define LISTSIZE 1000/注意#define语句后面不需要有分号“；”结尾struct StaticListint elemLISTSIZE;int length;int listsize;void InitList_StaticList(StaticList,void print(StaticList,代码量没有减少，但是程序的脉络却更加清晰了。这就是程序模块化的力量！,2、静态顺序表的结构基于静态数组的顺序表,1、从前面的例子可以看出，对静态数组适当包装（封装、改头换面），可以写成下面的形式：typedef int ElemType#define LISTSIZE 1000/注意#define语句后面不需要有分号“；”结尾struct StaticList ElemType elemLISTSIZE;/存储数组的空间 int listsize;/用来记录数组占据的空间大小 int length;/用来记录数组中实际存在元素的个数;,我给她取个名字“静态顺序表”2、写成这样的结构形式有很多好处：结构更紧凑；程序脉络更清晰；程序模块化更容易,2、静态顺序表的结构基于静态数组的顺序表,1、从前面的例子可以看出，对静态数组适当包装（封装、改头换面），可以写成下面的形式：typedef int ElemType;#define LISTSIZE 1000/注意#define语句后面不需要有分号“；”结尾struct StaticList ElemType elemLISTSIZE;/存储数组的空间 int listsize;/用来记录数组占据的空间大小 int length;/用来记录数组中实际存在元素的个数;,我给她取个名字“静态顺序表”2、写成这样的结构形式有很多好处：结构更紧凑；程序脉络更清晰；程序模块化更容易,注意：1、为方便调试，此处是以整型（int）为例来描述静态顺序表；2、如果你想存储、处理其他类型数据，只需改变int为其他类型即可。3、例如 typedef char ElemType;4、再例如：Struct student_informationchar No20;/学号 char Name20;/姓名；;typedef student_information ElemType;,本次课提纲,1、从静态数组谈起2、静态顺序表的结构基于静态数组的顺序表3、静态顺序表的初始化操作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)、void InitList_StaticList(StaticList 初始化操作就是为静态顺序表中的变量赋初值。,本次课提纲,1、从静态数组谈起2、静态顺序表的结构基于静态数组的顺序表3、静态顺序表的初始化操作4、静态顺序表的插入操作在表尾插入在表头插入在下标为i的位置插入,5、静态顺序表的删除操作删除表尾删除表头删除第i个位置的元素6、静态顺序表的遍历操作,4、静态顺序表的插入操作,静态顺序表的结构形式#define LISTSIZE 1000/注意#define语句后面不需要有分号“；”结尾struct StaticListint elemLISTSIZE;/存储数组的空间 int listsize;/用来记录数组占据的空间大小 int length;/用来记录数组中实际存在元素的个数;,(1)、在表尾插入int push_back(StaticList,4、静态顺序表的插入操作,静态顺序表的结构形式#define LISTSIZE 1000/注意#define语句后面不需要有分号“；”结尾struct StaticListint elemLISTSIZE;/存储数组的空间 int listsize;/用来记录数组占据的空间大小 int length;/用来记录数组中实际存在元素的个数;,(3)、在表头插入int push_head(StaticList,4、静态顺序表的插入操作,静态顺序表的结构形式#define LISTSIZE 1000/注意#define语句后面不需要有分号“；”结尾struct StaticListint elemLISTSIZE;/存储数组的空间 int listsize;/用来记录数组占据的空间大小 int length;/用来记录数组中实际存在元素的个数;,(4)、在下标为i的位置插入int insert(StaticList,本次课提纲,1、从静态数组谈起2、静态顺序表的结构基于静态数组的顺序表3、静态顺序表的初始化操作4、静态顺序表的插入操作在表尾插入在表头插入在下标为i的位置插入,5、静态顺序表的删除操作删除表尾删除表头删除第i个位置的元素6、静态顺序表的遍历操作,5、静态顺序表的删除操作,静态顺序表的结构形式#define LISTSIZE 1000/注意#define语句后面不需要有分号“；”结尾struct StaticListint elemLISTSIZE;/存储数组的空间 int listsize;/用来记录数组占据的空间大小 int length;/用来记录数组中实际存在元素的个数;,(1)、删除表尾元素int pop_back(StaticList,5、静态顺序表的删除操作,静态顺序表的结构形式#define LISTSIZE 1000/注意#define语句后面不需要有分号“；”结尾struct StaticListint elemLISTSIZE;/存储数组的空间 int listsize;/用来记录数组占据的空间大小 int length;/用来记录数组中实际存在元素的个数;,(2)、删除表头元素int pop_head(StaticList,5、静态顺序表的删除操作,静态顺序表的结构形式#define LISTSIZE 1000/注意#define语句后面不需要有分号“；”结尾struct StaticListint elemLISTSIZE;/存储数组的空间 int listsize;/用来记录数组占据的空间大小 int length;/用来记录数组中实际存在元素的个数;,(3)、删除表中下标为i处的元素int DeleteAny(StaticList,本次课提纲,1、从静态数组谈起2、静态顺序表的结构基于静态数组的顺序表3、静态顺序表的初始化操作4、静态顺序表的插入操作在表尾插入在表头插入在下标为i的位置插入,5、静态顺序表的删除操作删除表尾删除表头删除第i个位置的元素6、静态顺序表的遍历操作,6、静态顺序表的遍历操作,静态顺序表的结构形式#define LISTSIZE 1000/注意#define语句后面不需要有分号“；”结尾struct StaticListint elemLISTSIZE;/存储数组的空间 int listsize;/用来记录数组占据的空间大小 int length;/用来记录数组中实际存在元素的个数;,(1)、静态顺序表的遍历操作void print(StaticList,测试案例,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;,
