数据结构复习.ppt

1、审查审查审查审查，泛利信息通信工程部湖南工业大学第2020/7/17章，第2，1章概述，数据的基本逻辑结构(P3)线性表树图数据的存储结构(P3)顺序存储链接存储索引存储散列存储，非线性结构/顺序表指针int size/顺序表最大容量int length/顺序表中当前包含的元素数；Typedef struct list List，4，2-3章定线表格，插入和删除顺序表格(p18) intinsert (list * l，int x，int I)/顺序表格l的第一个位置在int j中插入x If(il-lent)for(j=L-length-1；j=I；j-)l-dataj 1=l-dataj；

2、/元素向后移动，第I个位置L-datai=x；/插入元素x l-长度；/表格元素数1 return 1，5，2-3章路线表，插入和删除顺序表(P18) int Remove(List* L，int i) /从顺序表L中删除第I个元素int j If(I=L-length |)for(j=I；j length-1；j)L-dataj=L-dataj 1；/元素向前l-长度-；/表元素数减去1 return 1，6，2-3章线性表，矢量顺序存储的随机访问(P20) add(j)=add(i) (j-i-1)*每个元素的空间大小示例：矢量第一个元素存储地址100，7插入(堆叠)的元素首先被删除(堆叠

3、)。示例：已知堆栈的堆栈顺序为第1、2、8、2-3章线性表，队列特性(P44)操作受限的线性表，插入删除操作仅在表的一端先进先出。也就是说，首先删除(出队)插入(入队)的元素。范例：已知伫列的排入伫列顺序为1，2。9、2-3章线性表、循环队列(P45)确保队列满时元素的数量为size-1，从而确保队列空，满的判断条件不相同。空： front=仅rear : front=(rear 1)，10，2-3章定线表格，已连接表格的性质(P61，P4)，11，2-3章定线表格，已连接表格的性质/后续节点指针int data/节点数据Typedef struct node Node，13，2-3章线性表，

4、链接表节点的结构(P62) struct node /节点结构struct node * next/后续节点指针int data/节点数据Typedef struct node Node示例：在附加了头节点的单个链接表中，链接表为空的条件是附加头节点的指针字段为_ _ _ _ _ _ _。14，2-3章线性表格，连结表格节点作业(P62) VoID Insertafter(节点* N，节点* P)/在节点N之后插入节点P-next=n /N/p删除节点* deleteafter(节点* p)/节点p(n的后续节点)的后续节点Node* ptr=p-next。/PRT p的后续节点if(ptr=

5、NULL) return NULL存储；/如果节点ptr为空，则返回空的p-next=ptr-next。/ptr的后续节点连接到P节点后返回ptr；15、2-3章线性表，双链接表的特征(P84)示例：在双链接表中，每个节点都有两个指针字段。一个指向前捕捉器，另一个指向_ _ _ _。16、5章排序、已排序分类(P102)、17、5章排序、已排序分类(P102)示例：快速排序属于_ _ _ _排序。典型的排序方法有五种：插入排序、排序选择、_ _ _ _ _ _、排序分配、合并排序。在以下排序方法中，稳定的是_ _ _ _ _ _。A.气泡排序b .选择排序c .快速排序d .对定位台阶排序，第

6、18、5章排序，直接插入排序(P103) 85、40、10、95、20、15、70列出每个排序的结果：40 15、20、70、查找第22、6章、散列祖怀(P134)中常见的散列函数余数法、平方法、随机乘数法、数字解析法、基数转换法等。常用冲突处理方法与开放地址方法相关联的列表地址方法是两大类别。查找第23、6章，散列祖怀(P137)示例：分别使用(线性检测)开放地址方法和(分离同义词)链地址方法，密钥代码54，77，94，89，14，45，76，24，7-8章树，完整的二进制示例：深度为n的完整二进制树包含总计_ _ _ _ _个节点。25，7-8章树，保存二叉树(P149)二叉树中的链接/二

7、叉树节点的结构声明(左右方法)type def struct tree _ node char data；Struct tree_node *left，* right节点；26，7-8章树，二叉树遍历(P154) /优先级(前面的顺序)是二叉树void preOrder(Node *t) if(t) if (t！=NULL) /与节点声明的成员类型匹配的printf (%c ，t-data)；preder(t-左)；preder(t-right)；27，7-8章树，二叉树遍历(P154) /中间顺序(对称顺序)是二叉树void inOrder(Node *t) if(t！=NULL)inOrd

8、er(t-left)；Printf(%c，t-data)；订购(t-right)；28，7-8章树，二叉树遍历(P154) /二叉树void postOrder(Node *t) if(t！=NULL)post order(t-left)；post order(t-right)；Printf(%c，t-data)；29，7-8章树，二进制树遍历(P154)示例：如果二进制树的顺序为wuvts，中间顺序为uwtvs，则二进制树的顺序为_ _ _ _ _ _。30，7-8章树，二进制树的所有节点x: x的左侧子树节点x的右侧子树节点示例：简要描述了辅助排序树的特征，并将节点插入顺序绘制为7，4，17，2，6。31、7-8章树、半甘露(P186)示例：指定外部节点集的权重3、15、7、9、20、16、25、11、28、20、32、具有n个顶点的全向图具有_ _ _ _ _个边。33，9章，保存地物(P201)示例：在无方向图的相邻矩阵A中，如果点I与点J连接边，则存在Ai，j=1。否则，Ai，j=_。如果有直接图形的邻接矩阵A，则图形有总计_ _ _ _ _个边。34，9章图，图遍历(P206)示例：创建以下图的宽度优先遍历序列(从顶点A开始逆时针搜索)，并绘制生成树。35、9章、图遍历(P227)示例、36、9章、图的最小生成树(P211)示例：简要介绍了