链表试题算法

1、1链表基本操作typedef struct myLinkint data;struct myLink *next;Link;/创建链表 包含头节点int creatLink(Link *phead)int res = 0;int num;Link *ptm = (Link *)malloc(sizeof(Link);ptm->data = 0;*phead = ptm;printf("请输入数据，以0结束！n");scanf("%d", &num);while (num != 0)Link *pNew = (Link *)malloc(si

2、zeof(Link);if (pNew = NULL)res = -1;printf("pNew=NULL 创建链表失败 error:%dn",res);pNew->data = num;ptm->next = pNew;ptm = pNew;printf("请输入数据，以0结束！n");scanf("%d", &num);ptm->next = NULL;return res;/打印链表int printLink(Link *pHead)int res = 0;Link *p = pHead->nex

3、t;if (p = NULL)res = -1;printf("printfLink() err:%d 链表为空打印失败n",res);return res;while (p != NULL)printf("data=%dn",p->data);p = p->next;return res;/插入链表在data=x的前面插入data=y;int insertLink(Link *pHead, int x, int y)int res = 0;if (pHead = NULL)res = -1;printf("pHead=NULL i

4、nsertLink() err:%dn",res);return res;Link *pNew = (Link *)malloc(sizeof(Link);pNew->data = y; Link *pPre = pHead;Link *pCurr = pHead->next;int flag = 0;while (pCurr != NULL)if (pCurr->data = x)flag = 1;break;pPre = pPre->next;pCurr = pCurr->next;if (flag = 0)res = -2;printf("

5、;原链表中没有%dn",x);return res;pNew->next = pCurr;pPre->next = pNew;return res;/删除链表中节点 删除data=x的节点int deleLink(Link *pHead, int x)int res = 0;if (pHead = NULL)res = -1;printf("pHead=NULL deleLink() error:%dn",res);return res;Link *pPre = pHead;Link *pCurr = pHead->next;int flag =

6、 0;while (pCurr != NULL)if (pCurr->data = x)flag = 1;break;pPre = pPre->next;pCurr = pCurr->next;if (flag = 0)res = -2;printf("原链表中没有%dn", x);return res;pPre->next = pCurr->next;return res;/反转链表int revertLink(Link *pHead)int res = 0;if (pHead = NULL|pHead->next=NULL|pHead

7、->next->next=NULL)res = -1;printf("pHead=NULL revertLink() error:%dn",res);return res;Link *pPre = pHead->next;Link *pCurr = pHead->next->next;Link *q = NULL;while (pCurr != NULL)q = pCurr->next;pCurr->next = pPre;pPre = pCurr;pCurr = q;pHead->next->next = NULL;p

8、Head->next = pPre;return res;/链表排序/再创建一个空链表 从原链表中找到最大值的那个节点 然后往空链表里添加 int sortLink(Link *pHead,Link *pHead1)int res = 0;Link *pNewHead = (Link *)malloc(sizeof(Link);pNewHead->data = 0;Link *pNewTail = pNewHead;if (pHead = NULL)res = -1;printf("pHead=NULL sortLink() erro:%dn", res);re

9、turn res;/先从原链表里找出最大值的那个节点start:Link *pMax = pHead->next;Link *pPre = pHead;Link *pCurr = pMax->next;while (pCurr != NULL)if (pCurr->data > pMax->data)pPre = pMax;pMax = pCurr;pCurr = pCurr->next;pPre->next = pMax->next;/ 让最大的那个节点脱离原链表if (pNewHead->next = NULL)pNewHead->

10、;next = pMax;pNewTail = pMax;pMax->next = NULL;elsepNewTail->next = pMax;pNewTail = pMax;pMax->next = NULL;if (pHead->next = NULL) /所有的节点都脱离了原链表goto sortEnd;goto start;sortEnd:*pHead1 = pNewHead;return res;int destoryLink(Link *pHead)int res = 0;if (pHead = NULL)res = -1;printf("pHe

11、ad=NULL 链表为空 释放内存失败 erro:%dn",res);return res;Link *pt = *pHead;while (pt != NULL)Link *tmp = pt->next;free(pt);pt =tmp;*pHead = NULL;return res;/测试案例void main()Link *pHead = NULL;int res;res = creatLink(&pHead);if (res != 0)printf("function creatLink() err:%dn",res);goto End;r

12、es = printLink(pHead);if (res != 0)printf("function printLink() err:%dn", res);goto End;printf("* 在3的前面插入4 *n");res = insertLink(pHead,3,4);if (res != 0)printf("function insetrLink() err:%dn", res);goto End;res = printLink(pHead);if (res != 0)printf("function print

13、Link() err:%dn", res);goto End;printf("* 删除data=4的节点 *n");res = deleLink(pHead,4);if (res != 0)printf("function deleLink() err:%dn", res);goto End;res = printLink(pHead);if (res != 0)printf("function printLink() err:%dn", res);goto End;printf("* 逆转链表 *n")

14、;res = revertLink(pHead);if (res != 0)printf("function revertLink() err:%dn", res);goto End;res = printLink(pHead);if (res != 0)printf("function printLink() err:%dn", res);goto End;printf("* 从大到小排序链表 *n");Link *pHead1 = NULL;res = sortLink(pHead,&pHead1);if (res !=

15、0)printf("function sortLink() err:%dn", res);goto End;res = printLink(pHead1);if (res != 0)printf("function printLink() err:%dn", res);goto End;End:if (pHead != NULL)res = destoryLink(&pHead);if (res != 0)printf("function destoryLink() is error:%dn",res);return;syst

16、em("pause");2、单链表的建立，把a-z26个字母插入到链表中，并且倒叙，还要打印#include <stdio.h>#include <stdlib.h>typedef struct valchar data;struct val *next;node,*p;void main(void)node *p = NULL;node *q = NULL;node *head = (node *)malloc(sizeof(node);head->data = ' 'head->next = NULL;node *fi

17、rst = (node *)malloc(sizeof(node);first->data = 'a'first->next = NULL;head->next = first;p = first;int longth = 'z' - 'b'int i = 0;while (i <= longth)node *temp = (node *)malloc(sizeof(node);temp->data = 'b'+i;temp->data = NULL;/开始逆转q = temp;head->

18、;next = temp;temp->next = p;p = q;i+;/打印链表node *tmp = head->next;while (tmp!= NULL)printf("data:%c ",tmp->data);tmp = tmp->next;3约瑟夫问题 循环链表.h文件#ifndef _CIRCLELIST_H_#define _CIRCLELIST_H_typedef void CircleList;/*typedef struct _tag_CircleListNode CircleListNode;struct _tag_Cir

19、cleListNodeCircleListNode* next;*/typedef struct _tag_CircleListNodestruct _tag_CircleListNode * next;CircleListNode;CircleList* CircleList_Create();void CircleList_Destroy(CircleList* list);void CircleList_Clear(CircleList* list);int CircleList_Length(CircleList* list);int CircleList_Insert(CircleL

20、ist* list, CircleListNode* node, int pos);CircleListNode* CircleList_Get(CircleList* list, int pos);CircleListNode* CircleList_Delete(CircleList* list, int pos);/addCircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node);CircleListNode* CircleList_Reset(CircleList* list);Circle

21、ListNode* CircleList_Current(CircleList* list);CircleListNode* CircleList_Next(CircleList* list);#endifC. 文件#include <stdio.h>#include <malloc.h>#include "circleList.h"typedef struct _tag_CircleListCircleListNode header;CircleListNode* slider;int length; TCircleList;CircleList*

22、 CircleList_Create() / O(1)TCircleList* ret = (TCircleList*)malloc(sizeof(TCircleList);if (ret = NULL)return NULL;ret->length = 0;ret->header.next = NULL;ret->slider = NULL;return ret;void CircleList_Destroy(CircleList* list) / O(1)if (list = NULL)return ;free(list);void CircleList_Clear(Ci

23、rcleList* list) / O(1)TCircleList* sList = (TCircleList*)list;if (sList = NULL)return ;sList->length = 0;sList->header.next = NULL;sList->slider = NULL;int CircleList_Length(CircleList* list) / O(1)TCircleList* sList = (TCircleList*)list;int ret = -1;if (list = NULL)return ret;ret = sList-&

24、gt;length;return ret;int CircleList_Insert(CircleList* list, CircleListNode* node, int pos) / O(n) int ret = 0, i=0;TCircleList* sList = (TCircleList*)list;if (list = NULL | node= NULL | pos<0)return -1;/if( ret )CircleListNode* current = (CircleListNode*)sList;for(i=0; (i<pos) && (cur

25、rent->next != NULL); i+)current = current->next;/current->next 0号节点的地址node->next = current->next; /1current->next = node; /2/若第一次插入节点if( sList->length = 0 )sList->slider = node;sList->length+;/若头插法if( current = (CircleListNode*)sList )/获取最后一个元素CircleListNode* last = Circle

26、List_Get(sList, sList->length - 1); last->next = current->next; /3return ret;CircleListNode* CircleList_Get(CircleList* list, int pos) / O(n)TCircleList* sList = (TCircleList*)list;CircleListNode* ret = NULL;int i = 0;if (list=NULL | pos<0)return NULL;/if( (sList != NULL) && (pos

27、 >= 0) && (sList->length > 0) )CircleListNode* current = (CircleListNode*)sList;for(i=0; i<pos; i+)current = current->next;ret = current->next;return ret;CircleListNode* CircleList_Delete(CircleList* list, int pos) / O(n)TCircleList* sList = (TCircleList*)list;CircleListNod

28、e* ret = NULL;int i = 0;if( (sList != NULL) && (pos >= 0) && (sList->length > 0) )CircleListNode* current = (CircleListNode*)sList;CircleListNode* last = NULL;for(i=0; i<pos; i+)current = current->next;/若删除第一个元素if( current = (CircleListNode*)sList )last = (CircleListNo

29、de*)CircleList_Get(sList, sList->length - 1);/求要删除的元素ret = current->next;current->next = ret->next;sList->length-;/判断链表是否为空if( last != NULL )sList->header.next = ret->next;last->next = ret->next;/若删除的元素为游标所指的元素if( sList->slider = ret )sList->slider = ret->next;/若删

30、除元素后，链表长度为0if( sList->length = 0 )sList->header.next = NULL;sList->slider = NULL;return ret;CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node) / O(n)TCircleList* sList = (TCircleList*)list;CircleListNode* ret = NULL;int i = 0;if( sList != NULL )CircleListNode* cur

31、rent = (CircleListNode*)sList;/查找node在循环链表中的位置ifor(i=0; i<sList->length; i+)if( current->next = node )ret = current->next;break;current = current->next;/如果ret找到，根据i去删除if( ret != NULL )CircleList_Delete(sList, i);return ret;CircleListNode* CircleList_Reset(CircleList* list) / O(1)TCirc

32、leList* sList = (TCircleList*)list;CircleListNode* ret = NULL;if( sList != NULL )sList->slider = sList->header.next;ret = sList->slider;return ret;CircleListNode* CircleList_Current(CircleList* list) / O(1)TCircleList* sList = (TCircleList*)list;CircleListNode* ret = NULL;if( sList != NULL

33、)ret = sList->slider;return ret;CircleListNode* CircleList_Next(CircleList* list) / O(1)TCircleList* sList = (TCircleList*)list;CircleListNode* ret = NULL;if( (sList != NULL) && (sList->slider != NULL) )ret = sList->slider;sList->slider = ret->next;return ret;Main.c 文件#include

34、 <stdio.h>#include <stdlib.h>#include "circlelist.h"typedef struct ValueCircleListNode node;int v;Va;void main()CircleList *circleList = NULL;circleList = CircleList_Create();Va v1, v2, v3, v4, v5, v6, v7, v8;v1.v = 1; v2.v = 2; v3.v = 3; v4.v = 4;v5.v = 5; v6.v = 6; v7.v = 7;

35、v8.v = 8;int res;res = CircleList_Insert(circleList, (CircleListNode *)&v1, CircleList_Length(circleList);res = CircleList_Insert(circleList, (CircleListNode *)&v2, CircleList_Length(circleList);res = CircleList_Insert(circleList, (CircleListNode *)&v3, CircleList_Length(circleList);res

36、= CircleList_Insert(circleList, (CircleListNode *)&v4, CircleList_Length(circleList);res = CircleList_Insert(circleList, (CircleListNode *)&v5, CircleList_Length(circleList);res = CircleList_Insert(circleList, (CircleListNode *)&v6, CircleList_Length(circleList);res = CircleList_Insert(c

37、ircleList, (CircleListNode *)&v7, CircleList_Length(circleList);res = CircleList_Insert(circleList, (CircleListNode *)&v8, CircleList_Length(circleList);int len = CircleList_Length(circleList);for (int i = 0; i < len; i+)Va *tmp = (Va *)CircleList_Get(circleList, i);if (tmp != NULL)printf

38、("tmp v:%dn",tmp->v);CircleList_Reset(circleList);printf("nn");Va *tmp = NULL;while (CircleList_Length(circleList) > 0)for (int i = 1; i < 3; i+)CircleList_Next(circleList); / 让游标后移两步tmp = (Va *)CircleList_Current(circleList); /获取游标所指的元素printf("tmp v:%dn", tmp-

39、>v);CircleList_DeleteNode(circleList, (CircleListNode *)tmp); /删除该节点并让游标后移/CircleList_Clear(circleList);CircleList_Destroy(circleList);system("pause");4有一个数组a1000存放0-1000；要求每个二个数删除一个，到末尾是循环至开头继续进行，求最后一个被删除的数的原始下标位置#include <iostream>using namespace std;struct nodeint data;node *next;int main()node *head = new node;head->data = 0;head->next = NULL;node *p = head;/创建链表for (int i = 1; i < 1000; i+)node *tmp = new node;tmp->data = i;tmp->next = NULL;head->next = tmp;head = head->next;/把链表的尾