数据结构_线性表及其基本算法

数据结构(一)目录第1章序论 (1)1.1 什么是数据? (1)1.2 什么是数据元素? (1)1.3 什么是数据结构及种类? (1)1.4 数据的逻辑结构 (1)1.5 数据的物理结构 (1)1.6 算法和算法分析 (1)1.7 算法的五个特性 (1)1.8 算法设计的要求 (2)1.9 算法效率的度量 (2)第2章线性表 (3)2.1 线性表举例 (3)2.2 线性表的存储 (4)2.3 线性表-栈 (4)2.4 队列 (4)2.5 双端队列 (6)第3章树和二叉树 (6)3.1 树 (6)3.1.1 树的基本概念 (6)3.1.2 树的常用存储结构 (6)3.1.3 树的遍历 (7)3.2 二叉树 (7)3.2.1 二叉树的基本概念 (7)3.2.2 二叉树与树的区别 (7)3.2.3 树及森林转到二叉树 (7)3.2.4 二叉树的性质 (8)3.2.5 满二叉树 (8)3.2.6 完全二叉树 (8)3.2.7 完全二叉树的性质 (9)3.2.8 二叉树的四种遍历 (9)3.2.9 二叉排序树 (10)3.2.10 平衡二叉树 (11)3.2.11 m阶B-树 (11)3.2.12 最优二叉树 (11)3.2.13 二叉树的存储结构 (12)3.3 广义表 (13)3.4 矩阵的压缩存储 (14)3.4.1 特殊矩阵 (14)3.4.2 压缩存储 (14)第4章历年真题讲解 (15)4.1 2009年上半年 (15)4.2 2009年下半年 (15)4.3 2010年上半年 (15)4.4 2011年上半年 (16)4.5 2011年下半年 (16)4.6 2012年上半年 (17)4.7 2012年下半年 (17)4.8 2013年上半年 (18)4.9 2013年下半年 (18)4.10 2014年上半年 (18)4.11 2014年下半年 (19)4.12 2015年上半年 (19)4.13 2015年下半年 (19)4.14 2016年上半年 (20)第1章序论什么是数据?所有能输入到计算机中并能够被计算机程序处理的符号的总称,它是计算机程序加工的原料。

数据结构的定义数据结构是计算机中存储、组织数据的方式，它定义了数据元素之间的逻辑关系以及如何在计算机中表示这些关系。

提高算法效率合适的数据结构可以显著提高算法的执行效率，降低时间复杂度和空间复杂度。

简化程序设计数据结构为程序设计提供了统一的抽象层，使得程序员可以更加专注于问题本身，而不是底层的数据表示和访问细节。

便于数据管理和维护良好的数据结构设计可以使得数据的管理和维护变得更加方便和高效。

数据结构的定义与重要性线性数据结构中的元素之间存在一对一的关系，如数组、链表、栈和队列等。

线性数据结构非线性数据结构中的元素之间存在一对多或多对多的关系，如树、图等。

非线性数据结构静态数据结构在程序运行期间不会发生改变，如数组、静态链表等。

静态数据结构动态数据结构在程序运行期间可以动态地添加或删除元素，如链表、动态数组等。

动态数据结构数据结构的分类01020304在计算机科学中，数据结构是算法设计和分析的基础，广泛应用于操作系统、编译原理、数据库等领域。

计算机科学在软件工程中，数据结构是软件设计和开发的重要组成部分，用于实现各种软件功能和性能优化。

软件工程在人工智能中，数据结构用于表示和处理各种复杂的数据和知识，如神经网络、决策树等。

人工智能在大数据处理中，数据结构用于高效地存储、管理和分析海量数据，如分布式文件系统、NoSQL 数据库等。

大数据处理数据结构的应用领域0102线性表是具有n个数据元素的有限序列创建、销毁、清空、判空、求长度、获取元素、修改元素、插入元素、删除元素等线性表的定义线性表的基本操作线性表的定义与基本操作03用一段地址连续的存储单元依次存储线性表的数据元素顺序存储结构的定义可以随机存取，即可以直接通过下标访问任意元素；存储密度高，每个节点只存储数据元素顺序存储结构的优点插入和删除操作需要移动大量元素；空间利用率不高，需要提前分配存储空间顺序存储结构的缺点链式存储结构的定义01用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的链式存储结构的优点02插入和删除操作不需要移动大量元素，只需要修改指针；空间利用率高，不需要提前分配存储空间链式存储结构的缺点03不能随机存取，只能通过从头节点开始遍历的方式访问元素；存储密度低，每个节点除了存储数据元素外，还需要存储指向下一个节点的指针0102定义栈（Stack）是一种特殊的线性数据结构，其操作只能在一端（称为栈顶）进行，遵循后进先出（LIFO）的原则。

数据结构--线性表实验报告+二叉树实验报告班级：学号：姓名：日期：1. 实验题目编辑一个程序，用来演示线性表的建立、插入、删除等操作。

2. 需求分析本演示程序在Microsoft Visual C++ 6.0环境下编写调试，完成线性表的生成、任意位置的插入、删除等。

（1）输入的形式和输入的范围：执行插入操作时，需要输入插入位置和元素的值；执行删除操作时，需要输入待删除元素的位置。

在所有输入中，元素的值都是由整数、字符数组和字符数组组成的。

（2）输出的形式：在所有操作中都要求显示相关操作是否正确以及操作后线性表的内容。

其中删除操作完成后，要显示删除后所剩的元素的值。

（3）程序所能达到的功能：完成线性表的生成、插入、删除操作。

3. 概要设计（1）为了实现上述程序功能，需要定义线性表的数据结构。

线性表单个元素的结构如图1.1所示。

图1.1 线性表元素的数据结构（2）本程序包含6个函数：①主函数main()。

②初始化线性表函数creat()。

③插入元素函数insert()。

④删除元素函数del()。

线性表实验报告+二叉树实验报告各函数间的关系如图1.2所示。

图1.2 程序所包含各函数之间的关系4. 详细设计实现概要设计中定义的所有的数据类型，对每个操作给出具体的算法；对主程序和其他模块也都需要写出具体算法。

（一）数据类型。

