指针构成的链表及链表的用途

1、Linear ListLinear List & Sequential ListsLinear Lists1.Conception of Linear List2.The ADT of Linear List3.What is Sequential List4.How to build a Sequential List5.To Implement Polynomial Addition Using Sequential ListLinear Lists1Conception of Linear ListnLinear List is a finite, ordered sequenc

2、e of data items known as elements.qData items must belong to same data type. qOperations do not depend on the elemental data type.qEmpty lists, sorted lists, and unsorted lists.qthe length, head, tail4线性表的定义及特点线性表n(n0)个具有相同特性的数据元素的有限序列其中n表示线性表的长度长度，即数据元素的个数n=0时表为空表空表n0时记为:（a1, a2， ai-1， ai， ai+1， an

3、）基本特征有且只有一个“第一元素”，有且只有一个“最后元素”除第一元素之外，其它元素都有唯一的直接前驱前驱（前趋）除最后元素之外，其它元素都有唯一的直接后继后继Linear Lists元素的含义n数据元素在不同问题中的含义各不相同n可以是一个数、一个符号，一个记录，或其它更复杂的信息n这里的学生成绩表是一个线性表n数据元素是每一个学生的信息，包括：学号、姓名、成绩共三个数据项学号学号姓名姓名计算机导论计算机导论04081101陈小洁陈小洁8004081102马丽丽马丽丽7504081103林春英林春英8204081104王澄娟王澄娟9004081150张吉祥张吉祥70Linear ListsA

4、DT LinearList Data object：D ai | ai ElemType, i=1,2,.,n, n0 Relation ：R1 |ai-1 ,aiD, i=2,.,n Operations ：Create (); 创建一个线性表Destroy(); 销毁一个线性表IsEmpty(); 判断线性表是否为空Length(); 获得线性表的长度GetValue(k,i);求线性表中第i个元素IndexOf(x); 查找满足给定条件的数据元素Del(k,i); 删除线性表中的第i个数据元素Add(k,i); 在线性表的第i个位置之前插入一个新的数据元素7n基本运算qInit（）；初始

5、化线性表qClear（）；表置空qPre（）；查找表中第i个元素的前驱qNext（）；查找表中第i个元素的后继qPrint（）；显示表中的数据qSetStart（）；定位线性表第一个元素qSetEnd（）；定位线性表最后一个元素n实际应用中，根据不同的要求选择适当的基本运算解决问题Linear ListsLinear Listsnha和hb分别是两个线性表，他们代表两个的数据元素排列非递减有序的数字序列串，要求使用线性表的基本操作，实现这两个数字串的合并操作Merge ()，产生一个新的数据元素非递减有序的数字串hc。 Linear ListsnMerge()ha.setstart(); hc

6、.setStart();for(int i = 1 ;i= ha.length; i+)tmpdata = ha.getValue();hc.insert(tmpdata);hc.next(); ha.next();hb.setStart();for(int i = 1; i = hb.length; i+)tmpdata = hb.getValue();hc.setStart(); tmpdata2 = hc.getValue();while(tmpdata2 tmpdata) hc.next(); tmpdata2 = hc.getValue(); hc.insert(tmpdata);h

7、b.next()nnTime Cost ha.length + ha.length*hb.lengthLinear ListsnMerge()ha.setStart(); hb.setStart();hc.setStart();int i= 1,j=1;While(i= ha.Length & j=hb.Length)tmp1= ha.getValue(i); tmp2 = hb.getValue(j);if(tmp1= tmp2) hc.insert(tmp1); ha.next(); else hc.insert(tmp2); hb.next();hc.next(); While(

8、i= ha.Length) tmp1= ha.getValue(i); ha.next(); hc.insert(tmp1); hc.next(); While(j= hb.Length) tmp2= hb.getValue(j); hb.next(); hc.insert(tmp2); hc.next(); nnTime Cost: ha.length + hb.lengthLinear Lists4Implementation of ListsnThere are two standard approaches to implementing lists, qthe array-based

