2第二讲 线性表.pptVIP

用一组地址任意的存储单元(连续的或不连 续的)依次存储表中各个数据元素, 数据元素之 间的逻辑关系通过 间接地反映出来。 指针 ( a1, a2, a3, a4, … , an-1, an ) … a2 d2 a1 d1 a4 d4 a3 d3 d2 d3 d4 d5 ^ a1 d1 a2 d2 a3 d3 a4 d4 an dn … list 一.构造原理 … 线性表的这种存储结构称为 ，或 者 ，其一般形式为： 单链表 线性链表 a1 d1 a2 d2 a3 d3 a4 d4 an dn … ^ list 一个链结点 数据域 指针域 data link 地址任意 k个存储单元 data link 链结点： Class node{ ElemType data; node *link; }; 类 型 定 义 No. Name Age a1 a2 a3 a30 60101 张三 17 60102 李四 16 60103 王五 20 node list, p; Class ElemType{ int Num; char Name[10]; int Age; }; 若指针变量p为指向链表中某结点的指针(即p 的内容为链表中某链结点的地址))，则 若出现在表达式中，表示由p指的链结点的数据域中的内容。 list ^ 1024 735 622 … 张三 … 李四 … 王五 … p 二.关于符号说明 p-data p-link 若出现在表达式中，表示由p指的链结点的 指针域的内容，即p所指的链结点的下一个 链结点的地址。 某一位置=p-link; p-link=某一地址; 例 将指针变量p由指向链表中某一个链结点改变为指向下一个链结点。 list ^ 1024 735 622 … 张三… 李四… 王五… p p r p-link=r; p-link=r-link; p=p-link; ? 求线性表的长度。 ? 建立一个线性链表。 ? 在非空线性链表的第一个结点前插入一个数据 信息为item的新结点。 ? 在线性链表中由指针q 指出的结点之后插入一 个数据信息为item的链结点。 ? 在线性链表中第i个结点后面插入一个数据信息 为item的链结点。 ? 从非空线性链表中删除链结点q(q为指向被删除 链结点的指针)。 三.链表的基本操作 ? 删除线性链表中满足某个条件的链结点。 ? 线性链表的逆转。 ? 将两个线性链表合并为一个线性链表。 ? 检索线性链表中的第i个链结点。 …… 1.求线性链表的长度 … … list ^ p=p-link; p p p n++; =NULL 链表长度 p 初始： n=0; int LENGTH( node *list ) { node *p=list; int n=0; /* 链表的长度置初值0 */ while(p!=NULL){ p=p-link; n++; } return n; /* 返回链表的长度n */ } 算法 时间复杂度O(n) 申请一个链结点的空间 释放一个链结点的空间 ( a1, a2, a3, … , an–1, an ) node p=new node(); C语言 delete p; 2. 建立一个线性链表 list ^ a1 a2 a3 an-1 an … ( a1, a2, a3, a4, … , an-1, an ) a1 list a2 a3 … an-1 an ^ a1 a2 a3 list r a4 p r-link=p; r r=p； 一个结点的插入过程 LinkList CREATE( int n ) { node *p, *r, *list=NULL; datatype a; for(i=1;i=n;i++){ READ(a); /* 取一个数据元素 */ p=new node(); p-data=a; p-link=NULL; if (list==NU