-
bool List::InsertHead(Node *pNode)
{
????Node* temp = m_pList->next;
????Node* newNode = new Node;
????if(newNode == NULL)
????{
????????return fasle;
????}
????newNode->data = pNode->data;
????m_pList->next = newNode;
????newNode = temp;
????return true;
}
bool List::InsertTail(Node *pNode)
{
????Node* currentNode = m_pList;
????while(currentNode->next != NULL)
????{
????????currentNode = currentNode->next;
????}
? ? Node* newNode = new Node;
????if(newNode == NULL)
????{
????????return fasle;
????}
????newNode->data = pNode->data;
????newNode->next = NULL;
????currnetNode->next = newNode;
??? ?return true;
}
查看全部 -
bool List::InsertHead(Node *pNode)
{
????Node* temp = m_pList->next;
????Node* newNode = new Node;
????if(newNode == NULL)
????{
????????return fasle;
????}
????newNode->data = pNode->data;
????m_pList->next = newNode;
????newNode = temp;
????return true;
}
bool List::InsertTail(Node *pNode)
{
????Node* currentNode = m_pList;
????while(currentNode->next != NULL)
????{
????????currentNode = currentNode->next;
????}
? ? Node* newNode = new Node;
????if(newNode == NULL)
????{
????????return fasle;
????}
????newNode->data = pNode->data;
????newNode->next = NULL;
????currnetNode->next = newNode;
??? ?return true;
}
查看全部 -
void List::ClearList()
{
????Node *currentNode = m_pList->next;
????while(currentNode != NULL)
????{
????????Node *temp = currentNode->next;
????????delete currentNode;
????????currentNode = temp;
????}
????m_pList->next = NULL;
}
List::~List()
{
????ClearList();
????delete m_pList;
????m_pList = NULL;?
}
查看全部 -
List::List()
{
????m_pList = new Node;
????m_pList->data = 0;
????m_pList->next = NULL;
????m_pList->iLength = 0;
}
bool List::ListEmpty()
{
????if(m_iLength == 0)
????{
????????return true;
????}
????else
????{
????????return false;
????}
}
int List::ListLength()
{
????return m_iLength;
}
查看全部 -
1234567
查看全部 -
數(shù)據(jù)結(jié)構(gòu)之線性表
查看全部 -
析構(gòu)函數(shù)(destructor) 與構(gòu)造函數(shù)相反,當(dāng)對象結(jié)束其生命周期,如對象所在的函數(shù)已調(diào)用完畢時,系統(tǒng)自動執(zhí)行析構(gòu)函數(shù)。?析構(gòu)函數(shù)往往用來做“清理善后” 的工作(例如在建立對象時用new開辟了一片內(nèi)存空間,delete會自動調(diào)用析構(gòu)函數(shù)后釋放內(nèi)存)。
查看全部 -
do more
查看全部 -
建立鏈表的時候,頭結(jié)點我們把數(shù)據(jù)域設(shè)置為固定的0,并且這個數(shù)據(jù)域沒有任何意義,這個頭結(jié)點存在的意義只是為了指向這一條鏈表。? ?頭結(jié)點之后的第一個節(jié)點, 我們認(rèn)為他是第0個節(jié)點。
建立一個毫無意義的頭結(jié)點的好處在于:
1、可以很好的固定住鏈表的入口
2、再清空整個鏈表的時候(清空不是釋放),可以留有一個入口記錄下鏈表的內(nèi)存位置。? 如果沒有這個節(jié)點,把鏈表清空了 就相當(dāng)于釋放了
查看全部 -
什么是線性表:n個?數(shù)據(jù)元素的有限序列
1、順序表:使用數(shù)組,訪問速度快,搜索能力強(qiáng)(數(shù)組本身就有下標(biāo))
2、鏈表:靜態(tài)鏈表、單鏈表、循環(huán)鏈表、雙向鏈表
棧與隊列都是一種特殊的操作受限的線性表,只允許在端點處進(jìn)行插入和刪除,二者的區(qū)別是:棧只允許在表的一端進(jìn)行插入和刪除操作,是一種“后進(jìn)先出”的線性表;而隊列是允許在一端進(jìn)行插入操作,在別一端進(jìn)行刪除和操作,是一種”先進(jìn)先出“的線性表
線性表的應(yīng)用場景:通訊錄、一元多項式
查看全部 -
List.h: //修改主要: //1.將Elem改為Node //2.加了兩個操作:一個向頭插入節(jié)點,一個向尾插入節(jié)點 #ifndef?INC_0131_LIST_H #define?INC_0131_LIST_H #include?"Node.h" class?List { public: ????List();//先放一個頭節(jié)點,不需要size作為參數(shù) ????~List(); ????void?ClearList();//清空鏈表較為麻煩 ????bool?ListEmpty(); ????int?ListLength(); ????bool?GetElem(int?i,?Node?*pNode);//獲取指定元素 ????int?LocateElem(Node?*pNode);//尋找第一個滿足e的元素的位序 ????bool?PriorElem(Node?*pCurrentNode,Node?*preNode);//獲取指定元素的前驅(qū) ????bool?NextElem(Node?*pCurrentNode,Node?*pNextNode);//獲取指定元素的后繼 ????bool?ListInsert(int?i,Node?*pNode); ????bool?ListDelete(int?i,Node?*pNode); ????void?ListTraverse();//遍歷鏈表元素 ????bool?ListInsertHead(Node?*pNode);//插入頭節(jié)點的下一個節(jié)點 ????bool?ListInserTail(Node?*pNode);//插入到最后一個節(jié)點 private: ????Node?*m_pList; ????//int?m_iSize;//鏈表不需要 ????int?m_iLength; }; #endif?//INC_0131_LIST_H
List.cpp: //n?2020-02-06. // #include?"List.h" #include?<iostream> #include?"Node.h" using?namespace?std; //構(gòu)造函數(shù) List::List()?{ ????m_pList?=?new?Node;//頭節(jié)點 ????m_pList->data?=?0;//頭節(jié)點的數(shù)據(jù)域沒有意義 ????m_pList->next?=?NULL; ????m_iLength?=?0;//頭節(jié)點不計入 } void?List::ClearList()?{ ????//順藤摸瓜式清除,先找頭節(jié)點,直到找到指針域為空,用while循環(huán) ?????Node?*currentNode?=?m_pList->next; ?????while(currentNode?!=?NULL){ ?????????Node?*tmp?=?currentNode->next; ?????????delete?currentNode;//釋放掉當(dāng)前currentNode的內(nèi)存 ?????????currentNode?=?tmp; ?????} ?????//不要忘記將頭節(jié)點的next置為0 ?????m_pList->next?=?NULL; } //析構(gòu)函數(shù):將整個內(nèi)存釋放掉, //與ClearList有異曲同工之處:~List需要將頭節(jié)點和后續(xù)所有節(jié)點都釋放掉,而ClearList不需要釋放頭節(jié)點 List::~List(){//可以利用已經(jīng)寫好的clearlist ????ClearList(); ????delete?m_pList; ????m_pList?=NULL; } bool?List::ListEmpty()?{ ????if(m_iLength?==?0){ ????????return?true; ????}?else?{ ????????return?false; ????} } int?List::ListLength(){ ????return?m_iLength; } bool?List::ListInsertHead(Node?*pNode){ ????Node?*tmp?=?m_pList->next; ????Node?*newNode?=?new?Node;//一定要從堆中去申請內(nèi)存,因為如果從棧中申請內(nèi)存,函數(shù)執(zhí)行完成之后這個內(nèi)存就被回收了 ????//注意考慮內(nèi)存申請失敗的情況 ????if(newNode?==?NULL){ ????????return?false; ????} ????newNode->data?=?pNode->data; ????m_pList->next?=?newNode; ????newNode->next?=?tmp; ????m_iLength++; ????return?true; } bool?List::ListInserTail(Node?*pNode){ ????Node?*curentNode?=?m_pList; ????while(curentNode->next?!=?NULL){ ????????curentNode?=?curentNode->next; ????} ????Node?*newNode?=?new?Node; ????if(newNode?==?NULL){ ????????return?false; ????} ????newNode->data?=?pNode->data; ????newNode->next?=?NULL; ????curentNode->next?=?newNode; ????m_iLength++; ????return?true; } bool?List::ListInsert(int?i,Node?*pNode){ ????if(i?<?0?||?i?>?m_iLength){ ????????return?false; ????} ????Node?*currentNode?=?m_pList; ????for(int?k?=?0;k?<?i;k++){ ????????currentNode?=?currentNode->next; ????} ????//自己寫:找到插入的位置 ????Node?*newNode?=?new?Node; ????if(newNode?==?NULL){ ????????return?false; ????} //????newNode?=?currentNode->next; //????currentNode->next?=?pNode; //????pNode->next?=?newNode; //錯誤,為什么? ????newNode->data?=?pNode->data; ????newNode->next?=?currentNode->next; ????currentNode->next?=?newNode; ????m_iLength++; ????return?true; } bool?List::ListDelete(int?i,Node?*pNode){ ????if(i?<?0||i?>=?m_iLength){ ????????return?false; ????} ????Node?*currentNode?=?m_pList; ????Node?*currentNodeBefore?=?NULL; ????for(int?k?=?0;k?<=?i?;k++){ ????????currentNodeBefore?=?currentNode; ????????currentNode?=?currentNode->next; ????} ????currentNodeBefore->next?=?currentNode->next; ????pNode->data?=?currentNode->data; ????delete?currentNode; ????currentNode?=?NULL; ????m_iLength--; } bool?List::GetElem(int?i,?Node?*pNode){ ????if(i?<?0?||?i?>=?m_iLength){ ????????return?false; ????} ????Node?*currentNode?=?m_pList; ????Node?*currentNodeBefore?=?NULL; ????for(int?k?=?0;k?<=?i?;k++){ ????????currentNodeBefore?=?currentNode; ????????currentNode?=?currentNode->next; ????} ????pNode->data?=?currentNode->data; ????return?true; } int?List::LocateElem(Node?*pNode){ ????Node?*currentNode?=?m_pList; ????int?i?=?0; ????while(currentNode->next?!=?NULL){ ????????currentNode?=?currentNode->next;//對鏈表進(jìn)行遍歷,對比數(shù)據(jù)域 ????????//i++;不應(yīng)該寫在這里,只有不相同時才++ ????????if(currentNode->data?==?pNode->data)?{//返回什么?位置?而且只返回第一個符合的值(可能有多個) ????????????return?i; ????????} ????????i++;//不寫在if語句之前,因為m_pList的數(shù)據(jù)域無效。 ????} ????//如果一個節(jié)點都沒有找到,易忽略 ????return?-1; } bool?List::PriorElem(Node?*pCurrentNode,Node?*preNode){ ?????Node?*currentNode?=?m_pList; ?????Node?*tempNode?=?NULL; ?????while(currentNode->next?!=?NULL){ ?????????tempNode?=?currentNode; ?????????currentNode?=?currentNode->next; ?????????if(currentNode->data?==?pCurrentNode->data){ ?????????????if(tempNode?==?m_pList){//如果當(dāng)前節(jié)點的前驅(qū)是頭節(jié)點 ?????????????????return?false; ?????????????} ?????????????preNode->data?=?tempNode->data; ?????????????return?true; ?????????} ?????} } bool?List::NextElem(Node?*pCurrentNode,Node?*pNextNode){ ????Node?*currentNode?=?m_pList; ????while(currentNode->next?!=?NULL){ ????????currentNode?=?currentNode->next; ????????if(currentNode->data?==?pCurrentNode->data){ ????????????if(currentNode->next?==?NULL){ ????????????????return?false; ????????????} ????????????pNextNode->data?=?currentNode->next->data; ????????????return?true; ????????} ????} } void?List::ListTraverse(){ ????Node?*currentNode?=?m_pList; ????while?(currentNode->next?!=?NULL){ ????????currentNode?=?currentNode->next; ????????currentNode->printNode(); ????} }
Node.h: // //?Created?by?w?on?2020-02-07. // #ifndef?INC_0131_NODE_H #define?INC_0131_NODE_H class?Node{ public: ????int?data;//數(shù)據(jù)域,直接寫在public下邊就是為了方便付值 ????Node?*next;//指針域 ????void?printNode(); }; #endif?//INC_0131_NODE_H
Node.cpp: // //?Created?by?x?on?2020-02-07. // #include?<iostream> #include?"Node.h" using?namespace?std; void?Node::printNode(){ ????cout?<<?data?<<endl; }
main.cpp: #include?<iostream> #include?<stdlib.h> #include?"List.h" using?namespace?std; //int?a=3,b=5?; //printf(?"max=%d\n"?,?max(a,b)?);?//這里的a,b就是實參 //int?max(?int?a?,?int?b?)?;//這里的a,b就是形參 //在main函數(shù)中 //????????調(diào)用函數(shù)swap(&a,&b); //定義函數(shù)時: //void?swap(int?*a,?int?*b); //這個是配套使用的。 int?main(){ ????Node?node1;//括號加了會出錯?why? ????node1.data?=?3; ????Node?node2;//括號加了會出錯?why? ????node2.data?=?4; ????Node?node3;//括號加了會出錯?why? ????node3.data?=?5; ????Node?node4;//括號加了會出錯?why? ????node4.data?=?6; ????List?*pList?=?new?List(); ????Node?node5; ????node5.data?=7; ????Node?tmp; //????pList->ListInsertHead(&node1); //????pList->ListInsertHead(&node2); //????pList->ListInsertHead(&node3); //????pList->ListInsertHead(&node4); //????pList->ListTraverse(); ????pList->ListInserTail(&node1); ????pList->ListInserTail(&node2); ????pList->ListInserTail(&node3); ????pList->ListInserTail(&node4); ????pList->ListInsert(1,&node5); //????pList->ListDelete(1,&tmp); ????pList->PriorElem(&node5,&tmp); ????pList->ListTraverse(); ????cout?<<?"tmp?=?"?<<?tmp.data?<<endl; ????delete?pList; ????pList?=?NULL; ????return?0; }
查看全部 -
為什么有了順序表還需要鏈表,因為兩者互為補(bǔ)充
順序表的優(yōu)缺點:
優(yōu)點:遍歷和尋址時非常方便(因為基于數(shù)組)
缺點:插入刪除元素
鏈表:
有些計算機(jī)語言沒有指針:
查看全部 -
未完成,待細(xì)學(xué)
查看全部 -
List.h: // #ifndef?INC_0131_LIST_H #define?INC_0131_LIST_H class?List { public: ????List(int?size); ????~List(); ????void?ClearList();//清空線性表不等于釋放內(nèi)存 ????bool?ListEmpty(); ????int?ListLength(); ????bool?GetElem(int?i,?int?*e);//獲取指定元素 ????int?LocateElem(int?*e);//尋找第一個滿足e的元素的位序 ????bool?PriorElem(int?*currentElem,int?*preElem);//獲取指定元素的前驅(qū) ????bool?NextElem(int?*currentElem,int?*nextElem);//獲取指定元素的后繼 ????bool?ListInsert(int?i,int?*e); ????bool?ListDelete(int?i,int?*e); ????void?ListTraverse();//遍歷鏈表元素 private: ????int?*m_pList; ????int?m_iSize; ????int?m_iLength; }; #endif?//INC_0131_LIST_H
List.cpp: //n?2020-02-06. // #include?"List.h" #include?<iostream> using?namespace?std; //構(gòu)造函數(shù) List::List(int?size)?{ ????m_iSize?=?size; ????//c++中分配內(nèi)存,確定此線性表的容量: ????m_pList?=?new?int[size]; ????m_iLength?=?0; } //析構(gòu)函數(shù):作用主要是將在構(gòu)造函數(shù)中申請的內(nèi)存釋放掉 List::~List()?{ ????delete?[]m_pList; ????m_pList?=?NULL;//iSize置0無所謂,因為內(nèi)存被釋放后該對象也不存在了 } void?List::ClearList(){ ????m_iLength?=?0; } bool?List::ListEmpty(){ ????if(m_iLength?==?0){ ????????return?true; ????}?else{ ????????return?false; ????} ????//也可: ????//reture?m_iLength?==?0???true?:false; } int?List::ListLength(){ ????return??m_iLength; } bool?List::GetElem(int?i,int?*e){ ????if(i?<?0?||?i?>=?m_iSize){ ????????return?false; ????} ????*e?=?m_pList[i]; ????return?true; } int?List::LocateElem(int?*e){ ????for(int?i?=?0;i?<?m_iLength;i++) ????{ ????????if(m_pList[i]?==?*e) ????????{ ????????????return?i; ????????} ????} ????return?-1; } bool?List::PriorElem(int?*currentElem,int?*preElem){ ????int?tmp?=?LocateElem(currentElem); ????//不是先判斷是否是第一個元素,先判斷是否找得到這個數(shù) ????if(tmp?==?-1){ ????????return?false; ????}?else{ ????????if(tmp?==?0){ ????????????return?false; ????????}?else{ ????????????*preElem?=?m_pList[tmp?-?1];//注意是*preElem ????????????return?true; ????????} ????} } bool?List::NextElem(int?*currentElem,int?*nextElem){ ????//判斷是否存在這樣一個元素 ????int?tmp?=?LocateElem(currentElem); ????if(tmp?==?-1){ ????????return?false; ????}?else{ ????????if(tmp?==?m_iLength-1){ ????????????return?false; ????????}?else{ ????????????*nextElem?=?m_pList[tmp+1]; ????????????return?true; ????????} ????} } //自己寫的,有錯誤 //bool?List::PriorElem(int?*currentElem,int?*preElem){ //????//先判斷是否是第一個元素 //????int?tmp?=?LocateElem(currentElem);//注意用之前寫好的函數(shù) //????if(tmp?==?1){ //????????return?false; //????}?else?{ //????????preElem?=?m_pList[tmp?-?1]; //????????return?true; //????} //} // //bool?List::NextElem(int?*currentElem,int?*nextElem){ //????//先判斷是否為最后一個元素 //????int?tmp?=?LocateElem(currentElem); //????if(tmp?==?m_iLength-1){ //????????return?false; //????}?else{ //????????nextElem?=?m_pList[tmp+1]; //????????return?true; //????} //} void?List::ListTraverse(){ ????for(int?i?=?0;?i?<?m_iLength;i++){ ????????cout?<<?m_pList[i]?<<endl; ????} } bool?List::ListInsert(int?i,int?*e){ ????//先判斷是否超過size了 ????if(m_iSize?==?m_iLength?||?i?<?0?||?i?>?m_iLength){//已經(jīng)滿了或i不符合標(biāo)準(zhǔn) ????????return?false; ????}?else{ ????????for(int?k?=?m_iLength?-?1;?k?>=?i;?k--){ ????????????m_pList[k+1]?=?m_pList[k]; ????????} ????????m_pList[i]?=?*e; ????????m_iLength++;//容易忘 ????????return?true;//記得返回正確 ????} } bool?List::ListDelete(int?i,int?*e){ ????//先判斷i是否合法 ????if(i?<?0?||?i?>=?m_iLength){ ????????return?false; ????} ????*e?=?m_pList[i]; ????for(int?k?=?i+1;k?<?m_iLength;k++){ ????????m_pList[k-1]?=?m_pList[k]; ????} ????m_iLength--; ????return?true; }
main.cpp: #include?<iostream> #include?<stdlib.h> #include?"List.h" using?namespace?std; int?main(){ ????int?e1?=?1; ????int?e2?=?2; ????int?e3?=?3; ????int?e4?=?4; ????int?e5?=?5; ????int?e6?=?6; ????int?tmp?=?1; ????List?*list1?=?new?List(10); ????cout?<<?"length:"?<<?list1->ListLength()?<<endl; ????list1->ListInsert(0,&e1); ????cout?<<?"length:"?<<?list1->ListLength()?<<endl; ????list1->ListInsert(1,&e2); ????list1->ListInsert(2,&e3); ????list1->ListInsert(3,&e4); ????list1->ListInsert(4,&e5); ????list1->ListInsert(5,&e6); ????list1->ListDelete(0,&tmp); ????cout?<<?"#"?<<?tmp?<<endl; ????if(!list1->ListEmpty()){ ????????cout?<<?"not?empty"?<<endl; ????} ????list1->ClearList(); ????list1->ListTraverse(); ????list1->ListInsert(0,&e1); ????list1->ListInsert(1,&e2); ????list1->ListInsert(2,&e3); ????list1->ListInsert(3,&e4); ????list1->ListInsert(4,&e5); ????list1->ListInsert(5,&e6); ????list1->GetElem(4,&tmp); ????cout?<<?"tmp:"?<<?tmp?<<endl; ????cout?<<?list1->LocateElem(&tmp)?<<?endl;//注意是傳地址 ????list1->PriorElem(&e4,&tmp); ????cout<<"前驅(qū):"?<<?tmp?<<endl; ????list1->NextElem(&e4,&tmp); ????cout<<"后繼:"?<<?tmp?<<endl; ????delete?list1; ????list1?=?NULL; ????return?0; }
查看全部 -
順序表編碼:
查看全部 -
什么是線性表:n個?數(shù)據(jù)元素的有限序列
線性表分為?
?? ?1.順序表(數(shù)組) ?2.鏈表
鏈表:
1.靜態(tài)鏈表
2.單鏈表
3.循環(huán)鏈表
4.雙向鏈表
線性表的應(yīng)用場景:通訊錄、一元多項式
查看全部 -
頭結(jié)點沒有數(shù)據(jù)域?
查看全部 -
取出第N個節(jié)點的數(shù)據(jù),只需要找到該節(jié)點,將data部分賦值出去則可
查看全部 -
刪除第N個節(jié)點
思路:需保留第N個節(jié)點的上一個節(jié)點
將當(dāng)前的節(jié)點的next賦值給上一個節(jié)點的next則可,再釋放掉當(dāng)前節(jié)點
查看全部 -
鏈表插入到第N個節(jié)點
原理都是找到要使用的當(dāng)前節(jié)點,新結(jié)點被當(dāng)前節(jié)點指,前節(jié)點的next賦值給新結(jié)點的next
查看全部 -
鏈表尾部插入新結(jié)點
思路:先找到最后一個節(jié)點,在申請一個新結(jié)點,再讓最后一個節(jié)點的next指向新結(jié)點,并且傳參的節(jié)點只取了其中的數(shù)據(jù),指針是自己new出來的
查看全部 -
鏈表在頭部插入新結(jié)點
思路:其實是放到頭節(jié)點后的第一個位置
并且傳參的節(jié)點只取了其中的數(shù)據(jù),指針是自己new出來的
查看全部 -
循環(huán)清空鏈表的數(shù)據(jù)? 將當(dāng)前的下一個指針賦值給臨時指針 刪掉當(dāng)前指針 再將臨時指針賦值給當(dāng)前指針
查看全部 -
鏈表:指針域 數(shù)據(jù)域 頭結(jié)點 節(jié)點
查看全部 -
順序表缺點:插入刪除元素時,順序表需前移或者后移
查看全部 -
順序表鏈表互為補(bǔ)充
查看全部
舉報