第1章第2節練習問題17同じ値を用いて新しい単鎖表を形成する
問題の説明
AとBは2つの単一チェーンテーブル(先頭ノード)であり、要素は増分順であるとする.AとBの共通要素から単一チェーンテーブルCを生成するアルゴリズムを設計し、A、Bのノードを破壊しないことを要求する.
アルゴリズム思想
本アルゴリズムは実際には第1章第2節の練習問題16と並べ替え逆順の単鎖表と大きな違いはなく,同様に2枚の鎖表を遍歴し,同じ値を持つノードを1回複製し,その後複製した新しいノードを尾挿法で単鎖表の方程式を確立して新しい単鎖表を形成する.
アルゴリズムの説明
具体的なコードは添付ファイルを参照してください.
アタッチメント
AとBは2つの単一チェーンテーブル(先頭ノード)であり、要素は増分順であるとする.AとBの共通要素から単一チェーンテーブルCを生成するアルゴリズムを設計し、A、Bのノードを破壊しないことを要求する.
アルゴリズム思想
本アルゴリズムは実際には第1章第2節の練習問題16と並べ替え逆順の単鎖表と大きな違いはなく,同様に2枚の鎖表を遍歴し,同じ値を持つノードを1回複製し,その後複製した新しいノードを尾挿法で単鎖表の方程式を確立して新しい単鎖表を形成する.
アルゴリズムの説明
LinkList CreatNew(LNode *head1, LNode *head2, LNode *head)
{
LNode *p=head1->next;
LNode *q=head2->next;
LNode *r=head;
LNode *L;
while(p&&q){
if(p->data==q->data){
L=(LNode*)malloc(sizeof(LNode));
L->data=p->data;
r->next=L;
r=L;
p=p->next;
q=q->next;
}else if(p->data<q->data){
p=p->next;
}else{
q=q->next;
}
}
r->next=NULL;
return head;
}
具体的なコードは添付ファイルを参照してください.
アタッチメント
#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
LinkList CreatList(LNode*);
LinkList CreatNew(LNode*,LNode*,LNode*);
void Print(LNode*);
int main(int argc, char* argv[])
{
LNode *head1;
head1=(LNode*)malloc(sizeof(LNode));
head1->next=NULL;
head1=CreatList(head1);
LNode *head2;
head2=(LNode*)malloc(sizeof(LNode));
head2->next=NULL;
head2=CreatList(head2);
LNode *head;
head=(LNode*)malloc(sizeof(LNode));
head=CreatNew(head1, head2, head);
Print(head1);
Print(head2);
Print(head);
return 0;
}
//
LinkList CreatList(LNode* head)
{
LNode *L;
LNode *r=head;
ElemType x;
scanf("%d",&x);
while(x!=999){
L=(LNode*)malloc(sizeof(LNode));
L->data=x;
r->next=L;
r=L;
scanf("%d",&x);
}
return head;
}
//
LinkList CreatNew(LNode *head1, LNode *head2, LNode *head)
{
LNode *p=head1->next;
LNode *q=head2->next;
LNode *r=head;
LNode *L;
while(p&&q){
if(p->data==q->data){
L=(LNode*)malloc(sizeof(LNode));
L->data=p->data;
r->next=L;
r=L;
p=p->next;
q=q->next;
}else if(p->data<q->data){
p=p->next;
}else{
q=q->next;
}
}
r->next=NULL;
return head;
}
//
void Print(LNode *head)
{
LNode *p=head->next;
while(p){
printf("%4d",p->data);
p=p->next;
}
printf("
");
}