数据结构（一）———顺序表及其实现

数据结构

一、概念

先了解一下线性表，毕竟顺序表和链表都是线性表,顺序表和链表，是线性表的不同存储结构。它们各自有不同的特点和适用范围。。
线性表就是有线性结构的表。什么是线性结构呢？线性结构是n个数据元素的有序集合。它有四个基本特征：
　　1．集合中必存在唯一的一个"第一个元素"；
　　2．集合中必存在唯一的一个"最后的元素"；
　　3．除最后元素之外，其它数据元素均有唯一的"后继"；
　　4．除第一元素之外，其它数据元素均有唯一的"前驱"。
　　如（a1,a2,a3,.....,an）,a1为第一个元素，an为最后一个元素，此集合极为一个线性结构的集合。
　　相对应于线性结构，非线性结构的逻辑特征是一个结点元素可能对应多个直接前驱和多个后驱。
　　常用的线性结构有：线性表，栈，队列，双队列，数组，链表，串。

顺序表:是在计算机内存中以数组的形式保存的线性表,是指用一组地址连续的存储单元，依次存储数据元素的线性结构。顺序表的存储特点是：只要确定了起始位置，表中任一元素的地址都通过下列公式得到：

顺序表:一般表现为数组，使用一组地址连续的存储单元依次存储数据元素，如图 1 所示。它具有如下特点：

• 长度固定，必须在分配内存之前确定数组的长度。
• 存储空间连续，即允许元素的随机访问。
• 存储密度大，内存中存储的全部是数据元素。
• 要访问特定元素，可以使用索引访问，时间复杂度为 O(1)O(1)。
• 要想在顺序表中插入或删除一个元素，都涉及到之后所有元素的移动，因此时间复杂度为 O(n)O(n)。

顺序表最主要的问题就是要求长度是固定的，可以使用倍增-复制的办法来支持动态扩容，将顺序表变成“可变长度”的。

具体做法是初始情况使用一个初始容量（可以指定）的数组，当元素个数超过数组的长度时，就重新申请一个长度为原先二倍的数组，并将旧的数据复制过去，这样就可以有新的空间来存放元素了。这样，列表看起来就是可变长度的。

二、功能及实现

1. 结构体的定义
2. 初始化
3. 尾部插入值为x的节点
4. 打印各节点的值
5. 判断节点是否为空
6. 查找值为x的节点的位置
7. 取得i节点的值
8. 在i位置插入x值
9. 删除i位置的节点

三、代码实现

1. seqlist.h文件

#ifndef SEQLIST_H
#define SEQLIST_H
/***************************************************
顺序表结构定义及其实现
*****************************************************/
// 1. 顺序表结构
#define MAX_SIZE 100
typedef int datatype;
typedef struct tagSeqList {
    datatype a[MAX_SIZE];
    int size;//顺序表的元素个数
}seqlist;
//2. 初始化
void InitSequenceList(seqlist* slist);
//3. 尾部插入值为x的节点
void InsertInSequenceListTail(seqlist* slist,datatype x);
//4. 打印各节点的值
void PintSequenceList(seqlist* slist);
//5. 判断顺序表是否为空
int IsSequenceListEmpty(seqlist* slist);
//6. 查找值为x的节点的位置
int SearchNumInSequenceListPos(seqlist* slist, datatype x);
//7. 取得第i个节点的值
datatype GetValueInSequenceListPos(seqlist* slist, int i);
//8.在i位置插入x值
void InsertInSequenceListPos(seqlist* slist, int pos, datatype x);
//9. 删除i位置的节点
void DeleteInSequenceListPos(seqlist* slist, int pos);
#endif // SEQLIST_H

1. seqlist.cpp文件

#include"SeqList.h"
#include<stdio.h>
#include<stdlib.h>
//2. 初始化
void InitSequenceList(seqlist* slist)
{
    slist->size = 0;
}
//3. 尾部插入值为x的节点
void InsertInSequenceListTail(seqlist* slist, datatype x)
{
    if (slist->size == MAX_SIZE)
    {
        printf("the sequence list is full!\n");
        exit(1);
    }
    slist->a[slist->size]=x;
    slist->size++;
}
//4. 打印各节点的值
void PintSequenceList(seqlist* slist)
{
    if (!IsSequenceListEmpty(slist))
        printf("The list is empty!\n");
    else
        for (int i = 0; i < slist->size; i++)
            printf("%d", slist->a[i]);
}
//5. 判断顺序表是否为空
int IsSequenceListEmpty(seqlist* slist)
{
    return slist->size == 0 ? 0 : 1;
}
//6. 查找值为x的节点的位置
int SearchNumInSequenceListPos(seqlist* slist, datatype x)
{
    int i = 0;
    while (slist->a[i] != x&&i < slist->size)
        i++;
    return i < slist->size ? i : -1;
}
//7. 取得第i个节点的值
datatype GetValueInSequenceListPos(seqlist* slist, int i)
{
    if (i<0 || i >= slist->size)
    {
        printf("The position dese not exist!\n"); exit(1);
    }
    else
        return slist->a[i];
}
//8.在i位置插入x值
void InsertInSequenceListPos(seqlist* slist,int pos,datatype x)
{
    if(slist->size==MAX_SIZE)
    {
        printf("\nThe list is full!\n");
        exit(1);
    }
    if(pos<0||pos>slist->size)
    {
        printf("\nThe position does not exist!");
        exit(1);
    }
    for (int i = slist->size; i > pos; i--)
        slist->a[i] = slist->a[i - 1];
    slist->a[pos] = x;
    slist->size++;
}
//9. 删除i位置的节点
void DeleteInSequenceListPos(seqlist* slist, int pos)
{
    if(pos<0||pos>=slist->size)
    {
        printf("The position does not exist!\n");
        exit(1);
    }
    for (int i = pos; i < slist->size - 1; i++)
        slist->a[i] = slist->a[i + 1];
    slist->size--;
}

参考：http://www.cnblogs.com/cyjb/p/Lists.html
http://blog.csdn.net/fansongy/article/details/6783349