单链表&循环链表

Written with StackEdit中文版.

链表

简介

链表，是线性表的链式存储结构，相比于顺序表的结构特点来说，即逻辑关系上相邻的两个元素在物理位置上也相邻，是用一组（地址）任意的存储单元，如C语言中的结构体，来存储线性表的数据元素。这组存储单元可以是连续的，也可以是不连续的。

• 连续的存储单元是用数组来实现链表结构的，这种数组描述的链表又名静态链表（这里不实现）
• 不连续的存储单元使用指针来实现链表结构的，即存储单元之间用指针相连。根据相连的情况，分为单链表、循环链表和双向链表。

声明与定义

typedef int ElemType;
typedef int Status;
#define OK 1
#define ERROR 0

//单链表、循环链表的存储结构
typedef struct LNode
{
  ElemType data;//数据域
  struct LNode* next;//指针域
}LNode,*LinkList;

相关方法

逆位序手动输入n个元素的值，建立带表头结点的单链表L

void CreateList_L(LinkList* L, int n) {
  *L = (LinkList)malloc(sizeof(LNode));
  (*L)->next = NULL; //先建立一个带头结点的单链表，其中L是指向结构体指针的指针，加取值符变成结构体指针
  printf("开始输入元素\n");
  for (int i = n; i > 0; --i) {
    LinkList p = (LinkList)malloc(sizeof(LNode));
    scanf_s("%d", &p->data); //输入元素值
    p->next = (*L)->next; //插入到表头
    (*L)->next = p;
    printf("已经输入%d个元素\n", n - i + 1);
  }
}

---

顺位序手动输入n个元素的值，建立单链表L

注意是用返回值来接受参数

LinkList CreateList_L1(int n){
  LNode* end, * p, * L;
  L = (LinkList)malloc(sizeof(LNode));//L是头结点
  end = L;
  for (int i = 0; i < n; i++){
    p = (LinkList)malloc(sizeof(LNode));//p是普通结点
    if (p == NULL){
      return 0;
    }
    scanf_s("%d", &p->data);
    end->next = p;
    end = p;
  }
  end->next = NULL;//end是尾结点，指针域是NULL
  return L;
}

---

逆位序手动输入n个元素的值，建立带表头结点的循环链表L

void CreateCirList_L(LinkList* L, int n) {
  *L = (LinkList)malloc(sizeof(LNode));
  LinkList q = (LinkList)malloc(sizeof(LNode));//这是尾结点
  q->next = *L;//尾结点的指针指向头结点
  //初始化的时候头结点的指针也要指向尾结点
  (*L)->next = q; //先建立一个带头结点的单链表，其中L是指向结构体指针的指针，加取值符变成结构体指针
  printf("开始输入元素\n");
  for (int i = n; i > 0; --i) {
    LinkList p = (LinkList)malloc(sizeof(LNode));
    scanf_s("%d", &p->data); //输入元素值
    p->next = (*L)->next; //插入到表头
    (*L)->next = p;
    printf("已经输入%d个元素\n", n - i + 1);
  }
}

---

返回链表L的第i个元素

Status GetElem_L(LinkList L, int i,ElemType* e){ //值传递L
  //L是带头结点的单链表的头指针,若第i个元素存在则赋值给e并返回OK，否则返回ERROR
  LinkList p = L->next; //初始化，p指向L的第一个结点
  int j = 1; //计数器
  while (p && j < i) {//顺指针向后查找，直到p指向第i个元素或p为空
    p = p->next;
    ++j;
  }
  if (!p || j > i){
    printf("第%d个元素不存在!\n", i);
    return ERROR;
  }
  *e = p->data; //取第i个元素
  return OK;
}

---

在链表L的第i个位置插入元素e

Status ListInsert_L(LinkList *L, int i, ElemType e){
  LinkList p = *L;
  int j = 0;
  while (p && j < i - 1){//寻找第i-1个结点
    p = p->next;
    ++j;
  }
  if (!p || j > i - 1){//i小于1或者i大于表长+1
    printf("ERROR!\n");
    return(ERROR);
  }
  LinkList s = (LinkList)malloc(sizeof(LNode));//生成一个新节点并插入L中
  if (s != NULL){
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
  }
  else return ERROR;
}

---

删除链表L的第i个元素

将被删除的第i个元素赋值给e并由e返回值

Status ListDelete_L(LinkList *L, int i,ElemType *e){
  LinkList p = *L; //L是指向结构体指针的指针，需要取值符*
  int j = 0;
  while (p->next && j < i - 1){//寻找第i个结点，并令p指向其前驱
    p = p->next; ++j;
  }
  if (!(p->next) || j > i - 1){//删除位置不合理
    printf("ERROR!\n");
    return ERROR;
  }
  LinkList q = (LinkList)malloc(sizeof(LNode));
  q = p->next; p->next = q->next;//删除原本p->next结点
  *e = q->data; //释放结点
  free(q);
  return OK;
}

---

链表遍历函数

Status ListTraverse(LinkList L) {
  printf("遍历整个链表：");
  LinkList p = L->next;
  if (p) {
    while(p){
        printf("%d ", p->data);
        p = p->next;
      }
  }
  printf("遍历结束\n");
  return OK;
}

---

循环链表遍历函数

想要遍历的元素个数可以超过结点数，即实现循环

Status CirListTraverse(LinkList *L,int n) {
  printf("开始遍历：");
  LinkList p = (*L)->next;
  if (p) {
    while (n > 0) {
      if (p->next != *L) { //当没有遍历到尾结点的时候就打印输出元素
        printf("%d ", p->data);
        p = p->next; //访问下一个结点
        n--;
      }
      else{ //访问到尾结点了，就把指针指向到头结点后面的结点
        p = (*L)->next;
      }
    }
  }
  printf("遍历结束\n");
  return OK;
}

方法测试

int main(void)//上述函数的测试
{
  //逆位序建立n个元素的循环链表
  LinkList MyCirList;
  int m = 0;
  int count = 0;
  printf("需要建立几个元素的循环链表?（逆序输入！！！）\n");
  scanf_s("%d", &m);
  CreateCirList_L(&MyCirList, m);
  printf("需要遍历几个元素？\n");
  scanf_s("%d", &count);
  CirListTraverse(&MyCirList,count);


  //逆位序建立n个元素的单链线性表
  LinkList MyList;
  int n = 0;
  printf("需要建立几个元素的单链线性表?（逆序输入！！！）\n");
  scanf_s("%d", &n);
  CreateList_L(&MyList, n);
  ListTraverse(MyList);

  //取链表第n个元素并打印
  ElemType e;
  int pos;
  printf("需要取链表的第几个元素?\n");
  scanf_s("%d", &pos);
  GetElem_L(MyList, pos, &e);
  printf("链表第%d个元素是：%d\n", pos, e);

  //往链表的第n个位置插入元素e
  printf("需要向链表的什么位置插入元素?\n");
  scanf_s("%d", &pos);
  printf("插入元素是?\n");
  scanf_s("%d", &e);
  ListInsert_L(&MyList, pos, e);
  //查看插入位置的元素是否更新?
  GetElem_L(MyList, pos, &e);
  printf("链表第%d位的元素是：%d\n", pos, e);
  ListTraverse(MyList);

  //删除链表的第n个位置的元素，并打印其值
  printf("需要删除链表什么位置的元素?\n");
  scanf_s("%d", &pos);
  ListDelete_L(&MyList, pos, &e);
  printf("原本链表第%d个位置的元素%d被删除!\n", pos, e);
  ListTraverse(MyList);
  return 0;
}