首页 > 其他分享 >数据结构学习笔记-day4

数据结构学习笔记-day4

时间:2023-03-13 21:03:41浏览次数:41  
标签:linklist 结点 day4 笔记 next 链表 算法 new 数据结构

Day4

线性表的链式表示和实现:

一、单链表的定义和表示:

   1.单链表需要存储两部分信息,一是本身数据信息,二是下一节点的地址信息,两部分信息构成数据元素的存储映像,它包括数据域和指针域两个域。

 

     链表种类:单链表(线性链表)、循环链表、双向链表、二叉链表、十字链表、邻接表、邻接多重表等

 

代码表示:

      typedef struct LNode{

              elemtype data;

              struct LNode *next;

            }LNode,*linklist;

 

2.首元结点:链表中存储第一个数据元素的结点

  头结点:是在首元结点前附设的一个结点,其指针域指向首元结点,则头指

针指向头结点;

                     头结点的数据域可以不存储任何信息,也可以存储与数据元素类型相同的其他附加信息。

          

      二、单链表的基本操作

            1.初始化

              算法描述:

                     Status initlist(linklist &L){

                             L=new lnode;

                             L->next=NULL;

                             Return OK;

                             }

         

2.取值

  算法描述:

         Status getelem(linklist *L,int I,elemtype &e){

                   P=L->next;j=1;

                   While(p&&j<i){

                       P=p->next;

                       ++j;}

                   If(!p||j>i) return ERROR;

                   e=p->data;

                   return OK;

                   }

 

  算法分析:ASL=(n-1)/2

            T(n)=O(n)

 

3.查找  

算法描述:

       Lnode *locateelem(linklist L,elemtype e){

                P=L->next;

                While(!p&&p->date!=e)

                      P=p->next;

                Return p;

                }

算法分析:类似于查找。

  

             4.插入

                 算法描述:

                       Status listinsert(linklist &L,int I, elemtype e){

                                P=L;j=0;

                                While(p&&(j<i-1)){

                                     P=p->next;

                                     j++}

                                if(!p||j>i+1) return ERROR;

                                 s=new lnode;

s->data=e;

                                 s->next=p->next;

                                 p->next=s;

                                 retuen OK;

                                 }

 

   算法分析:类似于查找。

 

              5.删除

                   算法描述:

                        Status listdelete(linklist &L,int i){

                                  P=L;j=0;

                                  While(p->next&&(j<i-1)){

                                        p=p->next;

                                        j++;}

                                  if(!p->next||j>i-1) return ERROR;

                                  q=p->next;

                                  p->next=q->next;

                                  delete q;

                                  return OK;

                                  }

    算法分析:类似于查找。

 

               6.创建单链表

                     前插法:

                          Void createlist_H(linklisr &L,int n){

                                    L=new londe;

                                    L->next=NULL;

                                    For(i=0;i<n;i++){

                                         P=new lnode;

                                         Cin>>p->data;

                                         p->next=L->next;;

                                         L->next=p}

                                    }

                   

                     后插法:

                           Void creatlist_r(linklist &L,int n){

                                    L=new lonode;

                                    L->next=NULL;

                                    R=L;

                                    For(i=0;i<n;i++){

                                       P=new lnode;

                                       Cin>>p->data;

                                       p->next=NULL;r->next=p;

                                       r=p;}

                                       }

 

三、循环链表:最后一个结点的指针域指向头结点。

标签:linklist,结点,day4,笔记,next,链表,算法,new,数据结构
From: https://www.cnblogs.com/k4fk4-shaw/p/17212842.html

相关文章