データ構造リニアテーブルの2つの連結方式ユニオン()MergList()
5358 ワード
まず、studentという構造体を定義するとnumとnextがあります. 一つのポインター
typedef struct student
{ //
int num;
student *next;
}student,*stu;
本の第一の合併方式ユニオンvoid Union(stu &list1,stu list2) // list2 kist1 ( )
{
int temp;
int l1_len = ListLength(list1);
int l2_len = ListLength(list2);
for(int i =1;i<=l2_len;i++)
{
temp = GetElem(list2,i); // list2 i temp
if(!LocateElem(list1,temp)) // list1 list1
{
Insert(list1,temp);
}
}
}
第二の方式Merget List stu MergeList(stu list1,stu list2,stu &listc) // listc ( )
{ int i = 1,j = 1,k = 0;
int ai,bj,La_len,Lb_len;
La_len = ListLength(list1);
Lb_len = ListLength(list2);
while((i<=La_len)&&(j<=Lb_len)) //i j
{
ai = GetElem(list1,i);
bj = GetElem(list2,j);
if(ai<=bj)
{
Insert(listc,ai);
++i;
}
if(ai>bj)
{
Insert(listc,bj); // 1
++j;
}
}
while(i<=La_len) // list1
{
ai = GetElem(list1,i);
Insert(listc,ai);
++i;
}
while(j<=Lb_len) // list2
{
bj = GetElem(list2,j);
Insert(listc,bj);
++j;
}
return listc;
}
メイン関数とテスト int main()
{
stu list1,list2,listc,t;
printf(" list1:
"); //
list1 = CreatList();
printf("list2:
");
list2 = CreatList();
listc = InitList(listc);
listc = MergeList(list1,list2,listc);
Union(list1,list2);
// MergeList(list1,list2,listc); //MergeList
for(t = list1->next;t!=NULL;t = t->next)
{
printf("%d
",t->num);
}
return 0;
}
下のコードは構造体の後ろに貼って直接テストできます.stu InitList(stu L)
{
stu head = (stu)malloc(sizeof(student)); //
head->next = NULL;
head->num =0;
L = head;
return L;
}
stu CreatList() //
{
stu head,t;
head = (stu)malloc(sizeof(student));
head->num = 0;
head->next = NULL;
t = head; // t head
int temp;
while(scanf("%d",&temp)!=EOF) //EOF ctril+z
{
stu p;
p = (stu)malloc(sizeof(student)); //
p->num = temp;
t->next = p; //t( head) next
t = p; // t p t
}
t->next = NULL; // t next p->next==NULL
return head; // head
}
stu del(stu L,int x)
{
stu pre = L,p = L->next; //pre p
while(p->num!=x&&p->next!=NULL) // p p pre
{
pre = p; //pre p pre
p = p->next; //p
}
pre->next = p->next; //pre p->next
free(p);
return L;
}
int ListLength(stu L) //
{
int len = 0;
stu p = L;
while(p->next!=NULL)
{
p = p->next;
len++;
}
return len;
}
int GetElem(stu L,int n) // n
{
if(L->next==NULL){ //
return 0;
}
int num = 0;
stu p = L; // L
for(int j =1;j<=n;j++) // 1-n
{
p = p->next;
}
num = p->num;
return num;
}
int Compare(int a,int b) //
{
if(a>b)
{
return 1;
}
if(anext==NULL){
return 0;
}
stu p =L;
for(int i =1;i<=ListLength(L)+1;i++)
{
if(Compare(p->num,x)==0)
{
return 1; // 1
}
p = p->next;
}
return 0;
}
stu Insert(stu &L,int x){ //
stu pre = L,p = L->next;
if(L->next!=NULL) //L
{
while(p->numnext!=NULL) // x pre p x
{
pre = p;
p = p->next;
}
pre = pre->next; //pre
stu t;
t = (stu)malloc(sizeof(student));
t->num = x;
t->next = pre->next; // next pre->next ( )
pre->next = t; // pre->next
return L;
}
else //
{
stu t;
t = (stu)malloc(sizeof(student));
t->num = x;
t->next = NULL;
L->next = t;
return L;
}
}