计算机软件技术编程基础线性表.ppt
线性表的定义：线性表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 各数据元素在存储空间中按逻辑顺序依次存放内存空间a1a2aian存储地址Loc(a1)Loc(a1)+kLoc(ai)+(i-1)kLoc(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;cpj=cpj-1;cpi-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)coutoverflow*n_point)i=*n_point+1;for(j=*n_point;j=i;j-)cpj=cpj-1;cpi-1=b;*n_point=*n_point+1;插入位置插入值表表容量表长计数删除运算删除运算条件是：存在指定序号元素条件是：存在指定序号元素void desl(int*n_point,int*cp,int i)int j;if(*n_point=0)/空表if(i*n_point)/输入的序号不对coutnot this element in the listendl;return;for(j=i;j*n_point;j+)/i以后的各元素都向前移动一个位置 /线性表的长度-1coutunderflowendl;return;cpj-1=cpj;*n_point=*n_point-1;删除位置表表长计数void desl(int*n_point,int*cp,int i)int j;if(*n_point=0)/空表coutunderflowendl;return;if(i*n_point)/输入的序号不对coutnot this element in the listendl;return;for(j=i;j*n_point;j+)cpj-1=cpj;/i以后的各元素都向前移动一个位置*n_point=*n_point-1;/线性表的长度-1templateT max(T x,T y)return(xy)?x:y;如果使用模板，数据类型本身就是一个参数：如果使用模板，数据类型本身就是一个参数：类型作参数关键字关键字template 表示正在声明一个模板，数据类型参表示正在声明一个模板，数据类型参数数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);插入算法执行时间插入算法执行时间:元素总个数为元素总个数为n，各个位置插入的概率相等为，各个位置插入的概率相等为p1/n平均移动元素次数为平均移动元素次数为:总时间开销估计为总时间开销估计为:O(n)删除算法时间代价与插入操作相似，删除算法时间代价与插入操作相似，O(n)顺序表存取元素方便，时间代价为顺序表存取元素方便，时间代价为O(1)插入、删除操作则付出时间代价插入、删除操作则付出时间代价O(n)结论：当结论：当n较大时，大量移动元素，耗时较大时，大量移动元素，耗时解决办法：不移动元素的存储方法解决办法：不移动元素的存储方法2.2.2栈的定义栈的定义栈是只能在表尾进行插入和删除元素的线性表栈是只能在表尾进行插入和删除元素的线性表a1an-1an入栈push出栈pop栈底bottom栈顶top特性：后进先出 last in frist out栈的运算栈的运算栈的初始化栈的初始化建立一个空栈建立一个空栈入栈运算入栈运算将元素放到栈顶将元素放到栈顶退栈运算退栈运算删除当前栈顶元素删除当前栈顶元素读栈顶元素读栈顶元素/入栈运算void push(int*cp,int m,int*p_top,int x)if(*p_top=m)coutstack overflowendl;*p_top=*p_top+1;cp*p_top-1=x;栈顶指针栈插入元素插入位置/退栈运算void pop(int*cp,int m,int*p_top,int&y)if(*p_top=0)coutstack underflowendl;y=cp*p_top-1;*p_top=*p_top-1;栈顶指针栈删除元素的值删除位置void readtop(int*cp,int m,int*p_top,int&y)if(*p_top=0)coutstack empty,can not readendl;y=NULL;return;y=cp*p_top-1;/读栈顶元素读栈顶元素队列的定义：一端插入，另一端删除元素的线性表队列的定义：一端插入，另一端删除元素的线性表ABDE入队出队队尾rear队头front特点：先进先出，frist in frist outC插入一个元素插入一个元素BDE入队出队队尾rear队头frontCF删除一个元素后的线性表删除一个元素后的线性表BDE入队出队队尾rear队头frontC最先插入的元素将最先被删除ABDECA队头front循环队列循环队列将队首和队尾连接起来形成一个环形表将队首和队尾连接起来形成一个环形表rearmfront12m12m-1入队运算入队运算：循环队列的尾部加入一个新元素。1 判断循环队列是否已满。当循环队列非空(s=1)，且队尾指针等于队头指针时，循环队列已满，不能进行入队运算上溢(队尾指针赶上了队头指针）标志s=0,表示队列空；s=1,表示队列非空；2 队尾指针rear加一。当队尾指针rear=m+1时，则置rear=13新元素加入队尾指针所指位置。置队空标志s=1m12m-1frontrearivoid addcp(char*cp,int mm,int*rear,int*front,int&s,char x)if(s=1)&(*rear=*front)coutqueue-overflowendl;return;*rear=*rear+1;/队尾指针rear加一 /当队尾指针rear=m+1时，则置rear=1if(*rear=(mm+1)*rear=1;cp*rear-1=x;/将新元素放入队尾s=1;/标志队列非空队列队尾指针队头指针入队元素队列容量退队运算：每进行一次退队运算，队头指针front进一。当队头指针front=m+1时，则置front=1退队运算：1 判断队列是否为空(s=0)，空队列不能进行退队运算2 将队头指针front 进一(front=front+1)。当队头指针front=m+1时，则置front=13将队头指针front 所指的元素取出4 判断退队后循环队列是否为空。当front=rear时，循环队列为空，即置s=0m12m-1frontrearjvoid delcp(char*cp,int mm,int*rear,int*front,int&s,char&y)if(s=0)coutqueue-underflowendl;return;*front=*front+1;if(*front=mm+1)*front=1;y=cp*front-1;if(*front=*rear)s=0;队列队尾指针队头指针退队元素队列容量