用C语言描述如下：typedef struct {int num; float score; }student;（二）线性表的基本操作函数的具体算法：1. 主函数main()的具体算法：void main() {student L; creat(L); insert(L); del(L); }2. 初始化线性表函数creat()的具体算法：void creat(student s) {printf(“输入学生数据：\n"); for(i=0;ii++)scanf("%d%f",s[i].num,s[i].score);线性表实验报告+二叉树实验报告printf("目前数据数：%d组\n",i); for(i=0;ii++)printf("%d\t%5.1f\t\n",s[i].num,s[i].score); }3. 插入元素函数insert()的具体算法：void insert(student s) {printf("输入插入数据位置：\n"); scanf("%d", if(j4)printf("输入有误，请输入在0~4之间\n"); scanf("%d", // if(j=4)// printf("输入插入数据：\n");// scanf("%d%f",s[j-1].num,s[j-1].score); if(j=4)for(i=3;i=j-1;i--) s[i]=s[i-1];printf("输入插入数据：\n");scanf("%d%f",s[j-1].num,s[j-1].score); n=n+1;printf("目前数据数：%d组\n",n); for(i=0;ii++)printf("%d\t%5.1f\t\n",s[i].num,s[i].score); }4. 删除元素函数del()的具体算法：void del(student s) {printf("输入删除数据位置：\n"); scanf("%d", if(j4)printf("输入有误，请输入在0~4之间\n"); scanf("%d", for(i=j-1;ii++) s[i]=s[i+1]; n=n-1;printf("目前数据数：%d组\n",n); for(i=0;ii++)。

数据结构考研笔记整理（全）一、第二章线性表●考纲内容●一、线性表的基本概念●线性表是具有相同数据结构类型的n个数据元素的有限序列；线性表为逻辑结构，实现线性表的存储结构为顺序表或者链表●二、线性表的实现●1、顺序表●定义(静态分配)●#define MaxSize 50 \\ typedef struct{ \\ ElemType data[MaxSize];\\ intlength;\\ }SqList;●定义(动态分配)●#define MaxSize 50\\ typedef strcut{\\ EleType *data; //指示动态非配数组的指针\\ int MaxSize,length;\\ }SqList;●c的动态分配语句为L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);●c++动态分配语句为L.data=new ElemType[InitSize];●插入操作●删除操作●按值寻找●2、链表●单链表●单链表的定义●●头插法建立单链表●●尾插法建立单链表●●按序号查找getElem(LinkList L,int i)和按值查找locateElem(LinkListL,ElemType e)●插入结点（后插）●p=getElem(L,i-1); //查找插入位置的前驱结点\\ s.next=p.next;\\p.next=s;●将前插操作转化为后插操作,即先将s插入的p的后面然后调换s和p的数据域●s.next=p.next;\\ p.next=s.next;\\ temp=p.data;\\ p.data=s.data;\\s.data=temp;●删除结点●p.getElem(L,i-1);\\ q=p.next;\\ p.next=q.next;\\ free(q);●双链表（结点中有prior指针和next指针）●循环链表●静态链表●借助数组来描述线性表的链式存储结构，结点中的指针域next为下一个元素的数组下标●三、线性表的应用●使用的时候如何选择链表还是顺序表？●表长难以估计，经常需要增加、删除操作——链表;表长可以估计，查询比较多——顺序表●链表的头插法，尾插法，逆置法，归并法，双指针法；顺序表结合排序算法和查找算法的应用●小知识点（选择题）二、第三章栈，队列和数组●考纲内容●一、栈和队列的基本概念●栈：后进先出，LIFO，逻辑结构上是一种操作受限的线性表●队列：先进先出，FIFO，逻辑结构上也是一种操作受限的线性表●二、栈和队列的顺序存储结构●栈的顺序存储●●队列的顺序存储●进队：队不满时，送值到队尾元素，再将队尾指针加一●出队：队不空时，取队头元素值，再将队头指针加一●判断队空：Q.front==Q.rear==0;●循环队列（牺牲一个单元来区分队空和队满，尾指针指向队尾元素的后一个位置，也就是即将要插入的位置）●初始：Q.front==Q.rear●队满：(Q.rear+1)%MaxSize=Q.front●出队，队首指针进1:Q.front=(Q.front+1)%MaxSize●入队，队尾指针进1:Q.rear=(Q.rear+1)%MaxSize●队列长度：(Q.rear+MaxSize-Q.front)%MaxSize●三、栈和队列的链式存储结构●栈的链式存储●●队列的链式存储●实际是上一个同时带有头指针和尾指针的单链表，尾指针指向单链表的最后一个结点，与顺序存储不同,通常带有头结点●四、多维数组的存储●行优先：00，01，02，10，11，12●列优先：00，10，01，11，02，12●五、特殊矩阵的压缩存储●对称矩阵●三角矩阵●三对角矩阵（带状矩阵）●稀疏矩阵●将非零元素及其相应的行和列构成一个三元组存储●十字链表法●六、栈、队列、数组的应用●栈在括号匹配中的应用●栈在递归中的应用●函数在递归调用过程中的特点：最后被调用的函数最先执行结束●队列在层次遍历中的应用●二叉树的层次遍历●1跟结点入队●2若队空，则结束遍历，否则重复3操作●3队列中的第一个结点出队并访问，若有左孩子，则左孩子入队；若有右孩子，则右孩子入队●重点为栈的(出入栈过程、出栈序列的合法性)和队列的操作及其特征●小知识点(选择题)●n个不同元素进栈，出栈元素不同排列的个数为{2n\choose n }/(n+1)●共享栈是指让两个顺序栈共享一个存储空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸，可以更有效的利用存储空间，同时对存储效率没有什么影响●双端队列是指允许两端都可以进行入队和出队操作的队列●输出受限的双端队列：允许两端插入，只允许一端删除●输入受限的双端队列：允许两端删除，只允许一端插入三、第四章串●考纲内容●字符串模式匹配●暴力算法●注意指针回退时的操作是i=i-j+2;j=j+1;●kmp算法●手工求next数组时，next[j]=s的最长相等前后缀长度+1，其中s为1到j-1个字符组成的串●在实际kmp算法中，为了使公式更简洁、计算简单，如果串的位序是从1开始的，则next数组需要整体加一；如果串的位序是从0开始的，则next数组不需要加一●根据next数组求解nextval数组：如果p[j]==p[next[j]]，则nextval[j]=nextval[next[j]]，否则nextval[j]=next[j];●小知识点●串和线性表的区别：1线性表的数据元素可以不同，但串的数据元素一般是字符；2串的操作对象通常是子串而不是某一个字符四、第五章树与二叉树●考纲内容●一、树的基本概念●定义●树是一种递归的数据结构，是一种逻辑结构●树的性质●结点数为n，则边的数量为n-1●树中的结点数等于所有结点的度数之和加1（一个结点的孩子个数称为该结点的度，树中结点的最大度数称为树的度，每一条边表示一个结点，对应一个度，只有根结点上面无边，故结点树=度数之和+1）●度为m的树中第i层至多有m^{i-1}个结点（i\geq1）（m叉树的第i层最多有m^{i-1}个结点）●高度为h的m叉树至多有(m^h-1)/(m-1)个结点（假设每一个结点都有m个孩子，则由等比数列的求和公式可以推导出该式子）●具有n个结点的m叉树的最小高度是\lceil log_m(n(m-1)+1)\rceil（由高度为h的m叉树的最大结点树公式有，n满足式子(m^{h-1}-1)/(m-1) \leq n\leq (m^h-1)/(m-1)）●高度为h的m叉树至少有h个结点；高为h，度为m的树至少有h+m-1个结点（m叉树并不等于度为m的树，m叉树可以为空树，要求所有结点的度小于等于m，而度为m的树一定有一个结点的度数为m）●二、二叉树●二叉树的定义及其主要特征●定义●特点●每个结点至多只有两颗子树●二叉树是有序树，其子树有左右之分，次序不能颠倒，否则将成为另一颗二叉树，即使树中结点只有一颗子树，也要区分他是左子树还是右子树●特殊的二叉树●满二叉树：高度为h，结点数为2^h-1，所有叶子结点都集中在二叉树的最下面一层，除叶子结点外的所有结点度数都为2，从根结点为1开始编号，对于编号为i的结点，其父结点为\lfloor i/2 \rfloor，左孩子(若有)编号为2i，右孩子(若有)编号为2i+1，所以编号为偶数的结点只可能是左孩子，编号为奇数的结点只可能是右孩子●完全二叉树：删除了满二叉树中编号更大的结点，高为h，结点数为n的完全二叉树的每个结点的编号都与高度为h的满二叉树中编号为1到n的结点相同。

第一章数据结构概念——数据结构，数据元素，数据项，数据类型，抽象数据类型，算法，等。

数据结构定义——指互相有关联的数据元素的集合，用D_S=( D, S ) 或S=( D, R) 表示。

数据结构内容——数据的逻辑结构、存储结构和运算算法效率指标——时间效率（时间复杂度）和空间效率（空间复杂度）总结：数据的逻辑结构和存储结构数据的逻辑结构是数据的机外表示，数据的存储结构是数据的机内表示。

(2) 一种数据的逻辑结构可以用多种存储结构来存储。

(3) 数据结构的基本操作是定义（存在）于逻辑结构，计算机程序设计过程中实现于存储结构。

(4) 采用不同的存储结构，其数据处理的效率往往是不同的。

数据结构？有限个同构数据元素的集合，存在着一定的结构关系，可进行一定的运算。

算法--是对特定问题求解步骤的一种描述，是指令的有限序列。

算法有5个基本特性：有穷性、确定性、可行性、输入和输出第二章1. 数据的逻辑结构是指数据元素之间的逻辑关系，是用户按使用需要建立的。

对2. 线性表的逻辑结构定义是唯一的，不依赖于计算机。

对3. 线性结构反映结点间的逻辑关系是一对一的。

对4. 一维向量是线性表，但二维或N维数组不是。

错5. “同一数据逻辑结构中的所有数据元素都具有相同的 特性”是指数据元素所包含的数据项的个数都相等。

错 插入概率p(i)=1/(n+1) ，删除概率q(i)=1/n插入操作时间效率（平均移动次数）2)1(11)1(1111ni n n i n p E n i n i i is =+-+=+-=∑∑+=+=删除操作时间效率（平均移动次数）21)(1)(11-=-=-=∑∑==n i n n i n q E ni n i i dl 线性表顺序存储结构特点：逻辑关系上相邻的两个元素在物理存储位置上也相邻； 优点：可以随机存取表中任一元素;无需为表示表中元素 之间的逻辑关系而增加额外的存储空间；缺点：在插入、删除某一元素时，需要移动大量元素；表的容量难以确定，表的容量难以扩充。

数据结构与算法第一节数据结构及算法概述一、数据结构图、四类基本结构的示意图【要点】 1 .数据元素是数据的基本单位。

2 .数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

3 .4类基本的规律结构:集合、线性结构、树形结构和网状结构。

4 .4种数据存储方式：挨次、链式、索引和散列。

【例题•单选题】(2022年义省信用社聘请考试真题)下列说法不正确的是()OA.数据元素是数据的基本单位B.数据项是数据中不行分割的最小标志单位 C.数据可由若干个数据元素构成D.数据项可由若干个数据元素构成『正确答案』D『答案解析』数据元素是数据的基本单位，在计算机程序中通常被作为一个整体进 行考虑和处理。

一个数据元素可由若干个数据项组成。

数据项是不行分割的、含有独立 意义的最小数据单位。

因此D 选项不正确。

二、算法O ——O ——O ——O ——O ⑹树型结构⑹线性结构 (d)图形结构算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作。

算法的特性：有穷性、确定性、可行性、输入和输出。

【要点】评价算法优劣标准：正确性、可读性、健壮性、高效率与低存储量需求。

其次节线性表线性表是n (n≥0)个数据元素al, a2,…，an组成的有限序列,n=0时称为空表。

非空的线性表，有以下特征：L有且仅有一个开头结点al,没有直接前趋，有且仅有一个直接后继a2。

2.有且仅有一个终结结点an,没有直接后继，有且仅有一个直接前趋a-。

3.其余的内部结点ai (2WiWnT)都有且仅有一个直接前趋a-和一个直接后继3i+ι o线性表的链式存储包括单链表、循环链表和双链表。

head 头结点百结点尾结点【留意】与单链表的插入和删除操作不同的是，在双链表中插入和删除须同时修改两个方向上的指针。

第三节栈和队列一、栈栈是一种“特别的”线性表，这种线性表中的插入和删除运算限定在表的某一端进行。

不含任何数据元素的栈称为空栈。

一、实验目的二、实验内容和要求三、源代码1)顺序表的代码2)单链表的代码四、测试结果1)顺序表的测试结果2)单链表的测试结果五、心得体会实验一线性表的基本操作及其应用一、实验目的1、帮助读者复习C++语言程序设计中的知识。

