资源描述：
《2-基本数据结构1》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、ACM/ICPC程序设计基本数据结构及其在程序设计中的应用程序=数据结构+算法数据结构(DataStructure)是数据的计算机表示和相应的一组操作。算法(Algorithm)就是解决问题的方法或过程。基本数据结构线性结构非线性结构集合树结构图结构线性表栈队列串线性结构线性表:由n个元素组成的有限序列。每个元素有确定的前驱和后继。元素之间的关系仅限于前趋、后继关系表、栈、队列、串元素的存储方式数组链表线性结构由n个元素组成的有限序列。每个元素有确定的前驱和后继。表：不限制元素的插入和删除位置。有n+1个位置可
2、供插入，n个元素可供删除栈：插入和删除操作只允许在表尾进行队列：在表尾插入、在表头删除串：元素为字符的线性表，有求子串、子串定位、子串替换等操作(a1，a2，…，ai，…，an)表头元素表尾元素数组用一组连续的存储单元依次存储数据元素.表中任一元素可以随机存取.插入或删除一个元素需要移动其他元素.a1a2...aian...dai+1由下标确定数组元素a[i]：Loc(ai)=Loc(a1)+(i-1)*d(1≤i≤n)例如：由n个元素构成的一维数组a链表链式存储:任意存储单元存储元素链表结点包括数据域和指针域
3、插入或删除一个元素,只需修改结点指针域访问任一元素必须从链表头指针开始a2ai...a1ai+1...an...链表结点链式存储:任意存储单元存储元素链表结点包括数据域和指针域插入或删除一个元素,只需修改结点指针域访问任一元素必须从链表头指针开始数据data指针nextstructNode{ElemTypedata；//数据元素structNode*next；//指向后继结点的指针};单向链表线性表：(a1，a2，…，ai-1，ai，ai+1，…，an)(a)单向链表…a2a1an∧an-1…aiai-1ai+
4、1head头结点(b)带头结点的单向链表…a2a1an∧an-1…aiai-1ai+1head双向链表和循环链表线性表：(a1，a2，…，ai-1，ai，ai+1，…，an)head…a1∧a2an-1anai…∧(a)双向链表taila2a1anan-1…(b)循环单链表单链表的插入和删除链式存储:任意存储单元存储元素链表结点包括数据域和指针域插入或删除一个元素，只需修改结点指针域访问任一元素必须从链表头指针开始头结点带头结点的单向链表…a2a1an∧an-1…aiai-1ai+1head单链表中插入元素将元
5、素ai所在结点的地址赋给元素e结点的指针域：S->next=P->next;aiai-1…ai+1…PeS修改元素ai-1所在结点指针域的值：P->next=S;②①单链表中删除元素ai修改元素ai-1所在结点指针域的值：P->next=P->next->next;aiai-1…ai+1…P例1:UglyNumbersUglynumbersarenumberswhoseonlyprimefactorsare2,3or5.Thesequence1,2,3,4,5,6,8,9,10,12,15,...showsth
6、efirst11uglynumbers.Byconvention,1isincluded.Writeaprogramtofindandprintthe1500'thuglynumber.算法思路:一个正整数m可表示如下：m=(p1)j1*(p2)j2*…*(pn)jnUglynumber=2j1*3j2*5j3(j1,j2,j3>=0)在已知序列中,找一个最小的数,使得它乘以2比已知序列最后一个元素大;找一个最小的数,使得它乘以3比最后一个元素大;找一个最小的数,使得它乘以5比最后一个元素大.在这三个乘积中找最
7、小的添加到表尾,反复按此规则构造递增序列,直到表中有1500个元素。可以用数组预先分配1500个单元,也可以用链表动态分配.例2：TheBlocksProblem编号为0~n-1的n个木块，放在编号为0~n-1的n个格子里,可对它们进行四种有效的操作。01234n-1...InitialBlockWorldmoveaontob：先将a和b上的其他木块移回到它们的初始位置，然后将木块a摞在木块b上.moveaoverb：先将木块a上的其他木块移到它们的初始位置后，然后将木块a摞到包含了木块b的那一堆木块上面pil
8、eaontob：先将木块b上的所有木块移回到它们的初始位置，然后将木块a及其上的木块移到木块b上.pileaoverb：将包含木块a的那一摞木块移到包含了木块b的那一堆木块上面.moveaontob先将a和b上的其他木块移回到它们的初始位置，然后将木块a摞在木块b上.01234567890123456789Example:move3onto6012345678901234567893m
