数据结构完整版电子课件.ppt

;数据结构;项目一 数据结构导论;数据结构;项目二 线性表;一、线性表的定义 ;一、线性表的定义 ;二、线性表的基本操作 ;⑦ Locate (L, e)：线性表L已存在，返回表L中元素e所在位置；如果表L中不存在元素e，则返回0。 ;任务二 线性表的顺序存储结构 ;一、顺序表的结构特点 ;线性表的顺序存储结构是一种随机存取的存储结构。 ;顺序表的存储结构通常用一维数组来描述，用C语言实现线性表的顺序存储结构的类型定义如下： ;typedef struct { ElemType *elem; //线性表中数据元素的基地址 int length; //线性表的当前长度 int listsize; //当前为线性表分配的存储容量 }SeqList;;定义一个顺序表的方法有两种： ;二、顺序表的基本操作 ;1．初始化顺序表 ;2．插入数据元素 ;算法描述如下： ;假设在顺序表中第i个位置插入一个元素的概率为pi，则在长度为n的线性表中插入一个数据元素时，需要移动其他元素的平均次数为： ;3．删除数据元素 ;算法描述如下： ;假设删除顺序表中第i个数据元素的概率为qi，则在长度为n的线性表中删除一个数据元素时，需要移动其他元素的平均次数为 ;在顺序表中查找值为e的数据元素，并返回该元素在表中的位置。 ;算法描述如下： ;【例2-1】一个线性表L中的数据元素按升序排列，编写一个算法，实现在线性表中插入一个数据元素item，使得线性表仍然保持升序排列。 ;任务三 线性表的链式存储结构 ;数据元素的存储结构，称为结点（Node） ;将n个数据元素通过其对应结点的指针域按其逻辑关系链接成一个链表，链表中的每个结点只包含一个指针域，这样的链表称为线性链表或单链表，其一般形式如图2-5所示。 ;head称为头指针，用于指向单链表的第一个结点。由于单链表的最后一个结点没有直接后继，所以其指针域为“空”（NULL），用符号“∧”表示。 ;单链表的存储结构定义： ;通常在单链表的第一个结点之前设立一个结点，称之为头结点。头结点的数据域可以不存储任何数据信息，也可以存储一个线性表中不包括的元素值；头结点的指针域存储第一个结点的地址信息。 ;二、单链表的基本操作 ;1．建立单链表 ;LinkList *Create (LinkList *L) {//建立一个单链表，将???结点插入表尾 Node *r, *s; ElemType c; int i; *L = (LinkList) malloc (sizeof(Node)); //为头结点分配存储空间 r = *L; //r初值指向头结点 for (i = 1; i <= n; i ++) {READ (c); //获取一个数据元素 s = (LinkList) malloc (sizeof(Node)); //生成一个新结点 s -> data = c; //将要插入数据元素的值赋给新结点的数据域 s -> next = NULL; //链表末尾结点指针域为空 r -> next = s; //将新结点插入到当前链表的表尾上 r = s; } //r始终指向链表的当前表尾 return L; };2．插入数据元素 ;算法描述如下： ;3．删除数据元素 ;算法描述如下： ;4．查找数据元素 ;（2）按值查找 ;5．求单链表的长度 ;三、静态链表及其基本操作 ;1．初始化静态链表 ;2．分配结点 ;3．回收结点 ;四、循环链表及其基本操作 ;尾指针（rear）;五、双向链表及其基本操作 ;1．插入数据元素 ;Status DListInsert (DLinkList *L,int i, ElemType e) { //在双向循环链表L中第i个位置插入一个数据元素e DNode *s, *p if (! (p = GetElem (L, i))) return FALSE; //插入位置不合法 s = (DLinkList) malloc (sizeof (DNode) //生成新结点 if (! s) return FALSE; s -> data = e; //将e赋给新结点的数据域 s -> prior = p -> prior; //新结点的前驱指向p结点的前驱 p -> prior -> next = s; //p结点前驱的后继指向新结点 s -> next = p; //新结点的后继指向p结点 p -> prior = s; //p结点的前驱指向新结点 return TRUE; };2．删除数据元素 ;算法描述如下： ;数据结构;项目三 栈和队列;任务一 栈的定义、存储结构和基本操作 ;一、栈的定义及其基