《数据结构及应用算法》第2章 线性表Linear List(67P).ppt

ai-1 ai ai+1 p 修改指针的语句： p-prior-next=p-next; p-next-prior=p-prior; free(p) 删除操作： §2.2 线性表的链式表示和实现 ? 双向链表 §2.4有序表 举例：在有序顺表L中插入新结点，使得L仍然有序 void OrderInsert( SqList L, ElemType x ) { //L非递减有序的顺序表，插入新元素x，使L仍然有序 i=L.length-1; //i指向表尾元素 while(i=0 xL.elem[i]) { L.elem[i+1]=L.elem[i]; //大于x的元素右移 i--; } //while L.elem[i+1]=x; L.length++; } //OrderInser §2.4 有序表 举例：在有序单链表L中插入新结点，使得L仍然有序： void OrderInsert( LinkList L, ElemType e ) { //L是带头结点且非递减有序的单链表，插入新元素e，使L仍然有序 p=L; while(p-next!=NULL p-next-datae) p=p-next; //找插入位置 s=(LNode *)malloc(sizeof(LNode)); s-next=p-next; s-data=e; p-next=s; } //OrderInsert O(n) §2.4 有序表 举例：求有序顺表L的纯集合（P38例2.11) void purge( SqList L) { //L非递减有序的顺表，删除其中多多余的重复元素 i=-1; j=0; //i指向新表的表尾，j指向当前处理的结点 while(jL.lenght) if(j==0 || L.elem[i]!=L.elem[j]) L.elem[++i]=L.elem[j++]; L.length=i+1; } purge §2.4 有序表 举例，两个有序单链表的归并： void MergeList( LinkList La, LinkList Lb ) { //La和Lb是带头结点且非递减有序的单链表，将他们归并成Lc pa=La-next; pb=Lb-next; Lc=pc=La; //La的头结点作为Lc的头结点 while(pa pb) if(pa-data=pbdata){ pc-next=pa; pc=pa; pa=pa-next;} else { pc-next=pb; pc=pb; pb=pb-next;} pc-next = pa? pa : pb; delete Lb; } §2.4 有序表 顺序表其他运算举例：逆置顺序表 逆置前： (a1,a2,...,ai-1,ai,a1+1,...,an-1,an) 逆置后： (an,an-1,...,ai+1,ai,ai-1,...,a2,a1) §2.2 线性表的顺序表示和实现----顺序表 初始时在表头和表尾各设一个指针i和j； 互换i、j所指的元素； i++; j--; 重复执行，直至i和j相遇。 void invert ( ElemType *E，int s， int t ) { //将数组E自下标s至下标t之间的元素逆置 while(st) E[s++] ? E[t--] ; } void InvertSqList( SqList L ) { //将顺序表L中的所有元素逆置 invert(L.elem, 0, L.length-1); } §2.2 线性表的顺序表示和实现----顺序表 顺序表其他运算举例：用顺序表实现purge void purge(SqList A, SqList B){ //已知A为空顺序表。 //将顺序表B中所有值不同元素插入A中，然后销毁B A.elem[0]=B.elem[0]; A.length=1; for(i=1;iB.length;i++){ e=B.elem[i]; j=0; while(jA.length e!=A.elem[j]) j++; if(j==A.length) A.elem[A.lenght++]=e; }//for delete[]B.elem; B.listsize=0;B.length=0;