《数据结构》(C语言版)第二章(精品·公开课件).ppt

第二章 线性表 教学要求： 理解线性表的概念 掌握线性表的抽象数据类型和应具有的基本操作 掌握线性表的顺序存储结构的实现方法 掌握线性表的链表存储结构的实现方法 掌握线性表的简单应用 线性表：线性表是n个元素的有序序列，是最常用且最简单的一种数据结构。 （ A, B, C, D, …… , Z） 综上例： 线性表中的数据元素可以是各种各样的 但同一个表中的元素必须具有相同的特性 相邻数据元素之间存在序偶关系 线性表中每一个元素都有确定的位置，如a1是第一个数据元素，ai是第i个数据元素 在C语言中，一维数组的机内表示就是顺序结构。因此，可用C语言的一维数组实现线性表的顺序存储。 问题： １、在顺序表中，第ｉ个元素前面插入一个元素，要移动多少个元素？ ２、在顺序表中，要删除第ｉ个元素，要移动多少个元素？ 作业: 用C语言编写代码,实现顺序表里面所有的操作。 静态链表 用一维数组描述线性链表. 如线性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)可表示成: 有序链表中一些操作的功能: Status LocatElem(LinkList L,ElemType e,Positionq,int(*compare)(ElemType,ElemType) 如果有序链表中存在与ｅ满足函数Compare()的元素,那么q就指向L中第一个值为e的结点的位置,并返回True;否则,q返回第一个大于e的元素的前驱的位置. int cmp(term a,term b) 若ab 返回-1;若a=b 返回0;若ab 返回1 作业: 用类c的语言写出链式存储条件下，删除单链表L中值大于max小于min的算法：Delete(L,max,min) 《数据结构学习辅导》 Status ListInsert_L(LinkList L, int i, ElemType e) { // L 为带头结点的单链表的头指针，本算法 // 在链表中第i 个结点之前插入新的元素 e } // LinstInsert_L 算法的时间复杂度为: O(ListLength(L)) …… p = L; j = 0; while (p j i-1) { p = p-next; ++j; } // 寻找第 i-1 个结点 if (!p || j i-1) return ERROR; // i 大于表长或者小于1 s = (LinkList) malloc ( sizeof (LNode)); // 生成新结点 s-data = e; s-next = p-next; p-next = s; // 插入 return OK; e ai-1 ai ai-1 s p 线性表的操作ListDelete (L, i, e)在链表中的实现: 有序对ai-1, ai 和 ai, ai+1 改变为 ai-1, ai+1 ai-1 ai ai+1 ai-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 算法的时间复杂度为: 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; 操作 ClearList(L) 在链表中的实现: void ClearList(L) { // 将单链表重新置为一个空表 while (L-next) { p=L-next; L-next=p-next;