数据结构第二章 ——线性表之顺序表
[TOC]
快期末考试了，正好复习下数据结构。
基本
//INIT 初始化
Status SqInit(Sqlist &L){
L.elem=(ElemType *)malloc (List_Init_Size*sizeof(ElemType));
if (!L.elem)
exit(OVERFLOW);
else
printf("创建成功！\n");
L.length=0;
L.listsize=List_Init_Size;
}
//SqEmpty 判空
Status SqEmpty(Sqlist L){
if (L.length==0)
printf("空表\n");
else
printf("不是空表\n");
return OK;
}
//SqClear 重置线性表是将长度归零
Status SqClear(Sqlist &L){
if(!L.elem) //判断线性表是否存在
exit(OVERFLOW);
L.length=0;
printf("重置成功!\n");
return OK;
}
//SqLength 返回线性表长度
Status SqLength(Sqlist L){
if(!L.elem) //判断线性表是否存在
exit(OVERFLOW);
return L.length;
}
//SqDisplay 打印
void SqDisplay(Sqlist L){
int i;
for (i=0;i<L.length;i++) {
printf("%5d",L.elem[i]);
}
printf("\n");
}
//SqDestroy 销毁
Status SqDestroy(Sqlist &L){
if (L.elem) { // 检查是否为空
free(L.elem); // 删除分配的内存
L.elem = NULL; // 基地址设为空
}
L.length = 0; // 表长设为0
L.listsize = 0; // 表空间设为0
}
//SqGetElem 取顺序表中某个元素
Status SqGetElem(Sqlist L,int pos,ElemType e){
e = L.elem[pos-1];
return e;
}
//SqLocateElem 返回第一次出现elem的位置
Status SqLocateElem(Sqlist L,ElemType e){
int i;
int number =0;
int pos;
for (i=0;i<L.length;i++){
if (L.elem[i]==e){
pos = i+1;
number++;
}
}
if(number == 0)
pos =number;
return pos;
}
插入
//SqInsert
//顺序表的插入需将插入位置（含）后面的元素都往后移
// 1.往后移，因为是顺序表，所以从后往前移动，故 i = L.length-1
// 2.一直到插入位置（含）都需要移动，故 i = i>=pos-1 （我们说的插入位置即 pos 是正序（从 1 开始），所以在数组中的位置为 pos-1 ，又因为含所以要 =
// 3.所谓后移，即右移 即 L.elem[i+1]=L.elem[i] （将左边的值赋给右边）
Status SqInsert(Sqlist &L,int pos,ElemType e){
int i;
//判断插入的合法性
if(pos<1 || pos>L.length+1) //i值太小或太大，均不合法，注意可以插入到最后一个元素的后面那个空白处
return ERROR;
//再判断L是否空间已满，如果已满，需要拉大10个空间
if(L.length>=L.listsize)
{
L.elem=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
if(L.elem==NULL)
{
printf("对不起，申请空间失败，程序将退出\n");
exit(OVERFLOW);
}
L.listsize+=LISTINCREMENT; //总空间大小加10
}
//核心
for (i=L.length-1;i>=pos-1;i--){
L.elem[i+1]=L.elem[i];
}
L.elem[pos-1]=e;
L.length++;
return OK;
}
删除
//Delete
//顺序表的删除需将删除位置（不含）后面的元素都往前移
// 1.往前移，因为是顺序表，所以从插入位置往前移动，故 i = pos （不含，所以为 pos） d
// 2.范围为直到末尾即 L.elem[i-1]
// 3.所谓前移，即左移 即 L.elem[i-1]=L.elem[i]（将右边的值赋值给左边）
Status SqDelete(Sqlist &L,int pos,int &e){
int i;
e = L.elem[pos-1];
if(pos<1 || pos>L.length+1){ //pos值太小或太大，均不合法，
printf("删除位置不合法！\n");
return ERROR;
}
for (i=pos;i<L.length;i++){
L.elem[i-1]=L.elem[i];
}
L.length--;
}
前驱
//SqPriorElem cur 在L第一次出现，则返回它的前面一个 pir
Status SqPriorElem(Sqlist L,int cur,int pir){
int i;
int number = 0;
for (i=0;i<L.length;i++){
if (L.elem[i]==cur ){
pir =L.elem[i-1];
break;
}
number++;
}
if(number==0){
printf("当前为第一个元素，没有前驱！\n");
return ERROR;
}
else
printf("%d的前驱元素为：%d\n",cur,pir);
}
后继
//SqSubsequent cur 在L第一次出现，则返回它的后面一个 sub
Status SqSubsequent(Sqlist L,int cur,int sub){
int i;
int number = 0;
for (i=0;i<L.length;i++){
if (L.elem[i]==cur ){
sub =L.elem[i+1];
break;
}
number++;
}
if(number==L.length-1){
printf("当前为最后一个元素，没有后继！\n");
return ERROR;
}else
printf("%d的后继元素为：%d\n",cur,sub);
}
逆置
//SqConver 以对称位置，两两互换
Status SqConver(Sqlist &L){
int t;
int i,j;
for(i=0,j=L.length-1;i<=L.length/2&&j>=L.length/2;i++,j--){
t=L.elem[i];
L.elem[i]=L.elem[j];
L.elem[j]=t;
}
}
合：
//数据结构第二章
//线性表之顺序表
#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FLASE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;
#define List_Init_Size 100
#define LISTINCREMENT 10
//顺序表的结构体定义
typedef struct
{
ElemType *elem; //元素数组
int length; //长度
int listsize; //当前分配的存储容量
}Sqlist; //顺序表类型的定义
Status SqClear(Sqlist &L);
Status SqDelete(Sqlist &L,int pos,int &e);
void SqDisplay(Sqlist L);
Status SqEmpty(Sqlist L);
Status SqGetElem(Sqlist L,int pos,ElemType e);
Status SqInit(Sqlist &L);
Status SqInsert(Sqlist &L,int pos,ElemType e);
Status SqLength(Sqlist L);
Status SqLocateElem(Sqlist L,ElemType e);
Status SqPriorElem(Sqlist L,int cur,int pir);
Status SqSubsequent(Sqlist L,int cur,int sub);
Status SqConver(Sqlist &L);
Status SqDestroy(Sqlist &L);
int main(){
int i,j,t,m;
ElemType e;
int h;
int num;
int k;
int p1,p2;
//SqInit
Sqlist L;
SqInit(L);
//SqInsert
for ( i=1; i<=10 ;i++) {
L.elem[i-1]=i;
L.length++;
}
printf("插入前数据为：\n");
SqDisplay(L);
SqEmpty(L);
printf("顺序表长度为：%2d\n",SqLength(L));
//num=SqPriorElem(L,5,num);
//printf("5第一次出现在%d",num);
SqInsert(L,5,100);
printf("插入后数据为：\n");
SqDisplay(L);
printf("顺序表长度为：%2d\n",SqLength(L));
//SqGetElem
printf("请输入要返回元素的位置：");
scanf("%d",&h);
e=SqGetElem(L,h,e);
printf("顺序表中第%2d个元素为%2d\n",h,e);
printf("请输入要查找元素：");
scanf("%d",&m);
t=SqLocateElem(L,m);
if (t==0)
printf("顺序表中没有找到%d\n",m);
else
printf("顺序表中出现%d的位置是%d\n",m,t);
SqDisplay(L);
//SqPriorElem
/*
//不知道为什么不能使用多个 scanf ————在C语言中，如果使用字符型变量（就是char型）时在有连续输入的情况下，
//很容易因为出现垃圾字符而导致程序的流程非法。据说是这样可以通过其他的方法规避。
// printf("输入前驱查找元素：\n");
// scanf(" %d",p1);
//printf("输入后继查找元素：\n");
*/
SqPriorElem(L,m,k);
//SqSubsequent
SqSubsequent(L,m,k);
SqDisplay(L);
//SqDelete
SqDelete(L,m,j);
printf("删除元素%2d成功\n",j);
printf("删除元素后为:\n");
SqDisplay(L);
printf("逆置后：\n");
SqConver(L);
SqDisplay(L);
SqLength(L);
printf("顺序表长度为：%2d\n",SqLength(L));
//SqClear(L);
SqDestroy(L);
SqDisplay(L);
return 0;
}
//INIT 初始化
Status SqInit(Sqlist &L){
L.elem=(ElemType *)malloc (List_Init_Size*sizeof(ElemType));
if (!L.elem)
exit(OVERFLOW);
else
printf("创建成功！\n");
L.length=0;
L.listsize=List_Init_Size;
}
//SqEmpty 判空
Status SqEmpty(Sqlist L){
if (L.length==0)
printf("空表\n");
else
printf("不是空表\n");
return OK;
}
//SqClear 重置线性表是将长度归零
Status SqClear(Sqlist &L){
if(!L.elem) //判断线性表是否存在
exit(OVERFLOW);
L.length=0;
printf("重置成功!\n");
return OK;
}
//SqLength 返回线性表长度
Status SqLength(Sqlist L){
if(!L.elem) //判断线性表是否存在
exit(OVERFLOW);
return L.length;
}
//SqDisplay 打印
void SqDisplay(Sqlist L){
int i;
for (i=0;i<L.length;i++) {
printf("%5d",L.elem[i]);
}
printf("\n");
}
//SqDestroy 销毁
Status SqDestroy(Sqlist &L){
if (L.elem) { // 检查是否为空
free(L.elem); // 删除分配的内存
L.elem = NULL; // 基地址设为空
}
L.length = 0; // 表长设为0
L.listsize = 0; // 表空间设为0
}
//SqGetElem 取顺序表中某个元素
Status SqGetElem(Sqlist L,int pos,ElemType e){
e = L.elem[pos-1];
return e;
}
//SqLocateElem 返回第一次出现elem的位置
Status SqLocateElem(Sqlist L,ElemType e){
int i;
int number =0;
int pos;
for (i=0;i<L.length;i++){
if (L.elem[i]==e){
pos = i+1;
number++;
}
}
if(number == 0)
pos =number;
return pos;
}
//SqInsert
//顺序表的插入需将插入位置（含）后面的元素都往后移
// 1.往后移，因为是顺序表，所以从后往前移动，故 i = L.length-1
// 2.一直到插入位置（含）都需要移动，故 i = i>=pos-1 （我们说的插入位置即 pos 是正序（从 1 开始），所以在数组中的位置为 pos-1 ，又因为含所以要 =
// 3.所谓后移，即右移 即 L.elem[i+1]=L.elem[i] （将左边的值赋给右边）
Status SqInsert(Sqlist &L,int pos,ElemType e){
int i;
//判断插入的合法性
if(pos<1 || pos>L.length+1) //i值太小或太大，均不合法，注意可以插入到最后一个元素的后面那个空白处
return ERROR;
//再判断L是否空间已满，如果已满，需要拉大10个空间
if(L.length>=L.listsize)
{
L.elem=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
if(L.elem==NULL)
{
printf("对不起，申请空间失败，程序将退出\n");
exit(OVERFLOW);
}
L.listsize+=LISTINCREMENT; //总空间大小加10
}
//核心
for (i=L.length-1;i>=pos-1;i--){
L.elem[i+1]=L.elem[i];
}
L.elem[pos-1]=e;
L.length++;
return OK;
}
//Delete
//顺序表的删除需将删除位置（不含）后面的元素都往前移
// 1.往前移，因为是顺序表，所以从插入位置往前移动，故 i = pos （不含，所以为 pos） d
// 2.范围为直到末尾即 L.elem[i-1]
// 3.所谓前移，即左移 即 L.elem[i-1]=L.elem[i]（将右边的值赋值给左边）
Status SqDelete(Sqlist &L,int pos,int &e){
int i;
e = L.elem[pos-1];
if(pos<1 || pos>L.length+1){ //pos值太小或太大，均不合法，
printf("删除位置不合法！\n");
return ERROR;
}
for (i=pos;i<L.length;i++){
L.elem[i-1]=L.elem[i];
}
L.length--;
}
//SqPriorElem cur 在L第一次出现，则返回它的前面一个 pir
Status SqPriorElem(Sqlist L,int cur,int pir){
int i;
int number = 0;
for (i=0;i<L.length;i++){
if (L.elem[i]==cur ){
pir =L.elem[i-1];
break;
}
number++;
}
if(number==0){
printf("当前为第一个元素，没有前驱！\n");
return ERROR;
}
else
printf("%d的前驱元素为：%d\n",cur,pir);
}
//SqSubsequent cur 在L第一次出现，则返回它的后面一个 sub
Status SqSubsequent(Sqlist L,int cur,int sub){
int i;
int number = 0;
for (i=0;i<L.length;i++){
if (L.elem[i]==cur ){
sub =L.elem[i+1];
break;
}
number++;
}
if(number==L.length-1){
printf("当前为最后一个元素，没有后继！\n");
return ERROR;
}else
printf("%d的后继元素为：%d\n",cur,sub);
}
//逆置
//以对称位置，两两互换
Status SqConver(Sqlist &L){
int t;
int i,j;
for(i=0,j=L.length-1;i<=L.length/2&&j>=L.length/2;i++,j--){
t=L.elem[i];
L.elem[i]=L.elem[j];
L.elem[j]=t;
}
}
发表于 2022-6-13 12:50
