Note
- 使用的工具是CodeBlocks 16.01
- 啟用了C99標(biāo)準(zhǔn)
單向鏈表是這樣是個序列:對于單向鏈表中的某一個元素ai,ai.data保存了ai的值抠蚣,ai.pointer保存了ai+1的地址茉帅,最后一個Node的pointer為NULL蝉稳。
如果我們得到了第一Node的地址或第一個Node變量匈挖,我們就可以訪問到所有的Node稠氮。
Node結(jié)構(gòu)體的聲明如下:
// node.c
typedef struct node{
int data;
struct node* pointer;
}Node;
有了Node的模型,我們怎樣創(chuàng)建一個單向鏈表呢茉盏?我們可以創(chuàng)建一個個的Node鉴未,然后把它們連接起來,如下所示:
// node.c
typedef struct node{
int data;
struct node* pointer;
}Node;
int main(void)
{
Node n1,n2,n3,n4,n5,n6,n7; // 創(chuàng)建n1~n7共7個Node
//把n1~n7連接起來
n1.pointer = &n2;
n2.pointer = &n3;
n3.pointer = &n4;
n4.pointer = &n5;
n5.pointer = &n6;
n6.pointer = &n7;
n7.pointer = NULL; //n7是最后一個Node鸠姨,其pointer為NULL
//在n1~n7中存儲數(shù)據(jù)
n1.data = 1;
n2.data = 2;
n3.data = 3;
n4.data = 4;
n5.data = 5;
n6.data = 6;
n7.data = 7;
return 0;
}
使用上面的代碼歼狼,我們創(chuàng)建了一個具有7個元素的單向鏈表,其結(jié)構(gòu)圖如下:
使用上面的方法享怀,我們完全可以創(chuàng)建一個可以保存很多元素的單向鏈表,只要我們聲明一個Node趟咆,并且把它添加到鏈表中即可添瓷。例如梅屉,如果我們還有添加一個元素n8,我們可以這樣做:
Node n8;
n8.data = 8;
n8.pointer = NULL;
n7.pointer = &n8;
使用這種方式鳞贷,我們可以很方便第知道自己的單向鏈表有多少個元素坯汤;可以很方便第訪問其中的任一個元素;可以很方便的添加搀愧、刪除元素惰聂。但是使用這種方法也有缺點:
- 每次都要創(chuàng)建一個節(jié)點,然后為其賦值咱筛,并將其添加到單向鏈表的末尾搓幌。
- 如果需要添加的元素成百上千,我們就需要創(chuàng)建成百上千的Node變量迅箩,很麻煩溉愁。
因此,如果可以有一個函數(shù)饲趋,我們提供給他第一個Node或者最后一個Node的地址和需要添加的元素的值拐揭,它就可以幫我們創(chuàng)建一個節(jié)點,并為節(jié)點賦值奕塑,將節(jié)點添加到單向鏈表的末尾堂污,豈不是一個好事?龄砰!因此盟猖,我打算寫一個函數(shù)append(Node * pNode,int data)
,它接收第一個Node的地址(通過第一個Node寝贡,我們可以找到所有的Node)和需要添加的元素值data扒披。
bool append(Node*pNode,int data)
{
Node * pEnd = pNode; // 保存最后一個元素的地址
while(pEnd->pointer!=NULL){
pEnd = pEnd->pointer; // 讓pEnd保存下一個Node的地址,直到pEnd保存了最后一個Node的地址
}
// 創(chuàng)建一個新的Node
Node *pNew = (Node *)malloc(sizeof(Node));
if(pNew==NULL){
printf("內(nèi)存分配失敗!\n");
exit(-1);
}
// 保存元素圃泡;將新創(chuàng)建的Node變?yōu)樽詈笠粋€Node碟案;將新創(chuàng)建的Node和其他的Node連接起來
pNew->data = data;
pNew->pointer = NULL;
pEnd->pointer = pNew;
return true;
}
我們寫了上面的append(Node * pNode,int data)
函數(shù)后,我們就可以像這樣往單向鏈表中添加元素了颇蜡。
//node.c
#include<stdio.h>
#include<stdbool.h>
#include<malloc.h>
typedef struct node{
int data;
struct node * pointer;
}Node;
bool append(Node*pNode,int data)
{
Node * pEnd = pNode; // 保存最后一個元素的地址
while(pEnd->pointer!=NULL){
pEnd = pEnd->pointer; // 讓pEnd保存下一個Node的地址价说,直到pEnd保存了最后一個Node的地址
}
// 創(chuàng)建一個新的Node
Node *pNew = (Node *)malloc(sizeof(Node));
if(pNew==NULL){
printf("內(nèi)存分配失敗!\n");
exit(-1);
}
// 保存元素;將新創(chuàng)建的Node變?yōu)樽詈笠粋€Node风秤;將新創(chuàng)建的Node和其他的Node連接起來
pNew->data = data;
pNew->pointer = NULL;
pEnd->pointer = pNew;
return true;
}
int main(void)
{
// 先創(chuàng)建第一個Node鳖目,因為append(Node*pNode,int data)需要第一個Node的地址。
Node n1;
n1.data = 1;
n1.pointer = NULL;
append(&n1,2);
append(&n1,3);
append(&n1,4);
append(&n1,5);
append(&n1,6);
append(&n1,7);
append(&n1,8);
//輸出
Node *pEnd = &n1;
while(pEnd->pointer!=NULL){ // 如果pEnd保存的不是最后一個元素的地址
printf("%d ",pEnd->data);
pEnd = pEnd->pointer;
}
// 循環(huán)結(jié)束后缤弦,pEnd保存的是最后一個元素的地址
printf("%d \n",pEnd->data);//輸出最后一個元素的值
return 0;
}
到現(xiàn)在為止领迈,似乎沒有什么問題。現(xiàn)在我想寫一個函數(shù),求單向鏈表的長度狸捅。我們知道通過第一個節(jié)點的地址衷蜓,我們可以找到所有節(jié)點,因此函數(shù)需要第一個Node的地址作為參數(shù):
int len(Node*pNode){
int len = 1; //這里設(shè)置了初始值為1尘喝,因為我們傳遞過來的第一個節(jié)點是有值的
Node*pEnd = pNode;
while(pEnd->pointer!=NULL){
len++;
pEnd = pEnd->pointer;
}
return len;
}
發(fā)現(xiàn)沒有磁浇,似乎我們的單向鏈表的長度永遠(yuǎn)不可能為0啊朽褪!我們也無法清空我的單向鏈表置吓,因為其長度最少都是1。怎么辦呢缔赠?這就需要在第一個節(jié)點的前面引入另一個節(jié)點衍锚,這個節(jié)點的data中不保存數(shù)據(jù),pointer則指向我們存儲數(shù)據(jù)的第一個節(jié)點橡淑。這樣可以方便我們創(chuàng)建空的單向鏈表构拳,清空鏈表,在第一個存儲數(shù)據(jù)的節(jié)點前插入節(jié)點梁棠。
- 我們在第一個存儲數(shù)據(jù)的Node前插入的節(jié)點又叫頭節(jié)點
- 存儲頭結(jié)點地址的變量叫頭指針
- 第一個存儲數(shù)據(jù)的節(jié)點叫首節(jié)點
<big><b>Note</b></big>:頭節(jié)點的data中并沒有存儲數(shù)據(jù)置森;頭節(jié)點的pointer存儲了首節(jié)點的地址;如果頭節(jié)點的pointer為NULL符糊,則說明單向鏈表為空凫海。
知道這些東西后,我們就可以編寫操作單向鏈表的函數(shù)了男娄。如下:linked_list.h
中定義了單向鏈表的結(jié)構(gòu)體和可以對其進(jìn)行操作的函數(shù)行贪。
linked_list.h
#include<stdbool.h>
typedef struct node{
struct node * pNext; // 指針域:指向下一個元素的指針
int element; // 數(shù)據(jù)域:保存元素值
}Node,LinkedList; // 給struct node數(shù)據(jù)類型起了兩個別名Node,LinkedList
// LinkedList別名傾向于表示整個的單向鏈表
// Node別名傾向于表示單向鏈表中的節(jié)點
void linkedListInit(Node * pNode); // 初始化單向鏈表
void linkedListShow(const LinkedList * const pList);//顯示單向鏈表中的所有元素
bool linkedListEmpty(const LinkedList * const pList);//判斷單向鏈表是否為空
bool linkedListAppend(LinkedList*pList,int e);//在單向鏈表的末尾追加元素
bool linkedListInsert(LinkedList*pList,int i,int e);//在單向鏈表的第i處插入元素
int linkedListLen(const LinkedList*const pList);//計算單向鏈表中有多少個元素
bool linkedListRemove(LinkedList*pLisy,int i,int*e);//移除單向鏈表中指定位置的元素
bool linkedListPop(LinkedList*pList,int*e);//彈出單向鏈表中最后一個元素
void linkedListSort(LinkedList*pList);//排序
bool linkedListContain(const LinkedList*const pList,int e);//判斷單向鏈表中是否包含某個元素
bool linkedListGet(const LinkedList*const pList,int i,int *e);//得到單向鏈表中某一個位置的元素
int linkedListIndex(const LinkedList*const pList,int e);//得到元素e在單向鏈表中的索引
void linkedListClear(LinkedList*pList);//清空單向鏈表
linkedList.c
是以上定義的函數(shù)的實現(xiàn)代碼模闲。
linkedList.c
#include<stdio.h>
#include"linked_list.h"
#include<malloc.h>
/** \brief 初始化LinkedList對象
*
* \param pNode Node* 指向LinkedList對象的指針
* \return void
*
*/
void linkedListInit(LinkedList * pList)
{
pList->pNext=NULL; //讓頭結(jié)點的pointer為空建瘫,以創(chuàng)建一個空的單向鏈表;注意并沒有為頭結(jié)點的data賦值尸折。
return;
}
/** \brief 打印LinkedList對象的每一個元素
*
* \param pList const LinkedList*const LinkedList對象
* \return void
*
*/
void linkedListShow(const LinkedList*const pList)
{
if(linkedListEmpty(pList)) // 如果單向鏈表為空
{
printf("LinkedList is empty!");
return;
}
LinkedList* pTemp = pList->pNext;
while(pTemp!=NULL)
{
printf("%d ",pTemp->element);
pTemp = pTemp->pNext;
}
printf("\n");
return;
}
/** \brief 判斷LinkedList是否為空
*
* \param const LinkedList * const pList 判斷是否為空的LinkedList對象
* \return bool 如果為空則返回true啰脚,否則返回false
*
*/
bool linkedListEmpty(const LinkedList * const pList)
{
return pList->pNext==NULL;
}
/** \brief 向LinkedList末尾添加元素
*
* \param LinkedList*pList LinkedList對象
* \param e int 添加的元素
* \return bool 添加成功則返回true,否則返回false
*
*/
bool linkedListAppend(LinkedList*pList,int e)
{
Node* pNode = pList;
while(pNode->pNext!=NULL)
{
pNode=pNode->pNext;
}
Node* pNew = (Node*)malloc(sizeof(Node));
if(pNew==NULL)
{
printf("分配內(nèi)存失敗!\n");
exit(-1);
}
pNew->element=e;
pNew->pNext=NULL;
pNode->pNext=pNew;
return true;
}
/** \brief 在LinkedList的某一個位置i處插入元素e
*
* \param LinkedList*pList 指向LinkedList對象的指針
* \param i int 插入元素的位置实夹,從0開始
* \param e int 被插入的元素e
* \return bool 如果插入的位置不屬于[0,len-1]橄浓,則插入失敗
*
*/
bool linkedListInsert(LinkedList*pList,int i,int e)
{
int len = linkedListLen(pList);
if(i>=0 && i<len){
Node* pNode = pList;
for(int index = 0; index < len;index++){
if(index==i){
Node*pNew = (Node*)malloc(sizeof(Node));
if(pNew==NULL){
printf("分配內(nèi)存失敗!\n");
exit(-1);
}
pNew->element=e;
pNew->pNext=pNode->pNext;
pNode->pNext=pNew;
return true;
}
pNode=pNode->pNext;
}
}
return false;
}
/** \brief 獲取LinkedList的長度
*
* \param pList const LinkedList*const 指向LinkedList對象的指針
* \return int 長度
*
*/
int linkedListLen(const LinkedList*const pList)
{
int len = 0;
Node* pNode = pList->pNext;
while(pNode!=NULL)
{
pNode=pNode->pNext;
len++;
}
return len;
}
/** \brief 從LinkedList中移除指定位置的元素
*
* \param LinkedList*pLisy 指向LinkedList對象的指針
* \param i int 指定的位置,從0開始
* \param int *e 保存被移除的元素
* \return bool 如果LinkedList為空或者指定的位置不存在亮航,則返回false荸实。
*
*/
bool linkedListRemove(LinkedList*pList,int i,int *e)
{
if(linkedListEmpty(pList)){
return false;
}
if(i<0){
return false;
}
int len = linkedListLen(pList);
if(i>=len){
return false;
}
Node * pNode = pList;
for(int index = 0; index < len; index++){
if(index==i){
Node*pTemp = pNode->pNext;
*e = pTemp->element;
pNode->pNext=pTemp->pNext;
pTemp->pNext=NULL;
free(pTemp);
return true;
}
pNode=pNode->pNext;
}
}
/** \brief 從LinkedList中彈出最后一個元素
*
* \param LinkedList*pList 指向LinkedList對象的指針
* \param int *e 保存被彈出的元素
* \return bool 如果LinkedList為空,則返回false
*
*/
bool linkedListPop(LinkedList*pList,int *e)
{
if(linkedListEmpty(pList)){
return false;
}
int len = linkedListLen(pList);
Node* pNode = pList->pNext;
for(int index = 0; index < len-2; index++){
pNode=pNode->pNext;
}
Node* pTemp = pNode->pNext;
*e = pTemp->element;
free(pTemp);
pNode->pNext=NULL;
return true;
}
/** \brief 對LinkedList進(jìn)行排序
*
* \param LinkedList*pList 指向LinkedList對象的指針
* \return void
*
*/
void linkedListSort(LinkedList*pList)
{
if(linkedListEmpty(pList))
{
printf("List is empty!\n");
return;
}
Node* p1 = pList->pNext;
Node* p2;
if(p1->pNext!=NULL)
{
p2=p1->pNext;
}
while(p1!=NULL)
{
while(p2!=NULL)
{
if(p1->element>p2->element)
{
p1->element=p1->element^p2->element;
p2->element=p1->element^p2->element;
p1->element=p1->element^p2->element;
}
p2=p2->pNext;
}
if(p1->pNext==NULL){
return;
}else{
p1 = p1->pNext;
}
if(p1->pNext==NULL){
return;
}else{
p2=p1->pNext;
}
}
return;
}
*/
/** \brief 判斷LinkedList中是否包含元素e
*
* \param pList const LinkedList*const 指向LinkedList對象的指針
* \param e int e元素
* \return bool 如果包含缴淋,則返回true准给,否則返回false
*
*/
bool linkedListContain(const LinkedList*const pList,int e)
{
if(linkedListEmpty(pList))
{
return false;
}
Node*pNode = pList->pNext;
while(pNode!=NULL)
{
if(pNode->element==e)
{
return true;
}
pNode=pNode->pNext;
}
return false;
}
/** \brief 獲取指定索引處的元素
*
* \param pList const LinkedList*const 指向LinkedList對象的指針
* \param i int 索引
* \return bool 如果獲取該元素在LinkedList中泄朴,則獲取成功,否則獲取失敗
*
*/
bool linkedListGet(const LinkedList*const pList,int i,int *e)
{
if(linkedListEmpty(pList))
{
printf("LinkedList是空的!\n");
return false;
}
int index=0;
Node* pNode = pList->pNext;
while(pNode!=NULL)
{
if(index==i)
{
*e=pNode->element;
return true;
}
pNode=pNode->pNext;
index++;
}
return false;
}
/** \brief 在LinkedList中查找某一個元素e索引圆存,索引從0開始
*
* \param pList const LinkedList*const 指向LinkedList對象的指針
* \param e int 查找的元素e
* \return int 找到則返回e在LinkedList中的索引叼旋,否則返回-1
*
*/
int linkedListIndex(const LinkedList*const pList,int e)
{
if(linkedListEmpty(pList))
{
return -1;
}
int index = 0;
Node* pNode = pList->pNext;
while(pNode!=NULL)
{
if(pNode->element==e)
{
return index;
}
pNode=pNode->pNext;
index++;
}
return -1;
}
/** \brief 清空LinkedList
*
* \param LinkedList*pList 需要清空的LinkedList對象
* \return void
*
*/
void linkedListClear(LinkedList*pList)
{
if(linkedListEmpty(pList))
{
return;
}
Node* pNode = pList->pNext;
pList->pNext=NULL;
Node* pTemp;
while(pNode->pNext!=NULL)
{
pTemp=pNode->pNext;
free(pNode);
pNode=pTemp;
}
free(pNode);
return;
}
測試代碼
linkedListTest.c
#include"linked_list.h"
#include<stdio.h>
int main(void)
{
LinkedList myList,*pMyList;
pMyList = &myList;
linkedListInit(pMyList);
linkedListAppend(pMyList,89);
linkedListAppend(pMyList,90);
linkedListAppend(pMyList,78);
linkedListAppend(pMyList,82);
linkedListAppend(pMyList,87);
linkedListAppend(pMyList,60);
linkedListShow(pMyList);
printf("%d在LinkedList中的索引是:%d\n",90,linkedListIndex(pMyList,90));
//linkedListClear(pMyList);
linkedListShow(pMyList);
int e;
linkedListGet(pMyList,5,&e);
printf("第%d個位置的元素是:%d\n",5,e);
if(linkedListContain(pMyList,60)){
printf("True\n");
}else{
printf("false\n");
}
printf("linkedList的長度是:%d\n",linkedListLen(pMyList));
printf("------排序-----\n");
linkedListSort(pMyList);
//linkedListReverse(pMyList);
linkedListShow(pMyList);
printf("------刪除-----\n");
linkedListRemove(pMyList,5,&e);
printf("%d\n",e);
linkedListShow(pMyList);
linkedListInsert(pMyList,0,12);
linkedListInsert(pMyList,1,40);
linkedListInsert(pMyList,5,88);
linkedListInsert(pMyList,3,72);
linkedListShow(pMyList);
linkedListPop(pMyList,&e);
linkedListShow(pMyList);
return 0;
}