转载

线性表的本质

有时候就会有一种感觉，尽管学习了C和C++，看到程序都差不多看得懂，但是真正让自己去开发一个软件或者独立性的去写一些代码的时候还是很困难，我们都知道程序的灵魂是算法，一个程序是算法和数据结构的相结合，在接下来来的寒假时光中，笔者将会学习数据结构的一些基础知识，并且加上个人的一些理解，和大家一起分享。

下面我将从4个方面介绍线性表的基本和常用知识。线性表的本质，线性表的相关操作，线性表的顺序存储结构，线性表链式存储结构。

一个线性表是是n个数据元素的有限序列，有以下定义：

线性表是零个或者多个数据元素的集合

线性表中的数据之间是有顺序的

线性表中的数据元素是有限的

线性表中的数据元素的类型必须相同

线性表的一些常用操作：

List* List_Create(); //创建线性表

void List_Destrory(List* list); //销毁线性表

void List_Clear(List* list); //清空线性表

int List_Insert(List* list,ListNode* node,int pos); //将元素插入线性表

ListNode* List_Delete(List* list,int pos); //将元素在线性表中删除

ListNode* List_Get(List* list,int pos); //获取线性表中的某个位置的元素

int List_Length(List* list); //获取线性表的长度

这些都是线性表的一些基础知识，线性表还有好些操作，当然相关命名也是可以变得，在后面的线性表的顺序存储结构和线性表链式存储结构中会运用到这些，下面来介绍一下线性表的顺序存储结构。

顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

线性表的本质

在C语言中，可以用一维数组来实现顺序存储结构。存储空间的起始位置：数组node;线性表的最大容量：数组长度MAXSIZE；线性表的当前长度：length。。可表示如下:

 1 #define MAXSIZE 20  2   3 typedef struct _tag_List  4   5 {  6   7     char node[MAXSIZE];  8   9     int length; 10  11 }　List;

获取元素操作算法如下：

 1 char Get(List* list,int pos)  2 {  3     cahr ret = -1;  4       5     //判断线性表是否合法  6     //判断位置是否合法  7      8     if((List != NULL) && (0 <= pos) && (pos < list -> length))    9      { 10           //获取元素 11           ret = list -> node[pos]; 12      } 13      return ret; 14 }

插入元素算法：

 1 int Insert(List* list,cahr c,int pos)  2 {  3     //判断线性表是否合法  4     int ret = (list != NULL);  5     int i = 0;  6      7     //判断插入位置是否合法  8     ret = ret && (list -> length + 1 <= MAXSIZE);  9     ret = ret && (0 <= pos); 10  11     if( ret ) 12     { 13         if( pos >= list -> length ) 14         { 15                pos = list -> length; 16         } 17  18         //从最后一个元素开始到第pos个位置 19         //分别将他们都向后移动一个位置 20         for( i = list -> length;i>pos;i-- ) 21         { 22             list -> node[i] = list -> node[i-1]; 23         } 24  25         //将新元素插入 26         list -> node[i] = c; 27  28         //长度加1 29         list -> length++; 30     } 31  32     return  ret; 33 }

删除元素算法：

 1 char Delete(List* list,int pos)  2 {  3     char ret = -1;  4     int i = 0;  5   6     //判断线性表是否合法  7     //判断删除位置是都合法  8     if( (list != NULL) && (0 <= pos) && (pos < list -> length) )  9     { 10         //取出删除元素 11         ret = list -> node[pos]; 12  13         //把删除位置pos后的元素分别向前移动一个位置 14         for( int i = pos + 1;i < list -> length;i++) 15         { 16             list -> node[i-1] = list -> node[i]; 17         } 18  19         //长度减1 20         list -> length--; 21     } 22  23     return ret; 24 }

这种方法无需为线性表中的逻辑关系增加额外的空间，可以快速的获取表中合法位置的元素，但是插入和删除元素的草种需要移动大量的元素，当线性表长度变化较大时难以确定存储空间的容量。

为了表示每个元素与其直接后继元素之间的逻辑关系，每个元素除了本身的信息之外，还需要存储指示其直接后继的信息，这就是链式存储。线性表的本质

在Ｃ语言中可以用结构体来定义链表中的指针域，链表中的表头结点也可以用结构体来实现，代码如下：

结点指针域定义
1 typedef struct _tag_LinkListNode LinkListNode 2 struct _tag_LinkListNode 3 { 4     LinkListNode* next; 5 };

1 头结点定义 2 typedef struct _tag_LinkList 3 { 4     LinkListNode header; 5     int length; 6 } TLinkList;

数据元素定义示例 struct Value {     LinkListNode header；     int v; };

获取第pos个元素操作

 1 LinkListNode* current = (LinkListNode*) list;  2 //判断线性表是否合法  3 //判断位置是否合法  4   5 for (i = 0;i<pos;i++)  6 {  7     //由表头开始通过next指针移动pos次后，当前元素的next指针即指      向要获取的元素  8     current = current -> next；  9 } 10  11 ret = current -> next;

插入元素到位置pos的算法

 1 LinkLinkNode* current = (LinkListNode*) list;  2 //判断线性表是否合法  3 //判断插入位置是否合法  4 for(i = 0;（i < pos) && (current -> next != NULL);i++)  5 {  6     //由表头看似hi通过next指针移动pos次后，当前元素的next指针即指向要插入的位置     7     current = current -> next;  8 }  9 //将新元素插入 10 node -> next = current -> next; 11 current -> next = node; 12 //线性表长度加1 13 sList -> length++;

删除第pos个元素的算法

 1 TLinkkList* sList = (TLinkList*)list;  2 //判断线性表是否合法  3 //判断插入位置是否合法  4   5 LinkListNode* ret = NuLL;  6 int i = 0;  7 //获取第pos个元素  8 if((sList != NULL) && (0 <= pos) && (pos <sList -> length))  9 { 10     LinkListNode* current = (LinkListNode*)list; 11  12     for( i = 0;i < pos;i++ ) 13     { 14         current = current ->next; 15     } 16 //将第pos个元素从链表中删除     17     ret = current -> next; 18     current ->next = ret ->next; 19 //线性表长度减1 20     sList -> length--; 21 }