数据结构复习教材_第1页
数据结构复习教材_第2页
数据结构复习教材_第3页
数据结构复习教材_第4页
数据结构复习教材_第5页
已阅读5页,还剩91页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、数据结构复习201406第一章绪论基本知识点:数据结构与算法的概念。重点:数据结构的逻辑结构、存储结构、数据运算三方面的概念及相互关系;算法时间复杂度分析。难点:分析算法的时间复杂度。知识要点:数据:在计算机科学中数据是指所有能输入到计算机中并被计算机处理的符号的总称。数据元素:数据的基本单位,是数据的一个元素。数据对象:性质相同的数据元素的集合,是数据的一个子集。数据结构:相互之间存在一种或多种特定关系的数据元素的集合,一般包括三个方面的内容,即数据的逻辑结构、存储结构和数据的运算。数据类型:一个值的集合和定义在这个值集上的一组运算的总称。数据结构是一门研究非数值计算的程序设计问题中计算机的

2、操作对象(数据元素)以及它们之间关系和操作(运算)的学科。数据的逻辑结构是指数据元素之间逻辑关系的整体。数据的存储结构是指数据结构在计算机内的表示。四种基本数据结构:集合、线性结构、树形结构、图结构。算法具有的五个基本特性是:有穷性、可行性、确定性、输入和输出。算法执行的时间是问题规模的函数。算法的时间复杂度是指,随着问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同时,则称该算法的时间复杂度为O(f(n)。算法的时间复杂度与问题的规模有关。选择题部分:1、数据结构是一门研究程序设计中数据的_以及它们之间的关系和运算等的学科。(A) 元素 (B) 计算方法 (C) 逻辑存储 (D)

3、映像2、在数据结构中,从逻辑上可以把数据结构分为_两类。(A) 动态结构和静态结构(B) 紧凑结构和非紧凑结构(C) 线性结构的非线性结构(D) 内部结构和外部结构3、数据的逻辑结构是_关系的整体。(A) 数据之间逻辑(B) 数据项之间逻辑(C) 数据类型之间(D) 存储结构4、在链式存储结构中,一个存储结点存储一个_。(A) 数据项(B) 数据元素(C) 数据结构(D) 数据类型5、数据结构在计算机内存中的表示是指_。(A) 数据的存储结构(B) 数据结构(C) 数据的逻辑结构(D) 数据元素之间的关系6、在数据结构中,与所使用的计算机无关的是_。(A) 逻辑结构(B) 存储结构(C) 逻辑

4、结构和存储结构(D) 物理结构7、数据采用链式存储结构时,要求_。(A) 每个结点占用一片连续的存储区域(B) 所有结点占用一片连续的存储区域(C) 结点的最后一个数据域是指针类型(D) 每个结点有多少个后继,就设多少个指针域8、算法的时间复杂度与_有关。(A) 问题规模(B) 计算机硬件性能(C) 编译程序质量(D) 程序设计语言9、算法分析的目的是_。(A) 找出数据结构的合理性(B) 研究算法中输入与输出的关系(C) 分析算法的效率以求改进(D) 分析算法的易读性和文档性10、某算法的时间复杂度为O(n2),表明该算法的_。(A) 问题的规模是n2(B) 执行时间等于n2(C) 执行时间

5、与n2成正比(D) 问题规模与n2成正比11、在数据结构中,与所使用的计算机无关的是数据的_结构。(A) 逻辑 (B) 存储 (C) 逻辑和存储 (D) 物理12、在数据的存储结构中,一个存储结点存储一个_。(A) 数据项 (B) 数据元素 (C) 数据结构 (D) 数据类型 13、在数据结构中,与所使用的计算机无关的是_。(A)逻辑结构 (B)存储结构(C)物理结构 (D)逻辑结构与存储结构判断题:1、数据结构包含数据的逻辑结构、数据的存储结构以及数据集合上定义的运算。2、数据项是数据的最小单位。3、数据项是数据的最小单位。4、数据结构包含数据的逻辑结构、数据的存储结构以及数据集合上定义的运

6、算。5、数据的物理结构是指数据在计算机内实际的存储形式。6、算法的优劣与算法描述语言无关,但与所用计算机有关。应用题与算法设计题部分:例题:设计一个算法,求整数数组的最大元素。解:算法如下:void MaxElem(int a , int n, int &maxE) int k; maxE=a0;for(k=0;kn;k+) if(maxEak) maxE=ak;/注:maxE表示数组a 的前n个元素的最大元素。例题:设计一个算法,求整数数组的最小元素。解:算法如下:void MinElem(int a , int n, int &minE) int k; minE=a0;for(k=0;ka

7、k) minE=ak;/注:maxE表示数组a 的前n个元素的最大元素。例题:编写一个算法,求一个整数数组中的最大元素和最小元素,并指出该算法的时间复杂度。解:对应的算法如下:void MaxMin(int a,int n, int &max, int &min)/该算法求数组a0.n-1的最大元素max和最小元素min。 max=min=a0;for(int i=1;imax) max=ai;else if(aia1) max1=a0;max2=a1;else max1=a1; max2=a0;for(int i=2;imax1)max2=max1; max1=ai;else if(aima

8、x2) max2=ai;该算法的时间复杂度为O(n)。例题:编写一个算法,求一个整数数组中的最小元素和次小元素,并指出该算法的时间复杂度。解:对应的算法如下:void Min12(int a, int n, int &min1, int &min2)/该算法求数组a0n-1的最小元素min1和次小元素min2。 if(a0a1) min1=a0; min2=a1;else min1=a1;min2=a0;for(int i=2;i=n-1;i+)if(aimin1) min2=min1;min1=ai;else if(aimin2) min2=ai;该算法的时间复杂度为O(n)。例题:用C/C

9、+语言描述下列算法,并给出算法的时间复杂度。(1)求一个n阶方阵的所有元素之和。(2)对于输入的任意三个整数,将它们按照从小到大的顺序输出。(3)对于输入的任意n个整数,输出其中的最大和最小元素。解:(1)算法如下:int sum(int Ann, int n) int i, j, s=0;for(i=0;in;i+)for(j=0;jb) if(bc) coutcbc) coutbca;else coutbac;else if(ca) coutcab; else if(cb) coutacb; else coutabc;本算法的时间复杂度为O(1)。(3)算法如下:void maxmin(i

10、nt a, int n, int &max, int &min) int k; min=a0; max=a0;for(k=1;kmax) max=ak; else if(akmin) min=ak;本算法的时间复杂度为O(n)。例题:设n是3的倍数,分析以下算法的时间复杂度(需给出推导过程)。void fun(int n) int i, j, x, y; for(i=0; i=n;i+) if(3*i=n) for(j=3*i; jnext=p (B) p-next-next=p-next(C) p-next-next=p (D) p-next=p-next-next8、在一个长度为n的线性表

11、中顺序查找值为x的元素时,在等概率情况下,查找成功时的平均查找长度为_。(A) n (B) n/2 (C) (n+1)/2 (D) (n-1)/29、在一个长度为n的顺序表中,删除值为x的元素时需要比较元素和移动元素的总次数是_。(A) (n+1)/2 (B) n/2 (C) n (D) n+110、在一个顺序表的表尾插入一个元素的时间复杂度是_。(A) O(n) (B) O(1) (C) O(n2) (D) O(log2n)11、在一个顺序表的任何位置插入一个元素的时间复杂度是_。(A) O(n) (B) O(1) (C) O(n2) (D) O(log2n)12、在一个不带头结点(首结点为

12、*head)的单循环链表中,至少有一个结点的条件是_。(A) head!=NULL (B) head-next!=NULL(C) head=NULL (D) head-next=NULL13、在带头结点*head的循环单链表中,至少有一个结点的条件是_。(A) head-next!=NULL (B) head-next!=head(C) head=NULL (D) head-next=NULL(C) head-next=head (D) head!=NULL15、将两个长度为n的有序表归并为一有序表时,算法的时间复杂度是_。(A) O(1) (B) O(n) (C) O(n2) (D) O(l

13、og2n)16、在长度为n的顺序表,当在任何位置上插入一个元素的概率相等时,插入一个元素需要移动的元素的平均个数为( ) (A) n/2 (B)(n-1)/ 2 (C) (n+1)/2 (D) (n+2)/217、在长度为n的顺序表中,删除第i个元素(1in)需要向后移动( )个元素。 (A) n-i (B) n-i+1 (C) n-i-1 (D) i18、一个栈的入栈顺序是1、2、3、4、5,则此栈不可能的输出顺序为( )。(A) 5、4、3、2、1 (B) 4、5、3、2、1 (C) 4、3、5、1、2 (D)1、2、3、4、519、一个队列的入队序列是a,b,c,d,则队列的输出序列是(

14、 )。(A)dcba (B)abcd (C)adcb (D)cbda20、空串是指( )。 (A)空白串 (B)长度为零的串 (C)长度为1的串 (D)仅由空格组成的串21、在链式存储结构中,一个存储结点存储一个_。(A) 数据项 (B) 数据元素 (C) 数据结构 (D) 数据类型22、算法分析的目的是_。(A) 找出数据结构的合理性 (B)研究算法中输入和输出的关系(C)分析算法的效率以求改进 (D)分析算法的易读性和文档性23、一个队列的入队序列是abcd,则队列的输出序列是_。(A)dcba (B)abcd (C)adcb (D)cbda24、在表长为n的顺序表上做插入运算,平均要移动

15、的结点数为( )。 (A)n (B) n/2 (C) n/3 (D) n/425、在双链表某结点(己知其地址)前,插入一新结点,其所需时间是( )。 (A)O(1) (B) O(lgn) (C) O(n) (D) O(n2)26、设长度为n的链队列用单循环链表表示,若只设头指针,则出队操作的时间复杂度为( )。 (A) O(1) (B) O(lgn) (C) O(n) D O(n2)27、在表长为n的顺序表上做删除运算,在等概率的情况下,平均要移动的结点数为( )。 (A)n/2 (B) (n-1)/2 (C) n/3 (D) n/428、线性表( a1,a2,an)以链接方式存储时,访问第i

16、位置元素的时间复杂性为( )(A)O(i) (B)O(1) (C)O(n) (D)O(n/2)29、线性表的下列存储结构中,读取指定序号的元素花费的时间最少的是_。(A)单链表 (B)顺序表 (C)双链表 (D)循环链表30、线性表采用链式存储结构时,其地址_。(A) 必须是连续的 (B) 一定是不连续的(C) 部分地址必须是连续的 (D) 连续与否均可31、在线性表的下列存储结构中,读取指定序号的元素花费时间最少的是_。(A) 单链表 (B) 双链表 (C)循环链表 (D)顺序表32、 若某线性表中最常用的操作是提取第i个元素及找第i个元素的前驱元素,则采用( )存储方式最省时间。(A)单链

17、表 (B)双链表 (C)单向循环链表 (D)顺序表33、在长度为n的顺序表中,向第i个元素(1in+1)前插入一个元素需要向后移动( )个元素。 (A) n-i (B) n-i+1 (C) n-i-1 (D) i34、在一个单链表HL中,若要在指针q所指结点的后面插入一个由指针p所指向的结点,则执行( )。(A) q-next=p-next; p-next=q; (B) p-next=q-next; q=p;(C) p-next=p-next; q-next=q; (D) p-next=q-next; q-nxet=p;35、在表长为n的顺序表上做插入运算,平均要移动的结点数为( )。 (A)

18、n (B) n/2 (C) n/3 (D) n/436、在双链表某结点(己知其地址)前,插入一新结点,其所需时间是( )。 (A)O(1) (B) O(lgn) (C) O(n) (D) O(n2)37、在长度为n的顺序表中,当在任何位置插入一个元素的概率相等时,插入一个元素需要移动的元素的平均个数是_。(A)n/2 (B) (n-1)/2 (C) (n+1)/2 (D)(n+2)/238、 若某线性表中最常用的操作是提取第i个元素及找第i个元素的前驱元素,则采用( )存储方式最省时间。(A)单链表 (B)双链表 (C)单向循环链表 (D)顺序表49、在长度为n的顺序表中,向第i个元素(1in

19、+1)前插入一个元素需要向后移动( )个元素。 (A) n-i (B) n-i+1 (C) n-i-1 (D) i40、在一个单链表HL中,若要在指针q所指结点的后面插入一个由指针p所指向的结点,则执行( )。(A) q-next=p-next; p-next=q; (B) p-next=q-next; q=p;(C) p-next=p-next; q-next=q; (D) p-next=q-next; q-nxet=p;判断题:1、顺序查找方法只能在顺序存储结构上进行。2、线性表的顺序存储结构优于链式存储结构。3、对于单链表来说,只有从头结点开始才能扫描表中全部结点。4、对于单链表来说,只

20、有从头结点开始才能扫描表中全部结点。5、双向链表的特点是很容易找任何一个结点的前趋和后继。6、线性表的顺序存储结构优于链式存储结构。7、凡是为空的单链表都是不含任何结点的。8、向顺序表中插入一个元素,平均要移动大约一半的元素。9. 线性表采用链表方式和顺序表方式存储,执行插入和删除运算的时间复杂度都是O(n),因而两种存储方式的插入、删除运算所花费的时间相同。10、线性表采用链表方式和顺序表方式存储,执行插入和删除运算的时间复杂度都是O(n),因而两种存储方式的插入、删除运算所花费的时间相同。11、线性表采用链式存储时,结点和结点内部的存储空间可以是不连续的。 12、单链表中的头结点就是单链表

21、的第一个结点。13、在带头结点的单循环链表中,任何一个结点的后继结点的指针均非空。14、线性表采用链表方式和顺序表方式存储,执行插入和删除运算的时间复杂度都相同。15、分配给单链表的内存单元地址必须是连续的。16、双向链表的特点是很容易找任何一个结点的前趋和后继。17、线性表的顺序存储结构优于链式存储结构。18、对于单链表来说,只有从头结点开始才能扫描表中全部结点。19、线性表就是顺序表。20、线性表采用链表方式和顺序表方式存储,执行插入和删除运算的时间复杂度都是O(n),因而两种存储方式的插入、删除运算所花费的时间相同。21、在带头结点的单循环链表中,任一结点的后继指针均非空。22、线性表采

22、用链表方式和顺序表方式存储,执行插入和删除运算的时间复杂度都是O(n),因而两种存储方式的插入、删除运算所花费的时间相同。23、在带头结点的单循环链表中,任一结点的后继指针均非空。24、线性表采用链式存储时,结点和结点内部的存储空间可以是不连续的。填空题:1、单链表是 的链接存储表示。2、在有n个元素的顺序表中删除任意一个元素所需移动结点的平均次数是 。3、在双链表中,每个结点有两个指针域,一个指向 另一个指向 。4、在带有头结点的单链表L中,第一个元素结点的指针是 应用题与算法设计题部分:例题、叙述线性表的两种存储结构各自的主要特点。答:线性表的两种存储结构分别是顺序存储结构和链式存储结构。

23、顺序存储结构的主要特点是:(1)结点中只有自身的信息域,没有关联信息域。因此,顺序存储结构的存储密度大、存储空间利用率高。(2)通过计算地址直接访问任何数据元素,即可以随机访问。(3)插入和删除操作会引起大量元素的移动。链式存储结构的主要特点是:(1)结点除自身的信息域外,还有表示关联信息的指针域。因此,链式存储结构的存储密度小、存储空间利用率低。(2)在逻辑上相邻的结点在物理上不必相邻,因此,不可以随机存取,只能顺序存取。(3)插入和删除操作方便灵活,不必移动结点只需修改结点中的指针域即可。例题、已知顺序表L,请设计一算法,在L的第i个位置插入x。解:存储结构如下:typedef struc

24、t SqList ElemType *elem;int length;int listsize;SqList;在顺序表L的第i个位置(下标为i-1)上插入x的算法如下:void InsertSqList(SqList &L, int i, ElemType x)ElemType *p, *q;if(iL.length) return; /插入位置不合法。p=&L.elemi-1; q=&L.elemL.length-1;while(q=p) *(q+1)=*q; q-;后移*p=x;/插入L.length+;例题、已知顺序表L,请设计一个算法,删除L中所有值为x的结点。解:存储结构如下:typ

25、edef struct SqList ElemType *elem;int length;int listsize;SqList;算法如下:void 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.length+;例题、编写一个算法逆置顺序表。解:存储结构如下:typedef struct SqList ElemType *elem;int length;int listsize;SqList;算法

26、如下:void Reverse(SqList &L) ElemType *p, *q;p=&L.elem0; q=&L.elemL.length-1;while(pq) ElemType *temp=*p; *p=*q; *q=temp;例题:编写一个算法,在顺序表中统计值为x的数据元素的个数。例题:设计一个算法,将顺序表逆置。解:设顺序表的存储结构如下:typedef struct DataType dataMaxsize; int length;SeqList;算法如下:void Reverse(SeqList &L) int i=0, j=L.length-1; while(ij)Dat

27、aType temp=L.datai; L.datai=L.dataj;L.dataj=temp;i=i+1; j=j-1;例题:设计一个算法,将顺序表逆置。解:设顺序表的存储结构如下:typedef struct DataType dataMaxsize; int length;SeqList;算法如下:void Reverse(SeqList *L)int k; DataType temp;for(k=0;klength/2;k+)temp=L-datak; L-datak=L-dataL-length-1-k;L-dataL-length-1-k=temp;例题:设计算法,逆置单链表L。

28、例题:设计算法,逆置双链表L。例题:设计算法,逆置单循环链表L。例题:设计算法,逆置双循环链表L。例题、编写一个算法,在顺序表中统计值为x的数据元素的个数。解:存储结构如下:typedef struct SqList ElemType *elem;int length;int listsize;SqList;在顺序表中统计值为x的数据元素的个数的算法如下:int CountxSqList(SqList &L, ElemType x) int num=0; int i=0; while(i=L.length-1) if(L.elemi=x) num+; i+; return num;例题:编写一

29、个算法,在单链表L中统计值为x的数据元素的个数。例题:编写一个算法,在单循环链表L中统计值为x的数据元素的个数。例题:编写一个算法,在双向链表L中统计值为x的数据元素的个数。例题:编写一个算法,在双向循环链表L中统计值为x的数据元素的个数。例题、编写算法,在顺序表中删除所有值为x的数据元素。解:存储结构如下:typedef struct SqList ElemType *elem;int length;int listsize;SqList;在顺序表中删除所有值为x的数据元素的算法如下:void DeleteAllxSqList(SqList &L, ElemType x)int i=0,j=

30、0;while(j=L.length-1) if(L.elemj!=x) L.elemi+=L.elemj; j+;L.length=i;例题、编写算法,在单链表L中删除所有值为x的数据元素。例题、编写算法,在双向链表L中删除所有值为x的数据元素。例题、编写算法,在单向循环链表L中删除所有值为x的数据元素。例题、编写算法,在双向循环链表L中删除所有值为x的数据元素。例题、编写算法,在顺序表中删除重复多余的值(每个值只保留一个)。解:存储结构如下:typedef struct SqList ElemType *elem;int length;int listsize;SqList;在顺序表中删除

31、重复多余的值的算法如下:void DeleteOtherxSqList(SqList &L) int i,j,k;i=0;while(iL.length-1)j=i+1;while(j=L.length-1) if(L.elemj=L.elemi)for(k=j; kL.length-1; k+) L.elemk=L.elemk+1; L.length-;else j+;i+;例题、编写一个算法,归并两个有序的顺序表。解:存储结构如下:typedef struct SqList ElemType *elem;int length;int listsize;SqList;算法如下:void Me

32、rgeSqList(SqList &L1, SqList &L2, SqList &L3) int i, j, k; i=j=k=0;while(iL1.length & jL2.length)if(L1.elemi=L2.elemj) L3.elemk+=L1.elemi+;else L3.elemk+=L2.elemj+;while(iL1.length) L3.elemk+=L1.elemi+;while(jnext;while(p) num+; p=p-next; return num;说明:上面的算法中,若假设单链表是带头指针的(即不带头结点),则算法如下:int Nodes(Lin

33、kList &H)int num=0; LNode *p=H;while(p)num+; p=p-next;return num;例题、设计算法,统计单链表L中元素的个数。例题、设计算法,统计双向链表L中元素的个数。例题、设计算法,统计单向循环链表L中元素的个数。例题、设计算法,统计双向循环链表L中元素的个数。例题:设L是带头结点的单链表,k为正整数,设计算法求L的倒数第k个结点。例题、设有一个单链表H,其数据元素按从小到大有序,设计一个算法,在H中插入一个值为x的结点,并保持其有序性。解:存储结构如下:typedef struct LNode ElemType data; struct LN

34、ode *next;LNode, *LinkList;算法如下:(假设单链表是带头结点的)void InsertOrderLinkList(LinkList &H, ElemType x)LNode *newNode=new LNode; newNode-data=x;LNode *p=H-next;while(p-next & p-next-datanext;newNode-next=p-next;p-next=newNode;例题、设计算法,在单链表H中删除所有值为x的结点。解:存储结构如下:typedef struct LNode ElemType data; struct LNode

35、*next;LNode, *LinkList;算法如下:(假设单链表是带头结点的)void DeleteAllx(LinkList &H, ElemType x) LNode *p, *s;p=H;while(p-next)if(p-next-data=x) s=p-next; p-next=s-next; delete s;else p=p-next;例题、假设不带头结点单链表H中有重复的数据域,设计算法,删除H中重复的数据域,即相同数据域的结点只剩一个。解:存储结构如下:typedef struct LNode ElemType data; struct LNode *next;LNode

36、, *LinkList;算法如下:void DeleteToSingle(LinkList &H) LNode *pre, *p, *pnext, *s;pre=H; while(pre) p=pre; while(p) if(p-next & p-next-data=pre-data) s=p-next; p-next=s-next; delete s;else p=p-next;pre=pre-next;例题、编写算法,在带头结点的单链表中删除重复多余的值(每个值只保留一个)。解:存储结构如下:typedef struct LNode ElemType data; struct LNode

37、 *next;LNode, *LinkList;算法如下:在带头结点的单链表中删除重复多余的值的算法如下:void DeleteOtherxLinkList(LinkList &L) LNode *pre,*p, *pn, *s;p=L-next;while(p)pre=p; pn=p-next; while(pn) if(pn-data=p-data) pre-next=pn-next; delete pn; pn=pre-next; else pre=pn; pn=pn-next; p=p-next; 例题:设计算法,判断顺序表L的数据域是否递增的。例题:设计算法,判断单链表L的数据域是否

38、递增的。例题:设计算法,判断双向链表L的数据域是否递增的。例题:设计算法,判断单向循环链表L的数据域是否递增的。例题:设计算法,判断双向循环链表L的数据域是否递增的。例题、判断带头结点的单链表H的数据域是否是递增的。解:存储结构如下:typedef struct LNode ElemType data; struct LNode *next;LNode, *LinkList;算法如下:int IsIncrease(LinkList &H)LNode *p, *pnext;p=H-next;if(!p | !p-next) return 0;while(p & p-next) if(p-data

39、p-next-data) return 0;else p=p-next;return 1;例题、编写一个算法,逆置带头结点的单链表。解:存储结构如下:typedef struct LNode ElemType data; struct LNode *next;LNode, *LinkList;算法如下:void Reverse(LinkList &H)LNode *p, *q;p=H-next;H-next=0;while(p) q=p; p=p-next; q-next=H-next; H-next=q;例题:试写一个算法,求带头结点的单链表L中所有结点的数据之和。例题:设计一个算法,求带头

40、结点的单链表的结点个数。解:设带头结点的单链表的存储结构如下:typedef struct nodeDataType data; node *next;LinkNode, *LinkList;算法如下:int Nodes(LinkList L)int num=0; LinkNode *p=L-next;while(p)num+; p=p-next;return num;例题:设计一个算法判断带头结点的单链表L是否是按值递增的。例题:在线性表的如下链表存储结构中,若未知链表头结点的指针,仅已知p指针指向的结点,能否将它从该结构中删除?为什么?(1)单链表;(2)双链表;(3)循环链表。答:(1)

41、不能删除。因为无法知道*p结点的前趋结点的地址。(2)能删除。由*p结点的左指针找到其前趋结点的地址,然后实施删除。(3)能删除。循环查找一周,可以找到*p结点的前趋结点的地址,然后实施删除。例题:已知长度为n的线性表A采用顺序存储结构,编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法,该算法删除线性表中所有值为item的数据元素。解:存储结构如下:typedef struct SeqList ElemTyep *elem;int length;int ListSize;SeqList; 用k记录顺序表A中等于item的元素个数,边扫描A边统计k,并将不为item的元素向前移动k个位置

42、,最后修改A的长度。算法如下:void DeleteNode(SeqList &A, ElemType item) int k=0, i=0;while(inext;A=C; A-next=0; B=new LNode; B-next=0; pa=A; pb=B;while(p) s=p-next; pa-next=p; pa=p; p=s; s=s-next;if(p) pb-next=p; pb=p; p=s; s=s-next;pa-next=0; pb-next=0;C=0; /C已经被拆分,拆分后不再存在。/A和B采用尾插法建立。例题:设计一个算法,将x插入一个有序(从小到大排序)的线性表(顺序存储结构)的适当位置上,并保持线性表的有序性。解:设存储结构如下:typedef struct SeqListElemType *elem;int length;int ListSize;SeqLi

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论