2_1软件技术基础.ppt

举例 ? 由食品组成的单链表 （ biscuit,butter,cheese,eggs,grapes,jam) 不带头结点。 grapes biscuit butter cheese jam eggs ^ head 头指针 单链表的物理存储 存储地址 数据域（ data ） 指针域（ next ） grapes 60 biscuit 61 cheese 13 eggs 1 jam NULL butter 12 1 11 12 13 60 61 11 头指针 head ? （ biscuit,butter,cheese,eggs,grapes,jam) 空表和非空表表示形式在头结点上得到统一 空表的形式 : head - next = NULL head ^ 头结点 head 头结点 非空表的形式 : head - Next = Address 头节点与无头节点 三、单链表的操作 1. 单链表的查找 find 2. 单链表的的插入 insert 3. 单链表的删除 delete 指针的基本操作 ? 设指针变量 p 、 q 的定义为： NODE *p ， *q ； ? 对链表的操作实际上是对指针的操作。例如， 要删除结点 a i ，首先要使指针 p 指向 a i ，即： a 1 ... ... head a i a n ^ p 指针 p 是存储单元的地址，地址内的内容可以通过 V(p) 得到，指向下个元素的指针用 next(p) 得到 指针的基本操作列表 ? p= （ NODE* ） malloc （ sizeof （ NODE ）） 申请一个结点空间，并将地址送入 p 中。 ? free （ p ） 释放 p 指针所指结点的空间 ? p=q 指针 p 指向指针 q 所指的结点 ? p=q-next 指针 p 指向指针 q 所指结点的后件 ? p=p-next 指针 p 向后移动一个结点 ? p-next=q 将指针 q 所指结点改接为指针 p 所指结点 的后件 ? p-next=NULL 将指针 p 所指结点与后件结点断开 1 单链表的查找算法 要求：在头指针为 HEAD 的非空线性链表中寻找包 含元素 x 的前一个结点 p 算法操作步骤 : ? step1 初始化 , 指针 p 指向头指针 ? step2 p 非空且 p 指向的下一个元素不是 x, 循环 ? step3 每循环一次 ,p 后移一个位置 ? step4 循环结束 , 返回指针 p. template class T ListNodeT * List T ::Find ( T x ) { p = head; // 当前指针 p 指示第一个结点 while ( p -next != NULL (p-next)-d != x ) p=p-next; return p; } 2 单链表插入算法 要求：在头指针为 HEAD 的线性链表中包含元素 x 的结 点之前插入新元素 b 算法操作步骤 : ? step1 找到 x 的位置 , 使指针 p 指向 x 的前一个结点； ? step2 申请并生成新结点 s ? step3 使 s 插入到 x 所在结点之前 template class T void linked_llistT::ins_linked_llist(T x, T b) { nodeT *p,*q; p= new nodeT ; p-d =b; if( head == NULL) {head=p; p-next=NULL; return;} if( head - d == x) { p-next =head; head=p; return;} q =head; while ((q-next !=NULL) ((q-next)-d)!=x)) q=q-next; p-next =q-next; q-next= p; return;} 第二章 基本数据结构及其运算 2.1.1 什么是数据结构 ? 数据（ Data ） 能存于计算机、并被计算机处理的符号的集合。 它是客观事物的符号表示。 ? 数据元素（ Element ） 是数据的基本单位、数据集合中的个体。 ? 关系 前后件关系，反映了数据元素固有的一种结构。 ? 数据结构（ Dat