线性表（线性存储、链式存储）

1 线性表的顺序储存结构及实现

1.1 静态一维数组（类）

const int MAXSIZE = 100; class SqList1 { private: int elem[MAXSIZE];//一维数组 int length; //线性表长度 public: SqList1() {}; };

1.2 动态一维数组（模板类）

//create template <class ItemType> class SqList2 { private: ItemType *elem; int length; //实际长度 int maxlen; //最大容量 public: SqList2(int _MAXLEN) { elem = new ItemType[_MAXLEN]; this->maxlen = _MAXLEN; } }; //use SqList2<int> sq(18);

1.3 顺序表类的定义及实现

插入删除 //类及定义 const int _MAXSIZE = 100; template <class ElemType> class SqList { private: ElemType elem[_MAXSIZE]; int length; public: SqList(); //构造 ~SqList(); //析构 void create(); //创建 void printOut(); //输出线性表 void insert(int pos, ElemType e); //插入 bool del(int pos); //删除 }; //实现 template <class ElemType> SqList<ElemType>::SqList(){this->length = 0;} //构造函数 构造空表 template <class ElemType> void SqList<ElemType>::create() { cout << "\n Input length = "; cin >> this->length; for(int i = 0; i < this->length; i++) cin >> this->elem[i]; } template <class ElemType> void SqList<ElemType>::printOut() { cout << "********DATA***********" << endl; for(int i = 0; i < this->length; i++) cout << i << " : " << this->elem[i] << setw(6); cout << endl; cout << "********DATA***********" << endl; } template <class ElemType> void SqList<ElemType>::insert(int pos, ElemType e) { //[11, 22, 33] //起始为1 在第pos处插入元素e，即在idx(pos-1, pos)中间插入e //其中 1 <= pos <= length .. (3) //则 0 <= idx <= length-1 int idx = pos-1; //要插入的索引位置 if(idx < 0 || idx > this->length) { cout << "insert idx is error!" << endl; } else { //移动elem[i:]的元素 for(int j = this->length; j > idx; j--) this->elem[j] = this->elem[j-1]; this->elem[idx] = e; //插入 this->length++; //更新长度 } } template <class ElemType> bool SqList<ElemType>::del(int pos) { int idx = pos - 1; //要删除的索引位置 idx->[0, length-1] if(idx < 0 || idx > this->length - 1) { cout << "del idx is error!" << endl; return false; } else { //[11, 22, 33] idx->[idx, length-1) //elem[length-1] 是最后一个元素 for(; idx < this->length - 1; idx++) this->elem[idx] = this->elem[idx+1]; this->length--; return true; } } //for test int pos, e; SqList<int> *sql = new SqList<int>; sql->create(); sql->printOut(); cout << "\nInput pos, e: "; cin >> pos >> e; sql->insert(pos, e); sql->printOut(); cout << "\nInput del pos:"; cin >> pos; sql->del(pos); sql->printOut();

2 线性表的链表储存结构及实现

2.1 指针、结点

1 指针 int *a; int b = 10; a = &b; // address:0x61fe78 num:10 cout << "address:" << a << setw(5) << "num:" << *a << endl;

---

2 结点 //链表 Node typedef int ElemType; struct NodeType { ElemType data; //数据域 存储数据 NodeType *next; //指针域 存储下一个结点的首地址（不用时，置为NULL) };

2.2 链表

2.2.1 函数实现链表

// DEFINE typedef struct Node { int data; //数据域 Node *next; //指针域 }NODE; Node *createLinkList(int n) { Node *head = new Node; //头结点，不存储数据 head->data = 0; head->next = NULL; Node *pre = head; for(int i = 0; i < n; i++) { Node *p = new Node; cout << "\n Input data:"; cin >> p->data; p->next = NULL; pre->next = p; pre = p; } return head; } void printLinkList(Node *head) { Node *p = head->next; while (p != NULL) { cout << "data:" << p->data << endl; p = p->next; } } // USE Node *head = createLinkList(3); printLinkList(head);

2.2.2 类实现链表

#include <iostream> #include <string.h> #include <iomanip> using namespace std; typedef struct Node { string name; int age; Node *next; }NODE; class LinkList { private: NODE *head; public: LinkList(); ~LinkList(); public: void create(int n); void insert(int pos, string name, int age); void del(int pos); void printOut(); int length(); }; LinkList::LinkList() { this->head = new Node; this->head->next = NULL; } // insert void LinkList::create(int n) { string name; int age; Node *pre = this->head; for(int i = 0; i < n; i++) { Node * p = new Node; cout << "Input Name : "; cin >> p->name; cout << "Input Age : "; cin >> p->age; p->next = NULL; pre->next = p; pre = p; } } void LinkList::printOut() { Node *p = this->head->next; while (p != NULL) { cout << "Name : " << p->name << " " << "Age : " << p->age << endl; p = p->next; } } void LinkList::insert(int pos, string name, int age) { if(pos < 1 || pos > this->length()) throw "out of range!!"; Node *pre = this->head; for(int i = 1; i < pos; i++) pre = pre->next; Node * insE = new Node; insE->name = name; insE->age = age; insE->next = pre->next; pre->next = insE; } void LinkList::del(int pos) { if(pos < 1 || pos > this->length()) throw "out of range!!"; Node *pre = this->head; for(int i = 1; i < pos; i++) pre = pre->next; Node *delNode = pre->next; //[1]要被删除的点 pre->next = pre->next->next; delete delNode; //[2]释放 } int LinkList::length() { int count = 0; Node * p = this->head->next; while (p != NULL) { count++; p = p->next; } return count; } int main() { LinkList *LL = new LinkList(); LL->create(2); LL->printOut(); cout << "***********" << endl; LL->insert(2, "zph", 17); LL->printOut(); cout << "***********" << endl; LL->del(3); LL->printOut(); cout << "xhh" << endl; return 0; }