还记得数据结构这个经典的分类图吧：




今天主要关注一下线性表。

什么是线性表



线性表的划分是从数据的逻辑结构上进行的。线性指的是在数据的逻辑结构上是线性的。即在数据元素的非空有限集中

(1) 存在唯一的一个被称作“第一个”的数据元素，(2) 存在唯一的一个被称作“最后一个”的数据元素，(3) 除第一个外，集合中的每个数据元素均只有一个前继元素，(4)除最后一个外，集合中的每个数据元素均只有一个后继元素。



那么对于线性表，从存储结构上分，可以有顺序存储结构和链式存储结构。顺序存储结构包括顺序表、顺序队列和顺序栈；链式存储结构包括链表、链队列和链栈。所有这些分类数据结构的实现，后续的博文将陆续进行介绍。

顺序表(数组,向量)

顺序表的结构：

顺序表的结构如下图所示：




从结构上可以看出，顺序表实际上就是一个动态数组，在C++的标准模板库（STL）中类似的对应着vector模板类。所以理解顺序表对于使用vector进行高级应用的开发有着极为重要的作用。

存储结构定义如下：



typedef struct

{

  DataType *m_pData;

    int m_nMax,m_nSize;

}SeqList;



typedef int DataType;

顺序表的基本操作及其实现
有了数据的结构定义，就必须有对应的方法实现从来进行相关的操作，基本的运算函数如下：





Void SetList(SeqList *L,int n);// 构造函数,建立数组长是n的空表



Void FreeList(SeqList *L); // 析构函数,释放数组空间




int ListSize(SeqList *L) // 求表的长度

int IsEmpty(SeqList *L); // 判断数组是否空,1:空,0满

int IfFull(SeqList *L); // 判断数组是否满





DataType GetData(int pos); // 获取数组某元素

int Locate(SeqList *L,DataTypeitem); // 判断元素位置

Void SetData(SeqList *L,DataTypeitem,int pos); //元素位置赋值




Void Insert(SeqList *L,int pos,DataType item); //在某位置插入元素

void InsertRear(SeqList *L,DataType&item); // 在末尾插入元素





void Delete(SeqList *L,int pos);//删除某位置元素

void ClearList(SeqList *L); // 清表,表中的元素个数是0;

Void DeleteBetween(SeqList *L,intstart, int end)



对应某些函数方法的实现如下：


voidSetList(SeqList *L,int n)

{

L->m_pData=newDataType[n];

if(L->m_pData==NULL)

{

  cout<<”overflow”<<endl;exit(1);

}

L->m_nMax=n;

L->m_nSize=0;

}




Void FreeList(SeqList *L)

{

delete [ ]L->m_pData;

L->m_nSize=0;

L->m_nMax=0;

}






void Insert(SeqList *L,DataType item,int pos)

{

//在顺序表中在pos处插入item

  i=1;

  if(L->m_nSize==L->m_nMax){printf(“SeqListis FULL\n”);exit(1)}

  if(pos<=0||pos>L->m_nSize)

  {

  printf(“Pos is out of range”);exit(1);

  }

  for(i=L->m_nSize-1;i>=pos;i--)

  L->m_nData[i+1]=L->m_nData[i];

  L->m_nData[pos]=item;

  L->m_nSize++;

}



顺序表的应用：动态字符串


C语言字符串



char str[13]=“Hello, world!”;

 char *pStr = str;
字符串函数

 gets(char *str);

 puts(char *str);

 strcpy(char *str1, char *str2); //字符串拷贝

 strcat(char *str1, char *str2); //字符串连接,str1必须足够大

 strcmp(char *str1, char *str2); //字符串比较

 strlen(char *str); //字符串求长,不包含’\0’的长度



动态字符串：


Typedef struct



 {

   int m_nSize;//不含结束符的长度

   char*m_pStr;

 }String;
基本运算： Concat(), SubString(), Insert(),Delete(),Clear()…


顺序队列
一种特殊的线性表：只能在表的一端插入，另一端删除，是先进先出的线性表；头指针(删除位置)和尾指针(插入位置)
First come, first serve(FIFO)
优点：循环结构、删除时不需移动元素





顺序队列的结构：
顺序队列的结构如下图所示：




存储结构定义如下：

typedef struct

{

  DataType *m_pData;

  int m_nMax;

  int m_nFront,m_nRear, m_nSize;

}Queue;




