天天看點
傳回

【資料結構】連結清單(C++)

連結清單

連結清單是線性表的鍊式存儲方式，邏輯上相鄰的資料在計算機中的記憶體位置不必須相鄰，給每一個元素 加一個指針域，指向下一個元素的位置。

如下圖所示:

【資料結構】連結清單(C++)

連結清單的核心要素：

  • 每個結點由資料域和指針域組成
  • 指針域指向下一個結點的記憶體位址

單連結清單

連結清單的結點均單項指向下一個結點，形成一條單項通路的資料鍊。

【資料結構】連結清單(C++)

相關接口實作 

typedef int DataType;

//結構體定義
typedef struct LinkNode
{
  DataType data;
  struct LinkNode* next;
}LinkNode,LinkList;//LinkList為頭結點
//初始化就是初始化頭結點
bool initLinkList(LinkList*& linklist)
{
  linklist = new LinkList;
  if (!linklist)
  {
    return false;
  }
  linklist->next = NULL;
  return true;
}
//前插法
bool pushFront(LinkList*& L, LinkNode* node)
{
  if (!L || !node)
  {
    return false;
  }
  node->next = L->next;//頭結點預設的next是NULL
  L->next = node;//與頭結點相連接配接
  return true;
}
//尾插法
bool pushBack(LinkList*& L, LinkNode* node)
{
  if (!L || !node)
  {
    return false;
  }
  
  LinkNode* tempnode = L;//從頭結點開始
  //通過循環找到最後一個結點
  while (tempnode->next)//直到循環到下一個結點為空，就進不去這個循環了，此時的tempnode就是最後一個結點
  {
    tempnode = tempnode->next;
  }
  //注意:如果隻有一個頭結點會直接到達這裡。因為頭結點的next指向空
  tempnode->next = node;
  node->next = NULL;
  return true;
}
//指定位置插入
bool insertLinkList(LinkList*& L,int index,DataType num)
{
  if (!L || index <= 0)
  {
    return false;
  }
  if (index == 1)
  {
    LinkNode* newnode = new LinkNode;
    newnode->data = num;
    pushFront(L, newnode);
    return true;
  }

  //循環周遊尋找
  int count = 0;
  LinkList* p, * newNode;
  p = L;

  while (p && count < index-1)//count<index-1條件控制，最後執行完這段代碼，count就是index前一個位置
  {
    //p最後就是要插入位置的前一個結點
    p = p->next;
    count++;
  }

  //與新的結點連結
  newNode = new LinkNode;//生成新的結點
  newNode->data = num;
  newNode->next = p->next;  
  p->next = newNode;
  return true;

}
//通路指定位置的元素 
bool getElems(LinkList*& L, int postion,int& e)
{
  if (!L || postion <= 0 || !L->next)
  {
    return false;
  }
  //為什麼這樣寫因為本連結清單頭結點無資料
  int count = 0;
  LinkList* tempnode = L;
  while (count < postion  && tempnode)
  {
    count++;
    tempnode = tempnode->next;
  }
  //錯誤的postion必定導緻tempnode為null
  if (!tempnode)
  {
    return false;
  }
  e = tempnode->data;
  return true;
}
//查找元素-按值
bool findElems(LinkList*& L, int e,int &index)
{
  if (!L || !L->next)
  {
    return false;
  }
  LinkList* tempnode = L;
  int count = 0;
  while (tempnode && tempnode->data != e)
  {
    tempnode = tempnode->next;
    count++;
  }
  //一遍下來沒查到，tempnode為NULL
  if (!tempnode)
  {
    return false;
  }
  
  index = count;
  return true;

}
//删除元素-下标
bool deleteElems(LinkList*& L, int index)
{
  if (!L || !L->next || index <= 0)
  {
    return false;
  }
  int count = 0;                                                    
  LinkNode* tempnode = L;
  //補充:也能再建立個接口來周遊連結清單統計結點數
  while (tempnode && count != index-1)//找到要删除結點的前一個結點
  {
    count++;
    tempnode = tempnode->next;
  }
  if (!tempnode->next)//找到的前一個結點是最後一個結點，說明index的下标過大，reture false
  {
    return false;
  }
  //成功找到
  LinkNode* removeNode = tempnode->next;
  tempnode->next = removeNode->next;
  delete removeNode;
  return true;
}
//銷毀連結清單
bool destoryList(LinkList*& L)
{
  LinkList* tempnode = L;
  while (tempnode)
  {
    L = L->next;
    delete tempnode;
    tempnode = L;//不斷的往下取都結點，依次釋放。
  }
  return true;
}

//列印輸出表中元素
void printLinkList(LinkList*& L)
{
  LinkNode* p = NULL;//用它拿到第一個結點
  if (!L)
  {
    return;
  }
  p = L->next;
  while (p)
  {
    cout << p->data <<" ";
    p = p->next;//通路下一個結點 
  }
  cout << endl;
}

循環連結清單

