资源描述：
《第十三章 数据抽象》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第十三章数据抽象学习目标理解数据抽象原则，了解抽象数据类型的概念理解栈，能使用多种方法实现栈理解队列，能使用多种方法实现队列熟悉符号表的概念，掌握抽象符号表的接口设计原则与基本实现策略熟悉哈希表的概念，了解哈希表设计的关键问题，并能针对具体应用问题进行具体分析13.1抽象数据类型抽象的表现形式行为抽象：函数数据结构抽象：抽象数据类型抽象数据类型的基本概念仅关心类型的行为，不关心数据的具体实现细节C语言中的基本数据类型：仅关心如何使用数据，而不关心如何表示这些数据抽象数据类型的划分：依据数据之间的关系线性
2、数据结构与非线性数据结构线性数据结构与非线性数据结构线性数据结构非线性数据结构13.2线性表类型线性表定义或为空表，或为数据类型相同的一组数据，且各元素只有一个直接前驱和一个直接后继表头元素只有后继没有前驱表尾元素只有前驱没有后继线性表抽象逻辑抽象：不关心元素的具体数据类型物理抽象：不关心元素的存储格式线性表操作创建新表；在某节点前插入新节点；在某节点后插入新节点；获得某个指定节点值；设置某个指定节点值；删除某个指定节点；删除线性表；获得当前元素的下一个元素；获得当前元素的上一个元素；设置当前元素位置；
3、获得当前元素位置；将非空线性表置为空；判断线性表是否为空；判断线性表是否为满；获得线性表长度；线性表操作intCreate(List*pList);intInsertBefore(List*pList,intpos,intvalue);intInsertAfter(List*pList,intpos,intvalue);intGetElement(Listlist,intpos,int*element);intSetElement(List*pList,intpos,intvalue);intDelet
4、eElement(List*pList,intpos);voidDeleteAll(List*pList);intNext(Listlist,int*next);intPrior(Listlist,int*prior);intGetCurPos(Listlist,int*pos);intSetCurPos(List*pList,intpos);voidClear(List*pList);intIsEmpty(Listlist);intIsFull(Listlist);intGetLength(Listl
5、ist,int*length);线性表应用示例主函数voidmain(){inti,temp;Listlist;if(!Create(&list)){printf(“Sorry!“);return;}for(i=0;i<10;i++)InsertBefore(&list,0,i);for(i=0;i<10;i++){GetElement(list,i,&temp);printf(“%d“,temp);}}线性表的顺序表示线性表的存储结构：结构体元素的存储结构：数组typedefstructtag
6、List{int*element;intlength;intcurrent;}List;创生线性表intCreate(List*pList){assert(pList!=NULL);pList–>element=(int*)malloc(MAXSIZE*sizeof(int));if(!pList–>element){printf(“Can‘tmallocmemoryforthelist!“);return0;}pList–>length=0;pList–>current=0;return1;}获取
7、下一元素intNext(List*pList,int*next){assert(pList!=NULL);if(!IsEmpty(*pList)){if(GetElement(*pList,pList–>current+1,next)){pList–>current++;return1;}return0;}return0;}获取上一元素intNext(List*pList,int*next){assert(pList!=NULL);if(!IsEmpty(*pList)){if(GetElement(*
8、pList,pList–>current–1,next)){pList–>current––;return1;}return0;}return0;}前插入元素intInsertBefore(List*pList,intpos,intvalue){inti;assert(pList!=NULL);if(IsFull(*pList)){printf(“Full!“);return0;}if(!IsEmpty(*pList)){if(pos<
