[计算机软件及应用]数据结构 课件 单链表

《[计算机软件及应用]数据结构 课件 单链表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、单链表数据结构电子教案1特点每个元素(表项)由结点(Node)构成。线性结构结点之间可以连续，可以不连续存储结点的逻辑顺序与物理顺序可以不一致表可扩充单链表(SinglyLinkedChain)datalinka1a2a3a4a5Λfirst2单链表的存储映像free(a)可利用存储空间a0a2a1a3freefirst(b)经过一段运行后的单链表结构3单链表的结构定义在C中定义单链表的结构十分简单：typedefintT;//结点数据的类型typedefstructnode{//结点结构定义T

2、data;//结点数据域structnode*link;//结点链接指针域}ChainNode;//结点命名这是一个递归的定义。在结构定义时不考虑操作，以后在定义和实现链表操作时直接使用结构的成分。4单链表的类定义使用面向对象方法，要把数据与操作一起定义和封装，用多个类表达一个单链表。链表结点(ChainNode)类链表(Chain)类定义方式复合方式嵌套方式继承方式结构方式5classChain;//复合方式classChainNode{//链表结点类friendclassChain;//链表类

3、为其友元类private:intdata;//结点数据,整型ChainNode*link;//结点指针};classChain{//链表类private:ChainNode*first;//表头指针};6classChain{//嵌套方式private:classChainNode{//嵌套链表结点类public:intdata;ChainNode*link;};ChainNode*first;//表头指针public://链表操作………};7//链表类和链表结点类定义(继承方式)classCha

4、inNode{//链表结点类protected:intdata;ChainNode*link;};classChain:publicclassChainNode{//链表类,继承链表结点类的数据和操作private:ChainNode*first;//表头指针};8在复合方式中，链表结点类中声明链表类是它的友元类，这样可以“奉献”它的私有成员给链表类。这种方式灵活。在嵌套方式中，链表结点类是链表类的私有成员，这样限制了链表结点类的应用范围。在继承方式中，链表类声明为链表结点类的派生类，这在实现上是

5、可行的。但在逻辑上是有问题的，如三角形is多边形（继承关系）链表is链表结点（显然概念不准确）9//链表类和链表结点类定义(结构方式)structChainNode{//链表结点类intdata;ChainNode*link;};classChain{//链表类,直接使用链表结点类的数据和操作private:ChainNode*first;//表头指针};//链表中的结点属于链表私有，别人无法访问10单链表中的插入与删除操作插入第一种情况：在链表最前端插入newnode->link=first;f

6、irst=newnode;（插入前）（插入后）firstnewnodenewnodefirst11(插入前)(插入后)第二种情况：在链表中间插入newnode->link=current->link;current->link=newnode；newnodecurrentnewnodecurrent12第三种情况：在链表末尾插入newnode->link=current->link;current->link=newnode；(插入前)(插入后)newnodenewnodecurrentcurre

7、nt13单链表的插入算法boolChain::Insert(inti,intx){//将新元素x插入到第i个结点之后。i从1开始，//i=0表示插入到首元结点之前。if(first==NULL

8、

9、i==0){//空表或首元结点前ChainNode*newNode=newChainNode(x);//建立一个新结点newNode->link=first;first=newNode;//新结点成为首元结点}else{//否则，寻找插入位置ChainNode*current=first;intk=1

10、;14while(klink;k++;}if(current==NULL&&first!=NULL)//链短{cerr<<“无效的插入位置!”;returnfalse;}else{//插入在链表的中间ChainNode*newNode=newChainNode(x);newNode->link=current->link;current->link=newNode;}}returntrue;}