锐客网

  1. 首页 > it技术 > >

数据结构——线性表

本文贴出顺序表、链表 的例子代码，以及实例通讯录的代码。
文中代码均已在VS2015上测试，空指针均为nullptr（C++11）。参考来源：慕课网
线性表 线性表是n个数据元素的有限序列。

  • 分类：顺序表（即数组）、链表（分为 静态链表、单链表、循环链表、双向链表）
  • 应用场景：通讯录、一元多项式
顺序表 前驱、后继
BOOL InitList(List **list); //创建线性表 void DestroyList(List *list); //销毁线性表 void CleanList(List *list); //清空线性表 BOOL ListEmpty(List *list); //判断线性表是否是空 int ListLength(List *list); //获取线性表长度 BOOL GetElem(List *list,int i,Elem *e); //获取指定元素 int LocateElem(List *list,Elem *e); //寻找第一个满足e的数据元素的位序 BOOL PriorElem(List *list,Elem *currentElem,Elem *preElem); //获取指定元素的前驱 BOOL NextElem(List *list,Elem *currentElem,Elem *nextElem); //获取指定元素的后继 BOOL ListInsert(List *list,int i,Elem *e); //在第i个位置上插入元素 BOOL ListDelete(List *list,int i,Elem *e); //删除第i个位置的元素 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++实现[MyList.cpp]*/ /******************************/ #include "MyList.h" #include 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; }/******************************/ /*顺序表使用实例[Main.cpp]*/ /******************************/ #include "MyList.h" #include 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 <NextElem(&e4, &temp); cout << temp << endl; delete list1; list1 = nullptr; return 0; }

链表 结点：头结点、数据域、指针域。
分类：
数据结构——线性表
文章图片
链表 示例：
#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++实现[MyList.cpp]*/ /******************************/ #include "MyList.h" #include using namespace std; MyList::MyList() { m_pList = new MyNode; m_pList->data = https://www.it610.com/article/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 = https://www.it610.com/article/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 =https://www.it610.com/article/= 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=https://www.it610.com/article/= pCurrentNode->data) { if (tempNode==m_pList) { return false; } pPreNode->data = https://www.it610.com/article/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 =https://www.it610.com/article/= pCurrentNode->data) { if (currentNode->next == nullptr) { return false; } pNextNode->data = https://www.it610.com/article/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; knext; } MyNode *newNode = new MyNode; if (newNode==nullptr) { return false; } newNode->data = https://www.it610.com/article/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 = https://www.it610.com/article/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 = https://www.it610.com/article/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 = https://www.it610.com/article/pNode->data; newNode->next = nullptr; currentNode->next = newNode; m_iLength++; return true; }/******************************/ /*结点类C++头文件[MyNode.h]*/ /******************************/ #ifndef MYNODE_H #define MYNODE_H #include using namespace std; class MyNode { public: int data; MyNode *next; void printNode(); }; #endif/******************************/ /*结点类C++实现[MyNode.cpp]*/ /******************************/ #include "MyNode.h" #include using namespace std; void MyNode::printNode() { cout << data << " "; }/******************************/ /*单链表使用实例[Main.cpp]*/ /******************************/ #include "MyList.h" #include using namespace std; int main() { MyNode node1; node1.data = https://www.it610.com/article/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 <GetElem(1,&temp); cout << temp.data << endl; //取前驱 pList->PriorElem(&node4, &temp); cout << temp.data << endl; //取后继 pList->NextElem(&node4, &temp); cout << temp.data << endl; //元素位置 cout

进阶（通讯录实现） 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"//不加总是报错（VS2015中） #include using namespace std; MyList::MyList() { m_pList = new MyNode; //m_pList->data = https://www.it610.com/article/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 = https://www.it610.com/article/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 =https://www.it610.com/article/= 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=https://www.it610.com/article/= pCurrentNode->data) { if (tempNode==m_pList) { return false; } pPreNode->data = https://www.it610.com/article/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 =https://www.it610.com/article/= pCurrentNode->data) { if (currentNode->next == nullptr) { return false; } pNextNode->data = https://www.it610.com/article/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; knext; } MyNode *newNode = new MyNode; if (newNode==nullptr) { return false; } newNode->data = https://www.it610.com/article/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 = https://www.it610.com/article/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 = https://www.it610.com/article/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 = https://www.it610.com/article/pNode->data; newNode->next = nullptr; currentNode->next = newNode; m_iLength++; return true; }

MyNode.h
#ifndef MYNODE_H #define MYNODE_H #include "Person.h" #include using namespace std; class MyNode { public: Person data; MyNode *next; void printNode(); }; #endif

MyNode.cpp
#include "MyNode.h" #include using namespace std; void MyNode::printNode() { cout << data << " "; }

Person.h
#ifndef PERSON_H #define PERSON_H#include #include 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 using namespace std; int menu() { cout << "功能菜单" << endl; cout << "1.新建联系人" << endl; //cout << "2.删除联系人" << endl; cout << "3.浏览通讯录" << endl; cout << "4.退出通讯录" << endl; int order; cout << "请输入:" << ends; cin >> order; return order; } void createPerson(MyList *pList) { MyNode node; Person person; cout << "请输入姓名：" << ends; cin >> person.name; cout << "请输入电话：" << ends; cin >> person.phone; node.data = https://www.it610.com/article/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; }

    推荐阅读


    上一篇：儿时的年味|儿时的年味|年，还是老家过的有味道

    下一篇：三分钟弄懂iPhone|三分钟弄懂iPhone X 设计尺寸和适配