资源描述：
《大数据结构(c语言)_2》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、实用文案第二章线性表本章的重点：掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析；难点：使用本章所学的基本知识设计有效算法解决与线性表相关的应用问题。要求达到“识记”的内容：线性表的逻辑结构特征，线性表上定义的基本运算，并利用基本运算构造出较复杂的运算。要求达到“综合应用”的内容：顺序表的含义及特点，顺序表上的插入、删除操作，解决简单应用问题。链表如何表示线性表中元素之间的逻辑关系；单链表、双链表、循环链表链接方式上的区别；单链表上实现的建表、查找、插入和删除等基本算法及其时间复杂度。循环链表上尾指针取代
2、头指针的作用，以及单循环链表上的算法与单链表上相应算法的异同点。双链表的定义和相关算法。利用链表设计算法解决简单应用问题。要求达到“领会”的内容：顺序表和链表的比较，以及如何选择其一作为其存储结构才能取得较优的时空性能。线性结构的特点：在数据元素的非空有限集中，⑴存在唯一的一个被称做“第一个”的数据元素；⑵存在唯一的一个被称做“最后一个”的数据元素；⑶除第一个之外，集合中的每个数据元素均只有一个前驱；⑷除最后一个之外，集合中每个数据元素均只有一个后继。2.1线性表的逻辑结构一、线性表的定义线性表是最常用且最简单的一
3、种数据结构。一个线性表是n个数据元素的有限序列。数据元素可以是一个数、一个符号、也可以是一幅图、一页书或更复杂的信息。线性表例：1、1234567标准文档实用文案2、3、学号姓名语文数学C语言6201001张三8554926201002李四9284646201003王五8774736201004 ... 数据元素也可由若干个数据项组成（如上例3）。这时常把数据元素称为记录。含有大量记录的线性表又称文件。线性表中的数据元素类型多种多样，但同一线性表中的元素必定具有相同特性，即属同一数据对象，相邻数据元素之
4、间存在着序偶关系。a1...ai-1aiai+1...anai是ai+1的直接前驱元素，ai+1是ai的直接后继元素。线性表中元素的个数n定义为线性表的长度，为0时称为空表。在非空表中的每个数据元素都有一个确定的位置。ai是第i个元素，把i称为数据元素ai在线性中的位序。二、线性表的类型定义⒈抽象数据类型线性表的定义如下：ADTList{数据对象:D={ai
5、ai(-ElemSet,i=1,2,...,n,n>=0}数据关系:R1={
6、ai-1,ai(-D,i=2,...,n}基本操作：InitL
7、ist(&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())}ADTList2、部分操作的类C实现：InitList(&L){L.elem=(E
8、lemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;returnOK;}//InitListGetElem(L,i,&e){*e=L.lem[i]}//GetElemListInsert(List&L,inti,ElemTypee){if(i<1
9、
10、i>L.length+1)returnERROR;q=&(L.elem[i-1]);for(p=&
11、(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;*q=e;++L.length;returnOK;}//ListInsertvoidunion(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))ListI
12、nsert(La,++La_len,e);}//unionvoidMergeList(ListLa,ListLb,List&Lc)//巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。{InitList(Lc);i=j=1;k=0;La_len=ListLength(La
