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

《计算机软件技术编程基础 线性表》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、线性表的定义：线性表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、储空间是连续的2各数据元素在存储空间中按逻辑顺序依次存放内存空间a1a2…ai…an存储地址Loc(a1)Loc(a1)+k…Loc(ai)+(i-1)k…Loc(an)+(n-1)k插入运算在表中插入元素的条件是：顺序表不满插入操作的步骤为元素后移如何实现？voidinsl(intm,int*n_point,intcp[],inti,intb){intj;if(*n_point==m){}if(i>*n_point)for(j=*n_point;j>=i;j--){}}cout<<"overflow"

3、<*n_point)i=*n_point+1;for(j=*n_point;j>=i;j--){cp[j]=cp[j-1];}cp[i

4、-1]=b;*n_point=*n_point+1;}插入位置插入值表表容量表长计数删除运算条件是：存在指定序号元素voiddesl(int*n_point,int*cp,inti){intj;if(*n_point==0)//空表{}if((i<1)

5、

6、(i>*n_point))//输入的序号不对{cout<<"notthiselementinthelist"<

7、t<<"underflow"<

8、

9、(i>*n_point))//输入的序号不对{cout<<"notthiselementinthelist"<

10、point;j++){cp[j-1]=cp[j];//i以后的各元素都向前移动一个位置}*n_point=*n_point-1;//线性表的长度-1}templateTmax(Tx,Ty){return(x>y)?x:y;}如果使用模板，数据类型本身就是一个参数：类型作参数关键字template表示正在声明一个模板，数据类型参数T由模板参数给出。该模板的含义为，无论模板参数T实例为int、float或任意其他类型，包括类类型时，函数max就为实例化了的类型的参数求最大值。

11、voidmain(){intx=9,y=8,t1;t1=max(x,y);doublex1=7.,y1=12.,t2;t2=max(x1,y1);}插入算法执行时间:元素总个数为n，各个位置插入的概率相等为p＝1/n平均移动元素次数为:总时间开销估计为:O(n)删除算法时间代价与插入操作相似，O(n)顺序表存取元素方便，时间代价为O(1)插入、删除操作则付出时间代价O(n)结论：当n较大时，大量移动元素，耗时解决办法：不移动元素的存储方法2.2.2栈的定义栈是只能在表尾进行插入和删除元素的线性表a1…a

12、n-1an入栈push出栈pop栈底bottom栈顶top特性：后进先出lastinfristout栈的运算栈的初始化——建立一个空栈入栈运算——将元素放到栈顶退栈运算——删除当前栈顶元素读栈顶元素//入栈运算voidpush(int*cp,intm,int*p_top,intx){if(*p_top==m){}}cout<<"stackoverflow"<