资源描述：
《第11章 数据结构和数据抽象》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第十一章数据结构和数据抽象10/1/20211程序设计基础（C语言）wh本章内容11.1数据抽象11.2线性表11.3堆栈11.4队列小结10/1/20212程序设计基础（C语言）wh11.1数据抽象11.1.1数据结构和数据类型数据结构用来反映数据的内部构成，有逻辑上的数据结构和物理上的数据结构之分。数据类型是一个值的集合和定义在此集合上的一组操作的总称。数据结构是指计算机处理的数据元素的组织形式和相互关系，数据类型是某种程序设计语言中已实现的数据结构。在程序设计语言提供的数据类型支持下，可以根据从问题中抽象出来的各种数据模型，逐步构造出描述这些数据模型的各
2、种新的数据结构。10/1/20213程序设计基础（C语言）wh11.1.2抽象数据类型抽象数据类型(abstractdatatype,ADT)是用户进行软件设计时，从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的一组操作，而不考虑计算机的具体存储结构和操作的具体实现算法。抽象数据类型可用(D,S,P)三元组表示。其中，D是数据对象；S是D上的关系集；P是D中数据运算的基本运算集。其基本格式如下：ADT抽象数据类型名{数据对象：<数据对象的定义>数据关系：<数据关系的定义>基本运算：<基本运算的定义>}ADT抽象数据类型名10/1/20214程序设计基
3、础（C语言）wh11.2线性表11.2.1线性表的定义线性表是具有相同特性的n(n≥0)个数据元素的有限序列，通常记为：(a1，a2，…ai-1，ai，ai+1，…an)其中n为表长，n＝0时称为空表。特点：均匀性：同一线性表的各数据元素必定有相同的数据类型和长度。有序性：有唯一的“第一个”和“最后一个”元素，每个元素只有一个直接前趋和一个直接后续。10/1/20215程序设计基础（C语言）wh11.2.2线性表的基本操作线性表上的基本操作有：(1)线性表初始化：InitList(&L)(2)求线性表的长度：ListLength(L)(3)求线性表中某个数据元
4、素值：GetElem(L,i,&x)(4)按元素值查找：LocateElem(L,x)(5)插入操作：InsertList(&L,i,x)(6)删除操作：DeleteList(&L,i,&x)说明：(1)某数据结构上的基本运算，不是它的全部运算，而是一些常用的基本的运算，而每一个基本运算在实现时也可能根据不同的存储结构派生出一系列相关的运算来。(2)在上面各操作中定义的线性表Ｌ仅仅是一个抽象在逻辑结构层次的线性表，尚未涉及到它的存储结构，因此每个操作在逻辑结构层次上尚不能用具体的某种程序语言写出具体的算法。10/1/20216程序设计基础（C语言）wh11.2
5、.3线性表的顺序存储从结构上考虑，通常线性表的存储类型可以描述如下：typedefstruct{elemtypedata[MAXSIZE];intlength;}SeqList;定义一个顺序表：SeqListL;,有时定义一个指向SeqList类型的指针更为方便：SeqList*L;L是一个指针变量，指向SeqList类型的数据，线性表的存储空间通过如下语句获得：L=(SeqList*)malloc(sizeof(SeqList));10/1/20217程序设计基础（C语言）wh11.2.4顺序表上基本运算的实现【算法11.1】顺序表的初始化SeqList*I
6、nit_SeqList(){SeqList*L;L=(SeqList*)malloc(sizeof(SeqList));L->length=0;returnL;}10/1/20218程序设计基础（C语言）wh【算法11.2】插入intInsert_SeqList(SeqList*L,intI,elemtypex){intj;if(i<1
7、
8、i>L->length+1)return(0);/*检查插入位置的正确性*/for(j=L->length;j>=i;j--)L->data[j]=L->data[j-1];/*向后移动*/L->data[i]=x;/*新元
9、素插入*/L->length++;/*顺序表长度增加1*/return(1);/*插入成功，返回*/}10/1/20219程序设计基础（C语言）wh【算法11.3】删除intDelete_SeqList(SeqList*L,inti){intj;if(i<1
10、
11、i>L->length)/*检查空表及删除位置的合法性*/return(0);for(j=i;j<=L->length-1;j++)L->data[j-1]=L->data[j];/*向前移动*/L->length--;/*顺序表长度减1*/return(1);}10/1/202110程序设计基础（C语
12、言）wh【算法11.4】按值查找int
