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

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、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;,cpj=cpj-1;,cpi-1=b;,*n_point=*n_point+1;

3、,插入位置,插入值,表,表容量,表长计数,void insl(int 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_poi

4、nt)/输入的序号不对 coutnot this element in the listendl; return; 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 listend

5、l; return; for(j=i;j*n_point;j+) cpj-1=cpj;/i以后的各元素都向前移动一个位置 *n_point=*n_point-1;/线性表的长度-1 ,template T 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

6、(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栈的定义 栈是只能在表尾进行插入和删除元素的线性表,a1,an-1,an,入栈 push,出栈 pop,栈底bottom,栈顶top,特性：后进先出 last in frist out

7、,栈的运算,栈的初始化建立一个空栈 入栈运算将元素放到栈顶 退栈运算删除当前栈顶元素 读栈顶元素,/入栈运算 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=cp*p_top-1;,*p_top=*p_top-1;,栈顶指针,栈,删除元素的值,删除位置,void readtop(

8、int *cp, int m, int *p_top, int 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,f

9、ront,1,2,m,1,2,m-1,入队运算：循环队列的尾部加入一个新元素。,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=1 3将队头指针front 所指的元