数据结构(C语言版)第2章线性表

《数据结构(C语言版)第2章线性表》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构(DataStructures)(C语言版)主讲教师：吴让仲Instructor:WU,RANGZHONGE-mail:wurangzhong@163.com第二章线性表2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.3.1线性链表2.3.2循环链表2.3.3双向链表2.4一元多项式的表示及相加2.1线性表的逻辑结构线性表(LinearList)：由n(n≧0)个数据元素(结点)a1，a2，…an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表(n>0)记作：(a1，a2，…an)这里的数据元素a

2、i(1≦i≦n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。例1、26个英文字母组成的字母表（A，B，C、…、Z）例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况。（6，17，28，50，92，188）例3、学生健康情况登记表如下：姓名学号性别年龄健康情况王小林790631男18健康陈红790632女20一般刘建平790633男21健康张立立790634男17神经衰弱……..……..…….…….…….例4、一副扑克的点数（2，3，4，…，J，Q，K，A）从以上例子可看出线性表的逻辑特征是：在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有

3、一个直接后继a2；有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋an-1；其余的内部结点ai(2≦i≦n-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。线性表是一种典型的线性结构。数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。抽象数据类型的定义为：P19抽象数据类型线性表的定义ADTList{数据对象：D={ai=ai∈ElemSet，i=1，2，…，n，n≧0}数据关系：R1={

4、ai-1，ai∈D,i=2,..,n}基本操作：InitList(&L);Destory(&L);ClearList(&L)；Li

5、stEmpty(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);}§2TheListADTObjects:(item0,item1,,itemN1)Operations:Findingthelength,N,ofalist.Printingalltheitemsinalist.Makinganemptylist.Fin

6、dingthek-thitemfromalist,0k

7、,}【Definition】AnAbstractDataType(ADT)isadatatypethatisorganizedinsuchawaythatthespecificationontheobjectsandspecificationoftheoperationsontheobjectsareseparatedfromtherepresentationoftheobjectsandtheimplementationontheoperations.算法2.1例2-1利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=A∪B。voidUnion(Sq

8、List*La,SqListLb){ElemTypee;intLa_len,Lb_len;inti;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);}}算法2.2例2-2巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一