chapter_2 线性表

线性表是一个具有相同特性的数据元素的有限序列。

相同特性：所有元素属于同一数据类型。
有限：数据元素个数是有限的。
序列：数据元素由逻辑序号唯一确定。一个线性表中可以有相同值的元素。

线性表中所含元素的个数叫做线性表的长度，用n表示，n≥0。
n=0时，表示线性表是一个空表，即表中不包含任何元素。

线性表的逻辑表示为：(a1，a2，…，ai，ai+1，…，an)
ai（1≤i≤n）表示第i（i表示逻辑位序）个元素。
a1为表头元素, an为表尾元素

线性表的运算

初始化线性表InitList(&L)：构造一个空的线性表L。
销毁线性表DestroyList(&L)：释放线性表L占用的内存空间。
判线性表是否为空表ListEmpty(L)：若L为空表，则返回真，否则返回假。
求线性表的长度ListLength(L)：返回L中元素个数n。
输出线性表DispList(L)：线性表L不为空时，顺序显示L中各结点的值域。
求线性表L中指定位置的某个数据元素GetElem(L，i，&e)：用e返回L中第 i（1≤i≤n）个元素的值。
定位查找LocateElem(L，e)：返回L中第一个值域与e相等的逻辑位序。若这样的元素不存在，则返回值为0。
插入一个数据元素ListInsert(&L，i，e)：在L的第i（1≤i≤n）个元素之前插入新的元素e，L的长度增1。
删除数据元素ListDelete(&L，i，&e)：删除L的第i（1≤i≤n）个元素，并用e返回其值，L的长度减1。

2. 线性表的顺序存储—顺序表

线性表的顺序存储结构：把线性表中的所有元素按照顺序存储方法进行存储。
按逻辑顺序依次存储到存储器中一片连续的存储空间中。

#include 
#include 
#define bool int
#define true 1
#define false 0
#define ElemType char
#define MaxSize 10001

typedef struct {
    ElemType data[MaxSize];
    int length;
} SqList;

//整体建立顺序表
void CreateList(SqList *&L, ElemType a[], int n) {
    int i = 0, k = 0;
    L = (SqList *)malloc(sizeof(SqList));
    while (i < n) {
        // i扫描a中元素
        L->data[k] = a[i];
        k++;
        i++; // k记录插入到L中的元素个数
    }
    L->length = k;
}

//（1）初始化线性表InitList(L)
void InitList(SqList *&L) {
    L = (SqList *)malloc(sizeof(SqList));
    L->length = 0;
}

//（2）销毁线性表DestroyList(L)
void DestroyList(SqList *&L) {
    free(L);
}

//（3）判定是否为空表ListEmpty(L)
bool ListEmpty(SqList *L) {
    return (L->length == 0);
}

//（4）求线性表的长度ListLength(L)
int ListLength(SqList *L) {
    return (L->length);
}

//（5）输出线性表DispList(L)
void DispList(SqList *L) {
    int i;
    if (ListEmpty(L))
        return;
    printf("length: %d\n", L->length);
    printf("data: ");
    for (i = 0; i < L->length; i++)
        printf("%c", L->data[i]);
    printf("\n");
}

//（6）求线性表L中指定位置的某个数据元素GetElem(L,i,&e)
bool GetElem(SqList *L, int i, ElemType &e) {
    if (i < 1 || i > L->length)
        return false;
    e = L->data[i - 1];
    return true;
}

//（7）按元素值查找LocateElem(L,e)
int LocateElem(SqList *L, ElemType e) {
    int i = 0;
    while (i < L->length && L->data[i] != e)
        i++;
    if (i >= L->length)
        return 0;
    else
        return i + 1;
}

//（8）插入数据元素ListInsert(L,i,e)
bool ListInsert(SqList *&L, int i, ElemType e) {
    int j;
    if (i < 1 || i > L->length + 1)
        return false;               //参数错误时返回false
    i--;                            //将顺序表逻辑序号转化为物理序号
    for (j = L->length; j > i; j--) //将data[i..n]元素后移一个位置
        L->data[j] = L->data[j - 1];
    L->data[i] = e; //插入元素e
    L->length++;    //顺序表长度增1
    return true;    //成功插入返回true
}

//（9）删除数据元素ListDelete(&L,i,&e)
bool ListDelete(SqList *&L, int i, ElemType &e) {
    int j;
    if (i < 1 || i > L->length) //参数错误时返回false
        return false;
    i--; //将顺序表逻辑序号转化为物理序号
    e = L->data[i];
    for (j = i; j < L->length - 1; j++) //将data[i..n-1]元素前移
        L->data[j] = L->data[j + 1];
    L->length--; //顺序表长度减1
    return true; //成功删除返回true
}

