线性表与链表复习

线性表的定义

struct Book {
    string id;//ISBN
    string name;//书名
    double price;//定价
};
typedef struct {
    Book *elem; //存储空间的基地址
    int length; //当前长度
} SqList;

线性表的初始化

Status InitList_Sq(SqList &L) { //算法2.1 顺序表的初始化
    //构造一个空的顺序表L
    L.elem = new Book[MAXSIZE]; //为顺序表分配一个大小为MAXSIZE的数组空间
    if (!L.elem)
        exit(OVERFLOW); //存储分配失败退出
    L.length = 0; //空表长度为0
    return OK;
}

线性表的查找

int LocateElem_Sq(SqList L, double e) { //算法2.3 顺序表的查找
    //顺序表的查找
    for (int i = 0; i < L.length; i++)
        if (L.elem[i].price == e)
            return i + 1;//查找成功，返回序号i+1
    return 0;//查找失败，返回0
}

线性表的插入

Status ListInsert_Sq(SqList &L, int i, Book e) { //算法2.4 顺序表的插入
    //在顺序表L中第i个位置之前插入新的元素e
    //i值的合法范围是1<=i<=L.length+1
    if ((i < 1) || (i > L.length + 1))
        return ERROR; //i值不合法
    if (L.length == MAXSIZE)
        return ERROR; //当前存储空间已满
    for (int j = L.length - 1; j >= i - 1; j--)
        L.elem[j + 1] = L.elem[j]; //插入位置及之后的元素后移
    L.elem[i - 1] = e; //将新元素e放入第i个位置
    ++L.length; //表长增1
    return OK;
}Status ListInsert_Sq(SqList &L, int i, Book e) { //算法2.4 顺序表的插入
    //在顺序表L中第i个位置之前插入新的元素e
    //i值的合法范围是1<=i<=L.length+1
    if ((i < 1) || (i > L.length + 1))
        return ERROR; //i值不合法
    if (L.length == MAXSIZE)
        return ERROR; //当前存储空间已满
    for (int j = L.length - 1; j >= i - 1; j--)
        L.elem[j + 1] = L.elem[j]; //插入位置及之后的元素后移
    L.elem[i - 1] = e; //将新元素e放入第i个位置
    ++L.length; //表长增1
    return OK;
}

线性表的删除

Status ListDelete_Sq(SqList &L, int i) { //算法2.5 顺序表的删除
    //在顺序表L中删除第i个元素，并用e返回其值
    //i值的合法范围是1<=i<=L.length
    if ((i < 1) || (i > L.length))
        return ERROR; //i值不合法
    for (int j = i; j <= L.length; j++)
        L.elem[j - 1] = L.elem[j]; //被删除元素之后的元素前移
    --L.length; //表长减1
    return OK;
}

链表的定义

struct Book {
    string id;//ISBN
    string name;//书名
    double price;//定价
};
typedef struct LNode {
    Book data; //结点的数据域
    struct LNode *next; //结点的指针域
} LNode, *LinkList; //LinkList为指向结构体LNode的指针类型

链表的初始化

Status InitList_L(LinkList &L) { //算法2.6 单链表的初始化
    //构造一个空的单链表L
    L = new LNode; //生成新结点作为头结点，用头指针L指向头结点
    L->next = NULL; //头结点的指针域置空
    return OK;
}

链表的查找

Status GetElem_L(LinkList L, int i, Book &e) { //算法2.7 单链表的取值
    //在带头结点的单链表L中查找第i个元素
    //用e返回L中第i个数据元素的值
    int j;
    LinkList p;
    p = L->next;
    j = 1; //初始化，p指向第一个结点，j为计数器
    while (j < i && p) { //顺链域向后扫描，直到p指向第i个元素或p为空
        p = p->next; //p指向下一个结点
        ++j; //计数器j相应加1
    }
    if (!p || j > i)
        return ERROR; //i值不合法i＞n或i<=0
    e = p->data; //取第i个结点的数据域
    return OK;
} //GetElem_L

链表的删除

Status ListDelete_L(LinkList &L, int i) { //算法2.9 单链表的删除
    //在带头结点的单链表L中，删除第i个位置    
    LinkList p, q;
    int j;
    p = L;
    j = 0;
    while ((p->next) && (j < i - 1)) //查找第i?1个结点，p指向该结点
    {
        p = p->next;
        ++j;
    }
    if (!(p->next) || (j > i - 1))
        return ERROR; //当i>n或i<1时，删除位置不合理 
    q = p->next; //临时保存被删结点的地址以备释放 
    p->next = q->next; //改变删除结点前驱结点的指针域 
    delete q; //释放删除结点的空间 
    --length;
    return OK;
} //ListDelete_L

链表的插入

Status ListInsert_L(LinkList &L, int i, Book &e) { //算法2.9 单链表的插入
    //在带头结点的单链表L中第i个位置插入值为e的新结点
    int j;
    LinkList p, s;
    p = L;
    j = 0;
    while (p && j < i - 1) {
        p = p->next;
        ++j;
    }//查找第i?1个结点，p指向该结点
    if (!p || j > i - 1)
        return ERROR; //i＞n+1或者i＜1
    s = new LNode; //生成新结点*s 
    s->data = e; //将结点*s的数据域置为e
    s->next = p->next; //将结点*s的指针域指向结点ai
    p->next = s; //将结点*p的指针域指向结点*s
    ++length;
    return OK;
}