目录
●数据结构作为计算机专业基础课，综合性强，抽象性高，在一定程度上增加了学习难度，本次我们共同从数据结构的基础探讨，由浅入深进行数据结构的学习。?
●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！
●本文只浅显的探讨了顺序表的基本知识，后续会进行链表的知识探讨。作者相信随着学习课程的深入，我们将会在对数据结构有更深的理解与收获！
设计出合适的数据结构及相应的算法 即：首先要考虑对相关的各种信息如何表示、组织和存储?
算法定义：一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列
●本文只浅显的探讨了顺序表的基本知识，后续会进行链表的知识探讨。作者相信随着学习课程的深入，我们将会在对数据结构有更深的理解与收获！
●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！
前言
●数据结构作为计算机专业基础课，综合性强，抽象性高，在一定程度上增加了学习难度，本次我们共同从数据结构的基础探讨，由浅入深进行数据结构的学习。?
●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！
正文
●本文只浅显的探讨了顺序表的基本知识，后续会进行链表的知识探讨。作者相信随着学习课程的深入，我们将会在对数据结构有更深的理解与收获！
一，什么是数据结构？
我们先从一个公式开始：
?程序=算法+数据结构??
?这是由N.沃思（Niklaus ?Wirth)（图灵奖获得者）提出，其将数据结构的功能形象化的展现出来。这个公式将在以后的学习中深深地印在每个编程学习者的脑海里。
那么什么是数据结构？
数据结构（Data Structure）是相互之间存在一种或多种特定关系的数据元素的集合。
看到这里，相必大家和作者有一样的想法：不就是集合吗？集合高一就学了，简单！但当我拿到课本，听了（非常认真）老师讲的第一节课后，我就很快打消以上念头，并在心里告诉自己：是我肤浅了！
几乎每本教材都对数据结构开了一篇绪论课！这代表着数据结构绝对是个重量级的选手！
看到这里，读者肯定在想：扯这么多废话，还不进入正题？
哈哈哈，其实作者也不想，作者目前也是数据结构初阶的学习，对这门课程也是充满了未知，但相信大家在一起交流学习，一定能够深刻理解这门课程！下面还是需要引入一些必要知识，有助下面章节的学习。
1.电子计算机的主要用途：
?早期： ? ? ? 主要用于数值计算。
?后来： ? ? ? 处理逐渐扩大到非数值计算领域，能处理多种复杂的具有一定结构关系的数据
那如何求解非数值计算的问题？? ? ?
设计出合适的数据结构及相应的算法 即：首先要考虑对相关的各种信息如何表示、组织和存储?
数据结构的研究内容为： 研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作。
数据结构主要涉及领域及地位：
数据结构的基本概念：
?
数据结构分类：
★?存储结构是逻辑结构在计算机内的映像
二，算法
算法定义：一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列
算法的描述： ?（1）自然语言? （2）流程图 ?（3）程序设计语言?（4?伪码??（5）类C
?
?
?
?
算法的特性： ?
输入 ?有0个或多个输入
输出 ?有一个或多个输出(处理结果) ?
确定性 ?每步定义都是确切、无歧义的
有穷性 ?算法应在执行有穷步后结束 ?
有效性 ?每一条运算应足够基本
算法的评价
正确性 可读性 健壮性 高效性（时间代价和空间代价）
算法的效率的度量
?算法效率：用依据该算法编制的程序在计算机上执行所消耗的时间来度量?? ?
（1）事后统计 （2）事前分析估计
?三，线性表
?线性表的定义 ? ? ? ? ?线性表是由具有相同类型的有限多个数据元素组成的一个有序序列。
??对于线性表，常用的基本运算用抽象数据类型描述如下：
ADT List?{
数据集合D：D={a1, a2,…, an},n≥0，D中的元素是DataType类型
数据关系R：R={r}，r={ <ai, ai+1>| i=1,2,…,n-1}?
基本操作P：
InitList(&L) ：线性表的初始化。 操作结果：构造一个空的线性表L。
InsertList(&L,i ,x) ：插入操作。
初始条件： 线性表L存在，插入位置1≤i≤n+1（n为插入前的表长），
操作结果：在线性表L的第i个位置插入一个值为x的新元素，插入后的表长加1。
DeleteList(&L,i)：删除操作。
初始条件：线性表L存在，删除位置1≤i≤n（n为删除前的表长），
操作结果：在线性表L删除第i个位置的数据元素，删除后的表长减1。
IsEmptyList(L)?：?判断线性表是否为空。
初始条件：线性表L存在，
操作结果：若线性L为空，则返回值1；否则返回值0。
LocationList(L,x)： 查找值为x结点位置。
初始条件：线性表L存在，已知数据元素x，
操作结果：若在L中找到第一个和x值相匹配的数据元素，则返回它在L中的位置；否则返回-1。
LengthList(L):求线性表L的表长。
初始条件：线性表L存在，
操作结果：返回线性表中所含元素的个数。
} ADT List；
?
线性表之顺序表?
线性表采用顺序存储的方式存储就称之为顺序表。
1.顺序表的存储：
?
线性表的顺序存储结构示意图：
?假设顺序表的每个结点占用k个内存单元，用location (ai)表示顺序表中第i个元素的存储地址。则有： ? ?location (ai+1) = location (ai) +k ? ?location (ai) = location(a1) + (i-1)*k? 其中，location(a1)是线性表的第一个元素a1的存储地址，也称线性表的起始位置或基地址。
?顺序表的类型定义：
//顺序表类型定义
#define MAXSIZE 100 //MAXSIZE是根据实际问题定义的足够大的整数常量
typedef int DataType;
typedef struct{
DataType data[MAXSIZE];
int length；
}SqList; //定义顺序表类型
定义一个顺序表语句：SqList L；
L是顺序变量，L.data表示顺序表的基地址，顺序表中的数据元素a1~an分别存放在L.data[0]~L.data[n-1]中，L.length表示顺序表的当前长度。
顺序表的初始化算法：
//顺序表的初始化算法
void InitSqList(SqList & L)
{
L.length=0;
}
?顺序表的插入算法：
?线性表插入x前后的状态?
//顺序表的插入算法
void InsertSqList(SqList &L,int i,DataType x)
{ int j;
if(L.length==MAXSIZE)
{ printf("\n顺序表是满的,无法插入元素!");
exit(1);
}
if(i<1||i>L.length+1)
{ printf("\n指定的插入位置不存在!");
exit(1);
}
for(j=L.length-1;j>=i-1;j--)
L.data[j+1]=L.data[j];
L.data[i-1]=x;
L.length++;
}
顺序表的删除算法：
?删除操作前后的状态
//顺序表的删除算法
void DeleteSqList(SqList &L,int i)
{ if(L.length==0)
{ printf("\n顺序表是空的,无法删除元素!");
exit(1);
}
if(i<1||i>L.length)
{ printf("\n指定的删除位置不存在!");
exit(1);
}
for(j= i;j< L.length;j++)
L.data[j-1]=L.data[j];
L.length--;
}
顺序表的按值查找 ：
给定数据x，在顺序表L中查找第一个与它相等的数据元素。如果查找成功，则返回该元素在表中的位置；如果查找失败，则返回-1。
//顺序表的按值查找算法
int ?LocationSqList(SqList L, DataType x)
{ ?for (i=0; i<L.length; i++) ? ?
? if (L.data[i] == x)?? ??? ?//查找成功,返回元素位置i ? ?
? ?return i+1; ? ?
?if (i == L.length) ? ??? ? ?//查找失败,返回-1 ? ? ?
?return -1; }顺序表的排序算法：
例1有顺序表A和B，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表C，要求C的元素也是从小到大的升序排列。 ? 算法思路：
void merge(SqList A, SqList B, SqList &C) { int i,j,k; i=0;j=0;k=0; while (i<=A.length-1 && j<=B.length-1) if (A.data[i]<B.data[j]) C.data[k++]=A.data[i++]; else C.data[k++]=B.data[j++]; while (i<=A.length-1) C.data[k++]=A.data[i++]; while (j<=B.length-1) C.data[k++]=B.data[j++]; C.length=k; }
顺序表的逆置算法：
例2：有一线性表的顺序表示 (a1，a2，… ，an) ，设计一算法将该线性表逆置成逆线性表(an，an-1，… ，a1)，要求用最少的辅助空间。 ? ?算法思路：
//顺序表的逆置算法 void ReverseSqList(SqList &L) { //将线性表逆置，入口参数:指向顺序表的指针,返回值：无 int i; DataType x; for (i=1; i<=L.length/2;i++) { x=L.data[i-1]; //完成元素ai与an-i+1交换 L.data[i-1]=L.data[L.length-i]; L.data[L.length–i]=x; } }
