c語言鏈表的實現
A. 如何用C 實現鏈表的查找、插入和刪除
如何用C語言實現鏈表的查找、插入和刪除，用C語言實現鏈表的查找、插入和刪除的方法。
鏈表
C語言中鏈表有很多種，我們來講C語言中最主要的鏈表——單向鏈表和雙向鏈表的查找，插入，刪除的實現方法。
單向鏈表
單鏈表使用按值查找，從鏈表的首元結點出發，依次將結點值和給定值e進行比較，返回查找結果。
其中單鏈表的查找的演算法步驟是： 1.使用指針P指向首元結點 2.從首元結點開始依次順著鏈域next向下查找，只要指向當前結點的指針P不為空，並且P所指結點的數據域不等於給定的值e，則循環執行「p指向下一個結點操作。 3.返回P。若查找成功，p此時即為結點的地址值，若查找失敗，P返回NULL 具體代碼如下。
SingleLinkList.h typedef int status;typedef int ElemType; //鏈表節點及鏈表數據表示定義typedef struct SingleLinkNode{ElemType data;struct SingleLinkNode *next;}SingleLinkNode,*SingleLinkList;//以下是單向鏈表操作函數原型 //初始化操作status InitSingleLinkList(SingleLinkList l);//鏈表銷毀操作void DestroySingleLinkList(SingleLinkList l);//鏈表清除操作void ClearSingleLinkList(SingleLinkList l);//鏈表長度int SingleLinkListLength(SingleLinkList l); //鏈表是否為空bool SingleLinkListEmpty(SingleLinkList l); //取鏈表中的第i個元素status GetSingleLinkListElem(SingleLinkList l,int i,ElemType e); //在鏈表的第i個位置插入元素status InsertSingleLinkList(SingleLinkList l,int i,ElemType e);//刪除鏈表的第i個元素status DeleteSingleLinkList(SingleLinkList l,int i); //列印鏈表void PrintSingleLinkList(SingleLinkList l);
SingleLinkList //必須包含此文件，因為它包含此文件中要用到的數據表示定義//以下實現的是帶頭節點的單向鏈表#include"SingleLinkList.h"#include"stdlib.h"#include"iostream.h"//初始化操作status InitSingleLinkList(SingleLinkList l){ //if(l)free(l); if(l=(SingleLinkList)malloc(sizeof(SingleLinkNode)))//如果分配成功，設置節點{l-next=NULL;return 1;}elsereturn 0;//表示失敗 }//鏈表銷毀操作void DestroySingleLinkList(SingleLinkList l){SingleLinkList p=l,q;while(p){q=p-next ;free(p);p=q;} }//鏈表清除操作void ClearSingleLinkList(SingleLinkList l){SingleLinkList p=l-next ,q;while(p){q=p-next ;free(p);p=q;}l-next =NULL; }//鏈表長度int SingleLinkListLength(SingleLinkList l){SingleLinkList p=l-next ;int i=0;if(l==NULL)return 0;while(p)i++,p=p-next; return i; } //鏈表是否為空bool SingleLinkListEmpty(SingleLinkList l){ return (l-next==NULL); } //取鏈表中的第i個元素status GetSingleLinkListElem(SingleLinkList l,int i,ElemType e){ int k=0;SingleLinkList p=l-next;if(i1||iSingleLinkListLength(l)) return 0;//1,尋找第i個節點 while(pki)k++,p=p-next; e =p-data ;return 1; } //在鏈表的第i個位置插入元素status InsertSingleLinkList(SingleLinkList l,int i,ElemType e){int k=0;SingleLinkList p,q ;if(SingleLinkListLength(l)==0)InitSingleLinkList(l);p=l ;if(i1||iSingleLinkListLength(l)+1) return 0;//1,尋找第i－1個節點 while(p-next ki-1)k++,p=p-next; //2,構造節點if(!(q=(SingleLinkList)malloc(sizeof(SingleLinkNode))))return 0;//3,設置節點並將節點鏈入q-data =e;q-next =p-next ;p-next =q;return 1;}//刪除鏈表的第i個元素status DeleteSingleLinkList(SingleLinkList l,int i){ int k=0;SingleLinkList p=l-next;if(i1||iSingleLinkListLength(l)) return 0;//1,尋找第i－1個節點 while(pki-1)k++,p=p-next; p-next =p-next-next ;free(p-next );return 1; } //列印鏈表void PrintSingleLinkList(SingleLinkList l){SingleLinkList p=l-next ;int i=1;while(p){coutp-data" " ;if(i%5==0)coutendl;p=p-next,i++ ;} }
Test #include"SingleLinkList.h"#includeiostream.h#includestdlib.h void main(void){ }
雙鏈表
雙鏈表的定義和各種操作實現方法，代碼如下；
DualLinkList.h typedef int status;typedef int ElemType; //鏈表節點及鏈表數據表示定義typedef struct DualLinkListNode{ElemType data;struct DualLinkListNode *next;}DualLinkListNode,*DualLinkListList;//以下是單向鏈表操作函數原型 //初始化操作status InitDualLinkListList(DualLinkListList l);//鏈表銷毀操作void DestroyDualLinkListList(DualLinkListList l);//鏈表清除操作void ClearDualLinkListList(DualLinkListList l);//鏈表長度int DualLinkListListLength(DualLinkListList l); //鏈表是否為空bool DualLinkListListEmpty(DualLinkListList l); //取鏈表中的第i個元素status GetDualLinkListListElem(DualLinkListList l,int i,ElemType e); //在鏈表的第i個位置插入元素status InsertDualLinkListList(DualLinkListList l,int i,ElemType e);//刪除鏈表的第i個元素status DeleteDualLinkListList(DualLinkListList l,int i); //列印鏈表void PrintDualLinkListList(DualLinkListList l);
B. 用C語言編寫鏈式存儲結構下實現線性表的創建,插入,刪除,按值查找
#include <stdio.h>
#include <stdlib.h>
typedef struct LNode{
int data; //鏈表數據
struct LNode* next; //鏈表指針
}LNode,*LinkList;
/*頭插法-建立單鏈表*/
LinkList HeadCreate(LinkList la)
{
int num;
la=(LinkList)malloc(sizeof(LNode)); //建立頭結點
la->next=NULL;
scanf("%d",&num);
while(num!=10)
{
LNode *p=(LinkList)malloc(sizeof(LNode));
p->data=num;
p->next=la->next;
la->next=p;
scanf("%d",&num);
}
return la;
}
/*尾插法-建立單鏈表*/
LinkList TailCreate(LinkList la)
{
int num;
la=(LinkList)malloc(sizeof(LNode));
la->next=NULL;
LinkList s,r=la;
scanf("%d",&num);
while(num!=10)
{
s=(LinkList)malloc(sizeof(LNode));
s->data=num;
r->next=s;
r=s;
scanf("%d",num);
}
r->next=NULL;
return la;
}
/*單鏈表遍歷*/
void TravelList(LinkList la)
{
LinkList p=la->next;
while(p!=NULL)
{
printf("%d->",p->data);
p=p->next;
}
printf("\n");
}
/*單鏈表的按位查找*/
LinkList GetElem(LinkList la,int i)
{
int j=1;
LNode* p=la->next;
if(i<1)
return NULL;
while(p && j<i)
{
p=p->next;
j++;
}
return p;
}
/*單鏈表的按值查找*/
LinkList LocalElem(LinkList la,int e)
{
LNode* p=la->next;
while(p!=NULL && p->data!=e)
p=p->next;
return p;
}
/*單鏈表插入操作*/
bool InsertList(LinkList la,int i,int e)
{
//在la鏈表中的i位置插入數值e
int j=1;
LinkList p=la,s;
while(p && j<i)
{
p=p->next;
j++;
}
if(p==NULL)
return false;
if((s=(LinkList)malloc(sizeof(LNode)))==NULL)
return false;
s->data=e;
s->next=p->next;
p->next=s;
return true;
}
/*單鏈表刪除操作*/
bool DeleteList(LinkList la,int i)
{
int j=1;
LinkList p=la,q;
while(p && j<i) //p指向第i-1個元素
{
p=p->next;
j++;
}
if(p==NULL || p->next==NULL) //表示不存在第i-1個和第i的元素
return false;
q=p->next;
p->next=q->next;
free(q);
return true;
}
/*單鏈表的表長*/
int LengthList(LinkList la)
{
int nLen=0;
LinkList p=la->next;
while(p)
{
p=p->next;
nLen++;
}
return nLen;
}
/*單鏈表逆置*/
LinkList Reserve(LinkList la)
{
if(la==NULL || la->next==NULL)
return la;
LinkList p=la->next,q=p->next,r=q->next;
la->next=NULL;
p->next=NULL;
while(r!=NULL)
{
q->next=p;
p=q;
q=r;
r=r->next;
}
q->next=p;
la->next=q;
return la;
}
int main()
{
LNode la;
LinkList p;
p=HeadCreate(&la); //頭插法創建單鏈表
TravelList(p);
printf("%p\n",GetElem(p,1)); //獲得第1個結點地址
InsertList(p,2,10); //在鏈表的第2個位置插入元素10
TravelList(p);
DeleteList(p,3); //刪除鏈表的第3個元素
TravelList(p);
printf("%d\n",LengthList(p)); //獲得鏈表長度
p=Reserve(p);
TravelList(p);
return 0;
}
//運行結果
//5 6 12 7 8 14 9 3 2 5 14 10 頭插法創建鏈表
//14->5->2->3->9->14->8->7->12->6->5-> 顯示鏈表
//00382490 第一個結點的地址
//14->10->5->2->3->9->14->8->7->12->6->5-> 插入元素值為10的結點
//14->10->2->3->9->14->8->7->12->6->5-> 刪除第三個結點
//11 獲得鏈表長度
//5->6->12->7->8->14->9->3->2->10->14-> 鏈表逆置
//Press any key to continue
這是我寫的一個線性表鏈式存儲的綜合程序，包含了你所要的創建、刪除、插入、按值查找的功能，還有一些額外的功能。下面加註釋的是程序運行結果，你可以參考試著改改程序，讓程序更加完美。希望對你有幫助，呵呵！
C. 用C語言實現： （1）用頭插法（或尾插法）建立帶頭結點的單鏈表；
C語言實現鏈表操作，具體包括鏈表的建立和數據的插入、刪除。首先，定義了一個結構體，用於描述鏈表節點，每個節點包含整型數據和指向下一個節點的指針。
程序中使用了一個帶頭結點的單鏈表，通過頭插法實現數據的插入。主函數中循環接受用戶輸入，選擇插入或刪除操作。插入操作時，用戶需先輸入要插入的數據個數，再逐一輸入數據。程序會為每個輸入的數據創建一個新的鏈表節點，並將其插入到鏈表頭部。插入完成後，輸出鏈表當前的數據內容。
刪除操作時，用戶輸入要刪除的值，程序遍歷鏈表，找到匹配節點後，將其從鏈表中移除。刪除操作完成後，輸出鏈表當前的數據內容。如果鏈表中不存在該值，程序會提示用戶。
通過這樣的實現，可以動態地添加或移除鏈表中的元素，滿足了基本的數據操作需求。頭插法使得新插入的元素總是位於鏈表的最前端，方便管理和操作。
需要注意的是，每次操作後都需要更新鏈表的結構，確保鏈表的正確性。在實際應用中，可以根據需求選擇不同的插入或刪除方法，如尾插法，以適應不同的應用場景。
此外，程序中的錯誤處理也較為完善，當用戶輸入非法選項時，程序會提示錯誤並要求重新選擇。這種機制有助於提高程序的健壯性和用戶體驗。
通過上述實現，可以靈活地對鏈表進行管理和操作，適用於多種場景，包括但不限於數據存儲、搜索和排序等。