数据结构-线性表

线性表的链式表示与基本操作

1.初始化

初始化带头结点的单链表

int InitLinkList(LinkList &L)
{
    L=(LinkList)malloc(sizeof(LNode));//为头结点分配空间
    if(L!=NULL)
    {
        L->next=NULL;//初始化next指针为NULL
        return OK;
    }
    else
    {
        return ERROR;//分配空间失败，返回ERROR
    }
}

2.采用头插法建立单链表

特点：每次在头结点后插入新结点

LinkList CreatList1(LinkList &L){
    LNode *node;int x=0;
    if(!L)
        InitLinkList(L);
    scanf("%d",&x);
    while(x!=9999){
        node=(LNode *)malloc(sizeof(LNode));
        node->data=x;
        node->next=L->next;
        L->next=node;
        scanf("%d",&x);
    }
    return L;
}

3.采用尾插法建立单链表

LinkList CreatList2(LinkList &L){
    LNode *node;int x;LNode *r=L;
    if(!L)
        InitLinkList(L);
    scanf("%d",&x);
    while(x!=9999){
        node=(LNode *)malloc(sizeof(LNode));
        node->data=x;
        r->next=node;
        r=node;
        scanf("%d",&x);
    }
    r->next=NULL;
    return L;
}

4.按序号查找结点值

从第一个结点出发，顺着next指针逐个往后搜索，直到找到第i个结点，返回该结点，若不存在，则返回NULL

LinkList GetElem(LinkList L,int i){
    int j=1;//j为计数变量
    LNode *p=L->next;
    if(i==0)
        return L;//若i==0，返回头结点
    if(i<1)
        return NULL;//i值无效，返回NULL
    while(p&&j<i){
        p=p->next;
        j++;
    }
    return p;
}

5.按值查找结点值

从第一个结点出发，顺着next指针逐个往后搜索，直到找到结点值等于e的结点，返回该结点，若不存在，则返回NULL

LinkList LocateElem(LinkList L,ElemType e){
    LNode *p=L->next;
    while(p&&p->data!=e){
        p=p->next;
    }
    return p;
}

6.插入结点操作

目标：将值为x的新结点插入到单链表的第i个位置上

LinkList insertforlist(LinkList &L,int x,int i){
    LNode *p=GetElem(L,i-1);LNode *node;//调用GetElem函数
    node=(LNode *)malloc(sizeof(LNode));
    node->data=x;
    node->next=p->next;
    p->next=node;
    return node;
}

7.删除结点操作

目标：将单链表的第i个位置上结点删除

LinkList DeleteElem(LinkList &L,int i){
LNode * p=GetElem(L,i-1);LNode *q;
    q=p->next;
    p->next=q->next;
    free(q);
}

8.求单链表长度

目标：统计单链表的长度（即包含多少节点）

int ListLength_L(LinkList L){
    //返回L中数据元素个数
    LNode *p;int i=0;
    p=L->next;//p指向第一个结点，因为不包含头结点
    while(p){//遍历单链表，统计节点数
        i++;
        p=p->next;
    }
    return i;
}

未完待续。。