上一篇寫單連結清單是帶頭結點的，但是其他這種寫法的單連結清單中，頭結點其實就不是那麼必要了，因為我們的單連結清單結構體中增加了一項m_length
下面的不加頭結點的單連結清單奉上
不帶頭結點的單連結清單結構體
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
///*////////////////////////////////////////////////////////////////////////////
///
/// 建立和初始化單連結清單
/// 建立 linklist* creatlinklist(void)
/// 初始化 void initlinklist(linklist *list)
typedef int elemtype; // 自定義資料類型
//typedef struct linklistnode* plinklistnode; // 連結清單結點指針域
// 連結清單結點資料域
typedef struct linklistnode
{
elemtype m_data; // 資料域
struct linklistnode *m_next; // 指針域
}linklistnode;
// 帶頭結點的單項連結清單
typedef struct linklist
linklistnode *m_head; // 連結清單頭結點
int m_length; // 單連結清單資料結點個數指針域
}linklist;
/// 開辟一個單連結清單資料結構，并初始化頭結點，然後将建立好的單連結清單指針傳回
/// linklist* creatlinklist(void)
/// 初始化單連結清單
/// void initlinklist(linklist *list)
///*///////////////////////////////////////////////////////////////////////////
/**
linklist* creatlinklist(void)
參數
list : 指向一個連結清單指針，此處傳入表頭位址
傳回值
若成功傳回建立好的單連結清單的指針
功能
開辟一個單連結清單資料結構，并初始化頭結點，然後将建立好的單連結清單指針傳回
注意
使用createlinklist建立的單連結清單，需要用destroylinklist來銷毀
以免發生記憶體洩漏
*/
linklist* createlinklist(void)
linklist *list = null;
if((list = (linklist *)malloc(sizeof(linklist))) == null) // 開辟單連結清單的空間
{ // 開辟失敗
fprintf(stderr, "not enough memory when create list...\n");
exit(exit_failure);
}
initlinklist(list); // 初始化單連結清單
return list;
}
void initlinklist(linklist *list)
無
初始化單連結清單， 執行以下操作
①開辟頭結點的空間 ②進行必要的初始化[頭結點的初始化和單連結清單結點數目的初始化]
使用initlinklist初始化的單連結清單(初始化時malloc了頭結點m_head的空間)
而使用用finitlinklist來進行後處理(後處理時free了頭結點的m_head空間)
void initlinklist(linklist *list)
list->m_head = null; // 初始化隻有頭結點
list->m_length = 0; // 資料元素個數為0
/// 銷毀以及後處理單連結清單
/// 銷毀用createlinklist建立的單連結清單
/// void destroylinklist(linklist *list)
/// 後處理單連結清單，
/// void finitlinklist(linklist *list)
/// 清空單連結清單中的所有元素
/// void clearlinklist(linklist *list)
void destroylinklist(linklist *list)
銷毀用createlinklist建立的單連結清單，執行以下操作
①清空單連結清單 ②釋放頭結點 ③釋放單連結清單
linklist* destroylinklist(linklist *list)
clearlinklist(list); // 清空連結清單
finitlinklist(list); // 銷毀頭結點
if(list != null) // 銷毀連結清單的空間
{
free(list);
list = null;
void finitlinklist(linklist *list)
後處理單連結清單， 執行以下操作
void finitlinklist(linklist *list)
assert(list->m_head == null); // 後處理指針針對空連結清單
// list->m_head = null;
list->m_length = -1; // 未經初始化的單連結清單元素個數記為-1
void clearlinklist(linklist *list)
清空單連結清單中的所有元素
void clearlinklist(linklist *list)
while(list->m_head != null)
deletenode(list, 0);
/// 查找函數
/// 查找到連結清單list中第position個結點
/// linklistnode* findposnode(linklist *list, int position)
/// 在連結清單list中找到currnode的前一個結點
/// linklistnode *findprevnode(linklist *list, linklistnode *currnode)
/// 判斷結點node指向的區域是不是連結清單中的結點
/// int isnodeinlist(linklist *list, linklistnode *node)
/// 找到資料域為data的結點首次出現的位置并傳回結點資訊
/// linklistnode* finddatanode(linklist *list, elemtype data, int *position)
linklistnode* findposnode(linklist *list, int position)
positon : 帶查找的連結清單指針的位置
若成功傳回指向待查找結點的指針
若失敗傳回null
該函數的功能是: 查找到連結清單list中第position個結點
linklistnode* findposnode(linklist *list, int position)
assert(list != null); // 連結清單不能為空
assert(position >= 0 && position < list->m_length); // 查找的位置隻能在[0, length)
linklistnode *pnode = list->m_head;
int pos = 0;
while(pnode != null && pos < position) // 周遊單連結清單，找到第position個結點的位置
pnode = pnode->m_next;
pos++;
if(pnode == null || pos < position)
return null;
else
#ifdef debug
printf("find the %d point success...[%p]\n", position, pnode);
#endif // debug
return pnode;
linklistnode *findprevnode(linklist *list, linklistnode *currnode);
list : 指向一個連結清單指針，此處傳入表頭位址
currnode : 待查找的連結清單指針的位置
在連結清單list中找到currnode的前一個結點
linklistnode *findprevnode(linklist *list, linklistnode *currnode)
assert(list != null);
assert(currnode != null);
linklistnode *pnode = list->m_head;
while(pnode->m_next != null && pnode->m_next != currnode)
if(pnode->m_next == currnode) // 查找成功
else // 查找失敗
int isnodeinlist(linklist *list, linklistnode *node)
node : 指向待查找的結點的指針
若成功 傳回結點node在連結清單中的位置
若失敗 傳回-1
判斷結點node指向的區域是不是連結清單中的結點
int isnodeinlist(linklist *list, linklistnode *node)
assert(list != null); // 連結清單不能為空 assert(node != null); // 待查找的指針不能為空
while(pnode != null && 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;
/// 插入函數
/// 将資料data插傳入連結表的prevnode結點的下一個位置個位置
/// linklistnode *addnode(linklist *list, linklistnode *prevnode, elemtype data)
/// 将資料data插傳入連結表的第position個位置
/// linklistnode *insertnode(linklist *list, int position, elemtype data)
void insertnode(linklist *list, int position, elemtype data)
positon : 待插入結點的位置
data : 待插入結點的資料
該函數的功能是: 将資料data插傳入連結表的第position個位置
linklistnode* insertnode(linklist *list, int position, elemtype data)
assert(position >=0 && position < list->m_length + 1); // 插入的位置應該在[0-length]
linklistnode *prevnode = null;
linklistnode *newnode = null;
// 為新結點開辟空間并且
if((newnode = (linklistnode *)malloc(sizeof(linklistnode))) == null) // 為新結點開辟空間
{ // 開辟新結點失敗
fprintf(stderr, "not enough memeory\n");
{ // 開辟新結點成功并且指派
newnode->m_data = data;
newnode->m_next = null;
// 将新結點添加在連結清單中
if(position == 0) // 如果目前連結清單是空連結清單
{ /// 插傳入連結表中第一個結點， 不帶頭結點的單連結清單，插入删除第一個元素時需要進行特殊判斷
if(list->m_head == null) // 如果插入之前單連結清單是空表
{
list->m_head = newnode; // 空表直接将新結點插入即可
}
else // 否則單連結清單不是空表
//prevnode = list->m_head;
newnode->m_next = list->m_head; // 将新結點插入頭指針的前面即可
list->m_head = newnode;
else // 否則目前連結清單不是空連結清單
prevnode = findposnode(list, position - 1); // 找到待插入點的前一個指針
// 将指針newnode連接配接在pnode的後面
newnode->m_next = prevnode->m_next;
prevnode->m_next = newnode;
list->m_length++; // 結點數目增加一個
printf("insert the value %d into list at position %d...\n", data, position);
return newnode; // 傳回指向插入的新結點的指針
linklistnode* addnode(linklist *list, linklistnode *prevnode, elemtype data);
prevnode : 待插入位置的前一個結點
data : 待插入結點的資料
該函數的功能是: 将資料data插傳入連結表的prevnode結點的下一個位置個位置
[注意] 由于單連結清單不存在連結清單頭，那麼第一個元素不存在前驅，是以插入第一個元素時，預設其prevnode是list
linklistnode *addnode(linklist *list, linklistnode *prevnode, elemtype data)
assert(prevnode != null); // 插入點不能是空指針
//else
//{
// 開辟新結點成功
newnode->m_data = data;
newnode->m_next = null;
if(prevnode == (linklistnode *)list)
//}
printf("the new node is inserted after point pointer[%p]\n", pnode);
return newnode;
/// 删除函數
/// 删除連結清單list中prevnode結點之後的指針個指針
/// void deletenode(linklist *list, int position)
/// elemtype subnode(linklist *list, linklistnode *prevnode)
/// elemtype deletecurrnode(linklist *list, linklistnode *currnode)
elemtype deletenode(linklist *list, int position)
positon : 待删除結點的位置
傳回待删除結點的資料域
将單連結清單的第position個結點删除
elemtype deletenode(linklist *list, int position)
assert(list != null); // 删除不能為空
assert(position >=0 && position < list->m_length); // 待删除的指針位置僅限于連結清單中存在的位置
linklistnode *delnode = null;
elemtype delelem = -1;
if(position == 0) // 如果待删除的是連結清單中第一個指針， 第一個元素沒有前驅結點
{ // 删除連結清單中第一個結點
delnode = list->m_head;
if(list->m_head->m_next == null) // 如果連結清單中隻剩下一個元素
list->m_head = null;
else // 否則連結清單中剩下多個元素
list->m_head = delnode->m_next;
else // 否則待删除的是其他結點
linklistnode *pnode = findposnode(list, position - 1); // 找到第position - 1個結點
// 删除pnode的後一個結點
delnode = pnode->m_next;
pnode->m_next = delnode->m_next;
delelem = delnode->m_data; // 儲存待删除結點的資料域
free(delnode);
list->m_length--; // 結點數目減少一個
printf("delete the list in the first %d node...\n", position);
return delelem;
elemtype subnode(linklist *list, linklistnode *prevnode)
删除連結清單list中prevnode結點之後的指針個指針
elemtype subnode(linklist *list, linklistnode *prevnode)
assert(list != null); // 連結清單不能為空
assert(prevnode != null); // 待删除結點的前一個位置不能為空
assert(isnodeinlist(list, prevnode) != -1); // 待删除位置的前一個結點必須在連結清單中
if(prevnode == list) // 如果待删除的是連結清單中第一個指針， 第一個元素沒有前驅結點[穿參數時預設為list]
delnode = list->m_head; // 待删除的元素為頭指針指向的元素
delnode = prevnode->m_next;
prevnode->m_next = delnode->m_next;
delelem = delnode->m_data;
list->m_head->m_data--; // 頭結點的資料域同樣存儲着結點總數
elemtype deletecurrnode(linklist *list, linklistnode *currnode);
elemtype deletecurrnode(linklist *list, linklistnode *currnode)
assert(list != null); // 連結清單不能為空
assert(currnode != null); // 待删除結點的前一個位置不能為空
assert(isnodeinlist(list, currnode) != -1); // 待删除的結點必須在連結清單中
elemtype delelem = -1; // 待删除結點的資料域
linklistnode *delnode = null; // 指向将要删除的結點的指針
if(currnode == list->m_head) // 如果待删除的是第一個結點
{ // 删除連結清單中第一個結點， 不帶頭結點的單連結清單，插入删除第一個元素時需要進行特殊判斷
else // 否則删除的不是第一個結點
if(currnode->m_next != null) // 如果待删除結點不是最後一個結點
{ // 删除連結清單中最後一個結點時，需要将其前驅的指針域置空
// 将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)]
linklistnode *prevnode = findprevnode(list, currnode);
prevnode->m_next = null;
/// 其他函數
/// 顯示單連結清單的資訊
/// void showlist(linklist *list
/// void setnode(linklist *list, int position, elemtype data)
/// 擷取單連結清單list第position個結點的資料域
/// elemtype getnode(linklist *list, int position)
/// 擷取單連結清單list的長度[即元素個數]
/// int lengthlinklist(linklist *list)
/// 判斷目前連結清單是否是空連結清單
/// bool isemptylinklist(linklist *list)
void showlinklist(linklist *list)
顯示單連結清單的資訊
void showlist(linklist *list)
printf("there are %d data in list\n", list->m_length);
linklistnode *pnode = list->m_head; // 從頭指針開始周遊
while(pnode != null) //開始周遊單連結清單
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(linklist *list, int position, elemtype data)
positon : 待修改的結點的資料
data : 待更正的新資料域
修改單連結清單list第position個結點的資料域為data
void setnode(linklist *list, int position, elemtype data)
linklistnode *pnode = findposnode(list, position); // 找到單連結清單的第position個結點
pnode->m_data = data;
elemtype getnode(linklist *list, int position
positon : 待查詢的結點的位置
擷取到的結點資料
擷取單連結清單list第position個結點的資料域
elemtype getnode(linklist *list, int position)
return pnode->m_data;
int lengthlinklist(linklist *list)
單連結清單的長度
擷取單連結清單的長度
int lengthlinklist(linklist *list)
return list->m_length;
bool isemptylinklist(linklist *list)
如果單連結清單是空表，傳回true
否則傳回false
bool isemptylinklist(linklist *list)
return (list->m_length == 0);
// return (list->m_head == null);
#define list_size 7
// main
int main(void)
int pos;
printf("test 1...\n");
linklist *plist = createlinklist( ); // 建立單連結清單
for(int pos = 0; pos < list_size; pos++) // 循環向單連結清單中插入資料
insertnode(plist, pos, pos + 1);
printf("head = %p\n", plist->m_head);
showlist(plist); // 插入結束後顯示單連結清單的資訊
deletenode(plist, 0); // 删除第一個元素
showlist(plist);
deletenode(plist, 1); // 删除第二個元素
clearlinklist(plist); // 将單連結清單清空
destroylinklist(plist); // 将單連結清單銷毀
plist = null;
printf("\n\ntest 2...\n");
linklist list;
initlinklist(&list); // 初始化單連結清單
for(int pos = 0; pos < list_size; pos++) // 訓話向單連結清單中插入資料
insertnode(&list, pos, pos + 1);
showlist(&list); // 顯示單連結清單
clearlinklist(&list); // 清空單連結清單
// finitlinklist(&list); // error== list->m_head->m_next == null
showlist(&list);
printf("\n\ntest 3...\n");
linklistnode *addnode = null;
prevnode = insertnode(&list, 0, 1); // 由于不帶頭結點是以進行插入第一個元素時第一個元素沒有前驅結點
// 但是也可以使用下面注視掉的代碼
for(int pos = 1; pos < list_size; pos++)
if((addnode = addnode(&list, prevnode, pos + 1)) != null)
prevnode = addnode;
// linklistnode *prevnode = (linklistnode*)&list;
// linklistnode *addnode = null;
// for(int pos = 0; pos < list_size; pos++)
// if((addnode = addnode(&list, prevnode, pos + 1)) != null)
// {
// prevnode = addnode;
// }
while(isemptylinklist(&list) != true) // 循環删除單連結清單中的資料
deletecurrnode(&list, list.m_head); // 删除第一個元素
return exit_success;
}
轉載：http://blog.csdn.net/gatieme/article/details/42527709