当前位置:首页 > 公司荣誉 >

关于单链表的算法题

作者:曲靖市宁江木业有限公司 来源:www.ynnjmy.com 发布时间:2017-09-12 16:11:38

关于单链表的算法题

首页 > 程序开发 > Web开发 > 其他 > 正文 关于单链表的算法题 2015-10-24 作者:小止1995 我要投稿 //1.顺序表和链表的优缺点。 //顺序表的优点是可以随机访问数据元素;缺点是大小固定,不利于增删结点。 //链表的优点是采用指针方式增减结点,非常方便(只需要改变指针指向,不移动结点); //缺点是不能进行随机访问,另外,每个结点上增加指针域,造成额外存储空间增大。 #include<stdio.h> #include<malloc.h> #include<stdlib.h> #include<string.h> #include<assert.h> typedef int DataType; typedef struct LinkNode { DataType _data; struct LinkNode *_next; }LinkNode,*pLinkNode; pLinkNode BuyNode(DataType x);//开辟节点 void InitNode(pLinkNode& pHead);//初始化 void DestoryNode(pLinkNode& pHead);//销毁节点 void PushBack(pLinkNode& pHead,DataType x);//尾插节点 void PrintNode(pLinkNode pHead);//打印 void PrintfFromTail(pLinkNode pHead);//从尾到头打印链表 void EraseNoHead(pLinkNode pos);//删除一个无头单链表的非尾节点 void InsertNoHead(pLinkNode pos, DataType x);//无头单链表非头节点插入一个节点 void Joseph(pLinkNode pHead,int Length);//实现约瑟夫环 void Reverse(pLinkNode& pHead);//逆置/反转单链表 void CombineTwoLink(pLinkNode& firstpHead, pLinkNode secondpHead); void SearchMid(pLinkNode pHead);//查找单链表的中间节点,只能遍历一次 pLinkNode SearchKNode(pLinkNode pHead,int k);//查找单链表的倒数第k个节点,只遍历一次 pLinkNode BuyNode(DataType x) { pLinkNode tmp; tmp = (pLinkNode)malloc(sizeof(LinkNode)); tmp->_data = x; tmp->_next = NULL; return tmp; } void InitNode(pLinkNode& pHead) { pHead=NULL; } void DestoryNode(pLinkNode& pHead) { pLinkNode del=pHead; while (pHead!= NULL)//如果phead指向结构体还有数据 { del = pHead; pHead = pHead->_next; free(del); } } pLinkNode Find(pLinkNode PLinkhead, DataType x) { pLinkNode cur = PLinkhead; while (cur) { if (cur->_data == x) return cur; else cur = cur->_next; } return NULL; } void PushBack(pLinkNode& pHead, DataType x) { if (pHead == NULL) { pHead = BuyNode(x); } else { pLinkNode newNode = BuyNode(x),cur=pHead; while (cur->_next != NULL) { cur = cur->_next; } cur->_next = newNode; } } void PrintNode(pLinkNode pHead) { assert(pHead); while (pHead != NULL) { printf("%d->", pHead->_data); pHead=pHead->_next; } printf("NULL\n"); } void PrintfFromTail(pLinkNode pHead) { if (pHead == NULL)//递归法 { printf("NULL->"); return; } else PrintfFromTail(pHead->_next); printf("%d->",pHead->_data); } void EraseNoHead(pLinkNode pos) { assert(pos); pLinkNode del = pos->_next; pos->_data = pos->_next->_data;//将pos后的值赋值给pos pos->_next = pos->_next->_next; free(del); } void InsertNoHead(pLinkNode pos, DataType x) { assert(pos); pLinkNode newNode = BuyNode(x); newNode->_next = pos->_next;//将新值插入到pos后 pos->_next= newNode; newNode->_data = pos->_data;//拷贝数据 pos->_data = x; } void Joseph(pLinkNode pHead,int Length) { assert(pHead);//循环链表 pLinkNode cur = pHead, del; while (1) { if (cur->_next == cur) { assert(cur->_data = 4); printf("所剩最后:%d\n", cur->_data); return; } int times = Length - 1; while (times--) { cur = cur->_next; } del = cur->_next; cur->_data = cur->_next->_data;//拷贝cur的下一个结点的数据,删除它 cur->_next = del->_next; free(del); } } void Reverse(pLinkNode& pHead) { assert(pHead); pLinkNode newHead = NULL; pLinkNode cur = pHead; if (cur == NULL || cur->_next == NULL)//如果链表中只有一个元素 return; while (cur) { pLinkNode tmp = cur;//摘节点 cur = cur->_next; tmp->_next = newHead;//头插 newHead = tmp; } pHead = newHead; } void CombineTwoLink(pLinkNode& firstpHead, pLinkNode secondpHead) { pLinkNode finally =BuyNode(-1),cur=finally,tmp=NULL; assert(firstpHead); assert(secondpHead); while (firstpHead&&secondpHead) { if (firstpHead->_data < secondpHead->_data) { tmp = firstpHead; firstpHead = firstpHead->_next; } else { tmp = secondpHead; secondpHead=secondpHead->_next; } tmp->_next = cur->_next; cur->_next = tmp; cur = tmp; } if (firstpHead) cur->_next = firstpHead; else cur->_next = secondpHead; firstpHead = finally->_next; free(finally); } void SearchMid(pLinkNode pHead) { pLinkNode fast=pHead, slow=pHead; assert(pHead); while (fast&&fast->_next&&fast->_next->_next)//考虑只有两个数的情况 { fast = fast->_next->_next; slow = slow->_next; } printf("%d\n",slow->_data); } pLinkNode SearchKNode(pLinkNode pHead,int k) { pLinkNode fastK=pHead; assert(pHead); while (fastK&&k--) { fastK = fastK->_next; } if (k > 0) return NULL; while (fastK) { fastK = fastK->_next; pHead = pHead->_next; } return pHead; } //void Test1() //{ // pLinkNode Link=NULL; // InitNode(Link); // PushBack(Link, 1); // PushBack(Link, 2); // /*PushBack(Link, 3); // PushBack(Link, 6); // PushBack(Link, 4); // PushBack(Link, 5);*/ // PrintNode(Link); // //EraseNoHead(Find(Link, 2));//非尾 // //PrintNode(Link); // //InsertNoHead(Find(Link,3), 7);//非头 // //PrintNode(Link); // // /*Find(Link, 5)->_next = Find(Link,1); // Joseph(Link, 3);*/ // //PrintfFromTail(Link); // // /*Reverse(Link);*/ // // SearchMid(Link); // PrintNode(Link); // DestoryNode(Link); //} void Test2() { pLinkNode target = NULL, source = NULL,kNode=NULL; InitNode(target); InitNode(source); PushBack(target, 1); PushBack(target, 3); PushBack(target, 4); PushBack(target, 6); PushBack(target, 9); PushBack(source, 3); PushBack(source, 5); PushBack(source, 7); PushBack(source, 10); PushBack(source, 12); PrintNode(target); PrintNode(source); CombineTwoLink(target, source); PrintNode(target); DestoryNode(target); kNode = SearchKNode(target, 3); printf("从尾往前第3个数据:\n%d\n", kNode->_data); } int main() { //Test1(); Test2(); system("pause"); return 0; } 点击复制链接 与好友分享!回本站首页 上一篇:运算符运用之判断一个数是不是2^n 下一篇: 相关文章

Weka算法Classifier-trees-REPTree源码

算法导论学习-binary search tree

算法-二叉查找树

学习日志---Apriori算法发现频繁集

算法-堆排序

排序算法之选择排序

图文推荐

企业建站2800元起,携手武汉肥猫科技,做一个有见地的颜值派!更多优惠请戳:神农架SEO http://shennongjia.raoyu.net

  • 上一篇:唐茶字节社与Python的故事(II)
  • 下一篇:最后一页