数据结构之线性表

  1 //线性表的顺序表示。。。
  2 #include <cstdio>
  3 #include <iostream>
  4 using namespace std;
  5 const int list_size = 100;
  6 const int ex_size = 10;
  7 typedef struct{
  8     int *h,size;
  9 }sqlist;
 10 void init(sqlist &l){//初始化线性表
 11     l.h = new int[list_size + 1];
 12     *l.h = 0;
 13     l.size = list_size;
 14 }
 15 void ex_list(sqlist &l){//增大线性表容量
 16     int len = *l.h;
 17     l.size += ex_size;
 18     int *p = new int[l.size];
 19     for(int i = 1; i <= len; ++i) p[i] = l.h[i];
 20     delete [] l.h;
 21     l.h = p;
 22 }
 23 bool empty(sqlist &l){//判断线性表是否为空
 24     if(*l.h == 0) return true;
 25     return false;
 26 }
 27 void destroy(sqlist &l){//销毁线性表（其实就是释放空间。。）
 28     if(l.h != NULL) delete [] l.h;
 29     l.size = 0;
 30 }
 31 void clear(sqlist &l){//清空线性表
 32     *l.h = 0;
 33 }
 34 void display(sqlist &l){//打印线性表
 35     if(empty(l)){
 36         cout << "The linear table is empty!" << endl;
 37         return;
 38     }
 39     for(int *p = l.h + 1; p <= l.h + *l.h; ++p)
 40         cout << *p << " ";
 41     cout << endl;
 42 }
 43 void merge_list(int *a, int l, int m, int r, int *t){//归并排序step2
 44     int i = l, j = m + 1, x = m, y = r, k = 0;
 45     while (i <= x && j <= y)
 46         if (a[i] < a[j]) t[k++] = a[i++];
 47         else t[k++] = a[j++];
 48     while (i <= x) t[k++] = a[i++];
 49     while (j <= y) t[k++] = a[j++];
 50     for (i = 0; i < k; ++i)
 51         a[l + i] = t[i];
 52 }
 53 void merge_sort(int *a, int l, int r,int *t){//归并排序step1
 54     if (l >= r) return;
 55     int mid = (l + r) / 2;
 56     merge_sort(a, l, mid, t);
 57     merge_sort(a, mid + 1, r, t);
 58     merge_list(a, l, mid, r, t);
 59 }
 60 void sort(sqlist &l){//归并排序
 61     int *t = new int[l.size];
 62     merge_sort(l.h, 1, *l.h, t);
 63     delete [] t;
 64 }
 65 void merge(sqlist &l1,sqlist &l2,sqlist &l3){//合并线性表1和线性表2到线性表3
 66     if(l3.size <= *l1.h + *l2.h){
 67         delete [] l3.h; l3.size = *l1.h + *l2.h + ex_size;
 68         l3.h = new int[*l1.h + *l2.h + ex_size];
 69     }
 70     *l3.h = *l1.h + *l2.h;
 71     int *i = l1.h + 1, *j = l2.h + 1, *k = l3.h + 1;
 72     while(i <= l1.h + *l1.h && j <= l2.h + *l2.h)
 73         if(*i < *j) *k++ = *i++;
 74         else *k++ = *j++;
 75     while(i <= l1.h + *l1.h) *k++ = *i++;
 76     while(j <= l2.h + *l2.h) *k++ = *j++;
 77 }
 78 bool insert(sqlist &l,int i,int x){//插入操作
 79     if(i < 1 || i > *l.h + 1) return false;
 80     if(*l.h + 1 >= l.size) ex_list(l);
 81     for(int *j = l.h + *l.h + 1; j > l.h + i; --j) *j = *(j-1);
 82     *(l.h + i) = x;
 83     ++(*l.h);
 84     return true;
 85 }
 86 bool del(sqlist &l,int i){//删除操作
 87     if(i < 1 || i > *l.h) return false;
 88     for(int *j = l.h + i + 1; j <= l.h + *l.h; ++j) *(j-1) = *j;
 89     --*l.h;
 90     return true;
 91 }
 92 int get(sqlist &l,int i){//返回第i个元素
 93     return *(l.h + i);
 94 }
 95 int *locate(sqlist &l,int i){//定位i在第位置，以指针形式返回
 96     for(int *p = l.h + 1; p <= l.h + *l.h; ++p)
 97         if(*p == i) return p;
 98     return NULL;
 99 }
