数据与结构算法中对线性表的理解.ppt

n n 线性表线性表 n n 顺序表顺序表 n n 链表链表 n n 顺序表与链表的顺序表与链表的 比较比较 线性表线性表 (Linear List)(Linear List) n n 线性表的定义和特点线性表的定义和特点 uu 定义定义 n n（ 0 0）个数据元素的有限序列个数据元素的有限序列 ，记作，记作 （a a 1 1 , a a 2 2 , , a a n n ） a a i i 是表中数据元素，是表中数据元素，n n 是表长是表长, , n=n=0 0时时 为空表为空表 uu 遍历遍历 逐项访问：逐项访问： 从前向后从前向后 从后向前从后向前 线性表的特点线性表的特点 n n 除第一个元素外，其他每一个元除第一个元素外，其他每一个元 素有且仅有一个素有且仅有一个直接前驱直接前驱 n n 除最后一个元素外，其他每一个除最后一个元素外，其他每一个 元素有且仅有一个元素有且仅有一个直接后继直接后继 a1a2a3a4a5 uu 线性表的初始化线性表的初始化 Init_ListInit_List (L) (L) uu 求线性表的长度求线性表的长度 Length_ListLength_List (L) (L) uu 取表元取表元 Get_ListGet_List (L, i) (L, i) uu 按值查找按值查找 Locate_ListLocate_List (L, x) (L, x) uu 插入操作插入操作 Insert_ListInsert_List (L, i, x) (L, i, x) uu 删除操作删除操作 Delete_ListDelete_List (L, i) (L, i) 线性表的基本操作线性表的基本操作 顺序表顺序表 (Sequential List)(Sequential List) n n 顺序表的定义和特点顺序表的定义和特点 uu 定义定义 将线性表中的元素相继存放在一将线性表中的元素相继存放在一 个连续的存储空间中。个连续的存储空间中。 uu 可利用可利用一维数组一维数组描述描述存储结构存储结构 uu 特点特点 逻辑顺序与物理顺序一致逻辑顺序与物理顺序一致 uu 访问访问 顺序存取顺序存取, , 随机存取随机存取 25 34 57 16 48 09 0 1 2 3 4 5 data 顺序表的连续存储方式顺序表的连续存储方式 35 27 49 18 60 54 77 83 41 02 1 2 3 4 5 6 7 8 9 10 l l l l l l l l l l Loc (ai) = Loc (a1) + (i1)*l 1in a 顺序表顺序表(SeqList)(SeqList)的定义的定义 #define Maxsize 100 /最大允许长 度 typedef int datetype; typedef struct datatype dataMaxsize; /存储 数组 int last; /当前元素个数 SeqList; SeqList *L; (或 SeqList L;) L.dataL.data a5 a4 a3 a2 a10 1 2 3 4 L.lastL.last = = L L datadata a5 a4 a3 a2 a10 1 2 3 4 L L lastlast = = Maxsize-1Maxsize-1 顺序表基本运算的实现顺序表基本运算的实现 n n 顺序表的初始化顺序表的初始化 SeqList *inti_Seqlist( ) SeqList *L; L=(SeqList*) malloc (sizeof(SeqList); Llast = -1; return L; n n 求表的长度求表的长度 int Length ( SeqList * L ) return Llast+1; n n 取表元：在表中提取第取表元：在表中提取第 i i 个元素的值个元素的值 datatype GetData ( SeqList *L, int i ) if ( i = 1 ; else return else return i; ; 按值查找按值查找动画演示 25 34 57 16 48 09 0 1 2 3 4 5 data 查找 16 i L last 0 1 2 3 4 5 查找成功，返回查找成功，返回i i的值的值 查找 50 25 34 57 16 48 09 0 1 2 3 4 5 data i L last 0 1 2 3 4 5 查找失败，返回查找失败，返回1 1 查找成功的平均比较次数查找成功的平均比较次数 若查找概率相等，则：若查找概率相等，则： 查找不成功查找不成功 ，数据比较，数据比较 n 次次 O(n) 25 34 57 16 48 09 63 0 1 2 3 4 5 6 7 data 50 25 34 57 0 1 2 3 4 5 6 7 data 50 i=4 例:在第个位置(i=4)插入一个值为50的新元素 Llast n n 插入运算：在顺序表的第插入运算：在顺序表的第 i i (1i (1i n+1)n+1)个位置插入一个值为个位置插入一个值为 x x 的新元素的新元素 63094816 i与Llast的关系？ int Insert ( SeqList *L, datatype x, int i ) /在表中第 i 个位置插入新元素 x if (i ) return 0; if (Llast= Maxsize-1) return -1; /参数不合理或表已满，插入不成功 for ( j = Llast; j = ; j- ) Ldataj+1 = Ldataj; = x; Llast+; return 1; /插入成功 Llast +2 i-1 Ldatai-1 n n 算法分析算法分析： n n 在顺序表上做插入操作需要移动表中一半在顺序表上做插入操作需要移动表中一半 的元素的元素 n n 时间复杂度为时间复杂度为(n)(n) 16 25 34 57 16 48 09 63 0 1 2 3 4 5 6 7 data 25 34 57 0 1 2 3 4 5 6 7 data i=4 例:将表中第个位置(i=4)上的元素删除 Llast n n 删除运算：将顺序表中的第删除运算：将顺序表中的第 i i (1i (1i n)n)个元素从表中删除个元素从表中删除 630948 i与Llast的关系？ int Delete ( SeqList *L, datatype x ) /删除表中第 i 个位置上的元素 if (i Llast +1) return 0; for ( ; j dataix) i+; if (L-datainext= s-next= ？ 如何利用如何利用nextnext指针在空指针在空 表的基础上建立一非空的单链表？表的基础上建立一非空的单链表？ n n 申请结点空间：申请结点空间： LNode *s; s = (LNode )malloc(sizeof(LNode); s-data = x; LinkList head = NULL; 前插法前插法 建立单链表建立单链表 n n 从一个空表开始，重复读入数据从一个空表开始，重复读入数据 ： uu用用mallocmalloc函数生成新结点函数生成新结点 uu读入的数据存放到新结点的读入的数据存放到新结点的datadata域域 中中 uu将该新结点插入到链表的将该新结点插入到链表的最前端最前端 n n 直到读入的数据等于结束符直到读入的数据等于结束符flagflag 为止。为止。 动画演示 s 25 head flag值为-1 x=25 ss x=45x=18 4518 x= - 1 2 2条重要的指针赋值语句：条重要的指针赋值语句： s-next=head;head=s; 前插法前插法 建立单链表的建立单链表的 动画演示动画演示 LinkList CreateListL ( ) int x; ListNode head=NULL; LNode *s; scanf(“%d”, while ( x!=flag ) s = (LNode *) malloc (sizeof(LNode); /建立新结点 s-data=x; /插入到表前端 scanf(“%d”, return head; s-next=head; head=s; 后插法后插法 建立单链表建立单链表 n n 从一个空表开始，重复读入数据从一个空表开始，重复读入数据 ： uu用用mallocmalloc函数生成新结点函数生成新结点 uu读入的数据存放到新结点的读入的数据存放到新结点的datadata域域 中中 uu将该新结点插入到链表的将该新结点插入到链表的最后端最后端 n n 直到读入的数据等于结束符直到读入的数据等于结束符flagflag 为止。为止。 动画演示 关键：引入尾指针关键：引入尾指针r ,r ,总是指向表中尾结点总是指向表中尾结点 head s x=25 s s x=45x=18 254518 x= - 1 r flag值为-1 后插法后插法 建立单链表的建立单链表的 动画演示动画演示 对于空表与非空表，后插结点的操作对于空表与非空表，后插结点的操作 是否一致？是否一致？ 思考：思考： r 后插法后插法 建立单链表的两种情况：建立单链表的两种情况： x s headx s r r NULLNULL r -next= s; head =s; 空 表： 非空表： if (head=NULL) else r = s; r = s; LinkList CreateListR ( ) LinkList head = NULL; LNode *s, *r = NULL; int x; scanf (“%d”, while ( x != flag ) s = (LNode*) malloc(sizeof(LNode); s-data = x; if (head=NULL) head=s; else r-next= s; /插入到表尾 scanf(“%d”, if ( ) r-next= NULL; return head; r = s; r!=NULL n n 前插法与后插法比较前插法与后插法比较 uu前插法前插法：不用辅助存储变量，简单：不用辅助存储变量，简单 ；空表与非空表的操作；空表与非空表的操作一致一致 uu后插法后插法：需要辅助存储变量；空表：需要辅助存储变量；空表 与非空表的操作与非空表的操作不一致不一致 n n 为使空表与非空表的操作一致，为使空表与非空表的操作一致， 可在链表的头部加入可在链表的头部加入 “ “头结点头结点” ” 带头结点的单链表带头结点的单链表 n n 头结点位于表的最前端，本身不带数头结点位于表的最前端，本身不带数 据据, ,仅标志表头，可用仅标志表头，可用mallocmalloc语句申请头语句申请头 结点空间结点空间 n n 设置头结点的目的：设置头结点的目的： 统一空表与非空表的操作，简化链表操统一空表与非空表的操作，简化链表操 作作 空表空表 非空表非空表 ana1headhead x s r r-next = s; head x s r r-next = s; 空表空表 非空表非空表 r = s; r = s; 例：带头结点的单链表的后插法建立例：带头结点的单链表的后插法建立 结论：结论：带头结点的单链表带头结点的单链表同样也会简化其它同样也会简化其它 的链表操作（如：插入、删除）的链表操作（如：插入、删除） head p a0a1a2 j = 0 head p a0a1a2 j = 1 head p a0a1a2 j = 2 head p a0a1a2 j = 3 n n 计算带头结点的单链表长度计算带头结点的单链表长度 int Length ( LinkList head ) LNode *p = head; /指针 p 指示头结点 int j = 0; while (p-next != NULL ) /逐个结点检测 p = p-next; j+; return j; n n 计算带头结点的单链表长度计算带头结点的单链表长度 head 0 p j = 0 思考：空表是否适用该算法？思考：空表是否适用该算法？ int Length2 ( LinkList head ) int j; LNode *p = head; /指针 p 指示头结点 if (p-next = NULL) return 0; j=1; while (p-next != NULL ) /逐个结点检测 p = p-next; j+; return j; a1a2a3a4a5 head p j = 1 n n 计算不带头结点的单链表长度计算不带头结点的单链表长度 LNode * Find ( LinkList head, datatype x ) /在链表中从头查找数据域的值为x的结点 LNode * p = head-next; /检测指针 p 指示第 1 号结点 while ( p != NULL return p; n n 在单链表中按值查找在单链表中按值查找 head p a1a2a3 LNode * Locate ( LinkList head, int i ) /返回表中第 i 个元素的地址 LNode * p = head; int j = 0 ; /置 于表头 while (p-next != NULL j+; /找第 i 个结点 if (j = i ) return p; else return NULL; /返回第 i 个结点地址或NULL n n 在单链表中按序号查找（定位）在单链表中按序号查找（定位） head p a1a2a3 j = 0 ( (插入前插入前) () (插入后插入后) ) n n 后插结点：在后插结点：在* *p p之后插入之后插入* *s s s-next= p-next; p-next= s； s p s p 单链表中的插入与删除单链表中的插入与删除 n n 前插结点：前插结点：在在* *p p之前插入之前插入* *s s head p a0a1a2 s q qhead; while(q-next!= p) q=q-next; s-next=q-next ； q-next=s; int Insert ( LinkList head, int x, int i ) /在链表第 i (=0)个位置处插入新元素 x LNode * p = head，*s; p=Locate( head, i-1); /找第 i-1个结点 if ( p = NULL) printf( “无效的插入位置!n” ); return 0; else s=(Lnode*)malloc(sizeof(Lnode); /创建新结点 s-data=x ; s-next= p-next; p-next= s; return 1; O(n) n n 删除删除 uu删除结点删除结点 uu删除运算删除运算 ai-1 ai-1 ai ai ai+1 ai+1 qp 删除前 删除后 q-nest=p-next;q-nest=p-next; free(pfree(p); ); int Delete ( LinkList head, int i ) /在链表中删除第 i 个结点 LNode *p = head, *s; p=Locate( head, i-1); /找第 i-1个结点 if ( p = NULL) printf( “第i1个结点不存在!n” ); return -1; else if (p-next= NULL ) printf ( “第i个结点不存在” ); return 0; else s = p-next; p-next= s-next; free(s); /删除s return 1; O(n) head q a0a1a2 【练习练习1 1】单链表清空单链表清空 q q void makeEmpty ( LinkList head ) /删去链表中除表头结点外的所有其他 结点 LNode *q; while ( ) q = head-next; /将表头结点后第 1 个结点从链中 摘下 /释放它 head-next!= NULL head-next= q-next; free (q); 【练习练习2 2】写出函数体 单链表 单链表求和求和 函数函数 typedef int datatype; int sum ( LinkList head ) LNode * p = head-next; int sum = 0; while ( p != NULL ) sum += p-data; /累 加 p = p-next; return sum; 循环链表循环链表 (Circular List)(Circular List) n n 循环链表：使单链表最后一个结点循环链表：使单链表最后一个结点 的的 nextnext 指针不为指针不为 NULLNULL，而是指向了而是指向了 表的最前端。表的最前端。 n n 为简化操作，往往在循环链表中加为简化操作，往往在循环链表中加 入表头结点。入表头结点。 n n 特点：特点：只要知道表中某一结点的地只要知道表中某一结点的地 址，就可搜寻到所有其他结点的地址址，就可搜寻到所有其他结点的地址 。 n n 循环链表的示例循环链表的示例 n n 带表头结点的循环链表带表头结点的循环链表 a1a2a3an head an head a2a1 head (空表) (非空表) 循环链表的定义循环链表的定义 typedef char datatype; typedef struct cnode /链表结 点 datatype data; /结点数据域 struct cnode * next; /结点链 域 CircListNode; typedef CircListNode * CircLinkList; /循环链表头指针 CircLinkList head; /循环链 表头指针 查找成功 查找不成功 循环链表的查找循环链表的查找 head head 31 31 48 48 15 15 57 57 查找15 查找25 ppp ppppp 循环链表的查找算法循环链表的查找算法 CircListNode * Find ( CircLinkList head, datatype x ) /在链表中从头搜索其数据值为x的结点 CircListNode * p = head-next; /检测指针 p 指示第 0 号结点 while ( ) p = p-next; if (p-data =x) return p; p != head R1-next= R2-next-next; free(R2-next); R2-next=p; 双向链表双向链表 n n 双向链表是指在前驱和后继方向都双向链表是指在前驱和后继方向都 能遍历的线性链表。能遍历的线性链表。 n n 双向链表每个结点结构：双向链表每个结点结构： n n 通常采用带表头结点的循环链表形通常采用带表头结点的循环链表形 式。式。 前驱方向 前驱方向 后继方向后继方向 prior data nextprior data next n n 结点指向结点指向 p = pp = p-priorprior-nextnext = p = p-nextnext- - prior;prior; 非空表非空表 空表 空表 p-priorp-nextp priornext headhead 双向循环链表的定义双向循环链表的定义 typedef struct dnode datatype data; /数 据 struct dnode * prior, *next; /指 针 DblNode; typedef DblNode * DblList; /双 向链表 建立空的双向循环链表建立空的双向循环链表 void CreateDblList ( DblList if ( head = NULL ) printf( “存储分配错!” ); exit (1); head-llink = head-rlink = head; /表头结点的链指针指向自己 计算双向循环链表的长度计算双向循环链表的长度 int Length ( DblList head ) /计算带表头结点的双向循环链表 的长度 DblNode * p = head-rlink; int count = 0; while ( p != head ) p = p-rlink; count+; return count; 查找成功 查找不成功 双向循环链表的查找双向循环链表的查找 head head 31 31 48 48 15 15 57 57 查找15 查找25 ListNode * Find ( DblList head, datatype x ) /在双向循环链表中搜索含 x 的结点, 若找到, /则返回该结点的地址, 否则返回表头地址。 DblNode * p = head-rlink; while ( p != head return p; /也可以在 llink (前驱) 方向查找, 程序类似。 DblNode * Locate ( DblList head, int i ) if ( i rlink; int j = 0; while ( p != head j+; return p; /也可以在 llink (前驱) 方向查找, 程序类似。 定位：查找第定位：查找第 i i 个结点在链中的位置个结点在链中的位置 在双向链表的插入结点在双向链表的插入结点 314815 p q-next = p-next; q-prior = p; q-next-prior = q; p-next = q; 25 q 例：例：在在*p 后插入值为后插入值为2525的新结点的新结点 思考：若顺序如下，则语句应改为什么？思考：若顺序如下，则语句应改为什么？ 314815 p q-prior = p-prior; p-prior-next = q; q-next = p; p-prior = q; 25 q 双向循环链表的插入双向循环链表的插入 ( (空表空表) ) 在结点在结点 *p 后插入后插入25 p q-rlink = p-rlink; ( = head ) p-rlink = q; q-llink = p; q-rlink-llink = q; ( head-llink = q ) headhead q 25 p 25 q int Insert ( DblList head, int i, datatype x ) DblNode * p = Locate ( head, i-1 ); /指针定位于插入位置 if ( p = head DblNode * q =(listnode*)malloc(sizeof(listnode) ; q-data = x; q-llink = p; p-rlink-llink = q; /在前驱方向链入新结点 q-rlink = p-rlink; p-rlink = q; /在后继方向链入新结点 return 1; 删除删除4848 在双向链表中结点的删除结点在双向链表中结点的删除结点 head head 314815 p 3115 p-prior-next = p-next; p-next-prior = p-prior; 删除删除3131 双向循环链表的删除双向循环链表的删除 headhead 31 p p-rlink-llink = p-llink; p-llink-rlink = p-rlink; int Remove ( DblList head, int i ) DblNode * p = Locate ( head, i ); /指针定位于删除结点位置 if ( p = head ) return 0; p-rlink-llink = p-llink; p-llink-rlink = p-rlink; /将被删结点 *p 从链上摘下 delete p; /删去 return 1; 静态链表结构静态链表结构 SL= AV= AV= AV= SL=SL= SL= (10, 15, 20, 30, 50, 67, 78, 81 ) 静态链表定义静态链表定义 const int MaxSize = 100; typedef in