链表的理解

资讯 2023-12-06 17:06:36

链表是结构体变量与结构连接在一起,在数据中线性排列。

链表都有一个头指针,一般以head 表示,存放的是一个地址。链表中的节点分为两类,头结点和一般节点,头结点是没有数据域的。链表中每个节点都分为两部分,一个数据域,一个是指针域。

第0个结点称为头结点,它存放有第一个结点的首地址,没有数据,只是一个指针变量。以下的每个结点都分为两个域,一个是数据域,存放各种实际的数据,如学号 num,姓名 name,性别 sex 和成绩score 等。另一个域为指针域,存放下一结点的首地址。链表中的每一个结点都是同一种结构类型。

首结点:存放第一个有效数据的结点
头结点:在单链表的第一个结点之前附设一个结点,它没有直接前驱,称之为头结点,头结点的数据域可以不存储任何信息(一般不使用,可以用其记录链表结点个数),指针域指向第一个结点(首结点)的地址。头结点的作用是使所有链表(包括空表)的头指针非空
头指针:指向头结点的指针,访问链表的关键
尾结点:存放最后一个有效数据的结点
尾指针:指向尾节点的指针

链表就如同火车,head指向第一个元素:第一个元素又指向第二个元素,直到最后一个元素,该元素不再指向其它元素,它称为“表尾”,它的地址部分放一个“NULL”(表示“空地址”),链表到此结束。

以下有借鉴

空链表

--->NULL
head

有n个结点的链表

--->[p1]--->[p2] ... --->[pn]--->NULL
head p1->next p2->next ... pn->next

创建链表

一般创建链表都用typedef struct,这样定义结构体变量时,可以直接用LinkList  *a,定义结构体类型变量。

typedef struct stduent{
   int score;
   struct student *next;
}Linklist;

初始化链表(n为链表结点个数)

Linklist *creat(int n){
   linkList *head, *node, *end; //定义头结点,普通结点,尾结点;
   head = (LinkList*)malloc(sizeof(LinkList)); //分配地址;
   end = head;
   for(int i = 0; i < n; i++){
      node = (LinkList*)malloc(sizeof(LinkList));
      scanf("%d", &node->score);
      end->next = node;
      end = node;
   }
   end->next = NULL; //结束创建;
   return head;
}

修改链表结点值

void change(LinkList *list,int n){ //n为第n个节点
   LinkList *t = list;
   int i = 0;
   while (i < n && t != NULL){
      t = t->next;
      i++;
   }
   if(t != NULL){
      puts(“输入要修改的值”);
      scanf("%d",&t->score);
   }
   else{
   puts(“结点不存在”);
   }
}

删除链表结点

删除链表的元素也就是把前结点的指针域越过要删除的结点指向下下个结点。

即:p->next = q->next;然后放出q结点的空间,即free(q)。
 

void delet(LinkList *list, int n){
   LinkList *t = list, *in;
   int i;
   while(i < n && t != NULL){
      in = t;
      t = t->next;
      i++;
   }
   if(t != NULL){
      in->next = t->next;
      free(t);
      else{ 
         puts(“结点不存在”);
   }
}

插入链表结点

插入结点是用插入前结点的指针域链接上插入结点的数据域,再把插入结点的指针域链接上插入后结点的数据域。插入结点也就是:e->next = head->next; head->next = e。

增加链表结点

用到了两个结构体指针和一个int数据。

void insert(LinkList *list, int n){
   LinkList *t - list, *in;
   int i = 0;
   while (i< n && t != NULL){
      t = t->next;
      i++;
   if (t != NULL){
      in = (LinkList*)malloc(sizeof(LinkList));
      puts("输入要插入的值");
      scanf("%d", &in->score);
      in->next = t->next; //填充in节点的指针域,也就是监把in的指针域指向下一个结点;
      t->next = in; //填结点的指针域,把t的指针域重新指向in;
   else{
      puts("结点不存在");
   }
}

输出链表

边输出边遍历。

while(h->next != NULL){
   h = h->next;
   printf("%d", h->score);
}

声明:该文观点仅代表作者本人,必看呐发布平台,仅提供信息存储空间服务。