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 R = {<ai-1 ai> | 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 (i<1 || i>L->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;j<=n-1;j++) L->data-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 (i<1 || i>n) Error(“Position error!”); //非法位置 for (j = i; j<=n-1; j++) 14 for (j = i; j<=n-1; j++) L->data[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;∥当i<0或i>n时未找到 ,思想： 顺链扫描：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 && j<i) {//顺链扫描，至p->next为空或j=i为止 p = p->next; j++; } 28 if (i == j) return p; //找到 else return NULL; //当i<0或i>n时未找到 } 时间分析 循环终止条件是搜索到表尾或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) // i<1或i>n+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