《数据结构(c语言版)第二单元复习纲要》由会员分享，可在线阅读，更多相关《数据结构(c语言版)第二单元复习纲要（8页珍藏版）》请在金锄头文库上搜索。
1、第二章 线性表2.1线性表的类型定义【线性表】是一个n个数据元素的有限序列线性表中的数据元素既可以是一个数字或者字符，如：（A, B, C, D, E, ）或者（6, 17, 23, 14, 56, 11）数据元素也可能是由由多个数据项构成的记录，如：姓名学号性别年龄班级健康状况张三209871男231良好李四3213857男212良好王五23413241男241良好【线性表的特点】：u 存在唯一的一个称作“第一个”的数据元素u 存在唯一的一个被称作“最后一个”的数据元素u 除第一个之外，集合中每一个元素均只有一个前驱u 除最后一个外，集合中每一个元素均只有一个后继【线性表的长度】：线性表中元
2、素的个数【空表】：元素个数n=0时，称为空表【注】线性表是指一种逻辑结构2.2线性表的顺序表示和实现【线性表的顺序存储表示】指的是用一组地址连续的存储单元依次存储线性表的数据元素假设线性表的每个元素需占用l个存储单元，设线性表第i个数据元素的存储位置为LOC(ai)，第i+1个数据元素的存储位置LOC(ai+1)则满足下列关系：LOC(ai+1) = LOC(ai) + l【顺序表】：通常称顺序结构的线性表为顺序表【特点】：逻辑上相邻的元素的存储位置也相邻，可以随机存取，因此，线性表是一种可以随机存取的数据结构。序号数据元素112213321424528630742777由于顺序表中，逻辑上相
3、邻的元素在物理位置上也相邻，因此在数据的插入和删除时需要移动元素。序号数据元素11221332142452562873074277在数据24后插入数据25由于原来逻辑上24和28相邻，因此在物理位置上24和28相邻，在24后插入元素25，24同元素25相邻，25和24、28相邻，因此需要移动数据元素序号数据元素112213321424528630742777序号数据元素1122133214285306427777删除数据24后原来数据24和21、28相邻，删除24后，21和28相邻，因此需要移动数据。【一般情况下】：l 假设顺序表有n个元素，在第i个位置之前插入一个元素时，需要将第n至第i个元
4、素向后移动一个位置，将第i个位置空出来，插入新元素。l 假设顺序表有n个元素，将第i个位置的元素删除，需要将从第i+1至第n（共n-i）个元素依稀向前移动一个位置。l 当在顺序表中插入和删除数据元素时，其时间主要耗费在移动元素上，而移动元素的个数取决于插入或删除元素的位置l 在等概率情况下，顺序表中删除或插入一个数据元素，平均约移动表中一半元素2.3 线性表的链式表示和实现线性链表【特点】用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）【举例】【结点结构】单链表的结点有两个域：数据域和指针域数据域用来存放单链表的数据信息指针域存放下指向下一个结点的指针，即
5、下一个结点的存储位置【线性链表&单链表】由于链表中每一个结点只包含一个指针域，因此又称单链表或线性链表。【头结点】为了操作方便有时在单链表的第一个结点之前附设一个头结点，头结点的数据域中可以不存放任何信心，或者存放单链表的长度等类的附加信息。【注】头结点并不是单链表的第一个结点【举例】带头结点的非空单链表head【举例】带头结点的空单链表head【单链表的插入】设有单链表HHAB【单链表结点类型定义】typedef struct Lnode ElemType data; /*数据域，保存结点的值 */struct Lnode *next; /*指针域*/LNode; 1、将数据D插入单链表，使
6、之成为单链表的第一个结点【操作】LNode *q=(LNode *)malloc(sizeof(LNode)*q - date = D*q - next = H - next;H - next = q步骤图示LNode *q=(LNode *)malloc(sizeof(LNode)HABq*q - date = DHABDq*q - next = H - next;HABDqH - next = qHABDq2、将数据D插入单链表A结点后面HABp【步骤】LNode *q=(LNode *)malloc(sizeof(LNode)*q - date = D*q - next = A - ne
7、xt;A- next = q【详解】步骤图示LNode *q=(LNode *)malloc(sizeof(LNode)HABpq*q - date = DHABpDq*q - next = A - next;HABpDqA- next = qHABpDq【单链表的删除】HABpCq1、 在单链表H中删除结点A【注】要删除单链表中的一个结点，必须知道该节点的前驱结点【步骤】q- next = p - nextfree( p )【详解】步骤图示q- next = p - nextHABpCqfree( p )HACq【练习】1、 如何找到单链表（整型）中最大关键字？时间复杂度是多少？【提示】先去
8、一个最小的整型数a，从链表头开始一个接一个的进行比较，若大于a，替换，小于a，转下一个结点，时间复杂度是O（n）2、 如何在单链表中第i个位置插入结点？时间复杂度是多少？【提示】首先判断i的有效性，然后遍历单链表，找到第i-1个位置，在第i-1个位置后插入新结点，时间复杂度是O(n)3、 如何删除单链表中关键字为key的第一个结点？ 时间复杂度是多少？循环链表【循环链表】表中最后一个结点的指针指向头结点，整个链表形成一个环，从循环链表中的任一个结点出发均可找到表中其他结点。【带尾结点的单链表】有时链表中不设头结点而设尾指针，可以使某些操作简化。【注】掌握循环链表的插入和删除操作ABC 双向链表【概念】双向链表中包含两个指针域，其一是指向直接后继，另一个是指向前趋。ABC【注】掌握双向链表的插入和删除操作
