【C++】链表反转逆序|建立、删除、修改、插入|linux内核链表与普通链表_linux 中内核 list 删除元素 c++

目录

C++实现链表逆序

链表的建立、删除、修改、插入 

linux内核链表与普通链表

---

C++实现链表逆序

实现链表逆序，首先要有一个链表，下面是链表的结构体：

typedef struct listnode {
	int data;
	struct listnode* next;
}listnode , *list;

实现思路：

  1. 若链表为空或只有一个元素，则直接返回；

  2. 设置两个前后相邻的指针p,q. 将p所指向的节点作为q指向节点的后继；

  3. 重复2,直到q==NULL

  4. 调整链表头和链表尾

示例：以逆序1->2->3->4为例，图示如下

完整实现代码：

#include<iostream>
using namespace std;
 
typedef struct listnode {
	int data;
	struct listnode* next;
}listnode , *list;
 
void print(list head);
list reverse(list head);
list fill(list head); //默认用1-10填充链表
 
int main() 
{
	//初始化链表头节点
	listnode* head;
	head = (listnode*)malloc(sizeof(listnode));
	head->next = NULL;
	head->data = -1;
	list linklist = fill(head);
	print(head);
	reverse(head);
	print(head);
	getchar();
	return 0;
}
 
list reverse(list head)
{
	if (head->next == NULL || head->next->next == NULL)
	{
		return head;   /*链表为空或只有一个元素则直接返回*/
	}
 
	list t = NULL;
	list p = head->next;
	list q = head->next->next;
	while (q != NULL)
	{
		t = q->next;
		q->next = p;
		p = q;
		q = t;
	}
 
	/*此时q指向原始链表最后一个元素，也是逆转后的链表的表头元素*/
	head->next->next = NULL;  /*设置链表尾*/
	head->next = p;           /*调整链表头*/
	return head;
}
 
list fill(list head)
{	
	listnode *p, *q;
	p = head;
	for (int i = 0; i < 10; i++) 
	{
		q = (listnode*)malloc(sizeof(listnode));
		q->data = i + 1;
		q->next = NULL;
		p->next = q;
		p = q;
	}
	return head;
}
 
