数据结构 循环链表、双向链表、一元多项式

单循环链表的实现

typedef int Elemtype; typedef struct node{ Elemtype data; struct node *next; }node,*linklist; void createList_L(linklist &l){ l=(linklist )malloc(sizeof(node)); linklist p=l,q; int x; scanf ("%d",&x); while (x!=-999){ q=(linklist )malloc(sizeof(node)); q->data=x; p->next=q; p=q; scanf ("%d",&x); } q->next=l; l=q; } void displayList_L(linklist &l){ linklist p=l->next->next; while (p!=l->next){//这里的头结点是l->next printf ("%d ",p->data); p=p->next; } printf ("\n"); } //把两个循环单链表合并成一个链表 void merge(linklist &la,linklist &lb,linklist &lc){ linklist p=la->next,q=lb->next; la->next=q->next; lb->next=p; lc=lb; free(q); }

双向链表的基本实现

typedef int Elemtype; typedef struct node{ Elemtype data; struct node *next; struct node *prior; }node,*linklist; void createList_L(linklist &l){ l=(linklist )malloc(sizeof(node)); linklist p=l,q; int x; scanf ("%d",&x); while (x!=-999){ q=(linklist )malloc(sizeof(node)); q->data=x; p->next=q; q->prior=p; p=q; scanf ("%d",&x); } q->next=NULL; l->prior=q; } void displayList_L(linklist &l){ linklist p=l->next; while (p!=NULL){//这里的头结点是l->next printf ("%d ",p->data); p=p->next; } printf ("\n"); } int listLength (linklist &l){ linklist p=l->next; int count=1; while (p){ p=p->next; count ++; }return count; } int listInsert_dul(linklist &l,int i,Elemtype e){ if (i<1||i>listLength(l)+1) { printf ("position error!\n"); return 0; } linklist p=l,q;int j=0; while (p->next&&j<i-1){ p=p->next;j++; } q=(linklist )malloc(sizeof(node)); q->data=e; q->prior=p; q->next=p->next; p->next->prior=q; p->next=q; return 1; } int listDelete_dul(linklist &l,int i,Elemtype &e){ linklist p=l,q;int j=0; if (i<1||i>listLength(l))return 0; while (p->next&&j<i-1){ p=p->next;j++; } e=p->next->data; q=p->next; p->next=q->next; p->next->prior=p; free(q); return 1; }

DuLNode * Locate_DuList(DuLinkedList &L,int x)//带freq域的双向循环链表上的查找 { p=L.next; while(p.data!=x&&p!=L) p=p->next; if(p==L) return NULL; //没找到 p->freq++;q=p->pre; while(q->freq<=p->freq) q=q->pre; //查找插入位置 if(q!=p->pre) { p->pre->next=p->next;p->next->pre=p->pre; q->next->pre=p;p->next=q->next; q->next=p;p->pre=q; //调整位置 } return p; }//Locate_DuList

思路：首先找到X所在位置，并让p指向它； 因为是非递增链表，p->freq++之后只能往左移动，所以通过prior指针来寻找插入位置。注意这里要判断一下if(q!=p->pre),这样就不用移动了。找到位置之后进行双向链表的插入算法。