《数据结构初步》PPT课件.ppt

数据结构初步,IA 事业部,第一部分 数据结构基础知识,主要内容,1.1 线性表以及其应用1.2 栈、队列1.3 排序、查找,1.1 线性表以及其应用（1）,线性表分为静态线性表和动态线性表静态线性表特征：表中节点的存储是连续的，占用一块连续存储区，一般节点的数量是固定的；存储表示如下图数据结构如下图,typedef struct Data_t data;/数据域 int next;/后继域Node_t,*PNode_t;/提供的操作有：初始化、插入、删除等。,1.1 线性表以及其应用（2）,动态线性表特征：表中节点的存储是不连续的，一般节点的数量是不固定的；存储表示如下图数据结构如下图,typedef struct Data_t data;/数据域 Node_t*next;/后继域Node_t,*PNode_t;/提供的操作有：初始化、插入、删除等。,1.1 线性表以及其应用（3）,线性表的应用索引表引出为便于对数据（线性数据和非线性数据）进行检索和更新；定义对数据进行索引的线性表；分类索引可以分为单级索引和多级索引单级索引的图示（如下图）,1.1 线性表以及其应用（4）,多级索引(以2级为例)的图示,1.1 线性表以及其应用（5）,使用索引表的好处可以将一些非线性的问题转换为了线性问题加以解决提高数据检索的效率便于数据的更新,1.2 栈、队列,栈栈的数据结构有什么特点栈有什么样的应用队列队列的数据结构有什么特点队列有什么样的用途,1.3 排序、查找(1),排序常用的排序方法冒泡排序程序:void BubbleSort(int a,n)int i,j;int x;for(i=1;iaj+1)/进行交换 x=aj;aj=aj+1;aj+1=x;,1.3 排序、查找(2),常用的排序方法选择排序程序:void SelectSort(int a,int n)int i,j,k;int x for(i=1;in;i+)/进行n-1次选择和交换 k=i-1;for(j=i;jn;j+)if(ajak)k=j;x=ai-1;ai-1=ak;ak=x;,1.3 排序、查找(3),查找常用的查找方法折半查找折半查找的前提线性表是有序的程序int BinarySearch(int a,int N,int x)int low=0,high=N-1;/定义并初始化区间下界和上界变量 int mid;/定义保存中点元素下标的变量 while(low=high)mid=(low+high)/2;if(x=amid)return mid;else if(xamid)high=mid-1;/在左半侧 else low=mid+1;/在右半侧 return-1;,第二部分 问题与习题,问题,Q1.为了描述并解决先进先出特征的问题，我们一般会采用考虑以下哪种数据结构 A,队列 B,栈 C,树 D,二叉树 Q2.为了描述并解决先进后出特征的问题，我们一般会采用考虑以下哪种数据结构（）。A,队列 B,栈 C,树 D,二叉树Q3.对线性表进行二分法查找，其前提条件是A,线性表以顺序方式存储，并且按关键码值排好序 B,线性表以顺序方式存储，并且按关键码值的检索频率排好序 C,线性表以链接方式存储，并且按关键码值排好序 D,线性表以链接方式存储，并且按关键码值的检索频率排好序,习题,题目10详细参见习题集。,谢谢！,