C語言實現(xiàn)數(shù)據(jù)結(jié)構(gòu)之鏈表

本文實例為大家分享了C語言實現(xiàn)通用數(shù)據(jù)結(jié)構(gòu)之通用鏈表的具體代碼，供大家參考，具體內(nèi)容如下

忽然想起來，大概在兩年之前學(xué)習(xí)C語言的時候，曾經(jīng)用C語言寫過一些通用的數(shù)據(jù)結(jié)構(gòu)。主要也

就實現(xiàn)了鏈表、隊列、椎、HashSet,還有HashMap。當(dāng)時只是知道標(biāo)準(zhǔn)的C語言中沒有這方面的

類庫，后來才知道有很多第三方的類似這樣的類庫。廢話不多說，先把代碼粘過來。

下面實現(xiàn)的是通用鏈表，注意鏈表中只存儲了指針，沒有儲存實際的數(shù)據(jù)。

頭文件

***FilemyList.h

**************************I

#ifndefMYLIST_H_INCLUDED

#defineMYLIST_H_INCLUDED

#include<stdio.h>

typedefstructmyNode

{

void*data;

structmyNode*next;

}MyNode;

typedefstructmyList

{

MyNode*first;

MyNode*last;

intcount;

int(*equal)(void*a,void*b);

}MyList;

typedefstructmyListlterator

{

MyNode*p;

intcount;

intallSize;

}MyListlterator;

〃創(chuàng)建鏈表

MyList*createMyList();

〃創(chuàng)建鏈表，帶有相等參數(shù)，用于查找

MyList*createMySearchList(int(*equal)(void*a,void*b));

〃釋放鏈表

voidfreeMyList(MyList*list);

〃插入在尾部

voidmyListInsertDataAtLast(MyList*constlist,void*constdata);

〃插入在首部

voidmyListlnsertDataAtFirst(MyList*constlist,void*constdata);

〃插入

voidmyListlnsertDataAt(MyList*constlist,void*constdata,intindex);

〃刪除在尾部

void*myListRemoveDataAtLast(MyList*constlist);

〃刪除在首部

void*myListRemoveDataAtFirst(MyList*constlist);

〃刪除

void*myListRemoveDataAt(MyList*constlist,intindex);

〃刪除對象，返回是否刪除成功

intmyListRemoveDataObject(MyList*constlist,void*data);

〃長度

intmyListGetSize(constMyList*constlist);

〃打印

voidmyListOutput(constMyList*constlist,void(*pt)(constvoid*const));

〃取得數(shù)據(jù)

void*myListGetDataAt(constMyList*constlist,intindex);

〃取得第?個數(shù)據(jù)

void*myListGetDataAtFirst(constMyList*constlist);

〃取得最后一個數(shù)據(jù)

void*myListGetDataAtLast(constMyList*constlist);

〃查找某個數(shù)據(jù)的位置，如果equal方法為空，比較地址，否則調(diào)用equal方法

〃如果不存在返回-1，如果存在，返回出現(xiàn)的第一個位置

intmyListFindDataIndex(constMyList*constlist,void*data);

〃創(chuàng)建遍歷般

MyListlterator*createMyListIterator(constMyList*constlist);

〃釋放遍歷器

voidfreeMyListIterator(MyListlterator*iterator);

〃遍歷器是否有下?個元素

intmyListIteratorHasNext(constMyListlterator*constiterator);

〃返回遍歷器的下一個元素

void*myListIteratorNext(MyListIterator*constiterator);

#endif//MYLIST_H_INCLUDED

源文件

