数据结构线性表1.ppt

数据结构DATA STRUCTURE;第二章 线性表;0;2.1 线性表的逻辑结构 定义：一个线性表是n个数据元素的有限序列;特征： 元素个数n—表长度，n=0空表 1in时 ai的直接前驱是ai-1，a1无直接前驱 ai的直接后继是ai+1，an无直接后继 元素同构，字符、数据、复合数据，且不能出现缺项 相邻的元素存在序偶关系 a0, a1, a2, …, an-2, an-1 ;线性表的抽象数据类型定义;线性表的抽象数据类型定义(续);集合合并;int ElemEqual(ElemType ea, ElemType eb) { if (ea == eb) return 0; else if (ea eb) return 1; else return -1; } void union_list(List *La, List *Lb) { int la_len = ListLength(La); // M int lb_len = ListLength(Lb); // N for (int i=0; ilb_len; i++) { // O(N×M) ElemType e; GetElem(Lb, i, e); if (LocateElem(La, e, ElemEqual) 0) // O(M/2) ListInsert(La, La_len++, e); } };;void Mergelist(List *La, List *Lb, List *Lc) { int la_len = ListLength(La); int lb_len = ListLength(Lb); InitList(Lc); int i=0, j=0, k=0; ElemType ea, eb; while (ila_len jlb_len) { GetElem(La, i, ea); GetElem(Lb, j, eb); if (compare(ea, eb) 0) {ListInsert(Lc, k++, ea); i++;} else {ListInsert(Lc, k++, eb); j++;} } while (i la_len) {GetElem(La, i++, ea); ListInsert(Lc, k++, ea);} while (j lb_len) {GetElem(Lb, i++, eb); ListInsert(Lc, k++, eb);} };2.2 线性表的物理存储结构;2.2.1 线性表的顺序存储结构 顺序表： 定义：用一组地址连续的存储单元存放一个线性表叫~ 元素地址计算方法： LOC(ai)=LOC(a1)+(i-1)*L LOC(ai+1)=LOC(ai)+L 其中： L—一个元素占用的存储单元个数 LOC(ai)—线性表第i个元素的地址 实现：可用C语言的一维数组实现 ;特点： 实现逻辑上相邻—物理地址相邻 实现随机存取 任意时刻存取任意数据单元的时间相同 不需要额外的空间 元素批量移动麻烦 插入 a0, a1, …, ai-1, b, ai, …, an-1 删除a0, a1, …, ai-1, ai, ai+1, …, an-1 ;;插入 定义：线性表的插入是指在第I（1?i ? n+1）个元素之前插入一个新的数据元素x，使长度为n的线性表;顺序表的插入;顺序表的错误插法;// 在顺序表L中的第i个位置之前插入新元素e // i的合法值范围为 0 ~ L-length Status ListInsert_Sq(SqList *L, int i, ElemType e) { if (i 0 || i L-length) return ERROR; if (L-length = L-listsize) { ElemType * newbase = (ElemType *)realloc(L-elem, (L-listsize+LIST_INCREMENT)*sizeof(ElemType)); if (newb