第二周 数据结构学习

本文由用户“zhabcdef”分享发布 更新时间:2022-01-25 22:39:29 举报文档

以下为《第二周 数据结构学习》的无排版文字预览,完整格式请下载

下载前请仔细阅读文字预览以及下方图片预览。图片预览是什么样的,下载的文档就是什么样的。

数据结构——线性表

线性表的基本操作:

InitList(&L) : 初始化表。构造一个空的线性表。

Length( L ) : 求表长。返回线性表 L 的长度,即 L 中数据元素的个数。

LocateElem( L , e ) : 按值查找操作。在表 L 中 查找具有给定关键字值的元素。

GetElem( L , i ) : 按位查找操作。获取表 L 中第 i 个位置的元素的值

ListInsert( &L , i , e ) :插入操作。在表 L 中的第 i 个位置插入指定元素 e

ListDelete( &L , i , &e) : 删除操作。删除表 L 中第 i 个位置的元素,并用 e 返回删除元素的值。

PrintList( L ) : 输出操作。按前后顺序输出线性表 L 的所有元素的值。

Empty( L ) : 判空操作。若 L 为空表,则返回 true ,否则返回 false 。

DestroyList( &L ) : 销毁操作。销毁线性表,并释放线性表 L 所占用的内存空间。

一.线性表的顺序存储结构,指的是用一段地址连续的存储单元依此存储线性表中的数据元素。

/

typedef struct LNode *List; struct LNode{ ElementType Data[MAXSIZE]; int Last; }; struct LNode L; List PtrL;

【插入功能实现】

检查目标位置是否合法

检查是否有剩余存储空间可供插入

将目标位置处元素及目标位置之后的所有元素后移一个位置

将新元素插入目标位置

线性表长度加1

void Insert(ElementType X,int i,List PtrL)//插入

{

int j;

if(PtrL->Last==MAXSIZE-1){//表空间已满,不能插入

printf("表满");

return;

}

if(iPtrL->Last+2){//检查插入位置的合法性

printf("位置不合法");

return;

}

for(j=PtrL->Last;j>=i-1;j--)

PtrL->Data[j+1]=PtrL->Data[j];//将ai~an倒序向后移动

PtrL->Data[I-1]=X;//新元素插入

PtrL->Last++;//Last仍指向最后元素

return;

} //平均比较次数为n/2,平均时间性能为O(n).

【删除功能实现】

检查目标位置是否合法

将目标位置之后的所有元素前移一个位置

线性表长度减一

void Delete(int i,List PtrL)//删除

{

int j;

if(iPtrL->Last+1) 内容过长,仅展示头部和尾部部分文字预览,全文请查看图片预览。 位某某1开始

p = L->Next;

while(p&&cnt Next;

cnt++;

}

if((cnt==K)&&p) printf("您查找的数为:%d\n",p -> Data);

else printf("您查找数不存在");

}

4.查找(按值查找Find)

按值查找的方法也是从头到尾遍历,直到找到为止

//按值查找

Position Find(List L,int X){

Position p;

p = L->Next;

while(p&&p->Data!=X){

p = p-> Next;

}

if(p) printf("查找成功,您查找的数为:%d\n",p->Data);

else printf("您查找数不存在");

}

5.插入

带头结点的链式表的插入

//插入

List Insert(List L ,ElementType X,int i){

Position tmp,pre;

int cnt =0 ;

pre = L;

while(pre&&cntNext;

cnt++;

}

if(pre==NULL||cnt!=i-1){

printf("插入位置参数错误\n");

}

else{

tmp = (Position)malloc(sizeof(struct LNode));

tmp->Data=X;

tmp->Next=pre->Next;

pre->Next=tmp;

}

}

6.删除

删除指定位序i的元素,首先需要找到被删除结点的前一个元素,然后再删除结点并释放空间。

//删除

bool Delete(List L,int i){

Position tmp,pre;

int cnt = 0;

pre = L;

while(pre&&cntNext;

cnt++;

}

if(pre==NULL||cnt!=i-1||pre->Next==NULL){

printf("删除位置参数错误");

}

else{

tmp = pre->Next;

pre->Next = tmp->Next;

free(tmp);

printf("删除成功");

}

}

7.遍历链表并输出

void DisLinkList(List L)

{

List p = L->Next;

printf("输出链表: ");

while (p)

{

printf("%d ", p->Data);

p = p->Next;

}

}

[文章尾部最后300字内容到此结束,中间部分内容请查看底下的图片预览]

以上为《第二周 数据结构学习》的无排版文字预览,完整格式请下载

下载前请仔细阅读上面文字预览以及下方图片预览。图片预览是什么样的,下载的文档就是什么样的。

图片预览