2014/47 §2.1线性表的逻辑结构 数据结构 ■线性表：由n(n20)个结点a1,,an组成的有限 序列 Ch.2线性表 记作：L=(a1,a2,,an, 属性：长度-结点数目n,n=0时为空表 a一般是同一类型 计算机学院 肖明军 Email:xiaomj@ustc.edu.cn http://staff.ustc.edu.cn/~xiaomj §2.1线性表的逻辑结构 §2.1线性表的逻辑结构 ■逻辑特征 ■举例： 当L中时， ◆英文字母表(AB,,Z) ◆扑克牌点数2,3…，10，小，Q,K,A) ①有且仅有1个开始结点a,和1个终端结点a,a,仅有 ◆学生成绩表等 一直接后继，a,仅有一直接前驱 ②内部结点a(2≤in-1)均有一直接前驱a.,和一直接 a抽象符号。具体应用可能是一个结构类型的对款 后继a+1 线性表是一种相当灵活的败据结构，其长度可根据需要增长或 缩短 结点之间的逻辑关系是由位置次序决定的，a] “基本运算： 出在表的第个位置。该关系是线性的（全序的， 故称L为线性表。 InitList(L),ListLength(L),GetNode(L,i)... 复杂运算可通过盖本运算去构造 sCh2线性表 SCh.2线性表 ■线性表的抽象数据类型定义 ADT List{ GetElem(L i.&e) 数据对橡：D={ailaic∈ElemSet,,i1,2,n,n20) 初始条件：线性表L已存在，1i百ListLength(L): 数据关系：R=(Kai-M,ai>1ai-1,aeD,i=2,3,n) 操作结果：用：返回L中第个数据元素的值： 基本操作： ListInsert (L,i &e InitList&L)】 初始条件：线性表L已存在，1 iListLength(L); 操作结果：构造一个空的线性表L； 操作结果：在线性表L中的第i个位置插入元素； ListLength(L) 初始条件：线性表L已存在： }ADT List 操作结果：若L为空表，则返回TRUE,否则返回 FALSE1
2014/4/7 1 数据结构 Ch.2 线性表 计 算 机 学 院 肖明军 Email: xiaomj@ustc.edu.cn http://staff.ustc.edu.cn/~xiaomj §2.1 线性表的逻辑结构 线性表：由n(n≥0)个结点a1, …, an组成的有限 序列 记作：L = (a1, a2, …, an), 属性：长度----结点数目n，n=0时为空表 a 般是同 类型 2 i ----一般是同一类型 §2.1 线性表的逻辑结构 逻辑特征 当L≠Ф时， ① 有且仅有1个开始结点a1和1个终端结点an，a1仅有 一直接后继，an仅有一直接前驱 ② 内部结点 (2≤i≤ 1)均有 直接前驱 和 直接 3 ② 内部结点ai (2≤i≤n-1)均有一直接前驱ai-1和一直接 后继ai+1 结点之间的逻辑关系是由位置次序决定的，ai 出在表的第i个位置。该关系是线性的(全序的)， 故称L为线性表。 §2.1 线性表的逻辑结构 举例： 英文字母表(A, B, …, Z) 扑克牌点数(2, 3, … , 10, J, Q, K, A) 学生成绩表 等 ai ----抽象符号。具体应用可能是一个结构类型的对象 4 ai 抽象符号。具体应用可能是 个结构类型的对象 线性表是一种相当灵活的数据结构，其长度可根据需要增长或 缩短 基本运算： InitList(L), ListLength(L), GetNode(L, i) …等 复杂运算可通过基本运算去构造 §Ch.2 线性表 线性表的抽象数据类型定义 ADT List{ 数据对象：D = { ai | ai∈ElemSet, i=1,2,…,n, n≧0 } 数据关系：R = { | ai 1, ai> | ai-1 ai ,∈D i=2 3 n } D, i=2,3,…,n } 基本操作： InitList( &L ) 操作结果：构造一个空的线性表L； ListLength( L ) 初始条件：线性表L已存在； 操作结果：若L为空表，则返回TRUE，否则返回 FALSE； §Ch.2 线性表 …. GetElem( L, i, &e ) 初始条件：线性表L已存在，1≦i≦ListLength(L)； 操作结果：用e返回L中第i个数据元素的值； ListInsert ( L, i, &e ) 初始条件：线性表L已存在，1≦i≦ListLength(L) ； 操作结果：在线性表L中的第i个位置插入元素e； … } ADT List
2014/47 §2.2线性表的顺序存储结构 82.2.1顺序表 §2.2.1顺序表 ■特征： ■定义：将线性表中结点按逻辑次序依次存储在 一组地址连续的存储单元里。由此存储的L称 ①随机存储 为顺序表。 ②只需存储结点。无需用 辅助空间存储逻辑关系。 ■地址计算： 但空闲大小不易确定， 响明 设结点大小为个单元，其中第个单元为该结点地址 易浪费空间 Loc(aj)=Loc(a)+(i-1)*1 ③静态分配（当用向量实 施时)亦可动态申请空 间，但copy成本大 L的基地址 (扩充表时)。 §2.2.1顺序表 §2：2.2顺序表上实现的基本运算 ■实现：用向量实现 1插入 #define ListSize100;l假定 ■基本思想： typedef int DataType;l依具体使用定 在L的第i个位量上插入一新结点x(1≤i≤n+1)。 typedef struct DataType data[ListSize];l存放结点 int length;/当前表长n (anaxn )Seglist; 为保持结点的物理顺序和逗辑顺序一致，须： ①将a,a依次后移1位，空出ith位量 ②插入x @表长加1 §2.2.2顺序表上实现的基本运算 82.2.2顺序表上实现的基本运算 ■算法： ■分析： 规模n void InsertList(SegList'L,DataType x,int i)( 循环后移，移动节点数为+1，时间与插入位置相关 intj;注意c数组1st位量的下标为0.ai的位置是data-1】. ①最好情况：当=nt1,不移动0(1 if(K1‖i>L>length+1)l1≤sn+1是合法播入位量 常败时间解释On)与n无关 Error("Position error!"); ②量坏情况：当i=1,全部后移0) if (L->length >ListSize)Error ("Overflow"); ®平均性能： for (j=L->length-1;j>=-1;j-) 设年何合法位置上捕入的辰本相等：片=， +(位置播入的颜率 当位量确定是，后移次数亦南定：-计1.放表中平均移动结点为： L->data[+1]=L->data[]; 结点后移 g0-2040--2-w L>data[i-1j=x;插入x 即指入式，平均移动表中一半结点 L>length+;长度加1 2
2014/4/7 2 §2.2 线性表的顺序存储结构 §2.2.1 顺序表 定义：将线性表中结点按逻辑次序依次存储在 一组地址连续的存储单元里。由此存储的L称 为顺序表。 地址计算 7 ： 设结点大小为l个单元，其中第i个单元为该结点地址 Loc(ai ) = Loc(a1) + (i-1) *l L的基地址 §2.2.1 顺序表 特征： ① 随机存储 ② 只需存储结点。无需用 辅助空间存储逻辑关系。 但空闲大小不易确定， 易浪费空间 ③ 静态分配（当用向量实 施时）亦可动态申请空 间，但copy成本大 （扩充表时）。 8 §2.2.1 顺序表 实现：用向量实现 #define ListSize 100; //假定 typedef int DataType; //依具体使用定 typedef struct { DataType data[ListSize]; //存放结点 9 data[ListSize]; //存放结点 int length; //当前表长n }Seglist; §2.2.2 顺序表上实现的基本运算 1.插入 基本思想： 在L的第i个位置上插入一新结点x(1 ≤ i ≤ n+1)。 x 10 (a1, …, ai-1, ai , ai+1, …, an) → (a1, …, ai-1, x, ai , …, an+1) 为保持结点的物理顺序和逻辑顺序一致，须： ① 将an, …, ai 依次后移1位，空出ith位置 ② 插入x ③ 表长加1 §2.2.2 顺序表上实现的基本运算 算法： void InsertList(SegList *L, DataType x, int i){ int j; //注意c数组1st位置的下标为0. ai的位置是data[i-1]. if (iL->length+1) //1≤i≤n+1是合法插入位置 Error(“Position error!”); 11 Error( Position error! ); if (L->length >= ListSize) Error (“Overflow”); //溢出 for (j = L->length-1; j>=i-1; j--) L->data[j+1] = L->data[j]; //结点后移 L->data[i-1] = x; //插入x L->length++; //长度加1 }; §2.2.2 顺序表上实现的基本运算 分析： 循环后移，移动节点数为n-i+1，时间与 相关 ① 最好情况：当i=n+1，不移动 O(1) 常数时间解释 O(n0)与n无关 ② 最坏情况：当i=1，全部后移 O(n) 12 ② 最坏情况：当i 1，全部后移 O(n) ③ 平均性能： 设任何合法位置上插入的概率相等： (位置i插入的概率) 当位置i确定是，后移次数亦确定：n-i+1. 故表中平均移动结点为： 即插入式，平均移动表中一半结点
2014/47 §2.2.2顺序表上实现的基本运算 §2.2.2顺序表上实现的基本运算 2副除 算法： ■基本思想： void DeleteList(SegList'L,int i){ intj,n=L->length; 在L中测除ith结点(1≤i≤n)。 if(ik1‖i>n)Error(Position errorl店非法位置 (a,,atya,a1g,an）→(a1g,a.1,a+ggan-】 for (i;jdata-1]=L->data:1/结点后移 为保持物理与逻辑顺序一致，须： L>length-;长度减1 ①前移：将a+1,,an依次前移1位，填朴副除a留 下的空间 ⑦表长减1 §2.2.2顺序表上实现的基本运算 §2.3线性表的链式存储结构 ■分析： ■顺序表 前移次数与n和i相关，移动节点数n-i。 缺点：移动节点，不利于动态插入和副除 ①最好情况：当i=n,不移动O(1) ◆优点：随机存取，得到第1个结点的时间为O(1)与 ②最坏情况：当i=1,前移n-1次O(n) 表长和位置无关 ③平均性能： 82.3.1单链表（线性链表） 存储方法： 用一组任意存储单元来存放结点（可连续，亦可不连媒）： 为表示逻辑关系，须存储后继或前驱信息 S2.3.1单链表（线性链表） 82.3.1单链表（线性链表) ■结点结构 head- 数据域指针域（链域） Zhao Qian Sun 山 data next next指向该结点的后继（的地址） 逻辑状态 ■表示 头指针唯一确定一个单链表 存情状态 见图2.5 ①开始结点无前驱，用头指针表示 ②终端结点无后继，next城为空(NULL) ■特征 ①非顺序存取 ②用指针表示结点间逻辑关系 ③动态分配 3
2014/4/7 3 §2.2.2 顺序表上实现的基本运算 2.删除 基本思想： 在L中删除ith结点 (1 ≤ i ≤ n)。 (a1, …, ai-1, ai , ai+1, …, an) → (a1, …, ai-1, ai+1, …, an-1) 13 为保持物理与逻辑顺序一致，须： ① 前移：将ai+1, …, an依次前移1位，填补删除ai 留 下的空间 ② 表长减1 §2.2.2 顺序表上实现的基本运算 算法： void DeleteList(SegList *L, int i){ int j， n=L->length; if (in) Error(“Position error!”); //非法位置 for (j = i; jdata[j-1] = L->data[j]; //结点后移 L->length--; //长度减1 }; §2.2.2 顺序表上实现的基本运算 分析： 前移次数与n和i相关，移动节点数n-i。 ① 最好情况：当i=n，不移动 O(1) ② 最坏情况：当i=1，前移n-1次 O(n) 15 ③ 平均性能： §2.3 线性表的链式存储结构 顺序表 缺点：移动节点，不利于动态插入和删除 优点：随机存取，得到第i个结点的时间为O(1)与 表长和位置无关 §2 3 1 单链表（线性链表） 16 §2.3.1 单链表（线性链表） 存储方法： 用一组任意存储单元来存放结点（可连续，亦可不连续）； 为表示逻辑关系，须存储后继或前驱信息 §2.3.1 单链表（线性链表） 结点结构 数据域 指针域（链域） next指向该结点的后继（的地址） 表示 17 ① 开始结点无前驱，用头指针表示 ② 终端结点无后继，next域为空（NULL） §2.3.1 单链表（线性链表） 逻辑状态 头指针唯一确定一个单链表 存储状态 见图2 5 18 2.5 特征 ① 非顺序存取 ② 用指针表示结点间逻辑关系 ③ 动态分配
201447 §2.3.1单链表（线性链表） §2.3.1单链表（线性链表） ■实现： 结点变量和指针变量 typedef struct node(I结点类型定义 p *g *(p->next) DataType data;I徽据城 struct node'next;w针城 (*p).data (*p).next )ListNode; p->data p>next P->next->data typedef ListNode"LinkList;;链表类型定义 指针变量p:值为结点地址 ListNode"p;结点定义 结点变量p:值为结点内容 LinkList head;Il链表头指针定义 动态申请，垃圾收集 S2.3.1单链表（线性链表） §2.3.1单链表（线性链表） 1建立单链表 ■(2)尾插法： ■(1)头插法： head ◆从空衰开始，重复读入数据：申请新结点、插入表头，直至 4a-…一d 输入结束。 ◆表次序与输入次序相反。 设为指针指向当前链冕（初值为NULL) ◆处理自然简单 ①申请新结点s ②将读入数据写入 ®新结点链到表尾（应注意边界条件） ④修改尾指针： S2.3.1单链表（线性链表） 82.3.1单链表（线性链表） 为简便起见，设结点数据类型DataType为char,输 else 入字符，换行符结束 r->next=s;∥③ LinkList CreateList(void) r=s;∥④ lch,head,r为局部量 许r=NULL)r->next=NULL;非空表，终州结点指针为空无后键 head=r=NULL;开始为空表 return headg while ((ch getchar())!=An'){ s=(ListNode)malloc(sizeof(ListNode));∥① 。边界条件处理： s>data=ch;∥② 空表和非空表处理不一致 f(head=NULL)插入空表 筒化方法：引入头结点（刚兵），其中data域可微它用 (如表长度) head=s;新结点插入空表（边界），r为空
2014/4/7 4 §2.3.1 单链表（线性链表） 实现： typedef struct node{ //结点类型定义 DataType data; //数据域 struct node *next; //指针域 }ListNode; 19 typedef ListNode *LinkList; //链表类型定义 ListNode *p; //结点定义 LinkList head; //链表头指针定义 §2.3.1 单链表（线性链表） 结点变量和指针变量 20 指针变量p：值为结点地址 结点变量*p：值为结点内容 动态申请，垃圾收集 §2.3.1 单链表（线性链表） 1.建立单链表 （1）头插法： 从空表开始，重复读入数据：申请新结点、插入表头，直至 输入结束。 表次序与输入次序相反。 21 处理自然简单 §2.3.1 单链表（线性链表） （2）尾插法： 设为指针r指向当前链尾（初值为NULL） 22 ① 申请新结点s ② 将读入数据写入 ③ 新结点链到表尾（应注意边界条件） ④ 修改尾指针r §2.3.1 单链表（线性链表） 为简便起见，设结点数据类型DataType为char，输 入字符，换行符结束 LinkList CreateList(void){ //ch, head, r为局部量 head = r = NULL; //开始为空表 23 while ((ch = getchar()) != ‘\n’){ s = (ListNode*)malloc(sizeof(ListNode)); // ① s->data = ch; // ② if (head == NULL) //插入空表 head = s; //新结点插入空表（边界），r为空 §2.3.1 单链表（线性链表） else r->next = s; // ③ r = s; // ④ } if (r != NULL) r->next = NULL; //非空表，终端结点指针为空无后继 return head； 24 return head } 边界条件处理： 空表和非空表处理不一致 简化方法：引入头结点（哨兵），其中data域可做它用 （如表长度）
2014/47 §2.3.1单链表（线性链表） S2.3.1单链表（线性链表） head子ZI因 r->next =s; head☑a1 anA r=8 头结点 开始结点 终端结点 r->next=NULL;些端结点浙针置空，或空表时头结点指针置空 LinkList CreateList(void){ return head; 川用凰插法建立带头纳点的单链表 char ch; LinkList head =(Linklist)malloc(sizeof(ListNode)); 性成头结点 Note:为简化起见，，申请结点时不判是否申请到 ListNode's,'r; g时间：O( r=head:∥为指针初始指向头结点 while () s=(ListNode")malloc(sizeof(ListNode)); s>data=ch; §2.3.1单链表（线性链表） S2.3.1单链表（线性链表） 2.查找 ListNode GetNode(LinkList head,int i){ 在赞衰（有头结点）中查找th结点找到0ss)测返回该结点的存侧 ①按值查找 位皇，否测返回NULL int j;ListNode "p; 找链表中关键字为k的结点 p=head;j=0;头结点开始扫描 ②按序号查找 while(p->next&8j长仙链扫捕，至p->next为空或j=i为止 p=p>next;j++; 合法位量1sin.头结点可作第0个结点 返回第i个结点的地址，即找到第i-1个结点，返回其next f(i=j)return p;找到 城 else return NULL;∥当in时未找到 ,思想： 顺链扫描：p当前扫描到的结点，初始指向头结点 ”时间分折 小一计算最。累加扫描到的结点，初始值为0 循环终止条件是搜索到表尾或户1。复杂度量多为引，与查找位 每次加1，直至j户i为止，p指向ith结点 置相关。 一算法 ∑i(m+)=n/2=0网i=0,找头结点 §2.3.1单链表（线性链表） 82.3.1单链表（线性链表） 3插入 void InsertList (LinkList head,DataType x,int i){ 1增头结点1≤isn+1 ■问题：将值为x的结点插到表的第个结点位置上。 ListNode"p; 即在a和a,之间插入。故须找到第a1个结点的地址 p=GetNode(head,i-1片l得找第i-1个结点① f(p==NULL)∥k1或Pn+1时播入位置有增 P,然后生成新结点s,将其链到a1之后，a之前。 Error("position error"片 s=(ListNode ")malloc(sizeof (ListNode)); s->data=x;③ eZ7…a1】 s->next=p->next;//③ p>next=s;l⑤ 思考：若无头结点，边界如何处理？ ■时间：主要是GetNode O(n)合法位置1≤iSn+1 GetNode:0sisn 5
2014/4/7 5 §2.3.1 单链表（线性链表） LinkList CreateList(void){ //用尾插法建立带头结点的单链表 25 char ch； LinkList head = (Linklist)malloc(sizeof(ListNode)); //生成头结点 ListNode *s, *r; r = head; //为指针初始指向头结点 while () { s = (ListNode*)malloc(sizeof(ListNode)); s->data = ch; §2.3.1 单链表（线性链表） r->next = s; r = s; } r->next = NULL; //终端结点指针置空，或空表时头结点指针置空 return head; } 26 Note：为简化起见，，申请结点时不判是否申请到 时间： O(n) §2.3.1 单链表（线性链表） 2.查找 ① 按值查找 找链表中关键字为k的结点 ② 按序号查找 合法位置 1≤i≤n 头结点可看作第0个结点 27 合法位置 1≤i≤n. 头结点可看作第0个结点 返回第i个结点的地址，即找到第i-1个结点，返回其next 域 思想： 顺链扫描：p----当前扫描到的结点，初始指向头结点 j----计算器。累加扫描到的结点，初始值为0 每次加1，直至 j=i为止，p指向ith结点 算法 §2.3.1 单链表（线性链表） ListNode *GetNode(LinkList head, int i){ //在链表（有头结点）中查找ith结点 找到(0≤i≤n)则返回该结点的存储 //位置，否则返回NULL int j; ListNode *p; p = head; j = 0; //头结点开始扫描 while (p->next && jnext为空或j=i为止 p = p->next; j++; } 28 if (i == j) return p; //找到 else return NULL; //当in时未找到 } 时间分析 循环终止条件是搜索到表尾或j=i。复杂度最多为i，与查找位 置相关。 //i=0，找头结点 §2.3.1 单链表（线性链表） 3.插入 问题：将值为x的结点插到表的第i个结点位置上。 即在ai-1和ai 之间插入。故须找到第ai-1个结点的地址 p，然后生成新结点*s，将其链到ai-1之后，ai 之前。 29 §2.3.1 单链表（线性链表） void InsertList (LinkList head, DataType x, int i) { //带头结点 1≤i≤n+1 ListNode *p; p = GetNode(head, i-1); //寻找第i-1个结点① if (p== NULL) // in+1时插入位置i有错 Error("position error"); s = (ListNode *)malloc(sizeof (ListNode)); //② s >data=x; //③ 30 ->data=x; //③ s->next=p->next; //④ p->next=s; //⑤ } 思考：若无头结点，边界如何处理？ 时间：主要是GetNode O(n) 合法位置 1≤i≤n+1 GetNode： 0≤i≤n
2014/47 §2.3.1单链表（线性链表） §2.3.1单链表（线性链表） 4.副除 void DeleteList(LinkList head,int i){ 副ith结点。首先找a。 合法位量是1≤i≤n p=GetNode (head,i-1);/ f(pI(p->next)∥iK1或>n时除位置有错 head- ai-1ai a日 Error("position error"); r=p>next;②令r指向被，结点a 存储池 p->next=r>next;∥③将a,从链上摘下 free(r); 1④释放a S2.3.1单链表（线性链表） §2.3.2循环链表（单） ■正确性分析 ■首尾相接：不增加存储量，只修改连接方式 ①K1时，GetNode中的参数next为空 ③i>n+1时，GetNodei返回p为空 非空表 空表 ■时间On) ●优点：从任一结点出发可访问到表中任一其 结论：链表上插、无须移动结点，仅需修改指针 它结点，如找前驱(O() ■遍历表的终止方式： p为空或p->next为空→p=head或p->next=head 3 82.3.2循环链表（单） 82.33双链表（循环) ■仅设尾指针更方便：访问开始结点和终端结 单链表只有后向链，找一结点的后继时间为0(1)， 点的时间均为0(1)。 但找前驱费时，若经常涉及找前驱和后继，则可选 双链表。 例如：合并两个单循环链表的时间为0(1)，但用头 指针表示时： prior net T(m,n=O(max(m,n)或O(min(m,n】 (。)结点结构(6)空的双狮环链表 (©)半空的双循环链表 6
2014/4/7 6 §2.3.1 单链表（线性链表） 4.删除 删ith结点。首先找ai-1。 31 §2.3.1 单链表（线性链表） void DeleteList (LinkList head, int i){ //合法位置是1 ≤ i ≤ n p = GetNode (head, i-1); //① if (!p || !(p->next)) // in时删除位置有错 Error("position error"); 32 ( p ); r = p->next; //② 令r指向被删结点ai p->next = r->next; // ③ 将ai 从链上摘下 free(r); // ④ 释放ai } §2.3.1 单链表（线性链表） 正确性分析 ① inext为空 ③ i>n+1时 GetNode返回p为空 33 ③ i>n+1时，GetNode返回p为空 时间 O(n) 结论：链表上插、删无须移动结点，仅需修改指针 §2.3.2 循环链表（单） 首尾相接：不增加存储量，只修改连接方式 34 优点：从任一结点出发可访问到表中任一其 它结点，如找前驱（O(n)） 遍历表的终止方式： p为空或p->next为空 p=head或p->next=head §2.3.2 循环链表（单） 仅设尾指针更方便：访问开始结点和终端结 点的时间均为O(1)。 例如：合并两个单循环链表的时间为O(1)，但用头 指针表示时： T(m n)=O(max(m n))或O(min(m n)) 35 T(m,n)=O(max(m,n))或O(min(m,n)) §2.3.3 双链表（循环） 单链表只有后向链，找一结点的后继时间为O(1)， 但找前驱费时，若经常涉及找前驱和后继，则可选 双链表。 36
201447 §2.3.3双链表（循环） S2.3.3双链表（循环） ■结构特征 ·例1：前插 s->data=x; ∥② 对称结构：若印不空，则 s->prior=p->prior;/ s->next=p; ∥④ p->prior->next p=p->next->prior p->prior->next=s;∥⑤ ■优点： p->prior=s; ∥⑥ ①找一结点前驱和找一结点后继同样方便 ②测p本身和删p的后继同样方便 ■例2：副p p->prior->next=p->next; p->next->prior=p->prior; free(p); 62.3.4静态链表 §2.3.4静态链表 上述链表是由指针实现的，其中结点分配 ■1.定义 和回收是由系统实现的，系统提供了malloc #define nil0空指针 和free动态执行，故称为动态链表。 #define MaxSize1000/可容纳的结点数 动态-程序执行时系统动态分配和回收 typedef struct{ 静态链表一 DataType data; 一先分配大空间作为备用结点空间（即存储池） int next; 一用下标（亦称游标cursor)模拟指针，自定义 }node,NodePool[MaxSize]; 分配和释放结点函数 typedef int StaticList; S2.3.4静态链表 82.3.4静态链表 ■2.基本操作（模拟动态链表） ②分配结点 ①初始化 在备用链表上申请一个结点，返回非空（不等于0） 将整个表空间链成一个备用链表，只做一次。 成功，否则失败。 int AllocNode(NodePool space){ void Initiate(NodePool space){ i=space[o].next; M备用链表的头结点位置为spacel0 取备用链表上开始结点，位量为i,即spacel的第i个分量 for (i=0;i<MaxSize-1;i++)space[i].next =+1; f(0开始结点非空 space[MaxSize-1].next nil; nace space[o].next=space[i].next; 1 将开始结点从备用链表上摘下 return i;l为nil时失效 data next Z子于 MaxSize-1 nil 7
2014/4/7 7 §2.3.3 双链表（循环） 结构特征 对称结构：若p不空，则 p->prior->next = p = p->next->prior 优点： 37 ① 找一结点前驱和找一结点后继同样方便 ② 删*p本身和删*p的后继同样方便 §2.3.3 双链表（循环） 例1：前插 s->data=x; // ② s->prior=p->prior; // ③ s->next=p; // ④ p->prior->next=s; // ⑤ p->prior=s; // ⑥ 38 例2：删*p p->prior->next=p->next; p->next->prior=p->prior; free(p); §2.3.4 静态链表 上述链表是由指针实现的，其中结点分配 和回收是由系统实现的，系统提供了malloc 和free动态执行，故称为动态链表。 动态----程序执行时系统动态分配和回收 静态链表 39 ---- 先分配大空间作为备用结点空间（即存储池） 用下标（亦称游标cursor）模拟指针，自定义 分配和释放结点函数 §2.3.4 静态链表 1.定义 #define nil 0 //空指针 #define MaxSize 1000 //可容纳的结点数 typedef struct { 40 DataType data; int next; }node, NodePool[MaxSize]; typedef int StaticList; §2.3.4 静态链表 2.基本操作（模拟动态链表） ① 初始化 将整个表空间链成一个备用链表，只做一次。 void Initiate(NodePool space) { //备用链表的头结点位置为space[0] 41 for (i=0; i<MaxSize-1; i++) space[i].next = i+1; space[MaxSize-1].next = nil; } §2.3.4 静态链表 ② 分配结点 在备用链表上申请一个结点，返回非空（不等于0） 成功，否则失败。 int AllocNode(NodePool space) { i = space[0].next; 取备用链表上开始结点 位置为 即 的第 个分量 42 //取备用链表上开始结点，位置为i，即space的第i个分量 if (i) //开始结点非空 space[0].next = space[i].next; //将开始结点从备用链表上摘下 return i; //为nil时失效 }
201447 §2.3.4静态链表 S2.3.4静态链表 ③释放结点 ■3.一般操作 将释放结点收还到备用链表的头上。 ①插入 void Insert(NodePool space,StaticListL,DataType x,int i){ void FreeNode(NodePool space,int ptr){ ∥在带头结点的静态链衰L的第个结点之前摆入新结点x p=Locate(space,L,-1片找L中a的前里① 将ptr所指结点回收到备用链表头结点之后 if (p =nil) space[ptr].next space[o].next; Eror"Position error!;I位置增 S=AllocNode(space):申请结点② space[o].next ptr; f(s=ni训 Eror"Overflow":∥申请失败，空间不足判定 space[s]..data=x;∥③ space[s].next space[p].next; space[p].next=s;∥③ S2.3.4静态链表 §2.3.4静态链表 少除 void Delete(NodePool space,StaticList L,int i){ data next p=Locate(space,,L,b1:I找L中a,的前里① data next 0A1 if (p =nil ll space[p].next =nil) Error("Position error!"5∥位置错 依次在L中用 在L的第二个 q=space[.next∥q指向放结点a,② 尾插法建立的 ■6■ 结点上插入d space[p].next=space[q]..next;∥将a箱下③ 链表(a,b,c) FreeNode(space,,qh∥④ 101 10F 注意：链表头指针实际上整数，即spacek的下标 S2.3.4静态链表 82.3.4静态链表 data nex L data next 利的第1个结点 Z的adG-Gn 0A6 0 存储 麻放 10 在spce中可能有多个链表，若再建立一个链表 head,头结点在愿个位置？ 8
2014/4/7 8 §2.3.4 静态链表 ③ 释放结点 将释放结点收还到备用链表的头上。 void FreeNode(NodePool space, int ptr) { //将ptr所指结点回收到备用链表头结点之后 43 space[ptr].next = space[0].next; space[0].next = ptr; } §2.3.4 静态链表 3.一般操作 ① 插入 void Insert(NodePool space, StaticList L, DataType x, int i) { // 在带头结点的静态链表L的第i个结点ai 之前插入新结点x p = Locate(space, L, i-1); //找L中ai 的前驱① if (p == nil) 44 (p ) Error(“Position error!”); //位置错 S = AllocNode(space); //申请结点② if (s == nil) Error(“Overflow”); //申请失败，空间不足判定 space[s].data = x; // ③ space[s].next = space[p].next; // ④ space[p].next = s; // ⑤ } §2.3.4 静态链表 ② 删除 void Delete(NodePool space, StaticList L, int i) { p = Locate(space, L, i-1); // 找L中ai 的前驱 ① if (p == nil || space[p].next == nil) Error(“Position error!”); // 位置错 45 q = space[p].next; // q指向被删结点ai ② space[p].next = space[q].next; // 将ai 摘下 ③ FreeNode(space, q); // ④ } 注意：链表头指针实际上整数，即space的下标 §2.3.4 静态链表 46 §2.3.4 静态链表 47 §2.3.4 静态链表 48 在spce中可能有多个链表，若再建立一个链表 head，头结点在哪个位置？
201447 §2.3.4静态链表 ■静态链表特点： 作业 没有指针类型的语言可以使用。亦可有双链表。循 1 为什么在单循环链表中设置尾指针比设置 环链表等。 头指针更好？ 对比： 2,写一个算法将单链表中值重复的结点副除 动态链表 静态链表 ,使所得的结果表中各结点值均不相同。 指针变量ptr 下标ptr 结点变量'pt 结点space[ptr的 结点后继位置ptr->next 结点后继位量space[ptr].next S2.4顺序表和链表之比较
2014/4/7 9 §2.3.4 静态链表 静态链表特点： 没有指针类型的语言可以使用。亦可有双链表。循 环链表等。 对比： 动态链表 静态链表 49 指针变量ptr 下标ptr 结点变量*ptr 结点space[ptr] 结点后继位置ptr->next 结点后继位置space[ptr].next §2.4 顺序表和链表之比较 作业 1. 为什么在单循环链表中设置尾指针比设置 头指针更好？ 2. 写一个算法将单链表中值重复的结点删除 ，使 得的结 表中各结点值均 相 使所得的结果表中各结点值均不相同