本文貼出順序表碑幅、鏈表 的例子代碼热芹,以及實(shí)例通訊錄的代碼斋荞。
文中代碼均已在VS2015上測(cè)試陌僵,空指針均為nullptr(C++11)轴合。參考來源:慕課網(wǎng)
線性表
線性表是n個(gè)數(shù)據(jù)元素的有限序列。
分類:順序表(即數(shù)組)碗短、鏈表(分為 靜態(tài)鏈表值桩、單鏈表、循環(huán)鏈表豪椿、雙向鏈表)
應(yīng)用場(chǎng)景:通訊錄奔坟、一元多項(xiàng)式
順序表
前驅(qū)、后繼
BOOL InitList(List **list);//創(chuàng)建線性表
void DestroyList(List *list);//銷毀線性表
void CleanList(List *list);//清空線性表
BOOL ListEmpty(List *list);//判斷線性表是否是空
int ListLength(List *list);//獲取線性表長(zhǎng)度
BOOL GetElem(List *list,int i,Elem *e);//獲取指定元素
int LocateElem(List *list,Elem *e);//尋找第一個(gè)滿足e的數(shù)據(jù)元素的位序
BOOL PriorElem(List *list,Elem *currentElem,Elem *preElem);//獲取指定元素的前驅(qū)
BOOL NextElem(List *list,Elem *currentElem,Elem *nextElem);//獲取指定元素的后繼
BOOL ListInsert(List *list,int i,Elem *e);//在第i個(gè)位置上插入元素
BOOL ListDelete(List *list,int i,Elem *e);//刪除第i個(gè)位置的元素
void ListTraverse(List *list);//遍歷線性表
示例:
#ifndef MYLIST_H
#define MYLIST_H
/****************************/
/*順序表C++類[MyList.h] */
/****************************/
class MyList
{
public:
MyList(int size);
~MyList();
void CleanList();
bool ListEmpty();
int ListLength();
bool GetElem(int i, int *e);
int LocateElem(int *e);
bool PriorElem(int *currentElem, int *preElem);
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 // !MYLIST_H
/******************************/
/*順序表C++實(shí)現(xiàn)[MyList.cpp] */
/******************************/
#include "MyList.h"
#include <iostream>
using namespace std;
MyList::MyList(int size)
{
m_iSize = size;
m_pList = new int[m_iSize];
m_iLength = 0;
}
MyList::~MyList()
{
delete []m_pList;
m_pList = nullptr;
}
void MyList::CleanList()
{
m_iLength = 0;
}
bool MyList::ListEmpty()
{
//return m_iLength==0?true:false;
if (m_iLength == 0)
{
return true;
}
return false;
}
int MyList::ListLength()
{
return m_iLength;
}
bool MyList::GetElem(int i, int * e)
{
if (i < 0 || i >= m_iLength)
{
return false;
}
else
{
*e = m_pList[i];
return true;
}
}
int MyList::LocateElem(int * e)
{
for (int i = 0;i < m_iLength;i++)
{
if (m_pList[i] == *e)
{
return i;
}
}
return -1;
}
bool MyList::PriorElem(int * currentElem, int * preElem)
{
int temp = LocateElem(currentElem);
if (temp == -1)
{
return false;
}
else if (temp == 0)
{
return false;
}
else
{
*preElem = m_pList[temp - 1];
return true;
}
}
bool MyList::NextElem(int * currentElem, int * nextElem)
{
int temp = LocateElem(currentElem);
if (temp == -1)
{
return false;
}
else if (temp == m_iLength - 1)
{
return false;
}
else
{
*nextElem = m_pList[temp + 1];
return true;
}
}
bool MyList::ListInsert(int i, int * e)
{
if (i<0 || i>m_iLength)
{
return false;
}
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 MyList::ListDelete(int i, int * e)
{
if (i < 0 || i >= m_iLength)
{
return false;
}
*e = m_pList[i];
for (int k = i;k < m_iLength - 1;k++)
{
m_pList[k] = m_pList[k + 1];
}
m_iLength--;
return true;
}
void MyList::ListTraverse()
{
for (int i = 0;i < m_iLength;i++)
{
cout << m_pList[i] << " ";
}
cout << endl;
}
/******************************/
/*順序表使用實(shí)例[Main.cpp] */
/******************************/
#include "MyList.h"
#include <iostream>
using namespace std;
int main(void)
{
int e1 = 3;
int e2 = 5;
int e3 = 7;
int e4 = 2;
int e5 = 9;
int e6 = 1;
int e7 = 8;
int e8 = 10;
int temp = -1;
MyList *list1 = new MyList(10);
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->ListInsert(6, &e7);
cout << list1->ListLength() << endl;
list1->ListTraverse();
/*cout << list1->ListEmpty() << endl;
list1->CleanList();
cout << list1->ListEmpty() << endl;
list1->ListInsert(0, &e8);
list1->ListTraverse();
list1->ListDelete(0, &temp);
cout << temp << endl;
cout << list1->ListLength() << endl;*/
if (list1->GetElem(0, &temp))
{
cout << temp << endl;
}
temp = 8;
int m = list1->LocateElem(&temp);
if(m!=-1)
cout << m << endl;
list1->PriorElem(&e4, &temp);
cout <<temp<< endl;
list1->NextElem(&e4, &temp);
cout << temp << endl;
delete list1;
list1 = nullptr;
return 0;
}
鏈表
結(jié)點(diǎn):頭結(jié)點(diǎn)搭盾、數(shù)據(jù)域咳秉、指針域。
分類:
示例:
#ifndef MYLIST_H
#define MYLIST_H
/****************************/
/*單鏈表C++類[MyList.h] */
/****************************/
#include "MyNode.h"
class MyList
{
public:
MyList();
~MyList();
void ClearList();
bool ListEmpty();
int ListLength();
bool GetElem(int i,MyNode *pNode);
int LocateElem(MyNode *pNode);
bool PriorElem(MyNode *pCurrentNode, MyNode *pPreNode);
bool NextElem(MyNode *pCurrentNode, MyNode *pNextNode);
void ListTraverse();
bool ListInsert(int i, MyNode *pNode);
bool ListDelete(int i, MyNode *pNode);
bool ListInsertHead(MyNode *pNode);
bool ListInsertTail(MyNode *pNode);
private:
MyNode *m_pList;
int m_iLength;
};
#endif
/******************************/
/*單鏈表C++實(shí)現(xiàn)[MyList.cpp] */
/******************************/
#include "MyList.h"
#include<iostream>
using namespace std;
MyList::MyList()
{
m_pList = new MyNode;
m_pList->data = 0;
m_pList->next = nullptr;
m_iLength = 0;
}
MyList::~MyList()
{
ClearList();
delete m_pList;
m_pList = nullptr;
}
void MyList::ClearList()
{
MyNode *currentNode = m_pList->next;
while (currentNode != nullptr)
{
MyNode *temp = currentNode->next;
delete currentNode;
currentNode = temp;
}
m_pList->next = nullptr;
}
bool MyList::ListEmpty()
{
if (m_iLength == 0)
{
return true;
}
return false;
}
int MyList::ListLength()
{
return m_iLength;
}
bool MyList::GetElem(int i, MyNode * pNode)
{
if (i < 0 || i >= m_iLength)
{
return false;
}
MyNode *currentNode = m_pList;
MyNode *currentNodeBefore = nullptr;
for (int k = 0;k <= i;k++)
{
currentNodeBefore = currentNode;
currentNode = currentNode->next;
}
pNode->data = currentNode->data;
return true;
}
int MyList::LocateElem(MyNode * pNode)
{
MyNode *currentNode = m_pList;
int count = 0;
while (currentNode->next != nullptr)
{
currentNode = currentNode->next;
if (currentNode->data == pNode->data)
{
return count;
}
count++;
}
return -1;
}
bool MyList::PriorElem(MyNode * pCurrentNode, MyNode * pPreNode)
{
MyNode *currentNode = m_pList;
MyNode *tempNode = nullptr;
while (currentNode->next!=nullptr)
{
tempNode = currentNode;
currentNode = currentNode->next;
if (currentNode->data== pCurrentNode->data)
{
if (tempNode==m_pList)
{
return false;
}
pPreNode->data = tempNode->data;
return true;
}
}
return false;
}
bool MyList::NextElem(MyNode * pCurrentNode, MyNode * pNextNode)
{
MyNode *currentNode = m_pList;
while (currentNode->next!=nullptr)
{
currentNode = currentNode->next;
if (currentNode->data == pCurrentNode->data)
{
if (currentNode->next == nullptr)
{
return false;
}
pNextNode->data = currentNode->next->data;
return true;
}
}
return false;
}
void MyList::ListTraverse()
{
MyNode *currentNode = m_pList;
while (currentNode->next!=nullptr)
{
currentNode = currentNode->next;
currentNode->printNode();
}
cout << endl;
}
bool MyList::ListInsert(int i, MyNode * pNode)
{
if (i<0 || i>m_iLength)
{
return false;
}
MyNode *currentNode = m_pList;
for (int k=0;k<i;k++)
{
currentNode = currentNode->next;
}
MyNode *newNode = new MyNode;
if (newNode==nullptr)
{
return false;
}
newNode->data = pNode->data;
newNode->next = currentNode->next;
currentNode->next = newNode;
m_iLength++;
return true;
}
bool MyList::ListDelete(int i, MyNode * pNode)
{
if (i<0||i>=m_iLength)
{
return false;
}
MyNode *currentNode = m_pList;
MyNode *currentNodeBefore = nullptr;
for (int k = 0;k <= i;k++)
{
currentNodeBefore = currentNode;
currentNode = currentNode->next;
}
currentNodeBefore->next = currentNode->next;
pNode->data = currentNode->data;
delete currentNode;
currentNode = nullptr;
m_iLength--;
return true;
}
bool MyList::ListInsertHead(MyNode * pNode)
{
MyNode *temp = m_pList->next;
MyNode *newNode = new MyNode;
if (newNode==nullptr)
{
return false;
}
newNode->data = pNode->data;
m_pList->next = newNode;
newNode->next = temp;
m_iLength++;
return true;
}
bool MyList::ListInsertTail(MyNode * pNode)
{
MyNode *currentNode = m_pList;
while (currentNode->next!=nullptr)
{
currentNode = currentNode->next;
}
MyNode *newNode = new MyNode;
if (newNode==nullptr)
{
return false;
}
newNode->data = pNode->data;
newNode->next = nullptr;
currentNode->next = newNode;
m_iLength++;
return true;
}
/******************************/
/*結(jié)點(diǎn)類C++頭文件[MyNode.h] */
/******************************/
#ifndef MYNODE_H
#define MYNODE_H
#include <iostream>
using namespace std;
class MyNode
{
public:
int data;
MyNode *next;
void printNode();
};
#endif
/******************************/
/*結(jié)點(diǎn)類C++實(shí)現(xiàn)[MyNode.cpp] */
/******************************/
#include "MyNode.h"
#include <iostream>
using namespace std;
void MyNode::printNode()
{
cout << data << " ";
}
/******************************/
/*單鏈表使用實(shí)例[Main.cpp] */
/******************************/
#include "MyList.h"
#include<iostream>
using namespace std;
int main()
{
MyNode node1;
node1.data = 1;
MyNode node2;
node2.data = 2;
MyNode node3;
node3.data = 3;
MyNode node4;
node4.data = 4;
MyNode node5;
node5.data = 5;
MyList *pList = new MyList();
//插入頭元素
pList->ListInsertHead(&node1);
pList->ListInsertHead(&node2);
pList->ListInsertHead(&node3);
pList->ListInsertHead(&node4);
pList->ListInsertHead(&node5);
//插入尾元素
pList->ListInsertTail(&node1);
pList->ListInsertTail(&node2);
pList->ListInsertTail(&node3);
pList->ListInsertTail(&node4);
pList->ListInsertTail(&node5);
pList->ListTraverse();
//在某位置插入元素
pList->ListInsert(1, &node5);
pList->ListTraverse();
MyNode temp;
//刪除某位置元素
pList->ListDelete(1, &temp);
pList->ListTraverse();
cout <<temp.data << endl;
//取某位置元素
pList->GetElem(1,&temp);
cout << temp.data << endl;
//取前驅(qū)
pList->PriorElem(&node4, &temp);
cout << temp.data << endl;
//取后繼
pList->NextElem(&node4, &temp);
cout << temp.data << endl;
//元素位置
cout<<pList->LocateElem(&node5)<<endl;
delete pList;
pList = nullptr;
return 0;
}
進(jìn)階(通訊錄實(shí)現(xiàn))
MyList.h
#ifndef MYLIST_H
#define MYLIST_H
#include "MyNode.h"
class MyList
{
public:
MyList();
~MyList();
void ClearList();
bool ListEmpty();
int ListLength();
bool GetElem(int i,MyNode *pNode);
int LocateElem(MyNode *pNode);
bool PriorElem(MyNode *pCurrentNode, MyNode *pPreNode);
bool NextElem(MyNode *pCurrentNode, MyNode *pNextNode);
void ListTraverse();
bool ListInsert(int i, MyNode *pNode);
bool ListDelete(int i, MyNode *pNode);
bool ListInsertHead(MyNode *pNode);
bool ListInsertTail(MyNode *pNode);
private:
MyNode *m_pList;
int m_iLength;
};
#endif
MyList.cpp
#include "MyList.h"
#include "MyNode.cpp"http://不加總是報(bào)錯(cuò)(VS2015中)
#include<iostream>
using namespace std;
MyList::MyList()
{
m_pList = new MyNode;
//m_pList->data = 0;
m_pList->next = nullptr;
m_iLength = 0;
}
MyList::~MyList()
{
ClearList();
delete m_pList;
m_pList = nullptr;
}
void MyList::ClearList()
{
MyNode *currentNode = m_pList->next;
while (currentNode != nullptr)
{
MyNode *temp = currentNode->next;
delete currentNode;
currentNode = temp;
}
m_pList->next = nullptr;
}
bool MyList::ListEmpty()
{
if (m_iLength == 0)
{
return true;
}
return false;
}
int MyList::ListLength()
{
return m_iLength;
}
bool MyList::GetElem(int i, MyNode * pNode)
{
if (i < 0 || i >= m_iLength)
{
return false;
}
MyNode *currentNode = m_pList;
MyNode *currentNodeBefore = nullptr;
for (int k = 0;k <= i;k++)
{
currentNodeBefore = currentNode;
currentNode = currentNode->next;
}
pNode->data = currentNode->data;
return true;
}
int MyList::LocateElem(MyNode * pNode)
{
MyNode *currentNode = m_pList;
int count = 0;
while (currentNode->next != nullptr)
{
currentNode = currentNode->next;
if (currentNode->data == pNode->data)
{
return count;
}
count++;
}
return -1;
}
bool MyList::PriorElem(MyNode * pCurrentNode, MyNode * pPreNode)
{
MyNode *currentNode = m_pList;
MyNode *tempNode = nullptr;
while (currentNode->next!=nullptr)
{
tempNode = currentNode;
currentNode = currentNode->next;
if (currentNode->data== pCurrentNode->data)
{
if (tempNode==m_pList)
{
return false;
}
pPreNode->data = tempNode->data;
return true;
}
}
return false;
}
bool MyList::NextElem(MyNode * pCurrentNode, MyNode * pNextNode)
{
MyNode *currentNode = m_pList;
while (currentNode->next!=nullptr)
{
currentNode = currentNode->next;
if (currentNode->data == pCurrentNode->data)
{
if (currentNode->next == nullptr)
{
return false;
}
pNextNode->data = currentNode->next->data;
return true;
}
}
return false;
}
void MyList::ListTraverse()
{
MyNode *currentNode = m_pList;
while (currentNode->next!=nullptr)
{
currentNode = currentNode->next;
currentNode->printNode();
}
cout << endl;
}
bool MyList::ListInsert(int i, MyNode * pNode)
{
if (i<0 || i>m_iLength)
{
return false;
}
MyNode *currentNode = m_pList;
for (int k=0;k<i;k++)
{
currentNode = currentNode->next;
}
MyNode *newNode = new MyNode;
if (newNode==nullptr)
{
return false;
}
newNode->data = pNode->data;
newNode->next = currentNode->next;
currentNode->next = newNode;
m_iLength++;
return true;
}
bool MyList::ListDelete(int i, MyNode * pNode)
{
if (i<0||i>=m_iLength)
{
return false;
}
MyNode *currentNode = m_pList;
MyNode *currentNodeBefore = nullptr;
for (int k = 0;k <= i;k++)
{
currentNodeBefore = currentNode;
currentNode = currentNode->next;
}
currentNodeBefore->next = currentNode->next;
pNode->data = currentNode->data;
delete currentNode;
currentNode = nullptr;
m_iLength--;
return true;
}
bool MyList::ListInsertHead(MyNode * pNode)
{
MyNode *temp = m_pList->next;
MyNode *newNode = new MyNode;
if (newNode==nullptr)
{
return false;
}
newNode->data = pNode->data;
m_pList->next = newNode;
newNode->next = temp;
m_iLength++;
return true;
}
bool MyList::ListInsertTail(MyNode * pNode)
{
MyNode *currentNode = m_pList;
while (currentNode->next!=nullptr)
{
currentNode = currentNode->next;
}
MyNode *newNode = new MyNode;
if (newNode==nullptr)
{
return false;
}
newNode->data = pNode->data;
newNode->next = nullptr;
currentNode->next = newNode;
m_iLength++;
return true;
}
MyNode.h
#ifndef MYNODE_H
#define MYNODE_H
#include "Person.h"
#include <iostream>
using namespace std;
class MyNode
{
public:
Person data;
MyNode *next;
void printNode();
};
#endif
MyNode.cpp
#include "MyNode.h"
#include <iostream>
using namespace std;
void MyNode::printNode()
{
cout << data << " ";
}
Person.h
#ifndef PERSON_H
#define PERSON_H
#include <string>
#include <ostream>
using namespace std;
class Person
{
friend ostream &operator<<(ostream &out, Person &person);
public:
string name;
string phone;
Person &operator=(Person &person);
bool operator==(Person &person);
};
#endif // !PERSON_H
Person.cpp
#include "Person.h"
Person & Person::operator=(Person & person)
{
this->name = person.name;
this->phone = person.phone;
return *this;
}
bool Person::operator==(Person &person)
{
if (this->name == person.name&&this->phone == person.phone)
{
return true;
}
return false;
}
ostream & operator<<(ostream & out, Person & person)
{
out << person.name << ":" << person.phone << " ";
return out;
}
Main.cpp
#include "MyList.h"
#include<iostream>
using namespace std;
int menu()
{
cout << "功能菜單" << endl;
cout << "1.新建聯(lián)系人" << endl;
//cout << "2.刪除聯(lián)系人" << endl;
cout << "3.瀏覽通訊錄" << endl;
cout << "4.退出通訊錄" << endl;
int order;
cout << "請(qǐng)輸入:" << ends;
cin >> order;
return order;
}
void createPerson(MyList *pList)
{
MyNode node;
Person person;
cout << "請(qǐng)輸入姓名:" << ends;
cin >> person.name;
cout << "請(qǐng)輸入電話:" << ends;
cin >> person.phone;
node.data = person;
pList->ListInsertTail(&node);
}
int main()
{
int userOrder=0;
MyList *pList = new MyList();
while (userOrder != 4)
{
userOrder = menu();
switch (userOrder)
{
case 1:
createPerson(pList);
break;
case 2:
break;
case 3:
cout << "liulan" << endl;
pList->ListTraverse();
break;
case 4:
exit(0);
default:
break;
}
}
delete pList;
pList = nullptr;
return 0;
}