掌握基本概念。
1、元素：数据基本单位。
2、逻辑结构。
定义：元素及关系，与计算机无关，只是实际问题的数学抽象表示。
分类：集合、线性结构、树、图。
3、存储结构。
定义：逻辑结构在计算机中的表示（内存）
分类：顺序存储（数组）、链式存储（链表）
4、算法及效率。
常见的基础算法。
定义：（计算机）解决问题的有限步骤。
效率度量：时间复杂度、空间复杂度。
1、 定义：由n（n>=0）个元素组成的有限序列。n为0，空表，n>0时，lists=(a1,a2,…an),ai称为元素，称为序偶，或前驱和后继关系。
2、 操作：插入、删除、排序、查找等。
1、 定义：用物理地址连续的一段内存存储线性表中逻辑相邻的元素，这种存储结构称为顺序表。
2、 c++的存储实现。
const int maxsize=100; /表示表中存储元素的最大值。
t data[maxsize]; 数组data用来存储元素，以整型为例。
int length; /length值记录表data中存储元素的实际个数。
3、 操作（常见算法）
1） 插入：已知表中length个元素已经存在，实现在表的i位置插入x
算法基本思想：
a） 表满不插入。
b） 位置i是否合法。
c） an，ai依次后移。
d） x插入。
e） n值加1
算法实现：c++描述（函数）
templat
void list::insert（int i， int x）
int j；
if （length>=maxsize） throw“表满，不能插入”；
if (i<1||i>length+1) throw“插入位置不合法”；
for (j=length-1;j>=i-1;j--)
data[j+1]=data[j]; 元素后移。
r[i]=x; /元素插入。
length++;表长增1
算法效率：表长为n的顺序表，i位置插入数据，需要（n-i+1）个元素后移。
等概率插入条件下，平均移动元素的次数。
∑pimi=1/(n+1)(n+(n-1)+…1+0)=n/2
即：算法的平均时间复杂度为o(n);
2） 删除：已知表中n个元素已经存在，实现在表的i位置删除。
略。3）逆置：将表中元素反向存储。
template
void list::reverse（）
int low,high;
low=0;
high=length-1;
while(low
1、定义：用物理（内存）地址任意的存储单元存储逻辑相邻的元素，元素间的逻辑关系通过各个结点的指针信息来体现。
2、c++存储实现（以单向链表为例）
结点结构如下(c++结构类型)：
其中data存储元素信息，next存储逻辑关系的后继结点地址。
first为头指针，用来指示头结点地址。
结点（结构类型）的c++描述：
template
struct node
t data；//data存储元素信息。
node *next；//next存储逻辑关系的后继结点地址。
4、 算法设计举例。
1） 链表的遍历：按逻辑次序依次输出表中元素。
template
void linklist::visit( )
node *p;
p=first->next;
while(p!=null)
cout p=p->next; 2） 链表插入(在非递增有序表中插入元素x，使序列仍然有序) 算法基本思想： a） 查找插入位置*p（在其后插入） b） 插入x template void linklist::insert(t x) node *p,*s; p=first; while(p->next &&p->next->data>=x) p=p->next; /查找插入位置。 s= new node; /为x元素申请结点空间。 s->data=x; s->next=p->next; /在结点*p后插入结点*s p->next=s; 引申：有序链表的构造(删除) template void linklist::create( ) int n=10; for(int i=1;i<=n;i++) 3） 逆置算法：将表中元素逆序存储。 template void linklist::reverse( ) node*p,*s; p=first->next; first->next=null;//拆开。 while(p!=null) 4） 假设链表元素为正整型，删除所有偶数。 思考：设表中元素为字符，删除所有元素值为大写字母的结点。 template void linklist::delete( ) if(s1)//s1中剩余一些大的结点。 rear->next=s1; /链接表尾。 elserear->next=s2; 7）完整的程序示例。 #include using namespace std; template struct node t data; /data存储元素信息。 node *next; /next存储逻辑关系的后继结点地址。 template class linklist public: linklist() 构造仅有头结点的空表。 void visit(); void insert(t x); void delete(); void create(); 一 简单题 1 在单链表中，头结点是必不可少的？2 链队列q为空的条件是什么？3 如果一个二叉树中没有度为1的结点，它是不是完全二叉树？4 具有n个顶点和n 1条边的无向连通图是否存在环路？5 判断一个有向图是否存在回路的方法有哪些？6 在一棵二叉排序树t中，先插入结点n，然后再删除结点n，得到的新... 下面我们来解析一下知识点。线性表这一章里面的知识点不多，但要做到深刻理解，能够应用相关知识点解决实际问题。链表上插入 删除节点时的指针操作是选择题的一个常考点，诸如双向链表等一些相对复杂的链表上的操作也是可以出现在综合应用题当中的。栈 队列和数组可以考查的知识点相比链表来说要多一些。最基本的，是栈与... 2011级数据结构大作业。1 公园导游图。给出一张某公园的导游图，用图的顶点表示各个景点 景点个数大于等于30 每个景点有属性值 h，t，c 其中h表示游览完成这个顶点给游客带来的happiness，t表示游览这个景点需要的时间，c表示游览这个景点需要的费用，顶点之间的边表示路径 边具有属性值w，表...数据结构2019辅导
2019数据结构
数据结构2019级数据结构大作业