《数据结构域算法设计__数据结构(压缩版)__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; /*结点的前驱指针域*/