河南住房和城乡建设厅一体化平台网站,莱芜金点子最新招工招聘启事,作文素材网站,网站正在升级建设中源码考纲
(一)数据结构部分;
线性表栈、队列、数组查找和内部排序树和图
(二)计算机算法设计部分:
递归与分省策路、回溯法贪心算法、分支限界法、动态规划算法设计中的数据结构运用
(三)程序设计基础(C或C)部分:
基本数据类型、各种运算符和表达式、基本控制结构。数组的定义… 考纲
(一)数据结构部分;
线性表栈、队列、数组查找和内部排序树和图
(二)计算机算法设计部分:
递归与分省策路、回溯法贪心算法、分支限界法、动态规划算法设计中的数据结构运用
(三)程序设计基础(C或C)部分:
基本数据类型、各种运算符和表达式、基本控制结构。数组的定义、数组元素的引用、数组的初始化掌握与字符串相关的库函数函数的定义语法函数调用中参数的传递机制:局部和全局变量的有效范围结构体类型变量的定义、引用、初始化方法结构体数组的定义、初始化和应用共同体变量的定义和使用方法。地址和指针的基本概念如何使用指针来处理数组、字符串以及结构体函数指针的基本概念以及使用。文件的定义以及对文件进行的各种操作的库函数。
数据结构
# 第二章 线性表 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.length0; //顺序表初始长度为0
)
静态分配在声明一个顺序表时就已为其分配了数组空间因此初始化时只需将顺序表的当前长度设为0。
//动态分配void Initlist(SeqList 6L){L.data(ElemType *)malloc(MaxSize*sizeof(ElemType));//分配存储空间L.length0; //顺序表初始长度为0L.MaxSizeInitsize; //初始存储容量
)
动态分配的初始化为顺序表分配一个预定义大小的数组空间并将顺序表的当前长度设为0。 MaxSize指示顺序表当前分配的存储空间大小一旦因插入元素而空间不足就进行再分配。
1.2.2插入操作O(n)
bool ListInsert(Sqlist l,int i,ElemType e)(if(i11liL.length1) //判断i的范围是否有效return false;if(L.lengthMaxSize) //当前存储空间已满不能插入return false;for(int jL.length;ji;j--) //将第1个元素及之后的元素后移L.data[j]L.data[j-1];L.data[i-1]e; //在位置i处放入eL.length; //线性表长度加1return true;
)
在顺序表L的第i(1iL.length1)个位置插入新元素e。若i的输入不合法则返回 false,表示插入失败否则将第i个元素及其后的所有元素依次往后移动一个位置腾出一个空位置插入新元素 e,顺序表长度增加1,插入成功返回 true。
1.2.3删除操作O(n)
bool ListDelete(SqList 6L,int i,ElemType 6e)(if(i1lliL.length) //判断i的范围是否有效return false;eL.data[i-1]; //将被删除的元素赋值给efor(int ji;jL.length;j) //将第1个位置后的元素前移L,data[j-1]L,data[j];L.length--; //线性表长度减1return true;
)
删除顺序表L中第i(1iL.length)个位置的元素用引用变量e返回。若i的输入不合法则返回false;否则将被删元素赋给引用变量e,并将第i1个元素及其后的所有元素依次往前移动一个位置返回true。
1.2.4查找操作按值查找O(n)
int LocateElem(SqList L,ElemType e)(int i;for(i0;iL.length;i)if(L.data[i]e)return i1; //下标为i的元素值等于e,返回其位序i1return 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个元素 ②顺序存储分配需要一段连续的存储空间不够灵活。
