程序编制 第2章 线性表.pptVIP

2.1 线性表的类型定义 线性表由一组具有相同属性的数据元素构成。数据元素的含义广泛，在不同的具体情况下，可以有不同的含义。例如：英文字母表（A，B，C，…，Z）是一个长度为26的线性表，其中的每一个字母就是一个数据元素；再如，某公司2000年每月产值表（400，420，500，…，600，650）(单位：万元)是一个长度为12的线性表，其中的每一个数值就是一个数据元素。上述两例中的每一个数据元素都是不可分割的，在一些复杂的线性表中，每一个数据元素又可以由若干个数据项组成，在这种情况下，通常将数据元素称为记录（record），例如，下图的某单位职工工资表就是一个线性表，表中每一个职工的工资就是一个记录，每个记录包含八个数据项：职工号、姓名、基本工资……。 矩阵也是一个线性表，但它是一个比较复杂的线性表。在矩阵中，我们可以把每行看成是一个数据元素，也可以把每列看成是一个数据元素，而其中的每一个数据元素又是一个线性表。 综上所述，一个线性表是n≥0个数据元素a0，a1，a2，…，an-1的有限序列。如果n0，则除a0和an-1外，有且仅有一个直接前趋和一个直接后继数据元素，ai（0≤i≤n-1）为线性表的第i个数据元素，它在数据元素ai-1之后，在ai+1之前。a0为线性表的第一个数据元素，而an-1是线性表的最后一个数据元素；若n=0，则为一个空表，表示无数据元素。因此，线性表或者是一个空表（n=0），或者可以写成：（a0，a1，a2，…， ai-1，ai，ai+1，…，an-1）。 本章小结 在单链表中删除第 i 个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。 ai-1 ai ai+1 ai-1 q = p-next; p-next = q-next; e = q-data; free(q); p q Status ListDelete_L(LinkList L, int i, ElemType e) { // 删除以 L 为头指针(带头结点)的单链表中第 i 个结点 } // ListDelete_L 算法2.10 算法的时间复杂度为: O(ListLength(L)) p = L; j = 0; while (p-next j i-1) { p = p-next; ++j; } // 寻找第 i 个结点，并令 p 指向其前趋 if (!(p-next) || j i-1) return ERROR; // 删除位置不合理 q = p-next; p-next = q-next; // 删除并释放结点 e = q-data; free(q); return OK; 如何从线性表得到单链表？ 链表是一个动态的结构，它不需要予分配空间，因此生成链表的过程是一个结点“逐个插入” 的过程。 例如：逆位序输入 n 个数据元素的值， 建立带头结点的单链表。 操作步骤： 一、建立一个“空表”； 二、输入数据元素an， 建立结点并插入； 三、输入数据元素an-1， 建立结点并插入； an an an-1 四、依次类推，直至输入a1为止。 void CreateList_L(LinkList L, int n) { // 逆序输入 n 个数据元素，建立带头结点的单链表 } // CreateList_L 算法的时间复杂度为: O(Listlength(L)) L = (LinkList) malloc (sizeof (LNode)); L-next = NULL; // 先建立一个带头结点的单链表 for (i = n; i 0; --i) { p = (LinkList) malloc (sizeof (LNode)); scanf(p-data); // 输入元素值 p-next = L-next; L-next = p; // 插入 } 回顾 2.1 节中三个例子的算法，看一下当线性表分别以顺序存储结构和链表存储结构实现时，它们的时间复杂度为多少？ void union(List La, List Lb) { La_len = ListLength(La); Lb_len =ListLength(Lb); for (i = 1; i = Lb_len; i++) { GetElem(Lb, i, e); if (!LocateElem(La, e, equal( )) ListInsert(La,