线性表--链式实现方式

链式方式的线性表。

在实现之前首先需要对其线性表的链式方式的特点做一个了解：

通俗的讲链式线性表就是元素之间逻辑相邻但是物理位置不一定相邻，那么既然物理位置不相邻

又是如何来体现其逻辑位置的呢？其逻辑关系是上一个元素来维护的。链式线性表的每个元素是

保存在结点中的，结点就是一块内存区域。它包含两个区域数据域、指针域。数据域保存元素值

指针域保存下一个结点指向性。

具体如何呢？看看结点数据结构吧：

[cpp] v
typedef struct LNode
{
ElemType data;//节点数据信息域
struct LNode * next;//指向下一个节点的指针
}LNode ,*LinkList;

typedef struct LNode
{
ElemType data;//节点数据信息域
struct LNode * next;//指向下一个节点的指针
}LNode ,*LinkList;
之后我们来看看其具体的实现和操作，在对链式线性表做一个总结

[cpp]
/**
Author Kiritor
线性表的链式实现*/
#include "stdafx.h"
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<malloc.h>
#define OK 1
#define OVERFLOW -1
#define ERROR -1
#define TRUE 1
#define FALSE 0
#define ElemType int
//线性表的单链表存储结构
typedef struct LNode
{
    ElemType data;//节点数据信息域
    struct LNode * next;//指向下一个节点的指针
}LNode ,*LinkList;

//初始化单链表
int init_List(LinkList &l)
{
    printf("初始化线性表\n");
    //产生一个头结点，并且使L指向头结点
    l = (LinkList)malloc(sizeof(LNode));
    if(!l)
        exit(OVERFLOW);//分配空间失败
    l->next=NULL;//头结点的指针域为空表示无元素
    l->data= 0;//头结点数据域用于表示链表的长度
    return OK;
}

//销毁链式单向线性表
void destory_List(LinkList &l)
{
    printf("销毁线性表");
    LinkList q ;
    /*循环的释放每一个结点的内存空间*/
    while(l)
    {
        q=l->next;
        free(l);
        l=q;
    }
}

//将线性表重新置为空表，并非销毁
int clear_List(LinkList &l)
{
    printf("清空线性表，并非销毁\n");
    LinkList p,q;
    p=l->next;//p指向第一个结点
    while(p)
    {
        q= p->next;
        free(p);
        p=q;
    }
    //之后将头指针域的指向性设置为空
    l->next = NULL;
    l->data=0;
    return OK;
}
//线性表插入(带头结点的)
//在第i个位置之前插入e，i值从1开始
int insert_List(LinkList &l,int i,ElemType e)
{
    printf("在第%d个位置插入%d\n",i,e);
    //首先寻找第i个结点
    LinkList q = l,s;
    int j=0;//用于循环的计数器
    while(q&&j<i-1)
    {
        q = q->next;
        j++;
    }
    if(!q||j>i-1)
    {
        return ERROR;
    }
    s=(LinkList)malloc(sizeof(LNode));//生成一个新的结点
    s->data=e;
    s->next=q->next;
    q->next =s;
    l->data++;//线性表的长度加1
    return OK;
}

/*取得线性表的i位置的元素，存在返回ok，并将之存在e中
反之返回ERROR，需要注意的是l是带头结点的单链表
*/
int getElem(LinkList l,int i,ElemType &e)
{
    LNode * p = l->next ;
    int count = 1;
    //初始化，使p指向第一个结点，count为计数器
    while(p&&count < i)
    {
        p = p ->next ;
        count++;
    }
    //p指针移动到要取得的元素位置的结点处
    if(!p||count >i)
        return ERROR;
    e=p->data;
    return e;
}
/*判断线性表是否为空*/
int isEmpty(LinkList &l)
{
     if(l->data==0)
         return FALSE;
     else
         return TRUE;

}
/*删除线性表中的某个位置元素
i是从1开始的**/
int delete_LinkList(LinkList &l,int i)
{
    printf("删除线性表%d位置的元素\n",i);
    int j=0;
    LinkList p = l;
    //首先找到要删除的元素的位置
    while (p->next&&i>=1&&j<i-1)
    {
        p=p->next;
        j++;
    }
    if(!p->next||j>i-1)
        return ERROR;//删除的位置不合理
    LinkList q = p->next;
    p->next = q->next;
    free(q);
    l->data--;
    return OK;
}&

补充：软件开发 , C++ ,