void print(list head)
{
	list p;
	p = head->next;
	while(p != NULL)
	{
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
}

执行结果：

void print(list head) 这个函数应该会少输出一个节点，而且如果head为空的话函数会崩溃？？

原文：C++ ——实现链表反转逆序_bingoCoder的博客-CSDN博客_链表逆序c++

链表的建立、删除、修改、插入 

在建立链表时，在单片机中要注意mallco函数使用的条件，在编译器上要记得分配足够的堆，否则mallco失败返回NULL，则整个链表的信息将无法读取。

求助一道C语言关于链表的问题，答对还有追加分数

已知学生基本信息由学号(长整型)、姓名(字符数组)、性别(字符型)、年龄(整型)组成。要求建立一个结点按学号顺序存储学生信息的单向链表，并实现依据学号对链表的添加、修改、删除和检索功能。添加新结点后，应继续保持结点按学号顺序的链接方式。

答对还有追加分数！！

     

最佳答案

struct _tagStudent
{
  long lNo; //=========学号
  char szName[20]; //==姓名
  char cSex; //========性别
  int nAge; //=========年龄
};

//定义Student结构
typedef struct _tagStudent Student;

struct _tagNode
{
  struct _tagNode* pNext;//=======下一个节点
  Student *pStudent; //===========本节点的学生信息
};

//定义Node结构（即一个节点）
typedef struct _tagNode Node;


//插入一个新的学生
//参数：
//Node* students 学生链表的头节点
//Student* newStudent 被插入的学生信息
//返回：
//新链表的头节点
Node* Insert(Node* students, Student* newStudent)
{
  Node* pCurNode;//当前节点
  Node* pNextNode;//下一节点
  Node* pPrevNode;//上一节点
  Node* pNode;

  Node* pNodeHead = students;//头节点

  if(pNodeHead == NULL)//尚未有节点，创建一个头节点
  {
    pNodeHead = (Node*)malloc(sizeof(Node));
    pNodeHead->pNext = NULL; //后一项为NULL;
    pNodeHead->pStudent = newStudent;

    return pNodeHead;
  }
  
  pCurNode = pNodeHead;
  pPrevNode = NULL;
  while(1)
  {
    if(newStudent->lNo <= pNode->pStudent->lNo)//按学号升序插入,插到当前节点前
    {
      pNode = (Node*)malloc(sizeof(Node));
      pNode->pStudent = newStudent;
      pNode->pNext = pCurNode;

      if(pPrevNode == NULL)//如果上一节点为NULL，表示插入链表头
         pNodeHead = pNode;//链表头指向新节点
      else
         pPrevNode->pNext = pNode;
      break;
    } 

    pNextNode = pCurNode->pNext;

    if(pNextNode == NULL)//如果当前节点是末节点,插入链表末尾
    {
      pNode = (Node*)malloc(sizeof(Node));
      pNode->pStudent = newStudent;
      pNode->pNext = NULL;

      pCurNode->pNext = pNode;

      break;
    }

    pPrevNode = pCurNode;
    pCurNode = pNextNode;
  }

  return pNodeHead;//返回新的头节点
}

//在学生链表中查找指定的学生
//参数：
//Node* strudent 学生链表的头节点
//Student* searchStudent 被查找的学生
//返回：
//被查学生所在节点
Node* FindNode(Node* students, Student* searchStudent)
{
  Node* pNode = students;

  while(pNode != NULL)
  {
    if(pNode->pStudent == searchStudent)
      return pNode;
    
    pNode = pNode->pNext;
  }

  return NULL;
}

//根据学号查找学生信息
//参数：
//Node* students 学生链表的头节点
//long nNo 被查学生的学号
//返回：
//被查学生的信息
Student* FindStudent(Node* students, long lNo)
{
  Node* pNode = students;

  while(pNode != NULL)
  {
    if(pNode->pStudent->lNo == lNo)
      return pNode->pStudent;
    
    pNode = pNode->pNext;
  }

  return NULL;
}

//修改学生信息
//参数：
//Node* students 学生链表头节点
//Student* oldStudent 被修改的学生信息
//Student* newStudent 被修改后的学生信息(即用newStudent替换oldStudent)
//返回：
// true -- 成功，false -- 失败
bool Modify(Node* students, Student* oldStudent, Student* newStudent)
{
  //查找被修改学生所在节点
  Node* pNode = FindNode(students, oldStudent);

  if(pNode == NULL)//没有找到返回false
    return false;

  //替换成新的学生信息
  pNode->pStudent = newStudent;

  return true;
}

//获取指定节点的上一个节点
//参数：
//Node* students 学生链表的头节点
//Node* pNode 指定节点
//返回：
//指定节点的上一个节点
Node* GetPrevNode(Node* students, Node* pNode)
{
  Node* pCurNode = students;

  if(pNode == students)//指定节点是头节点，返回上一节点NULL
    return NULL;

  while(pCurNode != NULL)
  {
    if(pNode == pCurNode->pNext)
      return pCurNode;

    pCurNode = pCurNode->pNext;
  }

  return NULL;//没有找到
}

//删除指定的学生信息
//参数：
//Node* students 学生链表头节点
//Student* pStudent 将被删除的学生
//返回：
//删除学生后的学生链表的头节点，如果为NULL，表示链表中已没有任何学生
Node* Delete(Node* students, Student* pStudent)
{
  Node* pNodeHead = students;
  Node* pPrevNode;//上一节点

  //查找被修改学生所在节点
  Node* pNode = FindNode(students, pStudent);

  if(pNode == NULL)//没有找到返回原先的头节点
    return pNodeHead;

  if(pNode == pNodeHead)//如果该学生是头节点
  {
    pNodeHead = pNodeHead->pNext;
  }
  else
  {
    pPrevNode = GetPrevNode(students, pNode);
    
    pPrevNode->pNext = pNode->pNext;
  }

  free(pNode);//释放该节点(没有释放节点中的学生信息，应另外释放)

  return pNodeHead;//返回头节点
}


好了！以上已经有了基本的学生链表操作功能了。只要通过调用上面的几个函数就可以实现学生信息的管理和应用。

例如：
//参考样例====
//1。机器模拟生成20个学生，学号随机生成
//2。修改原学号为100的学生，替换为一个新的学号为150的学生
//3。删除学号为200的学生
void main()
{
  int i = 0;
  Node* students = NULL;//初始化学生链表头节点为空
  Student* newStudent;
  Student* oldStudent;
  Node* pNode;

  //1。机器模拟生成20个学生，学号随机生成

  //随机产生20个学生，学号在0--1000之间，按照升序插入到学生链表中
  for(i = 0; i < 20; i++)
  {
    newStudent = (Student*)malloc(sizeof(Student));
    newStudent->lNo = rand() * 1000;//rand()为生成一个0到1的随机数，随机函数可以用别的替代，这里只是用于说明问题的
    
    students = Insert(students, newStudent);
  }

  //遍历输出学生信息,用于检验学生链表是否正确，包括学生个数，学号是否排序正确等
  i = 0;
  pNode = students;
  while(pNode != NULL)
  {
    printf("学生%d : 学号 -- %l\n", ++i, pNode->pStudent->lNo); 
    pNode = pNode->pNext;
  }
  
  //2。修改原学号为100的学生，替换为一个新的学号为150的学生
  oldStudent = FindStudent(students, 100);

  newStudent = (Student*)malloc(sizeof(Student));
  newStudent->lNo = 150;

  Modify(students, oldStudent, newStudent);


  //3。删除学号为200的学生

  //查找学号为200的学生
  oldStudent = FindStudent(students, 200);

  if(oldStudent != NULL)//如果找到
  {
    students = Delete(students, oldStudent);

    free(oldStudent);//释放学生信息
  }

  //最后结束程序前，最好要把所有的学生信息释放掉
  //。。。
}

linux内核链表与普通链表

 1、在Linux内核中经常能够看到 struct list_head 这样的一个结构体，这个就是内核中的一个链表，内核链表

struct list_head {
struct list_head *next, *prev;
};

这个结构体中只有两个指向链表结构体的指针，分为前向指针和后向指针，因为可以用来构建一个双向链表，但是这个链表的用法与我们普通的链表的用法不一样，

我们的一般的链表结构体中都会包含两部分：一个是指针（前向指针和后向指针）部分，还有就是有效数据部分。将我们链表需要存放的数据放在结构体中的有效数据

区中，通过两个节点分别指向上一个节点和下一个节点。这是一般的链表的使用方法。

(1)但是内核链表的结构体中只有两个指针，并没有有效数据区，所以内核链表的用法和我们的普通链表的用法是不一样的，我们使用内核链表的方法就是：

自己建立一个结构体去包含这个内核链表，将整个结构体作为一个链表的节点，然后使用内置的链表的前向指针指向下一个结构体中内置的链表，使用内置的链表的

后向指针指向上一个结构体中内置的链表。

例如：

struct A{                     

    struct list_head list;

    .........

};

struct A a;

struct A b;

struct A c;

a.list.next = b.list;

b.list.prev = a.list, b.list.next = c.list;

c.list.prev = b.list;

2、内核链表相关的函数和宏定义

(1)内核链表的初始化

    #define LIST_HEAD_INIT(name) { &(name), &(name) }

     #define LIST_HEAD(name)  struct list_head name = LIST_HEAD_INIT(name)

    static inline void INIT_LIST_HEAD(struct list_head *list)
    {
          list->next = list;
          list->prev = list;
    }

由上面可以知道，初始化就是将list_head中的两个指针都指向自己本身。初始化一个内核链表的方法：

(1.1) 定义一个内核链表并进行初始化可以直接调用宏： LIST_HEAD(list);      展开之后：   struct list_head list = { &(list), &(list) }

(1.2) 也可以定义和初始化分开， struct list_head list;    INIT_LIST_HEAD(&list);

  

(2)内核链表的常用函数

(2.1) list_add(struct list_head *new, struct list_head *head);         将节点插入到链表头部

        list_add_tail(struct list_head *new, struct list_head *head);   将节点插入到链表尾部

(2.2) list_del(struct list_head *entry);    删除一个节点，并将他的指针清除0

        list_del_init(struct list_head *entry);   删除一个节点，并将他的指针再次指向自己本身

(2.3) list_replace(struct list_head *old, struct list_head *new);   替换链表中的某个节点， old需要被替换的节点， new新的节点

        list_replace_init(struct list_head *old, struct list_head *new);   和上面的区别在于，把替换之后的老的节点进行初始化

(2.4) int list_is_last(const struct list_head *list, const struct list_head *head);  测试一个节点是否为链表头节点，list是要测试的节点，head是一个链表头

        int list_empty(const struct list_head *head);   测试链表是否为空

内核链表与普通链表 - 涛少& - 博客园

2.内核中链表的创建、挂接与遍历_wangdapao12138的博客-CSDN博客