数据结构讲义.doc
《数据结构讲义.doc》由会员分享,可在线阅读,更多相关《数据结构讲义.doc(34页珍藏版)》请在三一文库上搜索。
1、34【考查目标】 1. 理解数据结构的基本概念;掌握数据的逻辑结构、存储结构及其差异,以及各种基本操作的实现。 2. 掌握基本的数据处理原理和方法的基础上,能够对算法进行设计与分析。 3. 能够选择合适的数据结构和方法进行问题求解。 一、线性表大纲要求:(一) 线性表的定义和基本操作 (二) 线性表的实现 1. 顺序存储结构 2. 链式存储结构 3. 线性表的应用 知识点:1 深刻理解数据结构的概念,掌握数据结构的“三要素”:逻辑结构、物理(存储)结构及在这种结构上所定义的操作“运算”。2 时间复杂度和空间复杂度的定义,常用计算语句频度来估算算法的时间复杂度。以下六种计算算法时间的多项式是最常
2、用的。其关系为:O(1)O(logn)O(n)O(nlogn) O(n2)O(n3)指数时间的关系为: O(2n)O(n!)link=plink;plink=sBqlink=s;slink=pCplink=slink;slink=pDplink=s;slink=q10. 在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为( B )。AO(n) BO(1) CO(n2) DO(log2n)11. 表长为n的顺序存储的线性表,当在任何位置上插入一个元素的概率相等时,插入一个元素所需移动元素的平均个数为( B )An B. n/2C. (n-1)/2 D. (n+1)/212. 循环链表的
3、主要优点是( D )A不再需要头指针了。B已知某个结点的位置后,能很容易找到它的直接前驱结点。C在进行删除操作后,能保证链表不断开。D从表中任一结点出发都能遍历整个链表。(二)应用题1、按增长率由小至大排列以下7个函数。答:2、数据的存储结构由哪四种基本的存储方法实现,并做以简要说明?答:四种表示方法(1)顺序存储方式。数据元素顺序存放,每个存储结点只含一个元素。存储位置反映数据元素间的逻辑关系。存储密度大,但有些操作(如插入、删除)效率较差。(2)链式存储方式。每个存储结点除包含数据元素信息外还包含一组(至少一个)指针。指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续,便于动态操作(
4、如插入、删除等),但存储空间开销大(用于指针),另外不能折半查找等。(3)索引存储方式。除数据元素存储在一地址连续的内存空间外,尚需建立一个索引表,索引表中索引指示存储结点的存储位置(下标)或存储区间端点(下标),兼有静态和动态特性。(4)散列存储方式。通过散列函数和解决冲突的方法,将关键字散列在连续的有限的地址空间内,并将散列函数的值解释成关键字所在元素的存储地址,这种存储方式称为散列存储。其特点是存取速度快,只能按关键字随机存取,不能顺序存取,也不能折半存取。3. 线性表有两种存储结构:一是顺序表,二是链表。试问:(1)如果有 n个线性表同时并存,并且在处理过程中各表的长度会动态变化,线性
5、表的总数也会自动地改变。在此情况下,应选用哪种存储结构? 为什么?(2)若线性表的总数基本稳定,且很少进行插入和删除,但要求以最快的速度存取线性表中的元素,那么应采用哪种存储结构?为什么? 答:(1)选链式存储结构。它可动态申请内存空间,不受表长度(即表中元素个数)的影响,插入、删除时间复杂度为O(1)。(2)选顺序存储结构。顺序表可以随机存取,时间复杂度为O(1)。(三)算法设计题1设计算法,求带表头的单循环链表的表长。解:int length(Linklist L) int I; listnode *p; I=0; P=L; while (p-next!=L) p=p-next; I+;
6、return I;2.已知单链表L,写一算法,删除其重复结点。算法思路:用指针p指向第一个数据结点,从它的后继结点开始到表的结束,找与其值相同的结点并删除之;p指向下一个;依此类推,p指向最后结点时算法结束。算法如下:解:void pur_LinkList(LinkList H) LNode *p,*q,*r; p=H-next; /*p指向第一个结点*/ if(p=NULL) return; while (p-next) q=p; while (q-next) /* 从*p的后继开始找重复结点*/ if (q-next-data=p-data) r=q-next; /*找到重复结点,用r指向
7、,删除*r */ q-next=r-next; free(r); /*if*/ else q=q-next; /*while(q-next)*/ p=p-next; /*p指向下一个,继续*/ /*while(p-next)*/该算法的时间性能为O(n2)。3.已知指针la和lb分别指向两个无头结点的单链表中的首结点。请编写函数完成从表la中删除自第i个元素开始的共len个元素并将它们插入到表lb中第j个元素之前,若lb中只有j-1个元素,则插在表尾。函数原型如下:int DeleteAndInsertSub(LinkList &la,LinkList &lb,int i,int j,int
8、len);答:int DeleteAndInsertSub(LinkList &la,LinkList &lb,int i,int j,int len)int k; LinkList p,q,prev,s;if(i0|j0|len0)return -1;p=la;k=1;prev=NULL;while(p&knext;k+;if(!p)return -1;q=p;k=1;while(q&knext;k+;if(!q)return -1;if(!prev)la=q-next;elseprev-next=q-next;if(j=1)q-next=lb;lb=q;elses=lb;k=1;while
9、(s&knext;k+;if(!s)return -1;q-next=s-next;s-next=p;return 1;4写一算法,将一带有头结点的单链表就地逆置,即要求逆置在原链表上进行,不允许重新构造新链表。图 单链表的倒置254525187629L297625184525L(a)(b)函数原型如下:void LinkList_reverse(LinkList &L);答:void LinkList_reverse(LinkList &L)LinkList p,q,s;p=L-next;q=p-next;s=q-next;p-next=NULL;while(s-next)q-next=p;
10、p=q;q=s;s=s-next;q-next=p;s-next=q;L-next=s;5写一算法,将带有头结点的非空单链表中数据域值最小的那个结点移到链表的最前面。要求:不得额外申请新的链结点。函数原型如下:void delinsert(LinkList &L);答:void delinsert(LinkList &L)p=L-next;/p是链表的工作指针pre=L;/pre指向链表中数据域最小值结点的前驱q=p;/q指向数据域最小值结点,初始假定是第一结点while(p-next!=NULL)if(p-next-datadata)/找到新的最小值结点pre=p;q=p-next; p=p
11、-next;if(q!=L-next)/若最小值是第一元素结点,则不需再操作pre-next=q-next;/将最小值结点从链表上摘下q-next=L-next;/将q结点插到链表最前面L-next=q;6编写一个算法来交换单链表中指针P所指结点与其后继结点,HEAD是该链表的头指针,P指向该链表中某一结点。答:单链表中查找任何结点,都必须从头指针开始。本题要求将指针p所指结点与其后继结点交换,这不仅要求知道p结点,还应知道p的前驱结点。这样才能在p与其后继结点交换后,由原p结点的前驱来指向原p结点的后继结点。LinkedList Exchange(LinkedList HEAD,p) HEA
12、D是单链表头结点的指针,p是链表中的一个结点。本算法将p所指结点与其后继结点交换。q=head-next; q是工作指针,指向链表中当前待处理结点。pre=head; pre是前驱结点指针,指向q的前驱。while(q!=null & q!=p)pre=q;q=q-next; 未找到p结点,后移指针。if(p-next=null)printf(“p无后继结点n”); p是链表中最后一个结点,无后继。Else 处理p和后继结点交换 q=p-next; 暂存p的后继。 pre-next=q; p前驱结点的后继指向p的后继。 p-next=q-next;p的后继指向原p后继的后继。 q-next=p
13、 ;原p后继的后继指针指向p。 算法结束。7已知线性链表第一个链结点指针为list,请写一算法,将该链表分解为两个带有头结点的循环链表,并将两个循环链表的长度分别存放在各自头结点的数据域中。其中,线性表中序号为偶数的元素分解到第一个循环链表中,序号为奇数的元素分解到第二个循环链表中。答:算法如下:void split(ListNode *List, ListNode *&list1, ListNode *&list2)list1=(ListNode *)malloc(sizeof(ListNode );list2=(ListNode *)malloc(sizeof(ListNode );p=l
14、ist;;q=list1;r=list2;len1=0;len2=0;mark=1;while (p!=null)if(mark=1)q-next=p;q=q-next;len1+;mark=2;elser-next=p;r=r-next;len2+;mark=1;list1-data=len1;list2-data=len2;q-next=list1;r-next=list2;8. 设A和B是两个单链表,其表中元素递增有序。试写一算法将A和B归并成一个按元素值递减有序的单链表C,并要求辅助空间为O(1)。答:Linklist merge(Linklist A,Linklist B)Linkl
15、ist C;Listnode *p;C=null;while (A&B) if(A-datadata) p=A-next;A-next=C;C=A;A=p; else p=B-next;B-next=C;C=B;B=p; if (A)while(A) p=A-next;A-next=C;C=A;A=p; else while(B) p=B-next;B-next=C;C=B;B=p;return C;二、栈、队列和数组大纲要求:(一) 栈和队列的基本概念 (二) 栈和队列的顺序存储结构 (三) 栈和队列的链式存储结构 (四) 栈和队列的应用 (五) 特殊矩阵的压缩存储 知识点:1 栈、队列的定
16、义及其相关数据结构的概念,包括:顺序栈、链栈、循环队列、链队列等。栈与队列存取数据(请注意包括:存和取两部分)的特点。2 掌握顺序栈和链栈上的进栈和退栈的算法,并弄清栈空和栈满的条件。注意因栈在一端操作,故通常链栈不设头结点。3 如何将中缀表达式转换成前缀、后缀表达式,了解对两种表达式求值的方法。4 栈与递归的关系。用递归解决的几类问题:问题的定义是递归的,数据结构是递归的,以及问题的解法是递归的。掌握典型问题的算法以及将递归算法转换为非递归算法,如n!阶乘问题,fib数列问题,hanoi问题。了解在数值表达式的求解、括号的配对等问题中应用栈的工作原理。5 掌握在链队列上实现入队和出队的算法。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 讲义
链接地址:https://www.31doc.com/p-5185791.html