随笔-126  评论-247  文章-5  trackbacks-0

线性表是最常用且最简单的一种数据结构,一个线性表是 N 个数据元素的有限序列。

顺序表存储结构能够容易的实现随机存取线性表中的第 i 个数据元素,但是插入和删除表中的数据元素时,需要移动大量的数据元素。

因此,顺序表存储结构适用于数据相对稳定的线性表。

环境:eclipse,MinGW 5.1.4

File : list.h
  1 /**
  2  * =================================
  3  * @描述: List 头文件
  4  * @作者: fancy
  5  * @日期: 2012-11-02
  6  * @联系: fancydeepin@yeah.net
  7  * =================================
  8  */
  9 
 10 #include <stdio.h>
 11 #include <malloc.h>
 12 
 13 typedef int Data;
 14 typedef int Status;
 15 #define OK 1
 16 #define NO 0
 17 #define YES 1
 18 #define ERROR 0
 19 #define OVERFLOW -1
 20 #define OutOfBound -1
 21 #define LIST_INIT_SIZE 25
 22 #define LIST_INCREMENT_COUNT 15
 23 
 24 //线性表结构
 25 struct List {
 26     int size;    //线性表长度大小
 27     int count;    //线性表元素计数
 28     Data *data; //数据元素
 29 };
 30 
 31 /**
 32  * 描述: 初始化线性表
 33  * 参数: &L         线性表
 34  * 参数: length    长度
 35  * 返回: ERROR/OK
 36  */
 37 Status initList(List &L, int length){
 38 
 39     L.data = (Data*)malloc(length * sizeof(Data));
 40     if(!L.data){
 41         return ERROR;
 42     }
 43     L.count = 0;
 44     L.size = length;
 45     return OK;
 46 }
 47 
 48 /**
 49  * 描述: 初始化线性表
 50  * 参数: &L     线性表
 51  * 返回: ERROR/OK
 52  */
 53 Status initList(List &L){
 54 
 55     return initList(L, LIST_INIT_SIZE);
 56 }
 57 
 58 /**
 59  * 描述: 创建指定长度大小的线性表
 60  * 参数: size       长度
 61  * 返回: List
 62  */
 63 List newList(int size){
 64 
 65     List L;
 66     if(initList(L, size) == OK){
 67         return L;
 68     }
 69     exit(ERROR);
 70 }
 71 
 72 /**
 73  * 描述: 创建线性表
 74  * 返回: List
 75  */
 76 List newList(){
 77 
 78     return newList(LIST_INIT_SIZE);
 79 }
 80 
 81 /**
 82  * 描述: 判断线性表是否为空
 83  * 参数: &L     线性表
 84  * 返回: YES/NO
 85  */
 86 Status isEmptyList(List &L){
 87 
 88     if(!L.data){
 89         return YES;
 90     }
 91     return NO;
 92 }
 93 
 94 /**
 95  * 描述: 将数据存储到线性表中的index位置
 96  * 参数: &L     线性表
 97  * 参数: data    数据
 98  * 返回: ERROR/OK
 99  */
