list链表

《list链表》由会员分享，可在线阅读，更多相关《list链表（39页珍藏版）》请在金锄头文库上搜索。

1、,链表 List,大连理工大学软件学院,开发员工工资管理系统,每个员工的数据包括职工号、姓名、生日和工资。用什么数据结构表示员工的信息?公司有n名员工，用什么容器存储多条员工记录；如何输入并输出员工的信息? 交互界面如何设计?需要什么功能? 基本操作(增/删/改/查)统计功能(排序/平均值),大连理工大学软件学院,结构体与指针,结构体struct- 用户自定义的新数据类型 在结构体中可以包含若干个不同数据类型和不同意义的数据项，即若干数据项的一个聚合。 结构体相当于 “记录 record” 。,员工编号 员工姓名 员工工资,员工 结构体,大连理工大学软件学院,结构体应用,结构的嵌套定义日期结构

2、体定义时间结构体 如何显示系统时间,结构成员不能是自身的结构变量，但可用一个指向自身结构的指针作为成员 链表,大连理工大学软件学院,1. 存储分配的方式 顺序表的存储空间是静态分配的 链表的存储空间是动态分配的2.存取方式 顺序表可随机/顺序存取 链表必须顺序存取3.插入/删除操作,数组 vs. 链表,大连理工大学软件学院,数组的插入操作,25 34 57 16 48 09 63 ,0 1 2 3 4 5 6 7,50,插入 x,25 34 57 50 16 48 09 63 ,0 1 2 3 4 5 6 7,50,i,大连理工大学软件学院,/在表中第 i 个位置插入新元素 xint Inse

