文档介绍：数据结构
试卷结构与试题类型(100分), 占%70
单项选择题(4选1,10个) 20分
判断题(10个) 10分
填空题(10个,每空2分) 20分
简答题操作题(5个) 25分
算法填空(3个算法) 15分
读算法,说明功能(2个算法) 10分
知识点归纳:
算法基本特性:(有限时间)(算法确切)(存在基本操作)(0++)(1++)
(correctness)2. 可读性(readability)(Robustness)
数据结构研究数据之间的逻辑关系描述,称为数据的逻辑结构,强调从逻辑上来观察数据之间的关系,描述数据间的逻辑关系;
数据的存储结构是其逻辑结构在计算机存储器中的实现,研究数据的存储结构就是研究数据和数据之间关系的计算机表示。
抽象数据类型(AbstractDataType简称ADT)
是指一个数学模型以及定义在该模型上的一组操作;是对数据结构的一种更准确的抽象描述,忽略了数据结构的具体实现步骤,将注意力集中在数据的基本操作上,通过基本操作描述数据的逻辑关系。
顺序映象以相对固定的存储位置表示数据关系
链式映象用指示数据元素存储地址的指针(附加信息)表示数据元素间的逻辑关系
线性表是n个数据元素的有限序列, 通常记作(a1, a2, a3, …, an)
typedef struct { Status InitList_Sq(SqList &L){
ElemType *elem; //构造一个空的顺序表L
int length; =(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
int listsize; if (! ) exit(OVERFLOW); //存储分配失败
} SqList; L. length=0; //空表长度为0
=LIST_INIT_SIZE; //初始存储容量
Status DetroyList_Sq ( SqList &L) { Return OK;
If (!) return ERROR;} }//InitList_Sq
// 若表L不存在
free (); // 若表L已存在,回收动态分配的存储空间
= null; = 0; = 0;
return OK;
}// DetroyList_Sq
Status ListInsert_Sq(SqList &L, int i , ElemType e) {
//在顺序表L中第i个位置之前Insert新的元素e
if (i < 1 || i > +1) return ERROR; // i值不合法
if ( >= ) { // 当前存储空间已满,再分配、扩大空间
newbase = (ElemType *)realloc(, (+LISTINCREMENT)*sizeof (ElemType));
if (