第二章 线性表2 28.pptVIP

线性表 数据结构 2 线性表 数据元素之间具有的逻辑关系为线性关系的数据元素集合称为线性表。 一般表示为： A=( a1,a2,a3,... ...,an ) n个元素的有限序列 元素的个数n为线性表的长度，如果n=0，则为空表。 线性关系如下： 线性表的顺序表示和实现 线性表的顺序表示和实现 特点 各单元的内存地址连续 优点 存储密度大 元素的存储地址可通过一个简单的解析式计算出来 随机存取，访问任一元素所用时间都相同 缺点 插入、删除操作需移动大量元素 算法复杂度 = O(n) 必须预先确定空间 表空间不易扩充 线性表的链式表示和实现 插入操作的时间复杂度 插入这个过程所需时间为常数 但是找到插入位置的复杂度 = O(n) 所以插入操作的复杂度 = O(n) 循环链表 循环链表 尾指针指向表头 双向链表 单向链表 只知道后继结点，不知前趋结点 NextElem操作复杂度为O(1) PriorElem操作复杂度为O(n) 必须从头开始查找 双向链表 增加一个前趋指针 循环双向链表 循环单链表和循环双向链表可通过尾结点找到头结点。 在循环双向链表中，对于一些只涉及一个方向指针且存储结构不变的操作（如查找、求表长等），其算法实现与单链表相同。 在进行插入或删除等结构变化的操作时，与双链表相同，必须同时修改两个方向上的指针，操作过程比单链表复杂。 算法举例 2.14 循环链表的分解 已知L为无头结点单链表中第一个结点的指针，每个结点数据域存放一个字符，该字符可能是英文字母字符或数字字符或其它字符，编写算法构造三个以带头结点的单循环链表表示的线性表，使每个表中只含同一类字符。（要求用最少的时间和最少的空间） 算法举例 2.15 按序输出链表中各元素 设head是带头结点的单链表的头指针，试写出算法，按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间。要求不允许使用数组作辅助空间。 静态链表 有些高级程序设计语言没有指针类型，如FORTRAN和JAVA。我们可以用数组来表示和实现一个链表，称为静态链表。 可定义如下： #define MAXSIZE 1000 //最多元素个数 typedef struct { datatype data; //数据元素 int next; //指向后继元素在数组中的位置 }SLinkedList[MAXSIZE]; 静态链表图示 线性表L=(2,3,4,6,8,9)的静态链表图示 静态链表与动态链表 静态链表的操作和动态链表相似，只是以整型游标代替动态指针。 假设以Sa表示静态链表，通常可把Sa[0]理解为头结点，第1个元素的位置由Sa[0].next指出，用全局整型变量able指出可利用空间的下标。 初始时将整个静态链表看作一个空表，操作中用GetNode()和FreeNode()函数模拟C中的malloc()和free()函数。以下是初始化、取结点和释放结点3个函数。 静态链表的初始化 int Initilize() //初始可利用空间表 { int i; for (i=0;imaxsize-1;i++) // 链成可利用空间表 Sa[i].next=i+1; Sa[maxsize-1].next=-1; // 链表尾 able=1; return able; //返回可利用空间表的下标 } 静态链表的操作举例（1） (1)查找值为x的结点 int Locate(SLinkedList SL, datatype x) { int p=SL[0].next; //第一个结点 while( p!=-1 SL[p].data!=x ) p=SL[p].next; return p; //元素下标 } 静态链表的操作举例（2） (2)查找i第个结点 datatype Locate(SLinkedList SL,int i) {int j=1; if (i0) {printf(参数错误);exit(0);} p=SL[0].next; while( p!=-1 ji ) { p=SL[p].next; j++; } if (p==-1) {printf(参数错误 ) ;exit(0);} return SL[j].data; } 静态链表的操作举例（3） (3)插入第i个结点 void Insert(SLinkedList SL,datatype x,int i) {int pre=0;