线性表是最常用也是最简单的一种数据结构,一个线性表是n个数据元素的有限序列。
线性表的基本结构:
1 typedef struct xianxing{
2 int length;
3 int *data;
4 }L;
其中int *data也可以换成是一个数组,如int data[maxsize];maxsize你自己定咯,我这里用指针,然后初始化的时候申请动态空间。
上面是基本结构,然后要初始化咯,就是给他赋初值啦。代码如下:
1 int InitList(xianxing &L){//初始化相性表L
2 L.length=0;
3 L.data=(int *)malloc(ElemNum*sizeof(int));//申请空间,线性表最大容量:ElemNum个正数
4 if(!L.data)exit(0);
5 return 1;
6 }
插入元素:
1 int InsertList(xianxing &L,int i,int e){//将数值e插入线性表L第i个位置
2 if(i<1||i>L.length+1)return 0;
3 int *k,*m;
4 m=(L.data+i-1);
5 for(k=(L.data+L.length-1);k>=m;--k){
6 *(k+1)=*k;
7 }
8 *m=e;
9 ++L.length;
10 return 1;
11 }
删除元素:
1 int ListDelete(xianxing &L,int i,int &e){//删除L中第i的位置的数值,并将这个值赋值给e
2 if(i<1||i>L.length)return 0;
3 e=L.data[i-1];
4 int *p;
5 for(p=L.data+i-1;p<L.data+L.length-1;p++){
6 *p=*(p+1);
7 }
8 --L.length;
9 return 1;
10 }
有以上代码基本就可以生成一个线性表了,数据你自己输入,后面的代码有输入方式。比较完整的代码:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<ctype.h>
4 #define ElemNum 100
5 typedef struct xianxing{
6 int length;
7 int *data;
8 }L;
9 int InitList(xianxing &L){//初始化相性表L
10 L.length=0;
11 L.data=(int *)malloc(ElemNum*sizeof(int));//申请空间,线性表最大容量:ElemNum个正数
12 if(!L.data)exit(0);
13 return 1;
14 }
15 int InsertList(xianxing &L,int i,int e){//将数值e插入线性表L第i个位置
16 if(i<1||i>L.length+1)return 0;
17 int *k,*m;
18 m=(L.data+i-1);
19 for(k=(L.data+L.length-1);k>=m;--k){
20 *(k+1)=*k;
21 }
22 *m=e;
23 ++L.length;
24 return 1;
25 }
26 int ListDelete(xianxing &L,int i,int &e){//删除L中第i的位置的数值,并将这个值赋值给e
27 if(i<1||i>L.length)return 0;
28 e=L.data[i-1];
29 int *p;
30 for(p=L.data+i-1;p<L.data+L.length-1;p++){
31 *p=*(p+1);
32 }
33 /*for(p=&(L.data[i-1]);p<&(L.data[L.length-1]);p++){
34 *p=*(p+1);
35 }//跟上面的写法是一样的*/
36 --L.length;
37 return 1;
38 }
39 int LocateElem(xianxing L,int e,int &l){//查找L中数e第一次出现的位置并赋值给l
40 int *p;
41 l=-1;//l=-1表示没找到,外部要判断
42 for(p=L.data;p<=L.data+L.length-1;p++){
43 if(*p==e){
44 l=p-L.data;
45 break;
46 }
47 }
48 }
49 int shuru(xianxing &L){//对已经初始化了的线性表输入一串数
50 int i=0,t=0;
51 while(i<ElemNum){
52 scanf("%d",&t);//输入数值
53 if(t==-1)break;//输入-1表示输入结束
54 InsertList(L,i+1,t);//插入数值
55 i++;
56 }
57 }
58 int MergeList(xianxing &La,xianxing &Lb,xianxing &Lc){//合并两个线性表
59 int *pa,*pb,*pc;
60 int *pa_last,*pb_last;
61 pa=La.data;
62 pb=Lb.data;
63 pa_last=La.data+La.length-1;
64 pb_last=Lb.data+Lb.length-1;
65 Lc.length=La.length+Lb.length;
66 pc=Lc.data=(int *)malloc(Lc.length*sizeof(int));
67 if(!Lc.data)return 0;
68 while(pa<=pa_last)*pc++=*pa++;
69 while(pb<=pb_last)*pc++=*pb++;
70 }
71 int fuzhi(xianxing La,xianxing &Lb){//复制两个线性表
72 int *p,*q;
73 p=La.data;
74 q=Lb.data;
75 for(p;p<=La.data+La.length-1;p++){
76 *q++=*p;
77 }
78 Lb.length=La.length;
79 }
80 int clearList(xianxing &L){
81 L.data=(int *)malloc(ElemNum*sizeof(int));
82 L.length=0;
83 }
84 int getElem(xianxing L,int i,int &e){
85 if(i<1||i>L.length)return 0;
86 int *p;
87 e=*(L.data+i-1);
88 return 1;
89 }
90 int destroyList(xianxing &L){
91 int *p,*q;
92 p=L.data;
93 delete [] p;
94 L.data=NULL;
95 }
96 int main(){
97 /*****************定义一个线性表并输入一串数字,然后存入data.txt文件中*********************/
98 /*
99 xianxing L;//定义相性表L
100 InitList(L);//初始化线性表
101 shuru(L);
102 printf("\n\n");
103 int *p;
104 FILE *fp;
105 fp=fopen("data.txt","w");
106 for(p=(L.data);p<=L.data+L.length-1;++p){
107 fprintf(fp,"%d ",*p);
108 }
109 fclose(fp);
110 */
111 /**************删除你想要删除的第几位数*****************/
112 /*int m,l=0;
113 printf("输入你想删除的第几位数:");
114 scanf("%d",&l);
115 ListDelete(L,l,m);
116 fprintf(fp,"\n\n");
117 for(p=(L.data);p<=L.data+L.length-1;++p){
118 fprintf(fp,"%d ",*p);
119 }
120 printf("删除了第%d位数%d",l,m);*/
121
122 /***********************查找想要的数的第一次出现的位置*************************/
123 /*
124 int chazhaoshu=0;
125 printf("输入你想查找的数:");
126 while(scanf("%d",&chazhaoshu)!=EOF){//isalnum判断是不是数字
127 if(isalpha(chazhaoshu)!=0){
128 return 0;
129 }
130 int q;
131 LocateElem(L,chazhaoshu,q);
132 if(q==-1){
133 printf("抱歉没查到那个数的位置\n");
134 }else{
135 printf("你想要查找的数出现的第一次位置是在%d\n",q);
136 }
137 printf("输入你想查找的数:");
138 }
139 */
140 /*************合并两个线性表****************/
141 /*
142 xianxing La,Lb,Lc;
143 InitList(La);
144 InitList(Lb);
145 InitList(Lc);
146 shuru(La);
147 printf("\n\n");
148 shuru(Lb);
149 MergeList(La,Lb,Lc);
150 int *lc;
151 for(lc=Lc.data;lc<=Lc.data+Lc.length-1;lc++){//输出合并后的线性表
152 printf("%d\n",*(lc));
153 }
154 */
155 /********************复制线性表*************************/
156 /*
157 xianxing La,Lb;
158 InitList(La);
159 InitList(Lb);
160 shuru(La);
161 fuzhi(La,Lb);//执行复制
162 int *p;
163 for(p=Lb.data;p<=Lb.data+Lb.length-1;p++){//输出复制后的线性表
164 printf("%d\n",*p);
165 }
166 */
167 /*******************清空线性表**********************/
168 /*
169 xianxing L;
170 InitList(L);
171 shuru(L);
172 printf("%d %d",*(L.data+1),L.length);
173 printf("\n\n");
174 clearList(L);//清空
175 printf("%d %d",*(L.data+1),L.length);
176 */
177 /*******************根据序号查找元素值***********************/
178 /*
179 xianxing L;
180 InitList(L);
181 shuru(L);
182 int m=0;
183 printf("输入你想要查找第几个元素的值");
184 scanf("%d",&m);
185 int e;
186 if(getElem(L,m,e)){
187 printf("你想要查找的数的值是%d",e);
188 }else{
189 printf("没找到");
190 }
191 */
192 /**********************销毁线性表******************************/
193 xianxing L;
194 InitList(L);
195 shuru(L);
196 printf("%d",*(L.data+1));
197 destroyList(L);
198 //printf("%d",*(L.data+1));去掉注释则运行报错,因为已经销毁了L.data
199 return 0;
200 }
线性表特点:易查询,难增删;要查询一个线性表中某一个元素的值很简单,只要根据索引位置来查询就行,所以时间复杂度是O(1);但是如果要增加或者删除元素,最好的情况时间复杂度是O(1),最坏的情况是O(n);所以平均下来时间复杂度是O(n/2),再简化点就是O(n);所以线性表一般用来存储增删不太频繁的数据。