数据结构---线性表的顺序储存

数据结构中最基础的部分便是线性表得顺序储存结构，特在此分享一下 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <iostream> using namespace std; typedef struct { int *elem; int max_size; int n; }Sqlist; typedef enum{ERROR, OK} Status; Status initiate(Sqlist *p, int max_size)//初始化 { p->n = 0; //线性表内容的长度 p->max_size = max_size; //线性表的容量，即最大容纳的元素的个数 p->elem = (int *)malloc(sizeof(int)*max_size);//分配内存 if(!p->elem) return ERROR; return OK; } void clear(Sqlist *p)//清空线性表 { p->n = 0; } void destroy(Sqlist *p) // 摧毁线性表 { p->max_size = 0; p->n = 0; free((void *)p->elem); } /*！！！！有空测试下形参不用引用的结果是否正确！！！！*/ Status insert(Sqlist *p, int i, int e) //插入算法,将元素e插入到i号元素之前,时间复杂度O(n/2) { if(p->n >= p->max_size) return ERROR; //空间已满 if(i<0 || i>p->n) return ERROR; //插入位置无效 int j; for(j = p->n; j >i; j--) p->elem[j] = p->elem[j-1]; p->elem[i] = e; (p->n)++; return OK; } Status del(Sqlist *p, int i) //删除线性表里的i号元素 { if(p->n <= 0 ) //线性表的大小为0 return ERROR; if(i<0||i>p->n) //删除元素的下标无效 return ERROR; int j; for(j = i+1; j <p->n; j++) p->elem[j-1] = p->elem[j]; p->n--; return OK; } int locate(Sqlist *p, int e) //查找e是否在线性表中 { int i; for(i = 0; i<p->n; i++) if(p->elem[i] == e) break; if(i == p->n)//e不在线性表中，返回-1 i = -1; return i; } Status merge(Sqlist *a, Sqlist *b, Sqlist *c)//合并顺序表a,b 存于c中 { if(a->n + b->n > c->max_size) return ERROR; int i, j , k; i = k = j = 0; c->n = a->n + b->n; while(i<a->n && i<b->n) if(a->elem[i] < b->elem[i])//升序插入 c->elem[k++] = a->elem[i++]; else c->elem[k++] = b->elem[j++]; while(i<a->n) c->elem[k++] = a->elem[i++]; while(j<b->n) c->elem[k++] = b->elem[j++]; return OK; } int main() { Sqlist list; Sqlist *h = &list; initiate(h , 100);//初始化一个表 int i = 0; for(i = 0; i < 100; i++) if(!insert(h, i,i))//插入功能的验证 { cout << "插入出错\n" << endl; exit(0); } /* if(!del(h, 77))//删除的验证 { cout << "删除错误\n"<< endl; exit(0); } */ cout << locate(h, 78) << endl; //验证定位函数 for(i = 0; i<100; i++) cout << h->elem[i] << endl; return 0; }