öλÔÓéÀֵǼÈë¿ÚÏÂÔØ

¶þ¡¢Ëã·¨Éè¼ÆÌ⣺

2.7 (±¾Ìâ¸ÐлpastarµÄÖ¸Õý)
½â£º

Ëã·¨ÈçÏÂ:
#define ListSize 100// ¼Ù¶¨±í¿Õ¼ä´óСΪ100
#include
#include
void Error(char * message)
{
fprintf(stderr,"´íÎó:%s/n",message);
exit(1);
}//´Ó0¿ªÊ¼¼Æ£¬ ±í¿Õ¼ä´óСӦΪ101ÁË
typedef  int Datatype ;//¼Ù¶¨DatatypeµÄÀàÐÍΪintÐÍ
typedef  struct{
Datatype  data[ListSize];// ÏòÁ¿dataÓÃÓÚ´æ·Å±í½áµã
int length; //  µ±Ç°µÄ±í³¤¶È
} Seqlist;
//ÒÔÉÏΪ¶¨Òå±í½á¹¹

//------------ÒÔÏÂΪҪÇóËã·¨----------
void InsertList ( Seqlist *L, Datatype x, int i)
{
//½«Ð½áµãx²åÈëLËùÖ¸µÄ˳Ðò±íµÄµÚi¸ö½áµãaiµÄλÖÃÉÏ
int j;
if ( i < 0 || i > L -> length )
Error("position error");// ·Ç·¨Î»Öã¬Í˳ö
if ( L->length>=ListSize )
Error("overflow");
for ( j=L->length-1 ; j >= i ; j --)
L->data[j+1]=L->data [j];
L->data[i]=x ;
L->length++ ;
}

