資料結構體模版---循環單連結清單

#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

#include <assert.h>

//#define debug // 調試插樁資訊宏

///*////////////////////////////////////////////////////////////////////////////

///

/// 帶頭結點的單連結清單結構體

typedef int elemtype; // 自定義資料類型

//typedef struct cirlinklistnode* pcirlinklistnode; // 連結清單結點指針域

// 連結清單結點資料域

typedef struct cirlinklistnode

{

elemtype m_data; // 資料域

struct cirlinklistnode *m_next; // 指針域

}cirlinklistnode;

// 帶頭結點的單項連結清單

typedef struct cirlinklist

cirlinklistnode *m_head; // 連結清單頭結點

cirlinklistnode *m_tail; // 循環連結清單尾部

int m_length; // 單連結清單資料結點個數指針域

// this->m_head == this->m_tail->m_next; // 如果隻設尾結點要了解此等價關系

}cirlinklist;

/// 建立和初始化單連結清單

/// 開辟一個單連結清單資料結構，并初始化頭結點，然後将建立好的單連結清單指針傳回

/// cirlinklist* creatcirlinklist(void)

/// 初始化單連結清單

/// void initcirlinklist(cirlinklist *list)

///*///////////////////////////////////////////////////////////////////////////

/**

cirlinklist* creatcirlinklist(void)

參數

list : 指向一個連結清單指針，此處傳入表頭位址

傳回值

若成功傳回建立好的單連結清單的指針

功能

開辟一個單連結清單資料結構，并初始化頭結點，然後将建立好的單連結清單指針傳回

注意

使用createcirlinklist建立的單連結清單，需要用destroycirlinklist來銷毀

以免發生記憶體洩漏

cirlinklist* createcirlinklist(void)

cirlinklist *list = null;

if((list = (cirlinklist *)malloc(sizeof(cirlinklist))) == null) // 開辟單連結清單的空間

{ // 開辟失敗

fprintf(stderr, "not enough memory when create list...\n");

exit(exit_failure);

}

initcirlinklist(list); // 初始化單連結清單

return list;

}

void initcirlinklist(cirlinklist *list)

無

初始化單連結清單，執行以下操作

①開辟頭結點的空間 ②進行必要的初始化[頭結點的初始化和單連結清單結點數目的初始化]

使用initcirlinklist初始化的單連結清單(初始化時malloc了頭結點m_head的空間)

而使用用finitcirlinklist來進行後處理(後處理時free了頭結點的m_head空間)

void initcirlinklist(cirlinklist *list)

if((list->m_head = malloc(sizeof(cirlinklistnode))) == null) // 為頭結點開辟空間

fprintf(stderr, "not enough memory when malloc head...");

// 初始化頭結點資訊

list->m_head->m_next = list->m_head; // 初始化隻有頭結點[空循環連結清單的特征]

list->m_head->m_data = 0; // 資料元素個數為0

list->m_length = 0; // 資料元素個數為0

list->m_tail = list->m_head; // 尾指針指向頭結點

/// 銷毀以及後處理單連結清單

/// 銷毀用createcirlinklist建立的單連結清單

/// void destroycirlinklist(cirlinklist *list)

/// 後處理單連結清單，

/// void finitcirlinklist(cirlinklist *list)

/// 清空單連結清單中的所有元素

/// void clearcirlinklist(cirlinklist *list)

void destroycirlinklist(cirlinklist *list)

銷毀用createcirlinklist建立的單連結清單，執行以下操作

①清空單連結清單 ②釋放頭結點 ③釋放單連結清單

cirlinklist* destroycirlinklist(cirlinklist *list)

clearcirlinklist(list); // 清空連結清單

finitcirlinklist(list); // 銷毀頭結點

if(list != null) // 銷毀連結清單的空間

{

free(list);

list = null;

void finitcirlinklist(cirlinklist *list)

後處理單連結清單，執行以下操作

void finitcirlinklist(cirlinklist *list)

assert(list->m_head->m_next == list->m_head); // 後處理指針針對空連結清單

// assert(list->m_length == 0);

if(list->m_head != null) // 如果此時頭結點空間未被銷毀

free(list->m_head);

list->m_head = null;

list->m_length = -1; // 未經初始化的單連結清單元素個數記為-1

void clearcirlinklist(cirlinklist *list)

清空單連結清單中的所有元素

void clearcirlinklist(cirlinklist *list)

while(list->m_head->m_next != list->m_head)

deletenode(list, 0);

/// 查找函數

/// 查找到連結清單list中第position個結點

/// cirlinklistnode* findposnode(cirlinklist *list, int position)

/// 在連結清單list中找到currnode的前一個結點

/// cirlinklistnode *findprevnode(cirlinklist *list, cirlinklistnode *currnode)

/// 判斷結點node指向的區域是不是連結清單中的結點

/// int isnodeinlist(cirlinklist *list, cirlinklistnode *node)

/// 找到資料域為data的結點首次出現的位置并傳回結點資訊

/// cirlinklistnode* finddatanode(cirlinklist *list, elemtype data, int *position)

cirlinklistnode* findposnode(cirlinklist *list, int position)

positon : 帶查找的連結清單指針的位置

若成功傳回指向待查找結點的指針

若失敗傳回null

該函數的功能是: 查找到連結清單list中第position個結點

cirlinklistnode* findposnode(cirlinklist *list, int position)

assert(list != null); // 連結清單不能為空

assert(position >= -1 && position < list->m_length); // 插入的w位置隻能在[-1~length]

cirlinklistnode *pnode = list->m_head->m_next;

// cirlinklistnode *pnode = list->m_tail->m_next; // 當循環連結清單隻設尾指針時采用此代碼

if(position == -1) // -1表示尋找頭指針的前驅

return list->m_head; // 直接傳回前驅

int pos = 0;

while(pnode != list->m_head && pos < position) // 周遊單連結清單，找到第position個結點的位置

pnode = pnode->m_next;

pos++;

if(pos < position) // 如果找到連結清單尾部還沒有找到

return null;

else

#ifdef debug

printf("find the %d point success...[%p]\n", position, pnode);

#endif // debug

return pnode;

cirlinklistnode *findprevnode(cirlinklist *list, cirlinklistnode *currnode);

list : 指向一個連結清單指針，此處傳入表頭位址

currnode : 待查找的連結清單指針的位置

在連結清單list中找到currnode的前一個結點

cirlinklistnode *findprevnode(cirlinklist *list, cirlinklistnode *currnode)

assert(list != null);

assert(currnode != null);

cirlinklistnode *pnode = list->m_head;

while(pnode->m_next != list->m_head && pnode->m_next != currnode)

if(pnode->m_next == currnode) // 查找成功

else // 查找失敗

int isnodeinlist(cirlinklist *list, cirlinklistnode *node)

node : 指向待查找的結點的指針

若成功傳回結點node在連結清單中的位置

若失敗傳回-1

判斷結點node指向的區域是不是連結清單中的結點

int isnodeinlist(cirlinklist *list, cirlinklistnode *node)

assert(list != null); // 連結清單不能為空 assert(node != null); // 待查找的指針不能為空

while(pnode != list->m_head && pnode != node) // 周遊單連結清單，找到第position個結點的位置

if(pnode != node)

{ // 查找成功

return -1;

{ // 查找失敗

printf("find the [%p] point in the first %d pointer of the list...\n", fnode, pos);

return pos;

cirlinklistnode* finddatanode(cirlinklist *list, elemtype data, int *position

data : 待查找的結點的資料資訊

找到資料域為data的結點首次出現的位置并傳回結點資訊

cirlinklistnode* finddatanode(cirlinklist *list, elemtype data, int *position)

cirlinklistnode *node = list->m_head->m_next;

int pos = 0;

while(node != list->m_head && node->m_data != data)

node = node->m_next;

*position = pos; // 将出現的位置傳遞回去

return node; // 傳回結點的資訊

/// 插入函數

/// 将資料data插傳入連結表的prevnode結點的下一個位置個位置

/// cirlinklistnode *addnode(cirlinklist *list, cirlinklistnode *prevnode, elemtype data)

/// 将資料data插傳入連結表的第position個位置

/// cirlinklistnode *insertnode(cirlinklist *list, int position, elemtype data)

cirlinklistnode* addnode(cirlinklist *list, cirlinklistnode *prevnode, elemtype data);

prevnode : 待插入位置的前一個結點

data : 待插入結點的資料

該函數的功能是: 将資料data插傳入連結表的prevnode結點的下一個位置個位置

cirlinklistnode* addnode(cirlinklist *list, cirlinklistnode *prevnode, elemtype data)

assert(prevnode != null); // 插入點不能是空指針

cirlinklistnode *newnode = null;

if((newnode = (cirlinklistnode *)malloc(sizeof(cirlinklistnode))) == null) // 為新結點開辟空間

{ // 開辟新結點失敗

fprintf(stderr, "not enough memeory\n");

// 開辟新結點成功

newnode->m_data = data;

newnode->m_next = null;

// 将指針newnode連接配接在pnode的後面

newnode->m_next = prevnode->m_next;

prevnode->m_next = newnode;

list->m_length++; // 結點數目增加一個

list->m_head->m_data++; // 頭結點的資料域同樣存儲着結點總數

//}

printf("the new node is inserted after point pointer[%p]\n", pnode);

return newnode;

void insertnode(cirlinklist *list, int position, elemtype data)

positon : 待插入結點的位置

data : 待插入結點的資料

該函數的功能是: 将資料data插傳入連結表的第position個位置

cirlinklistnode* insertnode(cirlinklist *list, int position, elemtype data)

assert(list != null);

assert(position >=0 && position < list->m_length + 1);

cirlinklistnode *prevnode = findposnode(list, position - 1); // 找到待插入位置的前一個結點

// 下面調用insertpointnode直接将結點插入到pnode結點後面

if((newnode = addnode(list, prevnode, data)) != null) // 将新的結點插入到待插入前一個指針的後面

{ // 插入成功

return newnode; // 傳回新插入的結點

printf("insert the value %d into list at position %d...\n", data, position);

return null; // 插入失敗傳回null

// // 以可以使用下面的代碼

// if((newnode = (cirlinklistnode *)malloc(sizeof(cirlinklistnode))) == null) // 為新結點開辟空間

// { // 開辟新結點失敗

// fprintf(stderr, "not enough memeory\n");

// exit(exit_failure);

// }

// else

// { // 開辟新結點成功

// newnode->m_data = data;

// newnode->m_next = null;

// // 将指針newnode連接配接在pnode的後面

// newnode->m_next = prevnode->m_next;

// prevnode->m_next = newnode;

// list->m_length++; // 結點數目增加一個

// list->m_head->m_data++; // 頭結點的資料域同樣存儲着結點總數

/// 删除函數

/// 删除連結清單list中prevnode結點之後的指針個指針

/// void deletenode(cirlinklist *list, int position)

/// elemtype subnode(cirlinklist *list, cirlinklistnode *prevnode)

/// elemtype deletecurrnode(cirlinklist *list, cirlinklistnode *currnode)

void deletenode(cirlinklist *list, int position)

positon : 待删除結點的位置

傳回待删除結點的資料域

将單連結清單的第position個結點删除

elemtype deletenode(cirlinklist *list, int position)

assert(position >=0 && position < list->m_length);

cirlinklistnode *prevnode = findposnode(list, position - 1); // 找到第position - 1個結點

// 删除pnode的後一個結點

cirlinklistnode *delnode = prevnode->m_next;

elemtype delelem = delnode->m_data;

prevnode->m_next = delnode->m_next;

free(delnode);

list->m_length--; // 結點數目減少一個

list->m_head->m_data--; // 頭結點的資料域同樣存儲着結點總數

return delelem;

elemtype subnode(cirlinklist *list, cirlinklistnode *prevnode)

删除連結清單list中prevnode結點之後的指針個指針

elemtype subnode(cirlinklist *list, cirlinklistnode *prevnode)

assert(list != null); // 連結清單不能為空

assert(prevnode != null); // 待删除結點的前一個位置不能為空

assert(isnodeinlist(list, prevnode) != -1); // 待删除位置的前一個結點必須在連結清單中

elemtype deletecurrnode(cirlinklist *list, cirlinklistnode *currnode);

elemtype deletecurrnode(cirlinklist *list, cirlinklistnode *currnode)

assert(list != null); // 連結清單不能為空

assert(currnode != null); // 待删除結點的前一個位置不能為空

assert(isnodeinlist(list, currnode) != -1); // 待删除的結點必須在連結清單中

elemtype delelem = -1; // 待删除結點的資料域

cirlinklistnode *delnode = null; // 指向将要删除的結點的指針

// if(list->m_length == 0)

// {

// return -1;

// printf("length = %d\n", list->m_length);

if(currnode->m_next != list->m_head) // 如果待删除結點不是最後一個結點

// 将currnode的後一個結點delnode作為删除結點,

delnode = currnode->m_next;

currnode->m_next = delnode->m_next; //從連結清單中删除delnode

// 并将delnode的資料域儲存到delnode中

delelem = currnode->m_data; // delelem儲存currnode的資料域

currnode->m_data = delnode->m_data; // 真正删除的結點其實是currnode下一個結點, 是以用currnode儲存下一個結點的資料域

else // 否則待删除結點是最後一個結點

// 直接将最後一個結點删除即可，應該把其前一個結點的指針域指派為空

delnode = currnode;

// 下面應該将currnnode的前一個結點的指針域指派為空[時間複雜度o(n)]

cirlinklistnode *prevnode = findprevnode(list, currnode);

prevnode->m_next = list->m_head; /// bug1 最後一個結點的後一個結點

/// 其他函數

/// 顯示單連結清單的資訊

/// void showlist(cirlinklist *list

/// void setnode(cirlinklist *list, int position, elemtype data)

/// 擷取單連結清單list第position個結點的資料域

/// elemtype getnode(cirlinklist *list, int position)

/// 擷取單連結清單list的長度[即元素個數]

/// int lengthcirlinklist(cirlinklist *list)

/// 判斷目前連結清單是否是空連結清單

/// bool isemptycirlinklist(cirlinklist *list)

void showcirlinklist(cirlinklist *list)

顯示單連結清單的資訊

void showlist(cirlinklist *list)

// assert(list->m_head != null)

if(list->m_head == null) // 單連結清單可能沒有被初始化

fprintf(stderr, "you can't show the list without the list initlinklist...\n");

return ;

printf("there are %d data in list\n", list->m_length);

if(list->m_length == 0)

cirlinklistnode *pnode = list->m_head->m_next; // 從頭指針開始周遊

while(pnode != list->m_head) //開始周遊單連結清單

printf("%d ", pnode->m_data);

printf("\n");

// elemtype data;

// for(int pos = 0; pos < list->m_length; pos++)

// data = getnode(list, pos);

// printf("%d ", data);

// printf("\n");

void setnode(cirlinklist *list, int position, elemtype data)

positon : 待修改的結點的資料

data : 待更正的新資料域

修改單連結清單list第position個結點的資料域為data

void setnode(cirlinklist *list, int position, elemtype data)

cirlinklistnode *pnode = findposnode(list, position); // 找到單連結清單的第position個結點

pnode->m_data = data;

elemtype getnode(cirlinklist *list, int position

positon : 待查詢的結點的位置

擷取到的結點資料

擷取單連結清單list第position個結點的資料域

elemtype getnode(cirlinklist *list, int position)

return pnode->m_data;

int lengthcirlinklist(cirlinklist *list)

單連結清單的長度

擷取單連結清單的長度

int lengthcirlinklist(cirlinklist *list)

return list->m_length;

bool isemptycirlinklist(cirlinklist *list)

如果單連結清單是空表，傳回true

否則傳回false

bool isemptycirlinklist(cirlinklist *list)

return (list->m_head->m_next == list->m_head);

// return (list->m_tail == this->m_head);

cirlinklistnode* getfisrtnode(cirlinklist *list)

傳回頭指針

擷取循環連結清單的頭指針

cirlinklistnode* getfisrtnode(cirlinklist *list)

return list->m_head->m_next;

// return list->m_tail->m_next->m_next; // 隻設尾指針的時候使用此代碼

cirlinklistnode* getheadnode(cirlinklist *list)

傳回頭結點的位址

擷取指向頭結點的指針

cirlinklistnode* getheadnode(cirlinklist *list)

return list->m_head;

// return list->m_tail->m_next; // 隻設尾指針的時候使用此代碼

#define list_size 7

// 主函數

int main(void)

int pos;

printf("test 1...\n");

cirlinklist *plist = createcirlinklist( ); // 建立單連結清單

for(int pos = 0; pos < list_size; pos++) // 循環向單連結清單中插入資料

insertnode(plist, pos, pos + 1);

showlist(plist); // 插入結束後顯示單連結清單的資訊

deletenode(plist, 0); // 删除第一個元素

showlist(plist);

deletenode(plist, 1); // 删除第二個元素

clearcirlinklist(plist); // 将單連結清單清空

destroycirlinklist(plist); // 将單連結清單銷毀

plist = null;

printf("\n\ntest 2...\n");

cirlinklist list;

initcirlinklist(&list); // 初始化單連結清單

for(int pos = 0; pos < list_size; pos++) // 訓話向單連結清單中插入資料

insertnode(&list, pos, pos + 1);

showlist(&list); // 顯示單連結清單

clearcirlinklist(&list); // 清空單連結清單

// finitlinklist(&list); // error== list->m_head->m_next == null

showlist(&list);

printf("\n\ntest 3...\n");

cirlinklistnode *prevnode = list.m_head;

cirlinklistnode *addnode = null;

for(int pos = 0; pos < list_size; pos++)

if((addnode = addnode(&list, prevnode, pos + 1)) != null)

{

prevnode = addnode;

}

while(isemptycirlinklist(&list) != true) // 循環删除單連結清單中的資料

//printf("%p == %p\n", list.m_head->m_next, list.m_head);

deletecurrnode(&list, list.m_head->m_next);

return exit_success;

}

轉載：http://blog.csdn.net/gatieme/article/details/42714079

資料結構體模版---循環單連結清單

繼續閱讀

C語言第四章自述2第四章選擇結構程式設計

面試題:vector和map的差別，異同。空間分布，100萬資料存哪個比較合适。一、疊代器差別二、vector三、Map、Set四、vector_map 為什麼比map效率高五、如何選擇六、容器選擇原則七、效率對比

C++ 多線程用條件變量确定線程的執行順序而不是使用 sleep(1)

POJ 1284 Primitive Roots (歐拉函數&原根定理)

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

成員函數初始化清單

2021-08-13c++——類之操作符重載

swmm與lisflood-fp源碼如何一起編譯 CMake指令

Windows下VS開發環境環境安裝工程項目設定關于Debug和Release的提示

一文看懂字元串的加減乘除

C++ 第十五周報告1--《冒泡法排序》

C++實作簡單順序表

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

線性表之順序表的實作

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述