《数据结构辅导线性结构》由会员分享，可在线阅读，更多相关《数据结构辅导线性结构（15页珍藏版）》请在金锄头文库上搜索。
1、数据结构辅导201003A第一章绪论基本知识点：数据结构与算法的概念。重点：数据结构的逻辑结构、存储结构、数据运算三方面的概念及相互关系；算法时间复杂度分析。难点：分析算法的时间复杂度。知识要点：数据：在计算机科学中数据是指所有能输入到计算机中并被计算机处理的符号的总称。数据元素：数据的基本单位，是数据的一个元素。数据对象：性质相同的数据元素的集合，是数据的一个子集。数据结构：相互之间存在一种或多种特定关系的数据元素的集合，一般包括三个方面的内容，即数据的逻辑结构、存储结构和数据的运算。数据类型：一个值的集合和定义在这个值集上的一组运算的总称。数据结构是一门研究非数值计算的程序设计问题中计算机
2、的操作对象(数据元素)以及它们之间关系和操作(运算)的学科。数据的逻辑结构是指数据元素之间逻辑关系的整体。数据的存储结构是指数据结构在计算机内的表示。四种基本数据结构：集合、线性结构、树形结构、图结构。算法具有的五个基本特性是：有穷性、可行性、确定性、输入和输出。算法执行的时间是问题规模的函数。算法的时间复杂度是指，随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同时，则称该算法的时间复杂度为0(f(n)。算法的时间复杂度与问题的规模有关。例题：编写一个算法，求一个整数数组中的最大元素和最小元素，并指出该算法的时间复杂度。解：对应的算法如下：void MaxM in (i nt
3、a,i nt n, int &max, int &min)该算法求数组a0 n-1的最大元素 max和最小元素 min。 max= min=a0;for(i nt i=1 ;imax) max=ai;else if(aia1) max 仁a0 ;max2=a1 ;else max 仁 a1; max2=a0;for(i nt i=2;imax1)max2=max1; max1=ai;else if(aimax2) max2=ai;该算法的时间复杂度为0( n)。例题：编写一个算法，求一个整数数组中的最小元素和次小元素，并指出该算法的时间复杂度。解：对应的算法如下：void Min 12(i n
4、t a, i nt n, i nt &min 1, i nt &min2)该算法求数组 a0n-1的最小元素 min1和次小元素 min2。 if(a0a1) mi n1=a0; min 2=a1;else mi n仁 a1;mi n2=a0;for(i nt i=2;i=n _1;i+)if(aimi n1) mi n2=mi n1;mi n1=ai;else if(ai min2) min 2=ai;该算法的时间复杂度为O( n)。例题：选择题1、 数据结构是一门研究程序设计中数据的 以及它们之间的关系和运算等的学科。(A) 元素 (B)计算方法(C)逻辑存储(D)映像2、 在数据结构中，
5、从逻辑上可以把数据结构分为 两类。(A) 动态结构和静态结构(B) 紧凑结构和非紧凑结构(C) 线性结构的非线性结构(D) 内部结构和外部结构3、数据的逻辑结构是关系的整体。(A) 数据数据之间逻辑(B) 数据项之间逻辑(C) 数据类型之间(D) 存储结构4、 在链式存储结构中，一个存储结点存储一个 。(A) 数据项(B) 数据元素(C) 数据结构(D) 数据类型5、 数据结构在计算机内存中的表示是指 。(A) 数据的存储结构(B) 数据结构(C) 数据的逻辑结构(D) 数据元素之间的关系6、 在数据结构中，与所使用的计算机无关的是 。(A) 逻辑结构(B) 存储结构(C) 逻辑结构和存储结构
6、(D) 物理结构7、 数据采用链式存储结构时，要求 。(A) 每个结点占用一片连续的存储区域(B) 所有结点占用一片连续的存储区域(C) 结点的最后一个数据域是指针类型(D) 每个结点有多少个后继，就设多少个指针域8、算法的时间复杂度与有关。(A) 问题规模(B) 计算机硬件性能(C) 编译程序质量(D) 程序设计语言9、算法分析的目的是。(A) 找出数据结构的合理性(B) 研究算法中输入与输出的关系(C) 分析算法的效率以求改进(D) 分析算法的易读性和文档性10、 某算法的时间复杂度为0(n2)，表明该算法的 (A) 问题的规模是n2(B) 执行时间等于n2(C) 执行时间与n2成正比(D
7、) 问题规模与n2成正比第2章线性表基本知识点：线性表的逻辑结构特征，线性表的基本运算，线性表的两种存储结构，以及在 这两种存储结构下线性表的基本运算算法的实现，顺序表和链表的优缺点比较。重点：掌握线性表的定义和特点，线性表的存储结构；顺序表和链表的组织方法和算法设计。难点：单链表和双链表的各种算法设计。例题1、已知顺序表L,请设计一算法，在L的第i个位置插入x。解：存储结构如下：解:存储结构如下：typedef struct SqList ElemType *elem;in t le ngth;in t listsize;SqList;在顺序表L的第i个位置(下标为i-1)上插入x的算法如下
8、：void In sertSqList(SqList &L, int i, ElemType x)ElemType *p, *q;if(iL.length) return; / 插入位置不合法。p=&L.elemi-1; q=&L.elemL.le ngth-1;while(q=p) *(q+1)=*q; q-;/后移*p=x;/ 插入L.len gth+;例题2、已知顺序表L,请设计一个算法，删除L中所有值为x的结点。解：存储结构如下：typedef struct SqList ElemType *elem;in t le ngth;in t listsize;SqList;算法如下：voi
9、d DeleteAllx(SqList &L, ElemType x) int num=0;int i, j;i=0; j=0;while(j=0 & xL.elemk) L.elemk+1=L.elemk; k=k-1;L.elemk+1=x;L.len gth+;例题4、编写一个算法逆置顺序表。解：存储结构如下：typedef struct SqList ElemType *elem;in t le ngth;in t listsize;SqList;算法如下：void Reverse(SqList &L) ElemType *p, *q;p=&L.elem0; q=&L.elemL.le
10、 ngth-1;while(pvq) ElemType *temp=*p; *p=*q; *q=temp;例题5、编写一个算法，归并两个有序的顺序表。 解：存储结构如下：typedef struct SqList ElemType *elem;in t le ngth;in t listsize;SqList;算法如下：void MergeSqList(SqList & L1, SqList & L2, SqList & L3) int i, j, k; i=j=k=O;while(iL1.le ngth & jL2.le ngth)if(L1.elemi=L2.elemj) L3.elemk
11、+=L1.elemi+; else L3.elemk+=L2.elemj+;while(iL1.le ngth) L3.elemk+=L1.elemi+;while(j next;while(p) nu m+; p=p-n ext; return num;说明：，则算法如下:上面的算法中，若假设单链表是带头指针的(即不带头结点)int Nodes(Li nkList &H)int num=0;LNode *p=H;while(p) nu m+; p=p-n ext;return num;例题7、设有一个单链表 H，其数据元素按从小到大有序，设计一个算法, 值为x的结点，并保持其有序性。解：存储结构如下：typedef struct LNode ElemType data;struct LNode *n ext;LNode, *Li nkList;算法如下：(假设单链表是带头结点的)void In sertOrderLi nkList(Li nkList &H, ElemType x)LNode *n ewNode=new LNode; n ewNode-data=x;LNode *p=H- next;while(p-n ext & p-n ext-datan ext;n ewNode-n ext=p-n ext;
