数据结构（学习版）

考纲

(一)数据结构部分;

1. 线性表
2. 栈、队列、数组
3. 查找和内部排序
4. 树和图

(二)计算机算法设计部分:

1. 递归与分省策路、回溯法
2. 贪心算法、分支限界法、动态规划
3. 算法设计中的数据结构运用

(三)程序设计基础(C或C++)部分:

1. 基本数据类型、各种运算符和表达式、基本控制结构。
2. 数组的定义、数组元素的引用、数组的初始化，掌握与字符串相关的库函数
3. 函数的定义语法，函数调用中参数的传递机制:局部和全局变量的有效范围
4. 结构体类型变量的定义、引用、初始化方法，结构体数组的定义、初始化和应用，共同体变量的定义和使用方法。
5. 地址和指针的基本概念，如何使用指针来处理数组、字符串以及结构体，函数指针的基本概念以及使用。
6. 文件的定义以及对文件进行的各种操作的库函数。

数据结构

# 第二章  线性表

1.顺序存储

1.1顺序表

顺序表的特点是表中元素的逻辑顺序与其存储的物理顺序相同。

1.1.1静态分配

#define MaxSize 50 //定义线性表的最大长度
typedef struct{ElemType data[MaxSize]; //顺序表的元素int length; //顺序表的当前长度
)SqList; //顺序表的类型定义

1.1.2动态分配

#define Initsize 100 //表长度的初始定义
typedef struct{ElemType *data; //指示动态分配数组的指针int MaxSize,length; //数组的最大容量和当前个数
)SeqList; //动态分配数组顺序表的类型定义

1.2顺序表的基本操作

1.2.1初始化操作

//静态分配//sqList L; //声明一个顺序表
void Initlist(SqList SL)(L.length=0; //顺序表初始长度为0
)

静态分配在声明一个顺序表时，就已为其分配了数组空间，因此初始化时只需将顺序表的当前长度设为0。

//动态分配void Initlist(SeqList 6L){L.data=(ElemType *)malloc(MaxSize*sizeof(ElemType));//分配存储空间L.length=0; //顺序表初始长度为0L.MaxSize=Initsize; //初始存储容量
)

动态分配的初始化为顺序表分配一个预定义大小的数组空间，并将顺序表的当前长度设为0。
MaxSize指示顺序表当前分配的存储空间大小，一旦因插入元素而空间不足，就进行再分配。
 

1.2.2插入操作O(n)

bool ListInsert(Sqlist &l,int i,ElemType e)(if(i<11li>L.length+1) //判断i的范围是否有效return false;if(L.length>=MaxSize) //当前存储空间已满，不能插入return false;for(int j=L.length;j>=i;j--) //将第1个元素及之后的元素后移L.data[j]=L.data[j-1];L.data[i-1]=e;        //在位置i处放入eL.length++;           //线性表长度加1return true;
)

在顺序表L的第i(1<=i<=L.length+1)个位置插入新元素e。若i的输入不合法，则返回 false,表示插入失败；否则，将第i个元素及其后的所有元素依次往后移动一个位置，腾出一个空位置插入新元素 e,顺序表长度增加1,插入成功，返回 true。
 

1.2.3删除操作O(n)

bool ListDelete(SqList 6L,int i,ElemType 6e)(if(i<1lli>L.length) //判断i的范围是否有效return false;e=L.data[i-1]; //将被删除的元素赋值给efor(int j=i;j<L.length;j++) //将第1个位置后的元素前移L,data[j-1]=L,data[j];L.length--;    //线性表长度减1return true;
)

删除顺序表L中第i(1<=i<=L.length)个位置的元素，用引用变量e返回。若i的输入不合法，则返回false;否则，将被删元素赋给引用变量e,并将第i+1个元素及其后的所有元素依次往前移动一个位置，返回true。

1.2.4查找操作（按值查找）O(n)

int LocateElem(SqList L,ElemType e)(int i;for(i=0;i<L.length;i++)if(L.data[i]==e)return i+1;     //下标为i的元素值等于e,返回其位序i+1return 0;               //退出循环，说明查找失败
)

2链式存储 

2.1单链表

2.1.1单链表初始化

2.1.2求表长操作

2.1.3按序号查找结点

2.1.4按值查找表结点

2.1.5插入结点操作

2.1.6删除节点操作

2.1.7头插法建立单链表

2.1.8尾插法建立单链表

3.1双链表

3.1.1插入操作

3.1.2删除操作

3.2循环链表

3.3静态列表

3.顺序表和链表的比较

顺序表的主要优点：
①可进行随机访问，即可通过首地址和元素序号可以在O(1)时间内找到
指定的元素；
②存储密度高，每个结点只存储数据元素。
顺序表的缺点也很明显：
①元素的插入和删除需要移动大量的元素，插入操作平均需要移动n/2个元素，删除操作平均需要移动(n-1)/2个元素；
②顺序存储分配需要一段连续的存储空间，不够灵活。