数据结构c版第2章线性表

《数据结构c版第2章线性表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2.3线性表的链接存储结构及实现静态存储分配：在编译时为变量分配内存，并且一经分配就始终占有固定的存储单元，直到该变量退出其作用域。动态存储分配：在程序的运行期间根据实际需要随时申请内存，并在不需要时释放。C++中动态存储分配是通过指针实现的。静态存储分配顺序表事先确定容量链表动态存储分配运行时分配空间链式存储分配的特点：根据线性表的长度动态的申请存储空间，以解决顺序存储中存在的存储空间难以确定的问题。链式存储结构的实现单链表双向链表循环链表等单链表：线性表的链接存储结构之一。存储思想：用一组任意的存储单元存放线性表的元素。连续不连续零散分布存储特点：逻辑次序和物

2、理次序不一定相同。2.元素之间的逻辑关系用指针表示。例：(a1,a2,a3,a4)的存储示意图单链表0200020803000325…………a10200a20325a30300a4∧单链表单链表是由若干结点构成的；单链表的结点只有一个指针域。data：存储数据元素next：存储后继结点的地址datanext单链表的结点结构：数据域指针域0200020803000325…………a10200a20325a30300a4∧结点数据域指针域单链表templatestructNode{Tdata;Node*next;//此处也可以省略};如何申

3、请一个结点？datanext单链表的结点结构：单链表p=newNode;templatestructNode{Tdata;Node*next;};datanext单链表的结点结构：……pNode单链表p=newNode;datanext……pNode如何引用数据元素？p->data;*p.data;data如何引用指针域？nextp->next;区分：指针变量、指针、指针所指结点、结点的值P60单链表单链表0200020803000325…………a10200a20325a30300a4∧firsta1a2an∧非空表fi

4、rst=NULL空表重点在数据元素之间的逻辑关系的表示，所以，将实际存储地址抽象。什么是存储结构？单链表0200020803000325…………a10200a20325a30300a4∧firsta1a2an∧非空表first=NULL空表头指针：指向第一个结点的地址。尾标志：终端结点的指针域为空。单链表0200020803000325…………a10200a20325a30300a4∧firsta1a2an∧非空表first=NULL空表空表和非空表不统一，缺点？如何将空表与非空表统一？单链表头结点：在单链表的第一个元素结点之前附设一个类型相同的结点，以便空表和非

5、空表处理统一。非空表firsta1a2an∧空表first∧单链表templateclassLinkList{public:LinkList()；LinkList(Ta[],intn);~LinkList();intLength();TGet(inti);intLocate(Tx);voidInsert(inti,Tx);TDelete(inti);voidPrintList();private:Node*first;//单链表的头指针,可以省略};单链表类的声明单链表的实现——按位查找操作接口TGet(inti):查找第i个元素并返回

6、其值核心操作（关键操作）：工作指针后移。从头结点（或开始结点）出发，通过工作指针的反复后移而将整个单链表“审视”一遍的方法称为扫描（或遍历）。firsta1pa2pan∧aipp查找成功p查找失败1.工作指针p初始化;累加器j初始化;2.1工作指针p后移;2.2累加器j加1;2.循环直到p为空或p指向第i个结点3.若p为空，则第i个元素不存在，抛出查找位置异常；否则查找成功，返回结点p的数据元素；单链表的实现——按位查找算法描述——伪代码单链表的实现——按位查找templateTLinkList::Get(inti){p=first->next;j

7、=1;while(p&&jnext;j++;}if(!p)throw"位置";elsereturnp->data;}算法描述——C++描述p++能否完成指针后移？a1a2ppp复杂性分析templateTLinkList::Get(inti){Node*p;intj;p=first->next;j=1;//或p=first;j=0;while(p&&jnext;//工作指针p后移j++;}if(!p)throw"位置";elsereturnp->data;}查找算法的基本语句是工作指针p后移，该语句执

8、行的次数与