线性表之顺序表.docx
《线性表之顺序表.docx》由会员分享，可在线阅读，更多相关《线性表之顺序表.docx（38页珍藏版）》请在冰点文库上搜索。
线性表之顺序表
线性表之顺序表
采用顺序存储结构的线性表叫做顺序表！
线性表的顺序存储结构：
用一组地址连续的存储单元依次存储线性表的各个数据元素！
特点：
逻辑上相邻的数据元素，其物理位置也相邻！
通过数据元素物理存储上的相邻关系来反映数据元素之间逻辑上的相邻关系！
假设顺序表中有n个元素，每个元素占k个单元，第一个元素的存储地址为Loc（a1）,称为基地址，则第i个元素ai的存储地址为：
Loc（ai）=Loc（a1）+（i-1）*k
1）.可以这样定义顺序表（数组）：
#defineMaxSize1000//线性表可能达到的最大长度
ElemTyedata[MaxSize];//ElemType的类型可根据实际情况而定
intlength;//线性表的实际长度
2）.也可以这样定义（结构体类型）：
#defineMaxSize1000//线性表可能达到的最大长度
typedefstruct{
ElemTyedata[MaxSize];//ElemType的类型可根据实际情况而定
intlength;//线性表的实际长度
}SeqList;//把data,length作为该结构体的成员项，使其成为一个整体！
-----------------------------------------------------------------------------------------------------------------------
顺序表上基本运算的实现：
-----------------------------------------------------------------------------------------------------------------------
一，数据元素的插入：
编程实现：
顺序表的插入元素操作：
在顺序表L中第i个数据元素之前插入一个元素x
样例输入：
7302160251796277-1
275
样例输出：
7302160251796277
730216027251796277
//不用下标为0的空间，下标从1开始，使得表中元素位置一致！
//此时就是造成了存储空间的浪费！
#include
#defineMaxSize100
#defineElemTypeint
typedefstruct{
ElemTypedata[MaxSize];
intlength;
}SeqList;
voidinit（SeqList*L）
{
intx,i=1,k=0;
scanf（"%d",&x）;
while（x!
=-1）{
L->data[i++]=x;
L->length=++k;
scanf（"%d",&x）;
}
}
/*
把参数设计成指向线性表的指针后，在调用时传给形参的就是
指向线性表的指针即线性表的地址，再被调函数中，可以通过
这个地址直接对地址中存储的线性表的各项的值进行修改。
在主调函数中访问线性表时仍然对相同的地址空间进行访问，
当然这样的修改就可以反映到主调函数中了！
*/
voidinsert（SeqList*L,ElemTypex,inti）
{//在顺序表L中第i个数据元素之前插入一个元素x
intk;
if（（i<1）||（i>L->length+1））{
printf（"PositionError!
\n"）;//非法位置
return;
}
if（L->length>=MaxSize）{
printf（"Overflow!
\n"）;//表空间溢出
return;
}
for（k=L->length;k>=i;k--）//为插入元素，向后移动元素
L->data[k+1]=L->data[k];///注意区别
L->data[i]=x;///
L->length++;//表长加1
}
intmain（）
{
SeqListL;
init（&L）;//初始化
inty,i;
for（intj=1;j<=L.length;j++）
printf（"%d",L.data[j]）;
printf（"\n"）;
scanf（"%d%d",&y,&i）;
insert（&L,y,i）;
for（intj=1;j<=L.length;j++）
printf（"%d",L.data[j]）;
printf（"\n"）;
return0;
}
//下标从0开始,
由于表中元素位置比相应数组下标大1，处理的很不自然！
*/
#include
#defineMaxSize100
#defineElemTypeint
typedefstruct{
ElemTypedata[MaxSize];
intlength;
}SeqList;
voidinit（SeqList*L）
{
intx,i=0;
scanf（"%d",&x）;
while（x!
=-1）{
L->data[i++]=x;
L->length=i;
scanf（"%d",&x）;
}
}
voidinsert（SeqList*L,ElemTypex,inti）
{//在顺序表L中第i个数据元素之前插入一个元素x
intk;
if（（i<1）||（i>L->length+1））
printf（"PositionError!
\n"）;
if（L->length>=MaxSize）
printf（"Overflow!
\n"）;
for（k=L->length-1;k>=i-1;k--）//为插入元素，向后移动元素
L->data[k+1]=L->data[k];///注意区别
L->data[i-1]=x;///
L->length++;//表长加1
}
intmain（）
{
SeqListL;
init（&L）;//初始化
inty,i;
for（intj=0;jprintf（"%d",L.data[j]）;
printf（"\n"）;
scanf（"%d%d",&y,&i）;
insert（&L,y,i）;
for（intj=0;jprintf（"%d",L.data[j]）;
printf（"\n"）;
return0;
}
以上是两套代码：
区别就是在于第一个代码是下标从1开始的，第二个代码下标从0开始！
其他无差别！
---------------------------------------------------------------------------------------------------------------------------
二，数据元素的删除：
编程实现：
顺序表中删除元素的过程：
在顺序表中删除第i个数据元素
样例输入：
730216027251796277-1
6
样例输出：
730216027251796277
7302160271796277
///不用下标为0的空间，下标从1开始，使得表中元素位置一致！
//此时就是造成了存储空间的浪费！
#include
typedefstruct{
intdata[100];
intlength;
}SeqList;
voidinit（SeqList*L）
{
intx,i=1,k=0;
scanf（"%d",&x）;
while（x!
=-1）{
L->data[i++]=x;
L->length=++k;
scanf（"%d",&x）;
}
}
voidDeleList（SeqList*L,inti）
{//在顺序表L中删除第i个数据元素
intk;
if（（i<1）||（i>L->length））{
printf（"PositionError!
\n"）;
return;
}
for（k=i;k<=L->length;k++）
L->data[k]=L->data[k+1];///元素前移，注意区别
L->length--;//表长减1
}
voidPrint（SeqListL）{
intfirst=1;
for（inti=1;i<=L.length;i++）
if（first）{
printf（"%d",L.data[i]）;
first=0;
}else{
printf（"%d",L.data[i]）;
}
printf（"\n"）;
}
intmain（）
{
SeqListL;
init（&L）;//初始化
Print（L）;
inti;
scanf（"%d",&i）;
DeleList（&L,i）;
Print（L）;
return0;
}
///下标从0开始,
//由于表中元素位置比相应数组下标大1，处理的很不自然！
#include
typedefstruct{
intdata[100];
intlength;
}SeqList;
voidinit（SeqList*L）
{
intx,i=0;
scanf（"%d",&x）;
while（x!
=-1）{
L->data[i++]=x;
L->length=i;
scanf（"%d",&x）;
}
}
voidDeleList（SeqList*L,inti）
{//在顺序表L中删除第i个数据元素
intk;
if（（i<1）||（i>L->length））{
printf（"PositionError!
\n"）;
return;
}
for（k=i;k<=L->length-1;k++）//
L->data[k-1]=L->data[k];//元素前移，注意区别
L->length--;//表长减1
}
voidPrint（SeqListL）{
intfirst=1;
for（inti=0;iif（first）{
printf（"%d",L.data[i]）;
first=0;
}else{
printf（"%d",L.data[i]）;
}
printf（"\n"）;
}
intmain（）
{
inti;
SeqListL;
init（&L）;//初始化
Print（L）;
scanf（"%d",&i）;
DeleList（&L,i）;
Print（L）;
return0;
}
以上是两套代码：
区别就是在于第一个代码是下标从1开始的，第二个代码下标从0开始！
其他无差别！
---------------------------------------------------------------------------------------------------------------------------
三，数据元素的查找：
编程实现：
顺序表中数据元素的查找过程：
在顺序表中查找值为x的数据元素。
算法思想：
将顺序表中的数据元素依次与x比较，若某次比较相等，则返回数据元素的下标，运算结束；
否则继续比较！
若均不相等，则说明在该顺序表中不存在值为x的数据元素，返回-1.
样例输入：
730216027251796277-1
25
样例输出：
730216027251796277
7302160271796277
----------------------------------------------------------------
实现了查找到元素并删除的目的！
----------------------------------------------------------------
///不用下标为0的空间，下标从1开始，使得表中元素位置一致！
///此时就是造成了存储空间的浪费！
#include
#defineMaxSize100
typedefstruct{
intdata[MaxSize];
intlength;
}SeqList;
voidinit（SeqList*L）
{
intx,i=0;
scanf（"%d",&x）;
while（x!
=-1）{
L->data[++i]=x;
L->length=i;
scanf（"%d",&x）;
}
}
intLocate（SeqListL,intx）{
for（inti=1;i<=L.length;i++）
if（L.data[i]==x）
returni;
return-1;
}
voidDeleList（SeqList*L,inti）
{//在顺序表L中删除第i个数据元素
intk;
if（（i<1）||（i>L->length））{
printf（"PositionError!
\n"）;
return;
}
for（k=i;k<=L->length;k++）//
L->data[k]=L->data[k+1];//
L->length--;
}
voidPrint（SeqListL）{
intfirst=1;
for（inti=1;i<=L.length;i++）
if（first）{
printf（"%d",L.data[i]）;
first=0;
}else{
printf（"%d",L.data[i]）;
}
printf（"\n"）;
}
intmain（）{
SeqListL;
init（&L）;//初始化
Print（L）;
intx,i;
scanf（"%d",&x）;
i=Locate（L,x）;
if（i==-1）
printf（"%d\n",i）;
else
DeleList（&L,i）;///找到即删除
Print（L）;
return0;
}
/*
下标从0开始,
由于表中元素位置比相应数组下标大1，处理的很不自然！
*/
#include
#defineMaxSize100
typedefstruct{
intdata[MaxSize];
intlength;
}SeqList;
voidinit（SeqList*L）
{
intx,i=0;
scanf（"%d",&x）;
while（x!
=-1）{
L->data[i++]=x;
L->length=i;
scanf（"%d",&x）;
}
}
intLocate（SeqListL,intx）{
for（inti=0;iif（L.data[i]==x）
returni;
return-1;
}
voidDeleList（SeqList*L,inti）{//在顺序表L中删除第i个数据元素
intk;
if（（i<1）||（i>L->length））{
printf（"PositionError!
\n"）;
return;
}
for（k=i;k<=L->length-1;k++）//-----------
L->data[k-1]=L->data[k];//--------
L->length--;
}
voidPrint（SeqListL）{
intfirst=1;
for（inti=0;iif（first）{
printf（"%d",L.data[i]）;
first=0;
}else{
printf（"%d",L.data[i]）;
}
printf（"\n"）;
}
intmain（）{
SeqListL;
init（&L）;//初始化----------
Print（L）;
intx,i;
scanf（"%d",&x）;
i=Locate（L,x）;
if（i==-1）//找到即删除------
printf（"%d\n",i）;
else
DeleList（&L,i+1）;
Print（L）;
return0;
}
以上是两套代码：
区别就是在于第一个代码是下标从1开始的，第二个代码下标从0开始！
其他无差别！
---------------------------------------------------------------------------------------------------------------------------
四，对递增有序顺序表的插入：
编程实现：
顺序表L中的元素递增有序，将数据元素x插入到顺序表L的适当位置上，以保持该顺序表的有序性！
算法思想：
先找到适当的位置，然后后移元素空出一个位置，再将x插入，并把顺序表的长度加1！
样例输入：
1223314556586575788991-1
61
样例输出：
1223314556586575788991
122331455658616575788991
不用下标为0的空间，下标从1开始，使得表中元素位置一致！
此时就是造成了存储空间的浪费！
#include
#defineMaxSize100
typedefstruct{
intdata[MaxSize];
intlength;
}SeqList;
voidinit（SeqList*L）{
intx,i=0;
scanf（"%d",&x）;
while（x!
=-1）{
L->data[++i]=x;
L->length=i;
scanf（"%d",&x）;
}
}
voidSLOrderInsert（SeqList*L,intx）{
inti;
if（L->length>=MaxSize）{
printf（"Overflow!
\n"）;
return;
}
//顺序表L中从下标L.length至i+1的数据元素依次后移一个位置
for（i=L->length;i>=1&&xdata[i];i--）////主要在这：
xdata[i]
L->data[i+1]=L->data[i];////
L->data[i+1]=x;////
L->length++;
}
voidPrint（SeqListL）{
intfirst=1;
for（inti=1;i<=L.length;i++）
if（first）{
printf（"%d",L.data[i]）;
first=0;
}else{
printf（"%d",L.data[i]）;
}
printf（"\n"）;
}
intmain（）{
intx;
SeqListL;
init（&L）;
Print（L）;
scanf（"%d",&x）;
SLOrderInsert（&L,x）;
Print（L）;
return0;
}
以上就一套代码，下标从1开始，因为没有什么差别，--，不再赘述！
--------------------------------------------------------------------------------------------------------------------------
五，数据元素为x的删除
编程实现：
把顺序表L中所有值为x的数据元素全部删除！
算法思想：
对顺序表中所有数据元素从头到尾进行扫描，凡是与指定的值x相同的数据元素就删除！
样例输入：
123412561278121254-1
12
样例输出：
123412561278121254
34567854
/*
下标从0开始,
由于表中元素位置比相应数组下标大1，处理的很不自然！
*/
#include
#defineMaxSize100
typedefstruct{
intdata[MaxSize];
intlength;
}SeqList;
voidinit（SeqList*L）{
intx,i=0;
scanf（"%d",&x）;
while（x!
=-1）{
L->data[i++]=x;
L->length=i;
scanf（"%d",&x）;
}
}
voidDeleList（SeqList*L,inti）{//在顺序表L中删除第i个数据元素
intk;
if（（i<1）||（i>L->length））{
//printf（"PositionError!
\n"）;
return;
}
for（k=i;k<=L->length-1;k++）//
L->data[k-1]=L->data[k];//元素前移！
L->length--;
}
voidMdeleteList（SeqList*L,intx）{////调用删除函数来按个删除
inti,j;
for（i=0;ilength;i++）{
if（L->data[i]==x）{////
升级会员 