内容发布更新时间 : 2024/5/7 18:17:42星期一 下面是文章的全部内容请认真阅读。

while(p&&p->data!=x){ p=p->next; i++; }

if(!p) return 0; else return i; }

2.14 试写一算法在带头结点的单链表结构上实现线性表操作Length(L)。

解：

//返回单链表的长度

int ListLength_L(LinkList &L) {

int i=0;

LinkList p=L; if(p) p=p-next; while(p){

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

return i; }

2.15 已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起，假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。

解：

void MergeList_L(LinkList &ha,LinkList &hb,LinkList &hc) {

LinkList pa,pb; pa=ha; pb=hb;

while(pa->next&&pb->next){ pa=pa->next; pb=pb->next; }

if(!pa->next){ hc=hb;

while(pb->next) pb=pb->next; pb->next=ha->next; } else{

hc=ha;

while(pa->next) pa=pa->next; pa->next=hb->next;

精选

} }

2.16 已知指针la和lb分别指向两个无头结点单链表中的首元结点。下列算法是从表la中删除自第i个元素起共len个元素后，将它们插入到表lb中第i个元素之前。试问此算法是否正确？若有错，请改正之。

Status DeleteAndInsertSub(LinkedList la,LinkedList lb,int i,int j,int len) {

if(i<0||j<0||len<0) return INFEASIBLE; p=la; k=1;

while(knext; k++; } q=p;

while(k<=len){ q=q->next; k++; } s=lb; k=1;

while(knext; k++; } s->next=p; q->next=s->next; return OK; } 解：

Status DeleteAndInsertSub(LinkList &la,LinkList &lb,int i,int j,int len) {

LinkList p,q,s,prev=NULL; int k=1;

if(i<0||j<0||len<0) return INFEASIBLE; // 在la表中查找第i个结点 p=la;

while(p&&knext; k++; }

if(!p)return INFEASIBLE;

// 在la表中查找第i+len-1个结点 q=p; k=1;

while(q&&knext; k++; }

if(!q)return INFEASIBLE;

// 完成删除，注意，i=1的情况需要特殊处理 if(!prev) la=q->next; else prev->next=q->next;

// 将从la中删除的结点插入到lb中

精选

if(j=1){

q->next=lb; lb=p; } else{

s=lb; k=1;

while(s&&knext; k++; }

if(!s)return INFEASIBLE; q->next=s->next;

s->next=p; //完成插入 }

return OK; }

2.17 试写一算法，在无头结点的动态单链表上实现线性表操作Insert(L,i,b)，并和在带头结点的动态单链表上实现相同操作的算法进行比较。 2.18试写一算法，实现线性表操作Delete(L,i)，并和在带头结点的动态单链表上实现相同操作的算法进行比较。

2.19 已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效的算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素），同时释放被删结点空间，并分析你的算法的时间复杂度（注意，mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。

解：

Status ListDelete_L(LinkList &L,ElemType mink,ElemType maxk) {

LinkList p,q,prev=NULL; if(mink>maxk)return ERROR; p=L; prev=p; p=p->next;

while(p&&p->datadata<=mink){ prev=p; p=p->next; } else{

prev->next=p->next; q=p;

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

精选

return OK; } 2.20 同2.19题条件，试写一高效的算法，删除表中所有值相同的多余元素（使得操作后的线性表中所有元素的值均不相同），同时释放被删结点空间，并分析你的算法的时间复杂度。

解：

void ListDelete_LSameNode(LinkList &L) {

LinkList p,q,prev; p=L; prev=p; p=p->next; while(p){ prev=p; p=p->next;

if(p&&p->data==prev->data){ prev->next=p->next; q=p;

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

2.21 试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表

?a1,?,an?逆置为?an,?,a1?。

解：

// 顺序表的逆置

Status ListOppose_Sq(SqList &L) {

int i;

ElemType x;

for(i=0;i

L.elem[i]=L.elem[L.length-1-i]; L.elem[L.length-1-i]=x; }

return OK; }

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

解：

// 带头结点的单链表的逆置

Status ListOppose_L(LinkList &L) {

精选

}

LinkList p,q; p=L;

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

p=p->next;

q->next=L->next; L->next=q; }

return OK;

2.23 设线性表A??a1,a2,?,am?，B??b1,b2,?,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均未显式存储。

解：

// 将合并后的结果放在C表中，并删除B表

Status ListMerge_L(LinkList &A,LinkList &B,LinkList &C) {

LinkList pa,pb,qa,qb; pa=A->next; pb=B->next; C=A;

while(pa&&pb){

qa=pa; qb=pb;

pa=pa->next; pb=pb->next; qb->next=qa->next; qa->next=qb; }

if(!pa)qb->next=pb; pb=B; free(pb); return OK; }

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

精选