首页 > 代码库 > 每天一个小算法(4)----在O(1)时间删除指定结点
每天一个小算法(4)----在O(1)时间删除指定结点
O(1)时间内删除结点的思路只能是复制该结点下一个结点的数据,然后删除该结点的下一个结点,来等效删除此结点。
需要注意的地方是删除头结点和尾结点的处理。
1 #include <stdio.h> 2 #include <time.h> 3 #include <stdlib.h> 4 typedef struct Node 5 { 6 int data; 7 Node* next; 8 }Node, *List; 9 10 List createList(int num) //随机生成数字,构造链表11 {12 List aList = (List)malloc(sizeof(Node));13 aList->next = NULL;14 aList->data = http://www.mamicode.com/0;15 Node* qT = aList;16 17 // srand((int)time(0));18 for ( int i=0; i< num; ++i)19 {20 Node* pTN = (Node*)malloc(sizeof(Node));21 pTN->data = http://www.mamicode.com/rand()%100;22 pTN->next = NULL;23 qT->next = pTN;24 qT = pTN;25 }26 return aList;27 }28 29 void printList(List aList) //打印链表30 {31 if ( aList == NULL || aList->next == NULL )32 return;33 34 Node* pT = aList->next;35 printf("element of list:\n\t");36 while( pT != NULL )37 {38 printf("%d ", pT->data);39 pT = pT->next;40 }41 42 printf("\n");43 }44 45 void deleteList(List aList) //删除链表46 {}47 48 49 //删除结点主算法50 void deleteNode(List aList, Node* pNode)51 {52 if ( aList == NULL || pNode == NULL )53 return;54 55 if ( aList == pNode )56 {57 printf("refuse to delete head node\n");58 return;59 }60 61 if ( pNode->next == NULL )62 {63 Node* pT = aList->next;64 while ( pT->next != NULL )65 {66 pT = pT->next;67 }68 69 delete pNode;70 pT->next == NULL;71 }72 73 Node* pN = pNode->next;74 pNode->data = http://www.mamicode.com/pNode->next->data;75 pNode->next = pNode->next->next;76 77 delete pN;78 }79 80 int main(int argc, char const *argv[])81 {82 srand((int)time(0));83 List aList = createList(5);84 printList(aList);85 deleteNode(aList,aList->next->next);86 printList(aList);87 deleteList(aList);88 89 return 0;90 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。