3、rt (Array /插入成功 ,数组 的插入操作,大连理工大学软件学院,数组的删除操作,25 34 57 50 16 48 09 63 ,16,删除 x,25 34 57 50 48 09 63 ,0 1 2 3 4 5 6 7,大连理工大学软件学院,/在表中删除已有元素 x int Delete ( Array /表中没有 x,数组的删除操作,大连理工大学软件学院,1. 数据的存储方式2.数据的存取方式3.插入/删除操作 顺序表平均需要移动近一半元素 链表不需要移动元素，只需要修改指针例如:集合的合并操作,数组 vs. 链表,大连理工大学软件学院,每个元素由结点(Node)构成, 包括两个

4、域:数据域Data和指针域Link,data link,存储结构：链式存储结构 存储特点：存储单元可以不连续。 存取方式：顺序存取,Node,1.单链表结构,data link,data link,大连理工大学软件学院,2.单链表的类型定义,struct Stu int num;char name10;double score; Stu * next; ;,struct Stu ;struct Node /链表结点 Stu data; /结点数据域Node * link; /结点链域 ;Node * pHead; /链表头指针,大连理工大学软件学院,2.单链表的类型定义,class Stu;

5、/数据类 class StuNode /节点类 public:StuNode( );StuNode( );void print(); private:Stu s;StuNode* pNext; ,class StuList/链表类 public:StuList( );StuList( );int getNum( );void Add( Stu ,大连理工大学软件学院,2.单链表的类型定义 链表类模板,template class Node / 结点类模板 public:Node( );Node( const T,大连理工大学软件学院,template class List public:Lis

6、t( int s= 0);List( ); / void clear( );void insert( Node,2.单链表的类型定义 链表类模板,大连理工大学软件学院,链表的创建过程： 定义链表结点的数据结构； 创建一个空表，头指针为空； 向系统申请分配一个结点空间； 将新结点的成员赋值（指针成员赋值为空）； 若是空表，将新结点连接到表头；若是非空表，将新结点接到表尾。 判断是否有后续结点要接入链表若有转到3)继续增添节点，否则结束。,2. 链表的创建,大连理工大学软件学院,List:List( int size =0 ) Node* pCur;pHead = pTail = pCur = 0

7、; for(int i = 0; i; / 创建新节点 if( !pHead) /添加第一个节点pHead = pCur;else /在链尾追加节点 pTail-pNext = pCur;pTail = pCur ; /更新尾节点 ,2. 链表的创建,Insert(*pCur); insertFront( const T /在当前节点前插入,大连理工大学软件学院,pHead,NULL,pCur,pCur,pCur,pCur,pCur,pCur,pCur,单链表的创建,大连理工大学软件学院,找到表头。 若是空表则退出； 若是非空表，输出结点的值成员 跟踪链表的增长，即找到下一个结点的地址。 转到

8、2)，直至遍历到链尾。,2. 遍历动态链表,NULL,大连理工大学软件学院,/遍历链表 void List:showList( ) pCur = pHead; while( pCur != NULL ) pCur-getNode();pCur = pCur-next;,NULL,大连理工大学软件学院,3. 查找和修改链表节点,NULL,bool findNode( T key ); Node* findNode( T key);,大连理工大学软件学院,插入链表结点操作要保证不破坏链表的连接关系，往往还包含查找的子过程,插入分三种情况 结点插入的位置在链首 结点插入的位置在链中 结点插入的位置在

9、链尾,4. 插入链表节点,NULL,大连理工大学软件学院,插入分三种情况 1） 在第一个结点前插入insertFront( const T* pNew );pNew-pNext = pHead; pHead = pNew;,（插入前） （插入后）,大连理工大学软件学院,插入分三种情况 2）在链表中间插入pCur= findNode( key );pNew-pNext = pCur-pNext; pCur- pNext = pNew；,(插入前) (插入后),pNew,pCur,大连理工大学软件学院,插入分三种情况 3) 在链表末尾插入insertRear(const T* pNew ); pT

10、ail -pNext = pNew; pTail = pTail -pNext ; pNew-pNext = Null；,pTail,(插入前) (插入后),pNew,大连理工大学软件学院,删除整个链表操作要保证不破坏链表的连接关系， 逐个删除链表的所有节点。,5. 删除链表,PCur,NULL,PCur,head,bool delList( ); List:List（）；,大连理工大学软件学院,删除链表结点操作要保证不破坏链表的连接关系，往往还包含查找的子过程。删除链表结点，要考虑下面三种情况： 链表为空时不能执行删除操作 要删除的结点在链首 要删除的节点不在链首,6. 删除链表节点,大连理

11、工大学软件学院,在单链表中删除ai结点pCur = find(Key); /要删除的前驱pDel = pCur-pNext; /Node ai pCur-pNext = pDel-pNext;,删除前,删除后,大连理工大学软件学院,如何在程序中来描述该列火车？ 如何来描述火车头？ 如何来描述每一个集装箱？ 如何来描述各节车厢之间的链接关系？,大连理工大学软件学院,带表头结点的单链表,表头结点位于表的最前端，本身不带数据，仅标志表头。 设置表头结点的目的-简化链表操作的实现。,大连理工大学软件学院,单向链表循环链表双向链表,End Node,Head Node,大连理工大学软件学院,循环链表 (

12、Circular List),特点:最后一个结点的 link 指针不为NULL，而是指向头结点。只要已知表中某一结点的地址，就可搜寻所有结点的地址。 存储结构:链式存储结构带表头结点的循环链表,an-1,first,a1,a0,first,(空表),(非空表),大连理工大学软件学院,双向链表 (Doubly Linked List),双向链表结点结构：,prior data next,指向直接前驱 指向直接后继,非空表 空表,first,first,大连理工大学软件学院,课后练习,1、采用链式存储结构时，要求内存中可用存储单元的地址（ ）。 A、必须是连续的 B、部分地址必须是连续的 C、一定

13、是不连续的 D、连续或不连续都可以。2、在一个单链表中，若在所指结点之后插入所指结点，则执行（ ）。 、s-next=p;p-next=s; 、s-next=p-next;p-next=s; 、s-next=p-next;p=s; 、p-next=s;s-next=p;,大连理工大学软件学院,课后练习,3、在一个单链表中，已知q是p的前趋结点，若q和p之间插入结点s，则执行（ ）。 、s-next=p-next;p-next=s; 、p-next=s-next;s-next=p; 、q-next=s;s-next=p; 、p-next=s;s-next=q;,大连理工大学软件学院,课后练习,二、程序设计题 1、设计类模板List，实现链表的各种基本操作（链表节点的插入和删除，链表的构建和清空）2、用链表建立两个整数集合，完成以下操作： 集合的并操作，将两个链表按顺序进行合并； 集合的交操作，由共同的节点组成新的链表；,大连理工大学软件学院,课后练习,3、多项式问题实现多项式的存储和计算（相加或相乘）采用链表的优点：多项式的项数可以动态地增长，不存在存储溢出问题。插入、删除方便，不移动元素。,大连理工大学软件学院,多项式链表的相加,AH = 1 - 10x6 + 2x8 +7x14 BH = - x4 + 10x6 - 3x10 + 8x14 +4x18,