C/C++数据结构-顺序表考查题

前言

顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。

实验内容

线性表的顺序存储

完成顺序表的基本操作：初始化、插入、删除、逆转、输出、求表长、查找元素、判断线性表是否为空等操作。

实验步骤

头文件定义

#include<string.h>
#include<ctype.h>
#include<malloc.h> /* malloc()等 */
#include<limits.h> /* INT_MAX 等 */
#include<stdio.h> /* EOF(=^Z 或 F6),NULL */
#include<stdlib.h> /* atoi() */
#include<io.h> /* eof() */
#include<math.h> /* floor(),ceil(),abs() */
#include<process.h> /* exit() */
/* 函数结果状态代码 */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status; 
typedef int Boolean;
typedef int ElemType;

插入：

Status ListInsert_Sq(SqList &L,int i,ElemType e)

{ /* 初始条件：顺序线性表 L已存在，1≤i≤ListLength(L)+1 */

/* 操作结果：在 L中第 i个位置之前插入新的数据元素 e，L的长度加 1 */

ElemType *q,*p;

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

return ERROR;

if(L.length>=MAXSIZE)

return ERROR;

q=       L.elem + i - 1        ;

for(p=L.elem+L.length-1;     p >= q        ;--p)

*(p+1)=*p;

         *q     =e;

++L.length;

return OK;

}

分析：

L为顺序表，L.elem为表中的头元素的首地址。L.elem+L.length-1即为末元素的地址。*(p+1)=*p;将元素后移  所以可以推出q的作用是指向要插入的那个位置的元素，即q=L.elem+i-1 将第i个位置的元素以及后面所有元素向后移动，那么推出for中循环条件：p>=q

删除：

Status ListDelete_Sq(SqList &L,int i,ElemType *e)

{

ElemType *p,*q;

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

return ERROR;

p=L.elem+i-1;

*e=  *p           ;

q=L.elem+L.length-1;

for(     p=L.elem+i      ;p<=q;++p)

    *(p-1)     =*p;

L.length--;

return OK;

}

分析：p指向要删除的元素的地址， e在这段逻辑中貌似并无作用，观察类型为指针，推测用作值返回。即*e=*p。q指向表中末元素的地址。p<=q作为循环的条件语句，当某一次循环++p后，p超出q时候循环结束。可推出p=L.elem+i，*(p-1)=*p

逆序：

Status ListReverse_Sq(SqList &L)

{ /* 初始条件：顺序线性表 L已存在 */

/* 操作结果：依次对L的数据元素逆序存放*/

ElemType t;

int i;

for(i=0;        i<=L.length-i-1        ;i++)

{

t=L.elem[i];

L.elem[i]= L.elem[L.length-i-1];

L.elem[L.length-i-1]=t;

}

printf("\n");

return OK;

}

分析：循环内逻辑为首尾元素互相交换，依次递推。要想让它正确完成逆序，我们要让i不能于后端l.length-i-1发生重叠，所以推出循环的条件语句为i<=L.length-i-1。

打印

Status ListPrint_Sq(SqList L)
{ /* 初始条件：顺序线性表 L已存在 */
/* 操作结果：依次对L的数据元素输出*/
int i;
printf("\n");
for (i = 0; i < L.length; i++)
printf("%d ", L.elem[i]);
return OK;
}

测试

cpp文件：

#include "pubuse.h"
#include"seqlistDef.h" 
#include"seqlistAlgo.h"  

#define _CRT_SECURE_NO_WARNINGS
int main()
{
	SqList L;
	Status i;
	int j, k;
	ElemType t, e;
	i = ListInit_Sq(L);
	if (i == 1) /* 创建空表 L成功 */
		for (j = 1; j <= 5; j++)
			i = ListInsert_Sq(L, j, 2 * j);
	ListPrint_Sq(L);
	printf("\n输入在第几个位置前插入什么元素：");
	scanf_s("%d%d", &k, &e);
	if (ListInsert_Sq(L, k, e))
		ListPrint_Sq(L);
	else
		printf("input error\n");
	printf("\n输入要删除第几位序的元素：");
	scanf_s("%d", &k);
	if (ListDelete_Sq(L, k, &t))
		printf("\n 所删除的元素是 %d", t);
	else
		printf("input error\n");
	printf("\n新生成线性表：");
	ListPrint_Sq(L);
	printf("\n将线性表逆序存储：");
	ListReverse_Sq(L);
	ListPrint_Sq(L);
	return 0;
}

测试结果：