单循环链表的实现
1 typedef int Elemtype; 2 typedef struct node{ 3 Elemtype data; 4 struct node *next; 5 }node,*linklist; 6 7 void createList_L(linklist &l){ 8 l=(linklist )malloc(sizeof(node)); 9 linklist p=l,q; 10 int x; 11 scanf ("%d",&x); 12 while (x!=-999){ 13 q=(linklist )malloc(sizeof(node)); 14 q->data=x; 15 p->next=q; 16 p=q; 17 scanf ("%d",&x); 18 } 19 q->next=l; 20 l=q; 21 } 22 23 void displayList_L(linklist &l){ 24 linklist p=l->next->next; 25 while (p!=l->next){//这里的头结点是l->next 26 printf ("%d ",p->data); 27 p=p->next; 28 } 29 printf (" "); 30 } 31 //把两个循环单链表合并成一个链表 32 void merge(linklist &la,linklist &lb,linklist &lc){ 33 linklist p=la->next,q=lb->next; 34 la->next=q->next; 35 lb->next=p; 36 lc=lb; 37 free(q); 38 }
双向链表的基本实现
1 typedef int Elemtype; 2 typedef struct node{ 3 Elemtype data; 4 struct node *next; 5 struct node *prior; 6 }node,*linklist; 7 8 void createList_L(linklist &l){ 9 l=(linklist )malloc(sizeof(node)); 10 linklist p=l,q; 11 int x; 12 scanf ("%d",&x); 13 while (x!=-999){ 14 q=(linklist )malloc(sizeof(node)); 15 q->data=x; 16 p->next=q; 17 q->prior=p; 18 p=q; 19 scanf ("%d",&x); 20 } 21 q->next=NULL; 22 l->prior=q; 23 } 24 25 void displayList_L(linklist &l){ 26 linklist p=l->next; 27 while (p!=NULL){//这里的头结点是l->next 28 printf ("%d ",p->data); 29 p=p->next; 30 } 31 printf (" "); 32 } 33 int listLength (linklist &l){ 34 linklist p=l->next; 35 int count=1; 36 while (p){ 37 p=p->next; 38 count ++; 39 }return count; 40 } 41 int listInsert_dul(linklist &l,int i,Elemtype e){ 42 if (i<1||i>listLength(l)+1) 43 { 44 printf ("position error! "); 45 return 0; 46 } 47 linklist p=l,q;int j=0; 48 while (p->next&&j<i-1){ 49 p=p->next;j++; 50 } 51 q=(linklist )malloc(sizeof(node)); 52 q->data=e; 53 q->prior=p; 54 q->next=p->next; 55 p->next->prior=q; 56 p->next=q; 57 return 1; 58 } 59 int listDelete_dul(linklist &l,int i,Elemtype &e){ 60 linklist p=l,q;int j=0; 61 if (i<1||i>listLength(l))return 0; 62 while (p->next&&j<i-1){ 63 p=p->next;j++; 64 } 65 e=p->next->data; 66 q=p->next; 67 p->next=q->next; 68 p->next->prior=p; 69 free(q); 70 return 1; 71 }
1 DuLNode * Locate_DuList(DuLinkedList &L,int x)//带freq域的双向循环链表上的查找 2 { 3 p=L.next; 4 while(p.data!=x&&p!=L) p=p->next; 5 if(p==L) return NULL; //没找到 6 p->freq++;q=p->pre; 7 while(q->freq<=p->freq) q=q->pre; //查找插入位置 8 if(q!=p->pre) 9 { 10 p->pre->next=p->next;p->next->pre=p->pre; 11 q->next->pre=p;p->next=q->next; 12 q->next=p;p->pre=q; //调整位置 13 } 14 return p; 15 }//Locate_DuList
思路：首先找到X所在位置，并让p指向它；
因为是非递增链表，p->freq++之后只能往左移动，所以通过prior指针来寻找插入位置。注意这里要判断一下if(q!=p->pre),这样就不用移动了。找到位置之后进行双向链表的插入算法。