リニアテーブルの記憶および関連動作の実現
//以前の実験報告は見つけられました.まだQQ空間のスクリーンショットを使わないと分かりました.コードが悪いです.それは私がまだ初心者なので.
一、順番に保存します
この線形表は順序で保存して、初期化、建設表、検索、削除、印刷、クリア、廃棄を実現しました.
この線形表はチェーン式記憶を採用して、初期化、建設表、検索、削除、印刷、クリア、廃棄を実現しました.
一、順番に保存します
この線形表は順序で保存して、初期化、建設表、検索、削除、印刷、クリア、廃棄を実現しました.
--------------- ------------------
void InitList(sqList *L)
{
(*L).elem = (int*)malloc(LIST_INIT_SIZE*sizeof(int));
// ,
if(!(*L).elem) exit(0);//
(*L).length =0;// ,
(*L).listsize =LIST_INIT_SIZE;//
}//
void creatlist(sqList *L)
{
int n,x,i;
printf("
");
scanf("%d",&n);
printf(" :
");
for(i=1;i<=n;i++)//
{
scanf("%d",&x);
(*L).elem[i] = x;
}
(*L).length = n;//
}//
int destroyList(sqList *L){
int i;
if ((*L).elem)// ,
{
free((*L).elem);
(*L).elem = NULL;
printf("
-- --
");
}
else {printf("
-- --
");return FALSE;}//
return OK;
}//
void clearlist(sqList *L){
(*L).length=0; // 0
printf("
-- --
");// , 0 ( )
}//
int ListEmpty(sqList *L){
if ((*L).length==0)// ,
{
printf("
!!
");
return TRUE;
}
else
{
printf("
!!
");
return FALSE;
}
}//
int ListLength(sqList *L){
printf("
-- :%d--
",(*L).length);// , length
return ((*L).length);
}//
int GetElem(sqList *L,int i,int e)
{
if (i<1||i>(*L).length) {return 0;}
// i , , ERROR
else e = (*L).elem[i];// , elem[i]
return e;
}//
int LocateELem(sqList *L,int i,int e)
{
for (i=1;i <= (*L).length;i++)// (creatlist) , 1
if ((*L).elem[i]==e) return i;// 1
if(i = (*L).length&&(*L).elem[i] != e)
return ERROR;// 0
}//
int priorelem(sqList *L,int cur_e,int pre_e){
int i;
if((*L).elem == NULL)// ,
{
printf("-- --
");
exit(0);
}
for(i=1;((*L).elem[i]!=cur_e)&&(i<=(*L).length);i++);// for
// elem[i]=cur_e
if(i<=(*L).length)
printf("
-- :%d--
",i);//
else
{printf("
-- --
");return(FALSE);}
if((*L).elem[i] == cur_e)
pre_e = (*L).elem[i-1];//
else
{printf("
--%d --
",cur_e);return (FALSE);}
return pre_e;
}//
int nextelem(sqList *L,int cur_e,int next_e){
int i=1;
if((*L).elem == NULL)
{
printf("--is null--
");
exit(0);
}
for(i=1;(*L).elem[i]!=cur_e&&i<=(*L).length;i++);
if(i<=(*L).length)
printf("
-- :%d--
",i);
if(i (*L).length+1) {
printf("
-- , --
");return ERROR;}
if((*L).length >= (*L).listsize){
newbase=(int*)realloc((*L).elem,
((*L).listsize+LISTINCREMENT)*sizeof(int));
// ,
if(!newbase) exit(0);// ,
(*L).elem = newbase;// ( )
(*L).listsize += LISTINCREMENT; //
}
q = &((*L).elem[i]);//q
++(*L).length;// : , length-1
for(p = &((*L).elem[(*L).length-1]);p>=q;--p) *(p+1) = *p;// ( )
*q = e;
return OK;}
int ListDelete_sq(sqList *L,int i,int e){
if(i <1||i>(*L).length ) {
printf("
-- , --
");return -1;}
p = &((*L).elem[i]);//
e = *p;// e
q = (*L).elem + (*L).length;//
for(++p;p <= q;++p) *(p-1) = *p;//
--(*L).length;
return e;
}// i , e
int ListTraverse(sqList *L){
int i;
printf("
:
");
printf(" | ");
for(i=1;i<=(*L).length;i++)
{ if((*L).elem[i]<100)
printf("%2d ",i);
else if( (*L).elem[i] <1000)
printf("%3d ",i);
}
printf("
——————————————————————
");
printf(" | ");
for(i=1;i<=(*L).length;i++)//
{ if((*L).elem[i]<100)
printf("%2d ",(*L).elem[i]);
else if( (*L).elem[i] <1000)
printf("%3d ",(*L).elem[i]);
}
printf("
");
return OK;
}
—————————— ( )————————————
void main()
{
int cur_e;
int pre_e;
int next_e;
int e;
int i;
sqList myl;
/* */
sqList *L = &myl;//
InitList(L);//
creatlist(L);//
ListTraverse(L);//
/* */
printf("
, :
");
scanf("%d",&cur_e);
pre_e = priorelem(L,cur_e,pre_e);
if(pre_e != FALSE)
printf("--%d :%d--",cur_e,pre_e);
/* */
printf("
, :
");
scanf("%d",&cur_e);
next_e = nextelem(L,cur_e,next_e);
if(next_e != FALSE)
printf("--%d :%d--",cur_e,next_e);
/* */
ListLength(L);
/* */
printf("
:
");
scanf("%d",&i);
e = GetElem(L,i,e);
if(e == 0)
printf("
-- , --
");
else
printf("
-- %d :%d--
",i,e);
/* */
printf("
, :
");
scanf("%d",&e);
i = LocateELem(L,i,e);
if(i == 0)
printf("
-- , --
");
else
printf("
:%d
",i);
/* */
printf("
:
");
scanf("%d%d",&e,&i);
ListInsert_sq(L,i,e);
ListTraverse(L);
/* */
printf("
:
");
scanf("%d",&i);
e = ListDelete_sq(L,i,e);
if(e != -1)
printf("
-- %d :%d --
",i,e);
ListTraverse(L);
}
二.チェーン記憶この線形表はチェーン式記憶を採用して、初期化、建設表、検索、削除、印刷、クリア、廃棄を実現しました.
DAT *InitList(DAT *head)//
{
head = (DAT *)malloc(LEN);
if(!head)
{printf("
-- --
");exit(FALSE);}
head ->next = NULL;
return head;
}
DAT *creatList(DAT *head)//
{
DAT *p1,*p2;
char ch;
int n = 1;
head = (DAT *)malloc(LEN);
p1 = p2 = (DAT *)malloc(LEN);
if(p1 != NULL)
{
printf("
:
");
scanf("%d",&p1->data);//p1
head -> next = p1;// : //p2 = p1; ? p1,p2 !
printf("
(y/any other keys to exit)?
");
getchar();
scanf("%c",&ch);
while(ch == 'Y'||ch == 'y')
{
printf("
:
");
p1 = (DAT *)malloc(LEN);
if(p1 != NULL)
scanf("%d",&p1->data);
p2 -> next = p1;
p2 = p1;
printf("
(y/any other keys to exit)?
");
getchar();
scanf("%c",&ch);
}
p2 -> next = NULL;//p2 , next ,
printf("
-- --
");
}
return head;
}
int ClearList(DAT *head) // ,
{
if(head == NULL)
{
printf("
-- --
");
return FALSE;
}
DAT *p,*q;
p = head -> next;
while(p)
{
q=p->next;// q p
printf("
-- :%d--
",p -> data);
free(p);
p=q;// q = p -> next, p ,
}// p ,
head -> next = NULL; //
return TRUE;
}
DAT *destroyList(DAT *head)// {
if(head == NULL)
{
printf("
-- , --
");
exit(FALSE);
}
DAT *p;
p = head;
while(head)
{
p = head -> next;
free(head);//
head = p;
}
printf("
-- --
");
return head;
}
int ListLength(DAT *head)
{
DAT *p;
int i = 0;
p = head -> next;
while(p)
{
i++;
p = p -> next;
}
printf("
-- :%d--
",i);
return i;
}
void ListTraverse(DAT *head)//
{
DAT *p = head -> next;
DAT *q = p;//
int n = 0;
int length;
length = ListLength(head);
if(p)
{
printf("
| ");
for(n = 1;n <= length;n++)
{
if(q -> data <10)
printf("%d ",n);
else if(q -> data <100)
printf("%2d ",n);
else
printf("%3d ",n);
q = q -> next;
}
printf("
------------------------------------
");
printf(" | ");
do
{
printf("%d ",p -> data);
p = p -> next;
}
while(p);
}
printf("
");
}
int GetElem(DAT *head,int i,int e)
{
int n = 1;
DAT *p;
p = head ->next;
while(p && n < i )// p
{
p = p -> next;//
n++;
}
if(!p || n > i)
{printf("
-- --
");return FALSE;}
e = p -> data;
return e;
}
int LocateElem(DAT *head,int e)// e ,
{
DAT *p;
int i = 1;
printf("
:
");
scanf("%d",&e);
p = head -> next;
while(p)
{
if(p -> data == e)
{
printf("
--%d :%d--
",e,i);
return i;
}
else
p = p -> next;
i++;
}
printf("
-- --
"); return 0;
}
int PirrorElem(DAT *head,int cur_e,int pre_e)//
{
printf("
, :
");
scanf("%d",&cur_e);
if(head == NULL)
{
printf("
-- --
");
return FALSE;
}
DAT *p,*q;
q = head -> next;//q
while(p)
{
p = q -> next;//p q
if( q -> data == cur_e)//cur_e ,
{
printf("
-- , --
");
return FALSE;
}
if(p -> data == cur_e)// p cur_e, q
{
pre_e = q -> data;
printf("
--%d :%d--
",cur_e,pre_e);
return pre_e;
}
else
{
if( p -> next != NULL)
q = p;//p,q ,q p
else// p NULL ,
{
printf("
-- --
");
return FALSE;
}
}
}
}
int NextElem(DAT *head,int cur_e,int next_e)//
{
DAT *p,*q;
printf("
, :
");
scanf("%d",&cur_e);
p = head -> next;
while(p)
{
q = p -> next;
if( p -> data == cur_e && p -> next != NULL)//p ,
{
next_e = q -> data;
printf("
-%d :%d--
",cur_e,next_e);
return next_e;
}
if( p -> data != cur_e)
{
p = q;//p -> next ,p,q
if( p -> next == NULL && p -> data == cur_e )//
{
printf("
-- --
");
return FALSE;
}
if( p -> next == NULL && p ->data != cur_e)// cur_e
{
printf("
-- --
");
return FALSE;
}
}
}
}
DAT *ListInsert(DAT *head,int i,int e)// i e
// , head
{
printf("
");
scanf("%d%d",&i,&e);
DAT *p = head;// n = 0 ,head
DAT *q;
int n = 0;
while(p != NULL && n < i-1)// i
{
p = p -> next;// p , n=1
n++;//n = 1
}// n=i-1,p i
if(p == NULL || n > i-1)//i ( , ) ,
{
printf("
-- , --
");
return head;
}
q = (DAT *)malloc(LEN);//
q -> data = e;//
q -> next = p->next;// (p -> next i ), i , i
// ,q -> next == NULL
p -> next = q;// p ,
printf("
--%d %d --
",e,i);
return head;// ,
}
DAT *ListInsert_last(DAT *head,int e)//
// , head
{
int leng = ListLength(head);
DAT *p = head;// n = 0 ,head
DAT *q;
int n = 0;
while(p != NULL && n < leng)// ,
{
p = p -> next;// p , n=1
n++;//n = 1
}// n=leng,p
if(p == NULL || n > leng)//i ( , ) ,
{
printf("
-- , --
");
return head;
}
q = (DAT *)malloc(LEN);//
q -> data = e;//
q -> next = p->next;// (p -> next i ), i , i
// ,q -> next == NULL
p -> next = q;// p ,
printf("
--%d --
",e);
return head;// ,
}
DAT *ListDelete(DAT *head,int i,int e)
{
printf("
:
");
scanf("%d",&i);
DAT *p = head;
DAT *q;
int n = 0;
while(p -> next != NULL && n < i - 1)// , p
{
p = p -> next;
n++;
}
if(p -> next == NULL || n > i -1)//i ( )
{
printf("
-- , --
");
return head;
}
q = p -> next;//q p
p -> next = q -> next;// p q , q , q
e = q -> data;// e
free(q);
printf("
-- %d :%d --
",i,e);
return head;
}
————————— ——————————
void main()
{
DAT *L1,*L2;
int i,e;
int cur_e;
int pre_e;
int next_e;
//
L1 = InitList(L1);//
L2 = InitList(L2);
//L1 = ListInsert(L1,i,e);
L1 = creatList(L1);//
ListTraverse(L1);
L2 = creatList(L2);
ListTraverse(L2);
//ListTraverse(L1);//
ListLength(L1);//
//ClearList(L1);//
//ListTraverse(L1);//
//destroyList(L1);
//ListTraverse(L1);
//
/*printf("
:
");
scanf("%d",&i);
e = GetElem(L1,i,e);
if(e != FALSE)
printf("
-- %d :%d--
",i,e);*/
//
//PirrorElem(L1,cur_e,pre_e);
//
//NextElem(L1,cur_e,next_e);
//
//L1 = ListInsert(L1,i,e);
//
//L1 = ListDelete(L1,i,e);
// ( , )
/*printf("
:
");
scanf("%d",&e);
L1 = ListInsert_last(L1,e);
ListTraverse(L1);*/
//
MergerLinks(L1,L2);//
}
三.一方向チェーン基本関数の運用は、チェーンを結合する(並べ替えなし)void MergerLinks(DAT *L1,DAT *L2)
{
DAT *L3 = NULL;
DAT *p1 = NULL;
DAT *p2 = NULL;
DAT *p3 = NULL;
DAT *p4 = NULL;
DAT *p5 = NULL;
int n = 0;
int m = 0;
int leng1;
int leng2;
int leng3;
int i = 0,j = 0,k = 0;
p1 = L1;
p2 = L2;
leng1 = ListLength(L1);
leng2 = ListLength(L2);//
L3 = (DAT *)malloc(sizeof(DAT));// ,
p3 = p4 = (DAT *)malloc(sizeof(DAT));
if(leng1 >= leng2)
{
for(i = 0;i < leng2;i++)
{
if(p2 -> next != NULL)
{p2 = p2 -> next;}
for(j = 0; j < leng1;j++)
{
if(p1 -> next != NULL)
{
p1 = p1 -> next;
}
else//p1 -> next ==NULL
{
p1 = L1 -> next;// p1 L1
}
if(p2 -> data != p1 -> data)//
{
printf("
--%d--
",p2->data);
printf("
-|%d|-
",p1->data);
m++;
printf("
m = %d
",m);
if(m == leng1)// ,
{
p3 -> data = p2 -> data;
if(p3 -> data != NULL)
{
n++;
if(n == 1)
L3 -> next = p3;
else
p4 -> next = p3;
p4 = p3;
p3 =(DAT*)malloc
(sizeof(DAT));
}
p4 -> next = NULL;
m = 0;// m
}
}
}
if(m next = NULL;
if(L3 -> next != NULL)
{
printf("
:
");
ListTraverse(L3);
p5 = L3 -> next;
for(k = 0;k < n;k++)//n
{
if(p5 -> data != NULL)
{
leng1 = leng1 +1;
L1 = ListInsert_last(L1,p5 -> data);//
}
p5 = p5 -> next;
}
}
printf("
-- :--
");
ListTraverse(L1);
}
else//leng1 < leng1
{
for(i = 0;i < leng1;i++)
{
if(p1 -> next != NULL)
{p1 = p1 -> next;}
for(j = 0; j < leng2;j++)
{
if(p2 -> next != NULL)
{ p2 = p2 -> next;}
else
{p2 = L2 -> next;}
if(p1 -> data != p2 -> data)//
{
m++;
if(m == leng2)// ,
{
p3 -> data = p1 -> data;
if(p3 -> data != NULL)
{
n++;
if(n == 1)
L3 -> next = p3;
else
p4 -> next = p3;
p4 = p3;
p3 = (DAT*)malloc
(sizeof(DAT));
}
p4 -> next = NULL;
m = 0;// m
}
}
}
if(m next = NULL;
if(L3 -> next != NULL)
{
ListTraverse(L3);
p5 = L3 -> next;
for(k = 0;k < n;k++)//n
{
if(p5 -> data != NULL)
{
leng2 = leng2 +1;
L2 = ListInsert_last(L2,p5 -> data);
}
p5 = p5 -> next;
}
}
printf("
-- :--
");
ListTraverse(L2);
}
}