链表的C语言实现之单链表的实现/article/2779.html一、单链表的建立有了动态内存分配的基础，要实现链表就不难了。

所谓链表，就是用一组任意的存储单元存储线性表元素的一种数据结构。

链表又分为单链表、双向链表和循环链表等。

我们先讲讲单链表。

所谓单链表，是指数据接点是单向排列的。

一个单链表结点，其结构类型分为两部分：1、数据域：用来存储本身数据2、链域或称为指针域：用来存储下一个结点地址或者说指向其直接后继的指针。

例：typedef struct node{char name[20];struct node *link;}stud;这样就定义了一个单链表的结构，其中char name[20]是一个用来存储姓名的字符型数组，指针*link是一个用来存储其直接后继的指针。

定义好了链表的结构之后，只要在程序运行的时候爱数据域中存储适当的数据，如有后继结点，则把链域指向其直接后继，若没有，则置为NULL。

下面就来看一个建立带表头（若未说明，以下所指链表均带表头）的单链表的完整程序。

#include ＜stdio.h＞#include ＜malloc.h＞ /*包含动态内存分配函数的头文件*/#define N 10 /*N为人数*/typedef struct node{char name[20];struct node *link;}stud;stud * creat(int n) /*建立单链表的函数，形参n为人数*/{stud *p,*h,*s; /* *h保存表头结点的指针，*p指向当前结点的前一个结点，*s指向当前结点*/int i; /*计数器*/if((h=(stud *)malloc(sizeof(stud)))==NULL) /*分配空间并检测*/{printf("不能分配内存空间!");exit(0);}h-＞name[0]='\0'; /*把表头结点的数据域置空*/h-＞link=NULL; /*把表头结点的链域置空*/p=h; /*p指向表头结点*/for(i=0;i＜n;i++){if((s= (stud *) malloc(sizeof(stud)))==NULL) /*分配新存储空间并检测*/{printf("不能分配内存空间!");exit(0);}p-＞link=s; /*把s的地址赋给p所指向的结点的链域，这样就把p和s所指向的结点连接起来了*/printf("请输入第%d个人的姓名",i+1);scanf("%s",s-＞name); /*在当前结点s的数据域中存储姓名*/s-＞link=NULL;p=s;}return(h);}main(){int number; /*保存人数的变量*/stud *head; /*head是保存单链表的表头结点地址的指针*/number=N;head=creat(number); /*把所新建的单链表表头地址赋给head*/}这样就写好了一个可以建立包含N个人姓名的单链表了。

写动态内存分配的程序应注意，请尽量对分配是否成功进行检测。

数据结构学习(C++)之单链表节点类【说明】因为数据结构里用到这个结构的地方太多了，如果用《数据结构》那种声明友元的做法，那声明不知道要比这个类的本身长多少。

不如开放成员，事实上，这种结构只是C中的struct，除了为了方便初始化一下，不需要任何的方法，原书那是画蛇添足。

下面可以看到，链表的public部分没有返回Node或者Node*的函数，所以，别的类不可能用这个开放的接口对链表中的节点操作。

【重要修改】原书的缺省构造函数是这样的Node() : data(NULL), link(NULL) {} 。

我原来也是照着写的，结果当我做扩充时发现这样是不对的。

当Type为结构而不是简单类型（int、……），不能简单赋NULL 值。

这样做使得定义的模板只能用于很少的简单类型。

显然，这里应该调用Type的缺省构造函数。

这也要求，用在这里的类一定要有缺省构造函数。

在下面可以看到构造链表时，使用了这个缺省构造函数。

当然，这里是约定带表头节点的链表，不带头节点的情况请大家自己思考。

【闲话】请不要对int *p = new int(1);这种语法有什么怀疑，实际上int也可以看成一种class。

单链表类定义与实现#ifndef List_H#define List_H#ifndef TURE#define TURE 1#endif#ifndef FALSE#define FALSE 0#endiftypedef int BOOL;#include "Node.h"template <class Type> class List //单链表定义{//基本上无参数的成员函数操作的都是当前节点，即current指的节点//认为表中“第1个节点”是第0个节点，请注意，即表长为1时，最后一个节点是第0个节点public:List() { first = current = last = new Node<Type>; prior = NULL; }~List() { MakeEmpty(); delete first; }void MakeEmpty() //置空表{Node<Type> *q;while (first->link != NULL){q = first->link;first->link = q->link;delete q;}Initialize();}BOOL IsEmpty(){if (first->link == NULL){Initialize();return TURE;}else return FALSE;}int Length() const //计算带表头节点的单链表长度{Node<Type> *p = first->link;int count = 0;while (p != NULL){p = p->link;count++;}return count;}Type *Get()//返回当前节点的数据域的地址{if (current != NULL) return &current->data;else return NULL;}BOOL Put(Type const &value)//改变当前节点的data，使其为value{if (current != NULL){current->data = value;return TURE;}else return FALSE;}Type *GetNext()//返回当前节点的下一个节点的数据域的地址，不改变current{if (current->link != NULL) return &current->link->data;else return NULL;}Type *Next()//移动current到下一个节点，返回节点数据域的地址{if (current != NULL && current->link != NULL){prior = current;current = current->link;return &current->data;}else{return NULL;}}void Insert(const Type &value)//在当前节点的后面插入节点，不改变current{Node<Type> *p = new Node<Type>(value, current->link);current->link = p;}BOOL InsertBefore(const Type &value)//在当前节点的前面插入一节点，不改变current，改变prior {Node<Type> *p = new Node<Type>(value);if (prior != NULL){p->link = current;prior->link = p;prior = p;return TURE;}else return FALSE;}BOOL Locate(int i)//移动current到第i个节点{if (i <= -1) return FALSE;current = first->link;for (int j = 0; current != NULL && j < i; j++, current = current->link)prior = current;if (current != NULL) return TURE;else return FALSE;}void First()//移动current到表头{current = first;prior = NULL;}void End()//移动current到表尾{if (last->link != NULL){for ( ;current->link != NULL; current = current->link)prior = current;last = current;}current = last;}BOOL Find(const Type &value)//移动current到数据等于value的节点{if (IsEmpty()) return FALSE;for (current = first->link, prior = first; current != NULL && current->data != value;current = current->link)prior = current;if (current != NULL) return TURE;else return FALSE;}BOOL Remove()//删除当前节点，current指向下一个节点，如果current在表尾，执行后current = NULL {if (current != NULL && prior != NULL){Node<Type> *p = current;prior->link = p->link;current = p->link;delete p;return TURE;}else return FALSE;}BOOL RemoveAfter()//删除当前节点的下一个节点，不改变current{if (current->link != NULL && current != NULL){Node<Type> *p = current->link;current->link = p->link;delete p;return TURE;}else return FALSE;}friend ostream & operator << (ostream & strm, List<Type> &l){l.First();while (l.current->link != NULL) strm << *l.Next() << " " ;strm << endl;l.First();return strm;}protected:/*主要是为了高效的入队算法所添加的。