数据结构C语言版线性表的动态分配顺序存储结构表示和实现文库Word文档下载推荐.docx
- 文档编号:7810023
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:33
- 大小:22.19KB
数据结构C语言版线性表的动态分配顺序存储结构表示和实现文库Word文档下载推荐.docx
《数据结构C语言版线性表的动态分配顺序存储结构表示和实现文库Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《数据结构C语言版线性表的动态分配顺序存储结构表示和实现文库Word文档下载推荐.docx(33页珍藏版)》请在冰点文库上搜索。
return1;
}
//销毁顺序线性表L即将顺序表结构体中的所有成员销毁(空间释放,
//数值置0)。
intDestroyList(SqList*L)
//先释放空间,然后置空
free((*L).elem);
(*L).elem=NULL;
(*L).listsize=0;
//将L重置为空表(当前长度为0即是空表)。
intClearList(SqList*L)
{
若L为空表,则返回1,否则返回0。
如何判断是否为空表呢?
结构体中已经包含一个可以说明的元素,
那就是length,表示当前顺序表的长度,根据当前的长度就可以
判断了,为0就是空表,不为0就不是空表了。
intListEmpty(SqListL)
{
if(0==L.length)
return1;
else
return0;
//返回L中数据元素个数。
intListLength(SqListL)
//L.length刚好记录了当前顺序表的长度,直接返回
returnL.length;
//用e返回L中第i个数据元素的值,第i个数据元素就是L.elem[i-1]。
intGetElem(SqListL,inti,ElemType*e)
//首先进行异常处理
if(i<
1||i>
L.length)
/*
注意顺序表基址L.elem[0]表示第一个数,而第i个数则是用
基址L.elem+i-1来表示,也可以用L.elem[i-1]表示。
为什么
可以那样表示呢?
因为l.elem是基地址,相当于数组头一样,指
示了一个首地址,然后对地址进行加减,形成不同元素的地址。
*是取地址所指的内容,所以*(L.elem+i-1)就是第i个数据的值了。
*/
*e=*(L.elem+i-1);
//*e=L.elem[i-1];
/*算法2.6,P26
返回L中第1个与e满足关系compare()的数据元素的位序。
若这样的数据元素不存在,则返回值为0。
intLocateElem(SqListL,ElemTypee,
int(*compare)(ElemType,ElemType))
ElemType*p;
inti=1;
//i的初值为第1个元素的位序
p=L.elem;
//p的初值为第1个元素的存储位置即地址
//循环比较,直到找到符合关系的元素
while(i<
=L.length&
&
!
compare(*p++,e))
++i;
=L.length)
returni;
#if0
/*算法2.7与算法2.2区别
已知顺序线性表La和Lb的元素按值非递减排列。
归并La和Lb得到新的顺序
线性表Lc,Lc的元素也按值非递减排列。
算法的时间复杂度为O(La.length+Lb.length).
voidMergeList(SqListLa,SqListLb,SqList*Lc)
ElemType*pa,*pa_last,*pb,*pb_last,*pc;
pa=La.elem;
//pa指向线性表La的头结点
pb=Lb.elem;
//pb指向线性表Lb的头结点
/*不用InitList()创建空表Lc*/
(*Lc).listsize=(*Lc).length=La.length+Lb.length;
//pc指向线性表Lc的头结点
pc=(*Lc).elem=
(ElemType*)malloc((*Lc).listsize*sizeof(ElemType));
(*Lc).elem)/*存储分配失败*/
pa_last=La.elem+La.length-1;
//pa_last指向线性表La的尾结点
pb_last=Lb.elem+Lb.length-1;
//pb_last指向线性表Lb的尾结点
while(pa<
=pa_last&
pb<
=pb_last)/*表La和表Lb均非空*/
{/*归并*/
if(*pa<
=*pb)//*pa更小接到pc后
*pc++=*pa++;
else//*pb更小接到pc后
*pc++=*pb++;
}
=pa_last)/*表La非空且表Lb空*/
*pc++=*pa++;
/*插入La的剩余元素*/
while(pb<
=pb_last)/*表Lb非空且表La空*/
*pc++=*pb++;
/*插入Lb的剩余元素*/
#endif
//若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,否
//则返回0。
intPriorElem(SqListL,ElemTypecur_e,ElemType*pre_e)
inti=2;
//因为第一个数据元素无前继,从第二个数据元素开始
ElemType*p=L.elem+1;
//找到该cur_e对应的元素并赋给p
*p!
=cur_e)
{
p++;
i++;
if(i>
/*
将该cur_e的前驱赋给*pre_e.
对等式说明下:
*和--是同优先级的,且它们的结合性是自右
向左的,所以先p自减1,p指向其前驱,然后将p所指向的地址
的内容赋给*pre_e。
从这里要明白为什么用指针进行传值,我
给你一个地址,你把内容放进去,然后我就知道其中的值了。
这就是使用指针的用处。
*/
*pre_e=*--p;
若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继,否
则返回0
intNextElem(SqListL,ElemTypecur_e,ElemType*next_e)
ElemType*p=L.elem;
L.length&
if(i==L.length)
对这个等式说明下:
*和--是同优先级的,且它们的结合性
是自右向左的,所以先p自加1,然后将p所指向的地址的内容
赋给*next_e
*next_e=*++p;
//算法2.4P24
//在L中第i个位置之前插入新的数据元素e,L的长度加1.
intListInsert(SqList*L,inti,ElemTypee)
ElemType*newbase,*q,*p;
//输入的i不合法
(*L).length+1)
//当前存储空间已满,增加分配
if((*L).length>
=(*L).listsize)
//realloc改变(*L).elem所指内存的大小,原始所指内存中的
//数据不变。
newbase=(ElemType*)realloc((*L).elem,
((*L).listsize+LISTINCREMENT)*sizeof(ElemType));
if(!
newbase)
exit(0);
(*L).elem=newbase;
//新基址
(*L).listsize+=LISTINCREMENT;
//增加存储容量
//指定插入的位置
q=(*L).elem+i-1;
//q之后的元素右移一步,以腾出位置
for(p=(*L).elem+(*L).length-1;
p>
=q;
--p)
*(p+1)=*p;
*q=e;
//插入e
++(*L).length;
//表长增1
/*算法2.5P25
删除L的第i个数据元素,并用e返回其值,L的长度减1.
intListDelete(SqList*L,inti,ElemType*e)
ElemType*p,*q;
//i值不合法
if(i<
(*L).length)
p=(*L).elem+i-1;
//p为被删除元素的位置
*e=*p;
//被删除元素的值赋给e
q=(*L).elem+(*L).length-1;
//表尾元素的位置
for(++p;
p<
++p)//被删除元素之后的元素左移
*(p-1)=*p;
(*L).length--;
//表长减1
//依次对L的每个数据元素调用函数vi()。
intListTraverse(SqListL,void(*vi)(ElemType*))
inti;
//对顺序表中的每一元素调用函数vi()
for(i=1;
i<
=L.length;
i++)
vi(p++);
printf("
\n"
);
//判断两元素的值是否相等的函数,Union()用到,相等返回1,不相等返回0
intequal(ElemTypec1,ElemTypec2)
if(c1==c2)
/*算法2.1P20
将所有在线性表Lb中但不在La中的数据元素插入到La中。
voidUnion(SqList*La,SqListLb)
ElemTypee;
intLa_len,Lb_len;
La_len=ListLength(*La);
Lb_len=ListLength(Lb);
//依次对Lb中的元素与La的所有元素进行比较
=Lb_len;
//取Lb中第i个数据元素赋给e
GetElem(Lb,i,&
e);
//La中不存在和e相同的元素,则插入之
LocateElem(*La,e,equal))
ListInsert(La,++La_len,e);
算法2.2。
P21
已知线性表La和Lb中的数据元素按值非递减排列。
归并La和Lb得到新
的线性表Lc,Lc的数据元素也按值非递减排列。
voidMergeList(SqListLa,SqListLb,SqList*Lc)
inti=1,j=1,k=0;
ElemTypeai,bj;
InitList(Lc);
//创建空表Lc
La_len=ListLength(La);
=La_len&
j<
=Lb_len)//表La和表Lb均非空
GetElem(La,i,&
ai);
GetElem(Lb,j,&
bj);
if(ai<
=bj)//ai更小将ai插入Lc中
{
ListInsert(Lc,++k,ai);
++i;
}
else//bj更小将bj插入Lc中
ListInsert(Lc,++k,bj);
++j;
//表La非空且表Lb空则将La的剩余部分接到Lc中
=La_len)
GetElem(La,i++,&
ListInsert(Lc,++k,ai);
//表Lb非空且表La空则将Lb的剩余部分接到Lc中
while(j<
=Lb_len)
GetElem(Lb,j++,&
ListInsert(Lc,++k,bj);
//在L中按非降序插入新的数据元素e,L的长度加1.
voidInsertAscend(SqList*L,ElemTypee)
ElemType*newbase,*p;
intk;
//k为e要插入的位置
=(*L).listsize)//当前存储空间已满,增加分配
p=(*L).elem;
//中介,做对比用的。
for(k=1;
k<
=(*L).length;
k++)
if(e>
*p)
p++;
else
break;
ListInsert(L,k,e);
//在L中按非升序插入新的数据元素e,L的长度加1。
voidInsertDescend(SqList*L,ElemTypee)
//k为e要插入的位置
if((*L).length>
newbase=(ElemType*)realloc((*L).elem,
if(e<
//在L的头部插入新的数据元素e,L的长度加1。
intHeadInsert(SqList*L,ElemTypee)
ElemType*p,*q,*newbase;
=(*L).listsize)
q=(*L).elem;
//从表头至表尾的元素依次向后移动一位
for(p=(*L).elem+(*L).length-1;
--p)
(*L).length++;
//长度加1
//在L的尾部插入新的数据元素e,L的长度加1。
intEndInsert(SqList*L,ElemTypee)
ElemType*q,*newbase;
if(!
newbase)
q=(*L).elem+(*L).length;
//q为插入位置
//删除L的第一个数据元素,并由e返回其值,L的长度减1。
intDeleteFirst(SqList*L,ElemType*e)
ElemType*p,*q;
if(ListEmpty(*L))//空表无法删除
//p指向第一个元素
q=(*L).elem+(*L).length-1;
//q指向最后一个元素
++p)
//从第2个元素起,所有元素向前移动一个位置
//当前长度减1
//删除L的最后一个数据元素,并用e返回其值,L的长度减1。
intDeleteTail(SqList*L,ElemType*e)
(*L).length)//空表
p=(*L).elem+(*L).length-1;
//最后一个数据元素的位置
//被删除元素的值赋给e
//表长减1
//删除表中值为e的元素,并返回1;
如无此元素,则返回0
intDeleteElem(SqList*L,ElemTypee)
inti=0,//记录与e值相同的元素的位置
j;
//先判断i的位置是否越界,然后将e与顺序表的每一个元素相比较,
//直到找到
(*L).length&
e!
=*((*L).elem+i))
if(i==(*L).length)//没找到
//后面的元素依次前移
for(j=i;
(*L).length;
j++)
*((*L).elem+j)=*((*L).elem+j+1);
(*L).length--;
//用e取代表L中第i个元素的值。
intReplaceElem(SqListL,inti,ElemTypee)
L.length)//i值不合法
*(L.elem+i-1)=e;
//替换为e
//按非降序建立n个元素的线性表。
intCreatAscend(SqList*L,intn)
inti,
//记录数据要插入的位置
InitList(L);
请输入%d个元素:
(空格)\n"
n);
scanf("
%d"
&
ListInsert(L,1,e);
//在空表中插入第1个元素
n;
scanf("
&
//将待插入的数据与顺序表的每一个元素比较
//比期中一个小的话则退出循环
for(j
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 语言版 线性 动态分配 顺序 存储 结构 表示 实现 文库