void DeleteList ( Seqlist *L, int i )
{// ´ÓLËùÖ¸µÄ˳Ðò±íÖÐɾ³ýµÚi¸ö½áµãai
int j;
if ( i< 0 || i > L-> length-1)
Error( " position error" ) ;
for ( j = i+1 ; j < L-> length ; j++ )
   L->data [ j-1 ]=L->data [ j]; // ½áµãÇ°ÒÆ
L-> length-- ; //±í³¤¼õС
}
//===========ÒÔÏÂΪÑéÖ¤Ëã·¨¶ø¼Ó=======
void Initlist(Seqlist *L)
{
L->length=0;
}
void main()
{
Seqlist *SEQA=new Seqlist;
Initlist(SEQA);
int i;
for (i=0;i {
InsertList (SEQA,i,i);
printf("%d/n",SEQA->data[i]);
}
DeleteList (SEQA,99);
for (i=0;i {
printf("%d/n",SEQA->data[i]);
}
}

--------------------------------------------------------------------------------

(´ð°¸¼°µãÆÀ) 2.8 ÊÔ·Ö±ðÓÃ˳Ðò±íºÍµ¥Á´±í×÷Ϊ´æ´¢½á¹¹£¬ÊµÏÖ½«ÏßÐÔ±í(a0,a1,...an-1)¾ÍµØÄæÖõIJÙ×÷£¬Ëùν"¾ÍµØ"Ö¸¸¨Öú¿Õ¼äӦΪO(1)¡£

2.8 ½â£º

°´ÌâÒ⣬Ϊ½«ÏßÐÔ±íÄæÖ㬵«¸¨Öú¿Õ¼ä²»ÄÜËæ±íµÄ¹æÄ£Ôö´ó¡£ÎÒÃÇ·Ö±ðÌÖÂÛ˳Ðò±íºÍµ¥Á´±íµÄÇé¿ö£º

1. ˳Ðò±í£º
Òª½«¸Ã±íÄæÖ㬿ÉÒÔ½«±íÖеĿªÊ¼½áµãÓëÖն˽áµã»¥»»£¬µÚ¶þ¸ö½áµãÓëµ¹ÊýµÚ¶þ¸ö½áµã»¥»»£¬Èç´Ë·´¸´£¬¾Í¿É½«Õû¸ö±íÄæÖÃÁË¡£Ëã·¨ÈçÏ£º

// ±í½á¹¹¶¨ÒåͬÉÏ

void  ReverseList(  Seqlist *L)
{
Datatype   t ; //ÉèÖÃÁÙʱ¿Õ¼äÓÃÓÚ´æ·Ådata
int i;
for ( i=0 ; i < L->length/2 ; i++)
{   t = L->data[i];//½»»»Êý¾Ý
   L -> data[ i ]  = L -> data[ L -> length - 1 - i ]  ;
   L -> data[ L -> length - 1 - i ] = t  ;
}
}

2. Á´±í£º

Ò²ÊÇ¿ÉÒÔÓý»»»Êý¾ÝµÄ·½Ê½À´´ïµ½ÄæÖõÄÄ¿µÄ£¬µ«ÊÇÓÉÓÚÊǵ¥Á´±í£¬Êý¾ÝµÄ´æÈ¡²»ÊÇËæ»úµÄ£¬Òò´ËË㷨ЧÂÊÌ«µÍ£¬ÎÒÃÇ¿ÉÒÔÀûÓÃÖ¸ÕëµÄÖ¸Ïòת»»À´´ïµ½±íÄæÖõÄÄ¿µÄ¡£Ëã·¨ÊÇÕâÑùµÄ£º

// ½á¹¹¶¨ÒåÂÔ

LinkList  ReverseList( LinkList  head  )
{
// ½«head ËùÖ¸µÄµ¥Á´±íÄæÖÃ
ListNode *p  ,*q ;//ÉèÖÃÁ½¸öÁÙʱָÕë±äÁ¿
if( head->next && head->next->next)
{
//µ±Á´±í²»ÊÇ¿Õ±í»òµ¥½áµãʱ
p=head->next;
q=p->next;
p -> next=NULL;//½«¿ªÊ¼½áµã±ä³ÉÖն˽áµã

while (q)
{//ÿ´ÎÑ­»·½«ºóÒ»¸ö½áµã±ä³É¿ªÊ¼½áµã
p=q;
q=q->next ;
p->next = head-> next  ;
head->next = p;
}
return head;
}
return head;//ÈçÊÇ¿Õ±í»òµ¥½áµã±í£¬Ö±½Ó·µ»Øhead
}

--------------------------------------------------------------------------------

(´ð°¸¼°µãÆÀ) 2.9 Éè˳Ðò±íLÊÇÒ»¸öµÝÔöÓÐÐò±í£¬ÊÔдһËã·¨£¬½«x²åÈëLÖУ¬²¢Ê¹LÈÔÊÇÒ»¸öÓÐÐò±í¡£

2.9 ½â£º

ÒòÒÑ֪˳Ðò±íLÊǵÝÔöÓÐÐò±í£¬ËùÒÔÖ»Òª´ÓÍ·ÕÒÆðÕÒµ½µÚÒ»¸ö±ÈËü´ó(»òÏàµÈ)µÄ½áµãÊý¾Ý£¬°Ñx²åÈëµ½Õâ¸öÊýËùÔÚµÄλÖþÍÊÇÁË¡£Ëã·¨ÈçÏ£º

void InsertIncreaseList( Seqlist *L , Datatype x )
{
int i;
for ( i=0 ; i < L -> length && L->data[ i ] < x ; i++) ; // ²éÕÒ²¢±È½Ï,·ÖºÅ²»ÄÜÉÙ
InsertList ( L £¬x , i ); // µ÷ÓÃ˳Ðò±í²åÈ뺯Êý
}

--------------------------------------------------------------------------------

(´ð°¸¼°µãÆÀ) 2.10 Éè˳Ðò±íLÊÇÒ»¸öµÝ¼õÓÐÐò±í£¬ÊÔдһËã·¨£¬½«x²åÈëÆäºóÈÔ±£³ÖLµÄÓÐÐòÐÔ¡£

2.10 ½â£º
ÓëÉÏÌâÏàÀàËÆ£¬Ö»Òª´ÓÍ·ÕÒµ½µÚÒ»¸ö±ÈxС(»òÏàµÈ)µÄ½áµãÊý¾Ý£¬ÔÚÕâ¸öλÖòåÈë¾Í¿ÉÒÔÁË¡£Ëã·¨ÈçÏ£º

void InsertDecreaseList( Seqlist *L, Datatype x )
{
int i;
for (i=0; i< L -> length && L-> data[i] > x ; i++) ; //²éÕÒ
InsertList ( L , x , i ); // µ÷ÓÃ˳Ðò±í²åÈ뺯Êý
}

--------------------------------------------------------------------------------

(´ð°¸¼°µãÆÀ) 2.11 дһËã·¨ÔÚµ¥Á´±íÉÏʵÏÖÏßÐÔ±íµÄListLength(L)ÔËËã¡£

2.11 ½â£º

Çóµ¥Á´±í³¤Ö»ÄÜÓñéÀúµÄ·½·¨ÁË£¬´ÓÍ·Êýµ½Î²£¬×ÜÄÜÊý³öÀ´°É¡£Ëã·¨ÈçÏ£º

int ListLength ( LinkList L )
{
int len=0 ;
ListNode *p;
p=L; //Éè¸Ã±íÓÐÍ·½áµã
while ( p->next )
{
p=p->next;
len++;
}
return len;
}

--------------------------------------------------------------------------------

(´ð°¸¼°µãÆÀ) 2.12 ÒÑÖªL1ºÍL2·Ö±ðÖ¸ÏòÁ½¸öµ¥Á´±íµÄÍ·½áµã£¬ÇÒÒÑÖªÆ䳤¶È·Ö±ðΪmºÍn¡£ÊÔдһËã·¨½«ÕâÁ½¸öÁ´±íÁ¬½ÓÔÚÒ»Æð£¬Çë·ÖÎöÄãµÄËã·¨µÄʱ¼ä¸´ÔӶȡ£

2.12 ½â£º

Ëã·¨ÈçÏÂ:

LinkList Link( LinkList L1 , LinkList L2 )
{
//½«Á½¸öµ¥Á´±íÁ¬½ÓÔÚÒ»Æð
ListNode *p , *q ;
p=L1;
q=L2;
while ( p->next ) p=p->next; //²éÕÒÖն˽áµã
p->next = q->next ; //½«L2µÄ¿ªÊ¼½áµãÁ´½ÓÔÚL1Ö®ºó
return L1 ;
}

±¾Ëã·¨µÄÖ÷Òª²Ù×÷ʱ¼ä»¨·ÑÔÚ²éÕÒL1µÄÖն˽áµãÉÏ£¬ÓëL2µÄ³¤¶ÈÎ޹أ¬ËùÒÔ±¾ËãµÄ·¨Ê±¼ä¸´ÔÓ¶ÈΪ£º

m+1=O(m)

--------------------------------------------------------------------------------

(´ð°¸¼°µãÆÀ) 2.13 Éè AºÍBÊÇÁ½¸öµ¥Á´±í£¬Æä±íÖÐÔªËصÝÔöÓÐÐò¡£ÊÔдһËã·¨½«AºÍB¹é²¢³ÉÒ»¸ö°´ÔªËØÖµµÝ¼õÓÐÐòµÄµ¥Á´±íC£¬²¢ÒªÇó¸¨Öú¿Õ¼äΪO(1)£¬Çë·ÖÎöËã·¨µÄʱ¼ä¸´ÔӶȡ£

2.13  ½â£º

¸ù¾ÝÒÑÖªÌõ¼þ£¬AºÍBÊÇÁ½¸öµÝÔöÓÐÐò±í£¬ËùÒÔÎÒÃÇ¿ÉÒÔÒÔA±íΪ»ù´¡£¬°´ÕÕ²åÈëµ¥¸öÔªËصİ취°ÑB±íµÄÔªËزåÈëA±íÖУ¬Íê³Éºó£¬½«±íÄæÖþ͵õ½ÁËÒ»¸ö°´ÔªËØÖµµÝ¼õÓÐÐòµÄµ¥Á´±íCÁË¡£

Ëã·¨ÈçÏ£º

LinkList    MergeSort (  LinkList  A  , LinkList B )
{
// ¹é²¢Á½¸öµÝÔöÓÐÐò±íΪһ¸öµÝ¼õÓÐÐò±í