数据结构(c语言版)第二单元复习纲要

《数据结构(c语言版)第二单元复习纲要》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构(c语言版)第二单元复习纲要第二章线性表2.1线性表的类型定义【线性表】是一个n个数据元素的有限序列线性表中的数据元素既可以是一个数字或者字符，如：（A,B,C,D,E,）或者（6,17,23,14,56,11）数据元素也可能是由由多个数据项构成的记录，如：姓名学号性别年龄班级健康状况张三209871男231良好李四3213857男212良好王五23413241男241良好【线性表的特点】：*存在唯一的一个称作"第一个"的数据元素*存在唯一的一个被称作"最后一个"的数据元素*除第一个之外，

2、集合中每一个元素均只有一个前驱*除最后一个外，集合中每一个元素均只有一个后继【线性表的长度】：线性表中元素的个数【空表】：元素个数n=0时，称为空表【注】线性表是指一种逻辑结构2.2线性表的顺序表示和实现【线性表的顺序存储表示】指的是用一组地址连续的存储单元依次存储线性表的数据元素假设线性表的每个元素需占用l个存储单元，设线性表第i个数据元素的存储位置为LOC(ai)，第i+1个数据元素的存储位置LOC(ai+1)则满足下列关系：LOC(ai+1)=LOC(ai)+l【顺序表】：通常称顺序结构的线

3、性表为顺序表【特点】：逻辑上相邻的元素的存储位置也相邻，可以随机存取，因此，线性表是一种可以随机存取的数据结构。序号数据元素112213321424528630742777由于顺序表中，逻辑上相邻的元素在物理位置上也相邻，因此在数据的插入和删除时需要移动元素。序号数据元素11221332142452562873074277由于原来逻辑上24和28相邻，因此在物理位置上24和28相邻，在24后插入元素25，24同元素25相邻，25和24、28相邻，因此需要移动数据元素序号数据元素1122133214

4、24528630742777序号数据元素1122133214285306427777原来数据24和21、28相邻，删除24后，21和28相邻，因此需要移动数据。【一般情况下】：*假设顺序表有n个元素，在第i个位置之前插入一个元素时，需要将第n至第i个元素向后移动一个位置，将第i个位置空出来，插入新元素。*假设顺序表有n个元素，将第i个位置的元素删除，需要将从第i+1至第n（共n-i）个元素依稀向前移动一个位置。*当在顺序表中插入和删除数据元素时，其时间主要耗费在移动元素上，而移动元素的个数取决于插

5、入或删除元素的位置*在等概率情况下，顺序表中删除或插入一个数据元素，平均约移动表中一半元素2.3线性表的链式表示和实现2.3.1线性链表【特点】用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）【举例】【结点结构】单链表的结点有两个域：数据域和指针域数据域用来存放单链表的数据信息指针域存放下指向下一个结点的指针，即下一个结点的存储位置【线性链表&单链表】由于链表中每一个结点只包含一个指针域，因此又称单链表或线性链表。【头结点】为了操作方便有时在单链表的第一个结点

6、之前附设一个头结点，头结点的数据域中可以不存放任何信心，或者存放单链表的长度等类的附加信息。【注】头结点并不是单链表的第一个结点【举例】带头结点的非空单链表【举例】带头结点的空单链表【单链表的插入】设有单链表H【单链表结点类型定义】typedefstructLnode{ElemTypedata;/*数据域，保存结点的值*/structLnode*next;/*指针域*/}LNode;1、将数据D插入单链表，使之成为单链表的第一个结点【操作】LNode*q=(LNode*)malloc(sizeof

7、(LNode)*q->date=D*q->next=H->next;H->next=q步骤图示LNode*q=(LNode*)malloc(sizeof(LNode)*q->date=D*q->next=H->next;H->next=q2、将数据D插入单链表A结点后面【步骤】LNode*q=(LNode*)malloc(sizeof(LNode)*q->date=D*q->next=A->next;A->next=q【详解】步骤图示LNode*q=(LNode*)malloc(sizeof(LN

8、ode)*q->date=D*q->next=A->next;A->next=q【单链表的删除】1、在单链表H中删除结点A【注】要删除单链表中的一个结点，必须知道该节点的前驱结点【步骤】q->next=p->nextfree(p)【详解】步骤图示q->next=p->nextfree(p)【练习】1、如何找到单链表（整型）中最大关键字？时间复杂度是多少？【提示】先去一个最小的整型数a，从链表头开始一个接一个的进行比较，若大于a，替换，小于a，转下一个结点，时间复杂度是O（n）2、如