Linux内核中的队列链表代表什么意思

*** 作系统内核, 如同其他程序, 常常需要维护数据结构的列表. 有时, Linux 内核已经同时有几个列表实现. 为减少复制代码的数量, 内核开发者已经创建了一个标准环形的, 双链表鼓励需要 *** 作列表的人使用这个设施.

当使用链表接口时, 你应当一直记住列表函数不做加锁. 如果你的驱动可能试图对同一个列表并发 *** 作, 你有责任实现一个加锁方案. 可选项( 破坏的列表结构, 数据丢失, 内核崩溃) 肯定是难以诊断的.

为使用列表机制, 你的驱动必须包含文件 <linux/list.h>. 这个文件定义了一个简单的类型 list_head 结构:

struct list_head { struct list_head *next, *prev}

真实代码中使用的链表几乎是不变地由几个结构类型组成, 每一个描述一个链表中的入口项. 为在你的代码中使用 Linux 列表, 你只需要嵌入一个 list_head 在构成这个链表的结构里面. 假设, 如果你的驱动维护一个列表, 它的声明可能看起来象这样:

可以把链表设计成循环链表，用冒泡排序

在排序前设计一个交换标记，如在循环过程中有交换，则修改这个标记变量，如果在一次循环（当前节点为刚开始时节点，表示循环了一次）中，交换标记没有被修改，则表明该数列已排好序。

现在给一个双向循环链表的排序程序给你，该程序用了双向冒泡排序（也就是鸡尾酒排序法），希望对你有帮助

双向链表我用的鸡尾酒排序,也就是双向冒泡排序

#include<stdio.h>

#define LEN sizeof(struct list)

struct list//双向链表有两个指针域，一个指向前节点，一个指向后继节点

{struct list *lp //lp为前节点指针，rp为后继节点指针

int x

struct list *rp

}

int n

struct list *creat(void)

{struct list *head

struct list *p1,*p2 //两个节点指针，p1是当前新建节点指针，p2为p1的前一个节点

n=0

p1=p2=(struct list*)malloc(LEN)//申请内存空间

scanf("%d",&p1->x)

head=NULL //先把头指针设置为空

while(p1->x!=0)

{n=n+1

if(n==1){p1->lp=NULLhead=p1} //把head指向链表的第一个节点并把首节点的lp设为NULL

else

{p1->lp=p2新建了一个节点，把它的lp指向前一个节点p2

p2->rp=p1}把前节点的rp指针指向刚建立的节点

p2=p1 进行迭代，p1变成下一个新节点的后继节点

p1=(struct list*)malloc(LEN)//每次新建节点都要向系统申请内存空间

scanf("%d",&p1->x)

}

p2->rp=NULL 把随后的节点后继指针设为空

return(head)

}

void print(struct list *head)

{struct list *p

printf("\nNow,Thess %d records are :\n",n)

p=head

if(head!=NULL)

do

{printf("%d ",p->x)

p=p->rp//这个是个迭代过程，把p的后继节点变成下一次要输出的节点

}while(p!=NULL)

}

void sort(struct list *head) //排序用的双向排序法，提高排序效率

{struct list *p,*bottom,*top

int f,temp

p=head

if(head!=NULL)

{ f=1

bottom=NULL //bottom和top为数列左右冒泡的边界节点

top=NULL

while(f==1) //f为交换标记，如果没交换则f没变就推出循环

{f=0

do

{

if(p->x >(p->rp)->x)

{temp=p->x

p->x=(p->rp)->x

(p->rp)->x=temp

f=1

}

p=p->rp

}while(p->rp!=top)

print(head)

top=p

if((f==0)||(top==bottom))break

f=0

do

{

if(p->x<(p->lp)->x)

{

temp=p->x

p->x=(p->lp)->x

(p->lp)->x=temp

f=1

}

p=p->lp

}while(p->lp!=bottom)

bottom=p

if(top==bottom)break

print(head)

}

}

}

void main() //所有的函数都做成全局函数，可以随时调用

{struct list *head

head=creat() //建立链表

print(head) //输出链表

sort(head) //排序

print(head) //输出链表

system("PAUSE")

}

//创建data型结构，为生成链表做准备

struct data

{

int value

data *next

}

//对链表进行排列的函数

void line(data *p,int n)

{ int temp,i,j

data *tp

for(i=0i<n-1i++)

for(j=0,tp=pj<n-i-1j++,tp=tp->next)

{ if(tp->value>tp->next->value)

{temp=tp->next->value

tp->next->value=tp->value

tp->value=temp

}

}

}

以上是冒泡法对链表排序的例子；

//输出答案的函数

void answer(data *p)

{ while(p!=NULL) {

cout<<p->value<<endl

p=p->next

}

}

以上是遍历链表的函数p是链表的头指针

---