当前位置：首页 > news >正文

双向循环链表运用（2）

news 来源：原创 2024/5/10 17:14:09

问题描述：一双向循环链表，每个结点除了prior,data和next三个域外，还增设了一个访问频度域freq。链表启用前，freq为0，每对链表进行一次LOCATE(L，x)的操作后，该结点的freq加1，同时调整链表中结点之间的次序，使得被频繁访问的结点总是靠近表头结点

。编写符合上述要求的LOCATE算法。

问题分析：

重新把问题打在上面，更好地理解了一遍，也提高了自己的概括能力，挺好！

看吧，当自己写时，总感觉有那么些别扭，可是看着别人的就豁然开朗，自己还没想到豁然开朗，思维的锻炼还不够。。。

好吧，既然你已经看懂了答案了，很清晰的逻辑。但是我不想让自己现在就根据刚看的，然后写出来，看看明天还记不记得，今天暂且到这里吧。【2013-04-22】

实现代码：(暂存)

  1 #include<stdio.h>
  2  #include<stdlib.h>
  3  typedef  struct DuLNode{
  4   int  data;
  5   int freq;
  6   struct  DuLNode  *prior;//前驱结点
  7   struct  DuLNode  *next;//后继结点
  8  }DuLNode,*DuLinkList;
  9  void add(DuLinkList &L,int value)
 10  {
 11      if(L==NULL)
 12      {
 13         L=(DuLinkList)malloc(sizeof(DuLNode));
 14         L->data=value;
 15         L->next=L;
 16         L->prior=L;
 17         L->freq=0;
 18      }
 19      else
 20      {
 21         DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode));
 22         temp->data=value;
 23         temp->freq=0;
 24         L->prior->next=temp;
 25         temp->prior=L->prior;
 26         temp->next=L;
 27         L->prior=temp;//这下应该明白为什么是在这里插入。      
 28      }
 29  }
 30  void print(DuLinkList L)
 31  {
 32      if(L==NULL)
 33          printf("链表为空！");
 34      else
 35          if(L->prior==L)//只有一个结点的情况
 36              printf("%d",L->data);
 37          else//循环链表中多个结点的情况
 38          {
 39              DuLinkList cur=L;
 40              printf("%d",cur->data);
 41              while((cur=cur->next)!=L)
 42                  printf("%d",cur->data);
 43          }
 44  }
 45  void ListLocate_Dul(DuLinkList  &L, int e)
 46  {
 47       DuLinkList p,q;
 48       p=L;
 49       while(p->data!=e)
 50       {
 51         p=p->next;
 52         if((p==L)&&(p->data!=e)) //有待改进
 53         {
 54            printf("没有找到你要找的数：%d\n",e);
 55            return;
 56           //exit(0);//这个用的挺危险的。。。会结束程序，而不是此函数的返回值
 57         }
 58       }
 59       p->freq++;//p指向找到的数据
 60       p->prior->next=p->next;//将此结点抽离出来
 61       p->next->prior=p->prior;
 62       //插入到合适的位置
 63       q =L;
 64       while(true) 
 65       {
 66           if(p->freq>=q->freq)
 67                 break;
 68           else
 69              q=q->next; 
 70       }
 71        // if(q==L)
 72        //{
 73        //     p->next=q->next;
 74        //       q->next=p;
 75        //       p->prior=q->prior;
 76        //        q->prior=p;  
 77        // }
 78        // else
 79        //{
 80               q->prior->next=p;
 81               p->prior=q->prior;
 82               p->next=q;
 83               q->prior=p;//这还是插入之前呢。
 84        //}
 85  }
 86  int main()
 87  {
 88     DuLinkList L=NULL,pt;
 89     int temp;
 90     printf("创建循环链表：\n");
 91     while(scanf("%d",&temp)&&(temp!=-1))
 92     {
 93       add(L,temp);
 94     }
 95     printf("输入你要访问的数：\n");
 96     while(true){
 97     scanf("%d",&temp);
 98     if(temp==-1)
 99         break;
100     else
101        ListLocate_Dul(L,temp);
102     }
103     printf("访问后，链表数据调整为：\n");
104     pt=L;
105     int i=0;
106    // while(i<3)
107     //{
108        printf("数据元素为：%d,频率为：%d\n",pt->data,pt->freq);
109        pt=pt->next;
110     
111     //}
112  }

