《电子科大820数据结构考纲考点归纳》由会员分享，可在线阅读，更多相关《电子科大820数据结构考纲考点归纳（41页珍藏版）》请在金锄头文库上搜索。
1、ch1. 数据结构及算法的相关概念和术语（1） 数据结构及算法的概念；数据：所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素：数据的基本单位，一个数据项可由若干个数据项组成。数据项：构成数据元素的不可分割的最小单位。* 关系：数据数据元素数据项数据对象：性质相同的数据元素的集合。数据类型：原子类型、结构类型、抽象数据类型。数据结构：相互之间存在一种或多种特定关系的数据元素的集合。（2）数据的逻辑结构和存储结构；数据结构三要素： 数据的逻辑结构、数据的存储结构、数据的运算数据的逻辑结构：线性结构（线性表）、非线性结构（集合、树和图）。数据的存储结构：顺序存储：优点：可以随机存取，每个
2、元素占用最少存储空间缺点：可能产生较多碎片现象链式存储：优点：不会出现碎片现象缺点：每个元素占用较多存储空间，只能实现顺序存储索引存储：优点：检索速度快缺点：增加了附加的索引表，会占用较多存储空间散列存储：优点：检索、增加和删除结点的操作都很快缺点：可能出现存储单元的冲突，解决冲突会增加时间和空间的开销（3）算法的定义及特性；算法：对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。算法的特性：有穷性、确定性、可行性、输入、输出算法设计的要求：正确性、可读性、健壮性、效率与低存储量需求* 同一个算法，实现语言的级别越高，执行效率就越低（4）算法时间复杂度和空间复
3、杂度的分析方法。时间复杂度：主要分析语句频度（一条语句在算法中被重复执行的次数）之和T(n)的数量级加法原则：T(n)=T1(n)+T2(n)=O(max(f(n),g(n)乘法原则：T(n)=T1(n)T2(n)=O(f(n)g(n)* 常见时间复杂度比较：O(1)O(n)O(nlogn)O(n2)O(n3)O(2n)O(n!)O(nn)空间复杂度：算法所耗费的存储空间，S(n)=O(g(n)算法原地工作是指算法所需辅助空间是常量，即O(1)ch2线性表（1）线性表的定义线性表：具有相同数据类型的n(n0)个数据元素的有限序列，一般表示如下：L=(a1, a2, , ai+1, , an)其
4、中，a1是唯一的“第一个”数据元素，称为表头元素；an是唯一的“最后一个”数据元素，称为表尾元素；除第一个元素外，每个元素有且仅有一个直接前趋；除最后一个元素外，每个元素有且仅有一个直接后继。线性表的特点：表中元素具有逻辑上的顺序性，表中元素都是数据元素，表中元素的数据类型都相同，表中元素具有抽象性。（2）线性表的基本操作及在顺序存储及链式存储上的实现；线性表的基本操作：InitList(&L) 构造一个空的线性表ListLength(L) 求表长，即求线性表中数据结点（如果是带头结点单链表，则不含头结点）的个数LocateElem(L, e) 按值查找GetElem(L, i) 按位查找Li
5、stInsert(&L, i, e) 在表L中的第i个位置插入指定元素ListDelete(&L, i, &e) 删除表L中的第i个位置的元素，并输出其值PrintList(L) 按前后顺序输出线性表L的所有元素值ListEmpty(L) 判空，若L为空表，返回TRUE，否则返回FALSEDestroyList(&L) 销毁线性表，并释放表L占用的内存空间ClearList(&L) 将L重置为空表PriorElem(L,cur_e,&pre_e) 若cur_e是表L的数据元素，且不是第一个，用pre_e返回其前驱NextElem(L,cur_e,&next_e) 若cur_e是表L的元素，且不
6、是最后一个，用next_e返回其后继ListTraverse(L,visit() 表的遍历，即依次对L的每个元素调用函数visit()线性表的顺序存储（顺序表）：线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间关系：LOC(ai+1)= LOC(ai)+l线性表的第i个数据元素ai的存储位置：LOC(ai)= LOC(a1)+(i-1)l顺序表的特点：可以进行随机存取，即通过首地址和元素序号可以在O(1)的时间内找到指定元素，但插入和删除元素操作需要移动大量元素顺序表结构的定义：顺序表的静态分配：#define MaxSize 50typede
7、f structElemType dataMaxSize;int length;SqList;顺序表的动态分配：#define InitSize 50typedef structElemType *data;int ListSize,length;SqList;* 动态分配语句：L.data=(ElemType *)malloc(sizeof(ElemType)*InitSize);顺序表基本操作的实现：初始化操作：构造一个空的顺序表LBOOL InitList_Sq(SqList &L)L.data=(ElemType *)malloc(InitSize*sizeof(ElemType);i
8、f(!L.data) exit(OVERFLOW);L.length=0;L.ListSize=InitSize;return TRUE;/InitList_Sq插入操作：在第i(1in)个元素之前插入一个元素，需将第n至第i(共n-i+1)个元素向后移动一个位置。BOOL ListInsert_Sq(SqList &L,int i,ElemType e)/在顺序表L中的第i个位置插入新元素e/i的合法值为1iL.length+1if(iL.length+1) return FALSE; /i值不合法if(L.length=ListSize) /当前存储空间已满，不能插入return FALS
9、E;for(i=L.length;j=i;j-) /将第i个位置及之后元素后移L.dataj=L.dataj-1;L.datai-1=e;/在位置i处放入eL.length+;/表长加1return TRUE;/ListInsert_Sq时间复杂度：最好情况：在表尾插入，无须移动元素，T(n)=O(1)最坏情况：在表头插入，需要移动第一个元素后面所有元素，T(n)=O(n)平均情况：T(n)=n/2=O(n)删除操作：在顺序表L中删除第i(1in)个元素，需将第n至第i(共n-i+1)个元素向前移动一个位置。BOOL ListDelete_Sq(SqList &L,int i,ElemType
10、 e)/在顺序表L中删除第i个元素，并用e返回其值/i的合法值为1iL.lengthif(iL.length) return FALSE; /i值不合法e=L.datai-1;for(int j=i;jL.length;j+)L.dataj-1=L.dataj;L.length-;return TRUE;/ListDelete_Sq时间复杂度T(n)：最好情况：删除表尾元素，无须移动元素，T(n)=O(1)最坏情况：删除表头元素，需要移动第一个元素后面所有元素，T(n)=O(n)平均情况：T(n)=(n-1)/2=O(n)按值查找（顺序查找）:int LocateElem(SqList L,i
11、nt i,ElamType e)/查找顺序表中值为e的元素，若查找成功，返回元素位序，否则返回0for(int i=0;iL.length;i+)if(L.datai=e) return i+1; /下标为i的元素值等于e，返回其位号i+1return 0;/LocateElem顺序表的归并：T(n)=O(La.length+Lb.length)void MergeList_Sq(SqList La, SqList Lb, SqList &Lc)/已知顺序表La和Lb的元素按值非递减排列/归并La和Lb得到新的顺序表Lc，Lc的元素也按值非递减排列pa=La.data;pb=Lb.data;L
12、c.ListSize=Lc.length=La.length+Lb.length;pc=Lc.data=(ElemType *)malloc(Lc.ListSize*sizeof(ElemType);if(!Lc.data) exit(OVERFLOW);pa_last=La.data+La.length-1;pb_last=Lb.data+Lb.length-1;while(pa=pa_last&pb=pb_last) /开始归并if(*pa=*pb) *pc+=*pa+;else *pc+=*pb+;while(pa=pa_last) *pc+=*pa+;while(pbnext=NULL; /初始为空表for(i=n;i0;i-)p=(LinkList)malloc(sizeof(LNode); /创建新结点scanf(&p-data);p-next=L-next;L-next=p;/将新结点插入表中/CreateList1_L单链表的建立2（尾插法）：时间复杂度O(n)void CreateList2_L(LinkList &L,int n)/从表头到表尾正向输入n个元素的值，建立带头结点的单链表L/每次均在表尾插入元素L=(LinkList)malloc(sizeof(LNode); /创建头结
