windows内核驱动中的链表结构

windows内核驱动中的链表结构与数据结构中的链表结构在构造上有很大不同，以循环双链表为例

数据结构中的链表结构：数据就像集装箱，可以直接放置在火车上，而节点就像每节之间的挂接装置.

内核驱动中的链表结构:　数据就像车厢，自带挂接装置（节点）

1.链表结构体不同

数据结构中的链表结构，包含有节点和数据,

struct DataList{

　　DataType data;

　　struct DataList* next;

　　struct DataList* prev;

};

驱动中的链表结构，仅包含有节点，没有数据。

struct DriverList{

　　struct DriverList* next;

　　struct DriverList* prev;

};

2.数据结构中的数据，可以直接封装在链表结构体中; 而在驱动链表结构中，要将链表结构封装在数据中，　　

struct DataEntry{

　　struct DriverList node;

　　DataType data;

};

以下是示例代码

 1 #pragma once
 2 
 3 typedef struct List {
 4     struct List * next;
 5     struct List * prev;
 6 }List, *Plist;
 7 
 8 void initList(Plist head);
 9 bool isEmpty(Plist pHead);
10 void addFirst(Plist pHead, Plist pNewNode);
11 void addLast(Plist pHead, Plist pNewNode);
12 void traverse(Plist pHead, void (*pfun)(void *));
13 
14 void initList(Plist head)
15 {
16     head->next = head;
17     head->prev = head;
18 }
19 
20 
21 bool isEmpty(Plist pHead)
22 {
23     if (pHead->next == pHead || pHead->prev == pHead)
24         return true;
25     return false;
26 }
27 
28 void addFirst(Plist pHead, Plist pNewNode)
29 {
30     // list is not empty
31     if (pHead->next != pHead)
32     {
33         pHead->next->prev = pNewNode;
34         pNewNode->next = pHead->next;
35     }
36     else
37     {
38         pHead->prev = pNewNode;
39         pNewNode->next = pHead;
40     }
41     pHead->next = pNewNode;
42     pNewNode->prev = pHead;
43 }
44 
45 void addLast(Plist pHead, Plist pNewNode)
46 {
47     // list is not empty
48     if (pHead->next != pHead)
49     {
50         pNewNode->prev = pHead->prev;
51         pHead->prev->next = pNewNode;
52     }
53     else
54     {
55         pHead->next = pNewNode;
56         pNewNode->prev = pHead;
57     }
58     pHead->prev = pNewNode;
59     pNewNode->next = pHead;
60 }

List.h

 1 #include "stdafx.h"
 2 #include <cstdlib>
 3 #include <iostream>
 4 #include <cstring>
 5 #include "List.h"
 6 
 7 #define SIZE 20
 8 #define ARLEN 10
 9 
10 typedef struct Student {
11     List listEntry;
12     int age;
13     char name[SIZE];
14     double weight;
15 }Student, *Pstudent;
16 
17 using namespace std;
18 
19 void printStudent(Plist pHead);
20 
21 int main()
22 {
23     List head;
24     initList(&head);
25     Pstudent pStu[ARLEN];
26     for (int i = 0; i < ARLEN; i++)
27     {
28         pStu[i] = (Pstudent)malloc(sizeof(Student));
29         pStu[i]->age = i;
30         pStu[i]->weight = i*1.2;
31         sprintf_s(pStu[i]->name, "%s%d","student",i);
32         addLast(&head, &pStu[i]->listEntry);
33     }
34     printStudent(&head);
35 }
36 
37 void printStudent(Plist pHead)
38 {
39     Pstudent pStu;
40     Plist current = pHead->next;
41     while (current != pHead)
42     {
43         pStu = (Pstudent)(current);
44         cout << "stu->name = " << pStu->name << ", stu->age = " 
45             << pStu->age << ", stu->weight = " << pStu->weight << endl;
46         current = current->next;
47     }
48 }

main.c

output:

stu->name = student0, stu->age = 0, stu->weight = 0
stu->name = student1, stu->age = 1, stu->weight = 1.2
stu->name = student2, stu->age = 2, stu->weight = 2.4
stu->name = student3, stu->age = 3, stu->weight = 3.6
stu->name = student4, stu->age = 4, stu->weight = 4.8
stu->name = student5, stu->age = 5, stu->weight = 6
stu->name = student6, stu->age = 6, stu->weight = 7.2
stu->name = student7, stu->age = 7, stu->weight = 8.4
stu->name = student8, stu->age = 8, stu->weight = 9.6
stu->name = student9, stu->age = 9, stu->weight = 10.8
请按任意键继续. . .