线性结构笔记（一）

（一）链表

1.线性表的顺序存储

定义

typedef int Position;
typedef struct LNode * PtrToLNode;
struct LNode
{
    ElementType Data[MAXSIZE];
    Position Last;
};
typedef PtrToLNode List;

初始化

List MakeEmpty()
{
    List L;
    L = (List)malloc(sizeof(struct LNode));
    return L;
}

返回指定位置的元素

ElementType FindKth(List L, int i)
{
    return L->Last[i-1];
}

返回L中第一个与X相同的元素的位置，不存在就返回错误信息

Position Find(List L, ElementType X)
{
    Position i = 0;
    while(i<=L->Last&&L->Data[i]!=X)//如果i小于L->Last说明还有元素。如果还有元素，并且当前的元素不等于X，就i++
        i++;
    if(i > L->Last) return ERROR;//如果最后一个元素是X，那么i就等于L->Last，大于就说明没找到
    else return i;//既然不是没找到，那就是位置为i的元素
}

在位置i前面插入一个元素X

bool Insert(List L, ElementType X, int i)
{
    Position j;
    if(L->Last==MAXSIZE-1)//数组从0开始，假如有5个元素，最后一个下标为5-1
    {
        printf("表满了\n");
        return false;
    }
    if(i<1||i>L->Last+2)//L->Last是最后一个，插入到+2位置，就不是接着最后一个了
    {
        printf("位序不合法\n");
        return false;
    }
    //从后面开始每个元素都向后移动，将下标为i的元素移动后停止
    for(j=L->Last; j>=i; j--)
        L->Data[j+1] = L->Data[j];
    L->Data[i] = X;//对下标为i的元素赋值
    L->Last++;
    return true;
}

删除位置为i的元素

bool Delete(List L, int i)
{
    /*注意，删除第i个元素，其下标为i-1*/
    Position j;
    if(i<1||i>L->Last+1)
    {
        printf("位序%d不存在元素。\n", i);
        return false;
    }
    for(j=i-1; j<L->Last; j++)
        L->Data[j] = L->Data[j+1];
    L->Last--;
    return 0;
}

总结：链表的顺序存储就是对一个数组进行操作。

2.线性表的链式存储

定义

typedef struct LNode * PtrToLNode;
struct LNode
{
    ElementType Data;
    PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;

求表长（无头结点）

int Length(List L)
{
    Position p;
    int cnt = 0;
    p = L;
    while(p)
    {
        p = p->Next;
        cnt++;
    }
    return cnt;
}

按序号查找（无头结点）

Position Find(List L, ElementType X)
{
    Position p;
    p = L;
    while(p&&p->Data!=X)
    /*如果p不为NULL且元素不为X就到下一个，跳出的条件是到头或者找到X，返回值是X所在结点的地址或者NULL*/
        p = p->Next;
    return p;
}

插入（无头结点）

List Insert(List L, ElementType X, int i)
{
    Position tmp, pre;
    tmp = (Position)malloc(sizeof(struct LNode));   /*申请、填装结点*/
    tmp->Data = X;
    if(i==1)   /*新节点插在表头*/
    {
        tmp->Next = L;
        return tmp;
    }
    else   /*查找位序为i-1的结点*/
    {
        int cnt = 1;
        pre = L;
        while(pre&&cnt<i-1)
        {
            pre = pre->Next;
            cnt++;
        }
        if(pre==NULL||cnt!=i-1)  /*所查找的结点不在L中*/
        {
            printf("输入位置参数错误。\n");
            free(tmp);
            return ERROR;
        }
        else   /*找到了待插结点的前一个结点pre*/
        {
            /*插入新节点，并返回表头L*/
            tmp->Next = pre->Next;
            pre->Next = tmp;
            return L;
        }
    }
}

插入（有头结点）

bool Insert(List L, ElementType X, int i)
{
    /*这里假设L有头结点*/
    Position tmp, pre;
    int cnt=0;
    pre = L;
    while(pre&&cnt<i-1)
    {
        pre = pre->Next;
        cnt ++;
    }
    if(pre==NULL||cnt!=i-1)   /*所找的结点不在L中*/
    {
        printf("插入位置参数错误。\n");
        return false;
    }
    else   /*找到了待插入结点的前一个结点pre；若i=1，pre就指向表头*/
    {
        /*插入新节点*/
        tmp = (Position)malloc(sizeof(struct LNode)); /*申请、填装结点*/
        tmp->Data = X;
        tmp->Next = pre->Next;
        pre->Next = tmp;
        return true;
    }
}

删除（有头结点）

bool Delete(List L, int i)
{
    /*这里默认L有头结点*/
    Position tmp, pre;
    int cnt=0;
    /*查找位序为i-1的结点*/
    pre = L;   /*pre指向表头*/
    while(pre&&cnt<i-1)
    {
        pre = pre->Next;
        cnt++;
    }
    if(pre==NULL||cnt!=i-1||pre->Next==NULL)
    {
        /*pre不存在、cnt找不到i-1、要删除的结点不存在*/
        printf("删除位置参数错误。\n");
        return false;
    }
    else   /*找到了待删除结点的前一个结点*/
    {
        /*将结点删除*/
        tmp = pre->Next;
        pre->Next = tmp->Next;
        free(tmp);
        return true;
    }
}

总结：线性表的线性存储就是链表，对其进行操作时通常是先遍历链表，找到正确的位置之后进行操作，如果没找到就返回错误信息。

（一）链表

1.线性表的顺序存储

2.线性表的链式存储