（02）數據結構題解－線性表

2019-11-17 05:46:05

字體：大中小

來源：轉載

供稿：網友

　　　　　　　　　　　　　　　　　　　　第二章線性表
2.10
Status DeleteK(SqList &a,int i,int k)//刪除線性表a中第i個元素起的k個元素
{
if(i<1k<0i+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<B;值為零,表示A=B
{
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)    file://假如還有比mink更大的元素
{
    q=p->next;
    while(q->data<maxk) q=q->next; //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)
   {
     free(q);
     q=q->next;
   }
      p->next=q;p=q;q=p->next; //當相鄰元素相等時刪除多余元素
    }//else
}//while
}//Delete_Equal
2.21
void reverse(SqList &A)//順序表的就地逆置
{
for(i=1,j=A.length;i<j;i++,j--)
    A.elem[i]<->A.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;L->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; file://pa和pb分別指向A,B的當前元素
while(papb)
{
    if(pa->data<pb->data!pb)
    {
      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;
}
C=A;A->next=pc; //構造新表頭
}//reverse_merge
分析:本算法的思想是,按從小到大的順序依次把A和B的元素插入新表的頭部pc處,最后處理A或B的剩余元素.
2.25
void SqList_Intersect(SqList A,SqList B,SqList &C)//求元素遞增排列的線性表A和B的元素的交集并存入C中
{
i=1;j=1;k=0;
while(A.elem[i]&&B.elem[j])
{
    if(A.elem[i]<B.elem[j]) i++;
    if(A.elem[i]>B.elem[j]) j++;
    if(A.elem[i]==B.elem[j])
    {
      C.elem[++k]=A.elem[i]; //當發現了一個

上一篇：1996年9月全國計算機等級考試二級試卷C語言（帶答案）

下一篇：（04）第四章　串題解