下载文档原格式
1.3线性表及其顺序存储结构1.线性表的基本概念线性表是由n个数据元素组成的一个有限序列，表中的每一个数据元素，除了每一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。
即线性表或是一个空表。
显然线性表是一种线性结构，数据元素在线性表中的位置只取决于它们自己的序号，即数据元素之间的相对位置是线性的。
非空线性表有如下一些结构特征：（1）有且只有一个根结点，它无前件；（2）有且只有一个根结点，它无后件；（3）除了根结点与终端结点外，其他所有结点有且只有一个前件，也只有且只有一个后件。
2.线性表的存储结构线性表的顺序存储结构具有以下两个特征：（1）线性表中所有元素所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
由此可以看出，在线性表的顺序存储结构中，其前件和后件两个元素在存储空间中是紧邻的，且其前件元素一定存储在后件元素的前面。
在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储看见。
因为程序设计语言中的一维数组与计算机中的实际的存储空间结构是类似的，这就便于用程序设计语言对线性表进行各种运算处理。
在线性表的顺序存储结构中，可以对线性表进行各种处理。
主要的运算有如下几种：（1）在线性表的指定位置处加入一个新的元素；（2）在线性表中删除指定的元素；（3）在线性表中查找某个特定的元素；（4）对线性表中的元素进行整序；（5）按要求将一个线性表分解成多个线性表；（6）按要求将多个线性表合并成一个线性表；（7）复制一个线性表；（8）逆转一个线性表等。
3.顺序表的插入运算设长度为n的线性表为（a1,a2,a3,a4,…,ai, …,an）现要在线性表的第i个元素ai之前插入一个新元素b,插入后得到长度为n+1的线性表为（a1,a2,a3,a4,…,aj,aj+1, …,an,an+1）则插入前后的两线性表中的元素满足如下关系：a j0<j<iaj= b j=ia j-1i<j<n在一般情况下，要在第i（1<i<n+1）元素之间插入一个新元素时，首先要从最后一个元素开始，直到第i个元素之间共n-i+1个元素依次向后移动一个位置，移动结束后，第i个位置就被空出，然后将新元素插入到第i项。
数据结构习题及答案第1章算法一、选择题1.算法的时间复杂度是指（）。
A）执行算法程序所需要的时间B）算法程序中的指令条数C）算法执行过程中所需要的基本运算次数D）算法程序的长度2.算法的空间复杂度是指（）。
A）算法程序的长度B）算法程序所占的存储空间C）算法执行过程中所需要的存储空间D）算法程序中的指令条数3.下面（）的时间复杂度最好（即执行时间最短）。
logn)O(）O(n ) B）A2logn2 ) D）O(n)C）O(n24.下面累加求和程序段的时间复杂度为（）。
int sum(int a[],int n){int i, s=0;for (i=0;i<n;i++)< p="">s+=a[i];return s;}logn ) ）O(A）O(1 ) B22)）O(nC）O(n ) D中的算法，c[][]相加的结果存放到b[][]n阶矩阵5.下面是将两个n阶矩阵a[][]与。
该算法的时间复杂度为（）void matrixadd(int a[][],intb[][],c[][],int n){int i,j;for (i=0;i<n;i++)< p="">for(j=0;j<n;j++)< p="">c[i][j]=a[i][j]+b[i][j];}nlog) ）O(1 ) B）O(A22) ）O(nO( n ) DC）。
6.下面程序段的时间复杂度为（） 1int i=0,s1=0,s2=0;while(i<n)< p="">{if(i%2)s1+=i;elses2+=i;i++;}nlog) O(A）O(1 ) B）22) ）O(nC）O(n ) D ）。
7.下面程序段的时间复杂度为（int prime(int n){int i=1;int x=(int)sqrt(n);while(i<=x){i++;if(n%i==0)break;}if(i>x)return 1;elsereturn 0;}nlog) O(O(1 ) BA））2n) O(）CO(n ) D））下面程序段的时间复杂度为（8.int fun(int n){int i=1,s=1;while(s<n)< p="">{i++;s+=i;}return i;}nlog)O(n/2) BA））O(2 2n) ）O(C）O(n ) D9.下面程序段的时间复杂度为（）int i,j,m,n,a[][];for(i=0;i<m;i++)< p="">for(j=0;j<n;j++)< p="">a[i][j]=i*j;22) ）O(nA）O(m) BO(m+n) ）C）O(m*n ) D ）10. 下面程序段的时间复杂度为（int sum1(int n){int i,p=1,s=0;for(i=1;i<=n;i++){p*=i;s=s+p;}return s;}nlog) ）O(A）O(1 ) B22)O(n ) D）O(nC）二、填空题复杂度。
一、实验目的：. 掌握线性表的逻辑特征. 掌握线性表顺序存储结构的特点，熟练掌握顺序表的基本运算. 熟练掌握线性表的链式存储结构定义及基本操作. 理解循环链表和双链表的特点和基本运算. 加深对顺序存储数据结构的理解和链式存储数据结构的理解，逐步培养解决实际问题的编程能力二、实验内容：（一）基本实验内容（顺序表）：建立顺序表，完成顺序表的基本操作：初始化、插入、删除、逆转、输出、销毁, 置空表、求表长、查找元素、判线性表是否为空；1．问题描述：利用顺序表,设计一组输入数据（假定为一组整数），能够对顺序表进行如下操作：. 创建一个新的顺序表，实现动态空间分配的初始化；. 根据顺序表结点的位置插入一个新结点(位置插入)，也可以根据给定的值进行插入(值插入)，形成有序顺序表；. 根据顺序表结点的位置删除一个结点(位置删除)，也可以根据给定的值删除对应的第一个结点，或者删除指定值的所有结点(值删除)；. 利用最少的空间实现顺序表元素的逆转；. 实现顺序表的各个元素的输出；. 彻底销毁顺序线性表，回收所分配的空间；. 对顺序线性表的所有元素删除，置为空表；. 返回其数据元素个数；. 按序号查找，根据顺序表的特点，可以随机存取，直接可以定位于第i 个结点，查找该元素的值，对查找结果进行返回；. 按值查找，根据给定数据元素的值，只能顺序比较，查找该元素的位置，对查找结果进行返回；. 判断顺序表中是否有元素存在，对判断结果进行返回；. 编写主程序，实现对各不同的算法调用。
2．实现要求：对顺序表的各项操作一定要编写成为C（C++）语言函数，组合成模块化的形式，每个算法的实现要从时间复杂度和空间复杂度上进行评价；. “初始化算法”的操作结果：构造一个空的顺序线性表。
对顺序表的空间进行动态管理，实现动态分配、回收和增加存储空间；. “位置插入算法”的初始条件：顺序线性表L 已存在，给定的元素位置为i，且1≤i≤ListLength(L)+1 ；操作结果：在L 中第i 个位置之前插入新的数据元素e，L 的长度加1；. “位置删除算法”的初始条件：顺序线性表L 已存在，1≤i≤ListLength(L) ；操作结果：删除L 的第i 个数据元素，并用e 返回其值，L 的长度减1 ；. “逆转算法”的初始条件：顺序线性表L 已存在；操作结果：依次对L 的每个数据元素进行交换，为了使用最少的额外空间，对顺序表的元素进行交换；. “输出算法”的初始条件：顺序线性表L 已存在；操作结果：依次对L 的每个数据元素进行输出；. “销毁算法”初始条件：顺序线性表L 已存在；操作结果：销毁顺序线性表L；. “置空表算法”初始条件：顺序线性表L 已存在；操作结果：将L 重置为空表；. “求表长算法”初始条件：顺序线性表L 已存在；操作结果：返回L 中数据元素个数；. “按序号查找算法”初始条件：顺序线性表L 已存在，元素位置为i，且1≤i≤ListLength(L)操作结果：返回L 中第i 个数据元素的值. “按值查找算法”初始条件：顺序线性表L 已存在，元素值为e；操作结果：返回L 中数据元素值为e 的元素位置；. “判表空算法”初始条件：顺序线性表L 已存在；操作结果：若L 为空表，则返回TRUE，否则返回FALSE；分析: 修改输入数据，预期输出并验证输出的结果，加深对有关算法的理解。
线性表的顺序存储结构线性表的顺序存储结构相关概念举个栗⼦：⼤学的时候，宿舍有⼀个同学，帮⼤家去图书馆占座。
他每次去图书馆，挑⼀个好地⼉，把他书包⾥的书，⼀本⼀本按座位放好，若书不够，再把⽔杯，⽔笔都⽤上，长长⼀排，九个座硬是被他占了。
1. 顺序存储的定义线性表的顺序存储结构，指的是⽤⼀段地址连续的存储单元依次存储线性表的数据元素。
⽰意图：2. 顺序存储⽅式线性表的顺序存储结构，其实就和刚才图书馆占座的例⼦⼀样，就是在内存中找了块地⼉，通过占位的形式，把⼀定内存空间给占了，然后把相同数据类型的数据元素依次存放在这块空地中。
既然线性表的每个数据元素的类型都相同，所以可以⽤⼀维数组来实现顺序存储结构，即把第⼀个数据元素存到数组下标为0的位置中，接着把线性表相邻的元素存储在数组中相邻的位置。
这⾥有⼏个关键的地⽅：1）为了建⽴⼀个线性表，要在内存中找⼀块地，这块地的第⼀位置就⾮常关键，他是存储空间的起始位置2）数组的长度就是这个最⼤存储容量3）线性表的当前长度3. 数据长度与线性表长度区别1）数组的长度是存放线性表的存储空间的长度，存储分配后这个量⼀般是不变的。
当然，⼀般⾼级语⾔是可以通过编程⼿段实现动态分配数组，不过这会带来性能上的损耗。
2）线性表的长度是线性表中数据元素的个数，随着线性表插⼊和删除操作的进⾏，这个量是变化的。
在任意时刻，线性表的长度应该⼩于等于数组的长度。
4. 地址计算⽅法数组是从0开始第⼀个下标的，于是线性表的第i个元素是要存储在数组下标为i-1的位置，即数据元素的序号和存放它的数组下标之间存在对应关系：存储器中的每个存储单元都有⾃⼰的编号，这个编号称为地址。
假设每个数据元素占⽤的都是c个存储单元，那么每个数据元素地址可通过公式计算得到: LOC(ai)=LOC(a1)+(i-1)*c它的存取时间性能为O(1)。
我们通常把具有这⼀特点的存储结构称为随机存取结构。
相关操作1. 获得元素操作（GetElem）获取元素的思路：1）考虑边界问题，顺序线性表L已存在（⾮空表），并且i必须在1<=i<=ListLength(L)范围内，否则抛出异常2）将数值下标为i-1的值返回即可C语⾔的实现如下：1// 获得元素操作2#define OK 13#define ERROR 04#define TRUE 15#define FALSE 06 typedef int Status;7/*Status是函数的类型,其值是函数结果状态代码，如OK等*/8/*初始条件：顺序线性表L已存在，1<=i<=ListLength(L)*/9/*操作结果：⽤e返回L中第i个数据元素的值*/1011 Status GetElem(SqList L, int i, ElemType *e)12 {13if (L.length == 0 || i < 1 || i > L.length)14return ERROR;15 *e = L.data[i-1];16return OK;17 }PHP的实现如下：1 <?php2class Seqlist{34private$seq_list; //顺序表5/**6 * 顺序表初始化7 *8 * @param mixed $seq_list9 * @return void10*/11public function __construct($seq_list=array()){12$this->seq_list = $seq_list;13 }1415/**16 * 返回顺序表元素个数17 *18 * @return int19*/20public function listLength(){21return count($this->seq_list);22 }2324/**25 * 返回顺序表中下标为i的元素值26 *27 * @param int i28 * @return mixed 如找到返回元素值，否则返回false29*/30public function getElem($i){31if ($this->seq_list && $i > 0 && $i <= $this->listLength()) {32return$this->seq_list[$i-1];33 }else{34return false;35 }36 }37 }2. 插⼊操作插⼊算法的思路：1）如果插⼊位置不合理（1<=i<=ListLength(L)+1），抛出异常说明：最好的情况就是，插⼊的位置为末尾：ListLength(L)+1（不是数组下标）,这个时候不⽤移动元素，时间复杂度是O(1) 2）如果线性表长度⼤于等于数组长度，则抛出异常或动态增加容量3）从最后⼀个元素开始向前遍历到第i个位置，分别将它们都向后移动⼀个位置4）将要插⼊元素填⼊位置 i 处5）表长加1C语⾔的实现如下：1// 插⼊操作2#define OK 13#define ERROR 04#define TRUE 15#define FALSE6 typedef int Status;7/*初始条件：顺序线性表L已存在，1<=i<=ListLength(L)*/8/*操作结果：在L中第i个位置之前插⼊新的数据元素e,L的长度加1*/910 Status ListInsert(SqList *L, int i, ElemType e)11 {12int k;13if (L->length == MAXSIZE) /*顺序线性表已经满*/14return ERROR;15if (i < 1 || i > L->length + 1) /*当i不在范围内时*/16return ERROR;1718if (i <= L->length) /*若插⼊数据位置不在表尾*/19 {20for (k = L->length - 1; k >= i - 1; k--) /*将要插⼊位置后数据元素向后移动⼀位*/21 {22 L->data[k + 1] = L->data[k];23 }24 }25 L->data[i - 1] = e; /*将新元素插⼊*/26 L->length++;27return OK;28 }PHP的实现如下：1 <?php2class Seqlist{34private$seq_list; //顺序表5/**6 * 顺序表初始化7 *8 * @param mixed $seq_list9 * @return void10*/11public function __construct($seq_list=array()){12$this->seq_list = $seq_list;13 }1415/**16 * 在指定位置 i 插⼊⼀个新元素 $value17 *18 * @param int $i19 * @param mixed $value20 * @return bool 插⼊成功返回 true, 否则返回 false21*/22public function listInsert($i, $value){23// 三种情况：插⼊位置不合理24if ($i > $this->listLength()+1 || $i < 1) {25return false;26 }elseif ($i == $this->listLength()+1) {27// 最好的情况：元素插⼊到最后⼀个位置，不需要移动元素，时间复杂度为O(1)28$this->seq_list[$i-1] = $value;29 }else{30// 从 $i-1 到最后的元素位置向后移动⼀位31for ($k = $this->listLength()-1; $k >= $i-1; $k--) {32$this->seq_list[$k+1] = $this->seq_list[$k];33 }34$this->seq_list[$i-1] = $value;35 }3637return true;38 }39 }这⾥有⼀个疑问，因为前⾯我们提到了：在任意时刻，线性表的长度应该⼩于数组的长度。
数据结构（线性表的存储结构）顺序存储结构 定义：⼀段地址连续的储存单元依次存储的数据元素。
实际上就是把数组封装进结构体，增加⼀个记录当前长度的变量。
时间复杂度：存储，查看，时间复杂度为 O(1) 删除，插⼊，时间复杂度为 O(n)优点：⽆需为表⽰表中元素之间的逻辑关系⽽添加额外的存储空间 可以快速的存，取表中的任意位置的元素缺点：插⼊和删除操作需要移动⼤量的元素 当线性表的长度变化较⼤时，难以确定存储空间的容量 容易造成存储空间的碎⽚1 #include <stdio.h>2 #include <malloc.h>3#define MAXSIZE 204 typedef int ElemType;56 typedef struct SQList{7 ElemType data[MAXSIZE];//对数组进⾏封装8int length;//当前长度9 }List,* PList;1011void printList(PList);12void insert(PList);13void add(PList);14void del(PList);15void delAll(PList);1617void delAll(PList pL){18 pL->length=0;19 }2021void del(PList pL){22int i=0;23 printf("请输⼊要删除的元素位置:");24 scanf("%d",&i);25if(i>0 && i<=pL->length){26 i--;27while(i<pL->length){28 pL->data[i]=pL->data[i+1];29 i++;30 }31 pL->length--;32 }else33 printf("删除的位置错误！");34 }3536void printList(PList pL){37int i=0;38while(i<pL->length){39 printf("%d ",pL->data[i]);40 i++;41 }42 printf("\n");43 }4445void insert(PList pL){46int n=0,i=0;47 ElemType val;48 printf("请输⼊要插⼊的整数值（-1结束）:");49 scanf("%d",&val);50 printf("请输⼊要插⼊的位置:");51 scanf("%d",&i);52while(val != -1){53if(pL->length+1 < MAXSIZE){54if(i>0 && i<=pL->length){55for(n=pL->length ; n>=i ; n--){56 pL->data[n]=pL->data[n-1];57 }58 pL->data[n]=val;59 pL->length++;60 }else61 printf("插⼊位置有误！\n");62 }else{63 printf("线性表已满,⽆法插⼊！\n");64break;65 }66 printf("请输⼊要插⼊的整数值（-1结束）:");67 scanf("%d",&val);68if(val == -1)69break;70 printf("请输⼊要插⼊的位置:");71 scanf("%d",&i);72 }73 }7475void add(PList pL){76 ElemType val;77 printf("请输⼊要添加的整数值（-1结束）:");78 scanf("%d",&val);79while(val != -1){80if(pL->length < MAXSIZE){81 pL->data[pL->length]=val;82 pL->length++;83 }else{84 printf("线性表已满,⽆法添加！\n");85break;86 }87 printf("请输⼊要添加的整数值（-1结束）:");88 scanf("%d",&val);89 }90 }9192void main(){93int val=0;94int i=0;95 PList pL=(struct SQList *)malloc(sizeof(struct SQList));96 pL->length=0;9798 add(pL);99 printList(pL);100101 insert(pL);102 printList(pL);103104 del(pL);105 printList(pL);106107 delAll(pL);108 printList(pL);109 }链式存储结构 定义：⽤⼀组任意的存储单元存储线性表的数据元素，这组存储单元可以在内存中未被占⽤的任意位置 链式存储结构：除了要存储数据元素信息（数据域），还要存储他后继元素的存储地址（指针域）——指针。
数据结构（⼆）：线性表的链式存储结构1、为什么要使⽤链式存储结构？因为我们前⾯讲的线性表的顺序存储结构，他是有缺点的。
最⼤的缺点就是插⼊和删除时需要移动⼤量元素，这显然就需要耗费时间。
要解决这个问题，我们就需要分析⼀下为什么当插⼊和删除时，就要移动⼤量元素，因为相邻两元素的存储位置也具有相邻关系，它们在内存中的位置也是挨着的，中间没有空隙，当然就⽆法快速介⼊，⽽删除之后。
当中就会留出空隙，⾃然就需要弥补。
问题就出在这⾥。
为了解决这个问题，⾃然⽽然的就出现了链式存储结构。
2、线性表链式存储结构的特点：线性表的链式存储结构不考虑元素的存储位置，⽽是⽤⼀组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的，这就意味着，这些数据元素可以存在内存未被占⽤的任意位置。
顺序存储结构：只需要存储数据元素信息。
链式存储结构：除了要存储数据元素信息之外，还要存储⼀个指⽰其直接后继元素的存储地址。
3、关键词：数据域：存储数据元素信息的域。
指针域：存储直接后继位置的域。
指针或链：指针域中存储的信息。
结点（Node）：指针域+数据域组成数据元素的存储映像。
头指针：链表中第⼀个结点的存储位置。
头节点：在单链表的第⼀个结点前附设⼀个结点，成为头结点。
头结点的数据域不可以存储任何信息，可以存储线性表的长度等附加信息，头结点的指针域存储指向第⼀个结点的指针。
4、单链表：定义：n个结点链成⼀个链表，即为线性表的链式存储结构，因此此链表的每个结点中只包含⼀个指针域，所以叫做单链表。
PS：线性链表的最后⼀个结点指针为“空”,通常⽤NILL或“^”符号表⽰。
头节点：在单链表的第⼀个结点前附设⼀个结点，成为头结点。
头结点的数据域不可以存储任何信息，可以存储线性表的长度等附加信息，头结点的指针域存储指向第⼀个结点的指针。
5、头结点与头指针的异同（1）头结点头结点是为了操作的统⼀和⽅便⽽设⽴的，放在第⼀个元素的结点之前，其数据域⼀般⽆意义（也可存放链表的长度）有了头结点，对第⼀元素结点前插⼊和删除第⼀结点，其操作就统⼀了头结点不⼀定是链表的必要素（2）头指针头指针式指向第⼀个结点的指针，若链表有头结点，则是指向头结点的指针。