int main() {
    char a[] = "abcdef";
    int n = sizeof(a) / sizeof(a[0]) - 1; // '\0'

    SqList *L;
    CreateList(L, a, n);
    DispList(L);

    char e;
    GetElem(L, 1, e);
    printf("e = %c\n", e);

    int index = LocateElem(L, e);
    printf("index = %d\n", index);

    ListInsert(L, 1, e);
    DispList(L);

    ListDelete(L, 1, e);
    printf("e = %c\n", e);
    DispList(L);
    return 0;
}

【例】已知长度为n的线性表L采用顺序存储结构。
设计一个时间复杂度为O(n)、空间复杂度为O(1) 的算法，
该算法删除线性表中所有值为x的数据元素。

解法一（重建法）：设删除L中所有值等于x元素后的顺序表为L1，
显然L1包含在L中，为此L1重用L的空间。

思路：扫描顺序表L，重建L只包含不等于x的元素。

void delnode1(SqList *&L, ElemType x) {
    int k = 0, i; // k记录值不等于x的元素个数
    for (i = 0; i < L->length; i++)
        if (L->data[i] != x) {
            //若当前元素不为x,将其插入A中
            L->data[k] = L->data[i];
            k++; //不等于x的元素增1
        }
    L->length = k; //顺序表L的长度等于k
}

解法二（前移法）：用k记录顺序表L中等于x的元素个数,一边扫描L一边统计k值。

思路：将不为x的元素前移k个位置,最后修改L的长度。

delnode2(SqList *&L,ElemType x) {
    int k = 0, i = 0; // k记录值等于x的元素个数
    while (i < L->length) {
        if (L->data[i] == x) //当前元素值为x时k增1
            k++;
        else //当前元素不为x时将其前移k个位置
            L->data[i - k] = L->data[i];
        i++;
    }
    L->length -= k; //顺序表L的长度递减k
}

解法三（区间划分法）

    int i = -1,j = 0;
    while (j < L->length) {
        // j扫描所有元素
        if (L->data[j] != x) {
            //找到不为x的元素
            i++; //扩大不为x的区间
            if (i != j)
                swap(L->data[i] ,L->data[j]);
        }
        j++; //继续扫描
    }
    L->length = i + 1; //设置L中实际元素个数
}

【例】设顺序表L有10个整数。 设计一个算法,以第一个元素为分界线（基准）,
将所有小于等于它的元素移到该元素的前面,
将所有大于它的元素移到该元素的后面。

解法1（前后交换法）：

move1(SqList *&L) {
    int i = 0, j = L->length - 1;
    ElemType tmp;
    ElemType pivot = L->data[0]; //以data[0]为基准
    while (i < j) {
        while (i < j && L->data[j] > pivot)
            j--; //从后向前扫描,找一个≤pivot的元素
        while (i < j && L->data[i] <= pivot)
            i++; //从前向后扫描,找一个>pivot的元素
        if (i < j) {
            tmp = L->data[i]; // L->data[i] ? L->data[j]
            L->data[i] = L->data[j];
            L->data[j] = tmp;
        }
    }
    tmp = L->data[0]; // L->data[0] ? L->data[j]
    L->data[0] = L->data[j];
    L->data[j] = tmp;
}

解法2 （前后交换法） ：

move2(SqList *&L) {
    int i = 0,j = L->length - 1;
    ElemType pivot = L->data[0]; //以data[0]为基准
    while (i < j) {
        while (j > i && L->data[j] > pivot)
            j--;                 //从右向左扫描,找≤pivot的data[j]
        L->data[i] = L->data[j]; //将其放入data[i]处
        while (i < j && L->data[i] <= pivot)
            i++;                 //从左向右扫描,找>pivot的记录data[i]
        L->data[j] = L->data[i]; //将其放入data[j]处
    }
    L->data[i] = pivot; //放置基准
}

3. 线性表的链式存储—链表

线性表中每个结点有唯一的前驱结点和前驱结点。
设计链式存储结构时，每个逻辑结点存储单独存储，为了表示逻辑关系，增加指针域。
每个物理结点增加一个指向后继结点的指针域 -> 单链表。
每个物理结点增加一个指向后继结点的指针域和一个指向前驱结点的指针域 -> 双链表。
第一个结点的操作和表中其他结点的操作相一致，无需进行特殊处理；
无论链表是否为空，都有一个头结点，因此空表和非空表的处理也就统一了。

