ds_3

线性表

1、设线性表L=(a1,a2,a3, …,an-2,an-1,an)采⽤带头结点的单链表保存，链表中结点定义如下:

typedef struct node
{   
    int data;
    struct node* next;
} NODE;

2、请设计⼀个空间复杂度为0(1)且时间上尽可能⾼效的算法，重新排列L中的各结点,得到线性表L’=(a1,an,a2,an-1,a3,an-2,…),并计算空间复杂度。

void changeList(NODE * h)
{
   NODE *p,*q,*r,*s;
   p=q=h;
   while(q->next ! =NULL) //寻找中间结点
   {
       p=p->next; //p⾛⼀步
       q=q->next;
       if(q->next!=NULL) q=q->next: //q ⾛两步
   }
   q=p->next; //p所指结点为中间结点，q为后半段链表的⾸结点
   p->next=NULL;
   while(q!=NULL) //将链表后半段逆置(利⽤头插法)
   {
       r=q->next;
       q->next=p->next;
       p->next=q;
       q=r;
   }
   s=h->next; //s指向前半段的第⼀个数据结点，即插⼊点
   q=p->next; //q指向后半段的第⼀个数据结点
   p->next=NULL:
   while(q!=NULL) //将链表后半段的结点插⼊到指定位置
   {
       r=q->next; //r指向后半段的下⼀个结点
       q->next=s->next; //将q所指结点插⼊到s所指结点之后
       s->next=q:
       s=q->next; //s指向前半段的下⼀个插⼊点
       q=r;
   }
}
算法时间复杂度为O(

3、已知两个链表A和B分别为两个集合，其元素递增排列。请设计⼀个算法，⽤于求出A与B的交集，并存放在A链表中。

思路：A与B的交集是指同时出现在两个集合中的元素，因此，此题的关键点在于:依次摘取两个表中相等的元素重新进⾏链接,删除其他不等的元素。假设待合并的链表为La和Lb，合并后的新表使⽤头指针Lc(Lc的表头结点设为La的表头结点)指向。pa和 pb分别是链表La和Lb的⼯作指针，初始化为相应链表的⾸元结点。从⾸元结点开始进⾏⽐较，当两个链表La和Lb均为到达表尾结点时，如果两个表中的元素相等，摘取La表中的元素，删除Lb表中的元素;如果其中⼀个表中的元素较⼩，删除此表中较⼩的元素，此表的⼯作指针后移。当链表La和Lb有⼀个到达表尾结点为空时，依次删除另⼀个⾮空表中的所有元素。最后释放链表Lb的头结点。

void Intersection(LinkList &La, LinkList &Lb)
{
   LNode* pa = La->next; //pa是链表La的⼯作指针，初始化为⾸元结点
   LNode* pb = Lb->next; //pb是链表Lb的⼯作指针，初始化为⾸元结点
   LNode* pc = La; //⽤La的头结点作为Lc的头结点
   LNode* u;
   while(pa！=null && pb!=null)
   {
     if(pa->data == pb->data) //相等，交集并⼊结果表中
     {
       pc->next = pa;
       pc = pa;
       pa = pa->next;
       u = pb;
       pb = pb->next;
       free(u);
     }
     else if(pa->data < pb->data) //删除较⼩者La中的元素
     {
       u = pa;
       pa = pa->next;
       free(u);
     }
     else //删除较⼩者La中的元素
     {
       u = pb;
       pb = pb->next;
       free(u);
     }
   }
   while(pa) //Lb为空，删除⾮空表La中的所有元素
   {
     u = pa;
     pa = pa->next;
     free(u);
   }
   while(pb) //La为空，删除⾮空表Lb中的所有元素
   {
     u = pb;
     pb = pb->next;
     free(u);
   }
     pc->next = NULL;
     free(Lb) 
}

4、有⼀个带头节点的双链表L，每个节点中除有prior、data和next三个域外，还有⼀个访问频度域 freq ，在链表被起⽤之前，其值均初始化为零。每当进⾏LocateNode(L,x)运算时，令元素值为x的节点中freq域的值加1，并调整表中节点的次序，使其按访问频度的递减序排列，以便使频繁访问的节点总是靠近表头。试写⼀符合上述要求的LocateNode运算的算法。

思路：在DLinkList类型的定义中添加int freq域，将所有节点的freq域均初始化为0。在查找到data域为x的节点p时，将其freq域增1。再找到p节点的前驱节点pre，若pre不是头节点，且满⾜pre.freq < p.freq，则pre指针再向前移，直到找到⼀个节点pre，满⾜pre.freq≥p.freq，则将p节点移到pre节点之后，如图所示，其操作是先删除p节点,再将其插⼊到*****pre节点之后。

typedef struct DLNode {
   int data;
   int freq; //频度
   struct DLNode *prior;
   struct DLNode *next;
}DLNode,*DLinkList;
int LocateNode(DLinkList &L, int x)
{
   DLinkList *p = L->next, *pre;
   while(p!=NULL && p->data!=x)
     p = p->next; //找到data域值为x的结点p;
   if(p == NULL) //如果没有找到，返回
     return 0; 
   else
   { //找到这样的结点
     p.freq++; //频度freq +1
     pre = p->prior; //pre为p的前驱结点
     if(pre != L)
     {
       while(pre != L && pre.freq < p.freq) //找到pre结点
         pre = pre->prior;
       p->prior->next = p->next; //删除结点p
       if(p->next != NULL)
         p->next->prior = p->prior;
       p->next = pre->next; //将结点p插⼊到pre结点之后
       if(pre->next != NULL)
         pre->next->prior = p;
       pre->next = p;
       p->prior = pre;
     }
     return 1;
   }
}