数据结构（C语言版）课件 第2章线性表.pptxVIP

;第2章线性表

第3章栈和队列

第4章串、数组和广义表;;;;;;;;;2.2案例引入;;Rn(x)?=?Pn(x)?+?Qm(x);;;;;;;;马克思主义唯物论;;图书顺序表;;;线性表的类型定义;线性表的类型定义;线性表的类型定义;线性表的类型定义;线性表的类型定义;;数据的存储结构;线性表的顺序表示又称为顺序存储结构或顺序映像。;是一个典型的线性表的顺序存储结构;;;;;;补充：C语言的动态分配函数（stdlib.h）;补充：数组定义;new类型名T（初值列表）;函数调用时传送给形参表的实参必须与形参在类型、个数、顺序上保持一致。;传值方式;传地址方式－－指针变量作参数;传地址方式－－指针变量作参数;传地址方式－－引用类型作参数;传地址方式－－引用类型作参数;引用类型作形参的三点说明;;#includeiostream.h

#defineN10

intmax(inta[]);

voidmain(){

inta[10];

inti,m;

for(i=0;iN;i++)

cina[i];

m=max(a);

coutthemaxnumberis:m;

};练习;线性表的重要基本操作;操作算法中用到的预定义常量和类型;;;补充：几个简单基本操作的算法实现;补充：几个简单基本操作的算法实现;线性表的重要基本操作;;查找（根据指定数据获取数据所在的位置）;012344;;;;【算法步骤】;;;;【算法步骤】;;;;利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构一致。

;顺序表（顺序存储结构）的特点;;链表的优缺点

;;;线性表的链式表示和实现;如何实现？;;;与链式存储有关的术语;与链式存储有关的术语;与链式存储有关的术语;上例链表的逻辑结构示意图有以下两种形式：;;讨论2.在链表中设置头结点有什么好处？;讨论3.头结点的数据域内装的是什么？;结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。

;链表的优缺点

;练习;;;;单链表基本操作的实现;【算法步骤】;StatusDestroyList_L(LinkListL){

LinkListp;

while(L)

{

p=L;

L=L-next;

deletep;

}

returnOK;

};StatusClearList(LinkListL){

//将L重置为空表

LinkListp,q;

p=L-next;//p指向首元结点

while(p)//没到表尾

{q=p-next;deletep;p=q;}

L-next=NULL;//头结点指针域为空

returnOK;

};;求表长

intListLength_L(LinkListL){

//返回L中数据元素个数

LinkListp;

p=L-next;//p指向第一个结点

i=0;

while(p){//遍历单链表,统计结点数

i++;

p=p-next;}

returni;

};;单链表基本操作的实现;思考：顺序表里如何找到第i个元素？

链表的查找：要从链表的头指针出发，顺着链域next逐个结点往下有哪些信誉好的足球投注网站，直至有哪些信誉好的足球投注网站到第i个结点为止。因此，链表不是随机存取结构。;;;;;;将值为e的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间;;找到ai-1存储位置p。;;（1）找到ai-1存储位置p。

（2）保存要删除的结点的值。

（3）令p-＞next指向ai的直接后继结点。

（4）释放结点ai的空间。

;;删除（删除第i个结点）;;但是，如果要在单链表中进行前插或删除操作，由于要从头查找前驱结点，所耗时间复杂度为O(n)。;;;;;;;;;;;;;;;;双向链表;;;;双向链表的插入;双向链表的插入;双向链表的插入;双向链表的插入;;双向链表的删除;;;单链表、循环链表和双向链表的时间效率比较;;顺序表和链表的比较;;线性表的应用;线性表的合并;依次取出Lb中的每个元素，执行以下操作：;;问题描述：;【算法步骤】－有序的顺序表合并;;将这两个