软考之路--数据结构之线性表，软考数据结构
数据就是数值，也就是我们通过观察、实验或计算得出的结果。数据有很多种，最简单的就是数字。数据也可以是文字、图像、声音等。数据可以用于科学研究、设计、查证等。结构，组成整体的各部分的搭配和安排，两者完美结合在一起，我们这样需要重新认识她，对她重新审视与定义：数据结构是程序设计的重要理论和技术基础，她所讨论的内容和技术，对从事软件项目的开发有重要作用，通过学习数据结构，我们学会从问题出发，分析和研究计算机加工的数据的特性，以便为应用所设计的数据悬着适当的逻辑结构、存储结构及其相应的操作方法，为提高应用计算机解决问题的效率服务。
学习希赛视频有一段日子了，这一段日子夹杂的自考和等级考，夸张点儿来说，有过欢笑，也有过泪水，欢笑的是昨天等级考试抽到的两道大题都是原题，泪水的是，第二题有一个空少些了一个return，又想起那句话，总是要等到考试的时候，才知道该念的书没有念，大题一共六十分，如果按往年的算分制度，需要占百分之六十，也就是说六十分要考三十六分才算合格，可是我满打满算，最后一题只能拿到三十四分，可是后话是，过了我开心，过不了更开心，可以再学一遍C++`(*∩_∩*)′，今天小编主要来讲解一下数据结构的数据表，首先，我们来看一下基本数据结构的一张图：
了解了基本数据结构，进入到我们今天的主题线性表，该博文主要围绕以下内容展开进行阐述：
一、线性表
概念：线性表是最简单，最基本，也是最常用的一种线性结构，她有两种存储存储方法，顺序存储和链式存储，主要的基本操作是插入，删除和查找等。
分类：线性表分为顺序表和链表，其中链表又分为单链表、循环链表和双链表，依次进行分析。
顺序表，如下图所示：
顺序结构：顺序结构是最简单的程序结构，也是最常用的程序结构，只要按照解决问题的顺序写出相应的语句就行，它的执行顺序是自上而下，依次执行。举个简单的例子，a = 3，b = 5，现交换a，b的值，这个问题就好像交换两个杯子水，这当然要用到第三个杯子，假如第三个杯子是c，那么正确的程序为： c = a； a = b； b = c； 执行结果是a = 5，b = c = 3。
链表，如下图所示：
链表：链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。
链表的类别：单链表、循环链表、双链表。如下图所示：
数据域：存放数据；指针域：存放指向下一个节点的地址；循环链表：最后一个节点她的下一个节点是头节点。
双链表：有两个指针域，从两个不同的方向把链表链接起来。双链表可以从两个方向移动，单链表朝单一的方向移动，双链表的灵活度优于单链表。双链表的开支会大一些，因为她有两个指针域。 单双链表的删除和插入：单链表的删除：结点的删除，删除a2，方法：把a1的指针域直接指向a3，跳过a2，就可以了，a2就从链表中删除了，还有一个工作需要把a2释放掉。把要删除的前序结点，前序结点的next域指向她的后序结点。单链表的插入：删除结点是把前序指向后序，那么插入一个结点就是一个逆向的过程，把新的结点，从需要插入的位置，把她的前序结点next域指向新加入的结点，再把新加入的结点的next域指向下一个结点，就可以了。双链表的删除和插入：牵涉两个方面，从左至右列出来，从右至左列出来，并不是简单的一条链过去，一条链过来就完成的，我们需要把四个步骤都写出来，把两个操作的第一步都先完成，完成之后，接着第二步。 顺序表PK链表
二、队列
概念：队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。比如，去食堂排队，排头最先买到菜，后面来的同学排的队尾；进车站时，安检行李，先进去的最先出来，后进去的后出来。
分类：顺序队列和循坏队列；队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。在队列这种数据结构中，最先插入的元素将是最先被删除的元素；反之最后插入的元素将是最后被删除的元素，因此队列又称为“先进先出”（FIFO—first in first
out）的线性表。如下图：
顺序队列：
循环队列：
ps：“对”字写错了，大家不要见笑哦。
三、栈
栈：并不是一个实实在在存在的东西，是逻辑上的一个概念，一种思想，一种理念，她不像链式存储和顺序存储一个一个结点，很有规律，她是在顺序存储和链式存储之上的，是逻辑的概念，栈既可以用链式结构来实现，也可以用顺序结构来实现--即数组。定义一个规则，先进后出即可。如下：
小编寄语：线性表（亦作顺序表）是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。线性表的逻辑结构简单，便于实现和操作。因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构。其中栈和队列是一种特殊的线性表，软考之路，未完待续......
#include<iostream.h>
#include<stdlib.h>
#include<iostream.h>
typedef struct seqlist //定义线性表的顺序存储结构
{
int *elem; //存储空间分配的首地址
int length ; //线性长度
}seqlist;
//此变量可作为线性表数据类型定义线性表
void init(seqlist &l) //线性表的初始化
{
l.elem=new int[20]; //分配存储空间存储线性表中的元素
l.length=0; //空线性表的长度为0
}
void delseqlist(seqlist &l) //销毁建立的线性表
{
delete []l.elem;
l.length=0;
}
void insert(seqlist &l,int i, int x)//元素e插入线性表中的第i个位置上
{
if(i<1||i>l.length+1)
cout<<"i值不合法！"<<endl; //错误处理
for(int j=l.length;j>=i;j--)
l.elem[j+1]=l.elem[j]; //第i个元素及其后的元素依次后移
l.elem[i]=x; //插入新元素于第i个位置上
l.length++; //线性表的长度增1
}
void printout(seqlist &l) //输出线性表当中的所有元素
{
int j;
for(j=1;j<=l.length;j++)
cout<<l.elem[j]<<" ";
}
int llength(seqlist &l) //求线性表的长度
{
return l.length;
}
int locateElem(seqlist &l, int e) //在顺序表L中查找第一个值于e相等的数据元素
{
int i=1;
int *p;
p=l.elem; p++; //p指向线性表中的第一个元素
while (i<=l.length && *p++!=e ) //依次向后进行比较
++i;
if(i<=l.length)
return i;
else
return 0; //返回结果
}
void Delete( seqlist &l,int i,int &e)//此函数删除第i个元素，并将其值用e返回
{
int *p,*q;
if((i<1)||(i>l.length)) cout<<......余下全文>>
include "stdlib.h"
#include "stdio.h"
//顺序表基本操作实现
bool InitList_Sq(SqList &L){//初始化
L.elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int));
if(!L.elem) exit(1);
L.length=0;
L.listsize=LIST_INIT_SIZE;
return 1;
}
bool ListInsert_Sq(SqList &L, int i, int e) { // 算法2.4
// 在顺序线性表L的第i个元素之前插入新的元素e，
// i的合法值为1≤i≤ListLength_Sq(L)+1
int *p;
if (i < 1 || i > L.length+1) return false; // i值不合法
if (L.length >= L.listsize) { // 当前存储空间已满，增加容量
int *newbase = (int *)realloc(L.elem,
(L.listsize+LISTINCREMENT)*sizeof (int));
if (!newbase) return false; // 存储分配失败
L.elem = newbase; // 新基址
L.listsize += LISTINCREMENT; // 增加存储容量
}
int *q = &(L.elem[i-1]); // q为插入位置
for (p = &(L.elem[L.length-1]); p>=q; --p) *(p+1) = *p;
// 插入位置及之后的元素右移
*q = e; // 插入e
++L.length; // 表长增1
return true;
} // ListInsert_Sq
void printList_Sq(SqList L){//注意：1.参数是L,而非&L；2.该函数为扩展的操作。
if(L.length>0){
int i=1;
printf("元素的顺序是：");
for(i=1;i<L.length+1;i++){
printf("%d",L.elem[i-1]);
}
printf("\n");
}
}...余下全文>>