《数据结构课件(李春葆 第3版)第2章 线性表》由会员分享，可在线阅读，更多相关《数据结构课件(李春葆 第3版)第2章 线性表（108页珍藏版）》请在金锄头文库上搜索。
1、第2章 线性表 2.1 线性表的基本概念 2.2 线性表的顺序存储2.3 线性表的链式存储 2.4 线性表的应用 本章小结 2.5 有序表 2.1 线性表的基本概念 2.1.1 线性表的定义2.1.2 线性表的运算2.1.1 线性表的定义线性表是具有相同特性的数据元素的一个有 限序列。该序列中所含元素的个数叫做线性表的 长度,用n表示,n0。当n=0时,表示线性表是一个空表,即表中不包 含任何元素。设序列中第i(i表示位序)个元素为 ai(1in)。线性表的一般表示为:(a1,a2,ai,ai+1,an)其中a1为第一个元素,又称做表头元素,a2为 第二个元素,an为最后一个元素,又称做表尾元
2、 素。例如,在线性表(1,4,3,2,8,10)中,1为表头元素,10为表尾元素。2.1.2 线性表的运算线性表的基本运算如下:(1) 初始化线性表InitList(ElemType e;InitList(LC);for (i=1;idatai=ai;L-length=n;2. 顺序表基本运算算法(1) 初始化线性表InitList(L)该运算的结果是构造一个空的线性表L。实际上只 需将length成员设置为0即可。void InitList(SqList */*分配存放线性表的空间*/L-length=0;本算法的时间复杂度为O(1)。顺序表L(2) 销毁线性表DestroyList(L)该
3、运算的结果是释放线性表L占用的内存空间。void DestroyList(SqList *本算法的时间复杂度为O(1)。 (3) 判定是否为空表ListEmpty(L)该运算返回一个值表示L是否为空表。若L为空 表,则返回1,否则返回0。int ListEmpty(SqList *L)return(L-length=0);本算法的时间复杂度为O(1)。(4) 求线性表的长度ListLength(L)该运算返回顺序表L的长度。实际上只需返回 length成员的值即可。int ListLength(SqList *L)return(L-length);本算法的时间复杂度为O(1)。(5) 输出线性
4、表DispList(L)该运算当线性表L不为空时,顺序显示L中各元素的 值。void DispList(SqList *L)int i;if (ListEmpty(L) return;for (i=0;ilength;i+)printf(“%c“,L-datai);printf(“n“); 本算法中基本运算为for循环中的printf语句,故时间复杂度为:O(L-length)或O(n)(6) 求某个数据元素值GetElem(L,i,e)该运算返回L中第 i(1iListLength(L)个元素的值, 存放在e中。int GetElem(SqList *L,int i,ElemType e=L
5、-datai-1;return 1;本算法的时间复杂度为O(1)。 (7) 按元素值查找LocateElem(L,e)该运算顺序查找第1个值域与e相等的元素的位序。若 这样的元素不存在,则返回值为0。int LocateElem(SqList *L, ElemType e)int i=0;while (ilength if (i=L-length)return 0;else return i+1;本算法中基本运算为while循环中的i+语句,故时间复杂度为:O(L-length)或O(n)(8) 插入数据元素ListInsert(L,i,e)该运算在顺序表L的第i个位置 (1iListLeng
6、th(L)+1)上插入新的元素e。思路：如果i值不正确,则显示相应错误信息 ；否则将顺序表原来第i个元素及以后元素均后 移一个位置,腾出一个空位置插入新元素,顺序表 长度增1。int ListInsert(SqList *if (iL-length+1)return 0;i-; /*将顺序表逻辑位序转化为elem下标即物理位序*/for (j=L-length;ji;j-) L-dataj=L-dataj-1;/*将datai及后面元素后移一个位置*/L-datai=e;L-length+; /*顺序表长度增1*/return 1;a0ai-1aian-1逻辑位序 1 i i+1 n MaxS
7、ize 对于本算法来说,元素移动的次数不仅与表长L.length=n有关,而且与插入位置i有关:当i=n+1时,移动次数为0；当i=1时,移动次数为n,达到最大值。在线性表sq中共有n+1个可以插入元素的地方。假设pi(= )是在第i个位置上插入一个元素的概率,则在长度为n的线性表中插入一个元素时所需移动元素的平均次数为:因此插入算法的平均时间复杂度为O(n)。(9) 删除数据元素ListDelete(L,i,e)删除顺序表L中的第i(1iListLength(L)个元 素。思路：如果i值不正确,则显示相应错误信息； 否则将线性表第i个元素以后元素均向前移动一个 位置,这样覆盖了原来的第i个元
8、素,达到删除该元 素的目的,最后顺序表长度减1。int ListDelete(SqList *if (iL-length)return 0;i-; /*将顺序表逻辑位序转化为elem下标即物理位序*/e=L-datai;for (j=i;jlength-1;j+) L-dataj=L-dataj+1;/*将datai之后的元素后前移一个位置*/L-length-;/*顺序表长度减1*/return 1; a0ai-1aian-1逻辑位序 1 i i+1 n MaxSize 对于本算法来说,元素移动的次数也与表长n和删除元素的位置i有关:当i=n时,移动次数为0；当i=1时,移动次数为n-1。在
9、线性表sq中共有n个元素可以被删除。假设pi(pi= )是删除第i个位置上元素的概率,则在长度为n的线性表中删除一个元素时所需移动元素的平均次数为:= 因此删除算法的平均时间复杂度为O(n)。例2.2 设计一个算法,将x插入到一个有序( 从小到大排序)的线性表(顺序存储结构即顺序 表)的适当位置上,并保持线性表的有序性。解:先通过比较在顺序表L中找到存放x的位 置i,然后将x插入到L.datai中,最后将顺序表的 长度增1。void Insert(SqList *while (ilength j=i;j-)L-dataj+1=L-dataj;L-datai=x;L-length+;查找插入位置
10、元素后移一个位置a0ai-1aian-1逻辑位序 1 i i+1 n MaxSize 例2.3 设计一个算法,将两个元素有序(从 小到大)的顺序表合并成一个有序顺序表。 求解思路:将两个顺序表进行二路归并。 归并到顺序表r中 k记录r中元素个数1(i=0) 2(j=0) 将1(i=1)插入r(k=1)3(i=1) 2(j=0) 将2(j=1)插入r(k=2)3(i=1) 4(j=1) 将3(i=2)插入r(k=3)5(i=2) 4(j=1) 将4(j=2)插入r(k=4)5(i=2) 10(j=2) 将5(j=3)插入r(k=5)将q中余下元素插入r中。 顺序表p：1 3 5i顺序表q：2 4
11、 10 20j顺序表r：1 kSqList *merge(SqList *p, SqList *q) SqList *r; int i=0,j=0,k=0;r=(SqList *)malloc(sizeof(SqList);while (ilength i+;k+; else r- datak=q- dataj; j+;k+; while (ilength) r-datak=p-datai;i+;k+; while (jlength) r-datak=q-dataj;j+;k+; r-length=k; /*或p-length+q-length*/return(r); 例2.4 已知长度为n的
12、线性表A采用顺序存储结 构,编写一个时间复杂度为O(n)、空间复杂度为O(1) 的算法,该算法删除线性表中所有值为item的数据元 素。解:用k记录顺序表A中等于item的元素个数,边 扫描A边统计k,并将不为item的元素前移k个位置,最 后修改A的长度。对应的算法如下:void delnode1(SqList /*k记录值不等于item的元素个数*/for (i=0;inext=NULL;for (i=0;idata=ai; s-next=L-next;/*将*s插在原开始结点之前,头结点之后*/L-next=s;adcbi=0 i=1 i=2 i=3head采用头插法建立单链表的过程he
13、ad aheaddaheadc daheadb cda第1步:建头结点第2步:i0,新建a结点,插入到头结点之后第3步:i1,新建d结点,插入到头结点之后第4步:i2,新建c结点,插入到头结点之后第5步:i3,新建b结点,插入到头结点之后(2) 尾插法建表头插法建立链表虽然算法简单,但生成的链表 中结点的次序和原数组元素的顺序相反。若希望 两者次序一致,可采用尾插法建立。该方法是将 新结点插到当前链表的表尾上,为此必须增加一 个尾指针r,使其始终指向当前链表的尾结点。采 用尾插法建表的算法如下:void CreateListR(LinkList *int i;L=(LinkList *)mal
14、loc(sizeof(LinkList); /*创建头结点*/r=L; /*r始终指向终端结点,开始时指向头结点*/for (i=0;idata=ai;r-next=s; /*将*s插入*r之后*/r=s;r-next=NULL;/*终端结点next域置为NULL*/bcdai=0 i=1 i=2 i=3head头结点adcbb采用尾插法建立单链表的过程2. 插入结点运算插入运算是将值为x的新结点插入到单链表 的第i个结点的位置上。先在单链表中找到第i-1 个结点,再在其后插入新结点。单链表插入结点的过程如下图所示。插入结点示意图3. 删除结点运算删除运算是将单链表的第i个结点删去。先在单 链
15、表中找到第i-1个结点,再删除其后的结点。删除单链表结点的过程如下图所示。删除结点示意图4. 线性表基本运算实现(1) 初始化线性表InitList(L)该运算建立一个空的单链表,即创建一个头结点。void InitList(LinkList * /*创建头结点*/L-next=NULL;(2) 销毁线性表DestroyList(L)释放单链表L占用的内存空间。即逐一释放全部结点 的空间。void DestroyList(LinkList *while (q!=NULL) free(p);p=q;q=p-next;free(p);(3) 判线性表是否为空表ListEmpty(L)若单链表L没有数据结点,则返回真,否则返回假。int ListEmpty(LinkList *L)return(L-next=NULL);(4) 求线性表的长度ListLength(L)返回单链表L中数据结
