数据结构单链表表示的三种方法

　　对于线性表来说，总得有个头尾，头部做为基准地址，如数组的数组名，链表的头指针。尾部做为结束的标志，数组使用一个长度属性来标识数组的结束位置，字符串使用转义字符，链表使用NULL指针来标识结束位置。
　　我们知道，数组的全部元素是集中存储，数组的基准地址是第一个元素的地址，也就是数组名的值，其它元素的索引都是一个整型常量，对元素的访问就是基准地址相对于索引的偏移，所以数组元素可以随机访问。
　　链式存储是分散存储，通过节点的指针域来建立一个节点与其下一个邻接节点的联系。链式存储的头指针虽然也是整个链式数据结构的基准地址，但要找到某一节点，需要顺序访问，从头节点开始，顺着每一个节点的指针域的值，一个节点一个节点地挼。
　　我们把链表中第一个节点的存储位置叫做头指针，那么整个链表的存取就必须是从头指针开始进行了。之后的每一个节点，其实就是上一个的后继指针指向的位置。有时，我们为了更加方便地对链表进行操作，会在单链表的第一个结点前附设一个结点，称为头节点。头节点的数据域可以不存储任何信息，谁叫它是第一个呢，有这个特权。也可以存储如线性表的长度等附加信息，头节点的指针域存储指向第一个节点的指针。
　　头指针
　　头节点
　　1头指针是指链表指向第一个节点的指针，若链表有头结点，则是指向头结点的指针
　　1头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义（也可存放链表的长度）
　　2头指针具有标识作用，所以常用头指针冠以链表的名字
　　2有了头结点，对在第一个元素节点前插入节点和删除第一节点，其操作与其它结点的操作就统一了
　　3无论链表是否为空，头指针均不为空。头指针是链表的必要元素
　　3头结点不一定是链表必须要素
　　是否使用头节点，在实现链表的常用操作时代码的写法稍有区别，使用头节点的方法代码较为简洁。同时，也可以将这个表头节点指针封装到一个结构体中，并在结构体中增加链表长度等信息。
　　1使用头节点的链表表示
　　加头结点的优点：
　　1）链表第一个位置的操作无需特殊处理；
　　2）将空表和非空表的处理统一。includestdio。hincludemalloc。htypedefstructNode｛intdata；structNodenext；｝Node，pNode；pNodecreateList（）头节点是空节点｛pNodehead（pNode）malloc（sizeof（Node））；if（headNULL）｛printf（mallocfailed！）；returnhead；｝headdata0；headnextNULL；returnhead；｝intinsert（pNodehead，intdata）头插法｛pNodenewNode（pNode）malloc（sizeof（Node））；if（newNodeNULL）｛printf（mallocfailed！）；return1；｝newNodedatadata；newNodenextheadnext；headnextnewNode；return0；｝voidprintList（pNodehead）｛pNodecurheadnext；while（cur）｛printf（d，curdata）；curcurnext；｝｝voiddestroyList（pNodehead）｛pNodephead；pNodeqpnext；while（q！NULL）｛free（p）；pq；qpnext；｝free（p）；｝intmain（）｛pNodeheadcreateList（）；for（inti0；i10；i）insert（head，i1）；printList（head）；destroyList（head）；getchar（）；return0；｝10987654321
　　2不使用头节点的链表表示includestdio。hincludemalloc。htypedefstructNode｛intdata；structNodenext；｝Node，pNode；intinsert（pNodehead，intdata）头插法，头部是一个实节点｛pNodenewNode（pNode）malloc（sizeof（Node））；if（newNodeNULL）｛printf（mallocfailed！）；return1；｝newNodedatadata；if（headNULL）newNodenextNULL；elsenewNodenexthead；headnewNode；return0；｝voidprintList（pNodehead）｛pNodecurhead；while（cur）｛printf（d，curdata）；curcurnext；｝｝voiddestroyList（pNodehead）｛pNodephead；pNodeqpnext；while（q！NULL）｛free（p）；pq；qpnext；｝free（p）；｝intmain（）｛pNodeheadNULL；for（inti0；i10；i）insert（head，i1）；printList（head）；destroyList（head）；getchar（）；return0；｝10987654321
　　3链表和链表节点用不同的结构体来表示
　　链表用一个结构体来描述，封装一个节点指针做表头，并增加一个链表长度变量，需要时也可以增加一个节点指针做表尾。includestdio。hincludemalloc。htypedefstructNode｛intdata；structNodenext；｝Node，pNode；typedefstructList｛pNodehead；intsize；｝List，pList；pListcreateList（）｛pListpl（pList）malloc（sizeof（List））；if（plNULL）｛printf（mallocfailed！）；returnpl；｝plhead（pNode）malloc（sizeof（Node））；if（plheadNULL）｛printf（mallocfailed！）；returnNULL；｝plheaddata0；plheadnextNULL；plsize0；returnpl；｝intinsert（pListpl，intdata）头插法，头部是一个空节点｛pNodenewNode（pNode）malloc（sizeof（Node））；if（newNodeNULL）｛printf（mallocfailed！）；return1；｝newNodedatadata；newNodenextplheadnext；plheadnextnewNode；plsize；return0；｝voidprintList（pListpl）｛pNodecurplheadnext；while（cur）｛printf（d，curdata）；curcurnext；｝｝voiddestroyList（pListpl）｛pNodep（pl）head；pNodeqpnext；while（q！NULL）｛free（p）；pq；qpnext；｝free（p）；free（pl）；｝intmain（）｛pListplcreateList（）；for（inti0；i10；i）insert（pl，i1）；printList（pl）；destroyList（pl）；getchar（）；return0；｝10987654321
　　End