写点什么

数据结构与算法 之线性表

作者:喜羊羊
  • 2022 年 9 月 14 日
    河南
  • 本文字数:2034 字

    阅读完需:约 7 分钟

数据结构与算法 之线性表

线性表线性表(Linear List)是由有限个相同类型的数据元素组成的有序序列,一般记作(a,,a2,…….an)


特点:除了 a1 和 an 之外,任意元素 ai 都有一个直接前趋 ai-1 和一个直接后继 ai+1;


a1 无前趋 an 无后继


线性表的基本操作


采用顺序存储结构的称为顺序表 采用链式存储结构的称为线性链表


顺序表顺序表的特点:以物理位置相邻表示逻辑关系


顺序表的优点:任一元素均可随机存取。


顺序表的缺点:进行插入和删除操作时,需移动大量的元素。存储空间不灵活


Status Listlnsert_Sq(SqList &L,int i,ElemType e){if(i<1 || i>L.length+1) return ERROR;//i 值不合法 if(L.length==MAXSIZE)return ERROR;//当前存储空间已满 for(j=L.length-1;j>=i-1;j--)L.elem[j+1]=L.elem[j];//插入位置及之后的元素后移


    L.elem[i-1]=e;//将新元素e放入第i个位置
L.length++;//表长增1
return OK;
复制代码


}空表如何表示空表?


1.无头结点时,头指针为空时表示空表;


2.有头结点时,当头结点的指针域为空时表示空表


下面用几个图形象的表示一下空表和非空表


单链表单链表:每个结点只有一个指针域


双链表双链表:每个结点有两个指针域


循环链表循环链表:链表结点首尾相接


销毁单链表链表销毁后不存在


从头指针开始,依次释放所有结点


像这样


销毁单链表 L


Status DestroyList_L(LinkList &L){//销毁单链表 LLnode *p;//或 LinkList p;while(L){p=L;L=L->next;delete p;}清空单链表链表仍存在,但链表中无元素,成为空链表(头指针和头结点仍然在);


依次释放所有结点,并将头结点指针域设置为空


清空链表 L:Status ClearList(LinkList & L){//将 L 重置为空表


Lnode *p,*q;//或LinkList p,q;p=L->next;while(p){//没到表尾
q=p->next;delete p;p=q;
复制代码


}L->next=NULL;//头结点指针域为空


return OK;
复制代码


}


求单链表的表长 int ListLength_L(LinkList L){LinkList p;p=L->next;i=0;while(p){i++;p=p->next;}return i;}取第 i 个元素值 Status GetElem_L(LinkList L,int i,ElemType &e){p=L->next; //初始化 j=1; //初始化 while(p&&j<i){ //向后扫描,直到 p 指向第 i 个元素或 p 为空 p=p->next;j++;}if(!p\j>i) return ERROR; //第 i 个元素不存在 e=p->data; //取第 i 个元素 return OK;}//GetElem_L 按值查找


1.从第一个结点起,依次和 e 相比较。2.如果找到一个其值与 e 相等的数据元素,则返回其在链表中的位置”)或地址;3.如果查遍整个链表都没有找到其值和 e 相等的元素,则返回 0 或"NULL”


算法描述】Lnode *LocateELem_L (LinkList L, Elemtype e){//在线性表 L 中查找值为 e 的数据元素//找到,则返回 L 中值为 e 的数据元素的地址,查找失败返回 NULLp=L->next;while(p &&p->data!=e)p=p->next;return p;}按值查找 根据指定数据获取该数据位置序号


//在线性表 L 中查找值为 e 的数据元素的位置序号 int LocateELem_L (LinkList L,Elemtype e) {//返回 L 中值为 e 的数据元素的位置序号,查找失败返回 0p=L->next;j=1;while(p &&p->data!=e){p=p->next;j++;}if(p)return j;elsereturn 0;}


插入节点


不可以先执行 2,后执行 1,否则会丢失 ai 的地址


//在 L 中第 i 个元素之前插入数据元素 eStatus Listlnsert_L(LinkList &L,int i,ElemType e){p=L;j=o;while(p && j<i-1){p=p->next;++j;}//寻找第 i-1 个结点,p 指向 i-1 结点 if(!p llj>i-1)return ERROR;//i 大于表长+1 或者小于 1,插入位置非法 s=new LNode;s->data=e;//生成新结点 s,将结点 s 的数据域置为 es->next=p->next;//将结点 s 插入 L 中 p->next=s;return OK;}//ListInsert_L


删除节点


//将线性表 L 中第 i 个数据元素删除 Status ListDelete_L(LinkList &L,int i,ElemType &e){p=L;j=O;while(p->next &&j<i-1){ p=p->next;++j; }//寻找第 i 个结点,并令 p 指向其前驱


if(!(p->next)|lj>i-1)     return ERROR;//删除位置不合理q=p->next;//临时保存被删结点的地址以备释放
p->next=q->next;//改变删除结点前驱结点的指针域
e=q->data;//保存删除结点的数据域
delete q;//释放删除结点的空间
return OK;
复制代码


}//ListDelete_L


查找插入删除分析 2.5.2 单链表基本操作的实现单链表的查找、插入、删除算法时间效率分析


1.查找:因线性链表只能顺序存取,即在查找时要从头指针找起,查找的时间复杂度为 O(n)。


2.插入和删除:因线性链表不需要移动元素,只要修改指针,一般情况下时间复杂度为 O(1)。


头插法建立链表


void CreateList_H(LinkList &L,int n){L=new LNode;L->next=NULL;//先建立一个带头结点的单链表 for(i=n;i>O;--i){p=new LNode;//生成新结点 p=(LNode*)malloc(sizeof(LNode));cin> >p->data;//辅入元素值 scanf(&p-> data);p->next=L->next;//插入到表头


        L->next=p;}
复制代码


}//CreateList H//算法的时间复杂度是:0(n)尾插法建立链表


//正位序输入 n 个元素的值,建立带表头结点的单链表 Lvoid CreateList_R(LinkList &L, int n){L=new LNode;L->next=NULL;r=L;//尾指针 r 指向头结点 for(i=o;i<n;++i){p=new LNode;cin> >p->data;//生成新结点,输入元素值 p->next=NULL;r->next=p;//插入到表尾


    r=p;//r指向新的尾结点
复制代码


}结语一起加油哦~

发布于: 刚刚阅读数: 4
用户头像

喜羊羊

关注

还未添加个人签名 2022.09.01 加入

还未添加个人简介

评论

发布
暂无评论
数据结构与算法 之线性表_9月月更_喜羊羊_InfoQ写作社区