View Code

这个代码遇到的问题，访问第一个结点的处理方法跟其他位置的结点不同，为什么当p为第一个结点时，L没有抽离出第一个结点，但是其他位置却可以，按照分析，应该可以分离出第一个结点，以至于后面是第一个结点时要特殊处理，但是我却认为可以不用，这个地方就出现问题。。。。        p->freq++;//p指向找到的数据
      p->prior->next=p->next;//将此结点抽离出来
      p->next->prior=p->prior;
      //插入到合适的位置

用C#实现的链表的代码，没调整过来。。。

  1 using System;
  2 using System.Collections.Generic;
  3 using System.Linq;
  4 using System.Text;
  5 
  6 namespace SqList
  7 {
  8     class Program
  9     {
 10         #region 链表结点的数据结构
 11         public class Node
 12         {
 13             public int data;//结点数据域
 14             public int freq;//访问频率
 15             public Node next;
 16         }
 17         #endregion
 18         public class SqL
 19         {
 20             #region 将节点添加到链表的末尾
 21             public Node ChainListAddEnd(Node  head, int data)
 22             {
 23                 Node node = new Node();//申请一个新的结点
 24                 node.data = data;
 25                 node.freq = 0;
 26                 node.next = null;
 27                 //头为空，说明是一个空链表
 28                 if (head == null)
 29                 {
 30                     head = node;
 31                     return head;
 32                 }
 33                 //获取当前链表的最后一个结点
 34                 ChainListGetLast(head).next = node;
 35                 return head;
 36             }
 37             #endregion
 38 
 39             #region 得到当前链表的最后一个结点
 40             public Node ChainListGetLast(Node head)
 41             {
 42                 if (head.next == null)
 43                     return head;
 44                 return ChainListGetLast(head.next);//用递归返回当前链表中的最后一个结点
 45             }
 46             #endregion
 47 
 48             #region 将节点添加到链表的开头
 49             public  Node ChainListAddFirst(Node head, int data)
 50             {
 51                 Node node = new Node();
 52                 node.data = data;
 53                 node.freq = 0;
 54                 node.next = head;
 55                 head = node;
 56                 return head;
 57             }
 58             #endregion
 59 
 60             #region 将节点插入到指定位置
 61             public Node ChainListInsert(Node head, int key, int data)
 62             {
 63                 if (head == null)
 64                     return null;
 65                 if (head.data==key)
 66                 {
 67                     Node node = new Node();
 68                     node.data = data;
 69                     node.freq = 0;
 70                     node.next = head.next;
 71                     head.next = node;
 72                 }
 73                 ChainListInsert(head.next, key, data);
 74                 return head;
 75             }
 76             #endregion
 77 
 78             #region 删除结点
 79             public Node ChainListDelete(Node head, int key)
 80             {
 81                 if (head == null)
 82                     return null;
 83                 //这里针对只有一个结点的解决方案
 84                 if (head.data==key)
 85                 {
 86                     if (head.next != null)
 87                         head = head.next;
 88                     else
 89                         return head = null;
 90                 }
 91                 else
 92                 {
 93                     //判断一下此节点是否是要删除的结点的前一结点
 94                     while (head.next != null &&head.next.data==key)
 95                     {
 96                         head.next = head.next.next;
 97                     }//删除的方法有点奇怪
 98                 }
 99                 ChainListDelete(head.next, key);//又用到了递归。。。
100                 return head;
101             }
102             #endregion
103 
104             #region 通过关键字查找指定的结点
105             public Node ChainListFindByKey(Node head, int key)
106             {
107                 if (head == null)
108                     return null;
109                 if (head.data == key)
110                 {
111                     head.freq++;
112                     return head;
113                 }
114                 return ChainListFindByKey(head.next, key);
115             }
116             #endregion
117 
118             #region 获取链表的长度
119             public int ChanListLength(Node head)
120             {
121                 int count = 0;
122                 while (head != null)
123                 {
124                     count++;
125                     head = head.next;
126                 }
127                 return count;
128             }
129             #endregion
130         }
131 
132         static void Main(string[] args)
133         {
134             SqL mysql = new SqL();
135             Node mynode = null;
136            mynode=mysql.ChainListAddFirst(mynode, 1);
137            mynode=mysql.ChainListAddEnd(mynode, 2);
138            mynode=mysql.ChainListAddEnd(mynode, 3);
139            mynode=mysql.ChainListAddEnd(mynode, 4);
140            Display(mynode);
141            mynode = mysql.ChainListInsert(mynode, 3, 5);
142            Console.WriteLine("增加结点后，显示的值为：");
143            Display(mynode);
144            mynode = mysql.ChainListDelete(mynode, 2);
145            Console.WriteLine("删除结点2后，显示的值为：");
146            Display(mynode);
147            mynode = mysql.ChainListFindByKey(mynode,1);
148           // mynode = mysql.ChainListDelete(mynode, 1);
149            Console.WriteLine("查找结点1后，显示的值为：");
150            Display(mynode);
151            Console.ReadKey();
152         }
153         public static void Display(Node head)
154         {
155            Console.WriteLine("****链表数据如下*****"); 
156             var tempNode=head;
157             while(tempNode!=null)
158             {
159                 Console.WriteLine("数据值为："+tempNode.data+"频率为："+tempNode.freq);
160                 tempNode=tempNode.next;
161             }
162         }
163        }
164  }

