欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构与算法分析之单链表的建立,插入和删除操作。

程序员文章站 2024-03-06 08:44:01
...
  • 序言
    单链表:当一个序列中只含有指向它的后继结点的链接时,就称该链表为单链表。具体形式如下图:
    数据结构与算法分析之单链表的建立,插入和删除操作。
    其中:data称为数据域,next称为指针域。在链表的最开头是头指针head,头指针顾名思义,不含有数据域;尾接点指向NULL的地方。注意,若head==NULL,为空表
    具体代码如下:
    1、定义一个结构体,里面包含单链表的每个接点的数据域和指针域。
    2、要注意指针域的定义方式。因为是指向下一个结点的指针,所以定义为结点类型的指针,名为Next。
    3、最后申明*LinkList, 等同于 *LinkList==Node,定义为指向结构体的指针,名为 *LinkList。代码中是省略版,全称可以写成:typedef struct Node *LinkedList;
typedef struct Node
{
    int data;
    struct Node* Next;//指向结点类型的指针
}Node ,*LinkList;
  • 单链表的建立操作
    单链表的建立操作可以分成两种,一种是头插法,一种是尾插法。下面会分别进行讲解:
    头插法:就是讲新增结点插入第一个结点之前的位置,示意图如下:
    数据结构与算法分析之单链表的建立,插入和删除操作。
    解析:
    1、头插法建立单链表,首先需要建立一个媒介指针s,s用于传递新的结点插入链表的正确位置。
    2、因为是创建单链表,而且链表的每个指针里面需要存放数据,因此需要先申请内存空间。申请方式如下:
    *L=(LinkList)malloc(sizeof(LinkList)); 需要注意的是类型的强制转化,参照左边的类型。又因为是头插法,所以刚创建的链表头结点指向的下个结点应该是空结点,因为此时是空链表
    3、这里的随机生成方式调用的是srand函数。
    4、用循环的方式依次插入每个结点。每次插入结点也需要申请空间,并分别赋予数据域和指针域的值。特别注意指针指向的结点就是原本链表的下个位置,这种方式就叫头插法。
    5、最后把头指针指向插入的结点
void CreateListHead(LinkList *L,int n)
{
    LinkList s;
    int i;

    srand(time(0));//time函数配合使用,初始化随机数种子

    *L=(LinkList)malloc(sizeof(LinkList));
    (*L)->Next=NULL;

    for(int i=0;i<n;i++)
    {
        s=(LinkList)malloc(sizeof(Node));
        s->data=rand()%100+1;
        s->Next=(*L)->Next;
        (*L)->Next=s;
    }
    free(s);
}
  • 尾插法:
    是将新增结点插入最后一个结点之后,示意图如下:
    数据结构与算法分析之单链表的建立,插入和删除操作。
    解析:
    尾插法和头插法在实现方式上大致相同,
    区别在与:
    1、尾插法需要申明两个指针r和s,r用来指向当前结点的位置,s用来传递插入节点,因此只有s需要申请空间。
    2、把r的指针指向插入结点s,完成后把r指向s的位置。
    3、完成建立后,把r指向空结点。
    实现代码如下:
void CreateListLast(LinkList *L,int n)
{
    LinkList r,s;
    int i;

    srand(time(0));

    *L=(LinkList)malloc(sizeof(Node));
    r=*L;
    for(int i=0;i<n;i++)
    {
        s=(LinkList)malloc(sizeof(Node));
        s->data=rand()%100+1;
        r->Next=s;
        r=s;
    }
    r->Next=NULL;
}
  • 单链表的插入操作
    在结点p之前插入一个新的结点q,由于q的位置的不同,插入操作有以下两种情况:
    1)在链表的表头插入
    1、创建一个新的结点q。
    2、将此结点的数据域赋值e,并将它的Next指针指向第一个结点。
    3、将头结点的指针指向新的结点q。
    实现示意图如下:
    数据结构与算法分析之单链表的建立,插入和删除操作。
    2)在链表的中间插入
    1、创建一个新结点q。
    2、将此结点的数据域赋值为e,将next指针指向p.
    3、查找p指针的先驱结点pre。
    4、将pre的next指针指向q。
    实现示意图如下:
    数据结构与算法分析之单链表的建立,插入和删除操作。
    解析:
    1、插入操作需要
    代码实现如下:
int ListInsert(LinkList * L, int i,int e)
{
  int j;
  LinkList p,s;
  p=*L;
  j=1;

  while(p&&j<i)
  {
      p=p->Next;
      j++;
  }

  if(!p||j>i)
      return false;

  s=(LinkList)malloc(sizeof( Node));//左边是结构体类型的指针,右边也需要强制转化为这种类型

  p->data=e;
  s->Next=p->Next;
  p->Next=s;

  return true;
}
  • 单链表的删除操作
    删除链表中的某个元素e,如果e在链表中出现不止一次,将删除第一次出现的e:
    1)p是链表中的第一个结点
    1、将L指向p->next。
    2、释放p。
    示意图如下:
    数据结构与算法分析之单链表的建立,插入和删除操作。
    2)p是链表中的其他结点
    1、找到p的前驱结点pre。
    2、将pre->next指向p->next。
    3、释放p。
    示意图如下:
    数据结构与算法分析之单链表的建立,插入和删除操作。
    具体实现代码如下:
int ListDelete(LinkList * L ,int i,int *e)
{
    //查找到第i个位置
   LinkList p,q;
   int j=1;
   p=*L;

   while(p->Next&&j<i)//注意点,因为是删除,考虑的是链表的下一个元素是否为空
   {
       p=p->Next;
       j++;
   }

   if(!(p->Next)||j>i)
       return false;

   q=p->Next;
   p->Next=q->Next;

   *e=q->data;
   free(q);

   return true;

}这里写代码片

资料参考
http://blog.csdn.net/wp1603710463/article/details/50989500