计算机软件技术基础 第二章.ppt

线性表的逻辑结构及其基本操作线性表的顺序存储结构线性表的链式存储结构静态链表应用实例 第二章线性表 2 1 线性表的逻辑结构及其基本操作 线性表是n n 0 个相同类型数据元素a0 a1 an 1构成的有限序列 形式化定义 Linearlist D R 其中 D0为某个数据对象的集合N为线性表长度 线性表的主要操作 初始化求长度取元素定位插入删除 例 利用线性表的基本运算实现清除L中多余的重复节点 PURGE Linear list L inti 1 j x y while i LENGTH L x GET L i j i 1 while j LENGTH L y GET L j if x y DELETE L j elsej i 2 2线性表的顺序存储结构 顺序表 设线性表的基地址为 LOC a1 ai的存储地址为 LOC ai LOC a0 i k1 i n a0 a1 ai an 1 a0 a1 ai an 1 0 1 n 1 Loc a0 Loc a0 k i Loc a0 i k Loc a0 n 1 k 线性表的定义为 typedefintdatatype 假定线性表元素的类型为整型 definemaxsize1024 假定线性表的最大长度为1024typedefstruct datatypedata maxsize intlast 指向最后结点的位置 sequenlist 1 先定义结构类型 再定义变量名structstudent intnum charname 20 charsex intage floatscore charaddr 30 Structstudentstudent1 student2 C语言中定义结构的方法 2 在声明类型的同时定义结构变量structstudent intnum charname 20 charsex intage floatscore charaddr 30 student1 student2 3 直接定义结构变量struct intnum charname 20 charsex intage floatscore charaddr 30 student1 student2 例 defineMAXSIZEtypedefstruct charName 20 charSex intAge floatfareAmount datatype 线性表元素的插入intINSERT sequenlist L datatypex inti intj if L last maxsize 1 printf overflow n returnNULL 溢出elseif i L last 1 printf error n returnNULL 非法位置else for j L last j i 1 j L data j 1 L data j L data i 1 x L last L last 1 return 1 线性表元素的删除intDELETE sequenlist L inti intj if i L last 1 printf error n returnNULL 非法位置else for j i j L last j L data j 1 L data j L last 表长减1 return 1 1 插入n 22 删除 n 1 23 按序号检索O 1 4 按内容检索n 2 算法复杂性分析 顺序表的优点 无须为表示节点间的逻辑关系而增加额外的存储空间可以方便的随机存取表中的任一节点顺序表的缺点插入和删除运算不方便由于要求占用连续的存储空间 存储分配只能预先进行 2 3线性表的链式存储 h h 不带头节点的链表 带头节点的链表 单链表结点的定义 typedefintdatatype typedefstructnode datatypedata structnode next linklist 节点的申请p malloc sizeof linkist 节点的释放free p 头插法建立单链表 head 建立新节点 向新节点中添入内容 使新节点指向链首 改变头指针 s 头插法建立单链表linklist CREATELIST charch linklist head s head NULL ch getchar while ch s malloc sizeof linklist s data ch s next head head s ch getchar return head 尾插法建立单链表 head 建立新节点 向新节点中添入内容 将新节点链入链尾 改变尾指针 s linklist CREATELISTR charch linklist head s r head NULL r NULL ch getchar while ch s malloc sizeof linklist s data ch if head NULL head s elser next s r s ch getchar 尾插法建立单链表 if r NULL r next NULL returnhead 按序号查找linklist GET linklist head inti intj linklist p p head j 0 while p next NULL 按值查找linklist LOCATE linklist head datatypekey linklist p p head next 头结点不属于表while p NULL if p data key p p next elsebreak returnp 后插运算INSERTAFTER linklist p datatypex linklist s s malloc sizeof linklist s data x s next p next p next s 单个节点的后插操作 建立新节点 向新节点中添入内容 将新节点链入链中 改变新节点前一节点的指针 s p 前插运算INSERTBEFORE linklist head linklist p datatypex linklist s q s malloc sizeof linklist s data x q head while q next p q q next s next p q next s 单个节点的前插操作 建立新节点 向新节点中添入内容 查找插入点 将新节点链入链中 改变新节点前一节点的指针 s q p 改进的前插操作 s p a s p p x a 单链表的插入运算INSERT linklist L datatypex inti linklist p intj j i 1 p GET L j if p NULL printf error n elseINSERTAFTER p x 删除后继节点 存储池 r p 删除后继结点DELETEAFTER linklist p linklist r r p next p next r next free r 删除运算DELETE linklist L inti linklist p intj j i 1 p GET L j if p NULL 循环链表 head head 非空表 空表 rear rear 采用尾指针的循环链表 rear 两循环链表的链接 存储池 p 两循环链表的链接linklist CONNECT linklist ra linklist rb linklist p p ra next ra next rb next next free rb next rb next p returnrb 双链表结点的描述 typedefstructdnode datatypedata structdnode prior next dlinklist 双链表的前插操作DINSERTBEFORE dlinklist p datatypex dlinklist s s malloc sizeof dlinklist s data x s prior p prior s next p p prior next s p prior s s p x a 双链表的删除操作DELETENODEp dlinklist p p prior next p next p next prior p prior free p 静态链表的定义如下 definemaxsize1024 存储池最大容量typedefintdatatype typedefintcursor typedefstruct 结点类型 datatypedata cursornext node nodenodepool maxsize 存储池cursorav 初始化可用空间表avINITIALIZE inti for i 0 i maxsize 1 i nodepool i next i 1 nodepool maxsize 1 next NULL av 1 1 2 3 4 NULL 1 data next av Maxsize 1 Maxsize 1 结点的分配算法cursorGETNODE cursorp if av NULL p NULL else p av av nodepool av next returnp 结点的回收算法FREENODE cursorp nodepool p next av av p 静态链表查找算法cursorFINDSTLIST cursorL inti cursorp intj p L j 0 while nodepool p next NULL 静态链表插入算法intINSERTSTLIST cursorL datatypex inti cursorp s p FINDSTLIST L i 1 if p NULL s GETNODE if s NULL printf error n returnNULL else nodepool s data x nodepool s next nodepool p next nodepool p next s return 1 else printf error n returNULL 静态链表删除算法DELETESTLIST cursorL inti cursorp q p FINDSTLIST L i 1 if p NULL 顺序表与链表的比较 1 基于空间的考虑2 基于时间的考虑3 基于语言的考虑 应用实例 以单链表存储结构实现线性表的就地逆转1 全局变量法2 参数法 la 单链表的逆转 la la la la p p q p p q p p p p Linklist la Voidconvers1 linklist p q P la next la next NULL While p NULL q p p p next q next la next la next q Voidconvers2 linklist la linklist p q P la next La next NULL While p NULL q p p p next q next la next la next q 例 在一个给定的线性表中删除元素值在x到y之间的所有元素 要求以较高的效率实现算法思想 先将向量A中所有在x到y之间的元素置成一个特殊的值0 并不立即删除它们 然后从最后向前依次扫描 删除为0的元素 移动后面的元素 voiddel A n x y intA intn x y inti k for i 1 i x 例 用不多于3n 2的平均比较次数 在一个线性表中找出最大和最小值的元素 voidmaxmin A n intA intn intmax min i for i 2 imax max A i elseif A i min min A i printf max d min d n max min 分析 最坏情况 元素以递减顺序排列 A i max 和 A i max 均成立 不须进行 A i min 的比较 所以总的比较次数为 n 1 平均 2 n 1 n 1 2 3n 2 3 2 例 一元多项式的相加 typedefstructpnode floatcoef 系数intexp 指数structpnode next 指向下一节点 polynode coef exp next 多项式2 3X 5X3 2X4可表示为 1 0 0 2 1 3 3 5 4 2 多项式2 3X 5X3 2X43 2X 4X2相加 初始化 While 两个链都没处理完 if 指针指向当前节点的指数项相同 系数相加 在C链中天加新的节点 A B链的指针均前移 else 以指数小的项的系数添入C链中的新节点 指数小的相应链指针前移 While A链处理完 顺序处理B链 While B链处理