第2章-线性表及其顺序存储祥解.pptxVIP

数据结构;高等学校精品课程（省级） 国家十二五规划教材;; 线性表是一种常用的数据结构，本章介绍线性表及其顺序存储，并对栈和队列及它们的顺序实现给出了详细的设计描述。 ;例1、26个英文字母组成的字母表 （A，B，C、…、Z）;姓 名;例4、一副扑克的点数 （2，3，4，…，J，Q，K，A） 从以上例子可看出线性表的逻辑特征是： 在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2； 有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋an-1； 其余的内部结点ai(2≦i≦n-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。 线性表是一种典型的线性结构。;2.2.1顺序表 ;顺序表的存储结构如下图所示： ;2.2.2顺序表的实现 ;顺序表的存储结构的C语言描述如下： /*顺序表的头文件，文件名sequlist.h */ #define MAXSIZE 100 typedef int datatype; typedef struct{ datatype a[MAXSIZE]; int size; }sequence_list;;顺序表的几个基本操作的具体实现 ：;/?????????????????????????????????????????????????/ /? 函数功能:在顺序表后部进行插入操作 ?/ /? 函数参数:指向sequence_list型变量的指针变量slt ?/ /? datatype类型的变量x ? ?/ /? 函数返回值:空 ?/ /? 文件名:sequlist.c, 函数名:append() ?/ /?????????????????????????????????????????????????/ void append(sequence_list ?slt,datatype x) { if(slt-size==MAXSIZE) {printf(顺序表是满的!);exit(1);} slt-a[slt-size]=x; slt-size=slt-size+1; } 算法2.2 在顺序表后部进行插入操作; 打印顺序表的各结点值 ;判断顺序表是否为空 ; 查找顺序表中值为x的结点位置 ; 取得顺序表中第i个结点的值 ; 顺序表的插入运算是将一个值为x的结点插入到顺序表的第i个位置0≤i≤n，即将x插入到ki-1和ki之间，如果i=n，则表示插入到表的最后，一般地可表示为： 插入前：{k0, k1, …, ki-1, ki, …, kn-1} 插入后：{k0, k1, …, ki-1,x, ki, …, kn-1} ;/??????????????????????????????????????????????????????/ /? 函数功能:在顺序表的position位置插入值为x的结点 ?/ /? 函数参数:指向sequence_list型变量的指针变量slt ?/ /? datatype型变量x,int型变量 position ?/ /? 函数返回值:空 文件名:sequlist.c,函数名:insert() ?/ /??????????????????????????????????????????????????????/ void insert(sequence_list ?slt,datatype x,int position) { int i; if(slt-size==MAXSIZE) {printf(\n顺序表是满的!没法插入!);exit(1);} if(position0||positionslt-size) {printf(\n指定的插入位置不存在!);exit(1);} for(i=slt-size;iposition;i--) slt-a[i]=slt-a[i?1]; slt-a[position]=x; slt-size++; } 算法2.7 在顺序表的position位置插入值为x的结点; 算法2.7中，所花费的时间主要是