9、 list, （顺序存储结构）qthe linked list.（链式存储结构）Sequential Listsn在内存中开辟连续的存储空间，用连续的存储单元依次存放线性表的数据元素n顺序存储的线性表，称为顺序表特点逻辑上相邻的数据元素，其物理位置也相邻利用物理位置上的关系，反映元素的逻辑关系The elements are stored in a consecutive storage area one by one Sequential ListsnWith ordered pair to express “Storage is adjacent to” ， nLoc(ai)=loc(ai

10、-1)+CnUnnecessary to store logic relationship nFirst data component location can decide all data elements locations nData members :Datatype elementsMaxNumber;int size ;Sequential ListsnBasic operations:/* Initialize a List, Set size to 0, Set space to NULL*/Void Init()int i = 0;size = 0;for(i = 0;i

11、MaxNumber; i+)elementsi = NULL;Sequential ListsThe Method isEmptyn/* return true if the List is empty */ boolean isEmpty() if(size = = 0) retun true;elsereturn false;The Method getValuen/* return element with specified index*/datatype getValue(int index)if(index = size)printf(“the input error”)；retu

12、rn NULL;elsereturn elements index;The Method IndexOfn /* return index of first occurrence of the Element, return -1 if theElement not in list */int IndexOf(datatype theElement)/ search element for theElementint i = 0;for (int i = 0; i size; i+)if (element i .equals(theElement)return i;/ theElement n

13、ot foundreturn -1; n插入算法q在线性表的第i个数据元素前，插入一个新数据元素，使线性表的长度从n变成n+1n(a1, , ai-1, ai, , an)n(a1, , ai-1, x, ai, , an) The Method Add内存a1a2aiai+1an01i-1 下标len-1ilen12i元素序号i+1lenlen+1内存a1a2aiai+1an01i-1 下标len-1ilen12i元素序号i+1lenlen+1an-1xThe Method Addn判断线性表的存储空间是否已满，若已满，则进行“溢出”处理n检查i值是否超出允许的范围(1ilen+1)，若超出

14、，则进行“超出”处理n如果上述条件都允许,则将最后一个元素到第i个元素依次向后移动一个位置n将新的数据元素写到第i个位置上n线性表的长度增加1,插入成功The Method AddThe Method Addvoid add(Object theElement, int index)if(index size)printf(“the index error”)；else/ right one positionfor (int i = size - 1; i = index; i-) elementi + 1 = elementi;elementindex = theElement;size+;

15、Time cost of Addn插入算法的主要时间用于移动数据元素，该语句循环执行的次数为n-i+1n当i=n+1时，移动次数为0n当i=1时,移动次数为nn算法的最坏情况时间复杂度：O(n)n算法的最好情况时间复杂度：O(1)Average time cost of AddnTo get the average shift times of the insertnSet to insert an element at the position i, the shift times is size i +1nAnd the probability of this operation is 1

16、/size+1nThe average cost is =size/211)1(11sizeiisizesizeThe Method Deln删除操作q将线性表的第i个数据元素删去，使长为n的线性表变成长为n-1的线性表q(a1 ,.,ai-1 ,ai ,ai+1 ,.,an )q(a1 ,.,ai-1 ,ai+1 ,.,an )The Method Del内存a1a2aiai+1an01i-1 下标n-1in12i元素序号i+1nn+1内存a1a2ai+1 下标01i-1n-2in-112i元素序号i+1n-1nanai+2The Method Deln算法思路q判断i值是否超出允许的范围(

17、1ilen），若是，则进行“超出范围”处理；q否则，保存第i个元素的值；q将第i个元素后的所有元素依次向前移动一个位置；q线性表长度减1，删除成功The Method Deldatatype Del(int index)if(index = size)打印输出(“the input error”)；return NULL;else/ valid index, shift elements with higher indexdatatype delElement = elementindex;for (int i = index + 1; i Max - 1) output (“Error”); exit(-1);ck .coef = co; ck .exp = e;poly polyAdd(struct poly a, struct poly b, struct poly c, int at, int bt) int i