View Code

问题描述：

带头结点的双向循环链表表示的线性表L=(a1,a2,...,an). 写一时间复杂度为O(n)的算法，将L改造为L=(a1,a3,....,an,.....a4,a2);

问题分析：

傻了，按照刚才那道题的分析虽然有点眉目，可是做不下去了，思路断了。我的想法就是给这个链表两个指针p,q. 然后再遍历线性表L，遍历的同时给它一整形变量 COUNT,判断是奇数还是偶数，当是奇数是将这个值赋值给p;然后下一个奇数再赋值给p是怎么赋值的呢？是不是指针p往后移，(对哦，做完后面的题，思路是相近的)然后赋值就行？同样的办法得到q，最后再将q的表头插入到p的表尾，整合成循环链表。(或许这些是靠经验？没做过的题，自己有些想法，但是不知道具体怎么做，但愿自己在这些经验中多多吸取精华，思路是最重要的，以后自己不可能总是碰到自己以前做过的题，你不能下次碰到类似的题又不会了，举一反三啊)

呀呀，看了答案后，恍然大悟呀，作者真是聪明。参考算法：

代码实现：

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 typedef  struct DuLNode{
 4  int  data;
 5  int freq;
 6  struct  DuLNode  *prior;//前驱结点
 7  struct  DuLNode  *next;//后继结点
 8 }DuLNode,*DuLinkList;
 9 
10 void add(DuLinkList &L,int value)
11 {
12     if(L==NULL)
13     {
14        L=(DuLinkList)malloc(sizeof(DuLNode));
15        L->data=value;
16        L->next=L;
17        L->prior=L;
18        L->freq=0;
19     }
20     else
21     {
22        DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode));
23        temp->data=value;
24        temp->freq=0;
25        L->prior->next=temp;
26        temp->prior=L->prior;
27        temp->next=L;
28        L->prior=temp;//这下应该明白为什么是在这里插入。      
29     }
30 }
31 void print(DuLinkList L)
32 {
33     if(L==NULL)
34         printf("链表为空！");
35     else
36         if(L->prior==L)//只有一个结点的情况
37             printf("%d",L->data);
38         else//循环链表中多个结点的情况
39         {
40             DuLinkList cur=L;
41             printf("%d",cur->data);
42             while((cur=cur->next)!=L)
43                 printf("%d",cur->data);
44         }
45 }
46 void ListChange_Dul(DuLinkList &L)
47 {
48   int i=1;
49   DuLinkList p,q,r;
50   p=L;
51   r=L->prior;
52   while(p!=r)
53   {
54      if(i%2==0)
55      {
56          q=p;
57          p=p->next;
58          //将此节点分离出来
59          q->prior->next=q->next;
60          q->next->prior=q->prior;
61          //将此节点插到头结点的左面
62          q->prior=r->next->prior;
63          r->next->prior=q;
64          q->next=r->next;
65          r->next=q;
66 
67          
68      }
69      else
70          p=p->next;
71      i++;
72   }
73 }
74 int main()
75 {
76    DuLinkList L=NULL,pt;
77    int temp;
78    printf("创建循环链表：\n");
79    while(scanf("%d",&temp)&&(temp!=-1))
80    {
81      add(L,temp);
82    }
83    ListChange_Dul(L);
84    print(L);//现在能访问了
85 }