2、熟悉线性表的逻辑结构。

3、熟悉线性表的基本运算在两种存储结构上的实现。

4、掌握顺序表的存储结构形式及其描述和基本运算的实现。

5、熟练掌握动态链表结构及有关算法的设计二、实验内容题目一：顺序表的基本操作[问题描述]实现顺序表的建立、求长度，取元素、修改元素、插入、删除等顺序表的基本操作。

[基本要求]（1）依次从键盘读入数据，建立带头结点的顺序表；（2）输出顺序表中的数据元素（3）求顺序表的长度；（4）根据指定条件能够取元素和修改元素；（5）实现在指定位置插入和删除元素的功能。

（6）根据算法，将两个有序的顺序表合并成一个有序顺序表。

[测试数据] 由学生任意指定。

题目二：单链表的基本操作[问题描述]实现带头结点的单链表的建立、求长度，取元素、修改元素、插入、删除等单链表的基本操作。

[基本要求]（1）依次从键盘读入数据，建立带头结点的单链表；（2）输出单链表中的数据元素（3）求单链表的长度；（4）根据指定条件能够取元素和修改元素；（5）实现在指定位置插入和删除元素的功能。

（6）根据算法，将两个有序的单链表合并成一个有序单链表。

[测试数据]由学生任意指定。

