数据结构之线性表(单链表）

  

1. 线性链表

  

   线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。这些数据元素可以存在内存未被占用的任意位置。

   它包括两个域：其中存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称为指针或链。

   由于此链表的每个结点中只包含一个指针域，故又称为线性链表或单链表。

   对于线性表来说，总得有个头有个尾，链表也不例外。我们把链表中第一个结点的存储位置叫做头指针，那么整个链表的存取就必须是从头指针开始进行的。之后的每个结点，其实就是上一个后指针指向的位置。最后一个结点，意味着后继不再存在，所以，规定线性链表的最后一个结点指针为“空”（通常为NULL)。 

   线性表的单链表存储结构，如下所示。

typedef struct Node
{
     ElemType data;
     struct Node *next;
}Node, LinkList;

2. 线性表的操作

  获取链表第i个数据的算法思路：

  1）声明一个结点p指向链表第一个结点，初始化j从1开始；

  2）当j时，就遍历链表，p的指针向后移动，不断指向下一个结点，j累加1；

  3）若到链表末尾p为空，则说明第i个元素不存在；

  4）否则查找成功，返回结点p的数据。

  单链表第i个数据插入结点的算法思路：

  

  1）声明一个结点p指向链表的第一个结点，初始化j从1开始；

  2）当j时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1；

  3）若到链表末尾p为空，则说明第i个元素不存在；

  4）否则查找成功，在系统中生成一个空结点s；

  5）将数据元素e赋值给s->data；

  6）单链表的插入标准语句s->next = p->next；p->next = s；

  7）返回成功。

  单链表第i个数据删除结点的算法思路：

  

  1）声明一个结点p指向单链表的第一个结点，初始化j从1开始；

  2）当j时，就遍历链表，让p指针向后移动，不断指向下一个结点，j累加1；

  3）若到链表末尾p为空，则说明第i个元素不存在；

  4）否则查找成功，将欲删除的结点p->next赋值给q；

  5）单链表的删除标准语句p->next = q->next；

  6）将q结点中的数据赋值给e，作为返回；

  7）释放q结点。

  单链表的整表创建的算法思路：

  

  1）声明一个结点p和计数器变量i；

  2）初始化一空链表L；

  3）让L的头结点的指针指向NULL，即建立一个带头结点的单链表；

  4）循环

* 生成一新结点赋值给p；

* 随机生成一数字赋值给p的数据域p->data；

* 将p插入到头结点域前一新结点之间。

  单链表的整表删除的算法思路如下：

  

  1）声明一结点p和q；

  2）将第一个结点赋值给p；

  3）循环：

* 将下一个结点赋值给q；

* 释放p；

* 将q赋值给p；

3. 线性表操作的C实现

#include <stdio.h>
#include <stdlib.h>

#define OK     0
#define ERROR 1

//typedef ElemType int;
#define ElemType int
typedef struct Node
{
    ElemType  data;
    struct Node *next;
}Node, *LinkList;

/* 函数功能：获取链表第i个数据
 * 操作结果：用e返回L中第i个数据元素的值
 * 返回值：
 *         ERROR：i值不合法
 *         OK      ：操作成功
 *
 * 最坏时间复杂度为O(n)
*/
int GetElem(LinkList L, int i, ElemType *e)
{
    if( i <= 0)
    {
        fprintf(stderr, "i should more 1 and less LinkLength(L).\n");
        return ERROR;
    }
    LinkList p = L->next;            //声明一结点p
    int j = 1;                        //j为计数器

    while(j < i && p != NULL)        //p不为空且计数器j还没有等于i时，循环继续
    {
        p = p->next;
        j++;
    }

    if(!p || j > i)                    //第i个元素不存在
    {
        return ERROR;
    }

    *e = p->data;

    return OK;
}


/* 函数名称: ListInsert
 * 函数功能: 在链表的第i个位置之前插入数据元素e
 * 返回值:
 *        ERROR: i不合法
 *        OK : 插入成功
 *
 * 注意：参数L为指针的指针
*/

