第一章 数据结构概述
基本概念与术语
1 ．数据：数据是用来描述现实世界的文字，字符，图像，声音，以及能够输入到计算机中 并能被计算机处理的符号。
2. 数据元素 ：数据元素是数据的基本单位，是数据这个集合中的个体，也称之为元素，结点，顶点记录。
（补充：一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。） 3 ．数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。（有时候也叫做属性。）
4 ．数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 （ 1 ）数据的逻辑结构：数据的逻辑结构是指数据元素之间存在的固有逻辑关系，常称为数据结构。
数据的逻辑结构是从数据元素之间存在的逻辑关系上描述数据与数据的存储无关，是独立于计算机的。
依据数据元素之间的关系，可以把数据的逻辑结构分成以下几种：
a. 集合 ：数据中的数据元素之间除了“同属于一个集合“的关系以外，没有其他关系。 b. 线性结构 ：结构中的数据元素之间存在“一对一“的关系。若结构为非空集合，则除了第一个元素之外，和最后一个元素之外，其他每个元素都只有一个直接前驱和一个直接后继。 c. 树形结构 ：结构中的数据元素之间存在“一对多“的关系。若数据为非空集，则除了第一个元素（根）之外，其它 每个数据元素都只有一个直接前驱，以及多个或零个 直接后继。
d. 图状结构 ：结构中的数据元素存在“多对多”的关系。若结构为非空集，折每个数据可有多个（或零个）直接后继。
（ 2 ）数据的存储结构：数据元素及其关系在计算机内的表示称为数据的存储结构。 想要计算机处理数据，就必须把数据的逻辑结构映射为数据的存储结构。逻辑结构可以映射为以下两种存储结构：
a. 顺序存储结构 ：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中，借助元素在存储器中的相对位置来表示数据之间的逻辑关系。
b. 链式存储结构 ：借助指针表达数据元素之间的逻辑关系。不要求逻辑上相邻的数据元素物理位置上也相邻。
5. 时间复杂度分析 ： a. 常量阶：算法的时间复杂度与问题规模 n 无关系 T(n)=O(1) b. 线性阶：算法的时间复杂度与问题规模 n 成线性关系 T(n)=O(n) c. 平方阶和立方阶：一般为循环的嵌套，循环体最后条件为 i++ 时间复杂度的大小比较：
O(1)< O(log 2 n)< O(n )< O(n log 2 n)< O(n2)< O(n3)< O(2 n ) c 、有穷性：要求序列中的指令是有限的；每条指令的执行包含有限的工作量；整个指令序列的执行在有限的时间内结束。（程序与算法的区别在于，程序不需要有有穷性） d 、确定性：算法中的每一个步骤都必须是确定的，而不应当含糊、模棱两可。没有歧义。 1 e、可行性：算法中的每一个步骤都应当能被有效的执行，并得到确定的结果。 （ 2 ） . 算法设计的要求： 1 、正确性（达到预期效果，满足问题需求） 2 、健壮性（能处理合法数据，也能对不合法的数据作出反应，不会产生不可预期的后果） 3 、可读性（要求算法易于理解，便于分析） 4 、可修改可扩展性 5 、高效率（较好的时空性能 ） ? 补充内容： 1 、名词解释：数据结构、二元组 数据结构就是相互之间存在一种或多种特定关系的数据元素的集合。 二元组就是一种用来表示某个数据对象以及各个元素之间关系的有限集合。 2 、根据数据元素之间关系的不同，数据的逻辑结构可以分为集合、线性结构、树形结构和图状结构四种类型。 3 、常见的数据存储结构一般有两种类型，它们分别是顺序存储结构、链式存储结构 4. 以下说法中，正确的是（ D ） A. 数据元素是数据这个集合中的个体 B. 数据元素均由数据项组成 C ．数据项是数据的基本单位 D. 数据元素是数据的最小单位 5. 以下有关抽象数据类型的描述中，正确的是（ B ） A. 抽象数据类型是一个值的集合 B. 抽象数据类型是数据的逻辑结构及操作的组合 C. 抽象数据类型的操作可以没有操作结果 D. 抽象数据类型只能够用 C 语言来描述 6. 在一般情况下，一个算法的时间复杂度是问题规模的函数 7. 常见时间复杂度有：常数阶 O （ 1 ）、线性阶 O （ n ）、对数阶 O （ log 2 n ）、平方阶 O(n^2) 、指数阶 O(2^n) 。通常认为，具有常数阶量级的算法是好算法，而具有指数阶量级的算法是差算法。 第二章 线性表 定义：线性表是 n 个数据元素的有限序列。 一个数据元素可由若干个数据项组成。 1. 顺序表结构 线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称为顺序表。 2. 单链表 （ 1 ） 链表结点结构 线性表中的数据元素可以用任意的一组存储单元来存储，用指针表示逻辑关系逻辑相邻的两元素的存储空间可以是不连续的。 （ 2 ） 链表操作算法：初始化、插入、输出、删除、遍历 初始化： p=(struct student *)malloc(sizeof(struct student)); 插入： p->next=head->next; head->next=p; 输出： printf(“%d”,p->data); 2 删除： 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)* 每个元素的存储空间，如 a[12] （第 13 个元素）的地址 =a[0]+12*3 ） 6 、设有一带头结点单链表 L ，请编写该单链表的初始化，插入、输出和删除函数。（函数名自定义） ? 结点定义： typedef int datatype; // 结点数据类型，假设为 int typedef struct node { // 结点结构 datatype data; struct node *next; // 双向链表还应加上 *previous } Lnode, * pointer ; // 结点类型 , 结点指针类型 typedef pointer lklist; // 单链表类型，即头指针类型 ? 初始化： 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; } ? 插入：（ 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 点，即 i<1 或 i>n+1 时 { cout<<” 非法插入位置 !\\n”; // 这是 C++ 做法，即 C 语言中的 printf(“ 非法插入位置 !\\n”); return 0; } 3 s=new node;// 生成新结点 即 C 语言中的 s=( pointer)malloc(sizeof(Lnode)); s->data=x; s->next=q->next; // 新点的后继是原第 i 个点 q->next=s; // 原第 i-1 个点的后继是新点 return 1; // 插入成功 } ? 删除：（ C 语言中需要把 head 转化为全局变量才能实现此程序） int delete(lklist head,int i) { pointer p,q; q=get(head,i-1); // 找待删点的直接前趋 if(q==NULL || q->next==NULL) // 即 i<1 或 i>n 时 {cout<< ”非法删除位置 !\\n ” ;return 0;} p=q->next; // 保存待删点地址 q->next=p->next; // 修改前趋的后继指针 delete p; // 释放结点 即 C 语言中的 free(p); return 1; // 删除成 1. 不带头结点的单链表 head 为空的判定条件是 (A ) A. head=NULL B. head->next=NULL C. head->next=head D. head!=NULL 2. 带头结点的单链表 head 为空的判定条件是 (B ) A. head=NULL B. head->next=NULL C. head->next=head D. head!=NULL 3. 在一个单链表中，若 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->next D. p=p->next->next 5. 从一个具有 n 个结点的有序单链表中查找其值等于 x 结点时，在查找成功的情况下，需平均比较（ B ）个结点。 A. n B. n/2 C. (n-1)/2 D. O(n ㏒ 2n) 6. 给定有 n 个元素的向量，建立一个有序单链表的时间复杂度（ B ） A.O(1) B.O(n) C.O(n2) D.O(n ㏒ 2n) 7. 在一个具有 n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是 (B) A.O(1) B.O(n) C.O(n2) D.O(n ㏒ 2n) 8. 在一个单链表中删除 q 所指结点时，应执行如下操作： q=p->next; p->next=( p->next->next ); free(q);// 这种题目靠一根指针是没有办法完成的，必须要借助第二根指针。 9. 在一个单链表中 p 所指结点之后插入一个 s 所指结点时，应执行： s->next=( p->next ) 4