三、源代码(一)顺序表的基本操作#include<iostream>using namespace std;#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;typedef int ElemType;#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef struct { //结构体ElemType *elem;int length;int listsize;}SqList;SqList Lx;Status InitList_Sq(SqList &L) //分配空间{ L.elem=new ElemType[LIST_INIT_SIZE];if(!L.elem)exit(OVERFLOW);L.length =0;L.listsize=LIST_INIT_SIZE;return OK;}Status ListInsert(SqList &L,int i,ElemType e) //插入新元素{ int *q,*p;ElemType *newbase;if(i<1 || i>L.length+1) return ERROR;if(L.length>=L.listsize){ newbase=new ElemType[L.listsize+LISTINCREMENT];if(!newbase) exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;}q=&(L.elem[i-1]);for (p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;*q=e;++L.length;return OK;}Status Listlength(SqList L) //长度{ int *p=L.elem; //判断线形表是否存在while(p){ return (L.length); }}Status GetElem(SqList L, int i,ElemType &e) //取元素{ if(i<1 || i>L.length)return ERROR;else{ e=L.elem[i-1];return e;}}void MergeList(SqList La,SqList Lb,SqList &Lc) //合并{ ElemType ai,bj;InitList_Sq(Lc);int i=1,j=1,k=0;int La_len,Lb_len;La_len=Listlength(La);Lb_len=Listlength(Lb);while((i<=La_len)&&(j<=Lb_len)){ GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai<=bj){ ListInsert(Lc,++k,ai);++i; }else{ ListInsert(Lc,++k,bj);++j; }}while(i<=La_len){ GetElem(La,i++,ai);ListInsert(Lc,++k,ai);}while(j<=Lb_len){ GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);}}void show(SqList L,int i) //显示{ int j;ElemType k;cout<<"顺序表显示如下:"<<endl;for(j=0;j<i-1;j++){ k=L.elem[j];cout<<k<<"->"; }if(j==i-1 && i>0){ k=L.elem[j]; cout<<k; }cout<<endl;}void create(SqList &L,int n) //输入元素{ int e;for(int i=0;i<n;i++)L.elem[i]=e;L.length=i+1; }}Status ListDelete_Sq(SqList &L,int i,ElemType &e) //删除{ ElemType *p, *q;if(i<1 || i>L.length) return ERROR;p=&(L.elem[i-1]);e=*p;q=L.elem+L.length-1;for(++p;p<=q;++p) *(p-1)=*p;--L.length;return OK;}Status Listxiugei(SqList &L,int i,ElemType &e) //修改{ if(i<1 || i>L.length)return ERROR;else{ L.elem[i-1]=e;return OK; }}void shuru(SqList &L1) //顺序表的创建{ int a;InitList_Sq(L1);cout<<"请输入顺序表的长度：";cin>>a;cout<<"请输入顺序表的元素(共"<<a<<"个)"<<endl;create(L1,a);show(L1,a);}void chaxun(SqList &L1) //取第i个位置的元素{ int j;ElemType e1;cout<<"请选择所要取出元素的位置:";while(j<0||j>Listlength(L1)){ cout<<"输入有误，请重新输入"<<endl;cout<<"请选择所要取出元素的位置:";cin>>j; }GetElem(L1,j,e1);cout<<"取出的元素为:"<<e1<<endl; }void xiugai(SqList &L1) //修改第i个位置的元素{ int a;int j; ElemType e1;a=L1.length;cout<<"请选择所要修改元素的位置:";cin>>j;while(j<0||j>Listlength(L1)){ cout<<"输入有误，请重新输入"<<endl;cout<<"请选择所要修改元素的位置:";cin>>j; }cout<<"要修改成的元素:";cin>>e1;Listxiugei(L1,j,e1);cout<<"修改后的顺序表数据:"<<endl;show(L1,a);}void shanchu(SqList &L1) //删除顺序表里的元素{ int a;int j; ElemType e1;a=L1.length;cout<<"请选择所要删除元素的位置:";cin>>j;while(j<0||j>Listlength(L1)){ cout<<"输入有误，请重新输入"<<endl;cout<<"请选择所要删除元素的位置:";cin>>j; }ListDelete_Sq(L1,j,e1);cout<<"修改后的顺序表数据:"<<endl;show(L1,a-1);}void charu(SqList &L1) //插入元素到顺序表里{ int a; int j; ElemType e1;a=L1.length;cout<<"请选择所要插入元素的位置:";cin>>j;while(j<0||j>Listlength(L1)){ cout<<"输入有误，请重新输入"<<endl;cout<<"请选择所要插入元素的位置:";cin>>j; }cout<<"要插入的元素:";cin>>e1;ListInsert(L1,j,e1);cout<<"修改后的顺序表数据:"<<endl;show(L1,a+1);}void hebing(SqList &L3) //合并两个顺序表{ SqList L1,L2;int a,b;InitList_Sq(L1); InitList_Sq(L2);cout<<"请输入第一个有序表的长度："; cin>>a;cout<<"请输入第一个有序表的元素(共"<<a<<"个)"<<endl;create(L1,a);show(L1,a);cout<<"请输入第二个有序表的长度："; cin>>b;cout<<"请输入第二个有序表的元素(共"<<b<<"个)"<<endl;create(L2,b);show(L2,b);MergeList(L1,L2,L3);cout<<"合并后的有序表如下："; show(L3,a+b);}void main() //主菜单{ int choice;for(;;){ cout<<" 顺序表的基本操作"<<endl;cout<<" 1.顺序表的创建"<<endl;cout<<" 2.顺序表的显示"<<endl;cout<<" 3.顺序表的长度"<<endl;cout<<" 4.取第i个位置的元素"<<endl;cout<<" 5.修改第i个位置的元素"<<endl;cout<<" 6.插入元素到顺序表里"<<endl;cout<<" 7.删除顺序表里的元素"<<endl;cout<<" 8.合并两个顺序表"<<endl;cout<<" 9.退出系统"<<endl;cout<<"请选择：";cin>>choice;switch(choice){ case 1: shuru(Lx);break;case 2: show(Lx,Lx.length);break;case 3: cout<<"顺序表的长度:"<<Listlength(Lx)<<endl;break; case 4: chaxun(Lx);break;case 5: xiugai(Lx);break;case 6: charu(Lx);break;case 7: shanchu(Lx);break;case 8: hebing(Lx);break;case 9: cout<<"退出系统!"<<endl;exit(0);break;default : cout<<"输入有误，请重新选择"<<endl;break; }}}(二)单链表的基本操作#include<iostream>using namespace std;#define true 1#define false 0#define ok 1#define error 0#define overflow -2typedef int Status;typedef int ElemType;typedef struct LNode //存储结构{ ElemType data;struct LNode *next;}LNode,*LinkList;void CreateList(LinkList &L,int n) //尾插法创建单链表{ LinkList p;L=new LNode;L->next=NULL; //建立一个带头结点的单链表LinkList q=L; //使q指向表尾for(int i=1;i<=n;i++){ p=new LNode;cin>>p->data;p->next=NULL;q->next=p;q=p; }}Status GetElem(LinkList L,int i,ElemType &e)//取第i个元素{ LinkList p=L->next;int j=1;while(p&&j<i){ p=p->next;++j; }if(!p||j>i) return error; //第i个元素不存在 e=p->data;return ok;}Status LinkInsert(LinkList &L,int i,ElemType e) //插入{ LinkList p=L;int j=0;while(p&&j<i-1){ p=p->next;++j; } //寻找第i-1个结点 if(!p||j>i-1)return error; //i小于1或者大于表长加1 LinkList s=new LNode; //生成新结点s->data=e;s->next=p->next; //插入L中p->next=s;return ok;}Status ListDelete(LinkList &L,int i,ElemType &e) // 删除{ LinkList p=L;LinkList q;int j=0;while(p->next&&j<i-1){ //寻找第i个结点，并令p指向其前驱p=p->next;++j; }if(!(p->next)||j>i-1) return error; //删除位置不合理q=p->next;p->next=q->next; //删除并释放结点e=q->data;delete(q);return ok;}void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc) { //合并两个顺序链表LinkList pa,pc,pb;pa=La->next;pb=Lb->next;Lc=pc=La;while(pa&&pb){ if(pa->data<=pb->data){ pc->next=pa;pc=pa;pa=pa->next; }else{ pc->next=pb;pc=pb;pb=pb->next; }}pc->next=pa?pa:pb;delete(Lb);}void show(LinkList L) //显示{ LinkList p;p=L->next;while(p){ cout<<p->data<<"-->";p=p->next; }cout<<endl;}int Length(LinkList L,int i) //表长{ i=0;LinkList p=L->next;while(p){ ++i;p=p->next; }return i;}void xiugai(LinkList L) //修改{ int i,j=1;ElemType k;ElemType e,m;LinkList p=L->next;cout<<"请输入要修改的元素位置(0<i<length):";cin>>i;GetElem(L,i,e);cout<<"该位置的元素:"<<e<<endl;cout<<"修改后的元素值:";cin>>k;while(p&&j<i){ p=p->next;++j; }m=p->data;p->data=k;cout<<"修改后的单链表显示如下:"<<endl;show(L);}void hebing() //合并两个单链表{ int a,b;LinkList La,Lb,Lc;cout<<"请输入第一个有序链表的长度:"<<endl;cin>>a;cout<<"请输入第一个有序链表的元素共（"<<a<<"个）："<<endl;CreateList(La,a);show(La);cout<<"请输入第二个有序链表的长度:"<<endl;cin>>b;cout<<"请输入第二个有序链表的元素共（"<<b<<"个）："<<endl;CreateList(Lb,b);show (Lb);MergeList(La,Lb,Lc);cout<<"合并后的有序链表如下："<<endl;show(Lc);}void main() //主函数{ int select;int x;ElemType y;LinkList list;for(;;){ cout<<" 单链表的基本操作"<<endl;cout<<" 1.单链表的创建"<<endl;cout<<" 2.单链表的显示"<<endl;cout<<" 3.单链表的长度"<<endl;cout<<" 4.取第i个位置的元素"<<endl;cout<<" 5.修改第i个位置的元素"<<endl;cout<<" 6.插入元素到单链表里"<<endl;cout<<" 7.删除单链表里的元素"<<endl;cout<<" 8.合并两个单链表"<<endl;cout<<" 9.退出系统"<<endl;cout<<"请选择:";cin>>select;switch(select){ case 1:cout<<"请输入单链表的长度:"<<endl;cin>>x;cout<<"请输入"<<x<<"个元素"<<endl;CreateList(list,x);break;case 2: cout<<"单链表显示如下:"<<endl;show(list);break;case 3: int s;cout<<"单链表的长度为:"<<Length(list,s)<<endl;break;case 4: cout<<"请选择所要取出元素的位置:";while(x<0||x>Length(list,s)){ cout<<"输入有误，请重新输入"<<endl;cout<<"请选择所要取出元素的位置:";cin>>x; }GetElem(list,x,y);cout<<"该位置的元素为:"<<y<<endl;break;case 5: xiugai(list); break;case 6: cout<<"请选择要插入的位置:"; cin>>x;while(x<0||x>Length(list,s)){ cout<<"输入有误，请重新输入"<<endl;cout<<"请选择所要插入元素的位置:";cin>>x; }cout<<"要插入的元素值:";cin>>y;LinkInsert( list,x,y);cout<<"插入后单链表显示如下:"<<endl;show(list);break;case 7: cout<<"请选择要删除的位置:"; cin>>x;while(x<0||x>Length(list,s)){ cout<<"输入有误，请重新输入"<<endl;cout<<"请选择所要删除元素的位置:";cin>>x; }ListDelete(list,x,y);cout<<"要删除的元素值:"<<y<<endl;cout<<"删除后的单链表显示如下:"<<endl;show(list);break;case 8: hebing();break;case 9: exit(0);default : cout<<"输入有误，请重新输入"<<endl;break;}}}四、测试结果1)顺序表的测试结果2)单链表的测试结果五、心得体会当听到老师说写数据结构实验报告时，我有点惊讶，才学了不到一个月，就要写实验报告。

