线性表学习

线性表是最常用也是最简单的一种数据结构,一个线性表是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);所以线性表一般用来存储增删不太频繁的数据。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏coolblog.xyz技术专栏

LinkedHashMap 源码详细分析(JDK1.8)

LinkedHashMap 继承自 HashMap,在 HashMap 基础上,通过维护一条双向链表,解决了 HashMap 不能随时保持遍历顺序和插入顺序一致...

510100
来自专栏皮皮之路

【JDK1.8】JDK1.8集合源码阅读——Set汇总

323120
来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之二叉树中和为某一值的路径(九度OJ1368)

题目描述: 输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。 输入:...

21370
来自专栏恰童鞋骚年

剑指Offer面试题:24.复杂链表的复制

  下图是一个含有5个结点的复杂链表。图中实线箭头表示m_pNext指针,虚线箭头表示m_pSibling指针。为简单起见,指向NULL的指针没有画出。

8920
来自专栏一英里广度一英寸深度的学习

二叉树的深度优先遍历与广度优先遍历

先遍历子节点,再遍历兄弟节点。 从根节点开始递归,如果存在子节点,继续遍历子节点。

85530
来自专栏对角另一面

lodash源码分析之compact中的遍历

本文为读 lodash 源码的第三篇,后续文章会更新到这个仓库中,欢迎 star:pocket-lodash

22560
来自专栏chenssy

【死磕Java并发】-----J.U.C之阻塞队列:PriorityBlockingQueue

我们知道线程Thread可以调用setPriority(int newPriority)来设置优先级的,线程优先级高的线程先执行,优先级低的后执行。而前面介绍的...

36240
来自专栏王磊的博客

Java核心(四)面试必备—你不知道的数据集合

导读:Map竟然不属于Java集合框架的子集?队列也和List一样属于集合的三大子集之一?更有队列的正确使用姿势,一起来看吧!

11220
来自专栏李家的小酒馆

图的深度优先遍历和广度优先遍历

深度优先遍历 图的深度优先遍历类似于树的先序遍历,首先通过一个指定的节点开始遍历,然后访问第一个邻接点,然后切换到这个节点判断是否是否有邻接点,如果有,判断是否...

28000
来自专栏开发与安全

数据结构:静态链表

首先我们让数组的元素都是由两个数据域组成,data和cur。也就是说,数组的每一个下标都对应一个data和一个cur。 数据域data用来存放数据元素,也就是通...

22860

扫码关注云+社区

领取腾讯云代金券