/*************************

***FilemyList.c

**************************I

#include"myList.h"

#include<stdlib.h>

〃創(chuàng)建鏈表

MyList*createMyList()

{

MyList*re=(MyList*)malloc(sizeof(MyList));

re->count=0;

re->first=NULL;

re->last=NULL;

re->equal=NULL;

returnre;

}

〃釋放鏈表

voidfreeMyList(MyList*list)

{

MyNode*p;

while(list->first)

(

p=list->first->next;

free(list->first);

list->first=p;

)

free(list);

)

〃插入在尾部

voidmyListInsertDataAtLast(MyList*constlist,void*constdata)

(

MyNode*node=(MyNode*)malloc(sizeof(MyNode));

node->data=data;

node->next=NULL;

if(list->count)

(

list->last->next=node;

list->last=node;

}

else

(

list->first=node;

list->last=node;

)

(list->count)++;

}

〃插入在首部

voidmyListlnsertDataAtFirst(MyList*constlist,void*constdata)

{

MyNode*node=(MyNode*)malloc(sizeof(MyNode));

node->data=data;

node->next=NULL;

if(list->count)

{

node->next=list->first;

list->first=node;

)

else

<

list->first=node;

list->last=node;

}

(list->count)++;

}

〃長度

intmyListGetSize(constMyList?constlist)

returnlist->count;

}

〃打印

voidmyListOutput(constMyList*constlist,void(*pt)(constvoid*const))

{

MyNode*p=list->first;

while(p)

{

(*pt)(p->data);

p=p->next;

}

)

〃刪除在尾部

void*myListRemoveDataAtLast(MyList*constlist)

(

if(list->count==1)

<

returnmyListRemoveDataAtFirst(list);

)

MyNode*p=list->first;

while(p->next!=list->last)

p=p->next;

}

void*re=list->last->data;

free(list->last);

p->next=NULL;

list->last=p;

(list->count)--;

returnre;

}

〃刪除在首部

void*myListRemoveDataAtFirst(MyList*constlist)

{

MyNode*p=list->first;

list->first=p->next;

void*re=p->data;

free(p);

(list->count)--;

if(list->count==0)

(

list->last=NULL;

}

returnre;

}

〃插入

voidmyListInsertDataAt(MyList*constlist,void*constdata,intindex)

{

if(index==0)

myListInsertDataAtFirst(list,data);

return;

)

if(index==list->count)

<

myListInsertDataAtLast(list,data);

return;

}

MyNode*node=(MyNode*)malloc(sizeof(MyNode));

node->data=data;

node->next=NULL;

MyNode*p=list->first;

for(inti=0;i<index-1;i++)

{

p=p->next;

)

node->next=p->next;

p->next=node;

(list->count)++;

}

〃刪除

void*myListRemoveDataAt(MyList*constlist,intindex)

{

if(index==0)

returnmyListRemoveDataAtFirst(list);

}

if(index==list->count-1)

(

returnmyListRemoveDataAtLast(list);

)

MyNode*p=list->first;

for(inti=0;i<index-1;i++)

(

p=p->next;

)

MyNode*tp=p->next;

p->next=p->next->next;

void?re=tp->data;

free(tp);

(list->count)--;

returnre;

)

〃取得數(shù)據(jù)

void*myListGetDataAt(constMyList*constlist,index)

{

if(index==list->count-1)

{

returnmyListGetDataAtLast(list);

}

MyNode*p=list->first;

for(inti=0;i<index;i++)

{

p=p->next;

)

returnp->data;

}

〃取得第一個數(shù)據(jù)

void*myListGetDataAtFirst(constMyList*constlist)

{

returnlist->first->data;

}

〃取得最后一個數(shù)據(jù)

void*myListGetDataAtLast(constMyList*constlist)

{

returnlist->last->data;

}

〃查找某個數(shù)據(jù)的位置，如果equal方法為空，比較地址，否則調(diào)用equal方法

〃如果不存在返回-1，如果存在，返回出現(xiàn)的第一個位置

intmyListFindDataIndex(constMyList*constlist,void*data)

{

MyNode*p=list->first;

intre=0;

if(list->equal)

{

while(p)

if(p->data==data||(*(list->equal))(p->data,data))

{

returnre;

}

re++;

p=p->next;

)

)

else

{

while(p)

(

if(p->data==data)

{

returnre;

}

re++;

p=p->next;

)

}

return-1;

}

〃創(chuàng)建鏈表，帶有相等參數(shù)，用于查找

MyList?createMySearchList(int(*equal)(void*a,void?b))

MyList*re=createMyList();

re->equal=equal;

returnre;

}

〃創(chuàng)建遍歷器

MyListlterator*createMyListIterator(constMyList*constlist)

{

MyListlterator*re=(MyListlterator*)malloc(sizeof(MyListlterator));

re->p=list->first;

re->allSize=list->count;

re->count=0;

returnre;

}

〃釋放遍歷器

voidfreeMyListIterator(MyListIterator*iterator)

{

free(iterator);

}

〃遍歷器是否有下一個元素

intmyListIteratorHasNext(constMyListlterator*constiterator)

{

returniterator->count<iterator->allSize;

}

〃返回遍歷器的下一個元素

void*myListIteratorNext(MyListIterator*constiterator)

{

void*re=iterator->p->data;

iterator->p=iterator->p->next;

(iterator->count)++;

returnre;

}

〃刪除對象，返回是否刪除成功

intmyListRemoveDataObject(MyList*constlist,void*data)

{

MyListlterator*it=createMyListlterator(list);

inta=0;

while(myListlteratorHasNext(it))

{

void*Id=myListlteratorNext(it);

if(data==Id||(list->equal!=NULL&&(*(list->equal))(Id,data)))

{

a=1;

break;

)

}

if(a)

(

myListRemoveDataAt(list,it->count-1);

)

returna;

測試文件

/*************************

***Filemain.c

***testforMyList

**************************/

#include<stdio.h>

ttinclude<stdlib.h>

#include"myList.h"

typedefstructa

{

inti;

charc;

)A；

voidppt(constvoid*constp)

{

A*pp=p；

printf("%d(%c)”，pp->i,

}

intmain()

constintS=10;

〃創(chuàng)建并初始化數(shù)據(jù)

A*d