C說話 數據構造之鏈表完成代碼。本站提示廣大學習愛好者:(C說話 數據構造之鏈表完成代碼)文章只能為提供參考,不一定能成為您想要的結果。以下是C說話 數據構造之鏈表完成代碼正文
媒介
比來在溫習數據構造的相干常識,感到在初學的時刻照樣有許多器械沒有控制,不外如今終究算是弄得比擬有眉目了,所以就在寫出來和年夜家一路分享!
甚麼是鏈表
簡略的說,鏈表就是由多個結點團圓分派,彼此經由過程指針相連,每一個結點只要一個先驅結點和後繼結點。首節點無先驅結點,為結點無後繼結點的一種存儲構造。
鏈表的構造
頭結點:鏈表的第一個有用結點後面的結點,頭結點其實不寄存有用數據,也就是數據域為空,加頭結點的重要目標是為了便利鏈表的操作。
首節點:鏈表的第一個有用結點,結點包括數據域和指針域。
尾結點:尾結點的指針域為空。
頭指針:指向頭結點的指針變量,它寄存了頭結點的地址(在這裡留意一下,指針變量寄存的是地址,也就是說頭指針寄存的是
頭結點的地址,普通經由過程頭指針對鏈表停止操作)。
詳細完成
#include<stdio.h> #include<malloc.h> #include<stdlib.h> //界說鏈表節點 typedef struct Node { int data; //數據域 struct Node * pNext; //指針域 }NODE, * PNODE; //NODE等價於struct Node, PNODE等價於struct Node * //函數聲明 PNODE createLinkList(void); //創立鏈表的函數 void traverseLinkList(PNODE pHead); //遍歷鏈表的函數 bool isEmpty(PNODE pHead); //斷定鏈表能否為空的函數 int getLength(PNODE pHead); //獲得鏈表長度的函數 bool insertElement(PNODE pHead, int pos, int val); //向鏈表中拔出元素的函數,三個參數順次為鏈表頭結點、要拔出元素的地位和要拔出元素的值 bool deleteElement(PNODE pHead, int pos, int * pVal); //從鏈表中刪除元素的函數,三個參數順次為鏈表頭結點、要刪除的元素的地位和刪除的元素的值 void sort(PNODE pHead); //對鏈表中的元素停止排序的函數(基於冒泡排序) int main(void) { int val; //用於保留刪除的元素 PNODE pHead = NULL; //PNODE等價於struct Node * pHead = createLinkList(); //創立一個非輪回單鏈表,並將該鏈表的頭結點地址賦給pHead traverseLinkList(pHead); //挪用遍歷鏈表的函數 if(isEmpty(pHead)) printf("鏈表為空!\n"); else printf("鏈表不為空!\n"); printf("鏈表的長度為:%d\n", getLength(pHead)); //挪用冒泡排序函數 sort(pHead); //從新遍歷 traverseLinkList(pHead); //向鏈表中指定地位處拔出一個元素 if(insertElement(pHead, 4, 30)) printf("拔出勝利!拔出的元素為:%d\n", 30); else printf("拔出掉敗!\n"); //從新遍歷鏈表 traverseLinkList(pHead); //刪除元素測試 if(deleteElement(pHead, 3, &val)) printf("元素刪除勝利!刪除的元素是:%d\n", val); else printf("元素刪除掉敗!\n"); traverseLinkList(pHead); system("pause"); return 0; } PNODE createLinkList(void) { int length; //有用結點的長度 int i; int value; //用來寄存用戶輸出的結點的值 //創立了一個不寄存有用數據的頭結點 PNODE pHead = (PNODE)malloc(sizeof(NODE)); if(NULL == pHead) { printf("內存分派掉敗,法式加入!\n"); exit(-1); } PNODE pTail = pHead; //pTail一直指向尾結點 pTail->pNext = NULL; //清空指針域 printf("請輸出您想要創立鏈表結點的個數:len = "); scanf("%d", &length); for(i=0;i<length;i++) { printf("請輸出第%d個結點的值:", i+1); scanf("%d", &value); PNODE pNew = (PNODE)malloc(sizeof(NODE)); if(NULL == pHead) { printf("內存分派掉敗,法式加入!\n"); exit(-1); } pNew->data = value; //向新結點中放入值 pTail->pNext = pNew; //將尾結點指向新結點 pNew->pNext = NULL; //將新結點的指針域清空 pTail = pNew; //將新結點賦給pTail,使pTail一直指向為尾結點 } return pHead; } void traverseLinkList(PNODE pHead) { PNODE p = pHead->pNext; while(NULL != p) { printf("%d ", p->data); p = p->pNext; } printf("\n"); return; } bool isEmpty(PNODE pHead) { if(NULL == pHead->pNext) return true; else return false; } int getLength(PNODE pHead) { PNODE p = pHead->pNext; //指向首節點 int len = 0; //記載鏈表長度的變量 while(NULL != p) { len++; p = p->pNext; //p指向下一結點 } return len; } void sort(PNODE pHead) { int len = getLength(pHead); //獲得鏈表長度 int i, j, t; //用於交流元素值的中央變量 PNODE p, q; //用於比擬的兩個中央指針變量 for(i=0,p=pHead->pNext ; i<len-1 ; i++,p=p->pNext) { for(j=i+1,q=p->pNext;j<len;j++,q=q->pNext) { if(p->data > q->data) { t = p->data; p->data = q->data; q->data = t; } } } return; } bool insertElement(PNODE pHead, int pos, int val) { int i = 0; PNODE p = pHead; //斷定p能否為空而且使p終究指向pos地位的結點 while(NULL!=p && i<pos-1) { p = p->pNext; i++; } if(NULL==p || i>pos-1) return false; //創立一個新結點 PNODE pNew = (PNODE)malloc(sizeof(NODE)); if(NULL == pNew) { printf("內存分派掉敗,法式加入!\n"); exit(-1); } pNew->data = val; //界說一個暫時結點,指向以後p的下一結點 PNODE q = p->pNext; //將p指向新結點 p->pNext = pNew; //將q指向之前p指向的結點 pNew->pNext = q; return true; } bool deleteElement(PNODE pHead, int pos, int * pVal) { int i = 0; PNODE p = pHead; //斷定p能否為空而且使p終究指向pos結點 while(NULL!=p->pNext && i<pos-1) { p = p->pNext; i++; } if(NULL==p->pNext || i>pos-1) return false; //保留要刪除的結點 * pVal = p->pNext->data; //刪除p前面的結點 PNODE q = p->pNext; p->pNext = p->pNext->pNext; free(q); q = NULL; return true; }
開頭語
下面完成的重要是單鏈表,別的還有雙鏈表、輪回鏈表、非輪回鏈表等其他幾種罕見鏈表。雙鏈表的特別性表示在每一個根本結點有兩個指針域;輪回鏈表的特征重要表示在,在輪回鏈表中,經由過程任何一個結點可以找到其他一切結點。
感謝年夜家的浏覽,願望能贊助到年夜家,感謝年夜家對本站的支撐!