[工学]03第二章 基本数据结构及其运算中_40学时.ppt

计算机软件技术基础 第二章 数据结构及其运算（中） 2.3 线性链表及其运算 2.3.1 线性链表的基本概念 线性表的顺序存储结构的优点： 存储数据元素方便； 插入与删除算法结构比较简单。 线性表的顺序存储结构的缺点： 除了栈与队列，在一般情况下，要在顺序存储的线性表中插入一个新元素或删除一个元素的效率不高；平均而言，插入或者删除一个元素，大约需要移动表中一半的元素。 存储空间分配难题：当有多个大小不定的线性表同时存在时，若事先为每一个线性表都分配一个最大空间，则会造成存储空间的浪费。 线性表的容量不易扩充。顺序存储结构的特点是对应的存储空间必须连续，而线性表要扩充容量，必须在原存储空间的后部接地址连续的存储空间。在实际应用中，很难实现。 1. 线性链表 线性链表（Linked List）是线性表的链式存储结构。 在线性链表中，数据元素的存储空间一般是不连续的（即可以连续也可以不连续）。 每一个数据元素（线性链表中的一个结点）由两部分信息组成： 数据元素的值； 数据元素在线性表中的逻辑位置。 结论 线性链表是这样一种存储结构：它由若干个结点组成，每个结点有两个域： 数据域：用以存放数据元素的值； 指针域：用以存放后件的存储地址（即后件结点的存储序号）。 用链式结构表示线性表时，每个结点的存储地址可以任意分配，即表中各元素的存储位置可以不连续且是无序的，而它们的逻辑顺序由链表中的指针来确定。 图2.21 线性链表的逻辑状态（第54页） 线性链表的逻辑状态及链表的结点结构 线性表： 其它基本C++操作 在C++中，用户可以利用malloc函数向系统申请分配链表结点的存储空间： malloc( 存储区字节数 ) 该函数返回存储空间的首地址。例如， malloc( m*sizeof( node ) ) 为申请分配能存放m个链表结点node类型数据的存储空间，返回这个存储空间的首地址。 在C++中，也可以用new运算符申请分配链表结点的存储空间，其形式为 new 类型名 或 new 类型名[m] 其结果为存储空间的首地址。例如， new node 为申请分配能存放一个链表结点node类型数据的存储空间，返回这个存储空间的首地址。而 new node[m] 为申请分配能存放m个链表结点node类型数据的存储空间，返回这个存储空间的首地址。 #include iostream using namespace std; struct node //定义结点类型 { int d; //数据域 node *next; }; //指针域 int main( ) { node *p; //定义该类型的指针变量p … p = new node; //申请分配结点存储空间 … delete p; //释放结点存储空间 return 0; } 举例：扫描线性链表 strunct node { char name[10]; //数据域 char sex; //数据域 node *next; //指针域 }; 数据域包含两个数据项：一是包含10个字符的数组（字符串），用于表示姓名；二是字符类型数据，用于表示性别。 指针域用于连接两个结点间的前后件关系。 举例：扫描线性链表 对于线性链表，可以从头指针开始，沿各结点的指针扫描到链表中的所有结点。 算法：从头指针head开始，依次输出各结点值。 #include iostream using namespace std; struct node { char name[10]; //数据域 char sex; //数据域 node *next; //指针域 }; void prtll( node *head ) { node *p; p = head; while ( p!=NULL ) { cout“name=”p-nameendl; cout“sex=”p-sexend; p = p-next; } return; } 线性单链表：表中每一个结点只有一个指针域，由这个指针只能找到后件结点。 如果链表中的每个结点设置了两个指针：左指针（Llink）和右指针（Rlink），分别指向该结点的后件和前件。 2. 带链的栈、3. 带链的队列 栈也是线性表，也可以采用链式存储结构。 2.3.2 线性链表的基本运算 在线性链表中包含指定元素的结点之前插入一个新元素。 在线性链表中删除包含指定元素的结点。 将两个线性链表按要求合并成一个线性链表。 将一