[工学]C2012-d13.ppt

某一组数据的逻辑结构：是n=0个数据元素a1，a2……an-1，an的有序集合。集合中每个元素ai的位置仅取决于元素本身的序号i。 注意：同一集合中的元素必定具有相同的特性。 在计算机内部可以采用两种不同方法来表示这一组数据，它们分别是顺序表表示法和链表表示法。 顺序表示法用一组地址连续的存储单元依次存储数据元素，这种存储结构称为顺序存储结构，并称为顺序表。 顺序表示法的特点 优点： 1）存储密度大、空间利用率高； 2）数据元素逻辑位置相邻，物理位置也相邻。可随机存取，所以称为随机存取结构。 缺点： 1）插入和删除时要移动大量的元素； 2）长度较大的线性表须按最大需要的空间来分配存储空间。 链式存储方式 ? 链式存储结构不要求逻辑上相邻的数据元素在物 理位置上也相邻； 链式存储表示的特点 逻辑上相邻的元素对应的存储位置是通过指针反映的，不要求物理上相邻。进行插入、删除运算时，只需修改被插入位置指针域。 一般不预先分配好足够的存储空间以备使用，当有元素插入时，需临时分配一个空的结点空间，填上信息，插入到链表中；当某个结点不再使用时，应将其存储空间释放。 * * * * 特殊情况在空表中（0的后面）插入新结点 共 74 页 第 * 页 从表头开始将数据结点插入到链表中（插入第一个数据结点） NODE * p; p = (NODE *)malloc( sizeof(NODE) ); //申请结点 gets( p-name ); // 数据存入结点 p-link = head-link; // ① 修改结点指针 head-link = p; // ② 插入到表头 NULL 头指针 表头结点 head p 数据结点 name NULL 链表基础-建立链表的基本方法 共 74 页 第 * 页 在链头插入数据结点（插入下一个数据结点） p = ( NODE * ) malloc( sizeof(NODE) ) ; gets( p-name ); p-link = head-link; // ① 修改结点指针 head-link = p; // ② 插入到表头 p 头指针 表头结点 head 数据结点 name1 NULL 新数据结点 x name2 链表基础-建立链表的基本方法 头指针 表头结点 head name1 NULL name2 共 74 页 第 * 页 将结点插入到链表的链头（程序） 调用create函数时，已经建立好表头结点。 head = ( NODE * ) malloc( sizeof(NODE) ); head-link = NULL; // head指向头结点 void create( NODE * head, int n ) //建n个结点 { NODE * p; for ( ; n0 ; n-- ) { p = ( NODE * ) malloc( sizeof( NODE ) ); gets( p-name ); p-link = head-link; // ① 修改结点指针 head-link = p; // ② 插入到表头 } } 链表基础-建立链表的基本方法 共 74 页 第 * 页 访问链表中全部数据结点 void output( NODE * head ) { NODE * p; p = head-link; // 指向第一个数据结点 while ( p != NULL ) { puts( p-name ); // 输出结点数据 p = p-link; // p 指向下一结点 } } NULL 头指针 表头结点 head 链表基础-访问链表全部结点 头指针 表头结点 head 数据结点1 name 数据结点n name NULL .... 共 74 页 第 * 页 求链表长度：链表中所包含的数据结点的数量。 int length( NODE * head ) { int len; NODE * p; for ( len=0, p=head-link; p!=NULL; ++len ) p = p-link; // p 指向下一个结点 return ( len ); } 链表基础-求链表长度 NULL 头指针 表头结点 head 头指针 表头结点 head 数据结点1 name 数据结点n name NULL .... ^ p p p ^ p .... 共 74 页 第 * 页 在第 i 个结点的后面插入新结点：基本原理 定位：指