第一章 数据结构概述基本概念与术语1数据 ：数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被 计算机程序所处理的符号的总称。2. 数据元素 ：数据元素是数据的基本单位， 是数据这个集合中的个体， 也称之为元素， 结点， 顶点记录。(补充：一个数据元素可由若干个 数据项 组成。数据项是数据的不可分割的最小单位。 )3数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。(有时候也叫做属性。)4 数据结构 ：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。(1) 数据的逻辑结构：数据的逻辑结构是指数据元素之间存在的固有逻辑关系，常称为数 据结构。数据的逻辑结构是从数据元素之间存在的逻辑关系上描述数据与数据的存储无关，是 独立于计算机的。依据数据元素之间的关系，可以把数据的逻辑结构分成以下几种：1. 集合 ：数据中的数据元素之间除了“同属于一个集合“的关系以外，没有其他关系。2. 线性结构 ：结构中的数据元素之间存在“一对一“的关系。若结构为非空集合，则除了第 一个元素之外，和最后一个元素之外，其他每个元素都只有一个直接前驱和一个直接后继。3. 树形结构 ：结构中的数据元素之间存在“一对多“的关系。若数据为非空集，则除了第一 个元素 (根)之外，其它 每个数据元素都只有一个直接前驱， 以及多个或零个 直 接后继。4. 图状结构 ：结构中的数据元素存在“多对多”的关系。若结构为非空集，折每个数据可有 多个(或零个)直接后继。(2) 数据的存储结构：数据元素及其关系在计算机内的表示称为数据的存储结构。 想要计算机处理数据， 就必须把数据的逻辑结构映射为数据的存储结构。 逻辑结构可以映射 为以下两种存储结构：1. 顺序存储结构 ：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中，借助元素 在存储器中的相对位置来表示数据之间的逻辑关系。2. 链式存储结构 ：借助指针表达数据元素之间的逻辑关系。 不要求逻辑上相邻的数据元素物 理位置上也相邻。5. 时间复杂度分析 ：1.常量阶：算法的时间复杂度与问题规模n 无关系 T(n)=O(1)2. 线性阶：算法的时间复杂度与问题规模n 成线性关系 T(n)=O(n)3. 平方阶和立方阶：一般为 循环的嵌套 ，循环体最后条件为 i+ 时间复杂度的大小比较：O(1) O(log 2 n) O(n ) O(n log 2 n) O(n2) O(n3) O(2 n )O(n!)next=head-next; head-next=p; 输出： printf( “%d ”,p-data);删除： q=p-next; p-next = q-next ; free(q); 结点遍历： for(p=head;p;p=p-next);补充内容：1、线性表中，第一个元素没有直接前驱，最后一个元素没有直接后驱。2、 在一个单链表中，若p所指结点是q所指结点的前驱结点，则删除结点q的操作语句为P-next = q-next ; free（q）;3、在长度为 N 的顺序表中，插入一个新元素平均需要移动表中 N/2 个元素，删除一个元素 平均需要移动（ N-1 ） /2 个元素。4、若线性表的主要操作是在最后一个元素之后插入一个元素或删除最后一个元素，则采用 顺序表 存储结构最节省运算时间。5、 已知顺序表中每个元素占用3个存储单元，第 13 个元素的存储地址为 336，则顺序表的 首地址为 300。（第 n 个元素的地址即首地址 +（n-1）* 每个元素的存储空间，如 a12 （第 13 个元素）的地址 =a0+12*3 ）6、 设有一带头结点单链表L,请编写该单链表的初始化，插入、输出和删除函数。（函数名自定义）结点定义：typedef int datatype; /结点数据类型，假设为 inttypedef struct node /结点结构datatype data;struct node *next;/ 双向链表还应加上 *previous Lnode, * pointer ; / 结点类型 ,结点指针类型 typedef pointer lklist; /单链表类型，即头指针类型1. 初始化：lklist initlist() pointer head;head=new node;/这是 C+ 做法/head=( pointer)malloc(sizeof(Lnode);这是 C 语言做法head-next=NULL;/循环链表则是 head-next=head;/双向链表应加上 head-previos=NULL;return head;2插入：(C语言中需要把head转化为全局变量才能实现此程序)int insert(lklist head,datatype x,int i)pointer q,s;q=get(head,i-1); /找第 i-1 个点if(q=NULL)/无第 i-1 点，即 in+1 时coutdata=x;s-next=q-next;/新点的后继是原第i 个点q-next=s;/原第 i-1 个点的后继是新点return 1;/插入成功3删除：(C语言中需要把head转化为全局变量才能实现此程序)int delete(lklist head,int i) pointer p,q;q=get(head,i-1);/找待删点的直接前趋if(q=NULL | q-next=NULL)/即 in 时coutnext;/保存待删点地址q-next=p-next;/ 修改前趋的后继指针delete p;/释放结点即 C 语言中的 free(p);return 1;/删除成1. 不带头结点的单链表 head 为空的判定条件是 (A )A. head=NULLB.head-next=NULLC.head-next=head D. head!=NULL2. 带头结点的单链表 head 为空的判定条件是 (B )A.head=NULLB.head-next=NULLC.head-next=headD. head!=NULL3. 在一个单链表中，若 p所指结点不是最后结点，在p之后插入s所指结点，则执行(B )A.s-next=p; p-next=s;B. s-next=p-next; p-next=s;C. s-next=p-next; p=s;D. p-next=s; s-next=p;4. 在一个单链表中，若删除p所指结点的后续结点，则执行(A )A. p-next=p-next-next;B. p=p-next; p-next=p-next-next;C. p-next=p-nextD. p=p-next-next5. 从一个具有 n 个结点的有序单链表中查找其值等于 x 结点时， 在查找成功的情况下， 需 平均比较( B )个结点。A. n B. n/2 C. (n-1)/2D. O(n log 2n)6. 给定有 n 个元素的向量，建立一个有序单链表的时间复杂度(B)A.O(1)B.O(n)C.O(n2)D.O(n g 2n)7. 在一个具有 n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是(B)A.O(1)B.O(n)C.O(n2)D.O(n g 2n)8. 在一个单链表中删除 q 所指结点时，应执行如下操作： q=p-next;p-next=( p-next-next );free(q);/这种题目靠一根指针是没有办法完成的，必须要借助第二根指针。9. 在一个单链表中p所指结点之后插入一个s所指结点时，应执行：s-next=( p-next )p-next=(s) 操作。10. 对于一个具有 n 个节点的单链表 ,在已知所指结点后插入一个新结点的时间复杂度是（O（1）；在给定值为 x 的结点后插入一个新结点的时间复杂度是（O（n） ）。11. 问答题 线性表可用顺序表或链表存储。试问：（1） 两种存储表示各有哪些主要优缺点 ?顺序表的存储效率高， 存取速度快。 但它的空间大小一经定义， 在程序整个运行期间不会发 生改变，因此，不易扩充。同时，由于在插入或删除时，为保持原有次序，平均需要移动一 半（ 或近一半 ）元素，修改效率不高。链接存储表示的存储空间一般在程序的运行过程中动态分配和释放， 且只要存储器中还有空 间，就不会产生存储溢出的问题。 同时在插入和删除时不需要保持数据