顺序表-阿里云开发者社区

顺序表

2016-05-19 1628

版权

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

简介：

一顺序表的定义：即把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里的方法。

二顺序表类型定义：

[cpp]view plain copy 
 
#define ListSize 100 //定义表空间大小  
typedef int DataType;//假设为int类型  
typedef struct {  
    DataType data[ListSize];  
    int length;//顺序表的大小  
}SeqList  

注意：
① 用向量这种顺序存储的数组类型存储线性表的元素外，顺序表还应该用一个变量来表示线性表的长度属性，因此用结构类型来定义顺序表类型。
② 存放线性表结点的向量空间的大小ListSize应仔细选值，使其既能满足表结点的数目动态增加的需求，又不致于预先定义过大而浪费存储空间。
③ 由于C语言中向量的下标从0开始，所以若L是SeqList类型的顺序表，则线性表的开始结点a1和终端结点an分别存储在L．data[0]和L．Data[L．length-1]中。
④ 若L是SeqList类型的指针变量，则a1和an分别存储在L-＞data[0]和L-＞data[L-＞length-1]中。

三顺序表的运算

①表的初始化

[cpp]view plain copy 
 
<pre name="code" class="cpp">void InitList(SeqList *L)  
{  
    L->length = 0;//顺序表的初始化即就是讲表的长度置为0  
}  

②求表长

[cpp]view plain copy 
 
void Listlength(SeqList *L)  
{  
    return L->length ;//只需要返回length即可  
}  

③取表中第i个结点

[cpp]view plain copy 
 
DataType GetNode(SeqList *L,int i)  
{//取表中第i个结点返回L->data[i-1]即可  
    if(i<1||L->length-1)  
        Error("position error");  
    else  
        return L->data[i];  
}  

④查找x是否在表中

[cpp]view plain copy 
 
int FindNode(SeqList *L,int x)  
{  
    int i,p;  
      
    for(i=0;i<L->length;i++)  
    {  
        p = L->data[i];//取表中第一个节点  
        if(p!=x)  
        {  
            i++;  
        }  
        else break;  
        if(i==length-1)  
        {  
            printf("Sorry not fonud!");  
            return 0;  
        }     
    }  
    printf("the position is %d",i+1);  
    return 1  
}  

⑤将数据x插入到第i个位置上

[cpp]view plain copy 
void InsertList(SeqList *L,DataType x,int i)  
{  
    int j;  
    if(i<1||i>L->length+1)  
        Error("position error");  
    if(L->length>=ListSize)  
        Error("overflow")//表空间溢出  
    for(j=L->length-1;j>=i-1;i--)  
    {  
        L->data[j+1] = L->data[j];    //全体后移  
        L->data[i-1] = x;            //插入数据  
        L->length++;            //表长增加  
    }  
}  

四算法分析

① 问题的规模
表的长度L-＞length（设值为n）是问题的规模。
② 移动结点的次数由表长n和插入位置i决定
算法的时间主要花费在for循环中的结点后移语句上。该语句的执行次数是n-i+1。
当i=n+1：移动结点次数为0，即算法在最好时间复杂度是0(1)
当i=1：移动结点次数为n，即算法在最坏情况下时间复杂度是0(n)
③ 移动结点的平均次数Eis(n)

其中：
在表中第i个位置插入一个结点的移动次数为n-i+1
pi表示在表中第i个位置上插入一个结点的概率。不失一般性，假设在表中任何合法位置（1≤i≤n+1）上的插入结点的机会是均等的，则
p1=p2=…=pn+1=1/(n+1)

因此，在等概率插入的情况下，

即在顺序表上进行插入运算，平均要移动一半结点。

转载：http://blog.csdn.net/xsf50717/article/details/39895835

顺序表

热门文章

最新文章

相关电子书