1、线性表的定义 :
线性表是最常用且最简单的一种数据结构,简言之,一个线性表是n个数据元素的有限序列。
1、 线性表长度:线性表中元素的个数n ( n >= 0)定义为线性表的长度
2、 空表:线性表长度 = 0
2、线性表的操作:
1、插入
2、追加(特殊形式的插入)
3、删除
1、插入
标号(看作数组名,但不是数组):
编号(pos):
2、追加
追加(特殊形式的插入):
3、删除
源代码:
1 /* 1、 线性表 */ 2 /* 3 一些理解: 4 1、在对线性表删除的时候,必定要进行地址的变换,而最后一个元素交换后必定还是保留的, 5 但是可以在 显示全表 和 显示表中单个元素中 做限制,让其不影响。例如: 6 LIST : 1, 2, 3, 4, 5 7 DELETE POS(2): 1, 3, 4, 5 8 而LSIT(5)还是5,虽然它赋值给 LSIT(4),但是做了限制后,并不影响,而在追加或增插入中,会被自动覆盖。 9 2、而且在插入和追加中,需要让使用长度加1;同理在删除中,须要让使用长度减1。 10 3、有些函数中的返回值 是 TURE = 1, 这样做的目的是通过函数可以进行判断,从而使代码更健壮。 11 */ 12 13 #include <stdio.h> 14 #include <malloc.h> 15 #include <stdlib.h> 16 17 #define MAXSIZE 10 //本来是准备用于表的初始化,给予固定的表最大长度,但是没用 18 #define TURE 1 19 #define FALSE 0 20 21 struct List{ 22 int *pBase; //线性表的首地址 23 int cnt; //使用长度 24 int len; //最大长度 25 26 }; 27 28 typedef struct List Sqlist; //别名 Sqlsit 等价于 struct List 29 30 31 void Init_List( Sqlist *L, int length ); //初始化某个线性表,自定义长度 32 void Del_List( Sqlist *L ); //销毁某个线性表 33 void Cle_List( Sqlist *L ); //重置存在的线性表为空表 34 35 int List_isEmpty( Sqlist *L ); //判断线性表是否为空表 36 int List_isFull( Sqlist *L ); //判断线性表是否为满表 37 38 void List_ShowAll( Sqlist *L ); //显示表中所有元素 39 int List_ShowOne( Sqlist *L, int pos ); //显示表中第几个元素 40 int List_Insert( Sqlist *L, int pos, int elem ); //向表pos位置中插入一个元素,pos编号从1开始 41 int List_Delete( Sqlist *L, int pos, int *Pelem ); //往表中删除pos位子的一个元素并获得删除的值 42 int List_Append( Sqlist *L, int elem, int *Pelem ); //往表中追加一个elem的值并获得增加的值 43 int List_GetElem( Sqlist *L, int pos, int *Pelem ); //获得表中pos位子的元素 44 45 int List_Length( Sqlist *L ); //返回表最大长度 46 int List_ElemNum( Sqlist *L ); //返回表中元素个数 47 48 49 50 int main(void) 51 { 52 Sqlist L; 53 int val; 54 Init_List(&L,10); 55 List_Insert( &L, 1, 1 ); 56 List_Insert( &L, 2, 22 ); 57 List_Insert( &L, 3, 3 ); 58 List_Insert( &L, 4, 4 ); 59 List_Insert( &L, 5, 5 ); 60 List_Insert( &L, 6, 6 ); 61 62 List_ShowAll( &L ); 63 List_ShowOne( &L, 2 ); 64 if ( List_Append( &L, 99, &val ) ) 65 printf("追加的是%d ", val); 66 if ( List_Append( &L, 88, &val ) ) 67 printf("追加的是%d ", val); 68 if ( List_Append( &L, 77, &val )) 69 printf("追加的是%d ", val); 70 List_ShowAll( &L ); 71 72 List_GetElem( &L, 6, &val ); 73 printf("获取到的元素是%d ", val); 74 val = List_Length( &L ); 75 printf("表长为%d ",val); 76 val = List_ElemNum( &L ); 77 printf("表中元素数量为%d ",val); 78 79 //if( List_Delete( &L, 2, &val) ) 80 //{ 81 // printf("删除的元素是%d ", val); 82 // List_ShowOne( &L, 2 ); 83 // List_ShowOne( &L, 5 ); 84 // List_ShowOne( &L, 6 ); 85 // List_ShowAll( &L ); 86 //} 87 88 return 0; 89 } 90 91 void Init_List( Sqlist *L, int length ) 92 { 93 L->pBase = ( int *)malloc( sizeof(int) * length ); //申请动态内存 94 if( L->pBase == NULL ) //动态内存分配检测 95 { 96 printf("动态内存分配错误! "); 97 exit(-1); //中止程序 98 } 99 else 100 { 101 L->len = length; 102 L->cnt = 0; 103 } 104 return; 105 } 106 107 void Del_List( Sqlist *L ) 108 { 109 free(L); //销毁申请的动态内存 110 } 111 112 void Cle_List( Sqlist *L ) 113 { 114 L->cnt = 0; //把表的使用长度重置为0 115 } 116 117 int List_isEmpty( Sqlist *L ) 118 { 119 if( L->cnt == 0 ) 120 return TURE; 121 else 122 return FALSE; 123 } 124 125 int List_isFull( Sqlist *L ) 126 { 127 if( L->cnt == L->len ) 128 return TURE; 129 else 130 return FALSE; 131 } 132 133 void List_ShowAll( Sqlist *L ) 134 { 135 int i=0; 136 if( List_isEmpty(L) ) 137 printf("线性表为空 "); 138 else 139 { 140 //while( i < L->cnt ) //两种循环方法都行 141 // printf("%d ", L->pBase[i++]); 142 printf("全表为:"); 143 for ( i=0; i<L->cnt; ++i) 144 printf("%d ", L->pBase[i]); 145 printf(" "); 146 } 147 } 148 149 int List_ShowOne( Sqlist *L, int pos ) 150 { 151 if ( List_isEmpty(L) ) //判断是否为空表 152 { 153 printf("线性表为空 "); 154 } 155 if ( pos < 1 || pos > L->cnt ) //判断显示位置是否错误 156 { 157 printf("显示位置不正确 "); 158 return FALSE; 159 } 160 else 161 { 162 printf("表中第%d个元素是%d ", pos, L->pBase[pos-1] ); 163 } 164 return 0; 165 } 166 167 int List_Insert( Sqlist *L, int pos, int elem ) //pos从1开始 168 { 169 int i = 0; 170 if ( List_isFull(L) ) 171 { 172 printf("表已经满了,无法插入 "); 173 return FALSE; 174 } 175 if ( pos < 1 || pos > L->len ) 176 { 177 printf("插入位子不对,无法插入 "); 178 return FALSE; 179 } 180 for ( i = L->cnt ; i >= pos ; i-- ) //插入算法 181 { 182 L->pBase[i+1] = L->pBase[i]; 183 } 184 L->pBase[i] = elem; 185 L->cnt++; //表使用长度加1 186 187 return TURE; 188 } 189 190 int List_Delete( Sqlist *L, int pos, int *Pelem ) 191 { 192 int i = 0; 193 if ( List_isEmpty(L) ) 194 { 195 printf("空表无法删除元素! "); 196 return FALSE; 197 } 198 if ( pos < 1 || pos > L->cnt ) 199 { 200 printf("删除位置不对! "); 201 return FALSE; 202 } 203 *Pelem = L->pBase[pos-1]; //删除的元素通过指针获取 204 for( i = pos; i < L->cnt; ++i ) //删除算法 205 { 206 L->pBase[i-1] = L->pBase[i]; 207 } 208 (L->cnt)--; //表使用长度减1 209 210 return TURE; 211 } 212 213 int List_Append( Sqlist *L, int elem, int *Pelem ) 214 { 215 if( List_isFull(L) ) 216 { 217 printf("表格已满,无法追加元素 "); 218 return FALSE; 219 } 220 *Pelem = elem; 221 L->pBase[L->cnt] = elem; 222 L->cnt++; 223 224 return TURE; 225 } 226 227 228 int List_GetElem( Sqlist *L, int pos, int *Pelem ) 229 { 230 if ( pos < 1 || pos > L->cnt ) 231 { 232 printf("查询位置不对 "); 233 return FALSE; 234 } 235 *Pelem = L->pBase[pos-1]; //通过指针获取追加的元素 236 237 return TURE; 238 } 239 240 int List_Length( Sqlist *L ) 241 { 242 return L->len; 243 } 244 245 int List_ElemNum( Sqlist *L ) 246 { 247 return L->cnt; 248 }