顺序队列的基本操作及其实现
Void SetQueue(Queue *Q,int n); // 构造函数
void FreeQueue(Queun *Q); // 析构函数
int QSize(Queue *Q); // 队列长度
int QEmpty(Queue *Q); // 判断队列是否空
int QFull(Queue *Q); // 判断队列是否满
DataType QGetData(Queue *Q); // 获取数据
int QInsert(Queue *Q,DataType item); // 进队列
DataType QDelete(Queue *Q); // 出队列
void QClear(); // 清空
队列删除操作：


DataTypeQDelete(Queue *Q)

{

  DataType item;

  if(Q->m_nSize==0)

  {

printf(“队列空\n”);

    Exit(1);

  }

  item=Q->m_pData[Q->m_nFront];

  Q->m_nFront=(Q->m_nFront+1)%Q->m_nMax;

  Q->m_nSize--;
}




顺序栈
一种特殊的线性表：只能在表的一端插入和删除，是后进先出的线性表；进栈和出栈

顺序栈的结构：


结构如下图所示：





Typedef struct

{

  DataType *m_pData;

  int m_nMax;

  int m_nTop;//插入数据的位置,空为-1,入栈+1,出栈-1

}Stack;

顺序栈的基本操作
顺序栈的基本操作如下：
CStack()/CStack(int n); // 构造函数
~CStack(); // 析构函数
int SetSize(int n); // 设置栈的大小
int Free(); // 释放空间
int Size(); // 栈的大小
int Empty(); // 判断是否空
int Full(); // 判断是否满
int Push(DataType item); // 压栈
DataType Pop(); // 出栈
DataType GetPeek(); // 取栈顶元素
int Clear(); // 清空栈
顺序栈的基本运算函数声明如下：


Void SetStack(Stack *S,int n);
Void FreeStack(Stack *S);
Int StackEmpty(Stack *S);
Int StackFull(Stack *S);
Void Push(Stack *S,DataType item);
DataType Pop(Stack *S);
Void ClearStack(Stack *S);
DataType Peek(Stack *S);

大部分的Linux文件系统（如ext2、ext3）规定，一个文件由目录项、inode和数据块组成：
目录项：包括文件名和inode节点号。
Inode：又称文件索引节点，包含文件的基础信息以及数据块的指针。
数据块：包含文件的具体内容。

先说inode
理解inode，要从文件储存说起。文件储存在硬盘上，硬盘的最小存储单位叫做"扇区"（Sector），每个扇区储存512字节（相当于0.5KB）。

操作系统读取硬盘的时候，不会一个扇区一个扇区地读取，这样效率太低，而是一次性连续读取多个扇区，即一次性读取一个"块"（block）。这种由多个扇区组成的"块"，是文件存取的最小单位。"块"的大小，最常见的是4KB，即连续八个
 sector组成一个 block。

文件数据都储存在"块"中，那么很显然，我们还必须找到一个地方储存文件的元信息，比如文件的创建者、文件的创建日期、文件的大小等等。这种储存文件元信息的区域就叫做inode，中文译名为"索引节点"。

inode包含文件的元信息，具体来说有以下内容：
文件的字节数。
文件拥有者的User ID。
文件的Group ID。
文件的读、写、执行权限。
文件的时间戳，共有三个：ctime指inode上一次变动的时间，mtime指文件内容上一次变动的时间，atime指文件上一次打开的时间。
链接数，即有多少文件名指向这个inode。
文件数据block的位置。

可以用stat命令，查看某个文件的inode信息：
stat demo.txt
总之，除了文件名以外的所有文件信息，都存在inode之中。至于为什么没有文件名，下文会有详细解释。

当查看某个文件时，会先从inode表中查出文件属性及数据存放点，再从数据块中读取数据。

请看文件存储结构示意图：




inode的大小
inode也会消耗硬盘空间，所以硬盘格式化的时候，操作系统自动将硬盘分成两个区域。一个是数据区，存放文件数据；另一个是inode区（inode table），存放inode所包含的信息。

每个inode节点的大小，一般是128字节或256字节。inode节点的总数，在格式化时就给定，一般是每1KB或每2KB就设置一个inode。假定在一块1GB的硬盘中，每个inode节点的大小为128字节，每1KB就设置一个inode，那么inode
 table的大小就会达到128MB，占整块硬盘的12.8%。

查看每个硬盘分区的inode总数和已经使用的数量，可以使用df -i 命令。

查看每个inode节点的大小，可以用如下命令：
sudo dumpe2fs -h /dev/hda | grep "Inode size"
由于每个文件都必须有一个inode，因此有可能发生inode已经用光，但是硬盘还未存满的情况。这时，就无法在硬盘上创建新文件。

