C++程序设计 丁亚涛 第10章 链表.ppt

《C++程序设计 丁亚涛 第10章 链表.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、链表10用数组来存储数据，有存取效率高，方便等特点。但是，数组的元素个数不能动态扩充，大小固定，不适用于数据元素个数动态增长的数据。在数组中进行数组元素的插入与删除，需要移动其它数据元素，从而保持数组中数据元素的相对次序不变，这就造成了数组中数据的插入与删除的效率很低。而链表适用于数据元素频繁的插入与删除，其存储空间可以动态增长。10.1链表概述1.单链表的结构(1)单链表中构成链表的结点只有一个指向直接后继结点的指针域。其结构特点：逻辑上相邻的数据元素在物理上不一定相邻。数据域：存储元素数值数据，指针域：存储直接后继的存储位置。(2)头指针、头结点头指针是指向链表中第一

2、个结点（或为头结点、或为首元结点）的指针；头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息，它不计入表长度。10.2链表类templateclassLinList;templateclassListNode{friendclassLinList;private:ListNode*next;Tdata;public:ListNode(ListNode*ptrNext=NULL){next=ptrNext;}ListNode(constT&item,ListNode*ptrNext=NULL)

3、{data=item;next=ptrNext;}~ListNode(void){}}；2.结点类的定义和实现单链表类的定义：templateclassLinList{private:ListNode*head;//头指针intsize;//当前的数据元素个数ListNode*Index(inti);//定位public:LinList(void);//构造函数~LinList(void);//析构函数intSize(void)const;//取当前数据元素voidInsert(constT&item,inti);//插入TDelete(int

4、i);//删除TGetData(inti);//取数据元素};3.单链表类的定义和实现所设计的单链表带头结点，所以构造函数要用new运算符动态申请一个头结点并由头指针指示，初始时当前数据元素个数为0，程序如下：templateLinList::LinList()//构造函数{head=newListNode();//头指针指向头结点size=0;//size的初值为0}单链表所有结点都是用动态内存分配方法分配的内存空间，所以析构函数要完成单链表中所有结点内存空间的释放。实现方法如图示：单链表类的实现单链表类的实现单链表类的实现单链表类的实现循环

5、单链表是单链表的另一种形式，其结构特点是链表中最后一个结点的指针域指向整个链表的第一个结点，从而使链表形成一个环。它的优点是从链尾到链头比较方便。循环单链表也有带头结点和不带头结点两种结构。一个带头结点的循环单链表如下图示：4．循环单链表双向链表是每个结点除后继指针域外还有一个前驱指针域，它有带头结点和不带头结点，循环和非循环结构，双向链表是解决查找前驱结点问题的有效途径。结构如图所示：5．双向链表循环双向链表的插入过程循环双向链表的删除过程5．双向链表实现顺序存储结构的方法是使用数组。数组把线性表的数据元素存储在一块连续地址空间的内存单元中，这样线性表中逻辑上相邻的数据

6、元素在物理存储地址上也相邻。数据元素间的逻辑上的前驱、后继逻辑关系就表现在数据元素的存储单元的物理前后位置上。顺序表一般采用静态数组方法实现数据元素存储。10.3顺序表10.4程序示例例10－1在单链表中设计一个插入数据元素x的操作，要求插入后的单链表总数据元素从小到大有序排列。然后设计一个测试主函数进行测试。templatevoidLinListSort(LinList&L){ListNode*curr,*pre,*p,*q;p=L.head->next;//原单链表L.head->next=NULL;//新单链表while(p!=NULL)

7、{curr=L.head->next;pre=L.head;while(curr!=NULL&&curr->data<=p->data){pre=curr;curr=curr->next;}q=p;p=p->next;q->next=pre->next;pre->next=q;}}voidmain(void){LinListmyList;ints[]={1,3,9,11,8,6,22,16,15,10},n=10;inttemp;for(inti=0;i