顺序表的基本操作

　　

  1 //顺序线性表
  2 #include <stdio.h>
  3 #include <stdlib.h>
  4 #define list_init_size 100 //线性表储存空间的初始分配量
  5 #define listincrement 10  //线性表储存空间的分配增量
  6 #define ok 1
  7 #define error 0
  8 typedef double elemtype;
  9 typedef struct {
 10     elemtype *elem;  //储存空间基地址
 11     int length;        //当前长度
 12     int listsize;   //当前分配的储存容量(以sizeof(elemtype))为单位
 13 }sqlist;
 14 //顺序表的初始化
 15 void initlist(sqlist *l) {
 16     l->elem = (elemtype*)malloc(list_init_size);
 17     if (!l->elem)  //储存分配失败
 18         exit(-1);
 19     l->length = 0;    //空表长度为0
 20     l->listsize = list_init_size; //初始储存容量
 21 }
 22 //判断表是否为空
 23 int emptylist(sqlist *l)
 24 {
 25     if (l->length == 0)
 26     {
 27         return ok;
 28     }
 29     return error;
 30 }
 31 //顺序表的插入
 32 int listinsert(sqlist *l,int i,elemtype e) {
 33     //在顺序表l中的第i个位置之前插入新的元素e，l的长度加1
 34     //i=1时头插 i=l->length+1 时尾插
 35     elemtype *newbase, *q, *p;
 36     if (i<1 || i>l->length + 1)  //输入的i值不合法
 37         return error;
 38     if (l->length >= l->listsize)  //当前储存空间已满，增加分配
 39     {
 40         newbase = (elemtype*)realloc(l->elem, (l->listsize +
 41             listincrement) * sizeof(elemtype));
 42         if (!newbase)  exit(-1);
 43         l->elem = newbase;  //新基地址
 44         l->listsize += listincrement;  //增加储存容量
 45     }
 46     q = l->elem + i - 1;   //获得插入位置的地址
 47     for (p = l->elem + l->length - 1; p >= q; --p)
 48     //q之后的元素右移一步，腾出空间
 49         *(p + 1) = *p;
 50     *q = e;  //插入e
 51     ++l->length;  //表长加1
 52     return ok;
 53 
 54     
 55 }
 56 //头插
 57 int topinsert(sqlist *l, elemtype e) {
 58     elemtype *newbase, *p;
 59     int i;
 60     if (l->length >= l->listsize)  //当前储存空间已满，增加分配
 61     {
 62         newbase = (elemtype*)realloc(l->elem, (l->listsize +
 63             listincrement) * sizeof(elemtype));
 64         if (!newbase)  exit(-1);
 65         l->elem = newbase;  //新基地址
 66         l->listsize += listincrement;  //增加储存容量
 67     }
 68     p = l->elem + l->length - 1;
 69     for (i = l->length; i > 0; --i)
 70     {//表中所有元素右移一步，腾出空间
 71         *(p + 1) = *p;
 72         p--;
 73     }
 74     *l->elem = e;  //插入e
 75     ++l->length;  //表长加1
 76     return ok;
 77 }
 78 //尾插
 79 int backinsert(sqlist *l,elemtype e) {
 80     elemtype *newbase, *p;
 81     if (l->length >= l->listsize)  //当前储存空间已满，增加分配
 82     {
 83         newbase = (elemtype*)realloc(l->elem, (l->listsize +
 84             listincrement) * sizeof(elemtype));
 85         if (!newbase)  exit(-1);
 86         l->elem = newbase;  //新基地址
 87         l->listsize += listincrement;  //增加储存容量
 88     }
 89     p = l->elem + l->length;  //p指向最后一个元素的后一个地址
 90     *p = e;       //插入e
 91     l->length++;  //表长加1
 92     return ok;
 93 
 94 }
 95 //顺序表的删除
 96 int listdelete(sqlist *l, int i, elemtype *e) {
 97     //删除l的第i个元素，并用e返回其值，l的表长减1
 98     //i=1 头删  i=l->length+1  尾删
 99     elemtype *p, *q;
100     if (i<1 || i>l->length + 1)  //输入的i值不合法
101         return error;
102     p = l->elem + i - 1;  //p为被删除元素的位置
103     *e = *p;  //被删除元素的值赋给e
104     q = l->elem + l->length - 1;  //表尾元素的位置
105     for (++p; p <= q; ++p)//删除元素后的元素左移
106         *(p - 1) = *p;
107     l->length--;  //表长减1
108     return ok;
109 
110 }
111 //头删
112 int topdelete(sqlist *l, elemtype *e) {
113     elemtype *p, *q;
114     if (emptylist(l) == ok) return error;
115     p = l->elem ;  //p为被删除元素的位置
116     *e = *p;  //被删除元素的值赋给e
117     q = l->elem + l->length - 1;  //表尾元素的位置
118     for (++p; p <= q; ++p)//删除元素后的元素左移
119         *(p - 1) = *p;
120     l->length--;  //表长减1
121     return ok;
122 }
123 //尾删
124 int backdelete(sqlist *l, elemtype *e) {
125     
126     if (emptylist(l) == ok) return error;
127     *e = *l->elem + l->length - 1;
128     l->length--;  //表长减1
129     return ok;
130 }
131 
132 //打印表中元素
133 void printlist(sqlist *l)
134 {
135     int i;
136     if (emptylist(l)==ok)
137     {
138         printf("表为空！\n");
139         exit(-1);
140     }
141     for (i = 0; i< l->length; i++)
142     {
143         printf("%lf ",*( l->elem+i));
144     }
145     printf("\n");
146 }
147 //清空表
148 int clearlist(sqlist *l) {
149     l->length = 0;
150     return ok;
151 }
152 //销毁表
153 int destorylist(sqlist *l) {
154     
155     free(l->elem);
156     return ok;
157 }
158 
159 int main() {
160     sqlist *l;
161     l = (sqlist*)malloc(sizeof(sqlist));
162     elemtype  *e = (elemtype*)malloc(sizeof(elemtype));
163     initlist(l);
164     backinsert(l, 1);
165     backinsert(l, 2);
166     backinsert(l, 3);
167     printlist(l);
168 
169     topinsert(l, 0);
170     printlist(l);
171 
172     backinsert(l, 4);
173     printlist(l);
174 
175     listinsert(l, 2, 8);
176     printlist(l);
177 
178     listdelete(l, 2, e);
179     printf("被删除的元素为:%lf\n", *e);
180     printlist(l);
181 
182     topdelete(l, e);
183     printf("被头删的元素为:%lf\n", *e);
184     printlist(l);
185 
186     backdelete(l, e);
187     printf("被尾删的元素为:%lf\n", *e);
188     printlist(l);
189 
190     if (clearlist(l) == ok) printf("成功清空表\n");
191     printlist(l);
192     
193 
194 
195     return ok;
196 }