ch2线性表.ppt

第二章 线性表线性结构是一个数据元素的有序（次序）集。线性结构的特点：在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个外，集合中的每个数据元素均只有一个前驱，称为直接前驱（Immediate Predecessor）。除最后一个外，集合中的每个数据元素均只有一个后继，称为直接后继（ Immediate Successor）。2.1 线性表的类型定义一、定义：一个线性表是n个数据元素的有限序列niaaaa,21如例： 英文字母表（A,B,C,.Z)是一个线性表例：学号姓名年龄001张三18002李四19数据元素二、线性表的特征：v元素个数n称为表长度，n=0，称为空表v1in时l ai的直接前驱是ai1，a1无直接前驱l ai的直接后继是ai1，an无直接后继v元素同构，且不能出现缺项三、线性表抽象数据类型的定义ADT List 数据对象数据对象: D= ai | aiElemSet , i = 1,2,.,n, n 0数据关系数据关系: R1= |a i1 ,a iD, i = 1,2,.,n 基本操作：& 符号说明函数参数是引用型InitList(&L)DestroyList(&L)ClearList(&L) ListEmpty(L)ListLength(L) GetElem(L, i , &e)PutElem(&L, i, e)LocateElem(L , e)PriorElem(L , cur_e , &pre_e)NextElem(L , cur_e , &next_e)ListInsert(&L , i , e) ListDelete(&L , i , &e)ListTraverse(L, visit( ) 线性表初始化：线性表初始化： InitList(&L)InitList(&L)； 构造一个空的线性表L，即表的初始化。 求线性表的长度：求线性表的长度：ListLength (L)ListLength (L)； 返回线性表中数据元素的个数，即表长 。 取表中元素：取表中元素：GetElem(L, i,&e)GetElem(L, i,&e)； 取线性表L中的第i个结点，要求1iListLength(L) 插入操作：插入操作：ListInsert (&L, i, e)ListInsert (&L, i, e)； 在线性表L的第i个位置上插入一个值为e的数据元素。(5)(5)删除操作：删除操作：ListDelete (&L, i ,&e)ListDelete (&L, i ,&e)； 在线性表L中删除位序为 i 的数据元素。 按值查找：按值查找：LocateElem(L, e)LocateElem(L, e)； 在L中查找值为e的结点，并返回该结点在L中的位置。若L中有多个结点的值和e e相同，则返回首次找到的结点位置；若L中没有结点的值为e e，则返回一个特殊值(如零)表示查找失败。课后思考：应用基本操作实现课后思考：应用基本操作实现删除线性表删除线性表LaLa中大于中大于e e的所有的所有数据元素：数据元素：DelElems(&L,e)DelElems(&L,e)CopyList(La,&Lb)/CopyList(La,&Lb)/应用基本操作：实现应用基本操作：实现CopyList(La,&Lb)CopyList(La,&Lb) InitList(Lb) InitList(Lb)； LenA=ListLength(La);LenA=ListLength(La); for(i=1;i=LenA;i+) for(i=1;i=LenA;i+) GetElem(La,i,e); GetElem(La,i,e); ListInsert(Lb,i,e); ListInsert(Lb,i,e); 课堂练习：课堂练习：应用基本操作实现应用基本操作实现CopyList(La,&Lb)CopyList(La,&Lb)例例1:1:设计求设计求 A = AA = AB B 的算法的算法l分析：建立线性表分析：建立线性表 La、Lb分别表示集合分别表示集合A和和B，将，将Lb中存中存在而在而La中不存在的元素中不存在的元素e插入插入 La中，因此，中，因此，本算法的基本操本算法的基本操作是查找作是查找(比较比较)。算法算法思想思想： 1. 从从Lb中依次取得每个元素中依次取得每个元素e GetElem (Lb, i, e) 2. 判断该元素判断该元素e是否在是否在La中存在中存在 LocateElem (La, e) 3.若不存在，则将元素若不存在，则将元素e插入到插入到La中中 ListInsert (La, i, e)l基于基于逻辑逻辑结构的算法描述：结构的算法描述： void Union( &La , Lb) La_len=ListLength(La); Lb_len=ListLength(Lb); for(i=1; i=Lb_len; i+ +) GetElem(Lb, i, e); if (!LocateElem(La, e) ListInsert(La, + +La_len, e); l例例2：巳知线性表：巳知线性表LA和线性表和线性表LB中的数据元素按值非递减中的数据元素按值非递减有序排列，现要求将有序排列，现要求将LA和和LB归并为一个新的线性表归并为一个新的线性表LC，且，且LC中的元素仍按值非递减有序排列。中的元素仍按值非递减有序排列。Init_List (LC) Length_List (LA)& Length_List (LB)判断：若i所指元素 j所指元素，则将i所指元素插入在LC的k+1前(即LC的表尾)，且i、k的值分别+1;否则，将j所指元素插入在LC的k+1前(即LC的表尾)，且j、k的值分别+1;2.2 线性表的顺序表示和实现一、顺序表（Sequential List）1、定义：用一组地址连续的存储单元存放一个线性表叫2、元素地址计算方法：vLOC(ai)LOC(a1)+(i1)*LvLOC(ai+1)LOC(ai) Lv其中：l L 一个元素占用的存储单元个数l LOC(ai)线性表第i个元素的地址3、顺序表的特点：v实现逻辑上相邻物理地址相邻v实现随机存取4、顺序表的实现：可用C语言的一维数组实现a1a2an01n-112n内存V数组下标元素序号M-1#define List_Init_Size 100typedef int ElemType ; typedef ElemType ET;typedef struct ElemType *elem; /动态空间基址 int length; /实际元素个数 int listsize; /当前分配的存储容量 /(以sizeof(ElemType)为单位) SqList; 备用空间声明结构体类型， SqList 是顺序表的类型名动态申请和释放内存空间L.elem = (ElemType *)malloc(List_Init_Size*sizeof(ElemType); /申请内存free(L.elem); /释放内存typedef struct ElemType *elem ; int length ; int listsize ;SqList ; int ListLength_Sq(SqList L) void ClearList_Sq(SqList &L) 访问顺序表L中第3个元素：L.elem2 e=L.elem2; L.elem2=8; GetElem_Sq(SqList L, int i, ElemType &e) 525L5 5个有效数据个有效数据25个元素存储空间L L表的基址（数组名）是表的基址（数组名）是 L.elemL.elem关于数据类型名StatusStatusStatus是是“状态状态”的意思，不是的意思，不是C C语言中的关键字，其语言中的关键字，其目的是为了增强算法的目的是为了增强算法的“可读性可读性”typedef int Status;typedef int Status;StatusStatus型的数据范围是型的数据范围是: True: True、FalseFalse、OkOk、Error Error #define True 1 #define True 1 #define False 0#define False 0Status ListEmpty(SqList L)Status ListEmpty(SqList L)/判断线性表判断线性表L L是否为空表是否为空表 if ( L.length = =0)if ( L.length = =0) return True; return True; return False; return False; 顺序表基本操作的算法描述顺序表基本操作的算法描述/构造一个空的线性表构造一个空的线性表 L L#define List_Init_Size 10 /#define List_Init_Size 10 /存储空间的初始分配量存储空间的初始分配量#define ListIncrement 10 /#define ListIncrement 10 /存储空间的分配增量存储空间的分配增量Status Status InitList_Sq( SqList InitList_Sq( SqList & &L)L) L.elem=(ET L.elem=(ET * *) )mallocmalloc(List_Init_Size(List_Init_Size* *sizeofsizeof(ET);(ET); if if (L.elem = = NULL) (L.elem = = NULL) exitexit(OVERFLOW); (OVERFLOW); / /* *存储分配失败存储分配失败* */ / L.length=0; L.length=0; / /* * 空表的长度空表的长度 * */ / L.listsize=List_Init_Size; L.listsize=List_Init_Size; / /* * 初始存储容量初始存储容量 * */ / returnreturn OK; OK; 添加（添加（1 1，3 3，5 5，7 7，9 9）之后的状态：）之后的状态：创建空表之后，表创建空表之后，表L L的状态如下：的状态如下：L.0 0101024 4 12 1 3 5 7 11 0 31010个元素存储空间个元素存储空间删除第删除第3 3个元素之后的状态：个元素之后的状态：4 41010L. 1 3 7 9 9 5 7 11 0 31010个元素存储空间个元素存储空间是随机数据也是随机数据也就是无效数据就是无效数据顺序表的内存状态 问题：问题：在表的第在表的第1 1个位置插入个位置插入 6 6 之之后，表后，表L L的存储状态如何？的存储状态如何？问题：清空问题：清空L,L,即即 ClearList_Sq(L)ClearList_Sq(L)之后，表之后，表L L的存储状态如何？的存储状态如何？5 51010L. 1 3 5 7 9 5 7 11 0 31010个元素存储空间个元素存储空间添加（添加（1 1，3 3，5 5，7 7，9 9）之后的状态：）之后的状态：5 51010L. 1 3 5 7 91010个元素存储空间个元素存储空间创建空表之后，表创建空表之后，表L L的状态如下：的状态如下：L.0 010101010个元素存储空间个元素存储空间删除第删除第3 3和第和第4 4个元素之后的状态：个元素之后的状态：3 31010L. 1 3 91010个元素存储空间个元素存储空间将随机数据想将随机数据想象成空白象成空白顺序表的内存想象状态结论：凡是定义的结论：凡是定义的 或或 动态申动态申请的空间内，都想象为空白。请的空间内，都想象为空白。如如: : int x,A900; int x,A900; SqList L; SqList L; ElemType ElemType * *elem;elem;二、顺序表的插入操作 定义：顺序表的插入是指在第i个（1i n+1）元素之前插入一个新的数据元素x，使长度为 n 的线性表niiaaaaa,1,21 变成长度为 n+1 的线性表niiaaxaaa,1,21 需将第i至第n共（ni1)个元素依次后移一个位置。内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1an-1x顺序表的插入操作顺序表的插入操作在顺序表在顺序表L L中第中第i i个位置上插入一个新的元素个位置上插入一个新的元素e e, ,形式参数为：形式参数为：&L ,i , e&L ,i , e ；算法步骤如下：算法步骤如下：(1)(1)对输入参数的安全性检查对输入参数的安全性检查: : 插入位置插入位置 i i 应落应落在表长范围内，即：在表长范围内，即：1 1 i i L.length+1 L.length+1(2)(2)存储空间的处理：存储空间的处理：若原表的存储空间已满，应若原表的存储空间已满，应追加存储空间的分配；追加存储空间的分配；(3)(3)数据块的搬移：数据块的搬移：将表中从将表中从i i到到L.lengthL.length位置上位置上的所有元素依次往后移动一个位置；的所有元素依次往后移动一个位置；(4)(4)在第在第i i个位置上存储新的元素个位置上存储新的元素e,e,表长增，即表长增，即+L.lengthL.length 。注意：逻辑位置（序号）注意：逻辑位置（序号）i i 对应的存储下标是对应的存储下标是i-1i-1。重新分配动态存储空间的函数重新分配动态存储空间的函数realloc(原动态区首址，字节数原动态区首址，字节数)其功能为：其功能为：(1)(1)申请申请新的动态存储空间新的动态存储空间( (成功或失败成功或失败););(2)(2)将原动态区的数据将原动态区的数据拷贝拷贝到新动态区到新动态区; ;(3)(3)释放释放原动态存储区原动态存储区; ;(4)(4)返回返回新存储区首地址（无类型）。新存储区首地址（无类型）。用途：当原动态存储区不够用时，追加动态存储用途：当原动态存储区不够用时，追加动态存储区；区；顺序表的插入操作算法描述之一顺序表的插入操作算法描述之一Status ListInsert_Sq(SqList &L , int i , ET e) if ( iL.length+1) return ERROR; /i值不合法值不合法 if (L.length = L.listsize) /当前存储空间已满，增加分配当前存储空间已满，增加分配 p=(p=(ETET * *)realloc(L.elem,)realloc(L.elem,(L.listsize+ ListIncrement)(L.listsize+ ListIncrement)* *sizeof(sizeof(ETET) );); if (p=NULL) exit(OVERFLOW); /存储分配失败存储分配失败 L.elem=p; /新的基地址新的基地址 L.listsize+=ListIncrement; /增加存储容量增加存储容量 for ( j=L.length ; j=i ; -j ) L.elemj=L.elemj-1; /移动元素移动元素 L.elemj=e ; /插入新元素插入新元素 +L.length ; /表长增表长增1 return OK; 基于存储结构进行算法实现Status ListInsert_Sq(SqList &L , int i , ET e) if ( iL.length+1) return ERROR; if (L.length = L.listsize) p=( p=(ETET * *)realloc(L.elem,)realloc(L.elem,(L.listsize+ ListIncrement)(L.listsize+ ListIncrement)* *sizeof(sizeof(ETET) );); if (p=NULL) exit(OVERFLOW); L.elem=p; L.listsize+=ListIncrement; q=&(L.elemi-1); /* q=L.elem+(i-1) 为插入位置为插入位置 */ for (p=&(L.elemL.length-1); p=q; -p) *(p+1)=*p; /*移动元素移动元素*/ *q=e ; /*插入新元素插入新元素*/ +L.length ; /*表长增表长增1*/ return OK; 顺序表的插入操作算法描述之二顺序表的插入操作算法描述之二基于存储结构进行算法实现顺序表插入操作的算法评价顺序表插入操作的算法评价v设 Pi 是在第 i 个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时，所需移动的元素次数的平均次数为：11)1(niiinPEis nOnTninnEisnPnii112)1(1111则若认为三、顺序表的删除操作 定义：线性表的删除是指将第i（1i n）个元素删除，使长度为n的线性表niiaaaaa,1,21 变成长度为n-1的线性表niiaaaaa,11,21 需将第i+1至第n共（ni)个元素依次前移一个位置。内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1内存a1a2ai+1V数组下标01i-1n-2in-112i元素序号i+1n-1nanai+2 顺序表的删除操作顺序表的删除操作删除顺序表删除顺序表L L中第中第i i个位置上的元素，将删除的元素值赋给个位置上的元素，将删除的元素值赋给e e。形式参数为：形式参数为：&L, i, &e&L, i, &e 算法步骤如下：算法步骤如下：(1)(1)对输入参数的安全性检查对输入参数的安全性检查: : 删除位置删除位置 i i 应落在表长范应落在表长范围内，即：围内，即：1 1 i i L.lengthL.length ；(2)(2)取出删除的元素值赋给取出删除的元素值赋给e e ；(3)(3)数据块的搬移数据块的搬移：将表：将表L L中从中从i+1i+1到到L.lengthL.length位置上的所位置上的所有元素往前移动一个位置；有元素往前移动一个位置；(4)(4)表长减表长减：-L.length-L.length 。顺序表的删除操作算法描述一顺序表的删除操作算法描述一Status ListDelete_Sq(SqList &L , int i , ET &e) if (iL.length) return ERROR; /i值不合法值不合法 e=L.elemi-1; /被删除元素的值赋给被删除元素的值赋给e for( j=i ; jL.length; j+) L.elemj-1=L.elemj; /移动元素移动元素 -L.length; /表长减表长减1 return OK; 顺序表的删除操作算法描述二顺序表的删除操作算法描述二Status ListDelete_Sq(SqList &L , int i , ET &e) if (iL.length) return ERROR; /i值不合法值不合法 p=&(L.elemi-1; ) /p为被删除元素的位置为被删除元素的位置 e=*p; /被删除元素的值赋给被删除元素的值赋给e q=L.elem+L.length-1; /q为表尾元素的位置为表尾元素的位置 for ( +p; p=q; +p) *(p-1)=*p; /移动元素移动元素 -L.length; /表长减表长减1 return OK; 顺序表删除操作的算法评价顺序表删除操作的算法评价v设Qi 是删除第i个元素的概率，则在长度为n的线性表中删除一个元素所需移动的元素次数的平均次数为：niideinQE1)( nOnTninnEnQnidei121)(11则若认为故在顺序表中插入或删除一个元素时，平均约移动表中一半元素，当n很大时，效率很低。顺序表的定位操作顺序表的定位操作算法要求：在顺序表算法要求：在顺序表L中，查找第中，查找第 1 个值与数值个值与数值 e 相等的元素的位序。若找到，返回其在相等的元素的位序。若找到，返回其在L中的位中的位序，否则，返回序，否则，返回0；算法描述：算法描述： int LocateElem_Sq(SqList L , ET e) 请填写算法描述请填写算法描述； 算法分析：基本操作是什么？时间复杂度是多少？算法分析：基本操作是什么？时间复杂度是多少？Status GetElem_Sq(SqList L , int i , ET &e) if (iL.length|!L.elem) return ERROR; e=L.elemi-1; return OK;算法转换为C语言子程序的规则：引用型改为指针型Status GetElem_Sq(SqList L , int i , ET *e) if (iL.length |!L.elem) return ERROR; *e=L.elemi-1; return OK;顺序表的取值操作顺序表的取值操作顺序存储结构的优缺点顺序存储结构的优缺点v优点l逻辑相邻，物理相邻l可随机存取任一元素l存储空间使用紧凑v缺点l插入、删除操作需要移动大量的元素l预先分配空间需按最大空间分配，利用不充分l表容量难以扩充1编写程序实现顺序表的下列基本操作：编写程序实现顺序表的下列基本操作： (1)初始化顺序表初始化顺序表La。 (2)将将La置为空表。置为空表。 (3)销毁销毁La。 (4)在在La中插入一个新的元素。中插入一个新的元素。 (5)删除删除La中的某一元素。中的某一元素。 (6)在在La中查找某元素，若找到，则返回它在中查找某元素，若找到，则返回它在La中第一中第一次出现的位置，否则返回次出现的位置，否则返回0。 (7)打印输出打印输出La中的元素值。中的元素值。上机上机作业作业11顺序表基本操作（顺序表基本操作（2 2学时）学时）能力培养：通过实现顺序表的基本操作和具体的函数定义，掌能力培养：通过实现顺序表的基本操作和具体的函数定义，掌握程序的输入、编辑、调试和运行过程。握程序的输入、编辑、调试和运行过程。PracticeEngineering2 2编写程序完成下面的操作：编写程序完成下面的操作：(1)(1)构造两个顺序线性表构造两个顺序线性表LaLa和和LbLb，其元素都按值非递减顺序排列。，其元素都按值非递减顺序排列。(2)(2)实现归并实现归并LaLa和和LbLb得到新的顺序表得到新的顺序表LcLc，LcLc的元素也按值非递减顺的元素也按值非递减顺序排列。序排列。(3)(3)假设两个顺序线性表假设两个顺序线性表LaLa和和LbLb分别表示两个集合分别表示两个集合A A和和B B，利用，利用union_Squnion_Sq操作实现操作实现A=A A=A B B。上机上机作业作业11顺序表基本操作（续）顺序表基本操作（续）能力培养：训练学生通过顺序表的一些基本操作来解决实际问能力培养：训练学生通过顺序表的一些基本操作来解决实际问题的能力。题的能力。EngineeringPractice2.3 线性表的链式表示和实现线性表链式存储的特点：v用一组任意的存储单元存储线性表的数据元素v利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素v每个结点，除存储元素ai本身信息外，还需存储其直接后继元素ai+1的地址信息v结点（Node）l数据域：元素本身信息l指针域：指示直接后继的存储位置数据域 指针域结点ZHAOQIANSUNLIZHOUWUZHENGWANGH例： 线性表 (ZHAO, QIAN, SUN, LI, ZHOU, WU, ZHENG, WANG)43131NULL3771925数据域指针域LIQIANSUNWANGWUZHAOZHENGZHOU存储地址1713192531374331H头指针2、实现：typedef struct Node ElemType data; struct Node *next;LNode , *LinkList;/Lnode是结点类型名，/ LinkList是结点指针类型名 LinkList L; LNode *p;datanextL结点(*p)(*p)表示p所指向的结点(*p).datap data表示p指向结点的数据域(*p).nextp next表示p指向结点的指针域生成一个LNode型新结点：p = ( LNode * ) malloc (sizeof( LNode ); 或：p = ( LinkList ) malloc (sizeof( LNode );系统回收p结点：free(p)一、线性链表一、线性链表1、定义：每个结点中只含一个指针域的链表叫，也叫单链表 (Single Linked List)头结点：在单链表第一个结点前附设加一个结点叫头结点：在单链表第一个结点前附设加一个结点叫头结点指针域为空表示线性表为空表。头结点指针域为空表示线性表为空表。La1a2头结点an .L空表头指针头指针 L 是是LinkList类型，头结点是类型，头结点是Lnode类型类型 非空表：非空表： 空表：空表： 注意：注意：头结点的位序为头结点的位序为0 0，它不是线性表中的元素，它不是线性表中的元素，头结点的数据域可用于存储线性表的长度头结点的数据域可用于存储线性表的长度。单链表是非随机存取的存储结构单链表是非随机存取的存储结构 在单链表中，任何两个元素的存储位置之间在单链表中，任何两个元素的存储位置之间没有固定的联系，每个元素的没有固定的联系，每个元素的存储位置存储位置都包含在都包含在其其直接前驱结点的指针域中直接前驱结点的指针域中。 在单链表中，要取得第在单链表中，要取得第 i 个数据元素必须个数据元素必须从头从头结点结点出发寻找。出发寻找。头5836 L头L Status InitList_L (LinkList &L) L=( LinkList ) malloc ( sizeof ( Lnode ) ); if (L= =NULL) exit (OVERFLOW); /* L data=0;*/ L next = NULL; return OK; 时间复杂度：时间复杂度：O(1) L L 必须必须是引用型是引用型构造一个空的单链表的算法描述构造一个空的单链表的算法描述1. 指针指针p在链表上依次滑动：在链表上依次滑动：p=head; while (p next!=NULL) p=p next; 2. 前驱指针前驱指针 q 和当前指针和当前指针 p在链表上同步滑动：在链表上同步滑动： q=head ; p=q next; while(p) q=p ; p=q next; 例例1：int ListLength_L( LinkList L) /求线性表的长度求线性表的长度 p=L; j=0; while(p next!=NULL) 或或 while(p next) +j; p=p next; return(j);例例2： Status PriorElem_L (LinkList L, ET e, ET &pre) q=L; p=q next; while(p & p data!=e) q=p;p=q next; 例例3： Status NextElem_L(LinkList L,ET e, ET &next)单链表算法中的关键步骤的算法描述单链表算法中的关键步骤的算法描述单链表的基本运算单链表的基本运算查找查找在单链表在单链表L中，中，读取读取第第i个元素的值赋给参数个元素的值赋给参数e Status GetElem_L (LinkList L, int i, ElemType &e) p=L next ; j=1; /j为计数器为计数器 while (p&j i) 或或if (p= = NULL| j i) /第第i个元素不存在个元素不存在 return ERROR; e = p data; /取出第取出第i个元素的值赋给个元素的值赋给e return OK; 时间复杂度为：时间复杂度为：O(n) 问题：在顺序表中问题：在顺序表中GetElem_Sq时间复杂度是多少？时间复杂度是多少？在单链表在单链表L L中的第中的第i i个结点之前个结点之前插入元素插入元素e e的操作步骤：的操作步骤： (1)(1)寻找第寻找第i-1i-1个结点；个结点； /O(n)/O(n) (2) (2)测试已知量的合法性；测试已知量的合法性；/O(1)/O(1) (3) (3)申请一个新结点，并给其数据域赋值为申请一个新结点，并给其数据域赋值为e e； / O(1)/ O(1) (4) (4)新结点插入到单链表新结点插入到单链表L L中的第中的第i i个结点之前。个结点之前。/O(1)/O(1) 该算法的时间复杂度是：该算法的时间复杂度是：O(n)O(n)单链表的基本运算单链表的基本运算插入插入pai-1aies s next=p next ; p next = s ; Status ListInsert_L (LinkList &L, int i, ElemType e) p=L; j=0; /j为计数器为计数器 while (p& ji1) 或者或者if (p= =NULL | ji1) return ERROR; /i大于表长大于表长+1或者或者i小于小于1 s = ( LinkList ) malloc ( sizeof ( Lnode ) ); /申请新结点申请新结点s if (s = NULL) exit (OVERFLOW); s data=e; s next=p next ; / 在在 p结点结点之后插入新结点之后插入新结点s p next = s ; return OK;单链表的基本运算单链表的基本运算插入插入在单链表在单链表L L中删除第中删除第i i个结点，并由个结点，并由e e返回其值的操作步骤：返回其值的操作步骤： (1)(1)寻找第寻找第i-1i-1个结点；个结点； /O(n)/O(n) (2) (2)测试已知量的合法性；测试已知量的合法性； /O(1)/O(1) (3) (3)删除第删除第i i个结点，并取出数据域的值赋给个结点，并取出数据域的值赋给e e；/ O(1)/ O(1) (4) (4)释放第释放第i i个结点的存储空间。个结点的存储空间。/O(1)/O(1) 该算法的时间复杂度是：该算法的时间复杂度是：O(n)O(n)单链表的基本运算单链表的基本运算删除删除pai-1aiai+1p next = q next;qStatus ListDelete_L (LinkList &L, int i, ElemType &e) p=L; j=0; /j为计数器为计数器 while (p next & ji1 ) /i大于表长或者大于表长或者i小于小于1 return ERROR; q=pnext; /q指向要删除的结点指向要删除的结点ai p next=q next ; / 删除删除结点结点ai e=q data; free(q); /释放释放结点结点ai的存储空间的存储空间 return OK;单链表的基本运算单链表的基本运算删除删除逆位序输入n个元素的值，建立带表头结点的单链表L。算法评价：T(n) O(n)L头结点an 0L头结点an-10an a2.L头结点an-10an La1a2头结点an .0L头结点0动态建立单链表的算法动态建立单链表的算法逆向建立逆向建立Void CreateList_L (LinkList &L, int n)/建立一个带头结点的单链表建立一个带头结点的单链表L L=( LinkList ) malloc ( sizeof ( Lnode ) ); /L指向头结点指向头结点 L next = NULL; for ( i=n; i0; -i ) p=( LinkList ) malloc ( sizeof ( Lnode ) ); /p为新结点为新结点 scanf(&p data); /为结点为结点p的数据域赋值的数据域赋值 p next=L next ; /为结点为结点p的指针域赋值的指针域赋值 Lnext=p; /将结点将结点p插入到表头插入到表头 动态建立单链表的算法动态建立单链表的算法逆向建立逆向建立单链表特点它是一种动态结构，整个存储空间为多个链表共用不需预先分配空间，分配的空间连续与否均可指针占用额外存储空间不能随机存取，查找速度慢，便于插入、删除操作线性表的顺序存储和链式存储操作上的比较顺序存储顺序存储链式存储链式存储循环控制变量循环控制变量下标变量下标变量i指针变量指针变量p初始化初始化i=0；p=head; 或或p=head-next;循环条件循环条件idata） （p-next）下一对象下一对象i+;p=p-next;1编写程序实现单链表的下列基本操作：编写程序实现单链表的下列基本操作： (1)初始化单链表初始化单链表La。 (2)在单链表在单链表La中插入一个新结点。中插入一个新结点。 (3)删除单链表删除单链表La中的某一个结点。中的某一个结点。 (4)在单链表在单链表La中查找某结点并返回其位置。中查找某结点并返回其位置。 (5)打印输出单链表打印输出单链表La中的结点元素值。中的结点元素值。2构造两个带有表头结点的有序单链表构造两个带有表头结点的有序单链表La、Lb，编写程序实，编写程序实现将现将La、Lb合并成一个有序单链表合并成一个有序单链表Lc。上机上机作业作业22单链表基本操作（单链表基本操作（2 2学时）学时）能力培养：掌握对单链表的一些基本操作和具体的函数定义，能力培养：掌握对单链表的一些基本操作和具体的函数定义，通过实现两个有序表归并，训练单链表的一些基本操作。通过实现两个有序表归并，训练单链表的一些基本操作。EngineeringPractice二、循环链表 (Circular Linked List)v循环链表是表中最后一个结点的指针指向头结点，使链表构成一个环状v特点：从表中任一结点出发均可找到表中其他结点，提高了查找效率v循环链表操作与单链表基本一致，循环结束条件不同l单链表单链表L：p next = =NULLl循环链表循环链表L：p next = = Lv非空循环链表非空循环链表v空循环链表空循环链表头5836L头L仅设尾指针的两循环链表的链接仅设尾指针的两循环链表的链接AB存储池存储池p Void *Connect( LinkList &A, LinkList &B) LinkList *p; pA-next; A-nextB-next-next; free(B-next); B-nextp; 仅设尾指针的两循环链表的链接算法仅设尾指针的两循环链表的链接算法三、双向链表（Double Linked List）单链表具有单向性的缺点,所以引入双向链表。v结点定义typedef struct DuLNode ElemType data; struct DuLNode *prior,*next;DuLNode, *DuLinkList;priordatanextL空双向循环链表：非空双向循环链表： LABaiai+1ai-1pp prior next = p= p next proir ;算法评价：T(n)=O(n)eSaiai-1P插入操作算法描述Status ListInsert_DuL(DuLinkList &L, int i, ElemType e) if (!(p=GetElemP_DuL(L, i) /确定第确定第i个元素的位置指针个元素的位置指针p return ERROR; if (!(s = (DuLinkList)malloc(sizeof