西北大学《数据结构》典型例题（1-5章）(3)

2.10

Status DeleteK(SqList &a,int i,int k)//删除线性表a中第i个元素起的k个元素 {

if(i<1||k<0||i+k-1>a.length) return INFEASIBLE;

for(count=1;i+count-1<=a.length-k;count++) //注意循环结束的条件 a.elem[i+count-1]=a.elem[i+count+k-1]; a.length-=k; return OK; }//DeleteK 2.11

Status Insert_SqList(SqList &va,int x)//把x插入递增有序表va中 {

if(va.length+1>va.listsize) return ERROR; va.length++;

for(i=va.length-1;va.elem[i]>x&&i>=0;i--) va.elem[i+1]=va.elem[i]; va.elem[i+1]=x; return OK; }//Insert_SqList 2.12

int ListComp(SqList A,SqList B)//比较字符表A和B,并用返回值表示结果,值为正,表示A>B;值为负,表示A

for(i=1;A.elem[i]||B.elem[i];i++)

if(A.elem[i]!=B.elem[i]) return A.elem[i]-B.elem[i]; return 0; }//ListComp 2.13

LNode* Locate(LinkList L,int x)//链表上的元素查找,返回指针 {

for(p=l->next;p&&p->data!=x;p=p->next); return p; }//Locate

2.14

int Length(LinkList L)//求链表的长度 {

for(k=0,p=L;p->next;p=p->next,k++); return k; }//Length 2.15

void ListConcat(LinkList ha,LinkList hb,LinkList &hc)//把链表hb接在ha后面形成链表hc {

hc=ha;p=ha;

while(p->next) p=p->next; p->next=hb; }//ListConcat 2.16 见书后答案. 2.17

Status Insert(LinkList &L,int i,int b)//在无头结点链表L的第i个元素之前插入元素b {

p=L;q=(LinkList*)malloc(sizeof(LNode)); q.data=b; if(i==1) {

q.next=p;L=q; //插入在链表头部 } else {

while(--i>1) p=p->next;

q->next=p->next;p->next=q; //插入在第i个元素的位置 } }//Insert 2.18

Status Delete(LinkList &L,int i)//在无头结点链表L中删除第i个元素 {

if(i==1) L=L->next; //删除第一个元素 else { p=L;

while(--i>1) p=p->next;

p->next=p->next->next; //删除第i个元素 } }//Delete 2.19

Status Delete_Between(Linklist &L,int mink,int maxk)//删除元素递增排列的链表L中值大于mink且小于maxk的所有元素 { p=L;

while(p->next->data<=mink) p=p->next; //p是最后一个不大于mink的元素 if(p->next) //如果还有比mink更大的元素 {

q=p->next;

while(q->datanext; //q是第一个不小于maxk的元素 p->next=q; }

}//Delete_Between 2.20

Status Delete_Equal(Linklist &L)//删除元素递增排列的链表L中所有值相同的元素 {

p=L->next;q=p->next; //p,q指向相邻两元素 while(p->next) {

if(p->data!=q->data) {

p=p->next;q=p->next; //当相邻两元素不相等时,p,q都向后推一步

} else {

while(q->data==p->data) q=q->next;

p->next=q;p=q;q=p->next; //当相邻元素相等时删除多余元素 } }//while }//Delete_Equal 2.21

void reverse(SqList &A)//顺序表的就地逆置 {

for(i=1,j=A.length;iA.elem[j]; }//reverse 2.22

void LinkList_reverse(Linklist &L)//链表的就地逆置;为简化算法,假设表长大于2 {

p=L->next;q=p->next;s=q->next;p->next=NULL; while(s->next) {

q->next=p;p=q;

q=s;s=s->next; //把L的元素逐个插入新表表头 }

q->next=p;s->next=q;A->next=s; }//LinkList_reverse

分析:本算法的思想是,逐个地把L的当前元素q插入新的链表头部,p为新表表头. 2.23

void merge1(LinkList &A,LinkList &B,LinkList &C)//把链表A和B合并为C,A和B的元素间隔排列,且使用原存储空间 {

p=A->next;q=B->next;C=A; while(p&&q) {

s=p->next;p->next=q; //将B的元素插入 if(s) {

t=q->next;q->next=s; //如A非空,将A的元素插入 } p=s;q=t; }//while }//merge1 2.24

void reverse_merge(LinkList &A,LinkList &B,LinkList &C)//把元素递增排列的链表A和B合并为C,且C中元素递减排列,使用原空间 {

pa=A->next;pb=B->next;pre=NULL; //pa和pb分别指向A,B的当前元素 while(pa&&pb) {

if(pa->datadata) {

pc=pa;q=pa->next;pa->next=pre;pa=q; //将A的元素插入新表 } else {

pc=pb;q=pb->next;pb->next=pre;pb=q; //将B的元素插入新表 } pre=pc; } while(pa) {

q=pa->next;pa->next=pc;pc=pa;pa=q; //插入A中余下的元素 } while(pb) {

q=pb->next;pb->next=pc;pc=pb;pb=q; //插入B中余下的元素 }