原创 数据结构第二章习题参考答案(第二部分)

这是第2部分,其实还有几题没做,不过我不可能每题都做,没那么多时间啊.所有的课程资料,我会陆续放到 http://www.yulexuexi.cn/ 上,大家可以去那里看.

----------------------------------------------------------------------------------
#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"

typedef struct _LNode
{
 int data;
 struct _LNode *next;
}LNode, *LinkList;

//创建一个新的带头结点链表,即创建一个空表
bool create_list(LinkList *L)
{
 LinkList p;
 if((p=(LinkList)malloc(sizeof(LNode)))==NULL)
  return false;
 p->next=NULL;
 *L=p;
 return true;
}
//将x插入链表L的第i个结点前
bool insert_list(LinkList L,int i,int x)
{
 LinkList p,q;
 int k="1";
 if((p=(LinkList)malloc(sizeof(LNode)))==NULL)
  return false;
 p->data=x;
 q=L;
 for(k=1;k<i;k++)
 {
  q="q-">next;
  if(q->next==NULL)
   return false;
 }
 p->next=q->next;
 q->next=p;
 return true;
}

//习题2.23
LinkList join_list(LinkList La, LinkList Lb)
{
 LinkList Lc,p,q;
 Lc=La;
 p=La->next;
 q=Lb->next;
 while(p!=NULL&&q!=NULL)
 {
  Lc->next=p;
  Lc=p;
  p=p->next;
  Lc->next=q;
  Lc=q;
  q=q->next;
 }
 if(p!=NULL)
  Lc->next=p;
 if(q!=NULL)
  Lc->next=q;
 Lc=La;
 return Lc;
}

//习题2.24
LinkList merge_list_descend(LinkList La, LinkList Lb)
{
 LinkList p,q,Lc,tmp;
 if(!create_list(&Lc))
  return NULL;
 
 p=La->next;
 q=Lb->next;
 while((p!=NULL)&&(q!=NULL))
 {
  if(p->data<q->data)
  {
    tmp=p->next;
    p->next=Lc->next;
    Lc->next=p;
    p=tmp;
  }
  else
  {
    tmp=q->next;
    q->next=Lc->next;
    Lc->next=q;
    q=tmp;
  }
 }
 while(p!=NULL)
 {
    tmp=p->next;
    p->next=Lc->next;
    Lc->next=p;
    p=tmp;                                                                                                                                                
 }

 while(q!=NULL)
 { 
    tmp=q->next;
    q->next=Lc->next;
    Lc->next=q;
    q=tmp;
 }
   
 return Lc;
}
  
//习题2.25
#define LIST_INIT_SIZE  100  
#define LISTINCREMENT   10

typedef struct{
 int *base;
 int length;
 int listsize;
}SqList;

bool init_sqlist(SqList *L)
{
 if((L->base=(int *)malloc(sizeof(int)*LIST_INIT_SIZE))==NULL)
  return false;
 
 L->length=0;
 L->listsize=LIST_INIT_SIZE;
 return true;
}

bool intersect_sqlist1(SqList *La, SqList *Lb,SqList *Lc)
{
 int i,j,k;
 //if(La->length+Lb->length>LIST_INIT_SIZE)
  //return false;
 
 for(i=0,j=0,k=0;i<La->length&&j<Lb->length&&k<LIST_INIT_SIZE;)
 {
  if(La->base<Lb->base[j])
   i++;
  else if(La->base>Lb->base[j])
   j++;
  else
  {
   Lc->base[k++]=Lb->base[j];
   i++;
   j++;
  }
 }
 if(k>=LIST_INIT_SIZE)
  return false;
 
 Lc->length=k;
 return true;
}