首页 > 代码库 > 算法2---链表2---链表任意存储的实现
算法2---链表2---链表任意存储的实现
现在我们要在链表中存储任意类型的数据(也就是说数据所占字节数是在使用链表的时候确定)，既然要能存储任意类型的数据，那么我们的链表的节点和链表的定义就要做一些修改了。
下图是节点和链表的定义，data是一个ElemType类型的数据，而ElemType是被我们定义成了一个void *，也就是一个空指针。head和tail都是一个ChainNode类型的指针，作为链表的头结点和尾巴节点，头结点本书的数据域是不存放数据的。Nodesize表示要存储的数据类型的字节大小。
代码实现如下
#ifndef _List_Htypedef void * Elemtypetypedef struct node{ Elemtype data; struct node *next;}ChainNode;typedef struct{ ChainNode *head; int Nodesize; ChainNode *tail;}List;List *CreateList(int); //创建链表，传递的参数是链表的大小，返回值为指向链表的指针；void DestoryList(List *);//销毁链表；void ClearList(List *);//清空链表；int ListAppend(List*,...);//追加元素；int ListInsert(List*,int,...);//插入元素；int ListDelete(List*,int);//删除第几个元素；int GetElem(List*,int,Elemtype *);//取得第几个元素的值用第三个参数返回。ChainNode *GetAddr(List *,int);//取得编号为N的元素所在地址；int TraverseList(List *,int(*)(Elemtype));//遍历访问，访问某个节点元素用函数处理；ChainNode * NewChainNode (Elemtype);//得到新链表节点；int IsEmpty(List*);//链表判空；#endif/*===========================*/List *CreateList(int size){ List *pt = 0; Elemtype data = 0; pt=(List*)malloc(sizeof(List));//分配空间 if (!pt)//空间分配失败 { return 0; } pt->head=NewChainNode(data);//指向节点 if (!pt->head)//失败，释放空间 { free(pt); return 0; } pt->Nodesize=size; pt->tail=pt->head; return pt;}/*============================*/void DestoryList(List *plist){ ClearList(plist); free(plist->head); plist->head=0; free(plist); plist=0;}/*============================*/int ListAppend(List *plist,...){ ChainNode *newpt=0; void *data; void *pos; pos=&plist+1; if (!(plist&&plist->head)) { return 0; } data=(void*)malloc(plist->Nodesize); if (!data) { return 0; } memcpy(data,pos,plist->Nodesize); newpt = NewChainNode(data); if (!newpt) { return 0; } plist->tail->next = newpt; plist->tail = newpt; return 1;}/*============================*/int ListInsert(List *plist,int n,...){ ChainNode *pt=0; ChainNode *newpt=0; void *data; void *pos=&plist+2; pt = GetAddr(plist,n-1);//得到指定n位置的前一个地址； if (!(pt))//如果没有得到地址，返回0； { return 0; } data=(void*)malloc(plist->Nodesize);//给数据分配空间； if (!data) { return 0; } memcpy(data,pos,plist->Nodesize); newpt=NewChainNode(data); if (!newpt) { return 0; } if (pt->next==plist->tail) { plist->tail=newpt; } newpt->next=pt->next; pt->newpt; return 1;}/*============================*/int GetElem(List *plist,int n,Elemtype *data){ ChainNode *pt=0; if (!data) { return 0; } pt =GetAddr(plist,n)； if (!pt) { return 0; } memcpy(data,pt->data,plist->Nodesize); return 1;}/*============================*/int TraverseList(List *plist,int(*f)(Elemtype) ){ ChainNode *pt=0; int a =0; if (!(plist&&plist->head)) { return 0; } for (a = 0,pt=plist->head->next;pt;pt=pt->next) { if (!f((pt->data))) { return a+1; } a++; } return 0;}/*============================*/int ListDelete(List* plist,int n){ ChainNode *pt=0; ChainNode *pf=0; if (!plist->head->next) { return 0; } pt=GetAddr(plist,n-1); if (pt->next==plist->tail) { plisy->tail=pt; } if (!(pt&&pt->next)) { return 0; } pf=pt->next; pt->next=pt->next->next; free(pf->data); free(pf); return 1;}/*============================*/ChainNode * GetAddr(List * plist,int n) { ChainNode * pt = 0; int a = 0; if( n < 0) return 0; pt = plist->head; while( pt && a < n ) { pt = pt->next; a++; } return pt; } /*============================*/ChainNode * NewChainNode(ElemType data) { ChainNode * pChain=0; pChain = ( ChainNode * )malloc( sizeof(ChainNode) ); if( ! pChain ) return 0; pChain->data=http://www.mamicode.com/data; pChain->next=0; return pChain; }
#include "list.h" /*提供两种数据测试*/ typedef struct { char ch ; int id; char name[10]; int r;} myElemType; /* typedef char myElemType;*/ myElemType a[20] ={{‘a‘,1,"niei",2},{‘b‘,2,"aini",2},{‘c‘,3,"love",2},{‘d‘,4,"jack",2},{‘e‘,5,"alice",2},{‘f‘,6,"ben",2},{‘g‘,7,"carlo",2},{‘h‘,8,"mason",2}}; /*myElemType a[20]="Hello world!";*/ void showList(List* ); int putElem( myElemType *); void main() { List * mylist; int n=0; myElemType data; myElemType data2; myElemType* pdata; mylist = CreateList( sizeof(myElemType) ); if( ! mylist) { printf("error"); return; } for( n = 0 ;n < 8 ;n++) ListAppend(mylist ,a[n]); showList( mylist); data.ch = ‘*‘; data.id = 8; strcpy(data.name , "1223"); data.r = 2; /* a[0]=‘E‘; a[1]=‘r‘; a[2]=‘r‘; a[3]=‘o‘; a[4]=‘r‘;*/ ListInsert(mylist,1,data); showList( mylist); /**/ data2.ch = ‘A‘; data2.id = 54; strcpy(data2.name , "bill"); data2.r = 4; ListInsert(mylist,7,data2); showList( mylist); ListDelete(mylist,7); showList( mylist); ListDelete(mylist,1); showList( mylist); if (GetElem(mylist,5,&data2) ) /* printf("[%c %d %s %d] ",data2.ch,data2.id,data2.name,data2.r);*/ printf("[%c]",data2); ClearList(mylist); showList( mylist); DestoryList(mylist); mylist = 0; showList( mylist); } /*==================*/ void showList(List* plist) { if( !plist ) return; TraverseList(plist,(int(*)(void *))putElem); printf("\n"); } /*输出字符*/ /*int putElem(myElemType *data){ if( ! ( data) ) return 0; printf("%c",*data); return 1;}*/ /*输出结构体*/ /**/ int putElem(myElemType *data) { if( ! ( data) ) return 0; printf("[%c %d %s %d] ",(data)->ch,(data)->id,(data)->name,(data)->r); return 1; }
算法2---链表2---链表任意存储的实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。