文档介绍：word
word
2 / 35
word
数据结构与算法设计知识点
试题类型：
本课程为考试科目〔闭卷笔试〕，试题类型包括：概念填空题〔10 %〕，是非判断题〔10 %〕，单项选择题〔40 %〕，算法填空题〔10%〕，算法应用结点的单链表的根本操作〔结点的插入与删除运算〕，了解单向循环链表和双向链表存储表示方法。
单链表：用一组地址任意的存储单元存放线性表中的数据元素。
以元素(数据元素的映象) + 指针(指示后继元素存储位置) = 结点
(表示数据元素 或 数据元素的映象)
单链表是一种顺序存取的结构，求以此为存储表示的线性表长度，可设置一个计数器
3、了解有序线性表的特点〔顺序有序表、有序链表〕。
有序线性表：线性表中的数据元素相互之间可以比拟，并且数据元素在线性表中
word
word
6 / 35
word
依值非递减或非递增有序排列，即 ai≥ai-1或 ai≤ai-1(i = 2,3,…, n)，如此称该线性表为有序表(Ordered List)
4、学会对线性表设计相关的算法进展相应的处理。
第三章 排序
重点内容与要求：
1、掌握对顺序表数据记录进展排序的根本思路和常规操作〔比拟、移动〕，了解排序算法的稳定性问题。
2、掌握简单项选择择排序、直接插入排序、冒泡排序算法，了解各种排序算法的特点与时间复杂度。
排序：将一组“无序〞的记录序列按某一关键字调整为“有序〞的记录序列。
假如整个排序过程不需要访问外存便能完成，如此称此类排序问题为内部排序；反之如此为外部排序。
选择排序：从记录的无序子序列中“选择〞关键字最小或最大的记录，并将它参加到有序子序列中，以此方法增加记录的有序子序列的长度
根本代码如下
for(i=0;i<n-1;i++)/*外循环控制趟数，n个数选n-1趟*/
{
k=i;/*假设当前趟的第一个数为最值,记在k中 */
for(j=i+1;j<n;j++)/*从下一个数到最后一个数之间找最值*/
if(a[k]<a[j])/*假如其后有比最值更大的*/
k=j;/*如此将其下标记在k中*/
if(k!=i)/*假如k不为最初的i值，说明在其后找到比其更大的数*/
{
t=a[k];a[k]=a[i];a[i]=t;}/*如此交换最值和当前序列的第一个数*/
}
插入排序：插入排序是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据。
word
word
6 / 35
word
代码如下：void InsertSort ( SqList &L) // 对顺序表L作插入排序
{
for ( i=2; i<=; ++i )
if ( [i].key < [i-1].key )
{
[0] = [i]; // 复制为哨兵
for ( j=i-1; [0].key < [j].key; --j )
[j+1] = [j]; // 记录后移
[j+1] = [0]; // 插入到正确位置
}
}
冒泡排序：泡排序是一种最直观的排序方法，在排序过程中，将相邻的记录的关键字进展比拟，假如前面记录的关键字大于后面记录的关键字，如此将它们交换，否如此不交换。或者反过来，使较大关键字的记录后移，像水中的气泡一样，较小的记录向前冒出，较大的记录
像石头沉入后部。故称此方法为冒泡排序法
代码如下：
void BubbleSort( SqList &L )
{ RcdType W；
i = ;
while (i >1) { // i>1 明确上一趟曾进展过记录的交换
lastExchangeIndex = 1;
for (j = 1; j < i; j++){
if ([j+1].key < [j].key) {
W=[j]；[j] =[j+1]；[j+1] = W； // 互换记录
lastExchangeIndex = j;
}
}
i