即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

静态顺序表的基本操作

编程语言 fern_girl 16℃ 0评论

头文件:

#define _CRT_SECURE_NO_WARNINGS 1
#ifndef _STATICSEQLIST_H__
#define _STATICSEQLIST_H__

#include
#include
#include

#define MAXSIZE 10
typedef int DataType;
//#define DataType int

typedef struct Seqlist
{
    DataType array[MAXSIZE];
    size_t size;  //有效元素的个数

}Seqlist,*PSeqlist;

void IniSeqlist(PSeqlist seq);
void PushBack(PSeqlist seq,DataType data);
void PrintSeqlist(PSeqlist seq);
void PopBack(PSeqlist seq);
void PushFront(PSeqlist seq,DataType data);
void PopFront(PSeqlist seq);
void Insert(PSeqlist seq,DataType pos,DataType data);
void Erase(PSeqlist seq,size_t pos);
void Remove(PSeqlist seq,DataType data);
void RemoveAll(PSeqlist seq,DataType data);
void Bubblesort(PSeqlist seq);
void Secletsort(PSeqlist seq);
void Secletsort_OP(PSeqlist seq);
int BinarySearch(PSeqlist seq,DataType data);
int Size(PSeqlist seq);
int Empty(PSeqlist seq);



#endif //_STATICSEQLIST_H__

函数定义实现:

#include"StaticSeqList.h"

void IniSeqlist(PSeqlist seq)   //初始化静态顺序表
{
    assert(seq);
    seq->size = 0;
    memset(seq->array, 0 ,sizeof(seq->array));
}
void PushBack(PSeqlist seq,DataType data)   //静态顺序表数据后插
{
    assert(seq);
    if(seq->size == MAXSIZE)
    {
        return;
    }
    seq->array[seq->size++] = data;
}

void PopBack(PSeqlist seq)   //静态顺序表数据后删
{
    assert(seq);
    if(seq->size == 0)
    {
        return;
    }
    seq->size--;
}

void PushFront(PSeqlist seq,DataType data)    //静态顺序表数据前插
{
    DataType idx = 0;

    assert(seq);
    if(seq->size == MAXSIZE)
    {
        return;
    }
    for(idx=seq->size-1; idx>=0;--idx)
    {
        seq->array[idx+1] = seq->array[idx];
    }
    seq->array[0] = data;
    seq->size ++;
}


void PopFront(PSeqlist seq)   //静态顺序表数据前删
{
    int idx = 1;
    assert(seq);
    if(seq->size == 0)
    {
        return;
    }
    for(; idxsize; ++idx)
    {
        seq->array[idx-1] = seq->array[idx];
    }
    seq->size--;

}

void Insert(PSeqlist seq,size_t pos,DataType data)  //静态顺序表数据任意位置插入数据
{
    int idx = 0;

    assert(seq);
    if(pos > seq->size)
    {
        return;
    }
    for(idx=seq->size-1; idx>=pos; --idx)
    {
        seq->array[idx+1] = seq->array[idx];
    }
    seq->array[pos] = data;
    seq->size++;
}

void Erase(PSeqlist seq,size_t pos)   //静态顺序表数据任意位置删除数据
{
    int idx = pos;
    assert(seq);
    if(pos>seq->size)
    {
        return;
    }
    for(; idxsize-1; ++idx)
    {
        seq->array[idx] = seq->array[idx+1];
    }
    seq->size--;
}

int Find(PSeqlist seq,DataType data)   //查找静态顺序表data元素  返回下标
{
    int idx = 0;

    assert(seq);
    for(; idxsize; ++idx)
    {
        if(seq->array[idx] == data)
        {
            return idx;
        }
    }
    return -1;
}

void Remove(PSeqlist seq,DataType data)   //删除静态顺序表中值为data的元素
{
    int ret = 0;
    int idx = 0;
    assert(seq);
    if(seq->size == 0)
    {
        return;
    }
    if(-1 != (ret = Find(seq,data)))
    {
        Erase(seq,ret);
    }
}