100 Status putValue(List &L, int index, Data data){
101 
102     if(!isEmptyList(L) && index >= 0 && index < L.size){
103         Data *= L.data + index * sizeof(Data);
104         if(index >= L.count){
105             L.count++;
106         }
107         *= data;
108         return OK;
109     }
110     return ERROR;
111 }
112 
113 /**
114  * 描述: 将数据存储到线性表
115  * 参数: &L     线性表
116  * 参数: data    数据
117  * 返回: ERROR/OK
118  */
119 Status putValue(List &L, Data data){
120 
121     if(!isEmptyList(L)){
122         if(L.count >= L.size){
123             Data *= (Data*)realloc(L.data, (L.size + LIST_INCREMENT_COUNT) * sizeof(Data));
124             if(!p){
125                 return ERROR;
126             }else{
127                 L.data = p;
128                 L.size += LIST_INCREMENT_COUNT;
129             }
130         }
131         *(L.data + L.count * sizeof(Data)) = data;
132         L.count++;
133         return OK;
134     }
135     return ERROR;
136 }
137 
138 /**
139  * 描述: 将数据存储到线性表
140  * 参数: &L          线性表
141  * 参数: data         数据元素基址
142  * 参数: count 数据总计数
143  * 返回: ERROR/OK
144  */
145 Status putAll(List &L, Data *data, int count){
146 
147     for(int i = 0; i < count; i++){
148         putValue(L, data[i]);
149     }
150     return OK;
151 }
152 
153 /**
154  * 描述: 获取线性表中下标为index的值
155  * 参数: &L          线性表
156  * 参数: index 数据元素下标索引值
157  * 返回: Data
158  */
159 Data getValue(List &L, int index){
160 
161     if(index < 0 || index > L.count){
162         return OutOfBound;
163     }else{
164         return *(L.data + index * sizeof(Data));
165     }
166 }
167 
168 /**
169  * 描述: 获取线性表中下标为index的值,并存储到value中
170  * 参数: &L             线性表
171  * 参数: index  数据元素下标索引值
172  * 参数: &value 存储索引对应的值
173  * 返回: void
174  */
175 void getValue(List &L, int index, int &value){
176 
177     value = getValue(L, index);
178 }
179 
180 /**
181  * 描述: 在线性表中,在下标为index的位置插入一个数据元素,值为data,原先下标为index以及后面的数据元素往后移
182  * 参数: &L          线性表
183  * 参数: index 数据元素下标索引值
184  * 参数: data  插入的值
185  * 返回: ERROR/OK/OutOfBound
186  */
187 Status insertNode(List &L, int index, Data data){
188 
189     if(index < 0 || index > L.count){
190         return OutOfBound;
191     }
192     if(L.count >= L.size){
193         Data *= (Data*)realloc(L.data, (L.size + LIST_INCREMENT_COUNT) * sizeof(Data));
194         if(!p){
195             return ERROR;
196         }else{
197             L.data = p;
198             L.size += LIST_INCREMENT_COUNT;
199         }
200     }
201     Data *dp, *dq;
202     dq = L.data + index * sizeof(Data); //插入节点位置
203     dp = L.data + (L.count - 1* sizeof(Data); //表尾结点位置
204     while(dp >= dq){ //右移
205         *(dp + 1 * sizeof(Data)) = *dp;
206         dp -= 1 * sizeof(Data);
207     }
208     *dq = data;
209     L.count++;
210     return OK;
211 }
212 
213 /**
214  * 描述: 删除索引值为index的数据元素节点
215  * 参数: &L          线性表
216  * 参数: index 数据元素下标索引值
217  * 返回: OutOfBound/OK
218  */
219 Status removeNode(List &L, int index){
220 
221     if(index < 0 || index > L.count){
222         return OutOfBound;
223     }
224     Data *dp, *dq;
225     dp = L.data + index * sizeof(Data); //删除节点位置
226     dq = L.data + (L.count - 1* sizeof(Data); //表尾结点位置
227     while(dp < dq){ //左移
228         *dp = *(dp + 1 * sizeof(Data));
229         dp += 1 * sizeof(Data);
230     }
231     L.count--;
232     return OK;
233 }
234 
235 /**
236  * 描述: 获取数据元素个数
237  * 参数: data      数据元素基址
238  * 参数: size 所有数据元素总大小
239  * 返回: 数据元素个数
240  */
241 int arrayLength(Data *data, int size){
242 
243     int count = 0;
244     size /= sizeof(Data);
245     for(int i = 0; i < size; i++){
246         if(data[i] != '\0')
247             count++;
248     }
249     return count;
250 }
251 
252 /**
253  * 描述: 自然排序(插入排序法)线性表
254  * 参数: &L  线性表
255  */
256 Status sortList(List &L){
257 
258     if(isEmptyList(L)){
259         return OK;
260     }
261     int size = L.count;
262     Data data, *data_i, *data_j;
263     for(int i = 1; i < size; i++){
264         data_i = L.data + i * sizeof(Data);
265         for(int j = 0; j < i; j++){
266             data_j = L.data + j * sizeof(Data);
267             if(*data_j > *data_i){
268                 data = *data_j;
269                 *data_j = *data_i;
270                 *data_i = data;
271             }
272         }
273     }
274     return OK;
275 }


File : linearList.c
  1 /**
  2  * =================================
  3  * @描述: 测试
  4  * @作者: fancy
  5  * @日期: 2012-11-02
  6  * @联系: fancydeepin@yeah.net
  7  * =================================
  8  */
  9 
 10 #include "list.h"
 11 
 12 int main() {
 13 
 14     /*************************************************/
 15     /*                存取、插入、删除                                                           */
 16     /*************************************************/
 17     List list = newList();
 18     Data data[] = {3110005981};
 19     printf("存取数据: ");
 20     putAll(list, data, 10);
 21     for(int i = 0; i < list.count; i++){
 22         printf("%d", getValue(list, i));
 23     }
 24     printf("\n插入数据: ");
 25     insertNode(list, 99);
 26     for(int i = 0; i < list.count; i++){
 27         printf("%d", getValue(list, i));
 28     }
 29     printf("\n删除数据: ");
 30     removeNode(list, 9);
 31     for(int i = 0; i < list.count; i++){
 32         printf("%d", getValue(list, i));
 33     }
 34     printf("\n=======================================\n");
 35 
 36     /*************************************************/
 37     /*                      排序数据元素                                                             */
 38     /*************************************************/
 39     List linearList = newList();
 40     Data dataSet[] = {20618911};
 41     int count = arrayLength(dataSet, sizeof(dataSet));
 42     putAll(linearList, dataSet, count);
 43     printf("排序之前: ");
 44     for(int i = 0; i < count; i++){
 45         printf("%d\t", getValue(linearList, i));
 46     }
 47     printf("\n排序之后: ");
 48     sortList(linearList);
 49     for(int i = 0; i < count; i++){
 50         printf("%d\t", getValue(linearList, i));
 51     }
 52     printf("\n=======================================\n");
 53 
 54     /*
 55      * 已知线性表LA和LB中的数据元素按值非递减有序排列,
 56      * 现要求将LA和LB归并为一个新的线性表LC,且LC中的数据元素仍按值非递减有序排列。
 57      * 设:
 58      * LA = (3, 5, 8, 11)
 59      * LB = (2, 6, 8, 9, 11, 15, 20)
 60      * 则
 61      * LC = (2, 3, 5, 6, 8, 8, 9, 11, 11, 15, 20)
 62      */
 63     /*************************************************/
 64     /*                    合并两个线性表                                                           */
 65     /*************************************************/
 66     List LA = newList();
 67     List LB = newList();
 68     List LC = newList();
 69     Data DA[] = {35811};
 70     Data DB[] = {2689111520};
 71     putAll(LA, DA, 4);
 72     putAll(LB, DB, 7);
 73     printf("LA表数据元素: ");
 74     for(int i = 0; i < LA.count; i++){
 75         printf("%d\t", getValue(LA,i));
 76     }
 77     printf("\nLB表数据元素: ");
 78     for(int i = 0; i < LB.count; i++){
 79         printf("%d\t", getValue(LB,i));
 80     }
 81     int LA_index = 0, LA_size = LA.count, LA_value;
 82     int LB_index = 0, LB_size = LB.count, LB_value;
 83     while(LA_index < LA_size && LB_index < LB_size){
 84         getValue(LA, LA_index, LA_value);
 85         getValue(LB, LB_index, LB_value);
 86         if(LA_value < LB_value){
 87             putValue(LC, LA_value);
 88             LA_index++;
 89         }else{
 90             putValue(LC, LB_value);
 91             LB_index++;
 92         }
 93     }
 94     while(LA_index < LA_size){
 95         getValue(LA, LA_index++, LA_value);
 96         putValue(LC, LA_value);
 97     }
 98     while(LB_index < LB_size){
 99         getValue(LB, LB_index++, LB_value);
100         putValue(LC, LB_value);
101     }
102     printf("\nLC表数据元素: ");
103     for(int i = 0; i < LC.count; i++){
104         printf("%d\t", getValue(LC,i));
105     }
106     return 0;
107 }


测试结果:
存取数据: 3110005981
插入数据: 31100059891
删除数据: 3110005981
=======================================
排序之前: 20    6    18    9      11    
排序之后: 6       9    11    18    20    
=======================================
LA表数据元素: 3       5      8      11    
LB表数据元素: 2       6       8       9       11      15      20    
LC表数据元素: 2       3       5       6        8         8         9       11      11      15      20    



  
posted on 2012-11-02 19:57 fancydeepin 阅读(2127) 评论(1)  编辑  收藏

评论:
# re: 线性表的顺序表示和实现 2012-11-13 14:49 | BlogJava_Net_332
trwetwert  回复  更多评论
  

只有注册用户登录后才能发表评论。


网站导航: