《计算机软件技术编程基础线性表.ppt》由会员分享，可在线阅读，更多相关《计算机软件技术编程基础线性表.ppt（27页珍藏版）》请在三一办公上搜索。
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 各数据元素在存储空间中按逻辑顺序依次存放,内存空间,a1,a2,ai,an,存储地址,Loc(a
2、1),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;,cpj=cpj-1;,cpi-1=b;,*n_point=*n_point+1;,插入位置,插入值,表,表容量,表长计数,void insl(int
3、m,int*n_point,int cp,int i,int b)int j;if(*n_point=m)cout*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;
4、for(j=i;j*n_point;j+)/i以后的各元素都向前移动一个位置/线性表的长度-1,coutunderflowendl;return;,cpj-1=cpj;,*n_point=*n_point-1;,删除位置,表,表长计数,void desl(int*n_point,int*cp,int i)int j;if(*n_point=0)/空表cout*n_point)/输入的序号不对coutnot this element in the listendl;return;for(j=i;j*n_point;j+)cpj-1=cpj;/i以后的各元素都向前移动一个位置*n_point=*n
5、_point-1;/线性表的长度-1,templateT 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,平均
6、移动元素次数为:,总时间开销估计为:O(n),删除算法时间代价与插入操作相似，O(n),顺序表存取元素方便，时间代价为O(1)插入、删除操作则付出时间代价O(n),结论：当n较大时，大量移动元素，耗时,解决办法：不移动元素的存储方法,2.2.2栈的定义栈是只能在表尾进行插入和删除元素的线性表,a1,an-1,an,入栈push,出栈pop,栈底bottom,栈顶top,特性：后进先出 last in frist out,栈的运算,栈的初始化建立一个空栈入栈运算将元素放到栈顶退栈运算删除当前栈顶元素读栈顶元素,/入栈运算void push(int*cp,int m,int*p_top,int x
7、)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 read
8、endl;y=NULL;return;,y=cp*p_top-1;,/读栈顶元素,队列的定义：一端插入，另一端删除元素的线性表,A,B,D,E,入队,出队,队尾rear,队头front,特点：先进先出，frist in frist out,C,插入一个元素,B,D,E,入队,出队,队尾rear,队头front,C,F,删除一个元素后的线性表,B,D,E,入队,出队,队尾rear,队头front,C,最先插入的元素将最先被删除,A,B,D,E,C,A,队头front,循环队列将队首和队尾连接起来形成一个环形表,rear,m,front,1,2,m,1,2,m-1,入队运算：循环队列的尾部加入一个
9、新元素。,1 判断循环队列是否已满。当循环队列非空(s=1)，且队尾指针等于队头指针时，循环队列已满，不能进行入队运算上溢(队尾指针赶上了队头指针）,标志s=0,表示队列空；s=1,表示队列非空；,2 队尾指针rear加一。当队尾指针rear=m+1时，则置rear=1,3新元素加入队尾指针所指位置。置队空标志s=1,m,1,2,m-1,front,rear,i,void addcp(char*cp,int mm,int*rear,int*front,int/标志队列非空,队列,队尾指针,队头指针,入队元素,队列容量,退队运算：每进行一次退队运算，队头指针front进一。当队头指针front=m+1时，则置front=1,退队运算：1 判断队列是否为空(s=0)，空队列不能进行退队运算2 将队头指针front 进一(front=front+1)。当队头指针front=m+1时，则置front=13将队头指针front 所指的元素取出4 判断退队后循环队列是否为空。当front=rear时，循环队列为空，即置s=0,m,1,2,m-1,front,rear,j,void delcp(char*cp,int mm,int*rear,int*front,int,队列,队尾指针,队头指针,退队元素,队列容量,
