数据结构：线性表的顺序实现2.2-阿里云开发者社区

数据结构：线性表的顺序实现2.2

2016-09-13 872

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 对于一个线性表如果我们使用顺序的实现，那么在insert或者delete一个值的时候最坏渐进时间复杂度趋近于数据的规模n及 f(n)=O(n); 可以看到这个时候代价比较高，所以我们一般使用链试实现，关于这个算法我用C语言进行如下实现。

对于一个线性表如果我们使用顺序的实现，那么在insert或者delete一个值的时候最坏渐进时间复杂度
趋近于数据的规模n及
f(n)=O(n);
可以看到这个时候代价比较高，所以我们一般使用链试实现，关于这个算法我用C语言进行如下实现。
当使用链试实现的时候代替时间复杂度为O(1) 出于演示并没有写free 释放内存
但是我们也可以想到关于固定位置的元素查找顺序实现其时间复杂度为O(1)，而链表结构则为O(n)

点击(此处)折叠或打开

/*************************************************************************
> File Name: sqlist.c
> Author: gaopeng
> Mail: gaopp_200217@163.com
> Created Time: Tue 04 Oct 2016 09:12:11 PM CST
************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define INITSIZE 10
typedef unsigned int uint;
typedef int Etype;
typedef struct sqlist
{
Etype* elem; //pointer of sqlist base address
uint length; //current length of elem
uint m_size; //
} SQLIST;
void initsqlist(SQLIST* inlist)
{
inlist->elem = (Etype* )malloc(sizeof(Etype)*(INITSIZE+2) + 1);
inlist->length = 0;
inlist->m_size = INITSIZE; //maxsize
}
void initsqlinsert(SQLIST* inlist,Etype ielem,uint postion) //insert elem before postion
{
int i;
Etype* newbase;
if(postion > inlist->length + 1 || postion < 1)
{
printf("line table must continuous or postion must>0!\n");
exit(1);
}
if(inlist->length + 1 >= inlist->m_size ) //if memory small will give more memory
{
if(!(newbase =(Etype* )realloc(inlist->elem,(inlist->length+INITSIZE+2)* sizeof(Etype)+1)))
{
printf("mem alloc failed!\n");
exit(2);
}
inlist->elem = newbase;
inlist->m_size = inlist->m_size+INITSIZE;
}
for(i=0;i<(inlist->length-postion+2);i++) //every elem +1
{
*(inlist->elem+inlist->length+1-i) = * (inlist->elem+inlist->length-i);
}
*(inlist->elem+inlist->length+1-i) = ielem; //give value
inlist->length =inlist->length+1;
}
void delsqldel(SQLIST* inlist,uint postion) //delete elem of postion every elem -1
int i;
if((postion > inlist->length) ||(postion <1))
{
printf("give postion is must large than 1 and less than current length\n");
}
for(i=0;i<(inlist->length-postion) ;i++)
{
*(inlist->elem+postion+i) = *(inlist->elem+postion+i+1);
}
inlist->length =inlist->length-1;
}
void view(SQLIST* inlist)
{
int i;
if(inlist->length ==0 )
{
printf("init data arrary! no data found!\n");
exit(3);
}
for(i=0;i<inlist->length;i++)
{
printf("node:%d values is:%d data length:%d max_size:%d \n",i,*(inlist->elem+i),inlist->length,inlist->m_size);
}
}
int main(void)
{
SQLIST a;
initsqlist(&a);
printf("insert two values\n");
initsqlinsert(&a,5,1);
initsqlinsert(&a,10,1);
view(&a);
printf("delete one values\n");
delsqldel(&a,2);
view(&a);
printf("insert more than 10 values\n");
initsqlinsert(&a,10,1);
initsqlinsert(&a,20,1);
initsqlinsert(&a,30,1);
initsqlinsert(&a,40,1);
initsqlinsert(&a,50,1);
initsqlinsert(&a,10,1);
initsqlinsert(&a,10,1);
initsqlinsert(&a,10,1);
initsqlinsert(&a,10,1);
initsqlinsert(&a,10,1);
initsqlinsert(&a,10,1);
view(&a);
return 0;
}

运行如下：
gaopeng@bogon:~/datas/part2$ ./a.out
insert two values
node:0 values is:10 data length:2 max_size:10
node:1 values is:5 data length:2 max_size:10
delete one values
node:0 values is:10 data length:1 max_size:10
insert more than 10 values
node:0 values is:10 data length:12 max_size:20
node:1 values is:10 data length:12 max_size:20
node:2 values is:10 data length:12 max_size:20
node:3 values is:10 data length:12 max_size:20
node:4 values is:10 data length:12 max_size:20
node:5 values is:10 data length:12 max_size:20
node:6 values is:50 data length:12 max_size:20
node:7 values is:40 data length:12 max_size:20
node:8 values is:30 data length:12 max_size:20
node:9 values is:20 data length:12 max_size:20
node:10 values is:10 data length:12 max_size:20
node:11 values is:10 data length:12 max_size:20

上图演示的是删除data3的方式。插入相反

数据结构：线性表的顺序实现2.2

热门文章

最新文章

相关课程

相关电子书