datastructure_by_sunli

《datastructure_by_sunli》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构与基本算法DataStructures&Algorithm孙立多媒体通信实验室提纲基本数据结构与操作字符串操作常见算法2021/6/112ISP常见数据结构与操作链表StructListNode{intm_value;ListNode*p_Next;};1随机访问元素2插入删除移动元素3事先准备空间2021/6/114ISP简单不常用考察频繁题型多变链表基本操作1.头指针修改intInsert(listnode*head){listnode*newnode;newnode=(listnode*)malloc(sizeof(listnode

2、));if(!newnode)return0;newnode->next=head;head=newnode;return1;}}2021/6/11SoftwareArchitecture5链表插入与删除插入head->p1->p2->p3->p4->p5….pn->NULLpxPx->next=p2->next;p2->next=px删除head->p1->p2->p3->p4->p5….pn->NULL…………p->next=ptodelete…………..p->next=ptodelete->nextfree(ptodelete)插入和删除需

3、要依赖该位置之前的指针2021/6/11SoftwareArchitecture6链表高级操作：1删除O(1)给定链表的头指针和一个结点指针，在O(1)时间删除该结点。链表结点的定义如下：函数的声明如下：void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted)偷梁换柱，暗渡陈仓2021/6/117ISP2021/6/11SoftwareArchitecture8head->p1->p2->p3->p4->p5….pn->NULLp4要删：p4已找到--》删p4nextListNode

4、*pNext=pToBeDeleted->m_pNext;pToBeDeleted->m_nKey=pNext->m_nKey;pToBeDeleted->m_pNext=pNext->m_pNext;//deletethenodenexttothepToBeDeleteddeletepNext;pNext=NULL;2021/6/11SoftwareArchitecture92反转（输出）输入一个链表的头结点，反转该链表，并返回反转后链表的头结点。head->p1->p2->p3->p4->p5….pn->NULLVoidfunc(Listno

5、de*pHead){}NULL<-p1<-p2<-p3<-p4<-p5…pn<-headpPrevpNodepNextpReversedHead;2021/6/11SoftwareArchitecture10ListNode*ReverseIteratively(ListNode*pHead){      ListNode*pReversedHead=NULL;      ListNode*pNode=pHead;      ListNode*pPrev=NULL;      while(pNode!=NULL)      {   

6、         ListNode*pNext=pNode->m_pNext;            if(pNext==NULL)                  pReversedHead=pNode;            //reversethelinkagebetweennodes            pNode->m_pNext=pPrev;            //moveforwardonthethelist            pPrev=pNode;            pNode=pNext; 

7、     }return pReversedHead;}2021/6/11SoftwareArchitecture113链表相交（环）(阿里巴巴)判断一个单向链表中是否有环的最佳方法是：A两重遍历B快慢指针C路径记录D哈希表辅助这原来是个圈哦2021/6/11SoftwareArchitecture12While(pFast!=pSlow)pFast=pFast->next->next;pSlow=pSlow->next;2021/6/11SoftwareArchitecture13循环链表的入口点head->p1->p2->p3->p4->

8、p5….pn->pn1

9、

10、pn4<-pn3<-pn2<1.设pFast走过的路程为S(pFast)pSlow走过的路程S(pSlow)S