一、课程的性质、任务与基本要求（一）课程的性质、任务1．课程的性质《数据结构》是软件技术专业中一门重要的专业必修课程。

它与数学和计算机软件设计有十分密切的关系，是计算机软件专业的一门核心课程，是程序设计、操作系统、数据库等课程的基础。

同时，数据结构技术也广泛应用于信息科学、系统工程、应用数学以及各种工程技术领域。

当我们用计算机来解决实际问题时，就要涉及到数据的表示及数据的处理，而数据表示及数据处理正是《数据结构》课程的主要研究对象，通过这两方面内容的学习，为后续课程，特别是软件方面的课程打下了厚实的知识基础，同时也提供了必要的技能训练。

因此，《数据结构》课程在计算机软件专业中具有重要的作用。

2．课程的任务①本课程实现专业培养目标中所承担的任务：在基础方面，要求学生掌握常用数据结构的基本概念及其不同的实现方法；在技能方面，通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会。

②本课程教学内容及教学环节等方面与相关课程的联系与分工：《数据结构》是计算机软件专业的一门核心课程，数据结构技术也广泛应用于信息科学、系统工程、应用数学以及各种工程技术领域。

③本课程相关的先修课及后续课：先修课：《Java语言程序设计基础》或《Python语言程序设计基础》；后续课：程序设计、项目开发、数据库等课程。

（二）基本要求具体要求学生通过各个教学环节达到以下目标：1 通过学习掌握各种数据结构的逻辑结构、物理结构以及在之上实施的算法2 提高程序设计能力和编程质量3 学会分析研究计算机加工的数据对象的特性，能选择适当的数据结构以及相应的算法4 通过本课程的学习，使学生的逻辑分析、抽象思维和程序设计的能力有所提高，培养学生具有优良的程序设计风格5 通过本课程的学习，为后续的软件课程打下良好基础二、主要教学内容及教学要求第一章绪论教学内容1.1 数据结构的概念1.2 算法的概念1.3 算法描述和算法分析概念介绍教学要求⑴领会数据、数据元素和数据项的概念及其相互间关系⑵清楚数据结构的逻辑结构、存储结构的联系与区别，以及在数据结构上施加的运算及其实现⑶掌握“数据结构”的描述及算法的概念⑷掌握描述算法的方法⑸了解进行简单算法分析的方法第二章线性表教学内容2.1 线性表的基本概念和运算2.2 顺序表2.3 链表及其操作2.4 栈和队列教学要求⑴理解线性表的定义及其运算⑵理解顺序表定义、组织形式、结构特征和类型说明⑶掌握在顺序表上实现的插入、删除和查找的算法⑷掌握单链表和循环链表的结构特点及基本操⑸了解双向链表和双向循环链表的结构特点(6) 理解栈的定义、特征及在其上所定义的基本运算(7) 掌握在顺序和动态存储结构上栈基本运算的实现(8) 理解队列的定义、特征及在其上所定义的基本运算(9) 掌握在顺序和动态存储结构上队列基本运算的实现第三章串教学内容4.1 串的基本概念4.2 串的基本操作4.3 串的存储结构4.4 串操作应用举例教学要求⑴掌握串的基本概念、基本运算⑵了解串的存储方式⑶理解串的基本操作算法第四章数组和广义表教学内容4.1 多维数组4.2 特殊矩阵和压缩存储介绍4.3 稀疏矩阵介绍4.4 广义表介绍教学要求(1) 理解多维数组的逻辑结构和数组的顺序分配(2) 了解顺序存储结构上元素在存储区中地址的计算(3) 了解特殊矩阵和压缩存储、稀疏矩阵、广义表等概念第五章树教学内容5.1树的定义和基本术语5.2 二叉树5.3 遍历二叉树5.4 线索二叉树5.5树和森林5.6 哈夫曼树教学要求⑴深刻理解并掌握树的定义、术语⑵领会树的存储结构⑶深刻理解并掌握二叉树的定义、性质及其存储方法⑷掌握二叉树的存储方式、结点结构和类型定义⑸理解并掌握二叉树的三种遍历算法⑹能够运用二叉树的遍历方法解决简单的应用问题⑺了解线索二叉排的定义及构造方法⑻掌握二叉树与树、森林之间相互转换的方法⑼理解哈夫曼树并掌握哈夫曼算法第六章图教学内容6.1 图的定义和基本术语6.2 图的存储结构6.3 图的遍历6.4 生成树和最小生成树6.5拓扑排序6.6关键路径6.7 最短路径教学要求⑴理解图的定义、术语及其含义⑵掌握图存储结构⑶理解并掌握图的遍历方法⑷领会生成树和最小生成树的概念⑸掌握构造最小生成树的算法思想⑹领会拓扑序列和拓扑排序的概念⑺理解并掌握拓扑排序的算法思想⑻理解并掌握关键路径的算法思想⑼理解并掌握最短路径的算法思想第七章查找教学内容7.1 线性表查找7.2 顺序查找7.3折半查找7.4 索引查找7.5 二叉排序树7.6 哈希表查找教学要求⑴掌握查找操作的基本思想⑵理解查找表的基本概念及查找原理⑶掌握在顺序表、有序表、索引表、树表以及哈希表等结构上进行查找操作的方法和算法描述⑷掌握哈希表的组织以及解决冲突的方法⑸能够根据不同场合确定合适的查找方法第八章内部排序教学内容8.1 基本概念8.2 插入排序8.3 交换排序8.4 选择排序8.5 归并排序8.6 基数排序8.7 各种排序方法的比较及应用教学要求⑴理解排序基本概念及内部排序和外部排序、稳定排序和非稳定排序的区别⑵掌握直接插入排序的基本思想、基本步骤和算法⑶掌握希尔排序的基本思想、基本步骤和算法⑷掌握冒泡排序的基本思想、基本步骤和算法⑸掌握快速排序的基本思想、基本步骤和算法⑹掌握直接选择排序的基本思想、基本步骤和算法⑺掌握堆排序的基本思想、基本步骤和算法⑻理解两个有序文件合并的方法和算法⑼了解归并排序的基本思想、基本步骤和算法⑽了解基数排序的基本思想、基本步骤和算法⑾了解根据不同场合确定合适的排序方法。

1.基本数据结构与算法1.1算法算法：是指解题方案的准确而完整的描述。

特征包括：（1）可行性；（2）确定性，（3）有穷性，（4）拥有足够的情报。

算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。

指令系统：一个计算机系统能执行的所有指令的集合。

基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。

算法的控制结构：顺序结构、选择结构、循环结构。

算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。

算法复杂度：算法时间复杂度和算法空间复杂度。

算法时间复杂度是指执行算法所需要的计算工作量。

算法空间复杂度是指执行这个算法所需要的内存空间。

数据的存储结构有顺序、链接、索引等。

线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。

非线性结构：不满足线性结构条件的数据结构。

1.3线性表及其顺序存储结构非空线性表的结构特征：（1）且只有一个根结点a1，它无前件；（2）有且只有一个终端结点an，它无后件；（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。

结点个数n称为线性表的长度，当n=0时，称为空表。

线性表的顺序存储结构具有以下两个基本特点：（1）线性表中所有元素的所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

顺序表的运算：插入、删除。

1.4栈和队列a）栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。

栈按照“先进后出"（FILO）或“后进先出"（LIFO）组织数据，栈具有记忆作用。

用top表示栈顶位置，用bottom表示栈底。

栈的基本运算：（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。

b）队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。

