《数据与结构算法中对线性表的理解》由会员分享，可在线阅读，更多相关《数据与结构算法中对线性表的理解（108页珍藏版）》请在金锄头文库上搜索。
1、n n线性表线性表n n顺序表顺序表 n n链表链表n n顺序表与链表的顺序表与链表的 比较比较线性表线性表 (Linear List)(Linear List)n n线性表的定义和特点线性表的定义和特点uu 定义定义 n n（ 0 0）个数据元素的有限序列个数据元素的有限序列 ，记作，记作 （a a1 1 , a a2 2 , , a an n）a ai i 是表中数据元素，是表中数据元素，n n 是表长是表长, , n=n=0 0时时 为空表为空表uu遍历遍历 逐项访问：逐项访问：从前向后从前向后 从后向前从后向前 线性表的特点线性表的特点n n除第一个元素外，其他每一个元除第一个元素外，
2、其他每一个元 素有且仅有一个素有且仅有一个直接前驱直接前驱n n除最后一个元素外，其他每一个除最后一个元素外，其他每一个 元素有且仅有一个元素有且仅有一个直接后继直接后继a1a2a3a4a5uu 线性表的初始化线性表的初始化 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_Lis
3、tInsert_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 访问访问 顺序存取顺序存取, , 随机存
4、取随机存取 25 34 57 16 48 09 0 1 2 3 4 5 data顺序表的连续存储方式顺序表的连续存储方式35 27 49 18 60 54 77 83 41 021 2 3 4 5 6 7 8 9 10l 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; /当前元
5、素个数 SeqList; SeqList *L; (或 SeqList L;)L.dataL.dataa5a4a3a2a101234L.lastL.last = =L Ldatadataa5a4a3a2a101234L Llastlast = =Maxsize-1Maxsize-1顺序表基本运算的实现顺序表基本运算的实现n n顺序表的初始化顺序表的初始化SeqList *inti_Seqlist( )SeqList *L; L=(SeqList*) malloc (sizeof(SeqList); Llast = -1; return L;n n求表的长度求表的长度int Length ( S
6、eqList * 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查找 16iL last0 1 2 3 4 5查找成功，返回查找成功，返回i i的值的值查找 5025 34 57 16 48 09 0 1 2 3 4 5 dataiL last0 1 2 3 4 5查找失败，返
7、回查找失败，返回1 1查找成功的平均比较次数查找成功的平均比较次数若查找概率相等，则：若查找概率相等，则：查找不成功查找不成功 ，数据比较，数据比较 n 次次O(n)25 34 57 16 48 09 630 1 2 3 4 5 6 7data5025 34 57 0 1 2 3 4 5 6 7data50i=4例:在第个位置(i=4)插入一个值为50的新元素 Llastn n插入运算：在顺序表的第插入运算：在顺序表的第 i i (1i (1i n+1)n+1)个位置插入一个值为个位置插入一个值为 x x 的新元素的新元素63094816i与Llast的关系？int Insert ( SeqL
8、ist *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 +2i-1Ldatai-1n n算法分析算法分析：n n在顺序表上做插入操作需要移动表中一半在顺序表上做插入操作需要移动表中一半 的元素的元素n n时间复杂度为时间复杂度为(n)(n)1625 34 57 16 48
9、09 630 1 2 3 4 5 6 7data25 34 57 0 1 2 3 4 5 6 7datai=4例:将表中第个位置(i=4)上的元素删除Llastn n删除运算：将顺序表中的第删除运算：将顺序表中的第 i i (1i (1i n)n)个元素从表中删除个元素从表中删除630948i与Llast的关系？int Delete ( SeqList *L, datatype x ) /删除表中第 i 个位置上的元素if (i Llast +1) return 0;for ( ; j dataix)i+; if (L-datainext= s-next= ？ 如何利用如何利用nextnext
10、指针在空指针在空表的基础上建立一非空的单链表？表的基础上建立一非空的单链表？n n申请结点空间：申请结点空间：LNode *s;s = (LNode )malloc(sizeof(LNode);s-data = x; LinkList head = NULL;前插法前插法 建立单链表建立单链表n n从一个空表开始，重复读入数据从一个空表开始，重复读入数据：uu用用mallocmalloc函数生成新结点函数生成新结点uu读入的数据存放到新结点的读入的数据存放到新结点的datadata域域中中uu将该新结点插入到链表的将该新结点插入到链表的最前端最前端n n直到读入的数据等于结束符直到读入的数据等
11、于结束符flagflag为止。为止。动画演示s25headflag值为-1x=25ss x=45x=184518x= - 12 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”, ret
12、urn head; s-next=head; head=s;后插法后插法 建立单链表建立单链表n n从一个空表开始，重复读入数据从一个空表开始，重复读入数据：uu用用mallocmalloc函数生成新结点函数生成新结点uu读入的数据存放到新结点的读入的数据存放到新结点的datadata域域中中uu将该新结点插入到链表的将该新结点插入到链表的最后端最后端n n直到读入的数据等于结束符直到读入的数据等于结束符flagflag为止。为止。动画演示 关键：引入尾指针关键：引入尾指针r ,r ,总是指向表中尾结点总是指向表中尾结点heads x=25ss x=45x=18254518x= - 1rfla
13、g值为-1后插法后插法 建立单链表的建立单链表的 动画演示动画演示对于空表与非空表，后插结点的操作对于空表与非空表，后插结点的操作 是否一致？是否一致？思考：思考：r后插法后插法 建立单链表的两种情况：建立单链表的两种情况：xsheadxsrrNULLNULLr -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 =
14、 (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!=NULLn n前插法与后插法比较前插法与后插法比较uu前插法前插法：不用辅助存储变量，简单：不用辅助存储变量，简单；空表与非空表的操作；空表与非空表的操作一致一致uu后插法后插法：需要辅助存储变量；空表：需要辅助存储变量；空表与非空表的操作与非空表的操作不一致不一致n n为使空表与非空表的操作一致，为使空表与非空表的操作一致， 可在链表的头部加入可在链表
