单链表的基本操作(二)

2019/7/21 17:19:14 人评论 次浏览 分类:学习教程

一、删除:

a b c

要删除单链表中指定位置的元素,同插入元素一样,首先应该找到该位置的前驱结点;在单链表中删除元素b时,应该首先找到其前驱结点a,。为了在单链表中实现元素a、b、和c之间逻辑关系的变化,仅需要结点a中的指针域即可;假设p为指向结点a的指针,则修改指针的语句为:p->next=p->next->next;但在删除结点b时,除了修改结点a的指针域外,还要释放结点b所占的空间,所以在修改指针前,应该引入另外一指针q,临时保存结点b的地址以备释放。

算法步骤:

1、查找结点a并由指针p指向该结点

2、临时保存待删除结点b的地址在q中,以备释放

3、将结点*p的指针域指向b的直接后继结点

4、释放结点b的空间

Status ListDelete(LinkList &L,int i)  {       //在带头结点的单链表L中,删除第i个元素      p=L;      j=0;        while((p->next) &&(j1))     {          p=p->next;          ++j;//查找第i-1个结点,p指向该结点         if(!(p->next) || (j>i-1)) return ERROR;//当i>n或i<1时,删除位置不合理         q=p->next;//临时保存被删除结点的地址以备释放        p->next=q->next;//改变删除结点前驱结点的指针域       delete q;//释放删除结点的空间       return  ok;      }  }

二、创建链表:

链表和顺序表不同,链表它是一种动态结构。整个可用存储空间可为多个链表共同享用,每个链表占用的空间不需要预先分配好,而是由整个系统来按需及时分配;根据结点插入位置的不同,链表的创建方法可分为前插法和后插法;

a、前插法创建单链表:

算法步骤:

1、创建一个只有头结点的空链表

2、根据待创建链表包括的元素个数n,循环n次执行以下操作:

-----生成一个新结点*p

-----输入元素值赋给新结点*p的数据域

-----将新结点*p插入到头结点之后

void CreateList_H(LinkList &L,int n)  {      //逆位输入n个元素的值,建立带表头结点的单链表L     L=new LNode;     L->next=NULL;//先建立一个带头结点的空链表     for(i=0;ii)     {         p=new LNode;//生成新结点*p         cin>>p->data;//输入元素值赋给新结点*p的数据域         p->next=L->next;          L->next=p;//将新结点*p插入到头结点之后      }  }

b、后插法创建单链表:

算法步骤:

1、创建一个只有头结点的空链表

2、尾指针r初始化,指向头结点

3、根据创建链表包括的元素个数n,循环n次执行以下操作:

-----生成一个新结点*p;

-----输入元素值赋给新结点*p的数据域;

----将新结点*p插入到尾结点*r之后

----尾指针r指向新的尾结点*p

void CreateList_R(LinkList &L,int n)  {       //正位序输入n个元素的值,建立带表头结点的单链表L      L=new LNode ;     L->next=NULL;//先建立一个带头结点的空链表    r=L;//尾指针r指向头结点    for(i=0;ii)   {       p=new LNode;//生成新结点       cin>>p-data;//输入元素值赋给新结点*p的数据域       p->next=NULL; r->next=p;//将新结点*p插入尾结点*r之后       r=p;//r指向新的尾结点*p  }  }

相关资讯

    暂无相关的资讯...

共有访客发表了评论 网友评论

验证码: 看不清楚?
    -->