第一章：绪论：数据结构课程的任务是：讨论数据的各种逻辑结构、在计算机中的存储结构以及各种操作的算法设计;：数据：是客观描述事物的数字、字符以及所有的能输入到计算机中并能被计算机接收的各种集合的统称;数据元素：表示一个事物的一组数据称作是一个数据元素,是数据的基本单位;数据项：是数据元素中有独立含义的、不可分割的最小标识单位;数据结构概念包含三个方面：数据的逻辑结构、数据的存储结构的数据的操作;数据的逻辑结构指数据元素之间的逻辑关系,用一个数据元素的集合定义在此集合上的若干关系来表示,数据结构可以分为三种：线性结构、树结构和图;：数据元素及其关系在计算机中的存储表示称为数据的存储结构,也称为物理结构;数据的存储结构基本形式有两种：顺序存储结构和链式存储结构;：算法：一个算法是一个有穷规则的集合,其规则确定一个解决某一特定类型问题的操作序列;算法规则需满足以下五个特性：输入——算法有零个或多个输入数据;输出——算法有一个或多个输出数据,与输入数据有某种特定关系;有穷性——算法必须在执行又穷步之后结束;确定性——算法的每个步骤必须含义明确,无二义性;可行性——算法的每步操作必须是基本的,它们的原则上都能够精确地进行,用笔和纸做有穷次就可以完成;有穷性和可行性是算法最重要的两个特征;：算法与数据结构：算法建立数据结构之上,对数据结构的操作需用算法来描述;算法设计依赖数据的逻辑结构,算法实现依赖数据结构的存储结构;：算法的设计应满足五个目标：正确性：算法应确切的满足应用问题的需求,这是算法设计的基本目标;健壮性：即使输入数据不合适,算法也能做出适当的处理,不会导致不可控结高时间效率：算法的执行时间越短,时间效率越高; 果;高空间效率：算法执行时占用的存储空间越少,空间效率越高;可读性：算法的可读性有利于人们对算法的理解;：度量算法的时间效率,时间复杂度,课本39页;：递归定义：即用一个概念本身直接或间接地定义它自己;递归定义有两个条件：至少有一条初始定义是非递归的,如1=1.由已知函数值逐步递推计算出未知函数值,如用n-1定义n;第二章：线性表线性表：线性表是由nn>=0个类型相同的数据元素a0,a1,a2,…an-1,组成的有限序列,记作：Linear List = a0,a1,a2,…an-1其中,元素ai可以是整数、浮点数、字符、也可以是对象;n是线性表的元素个数,成为线性表长度;若n=0,则LinearList为空表;若n>0,则a0没有前驱元素,an-1没有后继元素,ai0<i<n-1有且仅有一个直接前驱元素ai-1和一个直接后继元素ai+1;线性表的顺序存储是用一组连续的内存单元依次存放线性表的数据元素,元素在内存的物理存储次序与它们在线性表中的逻辑次序相同;线性表的数据元素数据同一种数据类型,设每个元素占用c字节,a0的存储地址为Loca0,则ai的存储地址Locai为：Locai = Loca0+ ic数组是顺序存储的随机存储结构,它占用一组连续的存储单元,通过下标识别元素,元素地址是下标的线性函数;：顺序表的插入和删除操作要移动数据元素;平均移动次数是属数据表长度的一半;课本第50页：线性表的链式存储是用若干地址分散的存储单元存储数据元素,逻辑上相邻的数据元素在物理位置上不一定相邻,必须采用附加信息表示数据元素之间的顺序关系;它有两个域组成：数据域和地址域;通常成为节点;课本第55页及56页单链表课本56页单链表的遍历：Node<E> p = head; whilep=null{ 访问p节点；p = ;}单链表的插入和删除操作非常简便,只要改变节点间的链接关系,不需移动数据元素;单链表的插入操作：1：空表插入/头插入2中间插入/尾插入ifhead == null Node<E> q = new Node<E>x;{ head = new Node<E>x; = ;}else{ = q;Node<E> q=new Node<E>x; 中间插入或尾插入都不会改变单表= head; 的头指针head;head = q;}单链表的删除操作：头删除：head = ;中间/尾删除：if=null{ =循环单链表：如果单链表最后一个节点的next链保存单链表的头指针head值,则该单链表成为环形结构,称为循环单链表;课本67若rear是单链表的尾指针,则执行=head;语句,使单链表成为一条循环单链表;当==head时,循环单链表为空;：双链表结构：双链表的每个结点有两个链域,分别指向它的前驱和后继结点,当==null时,双链表为空;设p指向双链表中非两端的某个结点,则成立下列关系：p=;双链表的插入和删除：1插入2删除q=new DLinkNodex；= ;=; =p; if=null{= q;=q; .prev = ;}循环双链表：当==head且==head时,循环双链表为空;第三章：栈和队列栈：栈是一种特殊的线性表,其中插入和删除操作只允许在线性表的一端进行;允许操作的一端称为栈顶,不允许操作的一端称为栈底;栈有顺序栈和链式栈;栈中插入元素的操作称为入栈,删除元素的操作称为出栈;没有元素的中称为空栈;栈的进出栈顺序：后进先出,先进后出;及75页的思考题;：队列：队列是一种特殊的线性表,其中插入和删除操作分别在线性表的两端进行;向队列中插入元素的过程称为入队,删除元素的过程称为出对,允许入队的一端称为队尾,允许出队的一端称为对头;没有元素的队列称为空队列;队列是先进先出;第四章：串：串是一种特殊的线性表,其特殊性在于线性表中的每个元素是一个字符;一个串记为：s=“s0s1s2…sn-1” 其中n>=0,s是串名,一对双引号括起来的字符序列s0s1s2…sn-1是串值,sii=0,1,2,…n-1为特定字符集合中的一个字符;一个串中包含的字符个数称为串的长度;长度为0的串称为空串,记作“”,而由一个或多个空格字符构成的字符串称为空格串;子串：由串s中任意连续字符组成的一个子序列sub称为s的子串,s称为sub 的主串;子串的序号是指该子串的第一个字符在主串中的序号;串比较：两个串可比较是否相等,也可比较大小;两个串子串相等的充要条件是两个串子串的长度相同,并且各对应位置上的字符也相同;两个串的大小由对应位置的第一个不同字符的大小决定,字符比较次序是从头开始依次向后;当两个串长度不等而对应位置的字符都相同时,较长的串定义为较“大”;第五章：数组和广义表：数组是一种数据结构,数据元素具有相同的数据类型;一维数组的逻辑结构是线性表,多维数组是线性表的扩展;：一维数组：一维数组采用顺序存储结构;一个一维数组占用一组连续的存储单元;设数组第一个元素a0的存储地址为Loca0,每个元素占用c字节,则数组其他元素ai的存储地址Locai为：Locai= Loca0+ic数组通过下标识别元素,元素地址是下标的线性函数;一个下标能够唯一确定一个元素,所划给的时间是O1;因此数组是随机存取结构,这是数组最大的优点;：多维数组的遍历：有两种次序：行主序和列主序;行主序：以行为主序,按行递增访问数组元素,访问完第i行的所有元素之后再访问第i+1行的元素,同一行上按列递增访问数组元素;a00,a01,…a0n-1, a10,a11,…a1n-1,…am-10,am-11,…,am-1n-12列主序：以列为主序,按列递增访问数组元素,访问完第j列的所有元素之后再访问第j+1列的元素,同一列上按列递增访问数组元素;多维数组的存储结构：多维数组也是由多个一维数组组合而成,组合方式有一下两种;静态多维数组的顺序存储结构：可按行主序和列主序进行顺序存储;按行主序存储时,元素aij的地址为：Locaij= Loca00+in+jc按列主序存储时,Locaij= Loca00+jm+ic动态多维数组的存储结构;二维数组元素地址就是两个下标的线性函数;无论采用哪种存储结构,多维数组都是基于一维数组的,因此也只能进行赋值、取值两种存取操作,不能进行插入,删除操作;第六章：树是数据元素结点之间具有层次关系的非线性结构;在树结构中,除根以外的结点只有一个直接前驱结点,可以有零至多个直接后继结点;根没有前驱结点;树是由nn>=0个结点组成的有限集合树中元素通常称为结点;N=0的树称为空树；n>0大的树T；有一个特殊的结点称为根结点,它只有后继结点,没有前驱结点;除根结点之外的其他结点分为mm>=0个互不相交的集合T0,T1,T3……..,Tm-1,其中每个集合Ti0<=i<m本身又是一棵树,称为根的子树;树是递归定义的;结点是树大的基本单位,若干个结点组成一棵子树,若干棵互不相交的子树组成一棵树;树的每个结点都是该树中某一棵子树的根;因此,树是由结点组成的、结点之间具有层次关系大的非线性结构;结点的前驱结点称为其父母结点,反之,结点大的后继结点称为其孩子结点;一棵树中,只有根结点没有父母结点,其他结点有且仅有一个父母结点;拥有同一个父母结点的多个结点之间称为兄弟结点;结点的祖先是指从根结点到其父母结点所经过大的所有结点;结点的后代是指该结点的所有孩子结点,以及孩子的孩子等;结点的度是结点所拥有子树的棵数;度为0的结点称为叶子结点,又叫终端结点；树中除叶子结点之外的其他结点称为分支结点,又叫非叶子结点或非终端结点;树的度是指树中各结点度的最大值;结点的层次属性反应结点处于树中的层次位置;约定根结点的层次为1,其他结点的层次是其父母结点的层次加1;显然,兄弟结点的层次相同;树的高度或深度是树中结点的最大层次树;设树中x结点是y结点的父母结点,有序对x,y称为连接这两个结点的分支,也称为边;设X0,X1,….,Xk-1是由树中结点组成的一个序列,且Xi,Xi+10<=i<k-1都是树中的边,则该序列称为从X0到Xk-1的一条路径;路径长度为路径上的边数;在树的定义中,结点的子树T0,T1…..,Tm-1之间没有次序,可以交换位置,称为无序树,简称树;如果结点的子树T0,T1……,Tm-1从左到右是有次序的,不能交换位置,则称该树为有序树;森林是mm>=0棵互不相干的树的集合;给森林加上一个根结点就变成一棵树,将树的根节点删除就变成森林;二叉树的性质1：若根结点的层次为1,则二叉树第i层最多有2 的i-1次方i>=1个结点;二叉树的性质2：在高度为k的二叉树中,最多有2的k次方减一个结点;二叉树的性质3：设一棵二叉树的叶子结点数为n0,2度结点数为n2,则n0=n2+1;一棵高度为k的满二叉树是具有2的k次方减一个结点的二叉树;满二叉树中每一层的结点数目都达到最大值;对满二叉树的结点进行连续编号,约定根节点的序号为0,从根节点开始,自上而下,每层自左至右编号;一棵具有n个结点高度为k的二叉树,如果他的每个节点都与高度为k的满二叉树中序号为0~n-1的结点一一对应,则这棵二叉树为为完全二叉树;满二叉树是完全二叉树,而完全二叉树不一定是满二叉树;完全二叉树的第1~k-1层是满二叉树第k层不满,并且该层所有结点必须集中在该层左边的若干位置上;二叉树的性质4：一棵具有n个结点的完全二叉树,其高度k=log2n的绝对值+1二叉树的性质5：一棵具有n个结点的完全二叉树,对序号为i的结点,有若i=0,则i为根节点,无父母结点；若i>0,则i的父母结点的序号为i-1/2;若2i+1<n,则i的左孩子结点序号为2i+1；否则i无左孩子;若2i+2<n,则i的右孩子结点的序号为2i+2,否则i无右孩子;二叉树的遍历二叉树的遍历是按照一定规则和次序访问二叉树中的所有结点,并且每个结点仅被访问一次;二叉树的三种次序遍历1：先根次序；访问根节点,遍历左子树,遍历右子树;2：中根次序；遍历左子树,访问右子树,遍历右子树;3：后根次序；遍历左子树,遍历右子树,访问根节点;先根次序遍历时,最先访问根节点；后根次序遍历时,最后访问根节点；中根次序遍历时,左子树上的结点在根节点之前访问,右子树上的结点在根节点之后访问;二叉树的插入和删除操作P147二叉树的层次遍历P149习题P167 6—10,6—19第七章图是由定点集合及顶点间的关系集合组成的一种数据关边系;顶点之间的关系成为边;一个图G记为G=V,E,V是顶点A的有限集合,E是边的有限集合;即V={A|A属于某个数据元素集合}E={A,B|A,B属于V}或E={<A,B>|A,B属于V且PathA,B}其中PathA,B表示从顶点A到B的一条单向通路,即PathA,B是有方向的;无向图中的边事没有方向,每条边用两个顶点的无序对表示;有向图中的边是有方向,每条边用两个顶点的有序对表示;完全图指图的边数达到最大值;n个顶点的完全图记为Kn;无向完全图Kn的边数为nn-1/2,有向完全图Kn的边数为nn-1;子图：设图G==V,E,G’=V’,E’,若V’包含于V且E’包含于E,则称图G’是G的子图;若G’是G的真子图;连通图：在无向图G中,若从顶点VI到Vj有路径,则称Vi和Vj是联通的;若图G 中任意一对顶点Vi和VjVi不等于Vj都是联通的,则称G为连通图;非连通图的极大联通子图称为该图的联通分量;强连通图：在有向图中,若在每一对顶点Vi和VjVi不等于Vj之间都存在一条从Vi到Vj的路径,也存在一条从Vi到Vj的路径,也存在一条从Vi到Vj的路径,则称该图的强连通图;非强连通图的极大强连通子图称为该图的强连通图分量;图的遍历遍历图是指从图G中任意一个顶点V出发,沿着图中的边前行,到达并访问图中的所有顶点,且每个顶点仅被访问一次;遍历图要考虑一下三个问题：指定遍历的第一个访问顶点由于一个顶点可能与多个顶点相邻,因此要在多个邻接顶点之间约定一种访问次序;由于图中可能存在回路,在访问某个顶点之后,可能沿着某条路径又回到该顶点;深度优先搜索图的深度优先搜索策略是,访问某个顶点v,接着寻找v的另一个未被访问的邻接顶点w访问,如此反复执行,走过一条较长路径到达最远顶点；若顶点v没有未被访问的其他邻接顶点,则回到前一个被访问顶点,再寻找其他访问路径;图的深度优先搜索遍历算法P188联通的无回路的无向图,简称树;树中的悬挂点又成为树叶,其他顶点称为分支点;各连通分量均为树的图称为森林,树是森林;由于树中无回路,因此树中必定无自身环也无重边否则他有回路若去掉树中的任意一条边,则变成森林,成为非联通图；若给树加上一条边,形成图中的一条回路,则不是树;P191生成树和生成森林：一个连通无向图的生成树是该图的一个极小联通生成子图,它包含原图中所有顶点n个以及足以构成一棵树的n-1条边;一个非联通的无向图,其各连通图分量的生成图组成该图的生成森林;图的生成图或生成森林不是唯一的,从不同顶点开始、采用不同遍历可以得到不同的生成树或森林;在生成树中,任何树中,任何两个顶点之间只有唯一的一条路径;第八章折半查找算法描述P206,P207二叉排序树及其查找：二叉排序树或者是一棵空树；或者是具有下列性质的二叉树：每个结点都有一个作为查找依据的关键字,所有结点的关键字互不相同;若一个结点的左子树不空,则左子树上所有结点的关键字均小于这个节点的关键字；每个结点的左右子树也分别为二叉排序树;在一棵二叉排序树中,查找值为value的结点,算法描述如下：从根结点开始,设p指向根结点将value与p结点的关键字进行比较,若两者相等,则查找成功；若value值较小,则在p的左子树中继续查找；若value值较大,则在p的右子树中继续查找;重复执行上一步,直到查找成功或p为空,若p为空,则查找不成功;习题8-6第九章直接插入排序算法描述：p228冒泡排序算法的描述：p232快速排序算法描述p233直接选择排序算法描述p236直接选择排序算法实现如下：Public static void selectSortinttable{forint i=0;i<;i++{int min=I;forint j=i+1;j<;j++{iftablej<tableminmin=j;ifmin=i{int temp=tablei;tablei==tablemin;tablemin=temp;}}}}堆排序是完全二叉树的应用,是充分利用完全二叉树特性的一种选择排序;堆定义：设n个元素的数据序列{k0,k1,;;;;kn-1},当且仅当满足下列关系k1<=k2i+1且ki<=k2i+2 i=0,1,2,3,….,n/2-1或ki>==k2i+1且ki>=2i+2i=0,1,2,3,…..n/2-1时,序列{k0,k1…….kn-1}称为最小堆或最大堆;将最小大堆看成是一颗完全二叉树的层次遍历序列,则任意一个结点的关键字都小于等于大于等于它的孩子节点的关键字值,由此可知,根结点值最小大;根据二叉树的性质5,完全二叉树中的第i0<=i<n个结点,如果有孩子,则左孩子为第2i+1个结点,右孩子为第2i+2个结点;。

第一章用计算机处理的实际问题可分为两大类问题：数值计算非数值计算现实中对象之间的关系：线性关系，层次关系，网状关系数据结构定义: 是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科简单定义为：相互之间存在一种或多种特定关系的数据元素的集合。

基本概念和术语⏹数据（data)—所有能输入到计算机中去的描述客观事物的符号⏹数据元素（data element）—数据的基本单位，也称节点（node）或记录（record）⏹数据项（data item）—有独立含义的数据最小单位，也称域(field)⏹数据结构（data structure)—数据元素和数据元素关系的集合根据数据元素间关系的基本特性，有四种基本数据结构集合——数据元素间除―同属于一个集合‖外，无其它关系线性结构——一个对一个，如线性表、栈、队列树形结构——一个对多个，如树图状结构或网状结构——多个对多个，如图；数据的逻辑结构—指抽象反映数据元素的逻辑关系。

