类型定义

是一种最简单的线性结构，是一个数据元素的有序集。

两种表示方式

顺序表示

结构体定义：

#define  LIST_INIT_SIZE     80  
        // 线性表存储空间的初始分配量
#define  LISTINCREMENT    10 
        // 线性表存储空间的分配增量
        
typedef  struct {
    ElemType *elem;// 存储空间基址
	int length;    // 当前长度
	int listsize;  // 当前分配的存储容量  
                   // (以sizeof(ElemType)为单位)
} SqList;  // 俗称 顺序表

结构初始化函数：

Status InitList_Sq( SqList& L ) {
    // 构造一个空的线性表 
    L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));
    if(!L.elem) exit(OVERFLOW);
    L.length = 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≤L.length+1
    
    //插入位置不合法
    if(i > L.length + 1 || i < 1) return ERROR;
    
    //存储空间已满，重新分配
    if(L.length + 1 >= L.listsize){
        L.elem = (ElemType*)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType));
        L.listsize += LISTINCREMENT;
    }
    
	q = &(L.elem[i - 1]);
    for(p = &(L.elem[L.length - 1]); p >= q; --p)
        *(p + 1) = *p;
    *q = e;
    L.length ++;
    return OK;
} // ListInsert_Sq

删除元素：

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

查找：

int LocateElem_Sq(SqList L, ElemType e,Status (*compare)(ElemType, ElemType)){
    // 在顺序表中查询第一个满足判定条件的数据元素，
    // 若存在，则返回它的位序，否则返回 0
    int ans = 1;
    p = L.elem;
    while(i <= L.length && !(*compare)(*p++, e)) ++ i;
    if(i <= L.length) return i;
    else return 0;
} // LocateElem_Sq

链式表示

线性链表（单链表）

每个结点中只包含一个指针域

结构体定义：

typedef struct  LNode {
    ElemType data;  // 数据域
    struct Lnode *next;  // 指针域
} LNode, *LinkList;

取第 i 个元素：

Status GetElem_L(LinkList L, int i, ElemType &e) {
    // L是带头结点的链表的头指针，以 e 返回第 i 个元素
    p = L->next;
    int j = 1;
    while(j != i && p){
        p = p->next;
        j ++;
    }
    if(j > i || !p) return ERROR;
    e = p->data;
    return OK;
} // GetElem_L

在指定位置 i 插入元素：

Status ListInsert_L(LinkList L, int i, ElemType e) {
	// L 为带头结点的单链表的头指针，本算法
    // 在链表中第i 个结点之前插入新的元素 e
    p = L->next;
    int j = 1;
    while(p && j != i - 1){
        p = p->next;
        j ++;
    }
    if(!p || j > i - 1) return ERROR;
    
    //这里有个问题！！！！！！！！！！！！！！！！！！！！！！
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
} // LinstInsert_L

删除指定位置 i 的元素：

Status ListDelete_L(LinkList L, int i, ElemType &e) {
    // 删除以 L 为头指针(带头结点)的单链表中第 i 个结点
    p = L->next;
    int j = 1;
    while(p && j != i - 1){
        p = p->next;
        j ++;
    }
    if(!p || j > i - 1) return ERROR;
    
    q = p->next;
    e = q->data;
    p->next = q->next;
    free(q);     //记得释放结点！！！
    return OK;
} // ListDelete_L

将链表置为空：

void ClearList(&L) {
	// 将单链表重新置为一个空表
    
    //这里有问题！！！！！！！！！！！！！！！！记得问.和->
    p = L->next;
    while(p){
        L->next = p->next;
        free(p);
        p = L->next;
    }
} // ClearList

循环链表

最后一个结点的指针指向头结点

判断链表是否是最后一个结点：后继是否为头结点。

双向链表

typedef struct  DuLNode {
    ElemType data;        // 数据域
    struct DuLNode *prior;// 指向前驱的指针域
    struct DuLNode *next; // 指向后继的指针域
} DuLNode, *DuLinkList;

示意图：

双向链表结构图示

在指定位置 i 插入元素：

Status ListInsert_ DuL (DuLinkList &L, int i, ElemType e) {
	//在带头结点的双链循环线性表L中第i个位置之前插入  
    //元素e，i的合法值为1≤i≤表长+1. 
    p = L->next;
    int j = 1;
    while(p && j < i - 1){
        p = p->next;
        j ++;
    }
    if(j >= i - 1 || !p) return ERROR;
    s = (DuLinkList) malloc(sizeof(DuLNode));
    s->data=e;
    s->prior=p->prior; 
    p->prior->next=s;
    s->next=p;           
    p->prior=s;
    return OK;
}// ListInsert_ DuL

删除指定位置 i 的元素：

Status ListDelete_ DuL (DuLinkList &L, int i, ElemType &e) {      
    //删除带头结点的双链循环线性表L中第i个
    //元素，i的合法值为1≤i≤表长
    p = L->next;
    int j = 1;
    while(p && j < i - 1){
        j ++;
        p = p->next;
    }
    if(p || j >= i - 1) return ERROR;
    
    s = p->next;
    p->next = s->next;
    s->next->prior = p;
    e = s->data;
    free(s);
}// ListDelete_ DuL

对链表进行改进

1．增加“表长”、“表尾指针” 和 “当前位置的指针” 三个数据域；

2．将基本操作中的“位序 i ”改变为“指针 p ”。

typedef struct LNode { // 结点类型
	ElemType data;
    struct LNode *next;
} *Link, *Position;

typedef struct {     // 链表类型
	Link head, tail; // 分别指向头结点和最后一个结点的指针
    int len;         // 指示链表长度
    Link current;    // 指向当前被访问的结点的指针，初始位置指向头结点
}LinkList;