数据结构（C语言严蔚敏版）——第二章线性表

标签：pb 结点 NULL 线性表 next 链表 C语言严蔚敏版 struct

前言：

对这一章节的学习，我深有体会，只有把链表这一重点弄清楚，才算开始真正的正式学习数据结构，刚开始学习链表的朋友可能会感到有点绕脑，但是当你掌握链表以后，你会发现其实原来学习编程还是很有意思的，慢慢在学习中找到成就感，不断收获。

当然，这章的重点还是在链表的创建，删除，插入等操作，该部分我已经给出了详细的代码解释，理解起来也不算难，刚开始接触的朋友一定要把链表的基本操作理解透彻以后再开始下一部分的学习，切勿好高骛远，学习的目的是充实自己，而不是为了跟别人一较高下，多花时间，慢慢来，不要着急！加油！

2.1 线性表的类型定义

线性表（ linear_list ）：是最常用且最简单的一种数据结构，简言之，一个线性表是n个数据元素的有限序列。

在稍复杂的线性表中，一个数据元素可以由若干个数据项组成。在这种情况下，常把数据元素称为记录（record），含有大量记录的线性表又称文件（file）。

2.2 线性表的顺序表现和实现

这个地方不是重点，了解线性表的意思即可；

线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。

2.3 线性表的链式表示和实现（重点）

2.3.1 线性链表

线性表的存储结构的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素Ai与其直接后续数据元素Ai+1之间的逻辑关系，对数据元素Ai来说，除了存储其本身的信息之外，还需要存储一个指示其直接后继的信息（即直接后继的存储位置）。这两部分信息组成数据元素Ai的存储映像，称为结点（node).它包括两个域：其中存储数据元素信息的域称为数据域；存储直接后续存储位置的域称为指针域。指针域中存储的信息称作指针或链。n个结点（Ai(1<=i <=n)的存储映像）链结成一个链表，即为线性表（A1，A2，… ，An)的链式存储结构。又由于此链表的每个结点中只包括指针域，故又称线性链表或单链表。

整个链表的存取必须从头指针开始进行，头指针指示链表中第一个结点（即第一个数据元素的存储映像）的存储位置。同时，由于最后一个数据元素没有直接后续，则线性链表中最后一个结点的指针为“空”（NULL）

通常我们把链表画出用箭头相连接的结点的序列，结点之间的箭头表示链域中的指针。如图2.6，这是因为在使用链表时，关心的只是它所表示的线性表中数据元素之间的逻辑顺序，而不是每个数据元素在存储器中的实际位置。
#include<stdio.h>
typedef struct ListNode{
    int data //数据域
    struct ListNode *next;//指针域
}LNode,*Linklist;
//线性表的单链表存储结构
假设L是LinkList型的变量，则L为单链表的头指针，它指向表中的第一个结点。若L为“空”（L=NULL），则所表示的线性表为“空”表，其长度n为“零”。有时，我们在单链表的第一个结点之前附设一个结点，称之为头结点，头结点的数据域可以不存储任何信息，也可存储如线性表的长度等类的附加信息。头结点的指针域存储指向第一个结点的指针（即第一个元素结点的存储位置）。

2.3.2 动态链表的初始化、遍历、插入、清空、删除、销毁（重点，理解，消化）

（一）主函数部分

  #include<stdio.h>
//定义结点数据类型
struct LinkNode{
    int data;
    struct LinkNode *next;
};
int main(){
  //初始化链表
  struct LinkNode *Init_LinkNode();
  //在值为oldval的后面插入一个新的数据newval
  void InsertByValue_LinkList(struct LinkNode *header,int oldval,int newval);
  //删除值为val的结点
  void RemoveByValue_LinkList(struct LinkNode *header,int delValue);
  //遍历
  void Foreach_LinkList();
  //销毁
  void Destroy_LinkList(struct LinkNode *header);
  //清空
  void Clear_LinkList(struct LinkNode *header);
  return 0;
}

（二）链表的创建

