数据结构-顺序表

2013-10-08

数据结构--顺序表线性表由n（n0）个数据元素（结点）组成的有限（线段）序列。记为：(a0,a1,......,an-1)其中，数

数据结构--顺序表
线性表由n（n>=0）个数据元素（结点）组成的有限（线段）序列。记为： (a0,a1,......,an-1)其中，数据元素个数n称为表的长度，n=0时，称此线性表为空表。n=0时：为空表n不=0时：n为表长
线性表的结构仅涉及诸元素的线性相对位置。
例如：第i个元素ai处在第i-1个元素ai-1的后面，第i+1个元素ai+1的前面。
逻辑结构ai-1被称为是ai的直接前趋，但如果ai是第一个元素的话他没有直接前趋。ai+1被称为是ai的直接后继，但如果ai是最后一个元素的话他没有直接后继。

基本操作初始化操作，构造一个空的线性表LInitList（L）初始化做的工作就是清空线性表。
求表长，求出线性表L中的结点个数。ListLength（L）
取线性表L中的第i个结点GetNode（L,i） i表示第i个位置要求：0<=i<=ListLength(L)-1如果不存在，则返回NULL
查找结点LocateNode（L，x）在L中查找值为x的结点，并返回该结点在L中的位置，若L中共有多个结点的值和x相同，则返回首次找到的结点位，若L中没有结点值为x，则返回-1表示失败。
插入结点InsertList（L,x,i）在线性表L的第i个位置上插入一个值为x的新结点，原第i个位置结点以及后面的结点一次向后面移动一个位置。注： 0<=i<=n-1，n为原来L的长度，加入x后L的长度为n+1

容错保护：如果i<0,则让i=0，如果i>n，则让他变成i=n.
删除结点DeleteList（L,i）删除线性表L的第i个结点，原第i个位置结点被删除，i+1以及后面的结点依次向前移动一位注： 0<=i<=n-1，n为原来L的长度，删除第i个位置上的结点后长度变为n-1
顺序表把线性表的结点按逻辑次序依次放在一组地址连续的存储单元里。这种存储方式就是顺序表（Sequentail List）。数据结构-顺序表

#define LISTSIZE 100 //表的长度，根据实际情况而定typedef int DataType; //数据 typedef的作用是给类型起别名（可以使程序修改变得简单）给int起了个别名 DataTypestruct Seqlist //顺序表{    DataType data[LISTSIZE]; //存放所有数据的空间    int nLength; //当前表的长度};总结：插入和删除一个数据元素时，其时间主要耗费在移动元素上，而移动元素的个数取决于插入和删除元素的位置。空间不能充分利用，扩展能力较差。若线性表的操作主要进行查找以及随机存取表中任一元素，少做插入和删除操作时，采用顺序表存储结构为宜。
六个函数 //初始化
void init(struct Seqlist* s)
{
    s->nLength=0;
}
//输出表内容
void printf(Seqlist* s)
{
    for (int i=0;i<s.nLength;i++)
    printf("%d",s.data[i]);
}
//表长度
int  ListLength(Seqlist* s)
{
    return s->nLength;
}
//取线性表L中的第i个结点
DataType* GetNode(Seqlist* s,int i)
{
    if (i>=0&&i<=s->nLength-1)
         return &s->data[i];
    else
        return NULL;
}
// 查找结点
int LocateNode(const Seqlist* s,const DataType x)
{
    for (int i=0;i<s->nLength-1;i++)
        if(x==s->data[i])
            return i;
    return -1;
}
//插入结点
bool InsertList(Seqlist* s,int data,int index)
{
    if (s->nLength>=LISTSIZE)
        return false;
    if(index>s->nLength-1)
        s->data[s->nLength]=data;
    else
    {
        if(index<0)
            index =0;
        for (int i=s->nLength-1;i>=index;i--)
            s->data[i+1]=s->data[i];
        s->data[index]=data;
    }
    s->nLength++;
    return true;
}
//删除结点
bool DeleteList(Seqlist* s,int i)
{
    if (i<0||s->nLength-1)
        return false;
    else
    {
        for (int j=i;j<s->nLength-1;j++)
            s->data[j]=s->data[j+1];        s->nLength--;
        return true;
    }
}

热点排行

移动开发

数据结构-顺序表