#include 
#include 
#define ElemType char
#define MaxSize 10001

typedef struct LNode {
    ElemType data;
    struct LNode *next; //指向后继结点
} LinkNode;             //定义单链表结点类型

//（1）头插法建表
void CreateListF(LinkNode *&L, ElemType a[], int n) {
    LinkNode *s;
    int i;
    L = (LinkNode *)malloc(sizeof(LinkNode));
    L->next = NULL; //创建头结点,其next域置为NULL
    for (i = 0; i < n; i++) {
        //循环建立数据结点
        s = (LinkNode *)malloc(sizeof(LinkNode));
        s->data = a[i];    //创建数据结点s
        s->next = L->next; //将s插在原开始结点之前,头结点之后
        L->next = s;
    }
}
//（2）尾插法建表
void CreateListR(LinkNode *&L, ElemType a[], int n) {
    LinkNode *s, *r;
    int i;
    L = (LinkNode *)malloc(sizeof(LinkNode)); //创建头结点
    r = L;                                    // r始终指向尾结点,开始时指向头结点
    for (i = 0; i < n; i++) {
        //循环建立数据结点
        s = (LinkNode *)malloc(sizeof(LinkNode));
        s->data = a[i]; //创建数据结点s
        r->next = s;    //将s插入r之后
        r = s;
    }
    r->next = NULL; //尾结点next域置为NULL
}

//（1）初始化线性表InitList(L)
void InitList(LinkNode *&L) {
    L = (LinkNode *)malloc(sizeof(LinkNode)); //创建头结点
    L->next = NULL;
}

//（2）销毁线性表DestroyList(L)
void DestroyList(LinkNode *&L) {
    LinkNode *pre = L, *p = L->next; // pre指向p的前驱结点
    while (p != NULL) {
        //扫描单链表L
        free(pre); //释放pre结点
        pre = p;   // pre、p同步后移一个结点
        p = pre->next;
    }
    free(pre); //循环结束时,p为NULL,pre指向尾结点,释放它
}

//（3）判线性表是否为空表ListEmpty(L)
bool ListEmpty(LinkNode *L) {
    return (L->next == NULL);
}

//（4）求线性表的长度ListLength(L)
int ListLength(LinkNode *L) {
    int n = 0;
    LinkNode *p = L; // p指向头结点,n置为0（即头结点的序号为0）
    while (p->next != NULL) {
        n++;
        p = p->next;
    }
    return (n); //循环结束,p指向尾结点,其序号n为结点个数
}

//（5）输出线性表DispList(L)
void DispList(LinkNode *L) {
    LinkNode *p = L->next; // p指向开始结点
    printf("data: ");
    while (p != NULL) {
        // p不为NULL,输出p结点的data域
        printf("%c ", p->data);
        p = p->next; // p移向下一个结点
    }
    printf("\n");
}

//（6）求线性表L中位置i的数据元素GetElem(L，i，&e)
bool GetElem(LinkNode *L, int i, ElemType &e) {
    int j = 0;
    LinkNode *p = L; // p指向头结点,j置为0（即头结点的序号为0）
    while (j < i && p != NULL) {
        j++;
        p = p->next;
    }
    if (p == NULL)
        return false; //不存在第i个数据结点,返回false
    else {
        //存在第i个数据结点,返回true
        e = p->data;
        return true;
    }
}

//（7）按元素值查找LocateElem(L，e)
int LocateElem(LinkNode *L, ElemType e) {
    int i = 1;
    LinkNode *p = L->next; // p指向开始结点,i置为1
    while (p != NULL && p->data != e) {
        p = p->next; //查找data值为e的结点,其序号为i
        i++;
    }
    if (p == NULL)
        return (0); //不存在元素值为e的结点,返回0
    else
        return (i); //存在元素值为e的结点,返回其逻辑序号i
}

//（8）插入数据元素ListInsert(&L，i，e)
bool ListInsert(LinkNode *&L, int i, ElemType e) {
    int j = 0;
    LinkNode *p = L, *s; // p指向头结点,j置为0
    while (j < i - 1 && p != NULL) {
        j++;
        p = p->next;
    }
    if (p == NULL)
        return false; //未找到第i-1个结点,返回false
    else {
        //找到第i-1个结点p,插入新结点并返回true
        s = (LinkNode *)malloc(sizeof(LinkNode));
        s->data = e;       //创建新结点s,其data域置为e
        s->next = p->next; //将s插入到p之后
        p->next = s;
        return true;
    }
}

