09年自考《数据结构》各章要点一[3]

第二章 线性表

线性表是由n≥个数据元素组成的有限序列n=是空表;非空表只能有一个开始结点有且只能有一个终端结点

线性表上定义的基本运算

·构造空表Initlist(L)

·求表长Listlength(L)

·取结点GetNode(Li)

·查找LocateNode(Lx)

·插入InsertList(Lxi)

·删除Delete(Li)

顺序表是按线性表的逻辑结构次序依次存放在一组地址连续的存储单元中在存储单元中的各元素的物理位置和逻辑结构中各结点相邻关系是一致的地址计算LOCa(i)=LOCa()+(i)*d;(首地址为)

在顺序表中实现的基本运算

·插入平均移动结点次数为n/;平均时间复杂度均为O(n)

·删除平均移动结点次数为(n)/;平均时间复杂度均为O(n)

线性表的链式存储结构中结点的逻辑次序和物理次序不一定相同为了能正确表示结点间的逻辑关系在存储每个结点值的同时还存储了其后继结点的地址信息(即指针或链)这两部分信息组成链表中的结点结构 一个单链表由头指针的名字来命名

[] [] [] [] [] [] [] [] [] [] []