问题描述：一双向循环链表，每个结点除了prior,data和next三个域外，还增设了一个访问频度域freq。链表启用前，freq为0，每对链表进行一次LOCATE(L，x)的操作后，该结点的freq加1，同时调整链表中结点之间的次序，使得被频繁访问的结点总是靠近表头结点
。编写符合上述要求的LOCATE算法。
问题分析：
重新把问题打在上面，更好地理解了一遍，也提高了自己的概括能力，挺好！
看吧，当自己写时，总感觉有那么些别扭，可是看着别人的就豁然开朗，自己还没想到豁然开朗，思维的锻炼还不够。。。
好吧，既然你已经看懂了答案了，很清晰的逻辑。但是我不想让自己现在就根据刚看的，然后写出来，看看明天还记不记得，今天暂且到这里吧。【2013-04-22】
实现代码：(暂存)
1 #include2 #include 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 else101 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 }
这个代码遇到的问题，访问第一个结点的处理方法跟其他位置的结点不同，为什么当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 #endregion103 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 #endregion117 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 #endregion130 }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 }
问题描述：
带头结点的双向循环链表表示的线性表L=(a1,a2,...,an). 写一时间复杂度为O(n)的算法，将L改造为L=(a1,a3,....,an,.....a4,a2);
问题分析：
傻了，按照刚才那道题的分析虽然有点眉目，可是做不下去了，思路断了。我的想法就是给这个链表两个指针p,q. 然后再遍历线性表L，遍历的同时给它一整形变量 COUNT,判断是奇数还是偶数，当是奇数是将这个值赋值给p;然后下一个奇数再赋值给p是怎么赋值的呢？是不是指针p往后移，(对哦，做完后面的题，思路是相近的)然后赋值就行？同样的办法得到q，最后再将q的表头插入到p的表尾，整合成循环链表。(或许这些是靠经验？没做过的题，自己有些想法，但是不知道具体怎么做，但愿自己在这些经验中多多吸取精华，思路是最重要的，以后自己不可能总是碰到自己以前做过的题，你不能下次碰到类似的题又不会了，举一反三啊)
呀呀，看了答案后，恍然大悟呀，作者真是聪明。参考算法：
代码实现：
1 #include2 #include 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 else21 {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 else36 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 else70 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 }