【摘 要】线性数据结构是最常用的数据结构，也是非线性数据结构的基础。本文选用最基本的线性数据结构——线性表来分析数据逻辑结构到物理结构的两种实现方法，研究具体问题的计算机解决方案。

　　【关键词】数据结构;逻辑;物理;实现

　　【Abstract】Linear data structure is the most commonly used data structure and the basis of non-linear data structure. This paper analyzes the two implementation methods of data logic structure to physical structure by fundamental linear data structure - the linear table and researches computer solutions to the specific problems.

　　【Key Words】Data Structure; Logic; Physics; Implementation

　　《数据结构》是计算机类专业课程体系中一门综合性很强的专业基础课，也是专业核心课。是程序设计的重要理论支撑，为研制开发各种系统和应用软件奠定理论和实践基础，而且与计算机硬件联系紧密。

　　《数据结构》课程涉及的概念、内容比较多，而且大部分都有很强的技巧性。学习过程中要研究数据的逻辑结构以及它们在计算机中的存储方式，学会分析计算机内部执行时所加工数据的数据结构特性，为程序设计所涉及的数据选择适当的逻辑结构、存储结构及相应的算法，使学生开发程序时结构清楚、所写算法正确易读，符合软件工程的规范。在此过程中培养学生理解对数据的各种运算操作的物理实现尤为重要，本文选取数据结构中的典型结构——线性结构(以线性表为例)，展开其顺序及链式实现探讨。文中涉及算法均在Visual C++6.0环境中调试通过。

　　一、线性数据结构

　　1.1 数据的逻辑结构及物理结构

　　数据的逻辑结构包括两部分，线性结构和非线性结构。数据结点之间满足一对一关系的为线性数据结构，满足一对多或者多对多关系的为非线性数据结构。数据的逻辑结构抽象的反映数据元素的结构特点，但是并不考虑他们在计算机中的具体存放。脱离开计算机，从逻辑上观察数据便于在理论上、形式上进行研究、推理、运算等。而数据的存储结构也称为物理结构是数据结构在计算机中的表示，也就是数据在计算机中的存储方式。即任何一个算法的设计取决于选定的逻辑结构，而算法的最终实现依赖于采用的存储结构。

　　1.2 线性数据结构

　　线性数据结构是一种应用十分广泛的数据结构，包括线性表、栈、队列、串以及数组。是数据结构中最简单、最重要的结构形式之一，是程序设计中经常遇到的一种操作对象，也是许多其它数据结构的基础。线性结构中的数据元素之间是一种线性关系，数据元素一个接一个地排列成有限序列。其中的数据元素都属于同一类数据对象，相邻数据元素之间存在着序偶关系。现实生活中碰到的很多问题都可以抽象成线性数据结构，例如人事、财务、仓储、销售管理等问题，它们所使用的表格大部分都是线性结构的原型。

　　1.3 线性数据结构的基本运算

　　线性表的基本运算有确定元素在线性表中的位置，将新元素插入到线性表中的指定位置，删除线性表中指定位置的元素等;栈的基本运算有入栈、出栈、求栈顶元素等;队列的基本运算有入队及出队等。线性结构的基本运算是许多其他复杂数据结构运算的基础，也是常见的查找、排序等运算的基础。确定了相关的数据结构，也就确定了数据结点间的逻辑结构，物理结构就是用计算机语言表示结点之间的这种关系，即线性结构的各种基本运算的实现都是在其物理结构下进行的。线性数据结构的物理实现主要有顺序实现及链式实现两种方式。

　　二、线性表的顺序实现

　　线性表的顺序实现即顺序连续存放线性表中的数据元素，也称为顺序表。在内存中开辟一块连续的存储区域，按照线性表中数据结点的逻辑顺序依次让线性表的第一个元素存放在内存空间的第一个位置，第二个元素存放在第二个位置，其它元素以此类推。线性表中所有的数据元素都属于同一种数据类型，每个元素在存储器中占用的存储空间大小相同，数据元素间的前驱和后继关系体现在存放位置的前后次序上。

　　2.1 顺序存储结构的定义

　　一般情况下采用数组表示线性表的顺序存储结构。数组具有的及时存取、数据元素间地址连续、数据类型相同等特点与线性表的顺序存储空间结构非常类似。C语言中使用一维数组存放数据元素。描述如下：

　　#define MaxSize 100

　　typedef struct SeqList

　　{ ElemType elem[MaxSize];

　　int Length;

　　}SeqList;

　　2.2 顺序存储结构基本运算的实现

　　2.2.1 插入运算(前插)

　　检查表的存储空间，若已占满进行“溢出”处理;检查插入位置i，若超出允许范围进行错误处理;将表的第i个元素及其后所有元素均后移一位;新元素置入第i位;修改表的长度，递增1。算法描述如下：

　　int Insert_SeqList(SeqList &L,int i,int x)

　　{ int j;

　　if(L.length>=MaxSize)

　　{ printf("顺序表已满，无法进行插入操作!");

　　return 0; }

　　if(i<1||i>L.length+1)

　　{ printf("插入位置不正确!");

　　return 0; }

　　for(j=L.length-1;j>=i-1;j--)

　　{ L.elem[j+1]=L.elem[j]; }

　　L.elem[i-1]=x;

　　L.length++;

　　return 1;

　　}

　　2.2.2删除运算

　　检查待删除元素位置i，若超出允许范围进行错误处理;移除i位置上的数据元素;将表中第i个元素后面的所有元素均前移一位;修改表的长度，递减l。算法描述如下：

　　int Delete_SeqList(SeqList &L,int i)

　　{ int j;

　　if((i<1)||(i>L.length))

　　{ printf("删除位置不正确!");

　　return 0; }

　　for(j=i;j

　　L.elem[j-1]=L.elem[j];

　　L.length--;

　　return 1;

　　}

　　2.2.3查找运算(按值查找)

　　从首元素开始，依次将顺序表的元素和给定值x进行比较;找到与给定值相等的元素，返回其在顺序表中的序号i;若查遍顺序表都没找到与给定值相等的元素，返回查找失败提示信息。算法描述如下：

　　int Locate_SeqList(SeqList &L,int x)

　　{ int i=0;

　　while(i

　　i++;

　　if(i>=L.length)

　　{ printf("顺序表中不存在该元素\n");

　　return 0; }

　　else

　　return i+1;

　　}

　　三、线性表的链式实现

　　线性表的链式存储结构不需要使用地址连续的存储单元来实现，不要求数据元素的逻辑次序与其物理次序相一致。其存储单元既可以是连续的，也可以是非连续的，甚至可以零散地分布在存储空间的任何位置上，通过“指针”建立起数据元素之间的逻辑关系。链式存储结构不仅可以用来表示线性表，而且还可以用来表示各种非线性的数据结构，如树、图等。

 1/2    1 2 下一页 尾页