数据结构笔记目录：

单链表的表示

typedef struct Lnode{
  ElemType data;
  struct Lnode* next;
}Lnode,*LinkList; //LinkList为指向结构体Lnode的指针类型
//定义链表
LinkList L;
//定义节点指针p
LNode* p;
//LinkList == LNode*，分开两种定义方式的目的是使定义更加清晰

Ex:1：存储学生信息的单链表

typedef struct student{
  char nom[12]; //学号数据域
  char name[8]; //姓名数据域
  int score; //学生成绩数据域
  struct student* next; //指针域
}LNode,* LinkList;

单链表的初始化、判空、销毁、清空

单链表的初始化

int initList_L(LinkList &L){
  L = (Lnode*)malloc(sizeof(Lnode)); //生成新结点作为头结点，用头指针L指向头结点
  L -> next = NULL; //将头结点的指针域置空
  return 1;
}

单链表的判空：判断头结点指针域是否为空

int ListEmpty(LinkList L){
  if(L->next == NULL){
    return 1;
  }
  else{
    return 0;
  }
}

单链表的销毁：从头指针开始，依次释放所有节点

int DestroyList_L(LinkList &L){
  Lnode* p;
  while(L != NULL){
    Lnode* p = L;
    L = L->next;
    free(p);
  }
}

单链表的清空：依次释放所有结点，并将头结点指针域设置为空

int ClearList_L(LinkList &L){
  Lnode* p = L->next; //指向要销毁的结点
  Lnode* q; //指向要销毁的结点的下一个节点
  while(p != NULL){
    
    Lnode* q = p->next;
    free(p);
    p = q;
  }
  L->next = NULL;
  return 1;
}

求单链表的表长

int ListLength_L(LinkList L){
  Lnode* p = L->next;
  int sum = 0;
  while(p != NULL){
      sum++;
      p = p->next;
  }
  return sum;
}

单链表的增删查改

求单链表的第i个元素

int GetElem_L(LinkList L,int i,ElemType &e){
  Lnode* p = L->next;
  int j = 1; //j表示现在p所指向的结点是链表L中的第几个元素
  while(p != NULL && j < i){
    p = p->next;
    j++;
  } //向后扫描，直到p指向第i个元素或p为空（即i超过了链表长度）
  if( !p || j > i )return 0; //！p对应i值过大，找不到，j>i对应i太小，不合法
  e = p->data;
  return 1;
}

单链表按值查找

int LocateElem_L(LinkList L,ElemType e){
  Lnode* p = L->next;
  int i=1;
  while(p != NULL && p->data != e){
    p = p->next;
    i++;
  }
  if(p == NULL) return 0;
  else return i;
}

单链表的插入

int ListInsert_L(LinkList &L,ElemType e,int i){
  Lnode* p = L -> next; //现在指向的结点（头结点非首元结点情况）
  Lnode* q = (Lnode*)malloc(sizeof(Lnode)); //创建一个新结点
  q -> data = e;
  int j = 1; //j表示现在p所指向的结点是链表L中的第几个元素
  while(p != NULL && j < i - 1){
    p = p -> next;
    j++;
  }
  if(p == NULL || j > i) return 0;
  else{
    q -> next = p -> next;
    p -> next = q ;
    return 1;
  }
}

单链表结点的删除

int ListDelete_L(LinkList &L,int i,ElemType &e){
  Lnode* p = L -> next; //现在指向的结点（头结点非首元结点情况）
  int j = 1; //j表示现在p所指向的结点是链表L中的第几个元素
  while(j < i - 1 && p -> next != NULL){ //第二个条件不是p != NULL的原因是遍历的终点是链表最后一个元素的前驱，即倒数第二个元素
    p = p -> next;
    j++;
  } //寻找第i个结点的前驱
  if(p -> next == NULL || j > i) return 0;
    else{
      Lnode* q = p -> next; //临时保存被删结点的地址以备释放
      e = q -> data; //保存被删除结点数据域
      p -> next = q -> next; //改变被删除节点前驱的指针域（后继）
      free(q); //释放被删除结点所占空间
      return 1;
  }
}

头插法、尾插法建立链表

头插法建立链表

void CreateList_H(LinkList &L,int n){
  L = (LNode *)malloc(sizeofL(Node));
  L -> next = NULL;
  int i;
  for(i = n,i > 0,i--){
    Lnode* p = (LNode *)malloc(sizeof(LNode));
    cin >> p -> data;
    p -> next = L -> next;
    L -> next = p;
  }
}

时间复杂度为O(n)

尾插法建立链表

void CreateList_E(LinkList &L,int n){
  L = (LNode *)malloc(sizeof(LNode));
  L -> next = NULL; //建立头结点和指向头节点的指针
  Lnode* p = (LNode *)malloc(sizeof(LNode));
  p -> next = L; //指向当前最后一个结点的结点（尾指针）
  int i;
  for(i = 0,i < n,i++){
    Lnode* q = (LNode *)malloc(sizeof(LNode)); 
    q -> next = NULL; 
    cin >> q -> data;//生成新结点
    p -> next = q;
    p = q; 
  }
}