datas.cpp

线形表的顺序存储结构算法 ＶＣ＋＋６．０下开发～！

#include<stdlib.h>

#include<stdio.h>

enum status{OVERFLOW=0 , OK};

#define  LIST_INIT_SIZE     100  
                                      // 线性表存储空间的初始分配量
typedef struct {
					int      *elem;
					int      length;
					int      listsize;
				}SqList;

status InitList_Sq( SqList& L ) {  
                                        // 构造一个空的线性表 

								L.elem = (int*) malloc (LIST_INIT_SIZE*sizeof (int));
								if (!L.elem)  exit (OVERFLOW);    
																 // 存储分配失败
										L.length = 0;                                      
																 // 空表长度为零
										L.listsize = LIST_INIT_SIZE;           
																// 初始存储容量
								return OK;	
								}																
									// InitList_Sq



//status ListInsert_Sq(SqList &L, int i, int e) 
		//			{
															    	// 在顺序表L的第 i 个元素之前插入新的元素e,
															     	// i 的合法范围为  1≤i≤L.length+1
		//			int *q,*p;
			//		q = &(L.elem[i-1]);							    // q 指示插入位置
			//		for (p = &(L.elem[L.length-1]); p >= q;  --p)  
			//				*(p+1) = *p;						    // 插入位置及之后的元素右移
			//		*q = e;											// 插入e
			//		++L.length;										// 表长增1
			//		return OK;
//
			//		} // ListInsert_Sq            


void  MergeList_Sq(SqList La ,SqList Lb,SqList &Lc)
				{
																				//已知顺序线性表La和Lb的元素按值非递减排列
																				//归并La和Lb得到新的顺序表Lc，Lc的元素也按值非递减排列
					int *pa,*pb,*pc,*pa_last,*pb_last;

					pa=La.elem; pb=Lb.elem;										// pa, pb指示La表和Lb表第一个元素
					Lc.listsize=Lc.length=La.length+Lb.length;
					pc=(int*)malloc(Lc.listsize* sizeof(int));//
						
					Lc.elem=pc;//
					if(!Lc.elem) exit(OVERFLOW);
//
					pa_last=La.elem+La.length-1;								// pa_last指示La表最后一个元素
					pb_last=Lb.elem+Lb.length-1;								// pb_last指示Lb表最后一个元素

					while (pa<=pa_last&&pb<=pb_last)
							{  
								if (*pa<=*pb) *pc++=*pa++;
								else *pc++=*pb++ ;
							}
					while (pa<=pa_last) 
								*pc++=*pa++ ;									 // 插入 La 表中剩余元素
					while (pb<=pb_last) 
								*pc++=*pb++ ;									 // 插入 Lb 表中剩余元素
}																				 // MergeList



void Input_list(SqList &L)           //输入一个线性表；
				{
					int *pa=L.elem,i;
					printf("Please input a list:");
					scanf("%d",&i);
					while (i)
					{
						*pa++=i;
						L.length++;
						scanf("%d",&i);
					}
}



void Output_list(SqList &L)			//输出一个线性表；
				{
					int *pa=L.elem;
					int *pa_list=L.elem+L.length-1;
					printf("\n");
					while (pa<=pa_list)
						printf("%d\t",*pa++);
					printf("\n");
				}



void main()
{
	SqList La,Lb,Lc;
	InitList_Sq(La);
	InitList_Sq(Lb);
	InitList_Sq(Lc);
	Input_list(La);
	Input_list(Lb);
	MergeList_Sq(La,Lb,Lc);
	Output_list(Lc);
}