定义和逻辑特征

物理特征

连续存储使用数组存储线性表的元素，即用一组连续的存储单元依次存储线性表的数据元素。
不连续存储是使用链表存储线性表的元素，即用一组任意的存储单元存储线性表的数据元素。

一般线性表

顺序表示与实现

C语言结构类型定义顺序表类型

 # define LIST_INIT_SIZE   100  //存储空间初始分配量
 # define LISTINCREMENT  10 //存储空间分配增量
 typedef  struct  {
     ElemType *elem;       //存储空间基址  
     int length;       //当前长度
     int listsize;  //当前分配的存储容量
       } SqList;

线性表的初始化

Status  InitList_Sq(SqList &L) {
    L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));� //构造一个空的线性表
    if (!L.elem) exit(OVERFLOW);    //存储分配失败�  
    L.length = 0;     //空表长度为0�   
    L.listsize = LIST_INIT_SIZE;   //初始存储容量�   
    return OK;
}  // InitList_Sq

插入

Status ListInsert_Sq(SqList &L, int i, ElemType e) {
    //在顺序线性表L中第i个位置前插入新的元素e
    // i的合法值为1≤i ≤ListLength_Sq(L)+1
    if (i<1 || i >L.length + 1)
        return ERROR; // i 值不合法 
    if (L.length >= L.listsize) { //当前存储空间已满，增加分配
        newbase = (ElemType *)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType);
        if (!newbase)   exit(OVERFLOW);  //存储分配失效
        L.elem = newbase;      // 新基址 L.listsize+=LISTINCREMENT;    // 增加存储容量
    }
    q = &(L.elem[i - 1]);   // q为插入位置
    for (p = &L.elem[L.length - 1]; p >= q; --p) *(p + 1) = *p;
    // 插入位置及之后元素右移    
    *p = e;  ++L.length;    //插入e，表长加1  
    return OK;
}   //ListInsert_Sq

删除

Status ListDelete_Sq(SqList &L, int i, ElemType &e) {
    //在顺序线性表L中删除第i个元素，并用e返回其值
    // i的合法值为1≤i ≤ListLength_Sq(L)
    if (i<1 || i >L.length)      return ERROR;  // i 值不合法
    p = &(L.elem[i - 1]);             //p为被删除元素的位置
    e = *p;       //被删除元素的值赋给e
    q = L.elem + L.length - 1;      //表尾元素的位置
    for (++p; p <= q; ++p)
        *(p - 1) = *p;     //被删除元素之后的元素左移
    --L.length;
    return OK;
}

链式表示与实现

链表节点结构

单链表是由头指针唯一确定，在单链表的第一个结点之前附加一个结点，称之为头结点，其数据域可以为空，指针域存储指向第一个结点的指针。
用C语言中的“结构指针”描述的单链表如下：

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

插入

单链表插入

Status  ListInsert_L(LinkList  &L, int i, ElemType e) {
    // 在带头结点的单链线性表L中的第i个位置之前插入元素e
    p = L; j = 0;            // 初始化，p指向L中的头结点,j为计数器    �        
    while (p && j < i - 1) {  //p指向插入位置之前的结点                            
        p = p->next; ++j;
    }                       //寻找第i-1个结点,p指向第i-1个结点�     
    if (!p || j > i - 1) return false;            //i大于表长+1或小于1�         
    s = (LinkList)malloc(sizeof(LNode));   //生成新结点
    s->data = e; s->next = p->next;         // 插入L中
    p->next = s;
    return OK;
}

删除

单链表删除

ElemType  ListDelete_L(LinkList  &L, int i, ElemType &e) {
    // 在带头结点的单链线性表L中,删除第i个元素，并由e返回其值
    p = L; j = 0;            // 初始化，p指向L中的头结点,j 为计数器   �         
    while (p->next && j < i - 1) {//寻找第i个结点，并令p指向其前驱�              
        p = p->next; ++j;  // p指向被删除结点的前一个结点，所以
                   //  p->next不能为空，否则i值错误
    } �     if (!(p->next) || j > i - 1) return NULL;    //删除位置不合理�         
    q = p->next;  p->next = q->next;   //删除并释放结点
    e = q->data; free(q);
    return OK;
}  // ListDelete_L