单链表的操作

单链表的操作

2021 年 09 月 12 日

559 次浏览

2947字数

单链表代码定义

typedef struct LinkNode
{
  int data;                                //data存放结点的数据域（以int类型为例）
  struct LinkNode *next;    //结点的指针域
}LinkNode, LinkList;

初始化单链表

bool initList(LinkList* &L)            //L类型为引用类型的指针
{
  L = new LinkNode;            //为L分配一个动态内存
  if(!L)    return false;    //若分配失败则返回false
  
  //头结点指针指向空完成初始化，成功创建一个空的单链表并返回true
  L->next = NULL;
  return true;
}

插入结点

注： L为插入的单链表，node为将要插入的结点

前插法

bool ListInsert_front(LinkList* &L, LinkNode *node)
{
  //合法性检查
  if(!L || !node) return false;
  
  node->next = L->next;        //把新结点指针指向原来头结点所指向的结点
  L->next = node;                    //把头结点指向新结点
}

尾插法

bool ListInsert_back(LinkList* &L, LinkList *node)
{
  LinkNode *last = NULL;
  if(!L || !node) return false;
  
  last = L;
  
  //找到尾结点
  while(last->next) last = last->next;
  
  //重置指针
  node->next = NULL;
  last->next = node;
  
  return true;
}

任意位置插入

//任意位置插入
/*
 *  参数： 要插入的单链表， 位置， 取值 
 */
bool LinkInsert(LinkList* &L, int i, int &e)
{
    if(!L) return false;
  
    int j = 0;
    LinkList *p, *s;
    p = L;
  
    //让p寻找插入位置
    while(p && j<i-1)
    {
        p = p->next;
        j++;
    }
  
      //如果插入位置大于链表节点数，最后p为空
    //有一种情况为：若i <= 0 ,j<i-1不成立，但此时p为真，所以这里使用 !p || j>i-1
    if(!p || j>i-1)
    {
        return false;
    }
  
  //当i = 0时，p为真且 j = i - 1， 此时指向头结点，直接来到下方这一步
  
    s = new LinkNode;  //生成新结点
    //连接结点
    s->data = e;            //保存数据
    s->next = p->next;
    p->next = s;
  
    return true;
}

输出单链表中的元素

void LinkPrint(LinkList* &L)
{
  LNode *p = NULL;  
  if(!L)
  {
    cout << "此链表为空\n";
    return;
  }
  
  p = L->next;
  
  while(p)
  {
    cout << p->data << "\t";
    p = p->next;
  }
  cout << endl;
}

元素找查

按位置查找

与任意位置插入类似，只不过要注意访问头结点的情况（带头结点的单链表头结点数据域无初始化数据）

/*
 *  参数： 单链表， 位置， 取值 
 */
bool GetLinkListElemAsAddress(LinkList* &L, int i, int &e)
{
    if(!L || !L->next) return false;

    int j = 0;
    LinkList *p;
    p = L;

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

    if(!p || j >= i - 1)    //这里取等号是为了避免访问头结点数据
    {
        return false;
    }

    e = p->data;

    return true;
}

按值查找

/*
* 带头结点的单链表L中找查值为e的元素
* 参数：单链表， 取值, 返回所找元素的位置
*/
bool GetLinkListElemAsValue(LinkList *L, int e, int &index)
{
  LinkList *p;
  p = L->next;
  index = 1;
  
  if(!L || !L->next)
  {
    index = 0;
    return false;
  }
  
  while(p && p->data! = e)
  {
    p = p->next;
    index++;
  }
  
  if(!p)
  {
    index = 0;
    return false;    //查无此值
  }
  return true;
}

结点的删除

bool LinkListDel(LinkList* &L, int i)
{
  LinkList *p, *q;
  int index = 0;
  p = L;
  
  //合法性检查
  if(!L || !L->next)
  {
    return false;
  }
  
  while((p->next) && (index < i-1))
  {
    p = p->next;
    index++;
  }
  
  //删除位置不合理
  if(!p->next || (index > i - 1))
  {
    return false;
  }
  q = p->next;            //临时存放被删结点地址
  p->next = q->next;//改变删除结点前驱指针域
  delete q;
  return true;
  
}

单链表的销毁

分配动态内存后，记得销毁

void LinkDestory(LinkList* &L)
{
  //定义临时结点指向头结点
  LinkList *p = L;
  
  cout << "销毁链表" << endl;
  
  //遍历并删除结点
  while(p)
  {
    L = L->next;
    delete p;
    p = L;
  }
  
}

单链表的操作