大数据结构(C语言)_2.docVIP

第二章 线性表 实用文案 - PAGE 16 标准文档 第二章 线性表 本章的重点：掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析； 难点：使用本章所学的基本知识设计有效算法解决与线性表相关的应用问题。 要求达到“识记”的内容：线性表的逻辑结构特征，线性表上定义的基本运算，并利用基本运算构造出较复杂的运算。 要求达到“综合应用”的内容：顺序表的含义及特点，顺序表上的插入、删除操作，解决简单应用问题。链表如何表示线性表中元素之间的逻辑关系；单链表、双链表、循环链表链接方式上的区别；单链表上实现的建表、查找、插入和删除等基本算法及其时间复杂度。循环链表上尾指针取代头指针的作用，以及单循环链表上的算法与单链表上相应算法的异同点。双链表的定义和相关算法。利用链表设计算法解决简单应用问题。 要求达到“领会”的内容：顺序表和链表的比较，以及如何选择其一作为其存储结构才能取得较优的时空性能。 线性结构的特点： 在数据元素的非空有限集中， ⑴ 存在唯一的一个被称做“第一个”的数据元素； ⑵ 存在唯一的一个被称做“最后一个”的数据元素； ⑶ 除第一个之外，集合中的每个数据元素均只有一个前驱； ⑷ 除最后一个之外，集合中每个数据元素均只有一个后继。 2.1线性表的逻辑结构 一、线性表的定义 线性表是最常用且最简单的一种数据结构。一个线性表是n个数据元素的有限序列。 数据元素可以是一个数、一个符号、也可以是一幅图、一页书或更复杂的信息。线性表例： 1、 1 2 3 4 5 6 7 2、 3、 学号 姓名 语文 数学 C语言 6201001 张三 85 54 92 6201002 李四 92 84 64 6201003 王五 87 74 73 6201004 ? ? ? ? ... ? ? ? ? 数据元素也可由若干个数据项组成（如上例3）。这时常把数据元素称为记录。含有大量记录的线性表又称文件。 线性表中的数据元素类型多种多样，但同一线性表中的元素必定具有相同特性，即属同一数据对象，相邻数据元素之间存在着序偶关系。 a1 ... ai-1 ai ai+1 ... an ai是ai+1的直接前驱元素，ai+1是ai的直接后继元素。 线性表中元素的个数n定义为线性表的长度，为0时称为空表。在非空表中的每个数据元素都有一个确定的位置。ai是第i个元素，把i称为数据元素ai在线性中的位序。 二、线性表的类型定义 ⒈ 抽象数据类型线性表的定义如下： ADT List{ 数据对象: D={ai| ai(-ElemSet,i=1,2,...,n,n=0} 数据关系: R1={ai-1,ai| ai-1,ai(- D,i=2,...,n} 基本操作： InitList(L) DestroyList(L) ClearList(L) ListEmpty(L) ListLength(L) GetElem(L,i,e) LocateElem(L,e,compare()) PriorElem(L,cur_e,pre_e) NextElem(L,cur_e,next_e) ListInsert(L,i,e) ListDelete(L,i,e) ListTraverse(L,visit()) }ADT List 2、部分操作的类C实现： InitList(L) { L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L.elem)exit(OVERFLOW); L.length=0; L.listsize=LIST_INIT_SIZE; return OK; }//InitList GetElem(L,i,e) { *e=L.lem[i] }//GetElem ListInsert(List L,int i,ElemType e) { if(i1||iL.length+1) return ERROR; q=(L.elem[i-1]); for(p=(L.elem[L.length-1]);p=q;--p) *(p+1)=*p; *q=e; ++L.length; return OK; }//ListInsert void union(List La,List Lb) //利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=A∪B。 La_len=ListLength(La);Lb_len=ListLength(Lb); for(i=1;i=Lb_len;i++){ GetElem(Lb,i,e); if(!LocateElem(La,e,equal)) ListInsert(La,++La_len,e); }//union void MergeList(Lis