文档介绍：2 / 36
数据结构与算法设计知识点
试题类型：
本课程为考试科目（闭卷笔试），试题类型包括：概念填空题（10 %），是非判断题（10 %），单项选择题（40 %），算法填空题（10%），算法应用题（20 %)，算法设计题（10 %单链表的基本操作（结点的插入与删除运算），了解单向循环链表和双向链表存储表示方法。
单链表：用一组地址任意的存储单元存放线性表中的数据元素。
以元素(数据元素的映象) + 指针(指示后继元素存储位置) = 结点
(表示数据元素 或 数据元素的映象)
单链表是一种顺序存取的结构，求以此为存储表示的线性表长度，可设置一个计数器
3、了解有序线性表的特点（顺序有序表、有序链表）。
有序线性表：线性表中的数据元素相互之间可以比较，并且数据元素在线性表中
6 / 36
依值非递减或非递增有序排列，即 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;}/*则交换最值和当前序列的第一个数*/
}
插入排序：插入排序是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据
6 / 36
。
代码如下：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 = lastExchangeIndex; // 一趟排序中无序序列