首页 > > 程序设计 > C/C++ >

动态顺序表

2018-06-17 22:41:03来源：未知阅读 ()

本文原创，转发请表明出处 http://www.cnblogs.com/JK-HYJ/p/6807661.html

动态顺序表的结构体如下所示：

#define MaxSize 100
typedef struct{
ElemType *elem;
int length;
int listsize;
}Sqlist;

动态生成一张顺序表可以分为一下两步：

(1)定义一个类型Sqlist，它是一个结构体，其成员包括：指向顺序表的首地址elem,顺序表中表的长度length（表中的元素个数），顺序表的存储空间容量（占据内存的大小，以sizeof(ElemType)为单位，由MaxSize规定）listsize.

(2)通过调用一个函数initSqlist()实现动态生成一张顺序表。函数initSqlist()的参数是一个Sqlist类型的指针变量。

函数initSqlist()的代码如下：

void initSqlist(Sqlist *L)
{
L->elem=(int *)malloc(MaxSize*sizeof(ElemType));
if(!L->elem) exit(0);  //创建失败
L->length=0;
L->listsize=MaxSize;
}

函数initSqlist()的作用就是动态初始化一张顺序表，其操作如下:

(1)调用了C标准库函数malloc()动态地分配一段长度为MaxSize*sizeof(ElemType)的内存空间，并将该段函数的首地址赋值给变量L（Sqlist类型）的成员elem成员L->elem。

(2)将L->length置为0，表明此时刚刚生成一张空的顺序表，表内尚无内容，将L->listsize置为MaxSize,表明该顺序表占据内存空间大小为MaxSize（以sizeof(ElemType)为单位）。

函数InsertElem()的代码如下：

void InsertElem(Sqlist *L,int i,ElemType item)
{
  /*向顺序表L的第i个位置插入元素item*/
  ElemType *base,*insertPtr,*p;
  if(i<1 || i>L->length+1) exit(0);
  if(L->length>=L->listsize)
  {
      base=(ElemType*)realloc(L->elem,(L->listsize+100)*sizeof(ElemType));
      /*重新追加空间*/
      L->elem=base;
      L->listsize+=100;
  }
  insertPtr=&(L->elem[i-1]);
  for(p=&(L->elem[L->length-1]);p>=insertPtr;p--)  /*将i-1个位置以后的元素顺序向后移一个位置*/
      *(p+1)=*p;
  *insertPtr=item;
  L->length++;
}

函数InsertElem()的作用是在顺序表中第i个位置插入元素item,并将顺序表的长度增加1。其实现过程如下：

(1)判断插入元素的位置是否合法。一个长度为n的顺序表的可能插入元素的位置是1~n+1,因此如果i<1或者i>n+1,或者表已满，即n==MaxSize的插入都是非法的。

(2)将顺序表的i-1以后的元素顺序后移一个元素的位置，即：将顺序表从第i个元素到第n个元素顺序后移一个元素的位置。

(3)在表的第i个位置（下标是i-1）上插入元素item,并将表长加1。

函数DelElem()的代码如下：

void DelElem(Sqlist *L,int i)
{
    ElemType *delItem,*q;
    if(i<1 || i>L->length) exit(0);
    delItem=&(L->elem[i-1]);
    q=L->elem + L->length - 1;
    for(++delItem;delItem<=q;++delItem)
    {
        *(delItem-1)=*delItem;
    }
    L->length--;
}

函数DelElem()的作用是在顺序表中删除第i个位置的元素,并将顺序表的长度减少1。其实现过程如下：

(1)判断删除的元素是否合法。一个长度为n的顺序表的可能删除元素的位置是1~n+1,因此如果i<1或者i>n+1,都是非法的。

(2)将顺序表的i位置以后的元素顺序后前移动一个元素的位置，这样会覆盖第i个元素的位置，起到删除第i个元素的作用。

(3)将表长减1。

实例如下：

#include "stdio.h"
#include "conio.h"
#include "stdlib.h"
#define MaxSize 10
typedef int ElemType;

typedef struct{
ElemType *elem;
int length;
int listsize;
}Sqlist;

void initSqlist(Sqlist *L)
{
L->elem=(int *)malloc(MaxSize*sizeof(ElemType));
if(!L->elem) exit(0);  //创建失败
L->length=0;
L->listsize=MaxSize;
}

void InsertElem(Sqlist *L,int i,ElemType item)
{
  /*向顺序表L的第i个位置插入元素item*/
  ElemType *base,*insertPtr,*p;
  if(i<1 || i>L->length+1) exit(0);
  if(L->length>=L->listsize)
  {
      base=(ElemType*)realloc(L->elem,(L->listsize+100)*sizeof(ElemType));
      /*重新追加空间*/
      L->elem=base;
      L->listsize+=100;
  }
  insertPtr=&(L->elem[i-1]);
  for(p=&(L->elem[L->length-1]);p>=insertPtr;p--)  /*将i-1个位置以后的元素顺序向后移一个位置*/
      *(p+1)=*p;
  *insertPtr=item;
  L->length++;
}

void DelElem(Sqlist *L,int i)
{
    ElemType *delItem,*q;
    if(i<1 || i>L->length) exit(0);
    delItem=&(L->elem[i-1]);
    q=L->elem + L->length - 1;
    for(++delItem;delItem<=q;++delItem)
    {
        *(delItem-1)=*delItem;
    }
    L->length--;
}

/*测试函数*/
void main()
{
    Sqlist l;
    int i;
    initSqlist(&l);
    for(i=0;i<15;i++)
        InsertElem(&l,i+1,i+1); //向顺序表中插入1~15
    printf("\n The content of the list is \n");
    for(i=0;i<l.length;i++)
        printf("%d ",l.elem[i]);
    printf("\n Delete the fifth element\n");
    DelElem(&l,5);
    for(i=0;i<l.length;i++)
        printf("%d ",l.elem[i]);
    printf("\n");
    return;
}