单链表

更新时间：2022-08-12 23:23:02

 
 
来源：http://blog.csdn.net/hopeyouknow/article/details/6711216

[cpp] view plaincopy
#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  

实现如下

[cpp] view plaincopy
#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;  
}  

测试如下

[cpp] view plaincopy

1. #include"List.h"
2. #include<stdlib.h>
3. int main()
4. {
5. List list=NULL;
6. Position p;
7. int i;
8. list = MakeEmpty(list);
9. printf("已生成空链表list\n");
10. if(IsEmpty(list))
11. printf("经检验list是个空链表\n");
13. p = list;
14. for(i=0;i<5;i++)
15. {
16. Insert(i*i,list,p);
17. p = Advance(p);
18. printf("已插入的值为%d新节点\n",Retrieve(p));
19. }
20. p = FindNext(9,list);
21. printf("数据项为9的节点后继的数据项值为%d\n",Retrieve(p));
23. p = FindPrevious(9,list);
24. printf("数据项为9的节点前驱的数据项值为%d\n",Retrieve(p));
26. Delete(9,list);
28. p = list;
29. for(i=0;i<4;i++)
30. {
31. p = Advance(p);
32. printf("删除数据项为9的节点剩下的节点值为%d\n",Retrieve(p));
33. }
35. DeleteList(list);
36. printf("已删除链表list的所以数据节点\n");
37. if(IsEmpty(list))
38. printf("经检验list是个空链表\n");
40. }

本文转自夏雪冬日博客园博客，原文链接：http://www.cnblogs.com/heyonggang/p/3272645.html，如需转载请自行联系原作者

上一篇 : ：哈希表下一篇 : 一天一点学linux

单链表

相关阅读

推荐文章