//void RemoveAll(PSeqlist seq,DataType data)  //缺点  Find每次查找都要从第一个位置开始
//{
//  int pos = 0;
//  assert(seq);
//  while(-1!=(pos = Find(seq,data)))
//  {
//      Erase(seq,pos);
//  }
//}

void RemoveAll(PSeqlist seq,DataType data)  //自己实现的删除所有data元素
{
    int idx = 0;
    int count = 0;
    assert(seq);
    if(seq->size == 0)
    {
        return;
    }
    for(; idxsize; ++idx)
    {
        if(seq->array[idx] == data)
        {
            count++;
            Erase(seq,idx);
        }
    }
}
//void RemoveAll(PSeqlist seq,DataType data)  //(老师)上课所讲的方法删除所有data元素
//{
//  int count = 0;
//  int idx= 0;
//  assert(seq);
//  for(; idxsize; ++idx)
//  {
//      if(seq->array[idx] == data)
//      {
//          count++;
//      }
//      else
//      {
//          seq->array[idx-count] = seq->array[idx];
//      }
//  }
//  seq->size -= count;
//}


void PrintSeqlist(PSeqlist seq)   //打印顺序表
{
    int idx = 0;

    assert(seq);
    for(; idxsize; ++idx)
    {
        printf("%d ",seq->array[idx]);
    }
    printf("\n");
}
void Bubblesort(PSeqlist seq)   //冒泡排序
{
    DataType i = 0;
    DataType j = 0;
    DataType flag = 0;
    assert(seq);
    for(i=0; isize-1; ++i)
    {
        flag = 0;
        for(j=0; jsize-i-1; ++j)
        {
            if(seq->array[j]>seq->array[j+1])
            {
                DataType tmp = seq->array[j];
                seq->array[j] = seq->array[j+1];
                seq->array[j+1] = tmp;
                flag = 1;
            }
        }
        if(flag == 0)
        {
            break;         //防止当已排序成功但循环没有结束
        }
    }
}
void Secletsort(PSeqlist seq)  //选择排序法
{
    DataType i = 0;
    DataType j = 0;
    DataType pos = 0;
    DataType tmp = 0;
    assert(seq);
    for(i=0; isize-1; ++i)
    {
        pos = 0;
        for(j=1; jsize-i; ++j)
        {
            if(seq->array[pos]array[j])
            {
                pos = j;
            }
        }
            if(pos != seq->size-i)
            {
                tmp = seq->array[pos];
                seq->array[pos] = seq->array[seq->size-i-1];
                seq->array[seq->size-i-1] = tmp;
            }
    }
}
void Secletsort_OP(PSeqlist seq)    //优化后的选择排序法
{             
    DataType j = 0;
    DataType begin = 0;
    DataType end = 0; 
    DataType maxPos = 0;
    DataType minPos = 0;
    DataType tmp = 0;

    assert(seq);
    end = seq->size-1;

    while(beginfor(j=begin+1; j<=end; ++j)
        {
            if(seq->array[maxPos]array[j])
            {

                maxPos = j;
            }

            if(seq->array[minPos]>seq->array[j])
            {

                minPos = j;                        
            }                                        
        }

            if(end != maxPos)
            {
                tmp = seq->array[maxPos];
                seq->array[maxPos] = seq->array[end];
                seq->array[end] = tmp;
            }
            if(begin != minPos)
            {
                tmp = seq->array[minPos];
                seq->array[minPos] = seq->array[begin];
                seq->array[begin] = tmp;    
            }
                end--;
                begin++;
    }
}
int BinarySearch(PSeqlist seq,DataType data)  //二分查找
{
    DataType left = 0;
    DataType right = 0;
    DataType mid = 0;

    assert(seq);
    right = seq->size;
    while(left>1);
        if(seq->array[mid]>data)
        {
            right = mid;
        }
        else if(seq->array[mid]1;
        }
        else
        {
            return mid;
        }
    }
    return -1;
}
int Size(PSeqlist seq)
{
    assert(seq);
    return seq->size;
}
int Empty(PSeqlist seq)
{
    assert(seq);
    if(seq->size == 0)
    {
        return -1;
    }
    return 0;
}

转载请注明:CodingBlog » 静态顺序表的基本操作

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情