《数据结构域算法设计__数据结构(压缩版)__V》由会员分享，可在线阅读，更多相关《数据结构域算法设计__数据结构(压缩版)__V（40页珍藏版）》请在金锄头文库上搜索。
1、Huazhong Univ. of Sci. and Tech.Wuhan Polytechnic University单片机原理与应用*第4部分 数据结构(压缩版) 1l 学习内容和目标 数据结构的基本知识：指出方向 线性表的概念链表l 注意： 思维一定要开阔一些，多问为什么。 允许不用举手，并随时打断，向我提任何和课程相关的问 题。*2本节学习目标1.1 引论l当前看待程序和软件的主流观点： 程序 = 算法(处理问题的策略) + 数据结构(问题的数学模型) 软件工程的观点：软件 = 程序+文档l数据结构：由若干特性相同的数据元素构成的集合，且在集合上存在 一种或多种关系。即数据的组织形式。
2、*31数据结构概述数学 代数 系统硬件 计算机系 统设计软件 计算机程 序设计数据结构编码理论 数据类型 数据表示 数据运算 数据结构 数据存取三个内容：逻辑结构、存储 结构、基本操作（运算） 数据类型：一个值的集合和 定义在这个值集上的一组操 作。程序设计语言中对于给 定变量的所有可能取值的集 合。 抽象数据类型（ADT）l逻辑结构：S= D , R ；D表示数据元素的集合，R表示元素间关系 的集合 l四种结构：集合、线表、树、图 R1= R2=, R3=, R4=,*41.1 引论(续1)abce fgabcdefga ab bc cd de ef fg ga ab bc ce ef fg
3、 gl存储结构：数据元素的表示 及元素之间关系的表示。 顺 序存储结构 、链式存储结构 l基本操作及其实现：对数据 元素的修改、增加、删除， 移动等。l本课程的讲述特点、目标、和方法： 在同学们的原有基础上，对数据结构进行概括； 由于时间有限，并且是在单片机课程中，因此将挑选几个主要的数据 结构； 采用压缩的方式讲述数据结构，关键在于给出思想和方法； 通过指导培养自学能力； 掌握几种数据结构的思想，并能够处理相关问题；*51.2 教学方法和目标l主要涉及的数据结构：l算法：排序和查找（其他略） 有穷性-执行了有限条指令后一定要终止。 确定性（无二义）- 可（能）行性- 输入数据- 输出数据-*
4、61.3 当前的数据结构2.1 概念和定义l 线性结构： 有且仅有一个头元素 有且仅有一个尾元素 除第一个数据元素外，其余的数据元素有且仅有一个直接前驱 除末尾数据元素外，其余的数据元素有且仅有一个直接后继l 线性表的概念： 线性表是n(n=0)个数据元素的有限序列。 记作：(a1,a2,a3,.ai,.,an) , 下标i表示数据元素在线性表中的位序。 n定义为线性表的长度；n为0表示该线性表为空表。 线性表中的数据元素可以是一个数、一个符号或由多个数据项所构成 的。*72 线性表l 线性表的抽象数据类型(ADT)定义：*82.1 线性表的概念和定义(续1)ADT list 数据对象： 数据
5、关系： 基本操作： InitList( Lb_len=ListLength(Lb) for(i=1;islist=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType);if(!L-slist) return ERROR; /*初始化失败，返回0*/L-length=0; /*置空表长度为0*/L-listsize=INIT_SIZE; /*置初始空间容量*/return OK; /*初始化成功，返回1*/ /*InitList*/l顺序表的插入：在第i个元素之前插入一个新元素，此时因为逻辑结 构发生了变化，相应的存储结构也随之变化，就需要调整顺序表中各 元素
6、的相对位置。l插入算法的基本步骤： 判断插入位置是否超过了表的实际长度； 判断插入后，是否超过了表的实际空间，若发生溢出，则应先增加表 的空间，再完成插入； 为插入的元素空出位置，将插入位置开始的元素依次向后移动，完成 插入； 更新表的实际长度和实际空间大小。*122.4 顺序表的操作(续1)l顺序表的插入示例：*132.4 顺序表的操作(续2)/*在顺序表的第i个位置之前插入新元素e*/ int ListInsert_sq(Sqlist *L,int i,ElemType e)int k;if(iL-length+1) return ERROR; /*插入位置不合法*/if(L-length
7、=L-listsize) /*存储空间满，重新分配空间*/L-slist=(ElemType*)realloc(L- slist,(INIT_SIZE+INCREM)*sizeof(ElemType);if(!L-slist) return ERROR; /*存储分配失败*/L-listsize+=INCREM; /*修改存储空间大小*/for(k=L-length-1;k=i-1;k-) /*插入位置之后元素后移*/L-slistk+1= L-slistk;L-slisti-1=e; /*插入元素*/L-length+; /*顺序表长度加1*/return OK; /*ListInsert*
8、/l顺序表的删除：删除表中第i个位置的元素。l实现步骤： 判断i是否超过当前表的长度； 取出欲删除元素 将该位置后的元素依次向前移动一个位置； 修改当前表的长度*142.4 顺序表的操作(续3)/*在顺序表中删除第i个元素*/ int ListDelete_sq(Sqlist *L,int i)int k;if(iL-length) return ERROR; /*删除位置不合法*/for(k=i-1;klength-1;k+) /*元素前移*/L-slistk=L-slistk+1;L-length-; /*顺序表长度减1*/return OK; l顺序表的插入、删除算法分析：在顺序表中插入
9、和删除元素，其时间 耗费主要在元素的移动上。*152.4 顺序表的操作(续4) 在第i个元素前插入一个新元素，移动元素次数为： n-i+1平均移动次数 删除第i个元素，移动元素次数为： n-i平均移动次数时间复杂度：O(n)l顺序表的查找：在顺序表中查找某个值等于给定值的元素位置。 l实现步骤： 从顺序表的起始位置开始依次比较； 若找到对应的元素，则返回该元素在表中的位置； 若找到表的末尾位置，还未找到，则返回失败标识。l顺序表的特点： 简单直观，容易理解； 能够实现随机存取； 插入和删除需要移动大量的数据元素； 长度相对固定，易导致存储空间的浪费；*162.4 顺序表的操作(续5)l 链表：
10、采用一组任意的存储单元来存放线性表中的数据元素，这些存 储单元可以是连续的，也可以是不连续的。数据元素间的逻辑关系通 过附加信息指针来描述。 l 数据元素除了具有代表其本身信息的数据域外，还有一个用来指示逻 辑关系的指针域。这样的存储方式称为结点。l 链表的实现主要使用结构体：*172.5 线性表的链式表示数据域数据域 datadata指针域指针域 nextnext 结点nodetypedef struct LNodetypedef struct LNodeElemType ElemType datadata； /*/*结点的数据域结点的数据域* */ /struct LNode struct
11、 LNode *next*next；/*/*结点的指针域结点的指针域* */ / LNode,*Llist;LNode,*Llist;若LNode *p，则p的含义是什么？ 若 p 的值非空，则表明 p 指向某个结点，p-data 表示 p 所指结点中的数据域，p-next表示 p 所指结点中的指针域 ，若非空，则指向其“后继“结点。l 线性链表是一种动态存储结构，当线性链表要增加一个结点时，向系 统申请一个存储空间，删除结点时要将空间释放。l 单链表：结点中只有一个指针域*182.5 线性表的链式表示(续1)p=(LNode *)malloc(sizeof(LNode); free(p);不
12、带头结点的单链表， 头指针指向第一个数据 元素带头结点的单链表，头指针指向头 结点，头结点的数据域为空，指针 域为第一个数据元素的地址不带头结点的单链表为 空，则头指针为空，而 带头结点的，则头结点 的指针域为空l 单向循环链表的特点：表中最后一个结点的指针域指向头结点，整个 链表成为一个由链指针相链接的环，并且将头指针设成指向最后一个 结点。空的循环链表由只含一个自成循环的头结点表示。l 问题： 判断有头结点的循环链表是否到达表尾的条件是什么？ 判断循环链表为空的条件是什么？*192.5 线性表的链式表示(续1)头结点空表. .HH非空循环链表l双向循环链表的特点是其结点结构中含有两个指针域
13、，一个指向其直 接后继，一个指向其直接前趋。l循环链表可以看做环形*202.5 线性表的链式表示(续2)l单链表：建立一个空的线性链表。对于带头结点的单链表，设定一个 头指针指向头结点。并且设置头结点的指针域为空。*212.6 链表的创建(续2)Llist InitList_l(Llist H) H=(Lnode *)malloc(sizeof(LNode); /*申请一个头结点*/ if (!H) return ERROR; /*申请失败*/H-next=NULL; /*头结点的指针域置空*/return H;LNode *create_list(int n) LNode *head,*p,
14、*q;int i;p=(LNode*)malloc(sizeof(LNode);head=p;for(i=1;idata=i;q-next=NULL;p-next=q;p=q;return(head); l单链表：建立一个空的线性链表。对于带头结点的单链表，设定一个 头指针指向头结点。并且设置头结点的指针域为空。*222.6 链表的创建(续2)Llist InitList_l(Llist H) H=(Lnode *)malloc(sizeof(LNode); /*申请一个头结点*/ if (!H) return ERROR; /*申请失败*/H-next=NULL; /*头结点的指针域置空*/
15、return H; LNode *create_list(int n) /*n个节点*/ LNode *head,*p,*q;int i;p=(LNode*)malloc(sizeof(LNode);head=p;for(i=1;idata=i;q-next=NULL;p-next=q;p=q;return(head); l双向循环链表的创建*232.6 链表的创建(续2)typedef struct Lnode ElemType data； /*结点的数据域*/struct LNode *next； /*结点的后继指针域*/struct LNode *prior； /*结点的前驱指针域*/