数据的逻辑结构有两大类：⏹线性结构：线性表⏹非线性结构：树和图数据的存储（物理）结构—数据的逻辑结构在计算机存储器中的实现。

存储结构分为：顺序存储结构——借助元素在存储器中的相对位置来表示数据元素间的逻辑关系链式存储结构——借助指示元素存储地址的指针表示数据元素间的逻辑关系索引存储方法散列存储方法数据的逻辑结构与存储结构密切相关逻辑结构存储结构数据结构的研究内容●研究数据之间的相互关系，即数据的组织形式，包括：⏹数据元素之间的逻辑关系，也称为数据的逻辑结构(Logical structure)。

⏹数据元素及其关系在计算机存储器内的表示，称为数据的存储结构。

●数据的运算，即基于某种存储结构对数据施加的操作或运算。

算法：通俗地讲，一个算法就是一种解题方法更严格地说，算法是由若干条指令组成的有穷序列算法必须满足下述准则：重要特性输入：具有0个或多个输入的外界量。

输出：至少产生一个输出。

数据结构导论知识点第一章概论数据结构：是相互之间存在一种或多种关系的数据元素的集合。

和该集合中数据元素之间的关系组成。

数据结构包括数据的逻辑结构、数据的存储结构和数据的基本运算。

简单地说，数据结构是计算机组织数据和存储数据的方式。

