--
所谓链表记住一句即可：地址不连续，大家只是握个手而已；
list0.c
#include<stdio.h> #include<malloc.h> typedef int Item;//定义数据项类型 typedef struct node * PNode;//定义节点指针 //节点的定义 typedef struct node { Item item;//数据域 PNode next;//链域 }Node,* SList; /* int SL_Creat(SList *p_list,int size) 参数 p_list：指向一个链表指针，此处传入表头地址 size：要创建的链表分配的数据元素空间个数，不包含头节点 返回值 若成功返回1，否则返回0。 功能 该函数的功能是创建一个大小为size的链表并把链表的头指针赋给p_lsit所指的链表指针。 */ int SL_Creat(SList *p_list,int size) { PNode p=NULL; int i; *p_list = (SList)malloc(sizeof(Node)); if(*p_list==NULL) return -1; (*p_list)->next = NULL; for(i=size;i>0;i--) { p = (PNode)malloc(sizeof(Node)); if(p==NULL) return -1; p->item = 0; p->next = (*p_list)->next; (*p_list)->next = p; } return 1; } /* int SL_Insert(SList list,int pos,Item item) 参数 list：要插入数据的单链表 int：指定要插入元素的位置，从1开始计数 item:要插入的数据项 返回值 若成功返回1，否则返回-1。 功能 该函数的功能是在链表list的pos位置插入新元素，其值为item。 */ int SL_Insert(SList list,int pos,Item item) { PNode p,q; int i; p = list; i = 0; while(p!=NULL && i<pos-1)//将指针p移动到要插入元素位置之前 { p = p->next; i++;//i记录p指向的是第几个位置 } if(p==NULL || i > pos-1) return -1; q = (Node *)malloc(sizeof(Node));//未插入节点分配内存 if(q!=NULL)//若内存分配成功，将节点插入指定位置 { q->item = item; q->next = p->next; p->next = q; return 1; } else { return -1; } } /* int SL_GetItem(SList list,int pos,Item *p_item) 参数 list：要获取数据项所在的单链表 int：指定要获取元素在单链表中的位置 p_item:指向要接收数据项的变量 返回值 若成功返回1，否则返回-1。 功能 该函数的功能是获取在链表list的pos位置的元素的数据项，其值赋给p_item所指的变量。 */ int SL_GetItem(SList list,int pos,Item *p_item) { PNode p; int i; p = list; i = 0; while(p!=NULL && i<pos)//将指针p移动到要返回的元素位置 { p = p->next; i++;//i记录p指向的是第几个位置 } if((p==NULL)||(i>pos)) { return -1; } *p_item = p->item; return 1; } /* int SL_Delete(SList list,int pos,Item * p_item) 参数 list：要删除元素所在的单链表 int：指定要删除元素在单链表中的位置 p_item:指向接收删除元素的数据项的变量 返回值 若成功返回1，否则返回-1。 功能 该函数的功能是删除在链表list的pos位置的元素，其值赋给p_item所指的变量。 */ int SL_Delete(SList list,int pos,Item * p_item) { PNode p,q; int i; p = list; i = 0; while(p!=NULL && i<pos-1)//将指针p移动到要插入元素位置之前 { p = p->next; i++;//i记录p指向的是第几个位置 } if(p->next==NULL || i > pos-1) return -1; q = p->next; p->next = q->next; if(p_item != NULL) *p_item = q->item; free(q); return 1; } /* int SL_SetItem(SList list,int pos,Item item) 参数 list：要设置元素所在的单链表 int：指定要设置元素在单链表中的位置 p_item:要设置元素的数据项的值 返回值 若成功返回1，否则返回-1。 功能 该函数的功能是将链表list的pos位置的元素的数据项设置为item。 */ int SL_SetItem(SList list,int pos,Item item) { PNode p=NULL; int i; p = list; i = 0; while(p!=NULL && i<pos)//将指针p移动到要插入元素位置之前 { p = p->next; i++;//i记录p指向的是第几个位置 } if(p==NULL || i > pos) return -1; p->item = item; return 1; } /* int SL_Find(SList list,int *pos,Item item) 参数 list：要查找元素所在的单链表 int：指向要存储的查得的元素的位置的变量 p_item:要查找元素的数据项的值 返回值 若成功返回1，否则返回-1。 功能 该函数的功能是在链表list中查找数据项为item的元素，将其位置值赋给pos所指的变量。 */ int SL_Find(SList list,int *pos,Item item) { PNode p; int i; p = list; i = 0; while(p!=NULL && p->item!=item)//将指针p移动到要插入元素位置之前 { p = p->next; i++;//i记录p指向的是第几个位置 if(p->item == item) { *pos = i; //返回查询到的位置 return 1; } } return -1; } /* int SL_Empty(SList list) 参数 list：要判断的单链表 返回值 若为空则返回1，否则返回 0。 功能 该函数的功能是判断链表list是否为空表。 */ int SL_Empty(SList list) { PNode p; p = list; if(p->next == NULL) return 1; return 0; } /* int SL_Size(SList list) 参数 list：要查找的单链表 返回值 返回包含节点的个数。 功能 该函数的功能是返回链表list中节点的个数，包含头节点。 */ int SL_Size(SList list) { PNode p; int i; p = list; i = 0; while(p!=NULL) { p = p->next; i++; } return i; } /* int SL_Clear(SList *p_list) 参数 p_list：指向要清除的单链表 返回值 成功返回值为1。 功能 该函数的功能是清除链表的所有节点，包含头节点。 */ int SL_Clear(SList *p_list) { PNode p,q; int i; p = *p_list; i = 0; while(p!=NULL) { q = p->next;//借助于q存储p的链域，否则释放p后无法引用 free(p); p = q; } *p_list = NULL;//将所指的链表指针设为NULL return 1; }
list.c
#include"List.h" #include<malloc.h> #include<stdlib.h> /* List MakeEmpty(List L) 参数 L 要生成的空链表名 返回值 返回生成的空链表名 功能 生成空链表 */ List MakeEmpty(List L) { L = (PNode)malloc(sizeof(Node)); L->item = 0; L->next = NULL; return L; } /* int IsEmpty(List L) 参数 L 要判定的链表名 返回值 若L为空返回1，否则返回0 功能 判断链表L是否为空 */ int IsEmpty(List L) { return L->next == NULL; } /* int IsLast(Position P) 参数 P 要判定的位置 返回值 若P为为最后一个节点则返回1，否则返回0 功能 判断位置P的节点是否是链表最后一个节点 */ int IsLast(Position P) { return P->next == NULL; } /* Position Find(Item X,List L) 参数 X 要查找的数据项 L 要查找的链表 返回值 若X在L中存在则返回第一个匹配节点的位置，否则返回NULL 功能 判断位置P的节点是否是链表最后一个节点 */ Position Find(Item X,List L) { Position P; P = L->next; while( P!=NULL && P->item != X ) { P = P->next; } return P; } /* void Delete(Item X,List L) 参数 X 要删除的数据项 L 要删除节点所在的链表 返回值 无 功能 在链表L中删除查找到的第一个数据项为X的节点 */ void Delete(Item X,List L) { Position P,temp; /*读者请思考，temp为什么是必要的？*/ P = FindPrevious(X,L); if(!IsLast(P)) { temp = P->next; P->next = temp->next; free(temp); } } /* Position FindPrevious(Item X,List L) 参数 X 要查找的数据项 L 要查找的链表 返回值 若X在L中存在则返回第一个匹配节点的前驱位置，否则返回NULL 功能 返回链表L中数据项为X的节点的前驱节点位置 */ Position FindPrevious(Item X,List L) { Position P; P = L; while(P->next!=NULL && P->next->item != X) P = P->next; return P; } /* Position FindNext(Item X,List L) 参数 X 要查找的数据项 L 要查找的链表 返回值 若X在L中存在则返回第一个匹配节点的后继位置，否则返回NULL 功能 返回链表L中数据项为X的节点的后继节点位置 */ Position FindNext(Item X,List L) { Position P; P = L; while(P!=NULL && P->item != X) P = P->next; return P; } /* void Insert(Item X,List L,Position P) 参数 X 要插入的数据项 L 要插入的链表 返回值 无 功能 在链表L中P位置之后插入数据项为X的新节点 */ void Insert(Item X,List L,Position P) { Position temp; temp = malloc(sizeof(Node)); if(temp==NULL) exit(0); temp->item = X; temp->next = P->next; P->next = temp; } /* void DeleteList(List L) 参数 L 要删除节点的链表 返回值 无 功能 删除链表L中除了头节点之外的所有节点 */ void DeleteList(List L) { Position P,temp; P = L->next; L->next = NULL; while( P!=NULL) { temp = P->next; free(P); P = temp; } } /* Position Header(List L) 参数 L 要查找的链表 返回值 返回链表L的头节点位置 功能 返回头节点 */ Position Header(List L) { return L; } /* Position First(List L) 参数 L 要查找的链表 返回值 若链表非空则返回第一个数据节点，否则返回NULL 功能 返回第一个数据节点位置 */ Position First(List L) { if(L->next!=NULL) return L->next; } /* Position Advance(Position P) 参数 P 当前节点位置 返回值 若P位置后继节点存在则返回其位置，否则返回NULL 功能 获得位置P后继节点位置 */ Position Advance(Position P) { if(P!=NULL) return P->next; } /* Item Retrieve(Position P) 参数 P 当前节点位置 返回值 若P非空则返回其数据项的值 功能 返回P位置的数据项 */ Item Retrieve(Position P) { if(P!=NULL) return P->item; }
list.h
#ifndef List_H #define List_H typedef int Item;/*定义数据项类型*/ typedef struct node * PNode;/*定义节点指针*/ typedef struct node/*节点的定义*/ { Item item; /*数据域*/ PNode next; /*链域*/ }Node; typedef PNode Position; typedef PNode List; List MakeEmpty(List L); /* 功能 生成空链表L */ int IsEmpty(List L); /* 功能 判定链表是否为空 */ int IsLast(Position P); /* 功能 判定位置P的节点是否为尾节点 */ Position Find(Item X,List L); /* 功能 在链表L中查找数据项为X的第一个节点 */ void Delete(Item X,List L); /* 功能 在链表L中删除数据项为X的第一个节点 */ Position FindPrevious(Item X,List L); /* 功能 在链表L中查找数据项为X的第一个节点的前驱位置 */ Position FindNext(Item X,List L); /* 功能 在链表L中查找数据项为X的第一个节点的后继位置 */ void Insert(Item X,List L,Position P); /* 功能 在链表L中P位置插入数据项为X的节点 */ void DeleteList(List L); /* 功能 删除链表L初头节点外的所有节点 */ Position Header(List L); /* 功能 获得链表L中头节点位置 */ Position First(List L); /* 功能 获得链表L中第一个数据节点的位置 */ Position Advance(Position P); /* 功能 获得P位置的后继节点位置 */ Item Retrieve(Position P); /* 功能 获得P位置节点的数据项 */ #endif
main.c
#include"List.h" #include<stdlib.h> int main() { List list=NULL; Position p; int i; list = MakeEmpty(list); printf("已生成空链表list\n"); if(IsEmpty(list)) printf("经检验list是个空链表\n"); p = list; for(i=0;i<5;i++) { Insert(i*i,list,p); p = Advance(p); printf("已插入的值为%d新节点\n",Retrieve(p)); } p = FindNext(9,list); printf("数据项为9的节点后继的数据项值为%d\n",Retrieve(p)); p = FindPrevious(9,list); printf("数据项为9的节点前驱的数据项值为%d\n",Retrieve(p)); Delete(9,list); p = list; for(i=0;i<4;i++) { p = Advance(p); printf("删除数据项为9的节点剩下的节点值为%d\n",Retrieve(p)); } DeleteList(list); printf("已删除链表list的所以数据节点\n"); if(IsEmpty(list)) printf("经检验list是个空链表\n"); }
--
原创：
http://blog.csdn.net/hopeyouknow/article/details/6711216
--