计算机软件技术编程基础_线性表.pptVIP

* * 线性表的定义：线性表L是由n个数据元素a1,a2, …an组成的有限序列。L=（ a1,a2, … ai , ai+1, …, an） 其中n＞=0为表的长度 n=0时是空表，记为L=（ ） 特点： 唯一的起点：没有前驱，有一个唯一的后继 ???? 唯一的终点：有一个唯一的前驱而没有后继 ???? 内部结点：有唯一的前驱，唯一的后继 ???? 结点个数：线性表的长度 ???? 在同一表中，元素类型相同 例如： 字母表(A,B,C,D，…，Z)； 数字表（1，2，3， …，10)； 成绩表 2 线性表的存储结构 顺序存储结构——顺序表 链式存储结构——链表 顺序存储结构的特点： 1 存储空间是连续的 2 各数据元素在存储空间中按逻辑顺序依次存放 内存空间 a1 a2 … ai … an 存储地址 Loc(a1) Loc(a1)+k … Loc(ai)+(i-1)k … Loc(an)+(n-1)k 插入运算 在表中插入元素的条件是：顺序表不满 插入操作的步骤为 元素后移如何实现？ void insl(int m, int *n_point, int cp[], int i, int b) { int j; if(*n_point==m) { } if(i*n_point) for(j=*n_point;j=i;j--) { } } coutoverflowendl; return; i=*n_point+1; cp[j]=cp[j-1]; cp[i-1]=b; *n_point=*n_point+1; 插入位置 插入值 表 表容量 表长计数 void insl(int m, int *n_point, int cp[], int i, int b) { int j; if(*n_point==m) { coutoverflowendl; return; } if(i*n_point) i=*n_point+1; for(j=*n_point;j=i;j--) { cp[j]=cp[j-1]; } cp[i-1]=b; *n_point=*n_point+1; } 插入位置 插入值 表 表容量 表长计数 删除运算 条件是：存在指定序号元素 void desl(int *n_point,int *cp,int i) { int j; if(*n_point==0)//空表 { } if((i1)||(i*n_point))//输入的序号不对 { coutnot this element in the listendl; return; } for(j=i;j*n_point;j++) { //i以后的各元素都向前移动一个位置 } //线性表的长度-1 } coutunderflowendl; return; cp[j-1]=cp[j]; *n_point=*n_point-1; 删除位置 表 表长计数 void desl(int *n_point,int *cp,int i) { int j; if(*n_point==0)//空表 { coutunderflowendl; return; } if((i1)||(i*n_point))//输入的序号不对 { coutnot this element in the listendl; return; } for(j=i;j*n_point;j++) { cp[j-1]=cp[j];//i以后的各元素都向前移动一个位置 } *n_point=*n_point-1;//线性表的长度-1 } templateclass T T max(T x,T y) { return (xy)? x:y; } 如果使用模板，数据类型本身就是一个参数： 类型作参数 关键字template 表示正在声明一个模板，数据类型参数T由模板参数class T给出。 该模板的含义为，无论模板参数T实例为int、float或任意其他类型，包括类类型时，函数max就为实例化了的类型的参数求最大值。 void main() { int x=9,y=8,t1; t1=max(x,y); double x1=7., y1=12.,t2; t2=max(x1,y1);