第一章 绪论1、数据结构是数据及其相互之间的联系2、数据结构按逻辑结构分类，可分为：集合、线性关系、树、图。按存储结构分类，可分为：顺序、链接、索引散列。3、数据结构的二元组表示由数据元素的集合D和D上二元关系S所组成。例1.1:D=（D，S），其中D=(1,2,3,4,5,6)S=(r)r=((1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6))请画出对应的数据结构。（这是图结构）注：在考试时可给出数据结构的二元组表示，做各种操作，如树、图的遍历，图的最小生成树或拓朴排序等。4、时间复杂度和空间复杂度。例1.2：请给出下列程序段的时间复杂度（S视为一个原操作）。(1)for (int i=0;i<n;i++)S;0(n)(2)for (int i=0;i<n;i++)for (int j=ij<n;j++)
第一章 绪论 1、数据结构是数据及其相互之间的联系。 2、数据结构按逡辑结构分类，可分为：集合、线性关系、树、图。 按存储结构分类，可分为：顺序、链接、索引、 散列。 3、数据结构的二元组表示由数据元素的集合 D 和 D 上二元关系 S 所组 成。 例 1.1：D=（D，S），其中 D={1,2,3,4,5,6} S={r} r={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5 ),(4,6)} 请画出对应的数据结构。（这是图结构） 注：在考试时可给出数据结构的二元组表示，做各种操作，如树、图的 遍历，图的最小生成树或拓朴排序等。 4、时间复杂度和空间复杂度。 例 1.2：请给出下列程序段的时间复杂度（S 视为一个原操作）。 (1)for (int i=0;i<n;i++) S; O(n) (2)for (int i=0;i<n;i++) for (int j=i;j<n;j++)
S;0(n2)例1.3:求(n2+nlog2n+1)/n的数量级是:O(n2)例1.4：结合具体的算法，求时间复杂度，如：顺序存储线性表，表元素插入的时间复杂度是：O(n）链接存储线性表，表结点插入的时间复杂度是：O(1)快速排序的时间复杂度是：O(n*log2n)5、课后习题：所有选择、填空题、计算题。第二章线性表1、线性表的定义和抽象数据类型描述：（掌握函数的功能）例2.1：请写出下列程序段执行完后的结果InitList(La);int a[]=[32,45,24,64,79,8,16)For (int i=0;i<7;i++)Insert(La,i,a[i]);Delete(La,a[3]/2);int x=GetElem(La,5);InsertRear(La,x);TraverseList(La);结果:4524 6479 8 16 8
S; O(n2 ) 例 1.3：求(n2+nlog2n+1)/n 的数量级是：O(n2 ) 例 1.4：结合具体的算法，求时间复杂度，如： 顺序存储线性表，表元素插入的时间复杂度是：O(n) 链接存储线性表，表结点插入的时间复杂度是：O(1) 快速排序的时间复杂度是：O(n*log2n) 5、课后习题：所有选择、填空题、计算题。 第二章 线性表 1、线性表的定义和抽象数据类型描述：（掌握函数的功能） 例 2.1：请写出下列程序段执行完后的结果。 InitList(La); int a[]={32,45,24,64,79,8,16}; For (int i=0;i<7;i++) Insert(La,i,a[i]); Delete(La,a[3]/2); int x=GetElem(La,5); InsertRear(La,x); TraverseList(La); 结果：45 24 64 79 8 16 8
注：这种题型注意书写格式，如果题目要求是“请写出下列程序段执行完后的线性表”则答案为“La=(45,24,64,79,8,16,8)”2、在顺序存储和链接存储结构下的线性表的插入、删除和单链表求长度函数的实现。（教材主要函数必须理解）顺序存储：判空：L.length==0判满：L.length==L.listsize链接存储：判空：HL==NULL3、几种特殊的单链表：数组存储单链表，附加表头结点单链表，循环链表。例2.2：在下列数组a中链接着一个线性表，表头指针为a[0].next，则该线性表为(38,56,25,60,42,74)。(注：注意书写格式)301245687a605642387425data6207next44、课后习题：所有选择、填空题和简答题第三章栈和队列1、栈的定义与基本操作运算：（建立栈、入栈、出栈、取栈顶元素等）注意顺序栈、链栈的指针变化
注：这种题型注意书写格式，如果题目要求是“请写出下列程序段执行 完后的线性表”，则答案为“La=(45,24,64,79,8,16,8)” 2、在顺序存储和链接存储结构下的线性表的插入、删除和单链表求长 度函数的实现。（教材主要函数必须理解） 顺序存储： 判空：L.length==0 判满：L.length==L.listsize 链接存储： 判空：HL==NULL 3、几种特殊的单链表：数组存储单链表，附加表头结点单链表，循环 链表。 例 2.2：在下列数组 a 中链接着一个线性表，表头指针为 a[0].next，则该线性表为 (38,56,25,60,42,74) 。(注：注意书写格式) a 0 1 2 3 4 5 6 7 8 data 60 56 42 38 74 25 next 4 3 7 6 2 0 1 4、课后习题：所有选择、填空题和简答题 第三章 栈和队列 1、栈的定义与基本操作运算：（建立栈、入栈、出栈、取栈顶元素等）， 注意顺序栈、链栈的指针变化
例4.1：请写出下列程序段执行后的结果。InitStack(a);int b[]=[5,17,24,18,32,9);for (int i=0; i<4; i++)push(a,b[i]);int x=pop(a)+32;push(a,x);while (IStackEmpty(a)cout<<pop(a)<<"“;结果：50241752、顺序存储和链接存储的出栈和入栈算法及相应的时间复杂度α1）顺序存储：判空：S.top==-1判满：S.top==StackMaxSize-1链接存储：判空：HS==NULL3、中缀算术表达式和后缀算术表达式的转化，及后缀算术表达式的求值。例4.2：将下列中缀算术表达式转化为后缀算术表达式，并求值。3+4/（25-（6+15））*8@
例 4.1：请写出下列程序段执行后的结果。 InitStack(a); int b[]={5,17,24,18,32,9}; for (int i=0 ; i<4 ; i++) push(a,b[i]); int x=pop(a)+32; push(a,x); while (!StackEmpty(a)) cout<<pop(a)<<” “; 结果：50 24 17 5 2、顺序存储和链接存储的出栈和入栈算法，及相应的时间复杂度 O（1）。 顺序存储： 判空：S.top==-1 判满：S.top==StackMaxSize-1 链接存储： 判空：HS==NULL 3、中缀算术表达式和后缀算术表达式的转化，及后缀算术表达式的求 值。 例 4.2：将下列中缀算术表达式转化为后缀算术表达式，并求 值。 3+4/（25-（6+15））*8 @
答案：3425615+-/8*+@值为11注：若表达式后有“@”符号，则转化后在表达式后也加上“@”"4、队列的定义与基本操作运算：（建立队列、入队、出队、循环队列等），注意队列头、尾指针变化例4.3：请写出下列程序段执行后的结果。InitQueue(q1);InitQueue(q2);inta[]=[41,67,34,0,69,24,78,58,62,64)for (int i=0 ; i<10 ; i++) (if (a[i]%2= = 1)QInsert(q1,x);else QInsert(q2,x);1while (!QueueEmpty(q1)&&!QueueEmpty(q2))cout<<Qdelete(q1)<<”"<<Qdelete(q2)<<endl;结果：413467069245、顺序存储和链接存储的出队和入队算法
答案： 3 4 25 6 15 + - / 8 * + @ 值为 11 注：若表达式后有“@”符号，则转化后在表达式后也加上 “@” 4、队列的定义与基本操作运算：（建立队列、入队、出队、循环队列 等），注意队列头、尾指针变化 例 4.3：请写出下列程序段执行后的结果。 InitQueue(q1); InitQueue(q2); int a[]={41,67,34,0,69,24,78,58,62,64}; for (int i=0 ; i<10 ; i++) { if (a[i]%2==1) QInsert(q1,x); else QInsert(q2,x); } while (!QueueEmpty(q1) && !QueueEmpty(q2)) cout<<Qdelete(q1)< <” “<<Qdelete(q2)<<endl; 结果：41 34 67 0 69 24 5、顺序存储和链接存储的出队和入队算法