用C語言實(shí)現(xiàn)單鏈表的各種操作(二)
更新時間：2013年05月24日 17:39:16 作者：
本篇文章是對用C語言實(shí)現(xiàn)單鏈表的各種操作進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下
上一篇文章<用C語言實(shí)現(xiàn)單鏈表的各種操作(一)>主要是單鏈表的一些最基本的操作，下面，主要是一些其他的典型的算法和測試程序。
/* 對單鏈表進(jìn)行排序處理*/
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;
}
/*對單鏈表進(jìn)行逆置*/
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中的數(shù)據(jù)元素插入到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中的數(shù)據(jù)是按非遞減排列，歸并后的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);
}
}
/*只遍歷一次，找到單鏈表中的中間節(jié)點(diǎn)
1 定義兩個指針，一個指針每次移動兩個步長（快指針），另一個指針每次移動一個數(shù)據(jù)（慢指針）
2. 當(dāng)快指針到達(dá)鏈表尾部的時候，慢指針就到了鏈表的中間節(jié)點(diǎn)
在程序中也可以判斷一個單鏈表是否有環(huán)，如果快指針一定能夠追趕上慢指針，否則就會以NULL結(jié)束*/
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中間節(jié)點(diǎn)的值為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無前驅(qū)\n",*e1);
else
printf("元素%d的前驅(qū)為：%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個數(shù)據(jù)失敗\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下的部分運(yùn)行結(jié)果：
在L的表頭依次插入1～6后：L= 6 5 4 3 2 1
L中間節(jié)點(diǎn)的值為mid=：4
L逆置后的輸出：L= 1 2 3 4 5 6
L排序后依次為：L= 1 2 3 4 5 6
L 是否為空：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無前驅(qū)
元素2的前驅(qū)為：1
元素9的后繼為：10
元素10無后繼
刪除第11個數(shù)據(jù)失敗
刪除的元素為：10
依次輸出L的元素： 1 2 3 4 5 6 7 8 9
銷毀L后：L=7954544
*************************************************
La= 1 2 3 4 5
Lb = 2 4 6 8 10
new La= 1 2 3 4 5 6 8 10
*************************************************
La_1= 3 5 8 11
Lb_1= 2 6 8 9 11 15 20
Lc_1= 2 3 5 6 8 8 9 11 11 15 20
復(fù)制代碼 代碼如下:
/* 對單鏈表進(jìn)行排序處理*/
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;
}
/*對單鏈表進(jìn)行逆置*/
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中的數(shù)據(jù)元素插入到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中的數(shù)據(jù)是按非遞減排列，歸并后的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);
}
}
/*只遍歷一次，找到單鏈表中的中間節(jié)點(diǎn)
1 定義兩個指針，一個指針每次移動兩個步長（快指針），另一個指針每次移動一個數(shù)據(jù)（慢指針）
2. 當(dāng)快指針到達(dá)鏈表尾部的時候，慢指針就到了鏈表的中間節(jié)點(diǎn)
在程序中也可以判斷一個單鏈表是否有環(huán)，如果快指針一定能夠追趕上慢指針，否則就會以NULL結(jié)束*/
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;
}
下面主要是單鏈表的一個測試的程序。
復(fù)制代碼 代碼如下:
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中間節(jié)點(diǎn)的值為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無前驅(qū)\n",*e1);
else
printf("元素%d的前驅(qū)為：%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個數(shù)據(jù)失敗\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下的部分運(yùn)行結(jié)果：
復(fù)制代碼 代碼如下:
在L的表頭依次插入1～6后：L= 6 5 4 3 2 1
L中間節(jié)點(diǎn)的值為mid=：4
L逆置后的輸出：L= 1 2 3 4 5 6
L排序后依次為：L= 1 2 3 4 5 6
L 是否為空：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無前驅(qū)
元素2的前驅(qū)為：1
元素9的后繼為：10
元素10無后繼
刪除第11個數(shù)據(jù)失敗
刪除的元素為：10
依次輸出L的元素： 1 2 3 4 5 6 7 8 9
銷毀L后：L=7954544
*************************************************
La= 1 2 3 4 5
Lb = 2 4 6 8 10
new La= 1 2 3 4 5 6 8 10
*************************************************
La_1= 3 5 8 11
Lb_1= 2 6 8 9 11 15 20
Lc_1= 2 3 5 6 8 8 9 11 11 15 20
相關(guān)文章
這篇文章主要介紹了VS2019 Nuget找不到包的問題處理，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-03-03
大家好，本篇文章主要講的是C語言循環(huán)控制入門介紹，感興趣的同學(xué)趕快來看一看吧，對你有幫助的話記得收藏一下，方便下次瀏覽2022-01-01
64位linux 編譯c提示gnu/stubs-32.h:No such file or directory的解決方法
這篇文章主要介紹了64位linux 編譯c提示gnu/stubs-32.h:No such file or directory的解決方法,需要的朋友可以參考下2020-03-03
這篇文章主要介紹了C++遞歸線性陣列搜索數(shù)字的方法,涉及C++遞歸及數(shù)組操作的相關(guān)技巧,需要的朋友可以參考下2015-06-06
C語言字符串函數(shù)操作(strlen,strcpy,strcat,strcmp)詳解
大家好，本篇文章主要講的是C語言字符串函數(shù)操作（strlen,strcpy,strcat,strcmp）詳解，感興趣的同學(xué)趕快來看一看吧2021-12-12
這篇文章主要介紹了c語言實(shí)現(xiàn)多線程動畫程序示例，該程序是利用opengl圖形庫與fmod音頻庫寫的一個簡單3d動畫程序,需要的朋友可以參考下2014-04-04
Java?C++?算法題解leetcode652尋找重復(fù)子樹
這篇文章主要為大家介紹了Java?C++?算法題解leetcode652尋找重復(fù)子樹示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-09-09
C語言鏈表案例學(xué)習(xí)之通訊錄的實(shí)現(xiàn)
為了將所學(xué)到的鏈表的知識進(jìn)行鞏固學(xué)習(xí)，做到學(xué)以致用，本文將利用鏈表制作一個簡單的通訊錄。文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以了解一下2022-10-10
C++類和對象實(shí)戰(zhàn)之Date類的實(shí)現(xiàn)方法
C++ 標(biāo)準(zhǔn)庫沒有提供所謂的日期類型,C++ 繼承了C語言用于日期和時間操作的結(jié)構(gòu)和函數(shù),這篇文章主要給大家介紹了C++類和對象實(shí)戰(zhàn)之Date類的實(shí)現(xiàn)方法,需要的朋友可以參考下2021-12-12
nlohmann/json 是一個C++實(shí)現(xiàn)的JSON解析器,使用非常方便直觀,下面這篇文章主要給大家介紹了關(guān)于c++中nlohmann?json基本使用的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-09-09