100 int *binary_locate(sqlist &l,int i){//二分定位，只能对已排序的线性表进行定位
101     int x = 1, y = *l.h;
102     while(x <= y){
103         int *p = l.h + (x+y)/2;
104         if(*p == i) return p;
105         else if(*p < i) x = (x+y)/2 + 1;
106         else y = (x+y)/2 - 1;
107     }
108     return NULL;
109 }
110 int *prior(sqlist &l, int x){//返回x的前驱的指针
111     for(int *p = l.h + 1; p < l.h + *l.h; ++p)
112         if(*(p+1) == x) return p;
113     return NULL;
114 }
115 int *next(sqlist &l, int x){//返回x的后继的指针
116     for(int *p = l.h + 2; p <= l.h + *l.h; ++p)
117         if(*(p-1) == x) return p;
118     return NULL;
119 }
120 //以下为方便输出的函数。。。主要是控制格式和输出数据
121 void print_star(int x){
122     cout << "*****************************" << endl;
123     if(x) cout << endl << endl;
124 }
125 void print_inf(sqlist &l,int i){
126     cout << "线性表 " << i << " :长度为:" << *l.h << "  容量为:" << l.size << endl;
127 }
128 void print_list(sqlist &a,sqlist &b,sqlist &c){
129     cout << endl;
130     cout << "-------线性表  1 数据-------" << endl; display(a);
131     cout << "-------线性表  2 数据-------" << endl; display(b);
132     cout << "-------线性表  3 数据-------" << endl; display(c);
133     cout << endl;
134 }
135 void print_information(sqlist &a,sqlist &b,sqlist &c){
136     print_list(a,b,c); print_inf(a,1); print_inf(b,2); print_inf(c,3);cout << endl;
137 }
138 int main(){
139     cout << endl; print_star(0);
140     cout << "-------建立顺序线性表-------" << endl;
141     sqlist a,b,c; init(a); init(b); init(c);
142     print_information(a,b,c);
143     cout << "-------线性表建立成功-------" << endl;
144     print_star(1); print_star(0);
145     cout << "-------数据插入与删除-------" << endl << endl;
146     cout << "-------数据的插入操作-------" << endl;
147     for(int i = 1; i < 11; ++i)
148         insert(a,i,11-i);
149     for(int i = 1; i < 11; ++i)
150         insert(b,i,i);
151     print_information(a,b,c);
152     cout << "-------数据插入成功！-------" << endl << endl;
153     cout << "-------数据的删除操作-------" << endl;
154     del(a,1); del(b,1); del(c,1);
155     print_information(a,b,c);
156     cout << "-------数据删除成功！-------" << endl;
157     print_star(1); print_star(0);
158     cout << "-------数据的相关查询-------" << endl;
159     cout << "线性表1中第1个元素为:" << get(a,1) << endl;
160     cout << "线性表1中第一个6在第 " << locate(a,6) - a.h << endl;
161     cout << "线性表1中5的前驱为:" << *prior(a,5) << endl;
162     cout << "线性表1中5的后继为:" << *next(a,5) << endl;
163     cout << "-------数据查询完毕！-------" << endl;
164     print_star(1); print_star(0);
165     cout << "-------数据的归并排序-------" << endl;
166     cout << "初始数据：" << endl;
167     print_information(a,b,c);
168     sort(a); sort(b);
169     cout << "排序后数据:" << endl;
170     print_information(a,b,c);
171     cout << "排序后可以使用二分查找进行定位,如下:" << endl;
172     cout << "线性表1中第一个6在第 " << binary_locate(a,6) - a.h << endl;
173     cout << "-------数据排序完毕！-------" << endl;
174     print_star(1); print_star(0);
175     cout << "-------多组数据的合并-------" << endl;
176     merge(a,b,c);
177     print_information(a,b,c);
178     cout << "-------数据合并成功！-------" << endl;
179     print_star(0);
180     return 0;
181 }