1. 为什么要用到链表

         数组作为存放同类数据的集合，给我们在程序设计时带来很多的方便，增加了灵活性。但数组也同样存在一些弊病。如数组的大小在定义时要事先规定，不能在程序中进行调整，这样一来，在程序设计中针对不同问题有时需要3 0个大小的数组，有时需要5 0个数组的大小，难于统一。我们只能够根据可能的最大需求来定义数组，常常会造成一定存储空间的浪费。

        我们希望构造动态的数组，随时可以调整数组的大小，以满足不同问题的需要。链表就是我们需要的动态数组。它是在程序的执行过程中根据需要有数据存储就向系统要求申请存储空间，决不构成对存储区的浪费。

链表是一种复杂的数据结构，其数据之间的相互关系使链表分成三种：单链表、循环链表、双向链表，下面将逐一介绍。

2.单链表

链表在进行循环遍历时效率不高，但是插入和删除时优势明显。

单链表实际上是由节点（Node）组成的，一个链表拥有不定数量的节点。而向外暴露的只有一个头节点（Head），我们对链表的所有操作，都是直接或者间接地通过其头节点来进行的。节点（Node）是由一个需要储存的对象及对下一个节点的引用组成的。也就是说，节点拥有两个成员：储存的对象、对下一个节点的引用。其实应该用数据和地址代替前面的对象和引用的。

单链表的结构示意图（包括空的单链表）：

那么大家可能清楚了，为什么说有了头节点就可以操作所有节点。因为有连续不断的引用嘛！那么在链表里的属性大概就只有两个了：头节点和节点数量。当然，根据需要，我们通常需要更多的属性。

下面用C语言简单写一个单链表，并完成初始化，创建链表与链表遍历、插入、删除等操作。

（1）链表的创建、输出步骤

          单链表的创建过程有以下几步：

              1 ) 定义链表的数据结构;

              2 ) 创建一个空表;

              3 ) 利用malloc ( )函数向系统申请分配一个节点;

              4 ) 将新节点的指针成员赋值为空。若是空表，将新节点连接到表头；若是非空表，将新节点接到表尾;

              5 ) 判断一下是否有后续节点要接入链表，若有转到3 )，否则结束;

          单链表的输出过程有以下几步：

                 1 ) 找到表头;

                 2 ) 若是非空表，输出节点的值成员，是空表则退出;

                 3 ) 跟踪链表的增长，即找到下一个节点的地址;

                 4 ) 转到2 ) 。

           http://hi.csdn.net/attachment/201112/21/0_1324454910hoPP.gif

 3.代码

#include "stdafx.h"
#include "stdio.h"
#include
#include "string.h"

typedef int elemType;


 



















 
 

typedef struct Node{   
    elemType element;
    Node *next;
}Node;
 
 

void initList(Node **pNode)
{
    *pNode = NULL;
    printf("initList函数执行，初始化成功\n");
}
 

Node *createList(Node *pHead)
{
    Node *p1;
    Node *p2;
    p1=p2=(Node *)malloc(sizeof(Node)); //申请新节点
    if(p1 == NULL || p2 ==NULL)
    {
        printf("内存分配失败\n");
        exit(0);
    }
    memset(p1,0,sizeof(Node));
 
    scanf("%d",&p1->element);     //输入新节点
    p1->next = NULL;              //新节点的指针置为空
    while(p1->element > 0)        //输入的值大于0则继续，直到输入的值为负
    {
        if(pHead == NULL)         //空表，接入表头
        {
            pHead = p1;
        }
        else              
        {
            p2->next = p1;        //非空表，接入表尾
        }
        p2 = p1;
        p1=(Node *)malloc(sizeof(Node));    //再重申请一个节点
        if(p1 == NULL || p2 ==NULL)
        {
            printf("内存分配失败\n");
            exit(0);
        }
        memset(p1,0,sizeof(Node));
        scanf("%d",&p1->element);
        p1->next = NULL;
    }
    printf("creatList函数执行，链表创建成功\n");
    return pHead;           //返回链表的头指针
}

