数据结构之线性表

1 顺序存储结构
2 链式存储结构
2.1 头指针：链表中第一个节点的存储位置
2.2 头结点：放在第一个元素节点前
2.3 若线性表为空表，则头结点的指针域为空

2.3 线性表的单链表存储结构

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

2.4 单链表的读取

Status GetElem (LinkList L, int i, ElemType *e)
{
    int j;
    LinkList p;
    p = L->next;
    j = 1;

    while (p && j < i)
    {
        p = p->next;
        ++j;
    }

    if (!p || j > i)
    {
            return ERROR;
    }
    *e = p->data;
    return OK;  
}

2.5 单链表的插入

Status ListInsert (LinkList *L, int i, ElemType e)
{
    int j = 1;
    LinkList p = *L;
    LinkList s = NULL;
    if (i < 0)
    {
        printf ("illegal position. i = %d\r\n", i);
    }

    while (p && j < i)
    {
        p = p->next;
        ++j；
    }
    if (!p || j > i)
    {
        return ERROR;
    }

    s = (LinkList)malloc(sizeof (Node));
    if (s == NULL)
    {
        printf ("Failed to malloc memory.");
    }   
    s->data = e;
    s->next = p->next;
    p->next = s;

    return OK;
}

2.5 单链表的删除

Status ListDelete (LinkList *L, int i, ElemType *e)
{
    int j;
    LinkList p = *L;
    LinkList q;

    if (i < 0)
    {
        printf ("illegal position.\r\n");
    }

    while (p && j >i)
    {
        p = p->next;
        ++j;
    }
    if (!p || j > i)
    {
        return ERROR;
    }
    q = p->next;
    p->next = q->next;
    *e = q->data;
    free (q);

    return OK;
}

• 以上所有内容摘自《大话数据结构》程 杰 著 *
  

  ---