数据结构(C语言版)第二章1.ppt

本章主要重点和难点 重点： 1.线性表的类型定义 2.线性表的表示和实现 3.线性表的应用 线性表的结构特点 线性结构是一个数据元素的有序（次序）集合。 它有四个基本特征：　1．集合中必存在唯一的一个“第一元素”；　2．集合中必存在唯一的一个“最后元素”；　3．除第一元素之外，其它数据元素均有唯一的“前驱”。 　 4．除最后元素之外，其它数据元素均有唯一的后继； 例如：一个线性表的第一个元素的存储地址为100，每个元素的长度为2，则第5个元素的存储地址是多少？ 分析： 已知：loc(a1)=100,k=2；求loc(a5)=？ 根据公式loc(ai)= loc(a1)+(i-1)*k loc(a5)= loc(a1)+(5-1)*2 =100+4*2=108 线性表的静态分配存储结构： ＃define MAXSIZE=线性表可能达到的最大长度 typedef struct { ElemType elem［MAXSIZE］/* 存储空间 */ int length；/*记录线性表的长度 */ } SeqList； /*数组中的下标从0开始*/ 说明： 1.结点类型定义中ElemType数据类型是抽象化的一般形式，用户可以根据自己实际需要来具体定义顺序元素的数据类型。 2.从数组的下标为0的第一个单元开始存放第一个元素。需要注意数组的下标与元素的对应关系，即表中第i个数据元素是L.elem[i-1]。 利用顺序表定义变量的数据类型 1）通过变量定义语句：SeqList L;将L定义为SeqList类型。 访问顺序表中序号为i的元素ai：L.elem[i-1] 顺序表的表长：L.length 2)通过指针变量定义语句： SeqList *L，将L定义为指向SeqList类型的指针变量。 访问顺序表中序号为i的元素：L—elem[i-1] 得到顺序表的表长：L—length 1.初始化顺序表 status InitList_sq(seqList 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; } 1）算法设计：顺序表L，插入为序i，插入元素e。 插入分析：第i个位置存放e，则原表中的第i至第n个，共n-i+1个数据元素必须先依次后移1个位置，以腾出第i个位置。后移时从最后一个元素开始，逐个往后移。 合法位置：1≤i≤L.length+1; 上溢处理：上溢发生的条件是：L.length≥L.listsize，此时先申请一个有一定增量的空间，修改L.listsize的值。 2）算法描述： Status ListInsert_sq(SqList L,int i,ElemType e) {if(i1||iL.length+1) return ERROR; if(L.length=L.listsize) {newbase= (ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT * sizeof(ElemType)); if(!newbase)exit (OVERFLOW); L.elem=newbase; 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; } 3）算法动态演示 4）算法时间复杂度的分析 （1）当在表尾(即i=L.length+2)插入元素时，此时不需要移动元素， 可直接在表尾插入e。 （2）当在表头(即i=1)插入元素时， 将表中已存在的n个元素依次后移一个位置才能将e插入。 （3）一般情况下，在第i（1≤i≤n）个元素前插入一个元素时，需将第n至第i（共n-i+1）个元素向后移动一个位置。 （4）语句*(p+1)=*p的执行次数和插入位置有关。算法的时间复杂度为O(f(n))=n。 3.线性表的删除 （1）算法分析 线性表的删除运算是指将表的第i(1≤i≤n)个元素删去， 使长度为n的线性表(e1，…, ei-1，ei，ei+1，…，en)变成长度为n-1的线性表(e1，…, e