单链表

定义

数据域：存储数据元素信息的域，指针域：存储直接后继位置的域。指针域中存储的信息成为指针或链。这两部分信息组成数据元素成为存储映像，成为结点(Node)。
数据域|指针域
-|-
data|next

头结点与头指针

• 头结点
  头结点是加在单链表之前附设的一个头结点。头结点的数据域一般不存储任何信息，也可以存放一些关于线性表的长度的附加信息。
  -头指针
  头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针。

  代码

  #include<iostream>
  #include<stdio.h>
  #include<math.h>
  #define NULL 0
  
  typedef int ElemType;
  
  void Error(char *s){
      cout<<s<<endl;
      exit(1);
  }
  
  typedef struct LNode
  {
      ElemType data;
      struct LNode *next;
  }LNode;
  typedef LNode *Linklist;    //头指针
  void Error(char *s)           //错误指示
  {
      std::cout << s << endl;
      exit(1);
  }
  //创建链表,生成一个新节点作为头结点,并设其指针域为空
  Void InitList(Linklist &L)
  {
      L=new LNode;
      L->next=NULL;
  }
  //销毁链表,从链表的头结点开始依次释放表中每一个结点所占用的存储空间
  Void DestroyList(Linklist L)
  {
      while(L){
          LNode *p=L;
          L=L->next;
          delete p;
      }
  }
  //设置单链表为空表，并释放所有结点空间
  void ClearList(Linklist &L)
  {
      LNode *p = L->next;
      L->next=NULL;
      L.length=0;
      while (p)
      {
          Linklist *q=p;
          p = p->next;
          delete q;
      }
  }
  //求链表长度
  int ListLength(Linklist L)
  {
      int length=0;
      LNode *p = L;
      while(p->next){
          length++;
          p=p->next;
      }
      return length;
  }
  //返回链表中第i个结点数据域的值，1<=i<=表长;若i值不合法，则给出错误信息
  ElemType GetElem_L(Linklist L, int i)
  {
      int count = 1;
      LNode *p = L->next;
      while (p && (count < i)) {
          p = p->next;
          count++;
      }
      if (!(p->next)||count>i)  Error("position Error") ;
      else  return  p->data;
  }
  //查找链表中第一个数据域值和x相等的结点
  LNode *LocateElem_L(Linklist L, ElemType x)
  {
      LNode *p =L->next;              //将指针头传给指针p
      int j = 1;
      while (p && (p->data != x))   //向后扫描查找
      {
          p = p->next;
      }
      return p;
  }
  //向链表中第i个位置插入元素x ,1<=x<=表长+1
  //若插入位置不合理则给出相应信息
  void ListInsert(Linklist &L, int i, int stu)
  
  {
      LNode *p =L;              //将指针头传给指针p
      int j = 0;
      while (p && (j < i - 1))   //向后扫描查找
      {
          p = p->next;
          j++;
      }
      if (!p || (j > i - 1))     //输入参数不对，给出错误提示，并跳出
          Error("Postion Eeeor!");
      else
      {
          LNode *s = new  LNode;
          s->next = p->next;
          p->next = s;
      }
  }
  //删除链表L中第i个结点数据域值，并用返回,1<=x<=表长+1
  //若删除位置不合理则给出相应信息
  ElemType ListDelete_L(Linklist &L, int i)
  {
      LNode *p = L; //将指针头传给指针p
      int j = 0;
      while ((p ->next) && (j < i - 1))
      {
          p = p->next;
          j++;
      }
      if (!(p->next) || (j > i - 1))
          Error("Postion Eeeor!"); // 输入参数不对，给出错误提示，并跳出
      else
      {
          LNode *q = p->next;
          ElemType x= p->data;
          p->next = q->next;
          delete q;
          return x;
      }
  }

单链表正标操作

整表创建

头插法

/**
* 头插法
*/
void CreatListHead(LinkList *L, int n){

    LinkList p;
    int i;

    srand(time(0));  // 初始化随机数种子

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

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

        p = (LinkList)malloc(sizeof(Node)); // 生成新节点
        p ->data = rand()%100 + 1;
        p->next = (*L)->next;
        (*L)->next = p;

    }
}

尾插法

/**
* 尾插法
*/
void CreatListTail(LinkList *L, int n){

    LinkList p, r;
    int i;

    srand(time(0));
    *L = (LinkList)malloc(sizeof(Node));
    r = *L;

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

        p = (Node *)malloc(sizeof(Node));
        p->data = rand()%100+1;
        r->next = p;
        r = p;
    }

    r->next = NULL;
}

整表删除

Status ClearList(LinkList *L){

    LinkList p,q;

    p = (*L)->next;

    while (p) {
        q = p->next;
        free(p);
        p = q;
    }

    (*L)->next = NULL;

    return OK;
}