数据结构上机作业1-5章(2)

LinkList p,q; if(i==0) { } else if(i==1)

{ p=L;L=L->next;free(p);} else {

int j=1; p=L;

while(p->next!=NULL&&j

p=p->next; j++; }

q=p->next;

p->next=q->next; free(q); } }

2.20② 同2.19题条件，试写一高效的算法，删除表中所有值相同的多余元素 (使得操作后的线性表中所有元素的值均不相同) 同时释放被删结点空间，并分析你的算法的时间复杂度。 void Purge(LinkList &L) { LinkList p,q; p=L->next; q=p->next; while(q) {

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

q=q->next; p->next=q; }

q=q->next; p=p->next; } }

◆2.21③ 试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表(a1,a2,…,an)逆置为(an,an-1,…,a1)。

void Inverse(SqList &L) {

int temp; int i,j;

for(i=0,j=L.length-1;i<=j;i++,j--) {

temp=L.elem[i]; L.elem[i]=L.elem[j]; L.elem[j]=temp;

} }

◆ 2.22③ 试写一算法，对单链表实现就地置。

void Inverse(LinkList &L) /* 对带头结点的单链表L实现就地逆置 */ {

LinkList p,q,r;

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

{ r=q; q=p;p=p->next; q->next=r; } L->next=q; }

2.23③ 设线性表A=(a1,...,am), B=(b1,...,bn)，试写一个按下列规则合并A、B为线性表C的算法，即使得 C=(a1,b1,...,am,bm,bm+1,...,bn) 当m≤n时；或者 C=(a1,b1,...,an,bn,an+1,...,am) 当m＞n时。线性表A、B和C均以单链表作存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。

void Merge(LinkList ha, LinkList hb, LinkList &hc)/* 依题意，合并带头结点的单链表ha和hb为hc */ {

LinkList pa,pb,pc;

pa=ha->next;pb=hb->next;pc=hc=ha; while(pa&&pb)

{ pc->next=pa;pc=pa;pa=pa->next; pc->next=pb;pc=pb;pb=pb->next; }

while(pa) {

pc->next=pa; pc=pa;

pa=pa->next; }

while(pb) {

pc->next=pb; pc=pb;

pb=pb->next; } }

◆2.24④ 假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性表C， 并要求利用原表（即A表和B表）的结点空间构造C表。 void Union(LinkList &lc, LinkList &la, LinkList &lb) {

LinkList p,q,s,t;

lc=la; p=la->next; q=lb->next; lc->next=NULL; while (p && q)

if (p->datadata)

{ s=p->next; p->next=lc->next; lc->next=p; p=s; } else {

t=q->next; q->next=lc->next; lc->next=q; q=t; }

while (p) {s=p->next; p->next=lc->next; lc->next=p; p=s;} while (q) {t=q->next; q->next=lc->next; lc->next=q; q=t;} free(lb); }

2.31② 假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。

ElemType DeleteNode(LinkList s) /* 删除指针s所指结点的前驱结点，并返回被删结点的元素值 */ {