inode号码
每个inode都有一个号码，操作系统用inode号码来识别不同的文件。

这里值得重复一遍，Linux系统内部不使用文件名，而使用inode号码来识别文件。对于系统来说，文件名只是inode号码便于识别的别称或者绰号。表面上，用户通过文件名，打开文件。实际上，系统内部这个过程分成三步：首先，系统找到这个文件名对应的inode号码；其次，通过inode号码，获取inode信息；最后，根据inode信息，找到文件数据所在的block，读出数据。

使用ls -i命令，可以看到文件名对应的inode号码，例如：
ls -i demo.txt

目录项
Linux系统中，目录（directory）也是一种文件。打开目录，实际上就是打开目录文件。

目录文件的结构非常简单，就是一系列目录项（dirent）的列表。每个目录项，由两部分组成：所包含文件的文件名，以及该文件名对应的inode号码。

ls命令只列出目录文件中的所有文件名：
ls /etc
ls -i命令列出整个目录文件，即文件名和inode号码：
ls -i /etc
如果要查看文件的详细信息，就必须根据inode号码，访问inode节点，读取信息。ls -l命令列出文件的详细信息。
ls -l /etc

硬链接和软链接

硬链接
一般情况下，文件名和inode号码是"一一对应"关系，每个inode号码对应一个文件名。但是，Linux系统允许，多个文件名指向同一个inode号码。这意味着，可以用不同的文件名访问同样的内容；对文件内容进行修改，会影响到所有文件名；但是，删除一个文件名，不影响另一个文件名的访问。这种情况就被称为"硬链接"（hard
 link）。

ln命令可以创建硬链接，语法为：
ln source_file target_file
运行上面这条命令以后，源文件与目标文件的inode号码相同，都指向同一个inode。inode信息中有一项叫做"链接数"，记录指向该inode的文件名总数，这时就会增加1。反过来，删除一个文件名，就会使得inode节点中的"链接数"减1。当这个值减到0，表明没有文件名指向这个inode，系统就会回收这个inode号码，以及其所对应block区域。

这里顺便说一下目录文件的"链接数"。创建目录时，默认会生成两个目录项："."和".."。前者的inode号码就是当前目录的inode号码，等同于当前目录的"硬链接"；后者的inode号码就是当前目录的父目录的inode号码，等同于父目录的"硬链接"。所以，任何一个目录的"硬链接"总数，总是等于2加上它的子目录总数（含隐藏目录）,这里的2是父目录对其的“硬链接”和当前目录下的".硬链接“。

软链接
除了硬链接以外，还有一种特殊情况。文件A和文件B的inode号码虽然不一样，但是文件A的内容是文件B的路径。读取文件A时，系统会自动将访问者导向文件B。因此，无论打开哪一个文件，最终读取的都是文件B。这时，文件A就称为文件B的"软链接"（soft
 link）或者"符号链接（symbolic link）。

这意味着，文件A依赖于文件B而存在，如果删除了文件B，打开文件A就会报错："No such file or directory"。这是软链接与硬链接最大的不同：文件A指向文件B的文件名，而不是文件B的inode号码，文件B的inode"链接数"不会因此发生变化。

ln -s命令可以创建软链接，语法为：
ln source_file target_file


☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆
文章转载自：http://c.biancheng.net/cpp/html/2780.html

线性表包括顺序表和链表，其中链表又包括单链表、循环链表、双向链表。
顺序存储结构和链式存储结构有所不同，具体区别如下表所示：


线性表是一种逻辑结构，相同数据类型的n个数据元素的有限序列，除第一个元素外，每个元素有且仅有一个直接前驱，除最后一个元素外，每个元素有且仅有一个直接后继。
线性表的特点：

元素个数有限
逻辑上元素有先后次序
数据类型相同
仅讨论元素间的逻辑关系

注：线性表是逻辑结构，顺序表和链表是存储结构。


通过上面的对比，可以得出一些经验性的结论：

若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。若需要频繁插入和删除时，宜采用单链表结构。
当线性表中的元素个数变化较大或者根本不知道有多大时，最好用单链表结构，这样可以不需要考虑存储空间的大小问题。而如果事先知道线性表的大致长度，用顺序存储结构效率会高很多。

顺序表里面元素的地址是连续的，链表里面节点的地址不是连续的，是通过指针连起来的。
顺序存储：
顺序存储的优点：

无须为表示表中元素之间的逻辑关系而增加额外的存储空间。
可以快速地存取表中任意位置地元素

顺序存储的缺点：

插入和删除操作需要移动大量元素
当线性表长度变化较大时，难以确定存储空间的容量
容易造成存储空间的”碎片“

