鏈表試題算法

1、1鏈表基本操作typedef struct myLinkint data;struct myLink *next;Link;/創(chuàng)建鏈表 包含頭節(jié)點(diǎn)int creatLink(Link *phead)int res = 0;int num;Link *ptm = (Link *)malloc(sizeof(Link);ptm->data = 0;*phead = ptm;printf("請輸入數(shù)據(jù)，以0結(jié)束！n");scanf("%d", &num);while (num != 0)Link *pNew = (Link *)malloc(si

2、zeof(Link);if (pNew = NULL)res = -1;printf("pNew=NULL 創(chuàng)建鏈表失敗 error:%dn",res);pNew->data = num;ptm->next = pNew;ptm = pNew;printf("請輸入數(shù)據(jù)，以0結(jié)束！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;/刪除鏈表中節(jié)點(diǎn) 刪除data=x的節(jié)點(diǎn)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;/反轉(zhuǎn)鏈表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;/鏈表排序/再創(chuàng)建一個(gè)空鏈表 從原鏈表中找到最大值的那個(gè)節(jié)點(diǎn) 然后往空鏈表里添加 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;/先從原鏈表里找出最大值的那個(gè)節(jié)點(diǎn)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;/ 讓最大的那個(gè)節(jié)點(diǎn)脫離原鏈表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) /所有的節(jié)點(diǎn)都脫離了原鏈表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 鏈表為空 釋放內(nèi)存失敗 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的節(jié)點(diǎn) *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("* 逆轉(zhuǎn)鏈表 *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(bǔ)-z26個(gè)字母插入到鏈表中，并且倒敘，還要打印#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;/開始逆轉(zhuǎn)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約瑟夫問題 循環(huán)鏈表.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號(hào)節(jié)點(diǎn)的地址node->next = current->next; /1current->next = node; /2/若第一次插入節(jié)點(diǎn)if( sList->length = 0 )sList->slider = node;sList->length+;/若頭插法if( current = (CircleListNode*)sList )/獲取最后一個(gè)元素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;/若刪除第一個(gè)元素if( current = (CircleListNode*)sList )last = (CircleListNo

29、de*)CircleList_Get(sList, sList->length - 1);/求要?jiǎng)h除的元素ret = current->next;current->next = ret->next;sList->length-;/判斷鏈表是否為空if( last != NULL )sList->header.next = ret->next;last->next = ret->next;/若刪除的元素為游標(biāo)所指的元素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在循環(huán)鏈表中的位置ifor(i=0; i<sList->length; i+)if( current->next = node )ret = current->next;break;current = current->next;/如果ret找到，根據(jù)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); / 讓游標(biāo)后移兩步tmp = (Va *)CircleList_Current(circleList); /獲取游標(biāo)所指的元素printf("tmp v:%dn", tmp-

39、>v);CircleList_DeleteNode(circleList, (CircleListNode *)tmp); /刪除該節(jié)點(diǎn)并讓游標(biāo)后移/CircleList_Clear(circleList);CircleList_Destroy(circleList);system("pause");4有一個(gè)數(shù)組a1000存放0-1000；要求每個(gè)二個(gè)數(shù)刪除一個(gè)，到末尾是循環(huán)至開頭繼續(xù)進(jìn)行，求最后一個(gè)被刪除的數(shù)的原始下標(biāo)位置#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;/創(chuàng)建鏈表for (int i = 1; i < 1000; i+)node *tmp = new node;tmp->data = i;tmp->next = NULL;head->next = tmp;head = head->next;/把鏈表的尾