单链表的基本操作

• 按序号查找节点值算法

  int findNode(LinkedList *L,int i,int &e)
  {
  int j=0;
  LinkedList *ptr=L;
  
  while(ptr!=NULL && j<i)
  {
    j++;
    ptr=ptr->next;
  }
  if(NULL==ptr) return 0;
  else
  {
   e=ptr->data;
   return 1;
  }
  }
  

• 按元素值查找序号算法

  int findNode(LinkedList *L,int key)
  {
  LinkedList *ptr=L->next;
  int index=0;
  
  while(ptr!=NULL && ptr->data!=key)
  {
    index++;
    ptr=ptr->next;
  }
  
  if(ptr!=NULL) return index;
  else return 0;
  }
  

• 插入元素：将值为\(x\)的元素的新节点插入到第\(i\)个节点的位置上，即先在单链表中找到插入节点的前驱节点，即第\(i-1\)个节点，再在其后插入新节点。

  s->next=p->next;
  p->next=s;
  

• 删除元素:将单链表中的第 \(i\) 个节点删除。

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

有一个线性表\((a_1,a_2,...,a_n)\) 采用带头节点的单链表\(L\)存储，设计一个就地算法将其就地逆置，所谓“就地”是指算法的辅助空间为\(O(1)\).

void reverse(LinkedList * & L)
{
  LinkedList *ptr=L->next;
  LinkedList *q;
  L->next=NULL;
  while(ptr!=NULL)
  {
    q=ptr->next;
    ptr->next=L->next;
    L->next=ptr;
    ptr=q;
  }
}

设\(C=\{a_1,b_1,a_2,b_2,...,a_n,b_n\}\) 为一线性表，采用带头节点的\(hc\)单链表存放，设计一个就地算法，将其拆分为两个线性表（它们都是用单链表存放）使得\(A=\{a_1,a_2,...,a_n\},B=\{b_1,b_2,...,b_n\}\)

void split(LinkedList *hc,LinkedList *&ha,LinkedList *&hb)
{
  LinkedList *r=ha;
  LinkedList *p=hc->next;
  LinkedList *q;
  
  hb->next=NULL;
  while(p!=NULL)
  {
    r->next=p;
    r=p;
    
    p=p->next;
    
    q=p->next;
    p->next=hb->next;
    hb->next=p;
    p=q;
  }
  r->next=NULL;  //别忘了
}

王道题讲解

有一个带头结点的单链表\(L\),设计一个算法使其元素递增有序。

void sort（LinkedList * &L)
{
  LinkedList *p=L->next;
  LinkedList *q=p->next;
  LinkedList *pre,tmp;
  
  p->next=NULL:   //含有一个元素的有序单链表
  p=q;
  
  while(p!=NULL)
  {
    q=p->next;
    pre=L;   //单链表只能从头开始往后寻找节点
    
    tmp=pre->next;
    while(tmp!=NULL && tmp.data < p->data)
    {
      pre=tmp;
      tmp=tmp->next;
    }
    
    p->next=pre->next;
    pre->next=p;
    
    p=q;
  }
}

给定两个单链表，编写算法找出其公共的节点
分析：从头到尾扫描单链表\(A\)，判断当前元素是否在单链表\(B\)中出现，若在则插入到单链表\(C\)中。

void findSameNode(LinkedList *A,LinkedList *B,LinkedList *&C)
{
  LNode *p=A->next;
  LNode *q=B->next;
  LNode *r;
  
  C=(LNode*)malloc(sizeof(LNode));
  C->next=NULL;
  r=C;
  while(p!=NULL)
  {
    q=B->next;
    while(q!=NULL && q.data!=p.data)
         q=q->next;
    
    if(q!=NULL)
    {
      r->next=p;
      r=p;
    }
    p=p->next;
  }
}

\(2010\)年联考真题
设将\(n\) 个整数存放到一维数组R中。试设计一个在时间和空间尽可能高的算法。将\(R\)中保存的序列循环左移\(p （0 \lt q\lt n)\)个位置，即将\(R\)中的数据由\((X_0,X_1,...,X_{n-1})\) 变换为\((X_p,X_p+1,...,X_{n-1},X_0,X_1,....,X_{p-1})\)

void reverse(int R[],int left,int right)
{
 int i=left,j=right;
 int tmp;
 while(i<j)
 {
   tmp=R[i];
   R[i]=R[j];
   R[j]=tmp;
   i++;
   j--;
 }
}

void leftShift(int R[],int n,int p)
{
  if(p>0 &&p<n)
  {
   reverse(R,0,n-1);
   reverse(R,0,n-p-1);
   reverse(R,n-p,n-1);
  }
}

\(2011\)年联考真题
给定两个数组\(A\)和\(B\),数组的长度为\(n\),两个数组都分别有序，求出两个数组中的所有数的中位数。

int search(int A[],int B[],int n)
{
  int i,j,k;
  i=j=k=0;
  while(i<n &&j<n)
  {
    k++;
    if(A[i]<B[j])
    {
      if(k==n)
        return A[i];
       i++;
    }
    else
    {
      if(k==n)
        return B[j];
      j++;
    }
  }
}