在單連結清單的基礎上讓最後一個結點指向第一個結點。

相關接口實作 

typedef int DataType;

//循環連結清單
typedef struct LinkNode
{
  DataType data;
  struct LinkNode* next;
}LinkNode, LinkList;
//初始化
bool inintLinkList(LinkList*& L)
{
  L = new LinkList;
  if (!L)
  {
    return false;
  }
  L->next = L;
  L->data = -1;
  return true;
}
//尾插法
bool pushBack(LinkList*& L,LinkNode *node)
{
  if (!L || !node)
  {
    return false;
  }
  //頭結點的指針域指針指向自己的時候就是空的循環連結清單，本頭結點不存數值
  if (L == L->next)
  {
    L->next = node;
    node->next = L;
  }
//非空的循壞連結清單
  LinkNode* tempnode = NULL;
  tempnode = L->next;
  while (tempnode->next != L)//找到最後一個結點
  {
    tempnode = tempnode->next;
  }
  tempnode->next = node;
  node->next = L;
  return true;
}
//頭插法
bool pushFront(LinkList*& L, LinkNode* node)
{
  if (!L || !node)
  {
    return false;
  }
  LinkNode* tempnode = L->next;
  L->next = node;
  node->next = tempnode;
  return false;
}
//輸出
void printList(LinkNode*& L)
{
  if (!L || L == L->next)
  {
    return;
  }



  LinkNode* tempnode = NULL;
  tempnode = L->next;
  while (tempnode != L)
  {
    cout << tempnode->data << " ";
    tempnode = tempnode->next;
  }
  cout << endl;
}

約瑟夫環問題

定一個數，從頭開始依次報數，報道這個數的就delete,直到求出最後一個出局的編号是多少。

//約瑟夫環問題
//注意i 和 j的作用  
bool Joseph(LinkNode*& L,int val)
{

    LinkNode* p, * q;//p負責向下指，q負責與臨時儲存要删除的結點，連結到後面的結點
    p = L;

    if (!L || p->next == L)
    {
        return false;
    }
    if (val < 1)
    {
        return false;
    }
    
    int i = 0;//定位要删除結點的位置
    //通過i和j的不斷增加，來定位位置
    //j是不斷疊加的
    int j = 0;
    int times = 0;
    int num = 0;//記錄最後一個出圈者的編号
    //該結點的值即為編号。
    do
    {
        //i為第一個要删除的結點位置
        i += val;
        
        //查找第i個結點，p指向該結點的上一個結點
        //能夠進行這裡，這個while循環的條件肯定是成立的
        //作用就是通過對j增加，然後與i進行比較。
        //注意是從頭開始，頭結點不存數值
        //每次周遊都能周遊到頭結點
        //如果頭結點存數值的話，那j的條件就得修改
        //随便想了一下，應該是j < i
        while (p->next)
        {
            //這兩個判斷的位置要注意一下
            if (p->next != L)
            {
                j++;
            }
            if (j >= i)
            {
                break;
            }
            p = p->next;
        }
        times++;//進行了幾輪
        q = p->next;
        num = q->data;

        //重新連接配接起來
        p->next = q->next;
        delete q;//釋放被删除結點空間
        printList(L);   
    } while (L->next != L);//删到最後就剩自己指向自己了
    cout << "最後被删除的結點位置是第" << num << "個" << endl;
    return true;
}

雙向連結清單

在單連結清單的基礎上添加一個指向前一個結點的指針。

相關接口實作 

typedef int dataType;

typedef struct doubleNode
{
  dataType data;
  struct doubleNode* prev;
  struct doubleNode* next;
}LinkNode,LinkList;

//初始化
bool initLinkList(LinkList*& L)
{
  L = new LinkList;
  if (!L)
  {
    return false;
  }
  L->next = NULL;
  L->prev = NULL;
  L->data = -1;
  return true;
}
//尾插法
bool pushBack(LinkList*& L,LinkNode*& node)
{
  if (!L || !node)
  {
    return false;
  }
  LinkList* tempnode = NULL;
  tempnode = L;
  while (tempnode->next)
  {
    tempnode = tempnode->next;
  }
  //第一次進行尾插就直接來到這裡
  tempnode->next = node;
  node->prev = tempnode;
  node->next = NULL;
  return true;
}
//前插
bool pushFront(LinkList* &L, LinkNode* &node)
{
  if (!L || !node)
  {
    return false;
  }
  
  if (L->next == NULL)
  {
    L->next = node;
    node->next = NULL;
    node->prev = L;
  }
  else
  {
    LinkNode* tempnode = NULL;
    tempnode = L->next;
    L->next = node;
    node->prev = L;
    node->next = tempnode;
    tempnode->prev = node;
  }

  return true;
}


