操作系统常用到的数据结构-----------双链表

只看该作者 · 2019-6-29 19:36

//节点初始化
void NodeInit(tNode *node)
{
node->nextnode = node;
node->prenode = node;
}

只看该作者 · 2019-6-29 19:36

//链表初始化
void ListInit(tList *list)
{
list->headNode.nextnode = &(list->headNode);
list->headNode.prenode = &(list->headNode);
list->nodecount = 0;
}

只看该作者 · 2019-6-29 19:36

//返回链表节点数量
uint32_t ListCount(tList *list)
{
return list->nodecount;
}

只看该作者 · 2019-6-29 19:37

//返回链表的首个节点
tNode *ListFirst(tList *list)
{
tNode *node = (tNode *)0;
if(list->nodecount!=0)
{
node = list->headNode.nextnode;
}
return node;
}

只看该作者 · 2019-6-29 19:39

//返回链表的最后一个节点
tNode *ListLast(tList *list)
{
  tNode *node = (tNode *)0;
if(list->nodecount!=0)
{
   node = list->headNode.prenode;
}
  return node;
}

只看该作者 · 2019-6-29 19:39

//返回链表指定节点的前一节点
// list:查询链表
// node：参考节点
tNode *ListPre(tList *list,tNode *node)
{
  if(node->prenode == node)
{
   return (tNode *)0;
}
else
{
   return node->prenode;
}
}

只看该作者 · 2019-6-29 19:42

//返回链表中指定节点的后一个节点
// list:查询链表
// node：参考节点
tNode *ListNext(tList *list,tNode *node)
{
  if(node->nextnode ==node)
{
   return (tNode *)0;
}
else
{
   return node->nextnode;
}
}

只看该作者 · 2019-6-29 19:42

//删除链表中的所有节点
//list：需要删除的链表
void ListRemoveAll(tList *list)
{
int i;
tNode *nextNode;
//遍历所有节点
nextNode = list->headNode.nextnode;
for(i=list->nodecount;i!=0;i--)
{
//记录当前节点和下以节点
tNode *currentNode;
currentNode = nextNode;
nextNode = nextNode->nextnode;
//重置节点信息
currentNode->nextnode = currentNode;
currentNode->prenode = currentNode;
}
list->headNode.nextnode = &(list->headNode);
list->headNode.prenode = &(list->headNode);
list->nodecount = 0;
}

只看该作者 · 2019-6-29 19:43

//将指定节点添加到链表的头部
//list:待插入的链表
//node:待插入的节点
void ListAddFirst(tList *list,tNode *node)
{

node->prenode = &(list->headNode);
node->nextnode = list->headNode.nextnode;

list->headNode.nextnode->prenode = node;
list->headNode.nextnode = node;

list->nodecount++;
}

只看该作者 · 2019-6-29 21:25

//将指定节点添加到链表尾部
//list：待插入的链表
//node：待插入的节点
void ListAddLast(tList *list,tNode *node)
{
node->prenode = list->headNode.prenode;
node->nextnode = &(list->headNode);

list->headNode.prenode->nextnode = node;
list->headNode.prenode = node;
list->nodecount++;
}

只看该作者 · 2019-6-29 21:26

//移除链表中的第一个节点
//list：要移除的链表
//返回值：如果链表为空，返回0，否则返回第一个节点
tNode *tListRemoveFist(tList *list)
{
tNode *node = (tNode *)0;
if(list->nodecount != 0)
{
node =list->headNode.nextnode;

node->nextnode->prenode = &(list->headNode);
list->headNode.nextnode = node->nextnode;
list->nodecount--;
}
return node;
}

只看该作者 · 2019-6-29 21:26

//在指定节点后插入节点
//list：需要插入的链表
//afternode：参考节点
//insertnode:待插入的节点
void ListInsertAfter(tList *list,tNode *afternode,tNode *insertnode)
{
   insertnode->prenode = afternode;
      insertnode->nextnode = afternode->nextnode;
      afternode->nextnode = insertnode;
      afternode->nextnode->prenode =insertnode;
      list->nodecount++;
}

只看该作者 · 2019-6-29 21:26

//在指定节前插入节点
//list：需要插入的链表
//beforenode：参考节点
//insertnode:待插入的节点
void ListInsertBefore(tList *list,tNode *beforenode,tNode *insertnode)
{
   insertnode->prenode = beforenode->prenode;
   insertnode->nextnode = beforenode;
   beforenode->prenode = insertnode;
   beforenode->prenode->nextnode = insertnode;
   list->nodecount++;
}

只看该作者 · 2019-6-29 21:27

//将指定节点从链表中移除
//list:待移除的链表
//node：待移除的节点
void ListRemoveNode(tList *list,tNode *node)
{
node->prenode->nextnode = node->nextnode;
node->nextnode->prenode = node->prenode;
list->nodecount--;
}