数据结构笔记——线性表

思考：怎么编程解决多项式相加问题？

1.线性表概念

由同类型数据元素构成的有序序列的线性结构 1. 表中元素个数称为线性表的长度； 2. 线性表中没有元素时称为空表； 3. 表的起始位置称为表头，结束位置称为表尾。

2.线性表的ADT描述

类型名：线性表数据对象集：线性表是n(>=0)个元素构成的有序序列(a1,a2…,an)操作集： 1.SeqList():构造函数，初始化一个空线性表； 2.～SeqList():析构函数，释放线性表空间； 3.T FindKth(int K,SeqList L):根据位序K,返回相应元素； 4.int Find(T X,SeqList L):在线性表L中查找X第一次出现的位置； 5.void Insert(T X,inT i,SeqList L):在位序i前插入一个新元素X； 6.void Delete(int i,SeqList L)：删除指定位序i的元素； 7.int Length(SeqList L)：返回线性表L的长度n；

3.线性表的顺序存储实现

//代码未测试 #include <iostream> using namespace std; template <class T> class SeqList{ public: SeqList(maxSize); ~SeqList(); T FindKth(int K,SeqList s); int Find(T x,SeqList s); bool Insert(T X,int i,SeqList s);//插入时把元素放在下标i的位置上 bool Delete(int i,SeqList s); int Length(SeqList s){return n;}; private: int n; int maxSize; T *s; //二维数组用于存储线性表 }; template <class T> SeqList :: SeqList(maxSize){ T *s = new s[maxSize]; n = 0; } template <class T> SeqList :: ~SeqList(){ delete s[]; } template <class T> T SeqLIst::FindKth(int K,SeqList L){ int i=0; for(i=0;i<n;i++){ if(i==K) return s[i]; } return -1; } template <class T> int SeqList::Find(T x,SeqList s){ int i; for(i=0;i<n;i++){ if(s[i]==x) return i; } return -1; } template <class T> bool SeList::Insert(T X,inT i,SeqList L){ if(n==maxSize) return false; if(i<0||i>n) return false; //检测位置的合法性 int j; for(j=n-1;j>=i;j++){ s[j+1] = s[j]; } s[i] = X; n++; return true; } bool SeqList::Delete(int i,SeqList L){ if(n==0) return false; if(i<0||i>n-1) return false; //检测位置合法性 int j=0; for(j=i+1;j<n;j++){ s[j-1] = s[j]; } n--; return true; }

4.线性表的链式存储实现

特点：不要求逻辑上相邻的两个元素物理上也相邻，通过链建立起数据元素之间的逻辑关系。

//代码未测试可能有小错误 #include <iostream> using namespace std; template <class T> class TNode{ public: TNode(T X){ data = X; next = NULL; }; private: T data; TNode *next; }; class List{ public: List(); ~List(); int length(List* head); TNode* FindKth(int K,List* head);//查找链表中的第K个元素 TNode* Find(T X,List *head); TNode* Insert(T X,int i,List* head); TNode* Delete(int i,List* head); private: TNode *head; }; template <class T> int List::length(List* head){ TNode *p = head; int j = 0 while(p){ p = p->next; j++; } return j; } template <class T> TNode* List::FindKth(int K,List* head){ //返回一个TNode型的指针 TNode *p = head; int i = 1; while(p && i<K){ p = p->next; i++; } if(i==K) return p; else return NULL; } template <class T> TNode* List::Find(T X,List* head){ TNode *p = head; while(p && p->data!=X){ p = p->next; } // if(p->data==X) return p; // else return NULL; 这两句合起来就是return p； return p; } template <class T> TNode* List::Insert(T X,int i,List* head){ //插入在第i个元素前面,第i-1个元素后面 TNode *p = head; TNode *q = new TNode(X); if(i==1){ //插入在头节点之前 q->next = head; return q; } int j=1; while(p && j<i-1){ p = p->next; j++; } q->next = p->next; p->next = q; return head; } template <class T> TNode* List::Delete(int i,List* head){ //删除第i个元素 TNode *p = head; TNode *s = NULL; if(i==1) { //删除头节点 s = head; if(head) head = head->next; delete s; return head; } //删除非头节点 int j=1; while(j<i-1){ p = p->next; j++; } if(p && p->next){ //p和p->next均存在 s = p->next; p->next = s->next; delete s; return head; } }