徐镜春数据结构习题2.docxVIP

2.11 设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。Status? OrderListInsert-sq(SqList va, ElemType x) { //将x插入到递增有序的顺序表va中，插入后va仍然递增有序(算法1) if (va.length==va.listsize){ newbase=(ElemType *)realloc(va.elem,(va.listsize+LISTINCREMENT)*sizeof(ElemType)); if (!newbase) exit(OVERFLOW); va.elem=newbase; va.listsize+=LISTINCREMENT; }//当前存储空间已满，增加分配空间 if (!va.length) {va.elem[0]=x; ++va.length; return OK;} q=(va.elem[0]); while (*q=x)(q=(va.elem[va.length-1])) ++q; //查找插入位置 for (p=(va.elem[va.length-1]); p=q; --p) *(p+1)=*p; *q=x; ++va.length; return OK;}//OrderListInsert-sq　Status? OrderListInsert-sq(SqList va, ElemType x) { //将x插入到递增有序的顺序表va中，插入后va仍然递增有序(算法2) if (va.length==va.listsize){ newbase=(ElemType *)realloc(va.elem,(va.listsize+LISTINCREMENT)*sizeof(ElemType)); if (!newbase) exit(OVERFLOW); va.elem=newbase; va.listsize+=LISTINCREMENT; }//当前存储空间已满，增加分配空间 if (!va.length) {va.elem[0]=x; ++va.length; return OK;} p=(va.elem[va.length-1]); while (P=(va.elem[0])*px) {*(p+1)=*p; --p;} *(p+1)=x; ++va.length; return OK;}//OrderListInsert-sq　2.12 设A=(a1,...,am)和B=(b1,...,bn)均为顺序表，A和B分别为A和B中除去最大共同前缀后的子表。若A=B=空表，则A=B；若A=空表，而B≠空表，或者两者均不为空表，且A的首元小于B的首元，则AB；否则AB。试写一个比较A，B大小的算法。int Compare-List(SqList a, SqList b){ //a,b为顺序表，若ab时，返回-1；a=b时，返回0；ab时，返回1 i=0; while (i=a.length-1) (i=b.length-1) (a.elem[i]=b.elem[i]) ++i; switch { case i=a.length i=b.length : return 0; break; case (i=a.length i=b.length-1) ||(i=a.length-1 i=b.length-1 a.elem[i]b.elem[i]) : return -1;break; default : return 1; }}//Compare-List　2.19status del-l(LinkList la, int mink, int maxk){ //la为带头结点的单链表的头指针，单链表中的结点以值递增有序排列 //本算法删除表中所有值大于mink且小于maxk的元素，minkmaxk if (mink=maxk) return ERROR p=la; while (p-nextNULL p-next-data=mink) p=p-next; q=p; while (q-nextNULL q-next-datamaxk) q=q-next ; q=q-next; p1=p-next; while (p1q) {q1=p1; p1=p1-next; free(q1);} p-next=q;}//del-l2.21?LinkList priou(LinkList la, LinkList q1){ //返回指向单链表la中结点的指针p1，p1-next=q1 p1=la; while (p1-next!=q1) p1=p1-next; return p1;}//priouvoid