SqList.h
1: # ifndef _SQLIST_H_
2: # define _SQLIST_H_
3: /************************************************************************/
4: /* 存储结构的定义 */
5: /************************************************************************/
6: # define ElemType int /*表中存储数据的类型*/
7: # define LIST_INIT_SIZE 100 /*表的初始存储空间*/
8: # define LISTINCREMENT 20 /*表存储空间的增量 */
9:
10: typedef struct { 11: ElemType * elem ; /*基址的指针*/
12: int length ; /*表的长度，表中元素的个数*/
13: int size ; /*表的容量*/
14: }SqList;
15:
16: /************************************************************************/
17: /* 表的基本操作 */
18: /************************************************************************/
19:
20: void InitList(SqList * sqlist) ; /*初始化表*/
21:
22: void DestoryList(SqList * sqlist) ; /*销毁表，释放存储空间*/
23:
24: void ClearList(SqList * sqlist) ; /*将表置空*/
25:
26: int IsEmpty(SqList * sqlist) ; /*判断表是否为空，空则返回1，否则返回0 */
27:
28: int Length(SqList * sqlist) ; /*返回表的长度*/
29:
30: ElemType GetElem(SqList * sqlist,int i) ; /*返回表中第i个元素*/
31:
32: /*判断e是否为表中的元素，是则返回元素在表中的位置，否则返回-1*/
33: int LocateElem(SqList * sqlist,ElemType e) ;
34:
35: /*用pre_e获取元素e的前驱，返回值i为前驱在表中位置*/
36: /*如果e不在表中，返回-1 */
37: /*如果e为表中的第一个元素,返回-2*/
38: int PriorElem(SqList * sqlist,ElemType e,ElemType * pre_e) ;
39:
40: /*用next_e获取e的后继，返回值i为后继在表中的位置*/
41: /*如果e不是表中元素,返回-1*/
42: /*如果e为表中的最后一个元素,返回-2*/
43: int NextElem(SqList * sqlist,ElemType e ,ElemType * next_e) ;
44:
45: /*在位置i处插入元素e,成功则返回表的长度，否则返回0*/
46: int Insert(SqList * sqlist,ElemType e , int i ) ;
47:
48: /*删除表中的元素e，成功返回1，否则返回0*/
49: int Delete(SqList * sqlist,ElemType e) ;
50:
51: /*遍历*/
52: void traverse(SqList * sqlist) ;
53:
54: # endif
SqList.c
1: # include "SqList.h"
2: # include
3: # include
4:
5: /*初始化表*/
6: void InitList(SqList * sqlist) { 7: sqlist->elem = (ElemType *) malloc(LIST_INIT_SIZE) ;
8: if(!sqlist->elem)
9: exit(0) ;
10: sqlist->length = 0 ;
11: sqlist->size = LIST_INIT_SIZE ;
12: }
13:
14: /*销毁表，释放存储空间*/
15: void DestoryList(SqList * sqlist) { 16: if(sqlist->elem)
17: free(sqlist->elem) ;
18: }
19:
20: /*将表置空*/
21: void ClearList(SqList * sqlist) { 22: if(sqlist->elem)
23: sqlist->length = 0 ;
24: }
25:
26: /*判断表是否为空，空则返回1，否则返回0 */
27: int IsEmpty(SqList * sqlist) { 28: if(sqlist->elem) { 29: if(sqlist->length > 0)
30: return 0 ;
31: else
32: return 1 ;
33: }
34: else
35: return -1 ;
36:
37: }
38:
39: /*返回表的长度*/
40: int Length(SqList * sqlist) { 41: if(sqlist->elem)
42: return sqlist->length ;
43: else
44: return -1 ;
45: }
46:
47: /*返回表中第i个元素*/
48: ElemType GetElem(SqList * sqlist,int i) { 49: if( (i-1) > sqlist->length || i < 0)
50: return -1000 ;
51: return *(sqlist->elem + (i-1)) ;
52: }
53:
54: /*判断e是否为表中的元素，是则返回元素在表中的位置，否则返回-1*/
55: int LocateElem(SqList * sqlist,ElemType e) { 56: int i ;
57: for( i = 0 ; i < sqlist->length ; i ++) { 58: if( e == *(sqlist->elem + i) )
59: return i ;
60: }
61: return -1 ;
62: }
63:
64: /*用pre_e获取元素e的前驱，返回值i为前驱在表中位置*/
65: /*如果e不在表中，返回-1 */
66: /*如果e为表中的第一个元素,返回-2*/
67: int PriorElem(SqList * sqlist,ElemType e,ElemType * pre_e) { 68: int local ; //元素e在表中的位置
69: local = LocateElem(sqlist,e) ;
70: if(local == -1) //表中不存在该元素
71: return -1 ;
72: if(local == 0) //表中的第一个元素
73: return -2 ;
74: *pre_e = *(sqlist->elem + (local - 1)) ;
75: return (local - 1) ;
76: }
77:
78: /*用next_e获取e的后继，返回值i为后继在表中的位置*/
79: /*如果e不是表中元素,返回-1*/
80: /*如果e为表中的最后一个元素,返回-2*/
81: int NextElem(SqList * sqlist,ElemType e ,ElemType * next_e) { 82: int local ;
83: local = LocateElem(sqlist,e) ;
84: if(local == -1) //表中不存在该元素
85: return -1 ;
86: if(local == 0) //表中的第一个元素
87: return -2 ;
88: *next_e = *(sqlist->elem + (local + 1)) ;
89: return (local + 1) ;
90: }
91:
92: /*在位置i处插入元素e,成功则返回1，否则返回0*/
93: int Insert(SqList * sqlist,ElemType e , int i ) { 94: ElemType * temp ;
95: int cursor ;
96: if(sqlist->length >= sqlist->size) { 97: temp = (ElemType *)realloc(sqlist->elem,(LIST_INIT_SIZE + LISTINCREMENT) * sizeof(ElemType) ) ;
98: if(!temp)
99: exit(0) ;
100: else { 101: sqlist->elem = temp ;
102: sqlist->size += LISTINCREMENT ;
103: }
104: }
105:
106: for(cursor = sqlist->length ; cursor >= i ; cursor --) { 107: *(sqlist->elem + (cursor + 1)) = *(sqlist->elem + cursor) ;
108: }
109:
110: *(sqlist->elem + i) = e ;
111:
112: return ++ sqlist->length ;
113: }
114:
115: /*删除表中的元素e，成功返1，否则返回0*/
116: int Delete(SqList * sqlist,ElemType e) { 117: int local ;
118: local = LocateElem(sqlist,e) ;
119: if(local == -1) //表中不存在该元素
120: return 0 ;
121:
122: for(; local < sqlist->length ; local++)
123: *(sqlist->elem + local) = *(sqlist->elem + (local - 1)) ;
124:
125: --sqlist->length ;
126: return 1 ;
127: }
128:
129: /*遍历*/
130: void traverse(SqList * sqlist) { 131: int i = 0 ;
132: if(!sqlist->elem || sqlist->length == 0)
133: return ;
134: for( ; i < sqlist->length ;i ++)
135: printf("%4d",*(sqlist->elem + i)) ; 136: printf("\n") ; 137: }