数据结构复习资料.ppt

总复习
考试类型
选择题
填空题
简答题
编程题
绪论部分
数据结构中逻辑结构与物理结构的区别
时间复杂度
for (i=0;i<n;i++)
for(j=0;j<m;j++)
A[i][j]=0;
时间复杂度为O(m*n)。
线性表
线性表的特征
线性表的物理结构(存储):
顺序存储、链式存储
顺序存储与链式存储的区别
顺序存储:逻辑上相邻的数据元素,其物理上也相邻;
链式存储:逻辑上相邻的数据元素,其物理上不一定相邻;
顺序存储计算公式:
LOC(ai) = LOC(a1) + L *(i-1)
LOC(ai+1) = LOC(ai)+L
插入和删除需要移动大量元素
随机存取
每个元素由结点(Node)构成, 它至少包括两个
域:数据域Data和指针域Link
存储结构:链式存储结构
特点:存储单元可以不连续。
存取方式:顺序存取。
链表结构(重点)
data link
Node
存放数据元素值
直接前驱或直接后继结点的地址(指针)
链表结点插入和删除
插入和删除不需要移动大量元素
顺序存取
单链表的插入
在链表中插入一个元素的示意图如下:
x
s
b
a
p
a
b
p
插入步骤(即核心语句):
Step 1:s->next=p->next;
Step 2:p->next=s ;
p->next
s->next
元素x结点应预先生成:
S=(LinkList)malloc(m);
S->data=x;
S->next=p->next
单链表的删除
在链表中删除某元素的示意图如下:
c
a
b
p
删除步骤(即核心语句):
q = p->next; //保存b的指针,靠它才能指向c
p->next=q->next; //a、c两结点相连
free(q) ; //删除b结点,彻底释放
p->next
思考: 省略free(q)语句行不行?
(p->next) -> next
×
×
1、填空题:
1)在顺序表中插入和删除一个元素,需要平均移动
个元素,具体移动的元素个数与有关。
2)顺序表中逻辑上相邻的元素的物理位置紧邻。单链表中逻辑上相邻的元素的物理位置紧邻。
3)在单链表中,除了首元结点外,任一结点内的存储位置由指示。
4)在单链表中,设置头结点的作用是。