第2章 线性表(1)

1、2021-7-2 数据结构与算法数据结构与算法 第第2 2章章 线性表线性表 朱凌朱凌 2021-7-2 数据结构概论知识点数据结构概论知识点 2.1. 2.2. 2.3. 2.4. n 本章讨论几种常用的(统称为)： （也称为向量，是用），类似于 C/C+语言中的数组，。 （用）：链式结构的线性表，在结点中 附件来表达结点之间的关系。 单链表； 双链表； 循环链表：循环单链表，循环双链表。 2.1 2.1 线性表线性表 n 线性表是一类（区别于和）数据结构，它有多种 存储结构和应用方法，从而可以细分为、等。 是从的角度来描述数据结构的，它主要有两种存 储结构：和。 2.1.1 2.1.1 线

2、性表的抽象数据类型线性表的抽象数据类型 n 线性表：直观地讲， ，。 n 在线性表中： 有唯一的，它没有前驱；其他结点都有唯一的前驱结点 。 有唯一的，它没有后继；其他结点都有唯一的后继结点 。 除开始结点和末尾结点外，其他结点称为，中间结点有 唯一的前驱和后继。 n 可以从的角度对线性表进行严格定义(略)。 2.1.3 2.1.3 线性表的存储结构线性表的存储结构 n 线性表的：如何开辟存储空间，各结点存储空间的联系，如 何实现等。 n 线性表的存储结构主要有两种： 。特点是线性表结点可以按地址相邻的顺序存 储在一片连续的存储空间中，线性表的固定长度限制了线性表结点 个数变化不能超过该固定长

3、度。 。具体形式有链式存储结构，动态数组等。 在中，各结点的存储空间动态申请和释放，通过 指针域来表达结点的前驱/后继关系。 ：定长数组的变形，当结点个数超出最大限度时，重 新申请更长的数组（new和delete运算符）。 2.1.2 2.1.2 线性表运算分类线性表运算分类 n 典型的运算：(加)、(除)、(找)、(修)。 2.2 2.2 顺序表向量顺序表向量 (sequential list)又称为(vector)，它 。 n 向量的： 。 中，每一个元素按其顺序 有唯一的索引值，又称，用它可以方便地访问元素内容。 n 顺序表类似于C/C+语言中的，将各种操作封装一个类。 向量的抽象数据类

4、型向量的抽象数据类型 向量的抽象数据类型 ：向量长度，当前元素个 数，指向元素所占存储空间的指针 。 ：追加元素、插入 元素、删除元素、查找、判空、判 满、输出所有结点的值。 顺序表的类定义顺序表的类定义 / 顺序表的类定义顺序表的类定义 template class arrList private: T *aList; /int *aList; int maxSize; int curLen; int position; public: arrList(const int size) maxSize=size; aList=new TmaxSize; /aList = new intmaxS

