在存儲(chǔ)結(jié)構(gòu)上，不需要連續(xù)的存儲(chǔ)空間，需要上一個(gè)結(jié)點(diǎn)的指針域 指向下一個(gè)結(jié)點(diǎn)即可，找到一個(gè)結(jié)點(diǎn)就可以找到下一個(gè)結(jié)點(diǎn)。

學(xué)習(xí)教材是大話數(shù)據(jù)結(jié)構(gòu)，加上自己的一些個(gè)人理解。這個(gè)算法 有點(diǎn)繞，需要對(duì)指針 相關(guān)內(nèi)容相當(dāng)熟悉。通過學(xué)習(xí)感覺單鏈表相關(guān)算法還是蠻考驗(yàn)C知識(shí)的和邏輯思維。

下面看代碼：

#include <stdio.h> #include <stdlib.h> #define ERROR 0 #define OK 1 typedef int EleType; typedef int Status; typedef struct Node Node;//鏈表元素 struct Node {EleType data;//數(shù)據(jù)域Node * next;//指針域 }; typedef Node* LinkList; void printLinkList(const LinkList * const list) {if (NULL ==list) {//鏈表為空printf("printLinkList error \n");return;}int i = 1;LinkList li = (*list)->next;//從頭結(jié)點(diǎn)后面第一個(gè)結(jié)點(diǎn)開始遍歷while (li)//最后一個(gè)元素沒有指向，不會(huì)進(jìn)行循環(huán)。{printf("第%d元素:%d\t", i, li->data);li = li->next;i++;}printf("\n");return; } //創(chuàng)建擁有頭結(jié)點(diǎn)的鏈表 //頭插法創(chuàng)建鏈表，往鏈表中添加元素，新創(chuàng)建的的元素始終在頭結(jié)點(diǎn)后面類似 頭指針 -> 頭結(jié)點(diǎn)->An->An-1->An-2 ...-> A1 //元素的數(shù)據(jù) 隨機(jī)生成100以內(nèi)的數(shù)字 Status creatLinkListInHead(LinkList *list,int n) {srand(time(0));//設(shè)置隨機(jī)種子，為產(chǎn)生隨機(jī)數(shù)做準(zhǔn)備。//LinkList 類型 和 Node * 類型是一樣的！看最上方定義類型別名，為什么可以做呢？鏈表的頭指針 就是指向結(jié)點(diǎn)Node，所有鏈表類型是 Node *，只是為了更好看而已。 LinkList li=NULL;Node *node=NULL;//可以定義為 LinkList *node = NULL;int i = 0;li = (LinkList)malloc(sizeof(Node));//頭指針指向頭結(jié)點(diǎn)，給頭結(jié)點(diǎn)分配空間if (NULL == li||n<0) {//分配內(nèi)存空間失敗或者鏈表元素個(gè)數(shù)非法 返回return ERROR;}li->next = NULL;//初始頭結(jié)點(diǎn)沒有指向for ( i = 0; i < n; i++){node = (Node*)malloc(sizeof(Node));//給結(jié)點(diǎn)分配空間if (NULL==node) {//給分配空間失敗 return ERROR;}node->data = rand()%100;//除以100取余的到100以內(nèi)的數(shù)字，不包括100，如果含100 就需要+1node->next = li->next;//新添加的元素指針域 指向頭結(jié)點(diǎn)后面的結(jié)點(diǎn)li->next = node;//頭結(jié)點(diǎn)指針域 指向新增加的元素}*list = li;//通過指針 給外部鏈表賦值return OK; } //尾插法創(chuàng)建鏈表，往鏈表中添加元素，先添加的元素放前面，后添加的元素放后面，遵循先來后到的道理 Status creatLinkListInTail(LinkList *list, int n) {srand(time(0));//設(shè)置隨機(jī)種子LinkList li = NULL ;Node *node = NULL;int i = 0;li = (LinkList)malloc(sizeof(Node));if (NULL == li || n<0) {//分配內(nèi)存空間失敗或元素個(gè)數(shù)非法return ERROR;}li->next = NULL;//初始頭結(jié)點(diǎn)指向*list = li;//給通過外部鏈表賦值，指向頭結(jié)點(diǎn)，此時(shí) list 和 li 都指向頭結(jié)點(diǎn)。for ( i = 0; i < n; i++){node = (Node*)malloc(sizeof(Node));//給結(jié)點(diǎn)分配空間if (NULL == node) {//分配空間失敗 return ERROR;}node->data = rand() % 100;//除以100取余的到100以內(nèi)的數(shù)字，不包括100，如果含100 就需要+1li->next = node;//新結(jié)點(diǎn) 放到鏈表末尾li = node;//移動(dòng)鏈表指針指向最新鏈表最后一個(gè)元素，為了下次循環(huán)在鏈表末尾添加元素//temp = node;}//最后表尾元素指針域 設(shè)置NULLli->next = NULL;//*list = li;//一定要放在for循環(huán)前面，不然頭結(jié)點(diǎn)的內(nèi)存空間沒有指向！起初l指向頭結(jié)點(diǎn)，但是進(jìn)入for循環(huán)后l的指向發(fā)生改變要移動(dòng)指向最新添加的結(jié)點(diǎn)元素。return OK; } //獲取鏈表元素?cái)?shù)據(jù),通過指針返回 鏈表第i個(gè)元素的 數(shù)據(jù) //i還是按國(guó)人的順序來吧，從1開始 Status getELement(LinkList list, int position,EleType *e) {//異常情況：空指針,元素位置非法if (NULL == list || position < 1) {return ERROR;}LinkList li = list;int i = 1;while (li && i<position) {//在鏈表范圍內(nèi)遍歷元素 直到 找到第position位置的 元素 i++;li = li->next;}if (NULL == li || position > i) {//超出鏈表范圍，都遍歷完鏈表還沒找到元素。return ERROR;}//通上面 while循環(huán) 當(dāng)i = position 跳出循環(huán) ，li 此時(shí)指向鏈表 第position位置的 前面一個(gè)結(jié)點(diǎn)。*e = li->next->data;return OK; } //往鏈表中第position位置 插入元素，元素?cái)?shù)據(jù)為 e //元素位置從1開始數(shù) Status insertLinkList(LinkList *list,int position,EleType e) {Node *node = (Node*)malloc(sizeof(Node));//異常情況：空指針，為插入元素分配空間失敗，元素位置非法，if (NULL == list || NULL==node || position < 1) {return ERROR;}LinkList li = * list;int i = 1;while ( li && i<position) {//在鏈表范圍內(nèi)遍歷元素 直到 找到第position位置的 元素 i++;li = li->next;}if (NULL == li || position > i) {//超出鏈表范圍return ERROR;}//通上面 while循環(huán) 當(dāng)i = position 跳出循環(huán) ，li 此時(shí)指向鏈表 第position位置的 前面一個(gè)結(jié)點(diǎn)。node->data = e;node->next = li->next;//讓 插入結(jié)點(diǎn)指針域指向 原來位置的結(jié)點(diǎn)li->next = node;//讓插入結(jié)點(diǎn)位置前的結(jié)點(diǎn) 指向插入結(jié)點(diǎn)return OK; } //在鏈表第position位置 刪除元素，通過指針返回 刪除元素的數(shù)據(jù)內(nèi)容 Status delLinkListEle(LinkList *list, int position, EleType *e) {//異常情況：空指針,元素位置非法if (NULL == list || position < 1) {return ERROR;}LinkList li = *list;Node * node = NULL;int i = 1;while (li && i<position) {//在鏈表范圍內(nèi)遍歷元素 直到 找到第position位置的 元素 i++;li = li->next;}if (NULL == li || position > i) {//超出鏈表范圍，都遍歷完鏈表還沒找到元素。return ERROR;}//通上面 while循環(huán) 當(dāng)i = position 跳出循環(huán) ，li 此時(shí)指向鏈表 第position位置的 前面一個(gè)結(jié)點(diǎn)。node = li->next;//保存要?jiǎng)h除元素的地址li->next = node->next;//讓刪除元素前置結(jié)點(diǎn) 指向 刪除元素 直接后繼結(jié)點(diǎn)。然后就可以釋放 刪除結(jié)點(diǎn)的空間了。*e = node->data;//將刪除元素?cái)?shù)據(jù)通過指針修改返回free(node);//釋放刪除元素空間return OK; } //清空整個(gè)鏈表，釋放指針指向的內(nèi)存 Status freeLinkList(LinkList *list) {if (NULL == list)//空指針return ERROR;//注意：頭結(jié)點(diǎn)不要釋放！只釋放頭結(jié)點(diǎn)后面的結(jié)點(diǎn)元素//LinkList li = *list;這樣將會(huì)把頭結(jié)點(diǎn)也釋放掉LinkList li = (*list)->next;//將鏈表指針指向第一個(gè)結(jié)點(diǎn)元素，從這個(gè)元素開始釋放Node * node = NULL;//臨時(shí)變量，指向還未釋放的元素while (li){//鏈表指針向移動(dòng)指向結(jié)點(diǎn)元素，直到?jīng)]有后繼結(jié)點(diǎn)node = li->next;//保存要釋放結(jié)點(diǎn) 的直接后繼結(jié)點(diǎn)位置。 free(li);li = node;//繼續(xù)指向 未釋放結(jié)點(diǎn)}//將頭結(jié)點(diǎn)指針域設(shè)置為NULL(*list)->next = NULL;return OK; } int main(void) {LinkList linkList;EleType e;printf("頭插法創(chuàng)建鏈表結(jié)構(gòu)：\n");creatLinkListInHead(&linkList, 4);printLinkList(&linkList);//先釋放 然后再用尾插法freeLinkList(&linkList);printf("尾插法創(chuàng)建鏈表結(jié)構(gòu)：\n");creatLinkListInTail(&linkList, 4);printLinkList(&linkList);printf("第%d個(gè)位置插入%d：\n",5,100);//插入元素insertLinkList(&linkList, 5, 100);//往鏈表尾結(jié)點(diǎn)后面插入元素printLinkList(&linkList);printf("第%d個(gè)位置插入%d：\n", 3, 103);//插入元素insertLinkList(&linkList, 3, 103);//鏈表中間插入元素printLinkList(&linkList);//獲取元素getELement(linkList, 4, &e);printf("第%d個(gè)位置元素：%d\n", 4,e);//刪除元素delLinkListEle(&linkList, 5, &e);printf("第%d個(gè)位置刪除：%d\n", 5, e);printLinkList(&linkList);//刪除元素delLinkListEle(&linkList, 1, &e);printf("第%d個(gè)位置刪除：%d\n", 1,e);printLinkList(&linkList);//釋放整個(gè)表freeLinkList(&linkList);system("pause");return 0; }
結(jié)果驗(yàn)證截圖：

總結(jié)

以上是生活随笔為你收集整理的线性表之链式存储结构_单链表相关算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。