分别求出两个升序序列\(A\)，\(B\)的中位数，记为\(a\),\(b\)。若\(a=b\),则\(a\)或\(b\)即为所求，否则舍弃\(a,b\)中较小者所在序列的较小一半，同时舍弃较大者所在序列的较大一半，要求两次舍弃的元素个数相同（每次从左侧和右侧删除相同个数的元素后，新的两个数组，它们的中位数与原始数组的中位数是相同的）。重复上述过程，直到两个序列均只含一个元素为止，则较小的即为所求的中位数。

int searchMid(int A[],int B[],int n)
{
  int startA,midA,endA;
  int startA,midB,endB;
  
  startA=0; endA=n-1; 
  startB=0; endB=n-1;
  
  while(startA!=endA || startB!=endB)
  {
     midA=(startA+endA)/2;
     midB=(startB+endB)/2;
     
     if(A[midA]==B[midB])
        return A[midA];
        
     if(A[midA]<B[midB])
     {
       if((startA+endA)%2==0)//若元素个数为奇数时
       {
         startA=midA;  //舍弃A中间点以前的部分且保留中间点
         endB=midB;    //舍弃B中间点以后的部分且保留中间点
       }
       else  //若元素个数为偶数时
       {
        startA=midA+1;  //舍弃A的前半部分,每次舍弃的长度相同，可以保证同时到达
        endB=midB;      //舍弃B的后半部分
       }
     }
     else if(A[midA] > B[midB])
     {
       if((startA+endA)%2==0)//若元素个数为奇数时
       {
         endA=midA;  //舍弃A中间点以后的部分且保留中间点
         startB=midB;//舍弃B中间点以前的部分且保留中间点
       }
       else  //若元素个数为偶数时
       {
        endA=midA;       //舍弃A的后半部分
        startB=midB+1;   //舍弃B的前半部分
       }
     }
  }
  
  return A[startA]<B[startB]?A[startA]:B[startB];
}

• 若\(A\)和\(B\)数组的长度为\(2k+1\)，取\(A\)数组的中位数为\(A[k]\)，\(B\)数组的中位数为\(B[k]\)，\(A\)和\(B\)组合起来的中位数应该是第\(2k+1\)大的那个数。如果\(A[k]==B[k]\)，则\(A[k]\)必定为第\(2k+1\)大的数，是所有数字的中位数。如果\(A[k]\gt B[k]\)，则\(A[k]\)至少为第\(2k+2\)大的数，\(B[k]\)至多为第\(2k+1\)大的数，中位数介于\(B[k]\)和\(A[k]\)之间。
• 若\(A\)和\(B\)数组的长度为\(2k\)，按照题目所述条件，则\(A\)的中位数为\(A[k-1]\),则\(B\)的中位数为\(B[k-1]\),\(A\)和\(B\)组合起来的中位数应该是第\(2k\)大的那个数，若\(A[k-1]==B[k-1]\),则\(B[k-1]\)必为第\(2k\)大的那个数，即所有数字的中位数。如果\(A[k-1]\gt B[k-1]\)，则\(A[k-1]\)至少为第\(2k\)大的数，\(B[k-1]\)至多为第\(2k-1\)大的数，中位数介于\(B[k-1]\)和\(A[k-1]\)之间。

\(2013\)年联考真题
?
主元素问题方法一：对数组中元素进行计数，然后查看出现次数最多的元素，若次数大于一半，则为主元素。这种方式只需要对数组扫描一遍，时间复杂度为\(O(n)\),空间复杂度为\(O(n)\)。

int mainElement(int A[],int n)
{
  int *p=(int*)malloc(sizeof(int)*n);
  int max=0;
  
  for(int i=0;i<n;i++) p[i]=0;
  
  for(int i=0;i<n;i++)
  {
    p[A[i]]++;
    if(p[A[i])>p[A[max]]) max=A[i];
  }
  
  if(p[max]>(n/2)  return max;
  else return -1;
}

使用快速排序，然后统计相同元素出现的最大次数

void quickSort(int A[],int left,int right)
{
 int i=left,j=right;
 int tmp;
 
 if(i<j)
 {
    tmp=A[i];
    while(i<j)
    {
      while(i<j && A[j]>tmp) j--;
      A[i]=A[j];
      i++;
      while(i<j && A[i]<=tmp) i++;
      A[j]=A[i];
      j--;
    }
    A[i]=tmp;
    quickSort(A,left,i-1);
    quickSort(A,i+1,right);
 }
}
//然后使用平台算法

数组中存在主元素时，所有的非主元素个数和必少于一半。如果让主元素与一个非主元素"配对“，则最后多出来的元素（没有元素与之配对）就是主元素。从前往后扫描数组元素，假定遇到的当前值选定为主元素，再次遇到它时计数加1，遇到不等的值时，计数减1。当计数减为0后，将遇到的下一个值重新选定为主元素。扫描完毕，当前选定的元素（计数值大于0）可能是主元素，但未必是主元素。还需要对数组再进行一次扫描，记录它出现的实际个数，以判定它是否是主元素。

void mainElemment(int A[],int n)
{
 int base=A[0];
 int count=1;
 int count2=0;
 for(int i=1;i<n;i++)
 {
   if(A[i]==base)
      count++;
   else 
   {  
       if(count>0) count--;
       else 
       {
        base=A[i];
        count=1;
       }
    }
 }
 
 if(count>0)
 {
    count2=0;
    for(int i=0;i<n;i++)
    {
      if(base==A[i])
        count2++;
    }
 }
 if(count2>(n/2))  return base;
 else return -1;
}

线性表