链式存储：
比起顺序存储结构每个数据元素只需要存储一个位置就可以。现在链式存储结构中，除了要存储数据元素信息外，还要存储它的后继元素的存储地址（指针）。把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称为指针或链。这两部分信息组成数据元素称为存储映像，称为节点（Node）。
链表的每个节点中只包含一个指针域，则称为单链表。
头指针和头结点
头指针是指链表指向第一个节点的指针，若链表有头节点，则是指向头结点的指针。头指针具有表示作用，所以常用头指针冠以链表的名字。无论链表是否为空，头指针均不为空。头指针是链表的必要元素。


上图中的头结点可以存在也可以不存在，但是头指针必须有。
头结点是为了操作的统一和方便而设立的，放在第一个元素的节点之前，其数据域一般无意义通常为空，但是指针域指向第一个元素。有了头结点，对在第一元素节点前插入结点和删除第一结点起操作与其它结点的操作就统一了。头结点不一定是链表的必要元素。
单链表的创建

单链表和顺序存储结构不一样，他不像顺序存储结构数据那么集中，它的数据可以是分散在内存各个角落的，它的增长也是动态的。对于每个链表来说，它所占用空间的大小和位置是不需要预先分配划定的，可以根据系统的情况和实际的需求即时生成。
头插法：
头插法从一个空表开始，生成新结点，读取数据存放到新结点的数据域中，然后奖新结点插入到当前链表的表头上，直到结束为止。

简单来说，就是把新加进的元素放在表头后的第一个位置：

先让新节点的next指向头节点之后
然后让表头的next指向新节点

用现实环境模拟的话就是插队的方法，始终让新节点插在第一的位置上。

静态链表

对于线性链表，也可用一维数组来进行描述。这种描述方法便于在没有指针类型的高级程序设计语言中使用链表结构。用数组描述的链表，即称为静态链表。
这种存储结构，仍需要预先分配一个较大的空间，但在作为线性表的插入和删除操作时不需移动元素，仅需修改指针，故仍具有链式存储结构的主要优点。其实和顺序存储结构类似来分配空间，插入元素时，元素依次放在后面，但是插入的元素的游标域要根据插入位置来改变。
假如有如上的静态链表S中存储着线性表（a，b，c，d，f，g，h，i），Maxsize=11，如图所示，要在第四个元素后插入元素e，方法是：先在当前表尾加入一个元素e，即：S[9].data = e;然后修改第四个元素的游标域，将e插入到链表中，即：S[9].cursor = S[4].cursor; S[4].cursor = 9;，接着，若要删除第7个元素h，则先顺着游标链通过计数找到第7个元素存储位置6，删除的具体做法是令S[6].cursor = S[7].cursor。
关于静态链表：

我们对数组的第一个和最后一个元素做特殊处理，他们的data不存放数据。
我们通常把未使用的数组元素称为备用链表。
数组的第一个元素，即下标为0的哪个元素的cur（游标）就存放备用链表的第一个结点的下标。
数组的最后一个元素，即下标为MAXSIZE-1的cur则存放第一个有数值的元素的下标，相当于单链表中的头结点作用。

1、数据结构：指所有数据元素以及数据元素之间的关系，其中包括数据元素之间的逻辑关系（数据的逻辑结构）、数据元素及其关系在计算机存储系统中的存储方式（数据的存储结构）、施加在数据上的操作（数据的运算）
2、逻辑结构类型   （1）集合  （2）线性结构  （3）树形结构  （4）图形结构   
3、存储结构类型
（1）顺序存储结构：把逻辑上相邻的节点存储在物理位置上相邻的存储单元里，节点之间的逻辑关系有存储单元的邻接关系来体现。
         优点：节省存储空间     缺点：不便于修改。
（2）链式存储结构：不要求逻辑上相邻的节点在物理位置上也相邻，节点间的逻辑关系是由附加的指针字段表示的。
       优点：便于修改          缺点：存储空间的利用率低、不能对节点进行随机存取。
（3）索引存储结构：在存储节点信息的同时，建立附件的索引表。
       优点：大大提高了数据查找的速度  缺点：增加了索引表、因而降低了存储空间的利用率。
 （4）散列（或哈希）存储结构：根据节点的关键字通过哈希（或散列）函数直接计算出一个值，并将这个 值作为该节点的存储地址
      优点：查找速度快   缺点：由于哈希存储方法只存储节点的数据，不存储节点之间的逻辑关系。
    适合于要求对数据进行快速查找和插入的场合