数据结构 P22-24 算法实现线性表的插入与删除

95 阅读 0 评论 63 点赞

我是靠谱客的博主友好水杯，最近开发中收集的这篇文章主要介绍数据结构 P22-24 算法实现线性表的插入与删除，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

/*线性表的插入*/

#include <iostream>

using namespace std;

#define LIST_INIT_SIZE 100 //线性表的初始分配量
#define LISTINCREMENT 10 //线性表分配空间的增量

struct SqList //定义线性表结构体
{
int *elem; //存储空间基址
int length; //当前长度
int listsize; //当前分配的容量
};

int main()
{
struct SqList InitList_Sq = //初始化结构
{
InitList_Sq.elem=new int [LIST_INIT_SIZE], //动态分配内存
InitList_Sq.length=0, //空表长度为0
InitList_Sq.listsize=LIST_INIT_SIZE //初始存储容量
};

int e,i; //定义插入的元素为 e，插入的位置为 i

for(i=0;i<InitList_Sq.length;++i) //输出线性表里的初始元素
{
cout<<InitList_Sq.elem[i]<<" "<<endl;
}
if(InitList_Sq.length==0) //若线性表为空则输出 No Elem in it
cout<<"No Elem in it"<<endl;

while(1) //线性表插入元素的循环
{
cout<<"what are you want to insertion: ";
cin>>e; //输入你要插入的元素
cout<<endl<<"where are you want to insertion: ";
cin>>i; //输入你要插入的位置

if(i<1||i>InitList_Sq.length+1) //判断插入的位置是否合理
return 0;
/* if(InitList_Sq.length>=InitList_Sq.listsize) //判断线性表的长度是否大于当前的分配存储容量
{
InitList_Sq.elem=new int [InitList_Sq.elem,InitList_Sq.listsize+LISTINCREMENT]; //若长度大于容量，说明当前存储空间已满，增加分配内存
InitList_Sq.listsize += LISTINCREMENT; //将存储容量的值改为重新分配后的值
}*/
int *q,*p; //定义两个指针
q=&(InitList_Sq.elem[i-1]); //q指向插入的地址
p=&InitList_Sq.elem[InitList_Sq.length-1]; //p指向线性表的末尾
for(;p>=q;--p) //将插入的地址之后的元素右移
*(p+1)=*p;
*q=e; //将e的值赋给*q，插入线性表
++InitList_Sq.length; //表长参量增1

for(i=0;i<InitList_Sq.length;++i) //输出线性表的所有元素
{
cout<<InitList_Sq.elem[i]<<" ";
}
cout<<endl;
}
delete [] InitList_Sq.elem; //释放内存
delete [] InitList_Sq.elem;

return 0;

}

/* 线性表的删除 */

#include <iostream>

using namespace std;

#define LIST_INIT_SIZE 100 //线性表的初始分配量

struct SqList //定义线性表结构体
{
int *elem; //存储空间基址
int length; //当前长度
int listsize; //当前分配的容量
};

int main()
{
struct SqList InitList_Sq = //初始化结构
{
InitList_Sq.elem=new int [LIST_INIT_SIZE], //动态分配内存
InitList_Sq.length=3, //表长度为3
InitList_Sq.listsize=LIST_INIT_SIZE //初始存储容量
};

InitList_Sq.elem[0]=1;
InitList_Sq.elem[1]=2; //初始元素
InitList_Sq.elem[2]=3;

int e,i; //定义插入的元素为 e，插入的位置为 i

for(i=0;i<InitList_Sq.length;++i) //输出线性表里的初始元素
{
cout<<InitList_Sq.elem[i]<<" "<<endl;
}
if(InitList_Sq.length==0) //若线性表为空则输出 No Elem in it
cout<<"No Elem in it"<<endl;

while(1) //线性表删除元素的循环
{
cout<<endl<<"where are you want to delete: ";
cin>>i; //输入你要删除的位置

if(i<1||i>InitList_Sq.length) //判断删除的位置是否合理
return 0;

int *q,*p; //定义两个指针
q=&(InitList_Sq.elem[i-1]); //q指向删除的地址
p=&(InitList_Sq.elem[InitList_Sq.length-1]); //p指向线性表的末尾
for(++q;p>=q;--p) //将删除的地址之后的元素左移
*(p-1)=*p;

--InitList_Sq.length; //表长参量减1

for(i=0;i<InitList_Sq.length;++i) //输出线性表的剩余元素
{
cout<<InitList_Sq.elem[i]<<" ";
}
cout<<endl;
}
delete [] InitList_Sq.elem; //释放内存

return 0;
}

/*综合程序*/

#include <iostream>

using namespace std;

#define LIST_INIT_SIZE 100 //线性表的初始分配量
#define LISTINCREMENT 10 //线性表分配空间的增量

struct SqList //定义线性表结构体
{
int *elem; //存储空间基址
int length; //当前长度
int listsize; //当前分配的容量
};

int main()
{
struct SqList InitList_Sq = //初始化结构
{
InitList_Sq.elem=new int [LIST_INIT_SIZE], //动态分配内存
InitList_Sq.length=0, //空表长度为0
InitList_Sq.listsize=LIST_INIT_SIZE //初始存储容量
};

int e,i,key; //定义插入的元素为 e，插入的位置为 i
int *q,*p; //定义两个指针

for(i=0;i<InitList_Sq.length;++i) //输入线性表里的初始元素
{
cout<<InitList_Sq.elem[i]<<" "<<endl;
}
if(InitList_Sq.length==0) //若线性表为空则输出 No Elem in it
cout<<"No Elem in it"<<endl;

while(1)
{
cout<<"insertion or delete? 1 or 0 ? : "; //选择插入或删除
cin>>key;

if(key==1)
{
cout<<"what are you want to insertion: ";
cin>>e; //输入你要插入的元素
cout<<"where are you want to insertion: ";
cin>>i; //输入你要插入的位置

if(i<1||i>InitList_Sq.length+1) //判断插入的位置是否合理
continue;
if(InitList_Sq.length>=InitList_Sq.listsize) //判断线性表的长度是否大于当前的分配存储容量
{
InitList_Sq.elem=new int [InitList_Sq.elem,InitList_Sq.listsize+LISTINCREMENT]; //若长度大于容量，说明当前存储空间已满，重新分配内存
InitList_Sq.listsize += LISTINCREMENT; //将存储容量的值改为重新分配后的值
}
q=&(InitList_Sq.elem[i-1]); //q指向插入的地址
p=&InitList_Sq.elem[InitList_Sq.length-1]; //p指向线性表的末尾
for(;p>=q;--p) //将插入的地址之后的元素右移
*(p+1)=*p;
*q=e; //将e的值赋给*q，插入线性表
++InitList_Sq.length; //表长参量增1

}

else if(key==0)
{
if(InitList_Sq.length==0)
{cout<<"线性表内无元素可删除，请先输入"<<endl;
continue;}

cout<<"where are you want to insertion: ";
cin>>i; //输入你要删除的位置

if(i<1||i>InitList_Sq.length) //判断删除的位置是否存在
continue;

p=&InitList_Sq.elem[i-1]; //p指向要删除的位置
q=&InitList_Sq.elem[InitList_Sq.length-1]; //q指向表尾位置
for(++p;p<=q;--q)
*(p-1)=*p;
--InitList_Sq.length; //表长参量减1
}

else continue;

for(i=0;i<InitList_Sq.length;++i) //输出线性表的所有元素
{
cout<<InitList_Sq.elem[i]<<" ";
}
cout<<endl;
}

delete [] InitList_Sq.elem; //释放内存
delete [] InitList_Sq.elem;

return 0;
}