线性表

2.1 线性表

1.定义 是零个或多个具有相同类型的数据元素的有序数列； （长度等于零的线性表为空表） *非空线性表通常记为： L ＝ ( a 1 ， a 2 ，……， a n ) 其中， a i （ 1 ≤ i ≤ n ）称为数据元素， 下标 i 表示该元素在线性表中的位置或序号， 称元素 a i 位于表的第 i 个位置，或称 a i 是表中的第 i 个元素。 每个元素之间存在唯一的顺序关系。

2.2 顺序表（顺序表支持数据元素的随机访问）

2.2.1 1.特点：线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素。 2.顺序存储的实现：一维数组存储顺序表中的数据。

设顺序表的每个元素占用 c 个存储单元，则第 i 个元素的存储地址为： 　　　LOC ( a i ) = LOC ( a 1 ) ＋ ( i － 1 ) × c 　　　 2.2.2　顺序表的实现

const int Maxsize=100; template <class T> class SeqList{ 　private: 　　T data[MaxSize]; // 存放数据元素的数组 　　int length; // 线性表的长度 　public: 　　SeqList ( ) ;// 无参构造函数 　　SeqList ( T a[ ], int n ) ; // 有参构造函数 　　~SeqList( ) { } // 析构函数为空 　　int Length ( ) {return length;} // 求线性表的长度 T Get ( int i ); // 按位查找，取线性表的第 i 个元素 　　int Locate ( T x ) ; // 按值查找，求线性表中值为 x 的元素序号 　　void Insert ( int i, T x ) ; // 在线性表中第 i 个位置插入值为 x 的元素 　　T Delete ( int i ) ; // 删除线性表的第 i 个元素 　　void PrintList ( ) ; // 遍历线性表，按序号依次输出各元素 };

2.2.3 构造函数

1.定义了两个构造函数： *无参构造函数（构造一个空的顺序表） SeqList ( ) {length=0;} *构造一个非空的顺序表 SeqList ( T a[ ], int n ) ; // 有参构造函数 *有参构造函数的实现： 将长度为n的一维数组中的元素依次传入到data中。

template <class T> SeqList<T>:: SeqList(T a[], int n) { if (n>MaxSize) throw "参数非法"; for (int i=0; i<n; i++) data[i]=a[i]; length=n; }

2.2.4 插入算法的实现

1 如果顺序表已满，抛出上溢异常 2 如果元素插入位置不存在，抛出位置异常 3 将最后一个元素至第i个元素（i为插入位置）向后移动一个位置 4 将元素插入到i位置 5 将顺序表的长度增1

template <class T> void SeqList<T>::Insert(int i, T x){ int j; if (length>=MaxSize) throw "上溢"; if (i<1 || i>length+1) throw "位置"; for (j=length; j>=i; j--) data[j]=data[j-1]; data[i-1]=x; length++; } 复杂度分析 *问题规模：n *最好情况：在最后插入，不需要移动元素，时间复杂性为O(1); *最坏情况：在开头插入，需要移动n个数据，O(n) *平均复杂性 *平均时间复杂度： 元素总个数为n，各个位置插入的概率相等为p＝1/(n+1 ) *平均移动元素次数为

2.2.5 删除算法的实现 1 如果顺序表已空，抛出下溢异常 2 如果元素插入位置不存在，抛出位置异常 3 取出被删除的元素 4 将下标为i，i+1…n-1的元素一次移到i-1,i,…n-2的位置 5 将顺序表的长度减1，返回被删除的元素

template <class T> T SeqList<T>::Delete(int i){ int j; T x; if (length==0) throw "下溢"; if (i<1 || i>length) throw "位置"; x=data[i-1]; for (j=i; j<length; j++) data[j-1]=data[j]; length--; return x; } 复杂度分析 最好情况：在最后删除，不需要移动元素，时间复杂性为O(1); 最坏情况：在开头删除，需要移动n-1个数据，O(n) 平均复杂性

删除算法的复杂性分析 元素总个数为n，各个位置删除的概率为p＝1/n 平均移动元素次数为 按位置查找

template <class T> T SeqList<T>::Get(int i) { if (i<1 && i>length) throw "查找位置非法"; else return data[i-1]; }

按位查找算法的时间复杂度为 O ( 1 ) 。

2.2 单链表

2.2.1 单链表的构造 头插法

template <class T> LinkList<T>:: LinkList(T a[ ], int n) { first=new Node<T>; //生成头结点 first->next=NULL; Node<T> *s; for (int i=0; i<n; i++){ s=new Node<T>; s->data=a[i]; //为每个数组元素建立一个结点 s->next=first->next; first->next=s; } }

尾插法

template <class T> LinkList<T>:: LinkList(T a[ ], int n) { Node<T> *r,*s; //尾指针 first=new Node<T>; //生成头结点 r=first; for (int i=0; i<n; i++) { s=new Node<T>; s->data=a[i]; //为每个数组元素建立一个结点 r->next=s; r=s; //插入到终端结点之后 } r->next=NULL; //单链表建立完毕，将终端结点的指针域置空 }

单链表的遍历

template <class T> LinkList<T>:: PrintList() { Node<T> *p; p=first->next; while(p) { cout<<p->data; p=p->next; } }

不带头结点的单链表的构造

头插法： { first=NULL; for(int i=0;i<n;i++) { s=new node<T>; s->data=a[i]; s->next=first; first=s; } } 尾插法： node<T> *r; head=NULL; if（n<=0）return; s=new node<T>; s->data=a[0]; s->next=head; head=s; r=head; for(int i=1;i<n;i++) { s=new node<T>; s->data=a[i]; r->next=s; r=s; }

单链表中按位置查找

template <class T> T LinkList<T>::Get(int i) { Node<T> *p; int j; p=first->next; j=1; //或p=first; j=0; while (p && j<i) { p=p->next; //工作指针p后移 j++; } if (!p) throw "位置"; else return p->data; }

单链表的插入

template <class T> void LinkList<T>::Insert(int i, T x){ Node<T> *p; int j; p=first ; j=0; //工作指针p初始化 while (p && j<i-1) { p=p->next; //工作指针p后移 j++; } if (!p) throw "位置"; else { Node<T> *s; s=new Node<T>; s->data=x; //向内存申请一个结点s，其数据域为x s->next=p->next; //将结点s插入到结点p之后 p->next=s; } } 不带头结点的插入： Insert(int i, T x){ Node<T> *p; int j; if（i<=0） throw “位置非法”； if （i==1 ）{ s=new Node<T>;s->next=head;head=s;return} p=first ; j=1; //工作指针p初始化 while (p && j<i-1) { p=p->next; //工作指针p后移 j++; } if (!p) throw "位置"; else { Node<T> *s; s=new Node<T>; s->data=x; //向内存申请一个结点s，其数据域为x s->next=p->next; //将结点s插入到结点p之后 p->next=s; } }

单链表的删除

template <class T> T LinkList<T>::Delete(int i){ Node<T> *p; int j; p=first ; j=0; //工作指针p初始化 while (p && j<i-1) { //查找第i-1个结点 p=p->next; j++; } if (!p || !p->next) throw "位置"; //结点p不存在或结点p的后继结点不存在 else { Node<T> *q; T x; q=p->next; x=q->data; //暂存被删结点 p->next=q->next; //摘链 delete q; return x; } }

析构函数

template <class T> LinkList<T>:: ~LinkList() { Node<T> *q; while (first) { q=first->next; delete first; first=q; } }

2.3循环链表

将单链表或者双链表的头尾结点链接起来，就是一个循环链表。 不增加额外存储花销，却给不少操作带来了方便 从循环表中任一结点出发，都能访问到表中其他结点。

头插法： template <class T> CycleLinkList<T>:: CycleLinkList(T a[ ], int n) { first=new Node<T>; //生成头结点 Node<T> *r,*s; r=first; //尾指针初始化 for (int i=0; i<n; i++) { s=new Node<T>; s->data=a[i]; r->next=s; r=s; } r->next=first; //单链表建立完毕，将终端结点的指针域指向头结点 } 尾插法： template <class T> CycleLinkList<T>:: CycleLinkList(T a[ ], int n,int k) { first=new Node<T>; //生成头结点 first->next=first; Node<T> *s; for (int i=1; i<n; i++) { s=new Node<T>; s->data=a[i]; //为每个数组元素建立一个结点 s->next=first->next; first->next=s; } }

双链表

结构特点： 由于在双向链表中既有前向链又有后向链，寻找任一个结点的直接前驱结点与直接后继结点变得非常方便。设指针p指向双链表中某一结点，则有下式成立：

p->llink->rlink = p = p->rlink->llink

双链表的实现： template class DoubleLink { private: Node *head; public: DoubleLink() ； ~DoubleLink(); void Append(T data); void Display(); void Insert(int locate , T data); T Get(int locate); T Delete(int locate); }; 双链表的构造： template DoubleLink ::DoubleLink(){ head=new Node; head->rlink=NULL; head->llink=NULL; } 头插： template void DoubleLink::Append(T data){ Node *s; s=new Node; s->data=data; s->rlink=head->rlink; head->rlink=s; s->llink=head; if (s->rlink) s->rlink->llink=s; return; } 遍历： template void DoubleLink::Display(){ Node *p; p=head->rlink; while§ { cout<data<<" "; p=p->rlink; } cout<<endl; return; } 析构： template DoubleLink::~DoubleLink(){ Node *p,*q; p=head; while§ { q=p->rlink; delete p; p=q;

}

}