数据结构-链表（链表的基本实现C++）
本文共 9069 字，大约阅读时间需要 30 分钟。
线性表是最常用而且简单的一种数据结构，一个线性表是n个数据元素的有限序列。
当线性表需要频繁查找，较少插入和删除时，通常采用顺序存储结构，若需要频繁插入和删除，通常采用基于链表的形式；当线性表的元素个数变化较大或不确定时，最好用链表，这样不需要考虑存储空间大小问题，当事先知道线性表的大小长度，用顺序存储结构效率会高一些。
1、线性表的顺序表示和实现
顺序表，基于数组的一种实现，一组地址连续的存储单元。顺序表可以是动态的，也可以是静态的，“静态”就是一开始就知道表容量，并且这个容量在之后无法被更改；“动态”就是能够动态的改变表的容量，实现上基于动态内存分配。数组大小有两种方式指定，一是静态分配，二是动态扩展。
优点：查找很方便
缺点：插入元素、删除元素比较麻烦，时间复杂度 O(n)
顺序表实现：
#include#include #include "assert.h"const int MAXSIZE = 512;template class SeqList {public: SeqList() { length = 0; } //默认构造函数 SeqList(const T a[], int n); //含参构造函数 int GetLength() { return length; } //获取长度 void Insert(int i, T x); //插入元素 T Delete(int i); //删除元素 T Get(int i); //通过下标获取元素 int Locate(T x); //通过元素值查找元素 void Print(); //打印输出private: int length; T data[MAXSIZE];};template SeqList ::SeqList(const T a[], int n) { if (n > MAXSIZE) { throw "超过顺序表的最大长度"; } for (int i = 0; i < n; i++) { data[i] = a[i]; } length = n;}template void SeqList ::Insert(int i, T x) { if (length > MAXSIZE) throw "上溢异常"; if (i<0 || i>length) throw "位置异常"; for (int j = length; j >= i; j--) { data[j] = data[j - 1]; } data[i] = x; length++;}template T SeqList ::Delete(int i) { if (length == 0) throw "下溢异常"; if (i<0 || i>=length) { throw "位置异常"; } T x = data[i]; for (int j = i; j < length - 1; j++) { data[j] = data[j + 1]; } length--; return x;}template T SeqList ::Get(int i) { if (0 == length) throw"上溢异常"; if (i<0 || i>=length) { throw "查找位置非法"; } return data[i];}template int SeqList ::Locate(const T x) { for (int i = 0; i < length; i++) { if (x == data[i]) return i; } return 0;}template void SeqList ::Print() { cout << "遍历线性表数据元素：" << endl; for (int i = 0; i < length; i++) { cout << data[i] << " "; } cout << endl;}
2、线性表的链式表示和实现
顺序表的链式表示形式又分为了：单链表、双向链表、单循环链表、双向循环链表几种。
优点：插入或删除元素时很方便，使用灵活，存储空间利用率高。
缺点：存储密度小（<1），查找和修改需要遍历整个链表。
单链表
代码实现：
#include#include #include "assert.h"template class LNode{public: T data; LNode * next;};template class LinkList {public: LinkList() { head = nullptr; } ~LinkList(); bool clear(); bool empty() { return head == nullptr; }; int length(); bool getElem(int i, T& t); int locateElem(const T& t); bool priorElem(const T& t_cur, T& t_pre); bool nextElem(const T& t_cur, T& t_next); bool insert(int i, T t); bool term(int i, T t); LNode * reverse();private: LNode * head;};//清空函数template bool LinkList ::clear() { LNode *p = head; while (head) { p = head; head = head->next; delete(p); } return true;}//析构函数template LinkList ::~LinkList() { clear();}//获取链表长度template int LinkList ::length() { LNode * p = head; //不能直接用head循环 int len = 0; while (p != nullptr) { len++; p = p->next; } return len;}//获取指定位置元素template bool LinkList ::getElem(int i, T &t) { int j = 0; LNode * p = head; while (j < i && p) { p = p->next; j++; } if (p == nullptr) return false; t = p->data; return true;}//查找元素位置template int LinkList ::locateElem(const T& t) { int loc = 0; LNode * p = head; while (p->data!=t && p) { p = p->next; loc++; } if (p->data == t) return loc; else return -1;}//获取前驱节点template bool LinkList ::priorElem(const T& t_cur, T& t_pre) { LNode * p = head; if (p->data == t_cur) return false; while (p->next->data != t_cur && p->next) { p = p->next; } if (p->next->data == t_cur) { t_pre = p->data; return true; } return false;}//获取后继节点template bool LinkList ::nextElem(const T& t_cur, T& t_next) { LNode * p = head; if (head == nullptr || head->next == nullptr) return false; while (p->next != nullptr) { if (p->data == t_cur) { t_next = p->next->data; return true; } else p = p->next; } return false;}template bool LinkList ::insert(int i, T t) { LNode * p = head; LNode * s = head; int loc = 0; if (i == 0) { s = (LNode *)malloc(sizeof(LNode )); s->data = t; s->next = p; head = s; return true; } while (p && loc < i - 1) { p = p->next; loc++; } if (p == nullptr) return false; s = (LNode *)malloc(sizeof(LNode )); s->data = t; s->next = p->next; p->next = s; return true;}//删除指定位置元素template bool LinkList ::term(int i, T t) { LNode * p = head; int loc = 0; if (i == 0) { t = head->data; head = head->next; delete p; p = nullptr; return true; } while (p && loc < i - 1) { loc++; p = p->next; } if (p == nullptr) return false; LNode* s; s = p->next; p->next = p->next->next; t = s->data; delete s; s = NULL; return true;}//反转链表template LNode * LinkList ::reverse() { if (head == nullptr || head->next == nullptr) return head; LNode *p = head, *q = head->next, *r; head->next = nullptr; while (q) { r = q->next; q->next = p; p = q; q = r; } head = p; return head;}
双向链表
代码实现：
#include#include #include "assert.h"template class DNode{public: DNode *next; DNode *prev; T data;};template class List{public: List();//默认构造函数 List(const List& ln);//拷贝构造函数 ~List();//析构函数 void add(T e);//向链表添加数据 void remove(T index);//移除某个结点 T find(int index);//查找结点 bool empty();//判断是否为空 int size();//链表长度 void print();//显示链表 void print_reverse();//链表反向显示 void clear();//删除全部结点private: DNode *head; DNode *tail; int length;};//默认构造函数template List ::List(){ head = new DNode ; tail = new DNode ; head->next = tail; head->prev = nullptr; tail->next = nullptr; tail->prev = head; length = 0;}//拷贝构造函数template List ::List(const List &ln){ head = new DNode ; head->prev = nullptr; tail = new DNode ; head->next = tail; tail->prev = head; length = 0; DNode * temp = ln.head; while (temp->next != ln.tail) { temp = temp->next; tail->data = temp->data; DNode *p = new DNode ; p->prev = tail; tail->next = p; tail = p; length++; } tail->next = nullptr;}//析构函数template List ::~List(){ if (length == 0) { delete head; delete tail; head = nullptr; tail = nullptr; return; } while (head->next != nullptr) { DNode *temp = head; head = head->next; delete temp; } delete head; head = nullptr;}//向链表添加数据template void List ::add(T e){ DNode * temp = this->tail; tail->data = e; tail->next = new DNode ; DNode *p = tail; tail = tail->next; tail->prev = p; tail->next = nullptr; length++;}//查找结点template T List ::find(int index){ if (length == 0) { std::cout << "List is empty"; return NULL; } if (index >= length) { std::cout << "Out of bounds"; return NULL; } int x = 0; DNode *p; p = head->next; while (p->next != nullptr && x++ != index) { p = p->next; } return p->data;}//删除结点template void List ::remove(T index){ if (length == 0) { std::cout << "List is empty"; return; } DNode *p = head; while (p->next != nullptr) { p = p->next; if (p->data == index) { DNode *temp = p->prev; temp->next = p->next; p->next->prev = temp; delete p; length--; return; } }}//删除所有结点template void List ::clear(){ if (length == 0) { return; } DNode *p = head->next; while (p != tail) { DNode * temp = p; p = p->next; delete temp; } head->next = tail; tail->prev = head; length = 0;}//判断是否为空template bool List ::empty(){ if (length == 0) { return true; } else { return false; }}//链表长度template int List ::size(){ return length;}//输出链表template void List ::print(){ if (length == 0) { std::cout << "List is empty" << std::endl; return; } DNode *p = head->next; while (p != tail) { std::cout << p->data << " "; p = p->next; } std::cout << std::endl;}//反向输出链表template void List ::print_reverse(){ if (length == 0)return; DNode *p = tail->prev; while (p != head) { std::cout << p->data << " "; p = p->prev; } std::cout << std::endl;}
测试类main.cpp:
#include "CList.hpp"#includeusing namespace std;int main(int argc, char**argv){ cout << "***顺序表***" << endl; SeqList seqList; int val = -1; int iLocate = -1; for (int i = 0; i < 10; i++) { seqList.Insert(i, i+1); } seqList.Print(); val = seqList.Get(3); cout << "seqList.Get(3): " << val << endl; val = seqList.Delete(2); cout << "seqList.Delete(2): " << val << endl; seqList.Print(); iLocate = seqList.Locate(5); cout << "seqList.Locate(5): " << val << endl; cout << endl; cout << "***单链表***" << endl; int a = 0; int *p = &a; LinkList linkList; linkList.insert(0, 5); linkList.insert(1, 4); linkList.insert(2, 12); linkList.insert(3, 5); linkList.insert(3, 6); linkList.insert(1, 7); cout << "链表长度" << linkList.length() << endl; cout << "各个元素的值是: "; for (int i = 0; i < linkList.length(); i++)//遍历该链表 { if (linkList.getElem(i, *p)) cout << *p << " "; } cout << endl; cout << "反转后各个元素的值是: "; LNode * re_linkList = linkList.reverse(); while (re_linkList) { cout << re_linkList->data << " "; re_linkList = re_linkList->next; } cout << endl; cout << endl; cout << "***双向链表***" << endl; List list; list.add(6); list.add(443); list.add(767); list.add(56); List list2(list); list2.print_reverse(); list2.print(); std::cout << "list2.size(): " << list2.size() << std::endl; std::cout << "list2.find(2): " << list2.find(2) << std::endl; list2.remove(443); list2.print(); system("pause"); return 0;}
执行结果：
--|END|--
转载地址：http://seiii.baihongyu.com/
你可能感兴趣的文章
C++虚函数的总结
查看>>
什么是URL地址？
查看>>
C++多态的实现方式总结
查看>>
学习C++需要注意的问题
查看>>
C++模板
查看>>
C++双冒号（：：）的用法
查看>>
【Unity】封装SQLite管理类
查看>>
【Unity】面试题整理
查看>>
【C#】如何实现一个迭代器
查看>>
【Unity】Destroy和DestroyImmediate的区别
查看>>
【Lua】Mac系统下配置SublimeText的Lua编译环境
查看>>
【C#】利用Conditional属性完成编译忽略
查看>>
【Unity】微信登录后将头像存为bytes，将bytes读取成sprite图片
查看>>
【Unity】使用GPS定位经纬度
查看>>
【UGUI/NGUI】一键换Text/Label字体
查看>>
【C#】身份证本地验证
查看>>
【Unity】坑爹的Bug
查看>>
【算法】求数组中某两个数的和为目标值
查看>>
如何高效学习动态规划？
查看>>
动态规划法（六）鸡蛋掉落问题（一）
查看>>