//初始化链表
  struct LinkNode *Init_LinkNode(){
    //创建头结点
    struct LinkNode *header = (struct LinkNode*)malloc(sizeof(struct LinkNode));
    header->data = -1;
    header->next = NULL;
    
    //尾部指针
    struct LinkNode *pRear = header;
    
    int val = -1;
    while(1){
      printf("输入插入的数据：\n);
      scanf("%d",&val);
      if(val == -1){
        break;//这里以输入-1表示输入结束，具体按照题目要求来
      }
      //先创建新结点
      struct LinkNode *newnode = malloc(sizeof(struct LinkNode));
       newnode->data = val;
       newnode->next =NULL;
             
       //新结点插入到链表中
       pRear->next = newnode;
             
       //更新尾部指针指向
       pRear = newnode;
    }
    return header; 
  }

（二）在链表中插入一个链表中没有的数据（重点掌握怎么插入新数据）

//在值为oldval的后面插入一个新的数据newval
  void InsertByValue_LinkList(struct LinkNode *header,int oldval,int newval){
    if(NULL == header){
      return;
    }
    //两个辅助指针变量
    struct LinkNode *pPrev = headr;
    struct LinkNode *pCurrent = pPrev->next;
    while(pCurrent != NULL){
      if(pCurrent->data == oldval){
        break;
      }
      pPrev = pCurrent;
      pCurrent = pCurrent->next;
    }
    //如果pCurrent为NULL   说明链表中不存在值为oldval的结点
    if(pCurrent == NULL){
      return;
    }
    //先创建新结点
    struct LinkNode *newnode = malloc(sizeof(struct LinkNode));
    newnode->data = newval;
    newnode->next = NULL;
    //新结点插入到链表中
    newnode->next = pCrrent;
    pPrev->next = newnode;
  }

（三）删除某个结点

//删除值为val的结点
  void RemoveByValue_LinkList(struct LinkNode *header,int delValue){
    if(NULL == header){
      return;
    }
    //两个辅助指针变量
    struct LinkNode *pPrev = header;
    struct LinkNode *pCurrent = pPrev->next;
    while(pCurrent != NULL){
      if(pCurrent->data == delValue){
        break;
      }
      //移动两个辅助指针
      pPrev = pCurrent;
      pCurrent = pCurrent->next;
    }
    if(NULL == pCurrent){
      return;
    }
    //更新建立待删除结点的前驱和后继结点关系
    pPrev->next = pCurrent->next;
    //释放删除结点内存
    free(pCurrent);
    pCurrent = NULL;
  }

（四）遍历链表

//遍历
  void Foreach_LinkList(){
    if(NULL == header){
      return;
    }
    //辅助指针变量
    struct LinkNode *pCurrent = header->next;
    while(pCurrent != NULL){
      printf("%d ",pCurrent->data);
      pCurrent = pCurrent->next;
    }
  }
  //销毁
  void Destroy_LinkList(struct LinkNode *header){
    if (NULL == header){
      return;
    }
    //辅助指针变量
    struct Linknode *pCurrent = header;
    while (pCurrent != NULL){
    //先保存下当前结点的下一个结点地址
      struct LinkNode *pNext = pCurrent->next;
      //释放当前结点内存
      free(pCurrent);
      //指针向后移动
      pCurrent=pNext;
    }
  }

（五）清空

//清空
  void Clear_LinkList(struct LinkNode *header){
    if(NULL == header){
      return;
    }
    //辅助指针变量
    struct LinkNode *pCurrent = header->next;
    while(pCurrent != NULL){
      //先保存下当前结点的下一个结点地址
      struct LinkNode *pNext = pCurrent->next;
      
      //释放当前结点内存
      free(pCurrent);
      //pCurrent指向下一个结点
      pCurrent = pNext;
    }
    header->next = NULL;
  }

2.3.3 循环链表

循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域向头结点，整个链表形成一个环。类似地，还可以有多重链的循环链表。

循环链表的基本操作和线性链表基本一致，差别仅在于算法中的循环条件不是p或p->next是否为空，而是它们是否等于头指针。但有的时候，若在循环链表中设立尾指针而不设头指针（如图2.13（a）所示），可使某些操作简化。例如将两个线性表合并成一个表时，仅需将一个表的表尾和另一个表的表头相接。

当线性表以图2.13（a）的循环链表作存储结构时，这个操作仅需改变两个指针值即可，运算时间为O(1).合并后的表如图2.13（b）所示。

循环链表的代码：
struct ListNode{
    int data;
    struct ListNode *next;
};
void CreateLink(){
    int n;//创建n个结点
    scanf("%d",&n);
    struct ListNode *head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->data = -1;//设立头结点
    head->next = NULL;
    struct ListNode *tail = head;
    while(n--){
        struct ListNod *news = (struct ListNode*)malloc(sizeof(struct ListNode));
        scanf("%d",news->data);
        news->next = NULL;
        tail->next = news;
        tail = news;
    }
    tail->next = head //最后一个结点的指针域指向头，完成循环连接
    return tail;//注意，这个地方返回的是最后一个结点的地址，而不是头结点的
}

2.3.4 双向链表

单链表只有一个指示直接后继的指针域，由此，从某个结点出发只能顺指针往后寻查其他结点。若要寻查结点的直接前趋，则需从表头指针出发。为了克服单链表这种单向性的缺点，可利用双向链表。

typedef struct ListNode{
    int data;
    struct ListNode *prior;//保存上一个数据元素的地址
    struct ListNode *next;//保存下一个数据元素的地址
    }Node;

和单链的循环表类似，双向链表也可以有循环表，如图2.14(c)所示，链表中存有有两个环，图2.14(b)所示为只有一个表头结点的空表。

1、双向链表的创建和遍历

第一步：创建一个结点作为头结点，将两个指针域都保存为NULL

第二步：先找到链表中的最后一个结点，然后让最后一个结点的指针域保存新插入结点的地址，新插入结点的两个指针域，一个保存上一个结点地址，一个保存NULL

//定义结点结构体
typedef struct student
{
  //数据域
  int num;//学号
  int score;//分数
  char name[20];//姓名
  //指针域
  struct student *front;//保存上一个结点的地址
  struct student *next;//保存下一个结点的地址
}STU;
void double_link_creat_head(STU **p_head,STU *p_new)
{
  STU *p_mov = *p_head;
  if(*p_head == NULL)  //当第一次加入链表为空时
  {
    *p_head = p_new;
    p_new->front = NULL;
    p_new->next = NULL;
  }
  else  //第二次及以后加入链表
  {
    while(p_mov->next != NULL){
      p_mov = p_mov->next; //找到原有链表的最后一个结点
    }
    p_mov->next = p_new; //将新申请的结点加入链表
    p_new->front = p_mov;
    p_new->next = NULL;
  }
}

void double_link_print(STU *head)
{
  STU *pb;
  pb = head;
  while(pb->next != NULL)
  {
    printf("num=%d score=%d name:%s\n",pb->num,pb->score,pb->name);
    pb = pb->next;
  }
  printf("num=%d score=%d name:%s\n",pb->num,pb->score,pb->name);
  printf("***********************\n");
  while(pb!=NULL)
  {
    printf("num=%d score=%d name:%s\n",pb->num,pb->score,pb->name);
    pb = pb->front;
  }
}

int main(){
  STU *head = NULL,*p_new = NULL;
  int num,i;
  printf("请输入链表初始个数：\n");
  scanf("%d",&num);
  for(i=0;i<num;i++){
    p_new = (STU*)malloc(sizeof(STU));//申请一个新结点
    printf("请输入学号、分数、名字：\n");//给新结点赋值
    scanf("%d %d %s",&p_new->num,&p_new->score,p_new->name);
    double_link_creat_head(&head,p_new);//将新结点加入链表
    }
  double_link_print(head);
}

2、双向链表结点的删除

如果链表为空，则不需要删除

如果删除第一个结点，则保存链表首地址的指针保存后一个结点的地址，并且让这个结点的front保存NULL

如果删除最后一个结点，只需要让最后一个结点的前一个结点的next保存NULL即可

如果删除中间结点，则让中间结点的前后两个结点的指针域分别保存对方的地址即可

//双向链表的删除
void double_link_delete_num(STU **p_head,int num)
{
  STU *pb,*pf;
  pb = *p_head;
  if(*p_head == NULL)//链表为空，不需要删除
  {
    printf("链表为空，没有您要删除的结点\n");
    return NULL;
  }
  while((pb->num != num) && (pb->next != NULL))
  {
    pb = pb->next;
  }
  if(pb->num == num)//找到了一个结点的num和num相同，删除Pb指向的结点
  {
    if(pb == *p_head)//找到的结点是头结点
    {
      if(pb == *p_head)//找到的结点是头结点
      {
        if((*p_head)->next == NULL)//只有一个结点的情况
        {
          *p_head = pb->next;
        }
        else //有多个结点的情况
        {
          *p_head = pb->next;//mian函数中的head指向下个结点
          (*p_head)->front = NULL;
        }
      }
      else //要删的结点是其他结点
      {
        if(pb->next!=NULL)//删除中间结点
        {
          pf = pb->front;//让pf指向找到的结点的前一个结点
          pf->next = pb->next; //前一个结点的next保存后一个结点的地址
          (pb->next)->front = pf;//后一个结点的front保存前一个结点的地址
        }
        else //删除尾结点
        {
          pf = pb->front;
          pf->next = NULL;
        }
      }
      free(pb);//释放找到的结点
    }

3、双向链表的插入

void double_link_insert_num(STU **p_heaad,STU *p_new)
{
  STU *pb,*pf;
  pb = *p_head;
  if(*p_head == NULL)//链表为空，新来的结点就是头结点
  {
    *p_head = p_new;
    p_new->front = NULL;
    p_new->next = NULL;
    return NULL;
  }
  while((p_new->num >= pb->num) && (pb->next != NULL))
  {
    pb = pb->next;
  }
  if (p_new->num < pb->num) //找到了一个pb的num比新来的结点的num大,插在pb前面 
  {
    if(pb==*p_head)//找到的结点是头结点，插在头结点的前边
    {
      p_new->next = *p_head;//新插入的结点的next保存之前头结点的地址
      (*p_head)->front = p_new;//之前头结点的front保存新插入的结点的地址
      p_new->front = NULL;//新插入的结点的front保存NULL
      *p_head = p_new;//让原本保存链表首地址的指针保存新插入结点的地址
    }
    else
    {
      pf = pb->front;//pf指向 找到结点的前一个结点
      p_new->next = pb;
      p_new->front = pf;
      pf->next = p_new;
      pb->front = p_new;
    }
  }
  else //所有pb指向结点的num都比p_new指向的结点的num小，插在最后
  {
    pb->next = p_new;
    p_new->front = pb;
    p_new->next = NULL;
  }
}

标签：pb,结点,NULL,线性表,next,链表,C语言,严蔚敏版,struct
From： https://blog.csdn.net/2301_80818909/article/details/139456346

数据结构（C语言严蔚敏版）——第二章线性表

2.1 线性表的类型定义

2.2 线性表的顺序表现和实现

2.3 线性表的链式表示和实现（重点）

2.3.1 线性链表

2.3.2 动态链表的初始化、遍历、插入、清空、删除、销毁（重点，理解，消化）

2.3.3 循环链表

2.3.4 双向链表

相关文章

赞助商

阅读排行

数据结构（C语言严蔚敏版）——第二章 线性表

2.1 线性表的类型定义

2.2 线性表的顺序表现和实现

2.3 线性表的链式表示和实现（重点）

2.3.1 线性链表

2.3.2 动态链表的初始化、遍历、插入、清空、删除、销毁（重点，理解，消化）

2.3.3 循环链表

2.3.4 双向链表

相关文章

赞助商

阅读排行

数据结构（C语言严蔚敏版）——第二章线性表