//列印輸出
void printLinkList(LinkList*& L)
{
  if (!L || !L->next)
  {
    return ;
  }
  LinkList* tempnode = NULL;
  tempnode = L->next;
  while (tempnode)
  {
    cout << tempnode->data << " ";
    tempnode = tempnode->next;
  }
  cout << endl;
}
//指定位置插入元素
bool insertLinkList(LinkList*& L,int index,int num)
{
  if (!L || !L->next || index < 1)
  {
    return false;
  }

  int  count = 1;
  LinkNode* tempnode = NULL;
  tempnode = L->next;
  while (tempnode)
  {
    if (count == index)
    {
      break;
    }
    tempnode = tempnode->next;
    count++;
  }
  if (!tempnode)
  {
    return false;
  }
  LinkNode* newnode = new LinkNode;
  newnode->data = num;
  LinkNode* tempnodeII = tempnode->prev;
  tempnodeII->next = newnode;
  newnode->prev = tempnodeII;
  newnode->next = tempnode;
  tempnode->prev = newnode;
  return true;
}

//删除指定位置元素
bool deleteLinkList(LinkList*& L, int index)
{
  if (!L || !L->next || index < 1)
  {
    return false;
  }
  
  int count = 1;
  LinkNode* tempnode = NULL;
  tempnode = L->next;
  //同在指定位置插入元素,先定位到這個結點
  while (tempnode)
  {
    if (index == count)
    {
      break;
    }
    count++;
    tempnode = tempnode->next;
  }
  if (!tempnode->next)
  {
    tempnode->prev->next = NULL;
    delete tempnode;
  }
  else
  {
    tempnode->prev->next = tempnode->next;
    tempnode->next->prev = tempnode->prev;
    delete tempnode;
  }
  return true;
}

//得到某個位置的值
bool getElems(LinkList*& L, int index, int& e)
{
  if (!L || !L->next || index < 1)
  {
    return false;
  }
  int  count = 1;
  LinkNode* tempnode = NULL;
  tempnode = L->next;
  while (tempnode)
  {
    if (count == index)
    {
      break;
    }
    tempnode = tempnode->next;
    count++;
  }
  if (!tempnode)
  {
    return false;
  }
  e = tempnode->data;
  return true;
}
//銷毀
void  destoryLinkList(LinkList*& L)
{
  LinkNode* tempnode = NULL;
  tempnode = L;
  //找到下一個，删除前一個、從前往後删
  while (tempnode)
  {
    //L移動到真正的第一個結點
    L = L->next;
    //删除他原來的
    delete tempnode;

    tempnode = L;
  }
}

實際應用

Linux核心共享雙向連結清單

在 linux 核心中，有大量的資料結構需要用到雙向連結清單，例如程序、檔案、子產品、頁面等。

若采用雙向連結清單的傳統實作方式，需要為這些資料結構維護各自的連結清單，并且為每個連結清單都

要設計插入、删除等操作函數。因為用來維持連結清單的 next 和 prev 指針指向對應類型的對

象，是以一種資料結構的連結清單操作函數不能用于操作其它資料結構的連結清單。

有沒有一種方式讓多個連結清單共享同一套連結清單操作呢？

——将結點中的指針域和資料域分離。

【資料結構】連結清單(C++)

例如:

typedef struct LinkNode
{
  struct LinkNode* next;
  struct LinkNode* prev;
}LinkNode;

typedef struct
{
  int fd;
  time_t timeout;
  LinkNode node;//挂件
}ConnTimeOut;

特殊通路：

——取到結構體中挂件的的偏移量，得到結構體的位址，然後進行通路。

ConnTimeOut* ct = new ConnTimeOut;
ct->fd = 3;
LinkNode* p = &(ct->node);
int offset = offsetof(ConnTimeOut, node);//node成員在記憶體中距結構體起始位置16個位元組
ConnTimeOut* tmp = (ConnTimeOut*)((size_t)p - offset);
cout <<tmp->fd;      
//相關接口示例
bool initLinkNode(LinkNode& L)
{
  
  L.next = NULL;
  L.prev = NULL;

  return true;
}
int main(void)
{
  ConnTimeOut* cL = NULL;
  //初始化一個空的雙向連結清單
  cL = new ConnTimeOut;
  cL->fd = -1;
  initLinkNode(cL->node);

  return 0;
}
怎麼個共享法呢?

重新解釋：

将一個結點中的指針域剝離出來，建立一個新的結構體，來存放這個指針域，也就是說結構體嵌套。不同的結點(結構體資料内容不同，但是都有這個剝離出來的指針域。)，使用同一個接口進行操作，靠的就是他們中相同的"指針域"結構體，就是對這個結構體中的"指針域結構體"進行操作。

例如：

不同的結構體，但是但是他們都有上面LinkNode node這個挂件，那麼他們就共用同一個初始化指針指向的函數。

連結清單 資料結構 c++ 結點 頭結點
上一篇: Wayland協定解析 二 Wayland中的資料結構解析
下一篇: Wayland 協定解析工具代碼（Qt 将wayland協定轉換為C++接口，我把函數功能也識别進去，更友善通過生成的檔案閱讀wayland協定）

繼續閱讀