Node *createList()
{
    Node *pHead;                               //指向头结点指针
    Node *pTail,*pNew;
    int n = 0;
    pTail = pNew = (Node *)malloc(sizeof(Node));      //为头结点分配内存空间
    if(NULL == pTail || NULL == pNew)
    {
        printf("内存分配失败！\n");
        exit(0);
    }
    printf("开始插入记录！\n");
    scanf("%d", &pNew->element);
                                
    while(pNew->element >= 0)                    //遇到负数退出
    {
        n++;
        if(n == 1)
            pHead = pNew;
        else
            pTail->next = pNew;                  //将p指向新结点插入链表也就是头结点指针域指向下个结点
        pTail = pNew;                        //第一个结点就是p指向的，因为头结点内容为空,这个起着指向下一个结点的作用

  pNew=(Node *)malloc(sizeof(Node));        //为要插入的节点分配内存空间p指向新插入节点的首地址
        if(NULL == pNew)
        {
            printf("内存分配失败！\n");
            exit(0);
        }
        scanf("%d",&pNew->element);               //输入数据
    }
    pTail->next = NULL;                           //将头结点的指针域清空
    printf("记录插入完毕！\n");
    return pHead;
}

Node *createList(int num)
{
 Node *pHead;
 Node *pTail,*pNew;
 pHead = (Node *)malloc(sizeof(Node));
 if(NULL == pHead)
 {
  printf("内存分配失败！\n");
  exit(0);
 }
 printf("开始插入记录！\n");
 scanf("%d",&pHead->element);
 pTail = pHead;
 pTail->next = NULL;
 for(int i = 1; i < num; i++)
 {
  pNew=(Node *)malloc(sizeof(Node));
  scanf("%d",&pNew->element);
  pTail->next = pNew;
  pNew->next = NULL;
  pTail = pNew;
 }
 printf("记录插入完毕！\n");
 return pHead;
}
 

void printList(Node *pHead)
{
    if(NULL == pHead)   //链表为空
    {
        printf("PrintList函数执行，链表为空\n");
    }
    else
    {
        while(NULL != pHead)
        {
            printf("%d ",pHead->element);
            pHead = pHead->next;
        }
        printf("\n");
    }
}

void clearList(Node *pHead)
{
    Node *pNext;            //定义一个与pHead相邻节点
 
    if(pHead == NULL)
    {
        printf("clearList函数执行，链表为空\n");
        return;
    }
    while(pHead->next != NULL)
    {
        pNext = pHead->next;//保存下一结点的指针
        free(pHead);
        pHead = pNext;      //表头下移
    }
    printf("clearList函数执行，链表已经清除\n");
}
 

int sizeList(Node *pHead)
{
    int size = 0;
    while(pHead != NULL)
    {
        size++;         //遍历链表size大小比链表的实际长度小1
        pHead = pHead->next;
    }
    printf("sizeList函数执行，链表长度 %d \n",size);
    return size;    //链表的实际长度
}

int isEmptyList(Node *pHead)
{
    if(pHead == NULL)
    {
        printf("isEmptyList函数执行，链表为空\n");
        return 1;
    }
    printf("isEmptyList函数执行，链表非空\n");
 
    return 0;
}

elemType getElement(Node *pHead, int pos)
{
    int i=0;
 
    if(pos < 1)
    {
        printf("getElement函数执行，pos值非法\n");
        return 0;
    }
    if(pHead == NULL)
    {
        printf("getElement函数执行，链表为空\n");
        return 0;
        //exit(1);
    }
    while(pHead !=NULL)
    {
        ++i;
        if(i == pos)
        {
            break;
        }
        pHead = pHead->next; //移到下一结点
    }
    if(i < pos)                  //链表长度不足则退出
    {
        printf("getElement函数执行，pos值超出链表长度\n");
        return 0;
    }
 
    return pHead->element;
}

elemType *getElemAddr(Node *pHead, elemType x)
{
    if(NULL == pHead)
    {
        printf("getElemAddr函数执行，链表为空\n");
        return NULL;
    }
    if(x < 0)
    {
        printf("getElemAddr函数执行，给定值X不合法\n");
        return NULL;
    }
    while((pHead->element != x) && (NULL != pHead->next)) //判断是否到链表末尾，以及是否存在所要找的元素
    {
        pHead = pHead->next;
    }
    if((pHead->element != x) && (pHead != NULL))
    {
        printf("getElemAddr函数执行，在链表中未找到x值\n");
        return NULL;
    }
    if(pHead->element == x)
    {
        printf("getElemAddr函数执行，元素 %d 的地址为 0x%x\n",x,&(pHead->element));
    }
 
    return &(pHead->element);//返回元素的地址
}
 