5、ize; curLen=position=0; arrList() delete aList; void clear() delete aList; curLen=position=0; aList=new TmaxSize; int length(); bool append(const T value); bool insert(const int p,const T value); bool deletion(const int p); bool setValue(const int p,const T value); bool getValue(const int p, T bool

6、getPos(int ; template bool arrList:setValue(const int p,const T value) if() Tp=value; return true; template bool arrList:getValue(const int p, T return true; 顺序表的运算实现顺序表的运算实现 n 顺序表的检索 /arrList_getPos线性表的检索线性表的检索 template bool arrList:getPos(int for(i=0;in;i+) if(value=aListi) p=i; return true; retur

7、n false; 顺序表的运算实现顺序表的运算实现 n 顺序表的插入 /arrList_insert 线性表的插入线性表的插入 template bool arrList:insert(const int p,const T value) int i; if (curLen=maxSize) coutThe list is overflowendl; return false; if (pcurLen) coutInsertion point is illegalp;i-) aListi=aListi-1; aListp=value; curLen+; return true; 14 插入算法

8、的执行时间插入算法的执行时间 n 插入操作的主要代价体现在表中元素的移动 k - 1 i0 1 /(- ) 2 k kki q 在位置i插入元素，需移动k-i 个元素 元素总个数为k，假设各个位置插入的概率相 等，均为p1/k 平均移动元素次数为 总时间开销估计为O(k) 顺序表的运算实现顺序表的运算实现 n 顺序表的删除 /arrList_deletion 线性表的删除线性表的删除 template bool arrList:deletion(const int p) int i; if (curLen=0) coutNo element to delete nendl; return fa

9、lse; if (pcurLen-1) coutdeletion is illegalnendl; return false; for(i=p;icurLen-1;i+) aListi=aListi+1; curLen-; return true; 2.3 2.3 链表链表 ( )的特点是，并通过指针来链接 结点，按照线性表的把一个个结点链接起来。 n 几种用于线性表的链式存储结构： ； ； ； 。 n 链表存储是最常用的存储方式之一，它， ，如树结构和图结构。 2.3.1 2.3.1 单链表单链表 n 在单链表中，： 存放结点数据的； 存放指向后继结点的。 n 因为，因此由这种结点链接而成

10、的链表，称为。 ：指向单链表中第0个结点()。 template class Link/单链表中的结点类单链表中的结点类 public: T data; Link *next; Link(); ; 单链表的抽象数据类型单链表的抽象数据类型 ：表首指针head，单链表长度len。 ：查找结点、插入结点、删除结点、求单链表长度、 输出所有结点的值。 19 单链表的结点类型单链表的结点类型 template class Link public: T data; / 用于保存结点元素的内容 Link *next;/ 指向后继结点的指针 Link(const T info, const Link* ne

11、xtValue = NULL) data = info; next = nextValue; Link(const Link* nextValue) next = nextValue; ; 20 单链表的定义单链表的定义 template class lnkList : public List private: Link * head; / 单链表的头 int length; Link *setPos(const int p);/ 返回线性表指向第p个元素的指针值 public: lnkList(int s);/ 构造函数 lnkList();/ 析构函数 bool isEmpty(); /

12、判断链表是否为空 void clear(); / 将链表存储的内容清除，成为空表 int length(); / 返回此顺序表的当前实际长度 bool append(cosnt T value);/ 在表尾添加一个元素value，表的长度增 1 bool insert(cosnt int p, cosnt T value);/ 在位置p上插入一个元素value，表的长 度增1 bool delete(cosnt int p); / 删除位置p上的元素，表的长度减 1 bool getValue(cosnt int p, T/ 返回位置p的元素值 bool getPos(int / 查找值为va

13、lue的元素，返回第1次出现 的位置 查找单链表中第查找单链表中第i i个结点个结点 ：。 ：，。 n 查找的实现：通过结点的指针实现所有的结点，直至找 到满足要求的结点为止。 22 查找单链表中第查找单链表中第i i个结点个结点 / 函数返回值是找到的结点指针 template / 线性表的元素类型为T Link * lnkList : setPos(int i) int count = 0; if (i = -1) / i为-1则定位到头结点 return head; / 循链定位，若i为0则定位到第一个结点 Link *p = new Link(head-next); while (p

14、!= NULL count+; ; return p; / 指向第 i 结点，i0,1,，当链表中结点数小于i时返回 NULL 在单链表中插入结点在单链表中插入结点 ：。 ： n 插入结点的实现：特别需要。 24 单链表的插入单链表的插入 20231215 head tail 在23 和12 之间插入 10 20231215 headtail 10 创建新结点创建新结点 新结点指向右边的结点新结点指向右边的结点 左边结点指向新结点左边结点指向新结点 25 单链表插入算法单链表插入算法 / 插入数据内容为value的新结点作为第i个结点 template / 线性表的元素类型为T bool ln

15、kList : insert(const int i, const T value) Link *p, *q; if (p = setPos(i -1) = NULL) / p 是第i个结点的前驱 cout 非法插入点endl; return false; q = new Link(value, p-next); p-next = q; if (p = tail)/ 插入点在链尾，插入结点成为新的链尾 tail = q; return true; 在单链表中删除结点在单链表中删除结点 ：。 ：。 n 删除结点的实现：特别需要。 27 用p指向元素x的结点, 可以吗? . . x head p

16、. x p 单链表删除示意单链表删除示意 28 x p p p next = q next; q q = pnext; free(q); 删除值为删除值为 x x 的结点的结点 29 template / 线性表的元素类型为T bool lnkList: delete(const int i) Link *p, *q; / 待删结点不存在，即给定的i大于当前链中元素个数 if (p = setPos(i-1) = NULL | p = tail) cout 非法删除点 next;/ q是真正待删结点 if (q = tail) / 待删结点为尾结点，则修 改尾指针 tail = p; p-next = NULL: delete q; else if (q != NULL) / 删除结点q 并修改链指针 p-next = q-next; delete q; return true; 单链表删除算法单链表删除算法 2.3.2 2.3.2 双链表双链表 ：由于它的next指针仅指向后继结点，因此 。 n 在双链表中，除data域外，有： ：指向前驱结点； ：指向后继结点。 n 因为，因此由这种结点链接而成的链表，称为 。 2.3