단일 링크 흔 한 면접 문제
//LinkList.h
#ifndef _LINKLIST_H__
#define _LINKLIST_H__
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
typedef int DataType;
typedef struct Node
{
DataType data;
struct Node* next;
}Node,*pNode,*pList;
void InitList(pList* pplist);
//
void PushBack(pList* pplist);
//
void BubbleSort(pList* pplist);
//
void ReversePrint(pList plist);
//
void EraseNotTail(pNode pos);
//
void InsertFrontNode(pNode pos, DataType x);
//
void JosephCycle(pList* pplist, int k);
//
void ReverseList(pList* pplist);
//
pList Merge(const pList* p1, const pList* p2);
// ,
pNode FindMidNode(pList plist);
// k ,
pNode FindKNode(pList plist, int k);
//
pNode CheckCircle(pList plist);
//
int GetCircleLength(pNode meet);
//
pNode GetCycleEntryNode(pList plist, pNode meet);
//
int CheckCross(pList list1, pList list2);
//
pNode GetCrossNode(pList list1, pList list2);
#endif
//LinkList.c
#define _CRT_SECURE_NO_WARNINGS
#include"LinkList.h"
pNode buynode(DataType x)
{
pNode tmp = NULL;
tmp = (pNode)malloc(sizeof(Node));
if (tmp == NULL)
{
perror("malloc");
exit(1);
}
tmp->data = x;
tmp->next = NULL;
return tmp;
}
void InitList(pList* pplist)
{
assert(pplist);
*pplist = NULL;
}
//
void PushBack(pList* pplist,DataType x)
{
pNode cur = NULL;
assert(pplist);
cur = *pplist;
pNode newnode = buynode(x);
if (*pplist == NULL)
{
*pplist = newnode;
}
else
{
while (cur->next)
{
cur = cur->next;
}
cur->next = newnode;
}
}
//
void BubbleSort(pList* pplist)
{
pNode cur = NULL;
pNode tail = NULL;
assert(pplist);
cur = *pplist;
if (*pplist == NULL)
{
return;
}
while (cur != tail)
{
while (cur->next!=tail)
{
if (cur->data < cur->next->data)
{
DataType tmp = cur->data;
cur->data = cur->next->data;
cur->next->data = tmp;
}
cur = cur->next;
}
tail = cur;
cur = *pplist;
}
}
//
void Display(pList plist)
{
pNode tmp = plist;
while (tmp)
{
printf("%d->", tmp->data);
tmp = tmp->next;
}
printf("end
");
}
// x
pNode Find(pList pplist,DataType x)
{
pNode cur = pplist;
if (pplist == NULL)
{
return NULL;
}
else
{
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
}
//
void EraseNotTail(pNode pos)
{
pNode cur = NULL;
assert(pos);
cur = pos->next;
pos->data = cur->data;
pos->next = cur->next;
free(cur);
cur = NULL;
}
//
void InsertFrontNode(pNode pos, DataType x)
{
pNode NewNode = NULL;
assert(pos);
NewNode = buynode(x);
NewNode->next = pos->next;
pos->next = NewNode;
DataType tmp = pos->data;
pos->data = NewNode->data;
NewNode->data = tmp;
}
//
void JosephCycle(pList* pplist, int k)
{
}
//
void ReverseList(pList* pplist)
{
pNode cur = *pplist;
pNode p = NULL;
pNode r = NULL;
assert(pplist);
while (cur)
{
r = p;
p = cur;
cur = cur->next;
p->next = r;
}
*pplist = p;
}
//
pList Merge(const pList* p1, const pList* p2)
{
pList newnode = NULL;
pNode cur = NULL;
pNode cur1 = *p1;
pNode cur2 = *p2;
assert(p1);
assert(p2);
//p1 p1 ( NULL)
if (*p1 == *p2)
{
return *p1;
}
// ,
if ((*p1 == NULL) && (*p2 != NULL))
{
return *p2;
}
if ((*p2 == NULL) && (*p1 != NULL))
{
return *p1;
}
//2
if (cur1->data < cur2->data)
{
newnode = cur1;
cur1 = cur1->next;
newnode->next = NULL;
}
else
{
newnode = cur2;
cur2 = cur2->next;
newnode->next = NULL;
}
cur = newnode;
while (cur1&&cur2)
{
if (cur1->data > cur2->data)
{
cur->next = cur2;
cur2 = cur2->next;
cur = cur->next;
}
else
{
cur->next = cur1;
cur1 = cur1->next;
cur = cur->next;
}
}
if (cur1 == NULL)
{
cur->next = cur2;
}
else
{
cur->next = cur1;
}
return newnode;
}
// ,
pNode FindMidNode(pList plist)
{
pNode slow = plist;
pNode fast = plist;
if ((fast == NULL) || (fast->next == NULL))
{
return fast;
}
else
{
while (fast&&fast->next)
{
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
}
// k ,
pNode FindKNode(pList plist, int k)
{
pNode fast = plist;
pNode slow = plist;
if (plist == NULL)
{
return NULL;
}
int i = 0;
for (i; i < k-1; i++)
{
fast = fast->next;
if (fast == NULL)
{
return NULL;
}
}
fast = fast->next;
while (fast)
{
fast = fast->next;
slow = slow->next;
}
return slow;
}
//
pNode CheckCircle(pList plist)
{
pNode slow = plist;
pNode fast = plist;
if (plist == NULL)
{
return NULL;
}
else
{
while (fast&&fast->next)
{
fast = fast->next->next;
slow = slow->next;
if (fast == slow)
{
return slow;
break;
}
}
return NULL;
}
}
//
int GetCircleLength(pNode meet)
{
int count = 0;
pNode cur = meet;
do
{
count++;
cur = cur->next;
} while (cur!=meet);
return count;
}
//
pNode GetCycleEntryNode(pList plist, pNode meet)
{
}
//
int CheckCross(pList list1, pList list2)
{
pNode cur1 = list1;
pNode cur2 = list2;
if (cur1 == NULL || cur2 == NULL)
{
return 0; //0 ,1
}
while (cur1->next)
{
cur1 = cur1->next;
}
while (cur2->next)
{
cur2 = cur2->next;
}
if (cur1 == cur2)
{
return 1;
}
return 0;
}
//
pNode GetCrossNode(pList list1, pList list2)
{
int len1 = 0, len2 = 0;
pNode cur1 = NULL;
pNode cur2 = NULL;
cur1 = list1;
cur2 = list2;
while (cur1->next)
{
len1++;
cur1 = cur1->next;
}
while (cur2->next)
{
len2++;
cur2 = cur2->next;
}
int diff = abs(len2 - len1);
if (len1 > len2)
{
cur1 = list1;
cur2 = list2;
}
else
{
cur1 = list2;
cur2 = list1;
}
for (int i = 0; i < diff; i++)
{
cur1 = cur1->next;
}
while (cur1 != cur2)
{
cur1 = cur1->next;
cur2 = cur2->next;
}
return cur1;
}
//test.c
#define _CRT_SECURE_NO_WARNINGS
#include"LinkList.h"
void test1()
{
pList pplist;
InitList(&pplist);
PushBack(&pplist, 1);
PushBack(&pplist, 2);
PushBack(&pplist, 3);
PushBack(&pplist, 4);
Display(pplist);
//ReversePrint1(&pplist);
//ReversePrint2(&pplist);
Display(pplist);
}
void test2()
{
pList pplist;
pNode node = NULL;
InitList(&pplist);
PushBack(&pplist, 1);
PushBack(&pplist, 2);
PushBack(&pplist, 3);
PushBack(&pplist, 4);
Display(pplist);
node = Find(pplist, 3);
EraseNotTail(node);
InsertFrontNode(node, 10);
Display(pplist);
}
void test3()
{
pList pplist;
pNode node = NULL;
InitList(&pplist);
PushBack(&pplist, 11);
PushBack(&pplist, 2);
PushBack(&pplist, 7);
PushBack(&pplist, 4);
Display(pplist);
BubbleSort(&pplist);
Display(pplist);
}
void test4()
{
pList s1;
pList s2;
pList s3 = NULL;
pList node = NULL;
pNode mid = NULL;
InitList(&s1);
InitList(&s2);
PushBack(&s1, 1);
PushBack(&s1, 3);
PushBack(&s1, 5);
Display(s1);
PushBack(&s2, 2);
PushBack(&s2, 4);
PushBack(&s2, 6);
PushBack(&s2, 8);
PushBack(&s2, 10);
Display(s2);
node = Merge(&s2, &s1);
mid=FindMidNode(node);
Display(node);
printf("%d
", mid->data);
}
void test5()
{
pList pplist;
pNode node = NULL;
InitList(&pplist);
PushBack(&pplist, 11);
PushBack(&pplist, 2);
PushBack(&pplist, 7);
PushBack(&pplist, 44);
PushBack(&pplist, 5);
PushBack(&pplist, 8);
node= Find(pplist, 8);
node->next = Find(pplist, 2);
Display(pplist);
node = FindKNode(pplist, 7);
printf("%d
", node->data);
}
void test6()
{
pList pplist;
pNode node = NULL;
pNode newnode = NULL;
InitList(&pplist);
PushBack(&pplist, 11);
PushBack(&pplist, 2);
PushBack(&pplist, 7);
PushBack(&pplist, 44);
PushBack(&pplist, 5);
PushBack(&pplist, 8);
node = Find(pplist, 8);
node->next = Find(pplist, 2);
newnode = CheckCircle(pplist);
//printf("%d
", newnode->data);
int ret=GetCircleLength(newnode);
printf("%d
", ret);
}
void test7()
{
pList s1;
pList s2;
pNode node;
pNode c;
InitList(&s1);
InitList(&s2);
PushBack(&s1, 1);
PushBack(&s1, 3);
PushBack(&s1, 5);
PushBack(&s2, 2);
PushBack(&s2, 4);
PushBack(&s2, 6);
PushBack(&s2, 8);
PushBack(&s2, 10);
node = Find(s1, 5);
node->next = Find(s2, 6);
int ret = CheckCross(NULL, NULL);
if (ret == 1)
{
printf("
");
}
else
{
printf("
");
}
c = GetCrossNode(s1, s2);
printf("%d
", c->data);
}
int main()
{
//test1();
//test2();
//test3();
//test4();
//test5();
//test6();
test7();
system("pause");
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
데이터 구조 상의 연습 (2) 싱글 체인 시트#include "stdafx.h" #include "stdlib.h" #include "malloc.h" #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.