int modifyElem(Node *pNode,int pos,elemType x)
{
    Node *pHead;
    pHead = pNode;
    int i = 0;
 
    if(NULL == pHead)
    {
        printf("modifyElem函数执行，链表为空\n");
    }
    if(pos < 1)
    {
        printf("modifyElem函数执行，pos值非法\n");
        return 0;
    }
    while(pHead !=NULL)
    {
        ++i;
        if(i == pos)
        {
            break;
        }
        pHead = pHead->next; //移到下一结点
    }
    if(i < pos)                  //链表长度不足则退出
    {
        printf("modifyElem函数执行，pos值超出链表长度\n");
        return 0;
    }
    pNode = pHead;
    pNode->element = x;
    printf("modifyElem函数执行\n");
    
    return 1;
}
 

int insertHeadList(Node **pNode,elemType insertElem)
{
    Node *pInsert;
    pInsert = (Node *)malloc(sizeof(Node));
    memset(pInsert,0,sizeof(Node));
    pInsert->element = insertElem;
    pInsert->next = *pNode;
    *pNode = pInsert;
    printf("insertHeadList函数执行，向表头插入元素成功\n");
 
    return 1;
}
 

int insertLastList(Node **pNode,elemType insertElem)
{
    Node *pInsert;
    Node *pHead;
    Node *pTmp; //定义一个临时链表用来存放第一个节点
 
    pHead = *pNode;
    pTmp = pHead;
    pInsert = (Node *)malloc(sizeof(Node)); //申请一个新节点
    memset(pInsert,0,sizeof(Node));
    pInsert->element = insertElem;
 
    while(pHead->next != NULL)
    {
        pHead = pHead->next;
    }
    pHead->next = pInsert;   //将链表末尾节点的下一结点指向新添加的节点
    *pNode = pTmp;
    printf("insertLastList函数执行，向表尾插入元素成功\n");
 
    return 1;
}
 

int insertPosList(Node *pHead, int pos, elemType insertElem)
{
 int i = 0;
 Node *newElem;
 Node *cp = pHead, *ap = NULL;
 
 if(pos < 0)
 {
  printf("pos值非法，返回0表示插入失败！");
  return 0;
 }
 while(cp != NULL)
 {
  i++;
  if(pos == i)
   break;
  else
  {
   ap = cp;
   cp = cp->next;
  }
 }
 newElem = (Node *)malloc(sizeof(Node));
 if(NULL == newElem)
 {
  printf("内存分配失败！\n");
  exit(0);
 }
 newElem->element = insertElem;
 if(ap == NULL)
 {
  newElem->next = cp;
  pHead = newElem;
 }
 else
 {
  newElem->next = cp;
  ap->next = newElem;
 }
 return 1;
}

 

int main()
{
    Node *pList=NULL;
    int length = 0;
 
    elemType posElem;
 
    initList(&pList);       //链表初始化
    printList(pList);       //遍历链表，打印链表
 
    pList=creatList(pList); //创建链表
    printList(pList);
    
    sizeList(pList);        //链表的长度
    printList(pList);
 
    isEmptyList(pList);     //判断链表是否为空链表
    
    posElem = getElement(pList,3);  //获取第三个元素，如果元素不足3个，则返回0
    printf("getElement函数执行，位置 3 中的元素为 %d\n",posElem);  
    printList(pList);
 
    getElemAddr(pList,5);   //获得元素5的地址
 
    modifyElem(pList,4,1);  //将链表中位置4上的元素修改为1
    printList(pList);
 
    insertHeadList(&pList,5);   //表头插入元素12
    printList(pList);
 
    insertLastList(&pList,10);  //表尾插入元素10
    printList(pList);
 
    clearList(pList);       //清空链表
    system("pause");
    
}