上一篇文章<用C语言实现单链表的各种操作(一)>主要是单链表的一些最基本的操作，下面，主要是一些其他的典型的算法和测试程序。 复制代码 代码如下:/* 对单链表进行排序处理*/struct LNode *sort(struct LNode *head){ LinkList *p; int n,i,j; int temp; n = ListLength(head); if(head == NULL || head->next == NULL) return head; p = head->next; for(j =1;j<n;++j) { p = head->next; for( i =0;i<n-j;++i) { if(p->data > p->next->data) { temp = p->data; p->data = p->next->data; p->next->data = temp; } p = p->next; } } return head;}/*对单链表进行逆置*/LinkList *reverse(LinkList *head){ LinkList *p1,*p2 = NULL,*p3 = NULL; if(head == NULL || head->next == NULL) return head; p1 = head->next; while(p1!=NULL) { p3 = p1->next; p1->next = p2; p2 = p1; p1 = p3; } head->next = p2; // head = p2; return head; }Status equal(ElemType c1,ElemType c2){ if(c1== c2) return TRUE; else return FALSE;}/*将所有在线性表Lb中但不在La中的数据元素插入到La 中*/void Union(LinkList *La,LinkList *Lb){ ElemType *e; int La_len,Lb_len; int i; La_len = ListLength(La); Lb_len = ListLength(Lb); for(i=1;i<=Lb_len;i++) { GetElem(Lb,i,e); //取Lb中第i个元素赋给e if(!LocateElem(La,*e,equal))//La中不存在和e相同的元素，则插入 ListInsert(La,++La_len,*e); }}void print(ElemType c){ printf("%4d",c);}/* 合并两个单链表，La和Lb中的数据是按非递减排列，归并后的Lc还是安非递减排列*/void MergeList(LinkList *La,LinkList *Lb,LinkList **Lc){ int i =1,j=1,k=0; int La_len,Lb_len; ElemType *ai,*bj; ai = (ElemType *)malloc(sizeof(ElemType)); bj = (ElemType *)malloc(sizeof(ElemType)); InitList(Lc); La_len = ListLength(La); Lb_len = ListLength(Lb); while(i<=La_len && j<=Lb_len) { GetElem(La,i,ai); GetElem(Lb,j,bj); if(*ai<*bj) { ListInsert(*Lc,++k,*ai); ++i; } else { ListInsert(*Lc,++k,*bj); ++j; } } while(i<=La_len) { GetElem(La,i++,ai); ListInsert(*Lc,++k,*ai); } while(j<=Lb_len) { GetElem(Lb,j++,bj); ListInsert(*Lc,++k,*bj); }}/*只遍历一次，找到单链表中的中间节点 1 定义两个指针，一个指针每次移动两个步长（快指针），另一个指针每次移动一个数据（慢指针） 2. 当快指针到达链表尾部的时候，慢指针就到了链表的中间节点在程序中也可以判断一个单链表是否有环，如果快指针一定能够追赶上慢指针，否则就会以NULL结束*/LinkList *Searchmid(LinkList * head){ if(NULL == head) return NULL; if(head->next == NULL) return head; if(head->next->next == NULL) return head; LinkList *mid= head; LinkList *p = mid->next; while((p != NULL) && (NULL !=p->next)) { mid = mid->next; p = p->next->next; } return mid;}下面主要是单链表的一个测试的程序。复制代码 代码如下:Status comp(ElemType c1,ElemType c2){ if(c1==c2) return TRUE; else return FALSE;}void visit(ElemType c){ printf("%4d",c);}void main(){ LinkList *L; LinkList *mid; mid = (struct LNode *)malloc(sizeof(struct LNode)); ElemType *e,e0,*e1; Status i; int j,k; e = (ElemType *)malloc(sizeof(ElemType)); e1 = (ElemType *)malloc(sizeof(ElemType)); i = InitList(&L); for(j=1;j<=6;j++) { i = ListInsert(L,1,j); } printf("在L的表头依次插入1～6后：L="); ListTraverse(L,visit); printf("L中间节点的值为mid=："); mid = Searchmid(L); printf("%d\n",mid->data); printf("L逆置后的输出：L="); ListTraverse(reverse(L),visit); printf("L排序后依次为：L="); ListTraverse(sort(L),visit); i = ListEmpty(L); printf("L 是否为空：i=%d(1:是，0:否)\n",i); i = ClearList(L); printf("清空L后：L="); ListTraverse(L,visit); i = ListEmpty(L); printf("L是否为空：i=%d\n",i); for(j=1;j<=10;j++) { ListInsert(L,j,j); } printf("在L的表尾依次插入1~10后：L="); ListTraverse(L,visit); GetElem(L,5,e); printf("第5个元素的值为：%d\n",*e); for(j=0;j<=1;j++) { k = LocateElem(L,j,comp); if(k) printf("第%d个元素的值为%d\n",k,j); else printf("没有值为%d的元素\n",j); } for(j=1;j<=2;j++) { GetElem(L,j,e1); i = PriorElem(L,*e1,e); if(i== INFEASIBLE) printf("元素%d无前驱\n",*e1); else printf("元素%d的前驱为：%d\n",*e1,*e); } for(j=ListLength(L) -1;j<=ListLength(L);j++) { GetElem(L,j,e1); i = NextElem(L,*e1,e); if(i==INFEASIBLE) printf("元素%d无后继\n",*e1); else printf("元素%d的后继为：%d\n",*e1,*e); } k = ListLength(L); for(j=k+1;j>=k;j--) { i = ListDelete(L,j,e); if(i==ERROR) printf("删除第%d个数据失败\n",j); else printf("删除的元素为：%d\n",*e); } printf("依次输出L的元素："); ListTraverse(L,visit); DestroyList(L); printf("销毁L后：L=%u\n",L); printf("*************************************************\n"); LinkList *La,*Lb; i = InitList(&La); if(i==1) for(j=1;j<=5;j++) i= ListInsert(La,j,j); printf("La="); ListTraverse(La,print); InitList(&Lb); for(j=1;j<=5;j++) i = ListInsert(Lb,j,2*j); printf("Lb = "); ListTraverse(Lb,print); Union(La,Lb); printf("new La="); ListTraverse(La,print); printf("*************************************************\n"); LinkList *La_1,*Lb_1,*Lc_1; int a[4]={3,5,8,11},b[7]= {2,6,8,9,11,15,20}; InitList(&La_1); for(j=1;j<=4;j++) ListInsert(La_1,j,a[j-1]); printf("La_1="); ListTraverse(La_1,print); InitList(&Lb_1); for(j=1;j<=7;j++) ListInsert(Lb_1,j,b[j-1]); printf("Lb_1="); ListTraverse(Lb_1,print); MergeList(La_1,Lb_1,&Lc_1); printf("Lc_1="); ListTraverse(Lc_1,print);}下面是在Linux下的部分运行结果：复制代码 代码如下:在L的表头依次插入1～6后：L= 6 5 4 3 2 1L中间节点的值为mid=：4L逆置后的输出：L= 1 2 3 4 5 6L排序后依次为：L= 1 2 3 4 5 6L 是否为空：i=0(1:是，0:否)清空L后：L=L是否为空：i=1在L的表尾依次插入1~10后：L= 1 2 3 4 5 6 7 8 9 10第5个元素的值为：5没有值为0的元素第1个元素的值为1元素1无前驱元素2的前驱为：1元素9的后继为：10元素10无后继删除第11个数据失败删除的元素为：10依次输出L的元素： 1 2 3 4 5 6 7 8 9销毁L后：L=7954544*************************************************La= 1 2 3 4 5Lb = 2 4 6 8 10new La= 1 2 3 4 5 6 8 10*************************************************La_1= 3 5 8 11Lb_1= 2 6 8 9 11 15 20Lc_1= 2 3 5 6 8 8 9 11 11 15 20
加载中,请稍侯......
精彩评论