C++第8章-简单链表及其应用.ppt

(6) erase（）方法删除iterator指定的节点 liststring::iterator testiterator; // iterator类似指针 for (testiterator = test.begin(); testiterator != test.end();) { if(*testiterator ==“no”) //条件判定 testiterator =test.erase(testiterator); else testiterator ++;} assign() 给list赋值?back() 返回最后一个元素?begin() 返回指向第一个元素的迭代器?clear() 删除所有元素?empty() 如果list是空的则返回true?end() 返回末尾的迭代器?erase() 删除一个元素?front() 返回第一个元素?get_allocator() 返回list的配置器?insert() 插入一个元素到list中?max_size() 返回list能容纳的最大元素数量? merge() 合并两个list?pop_back() 删除最后一个元素?pop_front() 删除第一个元素? push_back() 在list的末尾添加一个元素?push_front() 在list的头部添加一个元素?rbegin() 返回指向第一个元素的逆向迭代器?remove() 从list删除元素?remove_if() 按指定条件删除元素?rend() 指向list末尾的逆向迭代器?resize() 改变list的大小?reverse() 把list的元素倒转?size() 返回list中的元素个数?sort() 给list排序?splice() 合并两个list?swap() 交换两个list?unique() 删除list中重复的元素 /sum_tw/article/details 简单链表及其应用 顺序存储结构的优缺点分析 优点： 缺点： 1.无需为表示结点间的逻辑关系而增加额外的存储空间； 2.可方便地随机存取表中的任一元素。 1.插入或删除平均需要移动一半的结点； 2.顺序表要求占用连续的存储空间(不管静态分配还是动态分配)。 过大 浪费 过小 溢出 链表 思考：如何描述一个班的学生基本信息（学号、姓名、年龄等）？ struct student{ int ID; char Name[20]; int age; }stu[30]; 1001 张 18 1002 李 19 1030 钱 18 。。。。。。 stu[0] stu[1] stu[29] 分配固定长度连续空间，操作没有灵活性 如何添加新转入学生信息？ 1. 基本概念 结点(Node)组成 数据域：存储数据元素本身 数据域 指针域 指针域：存储邻接元素的存储地址(位置) 头指针 ： 指向链表头结点的指针。 单链表 双向链表 循环链表 链接方式 每个结点只有一个指针域 每个结点有两个指针域 是一个首尾相接的链表 链表 将若干个同类型的结构体类型数据按一定的原则连接起来。 结点 实体数据 同类型指针 struct student{ int ID; char Name[20]; int age; student *next; }; 指向下一个结点 1001 张 18 1002 李 19 1030 钱 18 。。。。。。 NULL 链表的特点 student *head=首结点; couthead-ID; student *p=head; coutp-Name; p=p-next; coutp-age; 1001 张 18 1002 李 19 1030 钱 18 。。。。。。 NULL 值域 链域 head 首结点 尾结点 链表的特点 结点可不连续存储 操作灵活，便于扩充（动态分配空间） 1001 张 18 1002 李 19 1030 钱 18 。。。。。。 NULL head 1031 王 18 NULL 链表的特点 2000 A 2114 B 2056 C NULL 2000 2114 2056 head A C B free head ? 链表的操作之建立无序链 链表为空(head==0) head=p1; p2=p1; p1用来指向新结点 p2用来指向链表当前尾结点 head p1 data1 p2 链表的操作之建立无序链 链表为空(head==0) head=p1; p2=p1; 链表不为空 p2-next=p1; p2=p