首先贴出线性表结构定义
1 typedef int Position; 2 typedef struct LNode *List; 3 struct LNode { 4 ElementType Data[MAXSIZE]; 5 Position Last; /* 保存线性表中最后一个元素的位置 */ 6 };
1、创建新表
1 List MakeEmpty() 2 { 3 /*创建并返回一个空的线性表*/ 4 List L; 5 L = (List) malloc(sizeof(struct LNode)); 6 return L; 7 }
2、查找元素
1 Position Find( List L, ElementType X ) 2 { 3 //返回线性表中X的位置。若找不到则返回ERROR 4 int i; 5 if( !L ){ 6 return ERROR; 7 } 8 for( i=0; i<L->Last; i++){ 9 if( L->Data[i] == X){ 10 return i; 11 } 12 } 13 return ERROR; 14 }
3、插入元素
1 bool Insert( List L, ElementType X, Position P ) 2 { 3 /*X插入在位置P并返回true。若空间已满，则打印“FULL”并返回false； 如果参数P指向非法位置，则打印“ILLEGAL POSITION”并返回false；*/ 4 int i; 5 if(!L){ 6 return false; 7 } 8 if( L->Last==MAXSIZE){ 9 printf("FULL"); 10 return false; 11 } 12 if( P<0 || P>L->Last){ 13 printf("ILLEGAL POSITION"); 14 return false; 15 } 16 for( i=L->Last; i>P; i--){ 17 L->Data[i] = L->Data[i-1]; 18 } 19 L->Data[P] = X; 20 L->Last++; 21 return true; 22 }
4、删除元素
1 bool Delete( List L, Position P ) 2 { 3 //将位置P的元素删除并返回true。若参数P指向非法位置，则打印“POSITION P EMPTY”（其中P是参数值）并返回false。 4 int i; 5 if( !L ){ 6 return false; 7 } 8 if( P>=L->Last || P<0){ 9 printf("POSITION %d EMPTY",P); 10 return false; 11 } 12 for( i=P; i<L->Last; i++){ 13 L->Data[i] = L->Data[i+1]; 14 } 15 L->Last--; 16 return true; 17 }
5、有序表二分查找（折半查找）
1 Position BinarySearch( List Tbl, ElementType K ) 2 { 3 //保证传入的数据是递增有序的。函数BinarySearch要查找K在Tbl中的位置，即数组下标（注意：元素从下标1开始存储）。 4 //找到则返回下标，否则返回一个特殊的失败标记NotFound。 5 ElementType left = 1; 6 ElementType right =Tbl->Last; 7 ElementType mid; 8 while( left<=right ){ 9 mid = (left+right)/2; 10 if( Tbl->Data[mid]>K){ 11 right = mid-1; 12 } 13 else if( Tbl->Data[mid]<K ){ 14 left = mid + 1; 15 } 16 else{ 17 return mid; 18 } 19 } 20 21 return NotFound; 22 23 }