数据结构之顺序表、链表实现

这学期初学数据结构，同时学C语言。由于修的二专，没什么伙伴可以一块讨论。困惑还是很多的，希望自己可以坚持下来吧。

刚开始学的是线性表。线性表又可以分为顺序表和链表，两者的区别在于存储结构不同。

顺序表的存储特点是 依次存储，地址连续。因为地址连续，所以可以随机存取。

写一个构造体，命名为SqList。

 

typedef struct
{
  int data[Max_Length];
  int length;
}SqList;

 

而链表的特点是 任意存放，存储单元可以是不连续的，通过指针将一个个元素连接起来。指针真是个神奇的东西。。

写一个链表构造体，命名为Linknode。

 

typedef struct Linknode{
  int data;
  struct Linknode *next;
}Linknode,*Linklist;

 

显然，两者各有优点和缺点。优缺点互补。

顺序表的缺点是插入删除繁琐，导致这一致命问题的原因在于依次存放，如果想插入一个元素，那势必要将表中该位置以后的元素后移一位。如果想删除一个元素，势必要将表中该位置以后的元素前移一位。

顺序表插入

 

int List_Insert(SqList &L,int i,int e)
{
  int *p;
  int *q;
  //插入位置的前一位置
  q = &(L.data[i - 1]);
  //插入位置的后面的元素后移一位
  for(p = &L.data[L.length - 1];p >= q;--p)
  {
    *(p + 1) = *p;
  }
  *q = e;
  ++L.length;
  return 0;
}

 

顺序表删除

 

//按元素删除
int List_Delete_Elem(SqList &L,ElemType e)
{
  int j;
  //找到第一个所给元素
  for (j = 0;j <= L.length - 1;j++)
  {
    if(L.data[j] == e) break;
  }
  if (j >= L.length)
  {
    return 0;
  }
  int *p = &(L.data[j]);
  int *q = &L.data[0] + L.length -1;
  //删除元素的后面元素前移
  for (++p;p <= q;++p)
    {
      *(p - 1) = *p;
    }
  --L.length;
  return 1;
}

// 按照位置，删除表中指定位置元素
Status List_Delete_Pos(SqList &L, int i)
{
  if (i < 1 || i > L.length)
  {
    return 0;
  }
  int *p = &(L.data[i-1]);
  int *q = &L.data[0] + L.length -1;
  for (++p; p <= q; ++p)
    {
      *(p - 1) = *p;
    }
  --L.length;
  return 1;
}

 

依次存储 的问题在于，元素之间相互影响，这就好比一支军队，排列整齐的一列队伍，一个人的变动会影响全局。

那么，如果不是依次存储呢？链表的优势在于任意存储，形状不固定。人们将它视为一个链条，相互之间的连接依靠指针。我们老师的比喻比较形象，指针是开锁的钥匙，锁在另一个位置。一个元素包括下一个元素的地址，因此我们进入这个元素的房间，便可以找到这个房间存放的另一个房间的地址，从而也就找到了下一个房间。这里，一个房间由两种基本类型组成，一个是数据，一个是指针。

那么，链表如何插入和删除元素呢？我们想加入一个元素P，那个先找到加入的位置的前一个元素A，先使得P存放的地址是A存放的地址，然后使得A存放的地址是P的地址。同理，删除一个元素P，先找到加入的位置的前一个元素A，使得A存放的地址是P的存放的地址。

 

int List_Insert(Linklist &L,int i,int e)
{
    Linklist p,s;
    p = L;
    int j = 0;
    while(p->next && j < i - 1)
    {
        p = p ->next;
        ++j;
    }
    if(!p || j > i - 1) return ERROR;
    s = (Linklist)malloc(sizeof(Lnode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return 1;
}

int List_Delete_Pos(Linklist &L,int i)
{
    Linklist p,q;
    p = L;
    int j,e ;
    j = 0;
    while(p->next && j < i - 1)
    {
        p = p->next;
        j++;
    }
    if(!(p->next) || j > i - 1) return ERROR;
    q = p->next;
    p->next = q->next;
    e = q->data;
    free(q);
    return 1;
}

int List_Delete_Elem(Linklist &L,int m)
{
    Linklist p,q;
    p = L;
    int j,e ;
    j = 0;
    while(p->next && p->next->data != m)
    {
        p = p->next;
    }
    if(!(p->next)) return ERROR;
    q = p->next;
    p->next = q->next;
    e = q->data;
    free(q);
    return 1;
}