线性表的逻辑结构、顺序表示与链式表示.pptVIP

猴子选猴王 有 n 个猴子，编号从1到n,站成一圈从编号为1的猴子开始从1到3报数，凡报数为3的猴子退出圈子，圈中最后剩下的一个猴子就是猴王。 从键盘读入猴子个数n, 输出猴王的编号。可以用循环队列来模拟此过程，请编程实现。 解题思路 (1)先建立循环队列{1, 2, …, n} (2)模拟报数过程，删除报数为3的结点，当链表中只剩一个结点时，报数过程结束 只有一个结点的循环链表有何特征？ p p-next==p; 程序实现—（1）建立循环链表{1, 2,…, n} LinkList build (int n) { int i; LinkList head, p,s; p=head=(LinkList)malloc(sizeof(Lnode)); p-data=1; for(i=2; in=n; i++) { s=(LinkList)malloc(sizeof(Lnode)); s-data=i; p-next=s; p=s; } p-next=head; / /建立循环 return head; } int count(LinkList head) { int i=1;LinkList q, p=head; while(p-next!=p) { //当圈中猴子多于1个 if(i==2) { //跳过下一个,重新报数 q=p-next; p-next=q-next; free(q); p=p-next; i=1; } else { //正常报数 p=p-next; i++; } } return p-data; } 程序实现—（2）报数过程模拟 2.3.3 链表的运算效率分析 1. 查找 因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为 O(n)。 时间效率分析 2. 插入和删除 因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为 O(1)。 空间效率分析 链表中每个结点都要增加一个指针空间，相当于总共增加了n 个整型变量，空间复杂度为 O(n)。 2.4.1多项式的线性表表示 An(x)=anxn+an-1xn-1+...+a1x+a0 用线性表表示为： A=(an, an-1,..., a1, a0) 若多项式的阶次很高，而系数ai不为零的很少，则这 种表示浪费空间。 可写为： A(x)=amxem+am-1xem-1+...+a1xe1+a0xe0, 用线性表表示为: A=((am,em), (am-1,em-1), ..., (a1,e1), (a0,e0)) 比如：A(x)=2x32+3x2 表示为线性表：A=((2, 32), (3, 2) ) 2.4 应用举例: 一元多项式的计算 多项式相加的方法 A + B = C 线性表C置空 各取线性表A和B的第一个元素作为当前处理的元素 比较当前处理的元素的指数值，相等，系数相加若不为零追加到线性表C，各取线性表A和B的下一个元素作为当前处理的元素；若指数不相等，则把大的元素追加到线性表C，取该元素所在线性表的下一个元素作为当前处理的元素。 重复步骤3直到其中一个线性表处理完毕，再把另一个线性表的剩余元素追加到线性表C。 一、多项式的数组存放 #define MAXN 100 typedef struct term { float coef; //系数coefficient int exp; //指数exponent }TERM; TERM poly[MAXN]; 2.4.2 顺序结构的加法实现 二、程序实现 int ah, at, bh, bt, ch, ct, free; int append(float c, int e) { if(free=MAXN) return(1); poly[free].ceof=c; poly[free].exp=e; free++; return(0); } int poly_add(int ah, int at, int bh, int bt, int *ch_p, int *ct_p) { int a_p,b_p, a_exp, b_exp; float c_coef; a_p=ah;b_p=bh; *ch_p=free; while(a_p=at b_p=bt) { a_exp=poly[a_p].exp; b_exp=poly[b_p].cexp; if(a_exp==b_exp) { c_coef=poly[a_p].coef+poly[b_p].coef; if(c_coef)