엄 울 민 데이터 구조 학습: 제3 회

       

               (          )

         :
1.            "    "
2.            "    "
3.        ,   "     "
4.        ,   "     "

2.1         
	  
	    :
	1. {     } InitList(&L) 
	       :          L
	2. {    } DestroyList(&L) 
	       :    L   ; 
	       :      L
	3. {     } :                 
	   ListEmpty(L)	          
			    :    L   
			    :  L   ,    TRUE,   FALSE
	   ListLength(L)        
			    :    L   
			    :   L      
	   PriorElem(L, cur_e, &pre_e)       
			    :    L   
			    :  cur_e L   ,       ,   pre_e      ,       , pre_e   
	   NextElem(L, cur_e, &next_e)       
			    :    L   
			    :  cur_e L   ,        ,   next_e      ,       , next_e   
	   GetElem(L, i, &e)          
			    :    L   , 1 <= i <= LengthList(L)
			    :  e  L  i     
	   LocateElem(L, e, compare())            
			    :    L    , compare()       
			    :   L     e    compare()      .          ,      0
	   ListTravese(L, visit())   
			    :    L   
			    :    L         visit().   visit()  ,      
	4. {     }                
	   ClearList(&L)       
			    :    L   
			    :  L     
	   PutElem(L, i, &e)  i        
			    :    L   , 1 <= i <= LengthList(L)
			    : L  i      e  
	   ListInsert(&L, i, e)     
			    :    L   , 1 <= i <= LengthList(L) + 1
			    :  L  i           e, L    1
	   ListDelete(&L, i, &e)     
			    :    L      
			    :   L  i   ,   e    , L    1
	          ,             
	  :      A, B   
	    : 
	void union(List &La, List Lb)
	{
		La_len = ListLength(La);
		Lb_len = ListLength(Lb);
		for (i = 1; i <= Lb_len; i++)
		{
			//  Lb  i       e
			GetElem(Lb, i, e);
			//La     e       ,    
			if (!LocateElem(La, e, equal()))
			{
				ListInsert(La, ++La_len, e);
			}
		}
	}


	  :       B     
	    : 
	void purge(List &La, List Lb)
	{
		//     Lb       B     
		//      La,  La    Lb          
		InitList(La);//        La
		La_len = ListLength(La);
		Lb_Len = ListLength(Lb);

		for (i = 1; i <= Lb_len; i++)
		{
			//       i   
			GetElem(Lb, i, e);
			//   a    ,    
			if (!LocateElem(La, e, equal()))
			{
				++La_len;
				ListInsert(La, La_len, e);
			}
		}
	}

	  Lb      ,         : 
	void purge(List &La, List Lb)
	{
		//     Lb       B     
		//      La,  La    Lb          
		InitList(La);//        La
		La_len = ListLength(La);
		Lb_Len = ListLength(Lb);

		for (i = 1; i <= Lb_len; i++)
		{
			//       i   
			GetElem(Lb, i, e);
			//         a              
			if (ListEmpty(La) || !equal(en, e))
			{
				ListInsert(La, ++La_len, e);
				en = e;
			}
		}
	}//       n

	  :     "               "   La Lb,      Lc       
	1.    La Lb       ai bj;
	2.  ai<=bj,   ai   Lc ,    bj   Lc 
	    :
	void MergeList(List La, List Lb, List &Lc)
	{
		InitList(Lc);
		i = j = 1; k = 0;
		La_len = ListLength(La);
		Lb_len = ListLength(Lb);
		while ((i <= La_len) && (j <= Lb_len))//    ,        List      ,         ,            
		{
			//La Lb   
			GetElem(La, i, ai);
			GetElem(Lb, j, bj);
			if (ai <= bj)
			{
				ListInsert(Lc, ++k, ai);
				++i;
			} else {
				ListInsert(Lc, ++k, bj);
				++j;
			}
		}
		while (i <= La_len)//               ,           
		{
			GetElem(La, i++, ai);
			ListInsert(Lc, ++k, ai);
		}
		while (j <= Lb_len)
		{
			GetElem(Lb, j++, bj);
			ListInsert(Lc, ++k, bj);
		}
	}
	

2.2          -     
	                          
	                    ,      ,                    
	     C    :		
	#define LIST_INIT_SIZE 80 //             
	#define LISTINCREMENT 10 //            

	typedef struct 
	{
		ElemType *elem; //      
		int length; //    
		int listsize; //         ( sizeof(ElemType)   
	}SqList; //     

               

         ,     ,              

        ,    ...

         ,           ,        ,            

      ,  ...        ...     ...    ,       ,     OK

            

         ,          ,               ...

        ,              ...

   C      ,           

        ...       ...     ...