chapter2 线性表_链表ppt课件.ppt

《chapter2 线性表_链表ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、用一组地址任意的存储单元存放线性表中的数据元素。一、单链表这样：就以“结点的序列”来表示线性表称作链表……a20300……a10200……a3^……020002500300数据元素下一个地址2.3线性表类型的实现－－链式映象尾标志一、单链表抽象得知：元素(数据元素的映象)+指针(指示后继元素存储位置)=结点(表示数据元素及其映象)数据域指针域结点以线性表中第一个数据元素的存储地址作为线性表的地址，称作线性表的头指针。头结点a1a2…...an^头指针头指针有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指

2、针。空指针线性表为空表时，头结点的指针域为空template//模版实现structNode{Tdata;//数据域Node*next;//指针域};二、结点的C++语言描述2.2线性表类型的实现－－顺序映象二、结点的C++语言描述2.2线性表类型的实现－－顺序映象datanextPP为指针变量，简称指针；Pdata（*P.data），值为数据元素；Pnext（*P.next），值为一个指针.三、单链表的C++语言描述2.2线性表类型的实现－－顺序映象四、单链表操作的实现——按位查找TGet(inti)//取第i个

3、数据元素L211830754256∧pppj123在单链表中的实现:基本操作为：移动指针，比较j和i四、单链表操作的实现——按位查找TGet(inti)//取第i个数据元素算法分析算法时间复杂度为:O(n)算法实现TemplateTLinkList::Get(inti){p=firstnext;j=1;while(p&&j

4、ai-1xaiai-1基本操作:查找线性表中第i-1个结点，再修改其后继指针动画演示四、单链表操作的实现——插入voidInsert(inti，Tx)//在i位置插入x算法分析算法实现TemplatevoidLinkList::Insert(intI,Tx){p=first;j=0;//初始化while(p&&j

5、复杂度为:O(n)有序对和改变为ai-1aiai+1ai-1四、单链表操作的实现——删除TDelete(inti)//删除i位置的元素基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。ai-1aiai+1ai-1pq动画演示基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。具体操作：q=p->next;p->next=q->next;e=q->data;//暂存被删掉结点free(q);四、单链表操作的实现——删除算法分析TDelete(inti)//删除i位置

6、的元素时间复杂度:O(n)TemplateTLinkList::Delete(inti){p=first;j=0;//p指针初始化while(p&&j

7、

8、!pnext)throw“位置”;else{q=pnext;x=qdata;pnext=qnext;deleteq;returnx;}}算法实现如何建有n个元素的单链表？链表是一个动态的结构，它不需要予分配空间，因此生成链表的过程是一个结点“逐个插入”的过程。四、单链表操作的实现——建表LinkList(Ta[],i

9、ntn);//建立有n个元素的单链表LinkList（）//建立只有头节点的空链表｛first=newNode(T);firstnext=NULL}例如：在尾部插入元素，建立带头结点的单链表。操作步骤：1）建立一个“空表”；2）输入数据元素a1，建立结点并插入；3）输入数据元素a2，并在a1后面插入；a14）依次类推，直至输入an为止。a1a2templateLinkList::LinkList(Ta[],inta){}算法的时间复杂度为:O(n)first=newNode;firstnext=NULL;//先建立一

10、个带头结点的单链表last=first;for(i=0;i>n;i++){s=newNode;sdata=a[i]//建立结点lastnext=s;las