int LinkInsert(LinkList *L, int i, ElemType e)
{
    if( i <= 0)
    {
        fprintf(stderr, "i<=0不合法.\n");
        return ERROR;
    }

    LinkList p;
    p = *L;
    int j = 1;

    while(j < i && p != NULL)            //寻找第i个结点
    {
        p = p->next;
        ++j;
    }

    if(!p || j > i)                        //第i个结点不存在
    {
        return ERROR;
    }

    LinkList temp = (LinkList)malloc(sizeof(struct Node));
    if(!temp)
    {
        fprintf(stderr, "malloc() error.\n");
        return ERROR;
    }

    temp->data = e;

    temp->next = p->next;
    p->next = temp;

    return OK;
}

/* 函数名称: ListDelete
 * 函数功能: 删除L中的第i个元素，并用e返回其值
 * 返回值:
 *        ERROR: i不合法
 *        OK : 删除成功
 *
 * 最坏时间复杂度为O(n)
*/
int ListDelete(LinkList *L, int i, ElemType *e)
{
    if(i <= 0)
    {
        fprintf(stderr, "i <= 0不合法.\n");
        return ERROR;
    }

    LinkList p,q;
    p = *L;
    int j = 1;

    while(j < i && p->next != NULL)        //遍历寻找第i个结点
    {
        p = p->next;
        ++j;
    }

    if(p->next == NULL || j > i)
    {
        return ERROR;
    }

    q = p->next;
    p->next = q->next;
    *e = q->data;

    free(q);

    return OK;
}

/* 函数名称: CreateList
 * 函数功能: 随机产生n个元素的值，建立带头结点的单链表L(头插法)
 * 返回值:
 *        ERROR: malloc() error
 *        OK : 创建成功
 *
 */
int CreateList(LinkList *L, int n)
{
    LinkList p;
    int i = 1;
    srand(time(0));                                    //初始化随机数种子

    *L = (LinkList)malloc(sizeof(struct Node));        //先建立一个带头结点的单链表
    if(*L == NULL)
    {
        fprintf(stderr, "malloc() error.\n");
        return ERROR;
    }
    (*L)->next = NULL;

    while(i <= n)
    {
        p = (LinkList)malloc(sizeof(struct Node));
        if( p == NULL)
        {
            fprintf(stderr, "malloc() error.\n");
            return ERROR;
        }
        p->data = rand() % 100 + 1;
        p->next = (*L)->next;
        (*L)->next = p;                                    //插入到表头

        i++;
    }
    /*
    //尾插法
    LinkList r；
    r = *L;                                                //r为指向尾部的结点
    for(i = 0; i < n; i++)
    {
        p = (LinkList)malloc(sizeof(struct Node));        //生成新结点
        p->data = rand() % 100 + 1;
        r->next = p;                                    //将表尾终端结点的指针指向新结点
        r = p;                                            //将当前的新结点定义为表尾部结点
    }
    r->next = NULL;                                        //表示当前链表结束
    */
    return OK;
}

/* 函数名称: ClearList
 * 函数功能: 单链表删除
*/
int ClearList(LinkList *L)
{
    if(*L == NULL)
    {
        return ERROR;
    }

    LinkList q, p;
    p = (*L)->next;        //p指向第一个结点

    while(p)            //没有到表尾部
    {
        q = p->next;    //注意哦
        free(p);
        p = q;
    }

    (*L)->next = NULL;    //头结点指针域为空

    return OK;
}

int printList(LinkList L)
{
    LinkList p;
    p = L->next;
    if(p == NULL)
    {
        printf("链表为空.\n");
        return ERROR;
    }
    while(p)
    {
        printf("%d  ", p->data);
        p = p->next;
    }
    printf("\n");

    return OK;
}

int main(int argc, char **argv)
{
    LinkList L;

    printf("创建的新链表为:\n");
    CreateList(&L, 5);
    printList(L);

    printf("在第3个位置之前插入元素10后结果为:\n");
    LinkInsert(&L, 3, 10);
    printList(L);

    int e;
    GetElem(L, 3, &e);
    printf("链表第3个位置的元素为: %d\n", e);

    printf("删除第3个位置的元素后结果为:\n");
    ListDelete(&L, 3, &e);
    printList(L);

    printf("清空链表:\n");
    ClearList(&L);
    printList(L);

    return 0;
}

   运行环境：RedHat

   编译工具：Gcc

   

   运行结果如下所示：

    参考：严蔚敏老师之《数据结构》

                                                                                                                                                          梦醒潇湘love

                                                                                                                                                      2013-01-08 20:30