//（9）删除数据元素ListDelete(&L，i，&e)
bool ListDelete(LinkNode *&L, int i, ElemType &e) {
    int j = 0;
    LinkNode *p = L, *q; // p指向头结点,j置为0
    while (j < i - 1 && p != NULL) {
        //查找第i-1个结点
        j++;
        p = p->next;
    }
    if (p == NULL)
        return false; //未找到第i-1个结点,返回false
    else {
        //找到第i-1个结点p
        q = p->next; // q指向第i个结点
        if (q == NULL)
            e = q->data;   //若不存在第i个结点,返回false
        p->next = q->next; //从单链表中删除q结点
        free(q);           //释放q结点
        return true;       //返回true表示成功删除第i个结点
    }
}

int main() {
    char a[] = "abcdef";
    int n = sizeof(a) / sizeof(a[0]) - 1; // '\0'

    LinkNode *L;
    CreateListF(L, a, n);
    DispList(L);

    CreateListR(L, a, n);
    DispList(L);

    char e;
    GetElem(L, 1, e);
    printf("e = %c\n", e);

    int index = LocateElem(L, e);
    printf("index = %d\n", index);

    ListInsert(L, 1, e);
    DispList(L);

    ListDelete(L, 3, e);
    DispList(L);
    return 0;
}

【例】设计一个算法,删除一个单链表L中元素值最大的结点（假设最大值结点是唯一的）。

void delmaxnode(LinkNode *&L) {
    LinkNode *p = L->next, *pre = L, *maxp = p, *maxpre = pre;
    while (p != NULL) {
        if (maxp->data < p->data) { //若找到一个更大的结点
            maxp = p;     //更改maxp
            maxpre = pre; //更改maxpre
        }
        pre = p; // p、pre同步后移一个结点
        p = p->next;
    }
    maxpre->next = maxp->next; //删除maxp结点
    free(maxp);                //释放maxp结点
}

【例】有一个带头结点的单链表L（至少有一个数据结点）,
设计一个算法使其元素递增有序排列。

void sort(LinkNode *&L) {
    LinkNode *p, *pre, *q;
    p = L->next->next;    // p指向L的第2个数据结点
    L->next->next = NULL; //构造只含一个数据结点的有序表
    while (p != NULL) {
        q = p->next;      // q保存p结点后继结点的指针
        pre = L; //从有序表开头进行比较,pre指向插入p的前驱结点
        while (pre->next != NULL && pre->next->data < p->data)
            pre = pre->next; //在有序表中找插入p的前驱结点pre

        p->next = pre->next;
        pre->next = p;
        p = q; //扫描原单链表余下的结点
    }
}

【例】 假设有一个带头结点的单链表：L = (a1,a2,…,an)。
设计一个算法将所有结点逆置,即：L = (an,an - 1,…,a1)

void Reverse(LinkNode * &L) {
    LinkNode *p = L->next, * q;
    L->next = NULL;
    while (p != NULL) {
        q = p->next;       //临时保存p的后继结点
        p->next = L->next; //将p结点采用头插法连接
        L->next = p;
        p = q;
    }
}

【例】假设有一个带头结点的单链表 L = (a1,b1,a2,b2,…,an,bn)。
设计一个算法将其拆分成两个带头结点的单链表L1和L2：
L1 = (a1,a2,…,an), L2 = (bn,bn - 1,…,b1)
要求L1使用L的头结点。

解：利用原单链表L中的所有结点通过改变指针域重组成单链表L1和L2。
由于L1中结点的相对顺序与L中的相同,所以采用尾插法建立单链表L1；
由于L2中结点的相对顺序与L中的相反,所以采用头插法建立单链表L2。

void split(LinkNode * &L,LinkNode * &L1,LinkNode * &L2) {
    LinkNode *p = L->next, * q, * r1;        // p指向第1个数据结点
    L1 = L;                                    // L1利用原来L的头结点
    r1 = L1;                                   // r1始终指向L1的尾结点
    L2 = (LinkNode *)malloc(sizeof(LinkNode)); //创建L2的头结点
    L2->next = NULL;                           //置L2的指针域为NULL
    while (p != NULL) {
        r1->next = p; //采用尾插法将p(data值为ai)插入L1中
        r1 = p;
        p = p->next;        // p移向下一个结点(data值为bi)
        q = p->next;        //用q保存p的后继结点
        p->next = L2->next; //采用头插法将p插入L2中
        L2->next = p;
        p = q; // p重新指向ai+1的结点
    }
    r1->next = NULL; //尾结点next置空
}