《datastructurebysunli.ppt》由会员分享，可在线阅读，更多相关《datastructurebysunli.ppt（54页珍藏版）》请在三一文库上搜索。
1、数据结构与基本算法 Data Structures & Algorithm,孙立 多媒体通信实验室,提纲,基本数据结构与操作 字符串操作 常见算法,2019/9/1,2,ISP,常见数据结构与操作,链表,Struct ListNode int m_value; ListNode* p_Next; ; 1 随机访问元素 2 插入删除移动元素3 事先准备空间,2019/9/1,4,ISP,简单不常用 考察频繁 题型多变,链表,基本操作 1.头指针修改 int Insert(listnode *head) listnode *newnode; newnode = (listnode*) malloc
2、(sizeof(listnode); if(!newnode) return 0; newnode-next =head; head=newnode; return 1; ,2019/9/1,Software Architecture,5,链表,插入与删除 插入 head-p1-p2-p3-p4-p5.pn-NULL px Px-next=p2-next; p2-next=px 删除 head-p1-p2-p3-p4-p5.pn-NULL p-next=ptodelete p-next=ptodelete-next free(ptodelete) 插入和删除需要依赖该位置之前的指针,2019/
3、9/1,Software Architecture,6,链表,高级操作： 1 删除 O(1) 给定链表的头指针和一个结点指针，在O(1)时间删除该结点。链表结点的定义如下： 函数的声明如下： void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted) 偷梁换柱，暗渡陈仓,2019/9/1,7,ISP,2019/9/1,Software Architecture,8,head-p1-p2-p3-p4-p5.pn-NULL p4要删 ：p4已找到-删p4next ListNode* pNext = pToBeDeleted-m_pNex
4、t; pToBeDeleted-m_nKey = pNext-m_nKey; pToBeDeleted-m_pNext = pNext-m_pNext; / delete the node next to the pToBeDeleted delete pNext; pNext = NULL;,2019/9/1,Software Architecture,9,2 反转（输出） 输入一个链表的头结点，反转该链表，并返回反转后链表的头结点。 head-p1-p2-p3-p4-p5.pn-NULL Void func(Listnode* pHead) NULL-p1-p2-p3-p4-p5pn-he
5、ad pPrev pNode pNext pReversedHead;,2019/9/1,Software Architecture,10,ListNode* ReverseIteratively(ListNode* pHead) ListNode* pReversedHead = NULL; ListNode* pNode = pHead; ListNode* pPrev = NULL; while(pNode != NULL) ListNode* pNext = pNode-m_pNext; if(pNext = NULL) pReversedHead = pNode; / reverse
6、 the linkage between nodes pNode-m_pNext = pPrev; / move forward on the the list pPrev = pNode; pNode = pNext; return pReversedHead; ,2019/9/1,Software Architecture,11,3 链表相交（环） (阿里巴巴) 判断一个单向链表中是否有环的最佳方法是： A 两重遍历 B快慢指针C路径记录D哈希表辅助,这原来是个圈哦,2019/9/1,Software Architecture,12,While(pFast!=pSlow) pFast=pF
7、ast-next-next; pSlow=pSlow-next;,2019/9/1,Software Architecture,13,循环链表的入口点,head-p1-p2-p3-p4-p5.pn-pn1 | | pn4p1-p2-p3-p4-p5.pn-pn1 | | pn4-pn3-pn2,栈 队列 堆,栈： Stack(LIFO)： 队列： Queue（FIFO）： 堆： Heap,2019/9/1,14,ISP,2019/9/1,Software Architecture,15,栈的出栈顺序： 已知入栈顺序：1 2 3 4 5 6 下列不可能是出栈顺序： A 1 2 3 4 5 6 B
8、 2 3 4 1 5 6 C 5 6 4 3 2 1 D 1 5 4 6 2 3,栈 队列 堆,两个栈实现队列 template class CQueue public: CQueue() CQueue() void appendTail(const T,2019/9/1,16,ISP,2019/9/1,Software Architecture,17,思路 | | | | | | | | | a | | d | | b | | c | | c | | b | | d | tail | a | head,2019/9/1,Software Architecture,18,if(m_stack2
9、.size() 0) T 两个对列实现栈？,2019/9/1,Software Architecture,19,栈：min函数 最小的时间复杂度 一个辅助栈。每次push一个新元素的时候，同时将最小元素（或最小元素的位置。考虑到栈元素的类型可能是复杂的数据结构，用最小元素的位置将能减少空间消耗）push到辅助栈中；每次pop一个元素出栈的时候，同时pop辅助栈。,2019/9/1,Software Architecture,20,思路 | | | | | | | | | a | | x | | b | | x | | c | | x | | d | | x |,2019/9/1,Softwar
10、e Architecture,21,堆：heap 目的：解决两个问题 1.排序 2.优先队列 定义： 1.顺序 2.形状,2019/9/1,Software Architecture,22,堆：heap 实现：,2019/9/1,Software Architecture,23,两个关键函数: Siftup():当x1.n-1为堆时，插入新的元素使得x1n为堆,2019/9/1,Software Architecture,24,两个关键函数: Siftdown():当x1.n为堆时，将x1取走，使得x1n-1为堆,时间复杂度均为logn,2019/9/1,Software Architectu
11、re,25,优先队列 性质：队列通过insert和extract操作维护元素队列 其中extract返回队列中最小（最大）值,2019/9/1,Software Architecture,26,优先队列（堆实现） Insert：n+,x(n)=t,siftup(x1n) Extract: return x(1), x(1)=x(n),n-,siftup(x1n-1),2019/9/1,Software Architecture,27,排序： 利用优先队列： N次Insert： N次Extract for i=(2n) siftup(i) for i=n i=2 i- swap(1,i) sif
12、tdown(i-1) 对比快排优于时间复杂度（最坏情况） 劣于空间复杂度 但一般情况下快排仍要比堆排序快 快排为什么那么快：http:/ Architecture,28,程序中的堆： 要求对象只能分配在堆： Class UPNum; UPNun n; /error! UPNum *p=new UPNum ; /fine 析构函数声明为私有，建立伪构造函数 private: UPNum(); public: void destroy() const(delete this;) P-destroy();,2019/9/1,Software Architecture,29,禁止对象分配在堆上 UPN
13、um *p=new UPNum；/error 将new声明为私有 Class UPNum private: static void *operator new(size_t size); static void operator delete(void *ptr); ; 判断对象是否在分配堆上？,树,常见结构： 二叉树二元查找树 平衡二叉树 Struct btree int m_value; btree* left; btree* right; ,2019/9/1,30,ISP,2019/9/1,Software Architecture,31,查询二叉树：BST 优势在于快速查找数据 基本操
14、作：查询，插入，删除 时间复杂度logn,2019/9/1,Software Architecture,32,1.遍历顺序 在BST中查一个树：给出的序列不可能是检查的序列： 252 401 398 330 344 397 363 202 911 240 912 245 363 2 252 401 398 330 后面的值均小于后大于之前的值,2019/9/1,Software Architecture,33,遍历顺序 输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true，否则返回false。 4 7 5 12 10 10 / 5 12 / 4 7,2019/9/
15、1,Software Architecture,34,1.在后续遍历得到的序列中，最后一个元素为树的根结点。 Root=seqn 2.比根结点小的元素都应该位于序列的左半部分； seq1i 3.从第一个大于跟结点开始到跟结点前面的一个元素为止，所有元素都应该大于跟结点seqjn-1 根据这样的划分，把序列划分为左右两部分，我们递归地确认序列的左、右两部分是不是都是二元查找树。,2019/9/1,Software Architecture,35,for(; i root) break; int j = i; for(; j length - 1; + j) if(squencej root) r
16、eturn false;,bool left = true; if(i 0) left = verifySquenceOfBST(squence, i); bool right = true; if(i length - 1) right = verifySquenceOfBST(squence + i, length - i - 1); return (left ,2019/9/1,Software Architecture,36,输入一棵二元树的根结点，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。,如果一棵树只有一个结点，它的深度
17、为1。 如果根结点只有左子树而没有右子树，那么树的深度应该是其左子树的深度加1； 同样如果根结点只有右子树而没有左子树，那么树的深度应该是其右子树的深度加1。 如果既有右子树又有左子树呢？那该树的深度就是其左、右子树深度的较大值再加1。,2019/9/1,Software Architecture,37,int TreeDepth(SBinaryTreeNode *pTreeNode) if(!pTreeNode) return 0; int nLeft = TreeDepth(pTreeNode-m_pLeft); int nRight = TreeDepth(pTreeNode-m_pRi
18、ght); return (nLeft nRight) ? (nLeft + 1) : (nRight + 1); ,2019/9/1,Software Architecture,38,题目：输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。 例如输入整数22和如下二元树 10 / 5 12 / 4 7 则打印出两条路径：10, 12和10, 5, 7。,字符串操作,字符串基本操作,S系列 strnicmp strcasecmp strncasecmp strcpy strncpy strlcpy strcat str
19、ncat strlcat strcmp strncmp strchr strrchr strnchr strstrip strlen strnlen strspn strcspn strpbrk strseq strstr M系列 memset memcpy memmove memcmp memscan memchr A系列 atoi，itoa,2019/9/1,40,Software Architecture,Strcpy char * strcpy( char *strDest, const char *strSrc ) assert( (strDest != NULL) ,2019/9/
20、1,Software Architecture,41,Memcpy void * memcpy ( void * dst, const void * src, size_t count ) void * ret = dst; while (count-) *(char *)dst = *(char *)src; dst = (char *)dst + 1; src = (char *)src + 1; return(ret); ,2019/9/1,Software Architecture,42,【 】 pSrc 【 】 pDest,2019/9/1,Software Architecture
21、,43,void *MyMemCopy(void *dest,const void *src,size_t count) char *pDest=static_cast(dest); const char *pSrc=static_cast(src); if( pDestpSrc ,2019/9/1,Software Architecture,44,memcpy memmove 对于应用程序来说，因为代码“知道”两个内存块不会重叠，所以可以安全地使用memcpy()函数。,2019/9/1,Software Architecture,45,atoi字符串转换为整数 int StrToInt(c
22、onst char* str) 基本功能: 345 3:3 4: 3*10+4=34 5: 34*10+5=345 其他额外考虑： +、- 非法字符 编写 int StrToInt(const char* str); bool StrToInt(const char *str, int 整数变为字符串？,2019/9/1,Software Architecture,46,字符串算法设计,a. 旋转字符串 abcdef defabc b. hash字符串 删除字符串（特定要求） c. 递归字符串 字符串排列组合 字符串长度,（腾讯）,字符串算法设计,定义字符串的左旋转操作：把字符串前面的若干个字
23、符移动到字符串的尾部。如把字符串abcdef左旋转2位得到字符串cdefab。请实现字符串左旋转的函数。 hello world world hello a b c d e f g g f e d c b a d e f g a b c p1 p2,2019/9/1,Software Architecture,48,char* LeftRotateString(char* pStr, unsigned int n) ReverseString(pFirstStart, pFirstEnd); ReverseString(pSecondStart, pSecondEnd); ReverseStr
24、ing(pFirstStart, pSecondEnd); return pStr; ,2019/9/1,Software Architecture,49,题目：在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff，则输出b const int tableSize = 256; unsigned int hashTabletableSize;,2019/9/1,Software Architecture,50,const int tableSize = 256; unsigned int hashTabletableSize; char* pHashKey = pString;
25、while(*(pHashKey) != 0) hashTable*(pHashKey+) +; pHashKey = pString; while(*pHashKey != 0) if(hashTable*pHashKey = 1) return *pHashKey; pHashKey+; ,2019/9/1,Software Architecture,51,字符串长度 Int strlength(const char *p) return (p=NULL)?(0):(strlength(p+)+1); 123 ”123” 123%10 12/10 3 2 1 1 2 3 Void fun(int *p),2019/9/1,Software Architecture,52,Reference,数据结构 算法导论 编程珠玑 编程之美,2019/9/1,Software Architecture,53,Thank You！,Grady Booch,2019/9/1,54,Software Architecture,