谭浩强C语言_数据结构11.ppt

《谭浩强C语言_数据结构11.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构第一部分数据结构基础知识数据结构数据结构：是一门研究非数值计算的程序设计问题中计算机操作对象以及它们之间的关系和操作等等的学科。基本概念数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。数据的逻辑结构数据的存储结构数据的运算：检索、排序、插入、删除、修改等线性结构非线性结构顺序存储链式存储线性表栈队树形结构图形结构数据结构的三个方面：主要内容1.1线性表以及其应

2、用1.2栈、队列1.3排序、查找1.1线性表以及其应用（1）线性表分为静态线性表和动态线性表静态线性表特征：表中节点的存储是连续的，占用一块连续存储区，一般节点的数量是固定的；存储表示如下图数据结构如下图数据1后继:2数据2后继:3数据3后继:4…………数据n-1后继:n数据nendtypedefstruct{Data_tdata;//数据域intnext;//后继域}Node_t,*PNode_t;//提供的操作有：初始化、插入、删除等。线性表顺序存储结构特定：借助元素在存储器中的相对位置（即，物理位置相邻）来表示数据元素之间的逻辑关系。缺点：插入

3、、删除时，需移动大量数据。一次性分配内存空间。表的容量难以扩充。图顺序存储结构内存结构示意图1.1线性表以及其应用（2）动态线性表特征：表中节点的存储是不连续的，一般节点的数量是不固定的；存储表示如下图数据结构如下图typedefstruct{Data_tdata;//数据域Node_t*next;//后继域}Node_t,*PNode_t;//提供的操作有：初始化、插入、删除等。数据1后继数据2后继数据3后继…………数据n-1后继数据nend链式存储结构链式存储结构是计算机中的另一种最基本和最主要的数据存储结构。和顺序存储结构不同，初始时链式存储结

4、构为空链，每当有新的数据元素需要存储时用户向系统动态申请所需的存储空间插入链中。链式存储结构每个结点有两个域，其中存储数据元素信息的域称为整数域；存储直接后继存储位置的域称为指针域。structNode{intdata;structNode*Next;};typedefstructNodeNode_t;链式存储结构存储线性结构数据元素集合的方法是用结点（Node）构造链。线性结构数据元素的特点是：除第一个和最后一个元素外，每个元素只有一个惟一的前驱和一个惟一的后继。链式结构中每个结点除数据域外还有一个或一个以上的指针域，数据域用来存放数据元素，指针域

5、用来构造数据元素之间的关系。只有一个指针域的结点结构如图所示。图只有一个指针域的结点结构数据域指针域datanext或根据指针域的不同和结点构造链的方法不同，链式存储结构存储线性结构数据元素的方法主要有单链、单循环链和双向循环链等三种。这三种结构中每一种又有带头结点结构和不带头结点结构两种。头结点是指头指针所指的不存放数据元素的结点。其中，带头结点的链式结构在表的存储中更为常用，不带头结点的链式结构在堆栈和队列的存储中更为常用。我们把图中头结点的数据域部分涂上阴影，以明显表示该结点为头结点。图2和图3中的指针域为指向下一个结点的指针。图4中结点右部的

6、指针域为指向下一个结点的指针，结点左部的指针域为指向上一个结点的指针。在以后的图示中，头指针将用head表示。图2带头结点的单链结构(a)空链；(b)非空链图3带头结点的单循环链结构(a)空链；(b)非空链图4带头结点的双循环链结构(a)空链；(b)非空链图中的符号“∧”表示空指针，空指针在算法描述中用NULL表示。空指针是一个特殊标识，用来标识链的结束。NULL在C中宏定义为0，因此空指针在C中也就是0地址。为与顺序表中数据元素从a0开始相一致，讨论链表时数据元素也从a0开始。链式存储结构也可以方便地存储非线性结构的数据元素。链式存储结构存储非线性

7、结构数据元素的最典型的例子是链式结构的二叉树。添加插入删除图单链表在第一个位置删除结点过程p=a.next;a.next=a.next.next;dispose(p);图单链表在第一个位置插入结点过程（a）插入前；（b）插入后new(s);s.data=x;s.next=a.next;a.next=s;heada0a1…an£1xs(a)heada0a1…an£1x(b)循环链表(circularlinkedlist)循环链表是表中最后一个结点的指针指向头结点，使链表构成环状特点：从表中任一结点出发均可找到表中其他结点，提高查找效率操作与单链表基本一

8、致,循环条件不同单链表p或p->next=NULL循环链表p或p->next=Hhh空表双向链表双向链表(D