데이터 구조 선형 표 의 응용 - 고전 제목 분석
1. 역 치 싱글 체인 시트
2. 반전 싱글 링크
3. 두 개의 질서 있 는 단일 체인 표를 합 친다.
4. 단일 체인 표 에 고리 가 있 는 지 판단 합 니까?링 의 입구 점?링 길이?
5. 두 개의 단일 체인 표 가 교차 하 는 지 판단 합 니까?교점
6. O (1) 시간 에 단일 링크 의 한 노드 를 삭제 합 니 다.
7. 가장 빠 른 시간 안에 단일 체인 테이블 의 마지막 K 번 째 노드 를 찾 을 수 있 습 니까?
8. 가장 빠 른 시간 안에 단일 체인 테이블 의 마지막 K 번 째 노드 를 삭제 합 니까?
9. 두 순서 표 의 교 집합, 병렬 집합 과 차 집합 을 구한다.
10. 두 개의 질서 있 는 단일 체인 표 의 교 집합, 집합 과 차 집합 을 구한다.
11. 두 개의 단일 체인 표 (무질서 할 수 있 음) 의 교 집합, 집합 과 차 집합 을 구한다.
1. 역 치 싱글 체인 시트
/*
** ：
**
** next NULL
*/
void Reverse(List plist)
{
Node *p = plist->next;
plist->next = NULL;
while (p != NULL)
{
Node *pNext = p->next;
p->next = plist->next;
plist->next = p;
p = pNext;
}
}
Node* reverse(Node *head)
{
Node* curNode = head;
p = CurNode->next;
while(p)
{
Node *pNext = p->next;
p->next = curNode;
CurNode = p;
p = pNext;
}
head->next = nullptr;
head = curNode;
return head;
}2. 반전 싱글 링크
/*
** ：
** (prev)、 (cur)、 (pNext)
** ， show
*/
Node *Reverse_1(List plist)
{
Node *ReverseHead = NULL;
Node *prev = NULL;
Node *cur = plist;
while (cur != NULL)
{
Node *curNext =cur->next;
if (curNext == NULL)
{
ReverseHead = cur;
}
cur->next = prev;
prev = cur;
cur = curNext;
}
return ReverseHead;
}
void Show_1(List plist)
{
Node *p = plist;
while (p->next != NULL)
{
printf("%d ",p->data);
p = p->next;
}
printf("
");
}3. 두 개의 질서 있 는 단일 체인 표를 합 친다.
Node Merge_list(List La,List Lb)
{
Node Lc;
InitList(&Lc);
List p1 = La->next;
List p2 = Lb->next;
List p3 = &Lc;
while (p1 != NULL && p2 != NULL)
{
if (p1->data <= p2->data)
{
p3->next = p1;
p3 = p1;
p1 = p1->next;
}
else
{
p3->next = p2;
p3 = p2;
p2 = p2->next;
}
}
if (p1 != NULL)
{
p3->next = p1;
}
if (p2 != NULL)
{
p3->next = p2;
}
return Lc;
}
/*
** ：
** 1 2 ， 1
** ， 2 1 ， 2
** ，
** ，
*/
Node* Merge_list(Node *p1, Node *p2)
{
if (p1 == NULL)
{
return p2;
}
else if(p2 == NULL)
{
return p1;
}
Node *p3 = NULL;
if (p1->data < p2->data)
{
p3 = p1;
p3->next = Merge_list(p1->next,p2);
}
else
{
p3 = p2;
p3->next = Merge_list(p1,p2->next);
}
return p3;
}
4. 단일 체인 표 에 고리 가 있 는 지 판단 합 니까?링 의 입구 점?링 길이?
/*
** ：
** ： ， plist，
** plist ， ，
** ： ， ，
** ， ，
** ： p1，p2， p1 ，p2
** ， p1 p2 ，
*/
void CreateLoop(List plist) //
{
Node *p = plist;
while (p->next != NULL)
{
p = p->next;
}
p->next = plist->next->next->next;
}
Node* IsLoop(List plist)
{
Node *pslow = plist->next;
Node *pfast = pslow->next;
while (pfast != NULL && pslow != NULL)
{
if (pfast == pslow)
{
return pfast;
}
pslow = pslow->next;
pfast = pfast->next;
if(pfast != NULL)
{
pfast = pfast->next;
}
}
return NULL;
}
int LoopLen(List plist)
{
Node *loop = IsLoop(plist);
Node *p = loop;
if (p == NULL)
{
return NULL;
}
int len = 1;
while (p->next != loop)
{
len++;
p = p->next;
}
return len;
}
Node *Loopstart(List plist)
{
Node *p1 = plist;
Node *p2 = plist;
int len = LoopLen(plist);
for (int i = 0; i < len; i++)
{
p1 = p1->next;
}
while (p1 != p2)
{
p1 = p1->next;
p2 = p2->next;
}
return p1;
}5. 두 개의 단일 체인 표 가 교차 하 는 지 판단 합 니까?교점
/*
** ：
** ： p1 p2 pos ，
** p1 ， p1 pos，p2
** ， ， p1 = p2， 。
*/
void CreatCut(List plist1,List plist2) //
{
plist1->next->next = plist2->next->next->next;
}
bool IsCut(List plist1,List plist2)
{
int len1 = GetLength(plist1);
int len2 = GetLength(plist2);
Node *p1 = plist1;
Node *p2 = plist2;
int pos = len1 - len2;
if (pos < 0)
{
p1 = plist2;
p2 = plist1;
pos = len2 - len1;
}
for (int i = 0; i < pos; i++)
{
p1 = p1->next;
}
while (p1 != NULL && p2 != NULL && p1 != p2)
{
p1 = p1->next;
p2 = p2->next;
}
if (p1 == p2 && p1 != NULL)
{
return true;
}
return false;
}
Node *FirstNode(List plist1,List plist2)
{
int len1 = GetLength(plist1);
int len2 = GetLength(plist2);
Node *p1 = plist1;
Node *p2 = plist2;
int pos = len1 - len2;
if (pos < 0)
{
p1 = plist2;
p2 = plist1;
pos = len2 - len1;
}
for (int i = 0; i < pos; i++)
{
p1 = p1->next;
}
while (p1 != NULL && p2 != NULL && p1 != p2)
{
p1 = p1->next;
p2 = p2->next;
}
if (p1 == p2 && p1 != NULL)
{
return p1;
}
return NULL;
}
6. O (1) 시간 에 단일 링크 의 한 노드 를 삭제 합 니 다.
/*
** ：
** i， i j i，
** i j ， j ， i
** ， ， ，
** ， （ ）， ，
** NULL
*/
void DeleteNode(List plist,List pDel)
{
if (pDel->next != NULL)
{
Node *pDelNext = pDel->next;
pDel->next = pDelNext->next;
pDel->data = pDelNext->data;
free(pDelNext);
pDelNext = NULL;
}
else
{
Node *p = plist;
while (p->next != pDel)
{
p = p->next;
}
p->next = NULL;
}
}7. 가장 빠 른 시간 안에 단일 체인 테이블 의 마지막 K 번 째 노드 를 찾 을 수 있 습 니까?
/*
** ：
** p1 p2，p1 k-1 ，p1 p2 ，
** p1 ，p k
*/
Node *Lask_K(List plist,int k)
{
Node *p1 = plist;
Node *p2 = plist;
for (int i = 0; i < k-1; i++)
{
if (p1->next != NULL)
{
p1 = p1->next;
}
else
{
return NULL;
}
}
while (p1->next != NULL)
{
p1 = p1->next;
p2 = p2->next;
}
return p2;
}8. 가장 빠 른 시간 안에 단일 체인 테이블 의 마지막 K 번 째 노드 를 삭제 합 니까?
void DelLask_K(List plist,int k)
{
assert(plist != NULL);
Node *p1 = plist;
Node *p2 = plist;
for (int i = 0; i < k; i++)
{
if (p1->next != NULL)
{
p1 = p1->next;
}
else
{
return;
}
}
while (p1->next != NULL)
{
p1 = p1->next;
p2 = p2->next;
}
Node *pDel = p2->next;
p2->next = pDel->next;
free(pDel);
pDel = NULL;
}9. 두 순서 표 의 교 집합, 병렬 집합 과 차 집합 을 구한다.
/*
** ( )：
**
** ， ，
*/
void Intersection(PSqlist sq1,PSqlist sq2,PSqlist sq3)
{
int k = 0;
for (int i = 0; i < sq1->length; i++)
{
int j = 0;
while(j < sq2->length && sq2->elem[j] != sq1->elem[i])
{
j++;
}
if (j < sq2->length)
{
sq3->elem[k++] = sq2->elem[j];
}
}
sq3->length = k;
}
/*
** ( )：
**
** ， ， 。
** ， ， ，
** ，
*/
void Union(PSqlist sq1,PSqlist sq2,PSqlist sq4)
{
for (int i = 0; i < sq1->length; i++)
{
sq4->elem[i] = sq1->elem[i];
}
sq4->length = sq1->length;
int k = sq4->length;
for (int i = 0; i < sq2->length; i++)
{
int j = 0;
while(j < sq1->length && sq1->elem[j] != sq2->elem[i])
{
j++;
}
if (j == sq1->length)
{
sq4->elem[k++] = sq2->elem[i];
}
}
sq4->length = k;
}
/*
** ( )：
**
** A B A B
** ， ， ，
** ，
*/
void Difference_Set (PSqlist sq1,PSqlist sq2,PSqlist sq5)
{
int k = 0;
for (int i = 0; i < sq1->length; i++)
{
int j = 0;
while(j < sq2->length && sq1->elem[i] != sq2->elem[j])
{
j++;
}
if (j == sq2->length)
{
sq5->elem[k++] = sq1->elem[i];
}
}
sq5->length = k;
}10. 두 개의 질서 있 는 단일 체인 표 의 교 집합, 집합 과 차 집합 을 구한다.
두 개의 질서 있 는 머리 없 는 노드 의 링크 La, Lb 는 이들 의 교 집합, 집합, 차 집합 을 구하 고 결 과 를 각각 새로운 링크 에 저장 하여 되 돌려 줍 니 다.
/*
** ( )：
** ，
** ，
** ，
** ，
*/
BNode *Intersection(BTlist plist1,BTlist plist2)
{
BTlist Lc;
Lc = NULL; //
BTlist p1 = plist1;
BTlist p2 = plist2;
BTlist p3 = Lc;
while(p1 != NULL && p2 != NULL)
{
if (p1->data < p2->data)
{
p1 = p1->next;
}
else if(p1->data > p2->data)
{
p2 = p2->next;
}
else //
{
BNode *pGet = (BNode *)malloc(sizeof(BNode));
pGet->data = p2->data;
pGet->next = NULL;
if (p3 == NULL)
{
Lc = pGet; // Lc
p3 = Lc;
}
else
{
while (p3->next != NULL)
{
p3 = p3->next;
}
p3->next = pGet;
}
//Insert_tail(&Lc,p2->data);
p1 = p1->next;
p2 = p2->next;
}
}
return Lc;
}
/*
** ( )：
** ，
** ， ，
** ， ，
** ， ，
** ，
*/
BNode *Union(BTlist plist1,BTlist plist2)
{
BTlist Lc;
Lc = NULL; //
BTlist p1 = plist1;
BTlist p2 = plist2;
while(p1 != NULL && p2 != NULL)
{
if (p1->data < p2->data)
{
Insert_tail(&Lc,p1->data);
p1 = p1->next;
}
else if(p1->data > p2->data)
{
Insert_tail(&Lc,p2->data);
p2 = p2->next;
}
else
{
Insert_tail(&Lc,p1->data);
p2 = p2->next;
p1 = p1->next;
}
}
while (p1 != NULL)
{
Insert_tail(&Lc,p1->data);
p1 = p1->next;
}
while (p2 != NULL)
{
Insert_tail(&Lc,p2->data);
p2 = p2->next;
}
return Lc;
}
/*
** ( )：
** ，
** ，
** ， ，
** ，
*/
BNode *Difference_Set(BTlist plist1,BTlist plist2)
{
BTlist Lc;
Lc = NULL; //
BTlist p1 = plist1;
BTlist p2 = plist2;
while(p1 != NULL && p2 != NULL)
{
if (p1->data < p2->data)
{
Insert_tail(&Lc,p1->data);
p1 = p1->next;
}
else if(p1->data > p2->data)
{
p2 = p2->next;
}
else
{
p1 = p1->next;
p2 = p2->next;
}
}
while (p1 != NULL)
{
Insert_tail(&Lc,p1->data);
p1 = p1->next;
}
return Lc;
}
11. 두 개의 단일 체인 표 (무질서 할 수 있 음) 의 교 집합, 집합 과 차 집합 을 구한다.
bool IsPresent(BTlist plist,int elem)
{
BTlist p = plist;
while(p != NULL)
{
if (p->data == elem)
{
return true;
}
p = p->next;
}
return false;
}
/*
** ( )：
** ，
** ， 。
*/
BNode *Intersection_1(BTlist plist1,BTlist plist2)
{
BTlist Lc;
Lc = NULL; //
BTlist p1 = plist1;
BTlist p2 = plist2;
while(p1 != NULL)
{
if (IsPresent(p2,p1->data))
{
Insert_tail(&Lc,p1->data);
}
p1 = p1->next;
}
return Lc;
}
/*
** ( )：
**
** ，
** 。
*/
BNode *Union_1(BTlist plist1,BTlist plist2)
{
BTlist Lc;
Lc = NULL; //
BTlist p1 = plist1;
BTlist p2 = plist2;
while(p1 != NULL)
{
Insert_tail(&Lc,p1->data);
p1 = p1->next;
}
while(p2 != NULL)
{
if(!IsPresent(Lc,p2->data))
{
Insert_tail(&Lc,p2->data);
}
p2 = p2->next;
}
return Lc;
}
/*
** ( )：
** ， ， 。
*/
BNode *Difference_Set_1(BTlist plist1,BTlist plist2)
{
BTlist Lc;
Lc = NULL; //
BTlist p1 = plist1;
BTlist p2 = plist2;
while(p1 != NULL)
{
if(!IsPresent(p2,p1->data))
{
Insert_tail(&Lc,p1->data);
}
p1 = p1->next;
}
return Lc;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
OS를 자작 해 보았다!요즘 너무 추워서 진짜로 동사할 것 같은 dangomushi입니다. 진짜로 춥다. 어쨌든, 우선 이 기사는 완전히 스스로 만든 OS가 아닌 것 아직 개선의 여지가 있다 중학생이 만든 것 의 전제를 근거로 한 것이 됩...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
