Chinaunix首页 | 论坛 | 博客
  • 博客访问: 588772
  • 博文数量: 68
  • 博客积分: 2621
  • 博客等级: 少校
  • 技术积分: 1498
  • 用 户 组: 普通用户
  • 注册时间: 2010-10-23 21:04
文章分类

全部博文(68)

文章存档

2013年(8)

2012年(52)

2010年(8)

分类: C/C++

2010-10-31 22:02:22

线性表的顺序表示用一组地址连续的存储单元依次存储线性表的数据元素。
(1)地址连续的存储单元:指在物理内存中,存储单元是物理上相邻的。
(2)依次存储线性表的数据元素:指逻辑关系上,线性表中的数据元素是相邻的。

e.g.
我们定义一个数组a[5],在物理内存中的表示如图所示;在逻辑关系上就是,a[0]与a[1],a[1]与a[2]是相邻的,即它们的位序相邻。

 a[0] 
 a[1]
 a[2]
 a[3]
 a[4]


优点:线性表的顺序存储结构是一种随机存取的存储结构。
缺点:在作插入或删除操作时,需要移动大量元素。

线性表的顺序实现
线性表的动态顺序分配存储结构:

#define TRUE      1            //操作成功
#define FALSE     0            //操作失败
#define INIT_SIZE 100          //分配的存储空间的初始值
#define ADD_SIZE  10           //分配的存储空间的增量

/*定义一个结构体,来表示线性表*/
typedef struct
{
   MYTYPE   *elem;             //线性表的基地址
   int      length;            //当前的长度
   int      listsize;          //当前分配的存储空间大小,不够可以再分配
}List;
       
/*创建一个线性表*/
int creatList(List &L)
{
   int Ok;

   //构造一个空的线性表L
   L.elem = (MYTYPE *)malloc(INIT_SIZE * sizeof(MYTYPE));
   if(L.elem == NULL)
    {
         Ok = FALSE;            //存储分配失败
         exit();
    }
   L.length = 0;               //空表长度为0
   L.listsize = INIT_SIZE;     //分配的存储容量的初始值

   return Ok;
}//creatList

/*在线性表中插入一个数据元素*/
int inserttList(L *, int i, MYTYPE a)
{
   MYTYPE *new; 
   int Ok;
   MYTYPE *p, *q;
 
   //在线性表List中第i个之前插入新的元素
  
   //判断i值是否为合法值(i从第一个元素算起)
   if(i > L.length + 1)
    {
        printf("i 超出可以插入的范围!\n");
        return FALSE;
    }

   //判断线性表List是否为满
   if(L.length >= L.listsize)
    {
        //线性表已满,增加分配
        new = (MYTYPE *)realloc(L.elem, (L.listsize + ADD_SIZE) * sizeof(MYTYPE));
        if(new == NULL)
            Ok = FALSE;
        L.elem = new;                              //地址变为新的基址
        L.listsize += ADD_SIZE;                    //长度变为增加元素后的         
    }
       
   //插入元素(先右移插入位置及其后的元素,再插入新元素
   p = &(L.elem[i - 1]);                      //p为要插入的位置,下标要减1
   //元素右移,现从后面的元素开始,一个一个向后移动
   for(q = &L.elem[L.length - 1]; q >= p; --p)
         *(p + 1) = *p;   
   //插入元素a
   *p = e;
   //长度加1
   L.length++;

   return Ok;
}//insertList

/*在线性表中删除一个元素*/
int deleteList(L *, int i, MYTYPE a)
{
    //判断i值是否合法(i从第一个元素算起)
    if(i > L.length + 1)
    {
        printf("i 超出可以插入的范围!\n");
        return FALSE;
    }
   
    //删除元素(若有需要,先保存要被删除的元素的值,再左移要删除元素之后的元素
    p = &(L.elem[i - 1]);                      //p为要删除的位置,下标要减1
    q = L.elem + L.length - 1;                 //先确定表尾元素,再左移元素
    //元素左移,从左向右的先后顺序依次移动
    for(++p; p <= q; ++p)
        *(p - 1) = *p;
    //长度减1
    L.length--;
 
    return Ok;
}//deleteList


注:以上很多内容是参考清华大学出版社的《数据结构(c语言版)》,由严蔚敏老师和吴伟民老师编著的
阅读(1554) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~