《数据结构与算法-线性表.ppt》由会员分享，可在线阅读，更多相关《数据结构与算法-线性表.ppt（32页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2020/10/24,数据结构与算法,第2章 线性表 朱凌,Zhejiang University Of Finance /int *aList; int maxSize; int curLen; int position; public: arrList(const int size) maxSize=size; aList=new TmaxSize; /aList = new intmaxSize; curLen=position=0; arrList() delete aList; ,void clear() delete aList; curLen=position=0; aList=
2、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 ,template bool arrList:setValue(const int p,const T value) if() Tp=value; return true; template bool arrL
3、ist:getValue(const int p, T ,顺序表的运算实现,顺序表的检索,/arrList_getPos线性表的检索 template bool arrList:getPos(int ,顺序表的运算实现,顺序表的插入,/arrList_insert 线性表的插入 template bool arrList:insert(const int p,const T value) int i; if (curLen=maxSize) coutcurLen) coutp;i-) aListi=aListi-1; aListp=value; curLen+; return true; ,1
4、4,插入算法的执行时间,插入操作的主要代价体现在表中元素的移动,在位置i插入元素，需移动k-i 个元素 元素总个数为k，假设各个位置插入的概率相等，均为p1/k 平均移动元素次数为,总时间开销估计为O(k),顺序表的运算实现,顺序表的删除,/arrList_deletion 线性表的删除 template bool arrList:deletion(const int p) int i; if (curLencurLen-1) coutdeletion is illegalnendl; return false; for(i=p;icurLen-1;i+) aListi=aListi+1; c
5、urLen-; return true; ,2.3 链表,链表(linked list)的特点是动态申请内存空间，并通过指针来链接结点，按照线性表的前驱/后继关系把一个个结点链接起来。 几种用于线性表的链式存储结构： 单链表； 双链表； 循环单链表； 循环双链表。 链表存储是最常用的存储方式之一，它不仅可以用来表示线性表，而且也可以用于其他非线性的数据结构中，如树结构和图结构。,2.3.1 单链表,在单链表中，每个结点由两部分组成： 存放结点数据的data域； 存放指向后继结点的next指针域。 因为每个结点中只有指向后继结点的指针，因此由这种结点链接而成的链表，称为单链表。 表首指针head
6、：指向单链表中第0个结点(结点序号从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* nextValue = NUL
7、L) 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(); / 判断链表是否为空 void clear
8、(); / 将链表存储的内容清除，成为空表 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/ 查找值为value的元素，返回第1次出现的位置 ,查找单链表中第i个结点,讲解：查找结点数据为指定值的结点。
9、setPos函数：查找第i个结点，并返回该结点的指针。 查找的实现：通过结点的指针实现遍历(即扫描)所有的结点，直至找到满足要求的结点为止。,22,查找单链表中第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 != NULL / 指向第 i 结点，i0,1,，当链表中结
10、点数小于i时返回NULL ,在单链表中插入结点,讲解：在指针p所指向结点的后面插入新结点。 insert函数：插入新结点，使之成为第i个结点，返回该结点的指针 插入结点的实现：特别需要注意修改相关指针的值。,24,单链表的插入,在23 和12 之间插入 10,创建新结点 新结点指向右边的结点 左边结点指向新结点,25,单链表插入算法,/ 插入数据内容为value的新结点作为第i个结点 template / 线性表的元素类型为T bool lnkList : insert(const int i, const T value) Link *p, *q; if (p = setPos(i -1)
11、= NULL) / p 是第i个结点的前驱 cout (value, p-next); p-next = q; if (p = tail)/ 插入点在链尾，插入结点成为新的链尾 tail = q; return true; ,在单链表中删除结点,讲解：删除指针p所指向的结点。 deletion函数：删除第i个结点。 删除结点的实现：特别需要注意修改相关指针的值。,27,用p指向元素x的结点, 可以吗?,.,.,x,head,p,.,x,p,单链表删除示意,28,x,p,p,p next = q next;,q,q = pnext;,free(q);,删除值为 x 的结点,29,template
12、 / 线性表的元素类型为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
13、.2 双链表,单链表的不足：由于它的next指针仅指向后继结点，因此不方便找一个结点的前驱结点。 在双链表中，除data域外，有两个指针域： Llink：指向前驱结点； Rlink：指向后继结点。 因为每个结点有两个指针域，因此由这种结点链接而成的链表，称为双链表。,2.3.3 循环链表,循环单链表：将单链表末尾结点的指针域由NULL改为指向表首结点，就成为一个循环单链表。 循环双链表：将双链表的头结点和尾结点链接起来。 循环链表的优点：从循环链表中任一结点出发，都能访问到链表中每个结点。,顺序表与单链表比较分析,顺序表的优点恰好是单链表的缺点，顺序表的缺点恰好是单链表的优点。 顺序表适合于元素个数比较稳定的情形，单链表适合于结点个数动态变化的情形(如需要频繁删除和插入结点)。,