习题线性表.ppt

* Status Insert_Sq( SqList va, ElemType x ) { // 已知顺序表 va 中元素依值非递减有序排列，本算法 // 插入新的元素 x 并保持原表的有序性,返回 OK; // 若顺序表空间已满，则不再插入并返回 OVERFLOW if (va.length == va.listsize) return OVERFLOW; i = 0; while (iva.length x=va.elem[i]) i++; for ( j=va.length; ji; j-- ) va.elem[j] = va.elem[j-1]; // 右移所有值x的元素 va.elem[i] = x; va.length++; return OK; } //Insert_Sq 题 2.11 题2.12 已知 A=(a1, a2, …, am) B=(b1, b2, …, bn) 均为顺序表，试编写一个比较A?B大小的算法。 分析： 1. 算法的目标是分析两个表的大小，则算法中不应当破坏原表； 2. 按题意，表的大小指的是“词典次序”，则不应当先比较两个表的长度； 3. 算法中的基本操作为：同步比较两个表中相应的数据元素。 while (iLa.Length iLb.Length) { } int compare(SqList La, SqList Lb) { if (La.elem[i]==Lb.elem[i]) i++; else if (La.elem[i]Lb.elem[i]) return -1; else return 1; i=0; if ( i=La.length i=Lb.Length) return 0; else if (i=Lb.Length) return 1; else return -1; } 题2.19 删除有序表中所有其值大于 mink 且小于maxk的数据元素。 首先分析需要删除的结点的特点： =mink mink maxk =maxk pre q p 修改指针: pre-next = p; 释放结点: while (q!=p) {s=q-next; free(q); q=s; } … … void listdelete(LinkList L, int mink, int maxk) { } // listdelete while (p p-data=mink) { pre=p; p=p-next; } //查找第一个值mink的结点 if (p) { } // if q=pre-next; pre-next=p; // 修改指针 while (q!=p) { s=q-next; delete q; q=s; } // 释放结点空间 pre=L; p=L-next; while (p p-datamaxk) p=p-next; // 查找第一个值 ≥maxk 的结点 void purge_L( LinkList La ) { // 删除带头结点的单链表 La 中所有多余的结点 if (La-next) { // 只需要处理非空表 p = La-next; suc = p-next; while (suc) // 尚有后继未检查完 if (suc-data == p-data) { q = suc; suc = suc-next; delete q; } // 释放值相同的结点空间 else { // 链接值不同的结点 p-next= suc; p = suc; suc = suc-next; } }// if }//purge_L 题 2.20 void inverse1(SqList L) { i=0; j=L.length-1; while(ij) {temp=L.elem[i];L.elem[i]=L.elem[j]; L.elem[j]=temp; i++; j--;} } void inverse2(SqList L) { for(i=0; iL.length/2; i++) {temp=