更进一步地说，数据结构是指一组相互之间存在一种或多种特定关系的数据的组织方式和它们在计算机内的存储方式，以及定义在该组数据上的操作。

合理的数据结构可降低程序设计的复杂性，提高程序执行的效率。

1.1 引言计算机解决一个具体问题时，一般需要经过以下几个步骤：①从具体的问题抽象出一个适当的数学模型；②设计一个求解该数学模型的算法；③用某种计算机语言编写实现该算法的程序，调试和运行程序直至最终得到问题的解答。

数据的逻辑结构：数据和数据的组织方式称为数据的逻辑结构。

为了能用计算机加工处理，逻辑结构还必须转换为能被计算机存储的存储结构。

1976年瑞士计算机科学家尼克劳斯·维尔特提出公式：算法+数据结构=程序。

该公式简洁的描述了数据结构和程序之间关系。

1.2 基本概念和术语1.2.1 数据、数据元素和数据项数据：所有被计算机存储、处理的对象。

数据元素：简称元素（又称为结点），数据的基本单位，在程序中作为一个整体而加以考虑和处理。

数据元素是运算的基本单位，通常具有完整确定的实际意义。

数据元素由数据项组成。

数据项：在数据库中数据项又称为字段或域，是数据的不可分割的最小标识单位，组成数据元素。

关系：数据、数据元素和数据项实际上反映了数据组织的三个层次，数据可由若干个数据元素组成，而数据元素又可由若干个数据项组成。

表格（逻辑结构），行=记录=数据元素，列=数据项。

1.2.2 数据的逻辑结构数据的逻辑结构：是指数据元素之间的逻辑关系。

逻辑关系：是指数据元素之间的关联方式或邻接关系。

逻辑结构示意图中的小圆圈称为结点，一个结点代表一个数据元素（记录）。

根据数据元素之间关系的不同特性，通常有集合、线性结构、树形结构和图结构四类基本逻辑结构，反映了四类基本的数据组织形式。

数据结构笔记基础：数据结构与算法（一）数据结构基本概念数据（data）：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号总称数据元素（data element）：是数据的基本单位，在计算机中通常被当做一个整体进行考虑和处理数据对象（data object）：性质相同的数据元素的集合，是数据的一个子集数据结构（data structure）：相互之间存在一种或多种特定关系的数据元素的集合4类基本结构：集合、线性结构、树形结构、图形（网状）结构数据结构的形式定义为数据结构是一个二元组Data Structure = （D,S），其中D是数据元素的有限集，S是D上关系的有限集数据结构定义中的“关系”描述的是数据元素之间的逻辑关系，因此又称为数据的逻辑结构数据结构在计算机中的表示（映像）称为物理结构（存储结构）计算机中表示信息的最小单位是二进制中的一位，叫做位（bit），一到若干位组成一个位串表示一个数据元素，这个位串称为元素或结点数据结构之间关系在计算机中的表示有两种：顺序映像、非顺序映像，并由此得到两种存储结构：顺序存储、链式存储，前者运用相对位置表示数据元素间的逻辑结构，后者借助指针任何一个算法的设计取决于数据（逻辑）结构，而实现依赖于存储结构数据类型是一个值的集合和定义在这个值集上的一组操作的总称数据类型分两种：原子类型、结构类型，前者不可分解（例如int、char、float、void ），后者结构类型由若干成分按某种结构组成，可分解，成分既可以是非结构的也可以是结构的（例：数组）抽象数据类型（Abstract Data Type ）：是指一个数学模型及定义在该模型上的一组操作（P8）抽象数据类型格式如下：ADT抽象数据类型名{数据对象：<数据对象的定义>数据关系：<数据关系的定义>数据操作：<数据操作的定义>}ADT抽象数据类型名基本操作格式如下：基本操作名（参数表）初始条件：<初始条件描述>操作结果：<操作结果描述>多形数据类型（polymorphic data type）：是指其值得成分不确定的数据类型（P9）抽象数据类型可由固有数据类型来表示和实现（二）算法（概念）和算法分析（时、空性能）算法（algorithm）：对特定问题求解步骤的一种描述算法5特性：有穷、确定、可行、输入、输出1、有穷性：算法必须在可接受的时间内执行有穷步后结束2、确定性：每条指令必须要有确切含义，无二义性，并且只有唯一执行路径，即对相同的输入只能得相同输出3、可行性：算法中的操作都可通过已实现的基本运算执行有限次来完成4、输入：一个算法有一到多个输入，并取自某个特定对象合集5、输出：一个算法有一到多个输出，这些输出与输入有着某些特定关系的量算法设计要求（好算法）：正确性、可读性、健壮性、效率与低存储需求健壮性是指对于规范要求以外的输入能够判断出这个输入不符合规范要求，并能有合理的处理方式。