（二）线性表

2017-06-20

线性表

　　最常用且最简单的一种数据结构
　　一个线性表是ｎ个数据元素的有限序列
　　一个数据元素可以由若干数据项组成，这种情况下，常把数据元素称为记录，含有大量记录的线性表又称为文件

抽象数据类型

ADT List{
　数据对象：D={ai|ai∈ElemSet,i=1,2,...,n,n≥0}
　数据关系：Rl={<ai-1,ai>|ai-1,ai∈D，i=2,...,n}
　基本操作：
　　InitList(&L)
　　　　操作结果：构造一个空的线性表L
　　DestroyList(&L)
　　　　初始条件：线性表L已存在
　　　　操作结果：销毁线性表L
　　ClearList(&L)
　　　　初始条件：线性表L已存在
　　　　操作结果：将L重置为空表
　　ListEmpty(L)
　　　　初始条件：线性表L;已存在
　　　　操作结果：若L为空表，则返回true，否则false
　　ListLength(L)
　　　　初始条件：线性表L已存在
　　　　操作结果：返回L中数据元素个数
　　GetElem(L,i,&e)
　　　　初始条件：线性表L已存在，1≤i≤ListLength(L)
　　　　操作结果：用e返回L中第i个数据元素的值
　　LocateElem(L,e,compare())
　　　　初始条件：线性表L已存在，compare()是数据元  素判定函数
　　　　操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。若此数据元素不存在，则返回值为0
　　PriorElem(L,cur_e,&pre_e)
　　　　初始条件：线性表L已存在
　　　　操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义
　　NextElem(L,cur_e,&next_e)
　　　　初始条件：线性表L已存在
　　　　操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义
　　ListInsert(&L,i,e)
　　　　初始条件：线性表L已存在，1≤i≤ListLength(L)+1
　　　　操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
　　ListDelete(&L,i,&e)
　　　　初始条件：线性表L已存在且非空，1≤i≤ListLength(L)
　　　　操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1
　　ListTraverse(L,visit())
　　　　初始条件：线性表L已存在
　　　　操作结果：依次对L的每个数据元素调用函数visit().一旦visit()失败，则操作失败。
　　}ADT List

线性表的存储表示

　　1.线性表的动态分配顺序存储结构

　　　#define LIST_INIT_SIZE 100 //线性表存储控件的初始分配量
　　　#define LISTINCREMENT 10 //线性表存储空间的分配增量
　　　typedef struct{
　　　　　ElemType *　elem; //存储空间基址，用于创建线性数组
　　　　　int length; //当前长度
　　　　　int listsize; //当前分配的存储容量（以sizeof(ElemType)为单位）
　　　}Sqlist；

　图示
　

　　插入：平均移动节点次数为n/2；
　　删除：平均移动节点次数为(n-1)/2；

　　2.线性表的静态单链表存储结构

　　　#define MAXSIZE 1000  //链表的最大长度
　　　typedef struct{
　　　　　ElemType data;  //节点数据
　　　　　int cur;  //游标代替指针指向下一个节点
　　　}componet,SLinkList[MAXSIZE];

　图示
　

　　3.线性表的链式存储结构

　　　typedef LNode{
　　　　　ElemType data; //结点数据
　　　　　struct LNode *　next; //指针域
　　　}LNode,*　LinkList;

　　　不带头结点的空表判定：L==NULL
　　　带头结点的空表判定：L->next=NULL
　　　循环单链表为空的判定：L.next=L
　　　线性链表的最后一个结点的指针为：NULL
　　　头结点的数据域为空，指针域指向第一个元素

　　　a．单向链表
　　　　　图示
　　　　　　单向链表图示
　　　　　头结点的作用：对开始节点的操作，插入删除无需特殊处理，统一了空表和非空表
　　　　　建立单链表
　　　　　　①头插法：s->next=head->next; head->next=s; 生成的顺序与输入顺序相反。平均时间复杂度O(n)
　　　　　　②尾插法:s->next=head->next; head->next=s; head=s;生成的顺序与输入顺序相同。平均时间复杂度为O(n)

*查找*：与查找位置有关，平均时间复杂度均为O(n)

*插入运算*：p=GetNode(L, i-1); s->next=p->next; p->next=s; 平均时间复杂度O(n)

*删除运算*：p=GetNode(L, i-1); s=p->next; p->next=s->next; free(s); 平均时间复杂度O(n)

　　　b.单向循环链表
　　　　　图示
　　　　　单向循环链表图示

　　　c.双向链表

　　　　typedef struct DuLNode{
  　　　　　 ElemType  data;
   　　　　　struct DuLNode  *　prior;  //指向前一个节点
  　　　　　 struct DuLNode  *　next;  //指向后一个节点
　　　　}DuLNode,*　DuLinkList;

　　　　图示
　　　　　

typedef struct{  //链表类型
　　Link head,tail; //分别指向线性链表中的头结点和最后一个节点
　　int len; //链表的数据元素个数
}LinkList;

顺序表和单链表的比较

　顺序表
　　优点：
　　　存储密度大，可随机存储
　　缺点：
　　　①大小固定；
　　　②不利于增减节点；
　　　③存储空间不能充分利用；
　　　④容量难扩充；
　链式存储
　　优点：
　　　①易于插入删除；
　　　②可动态申请空间；
　　　③表容量仅受内存空间限制；
　　缺点：
　　　①增加了存储空间的开销；
　　　②不可以随机存储元素；

顺序表代码

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

typedef int Status;
typedef int ElemType;

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10

typedef struct{
	ElemType * elem;
	int length;
	int listsize;
}SqList;

class LIST{
	public:
		Status InitList_Sq(SqList &L);
		Status ListInsert_Sq(SqList &L,int i,ElemType e);
		Status ListDelete_Sq(SqList &L,int i,ElemType &e);
		Status GetElem(SqList L,int i,ElemType &e);
		Status ChaElem(SqList &L,int i, ElemType e);
		Status ListTraverse(SqList L);
};

Status LIST::InitList_Sq(SqList &L){
	//构造一个空的线性表L
	L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
	if(!L.elem) exit(OVERFLOW);
	L.length=0;
	L.listsize=LIST_INIT_SIZE;
	return OK;
}

Status LIST::ListInsert_Sq(SqList &L,int i,ElemType e){
	//在顺序线性表L中第i个位置之前插入新的元素e
	//i的合法值为1<=i<=ListLength_Sq(L)+1
	if(i<1||i>L.length+1) return ERROR;//i值不合法
	if(L.length>=L.listsize){
		//当前存储空间已满，增加分配
		ElemType * newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)* sizeof(ElemType));
		if(!newbase) exit(OVERFLOW);//存储分配失败
		L.elem=newbase;//新基址
		L.listsize+=LISTINCREMENT;//增加存储容量
	}
	ElemType * q=&(L.elem[i-1]);//q为插入位置
	for(ElemType * p=&(L.elem[L.length-1]);p>=q;--p)
		* (p+1)=* p;
	* q=e;
	++L.length;
	return OK;
}

Status LIST::ListDelete_Sq(SqList &L,int i,ElemType &e){
	//在顺序线性表L中删除第i个元素，并用e返回其值
	//i的合法值为1<=i<=ListLength_Sq(L)+1
	if(i<1||i>L.length+1||L.length==0) return ERROR;//i值不合法
	ElemType * p=&(L.elem[i-1]);     //p为被删除元素的位置
		e=* p;                //被删除元素的值赋给e
	ElemType * q=&(L.elem[L.length-1]);//表尾元素的位置
	for(++p;p<=q;++p)
		* (p-1)=* p;
	--L.length;
	return OK;
}

Status LIST::GetElem(SqList L,int i,ElemType &e){
	//线性表L已存在，1<=i<=ListLength_Sq(L)
	//用e返回L中的第i个元素
	if(i<1||i>L.length) return ERROR;
	e=L.elem[i-1];
	return OK;
}

Status LIST::ChaElem(SqList &L,int i, ElemType e){
	//用e更新线性表L的第i个元素，0<=i<=ListLength_Sq(L)
	if(i<0||i>L.length) return ERROR;
	L.elem[i-1]=e;
	return OK;
}

Status LIST::ListTraverse(SqList L){
	//遍历线性表
	ElemType * p=&L.elem[0];
	ElemType * q=&L.elem[L.length-1];
	for(p;p<=q;p++)
		printf("%d ",* p);
	printf("\n");
	return OK;
}

单链表代码

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW_ -2

typedef int Status;
typedef int ElemType;

typedef struct LNode {
	ElemType data;
	struct LNode * next;
}LNode, * LinkList;

class LINKLIST {
		public:
			Status InitList_L(LinkList &L);
			Status CreateList_L(LinkList L, int n);
			Status DestroyList_L(LinkList L);
			Status ClearList_L(LinkList L);
			int ListLength_L(LinkList L);
			Status ListInsert_L(LinkList L, int i, ElemType e);
			Status ListDelete_L(LinkList L, int i, ElemType &e);
			Status GetEleList_L(LinkList L, int i, ElemType &e);
			Status AlterEleList_L(LinkList L, int i, ElemType e);
			Status Inverse_L(LinkList L);
};

Status LINKLIST::InitList_L(LinkList &L) {
	//链表初始化
	L = (LinkList)malloc(sizeof(LNode));
	if (!L) exit(OVERFLOW_);
	L->next = NULL;
	return OK;
}

Status LINKLIST::CreateList_L(LinkList L, int n) {
	//初始化并正序或逆序插入单链表
	//逆位序输入n个元素的值，建立带头结点的单链表L
	/* for(int i=n;i>0;--i){
	LinkList p=(LinkList)malloc(sizeof(LNode));//生成新结点
	if(!p)	exit(OVERFLOW_);
	//scanf("%d",&p->data);
	cin>>p->data;
	p->next=L->next;
	L->next=p;
	}*/
	//正位序插入n个元素的值，建立带头结点的单链表
	LinkList s = L;
	for (int i = n;i>0;--i) {
		LinkList p = (LinkList)malloc(sizeof(LNode));
		if (!p) exit(OVERFLOW_);
		cin >> p->data;
		p->next = s->next;
		s->next = p;
		s = p;
	}
	return OK;
}

Status LINKLIST::DestroyList_L(LinkList L) {
	//摧毁链表
	LinkList p;
	while (L->next != NULL) {
		p = L->next;
		L->next = p->next;
		free(p);
	}
	free(L); //删除头结点
	return OK;
}

Status LINKLIST::ClearList_L(LinkList L) {
	//将链表重置为空表，并释放原链表的节点空间
	LinkList p;
	while (L->next != NULL) {
		p = L->next;
		L->next = p->next;
		free(p);
	}
	//free(L);
	return OK;
}

int LINKLIST::ListLength_L(LinkList L) {
	//返回链表长度
	int length = 0;
	LinkList p = L;
	while (p->next) {
		p = p->next;
		length++;
	}
	return length;
}

Status LINKLIST::ListInsert_L(LinkList L, int i, ElemType e) {
	//链表已存在，在第i个结点前插入一个结点
	if (i<1 || i>ListLength_L(L) + 1) {
		cout << "位置不合法，插入失败";
		return ERROR;
	}
		int locate = 0;
	LinkList p = L;
	while (p->next&&locate<i - 1) {
		p = p->next;
		locate++;
	}
	LinkList q = (LinkList)malloc(sizeof(LNode));
	q->data = e;
	q->next = p->next;
	p->next = q;
	return OK;
}

Status  LINKLIST::ListDelete_L(LinkList L, int i, ElemType &e) {
	//删除第i个结点，并用e返回其值
	if (i<1 || i>ListLength_L(L)) {
		cout << "位置不合法，删除失败";
		return ERROR;
	}
	int locate = 0;
	LinkList p = L;
	while (p->next&&locate < i - 1) {
		p = p->next;
		locate++;
	}
	e = p->next->data;
	cout << "该位置节点已删除，删除的值为：" << e;
	LinkList q = p->next->next;
	free(p->next);//释放第i个结点
				  //cout << p->next; //测试释放后的指针指向
	p->next = q;
	return OK;
}

Status  LINKLIST::GetEleList_L(LinkList L, int i, ElemType &e) {
	//获取第i个结点的值，并用e返回其值
	if (i<1 || i>ListLength_L(L)) {
		cout << "位置不合法，获取失败";
		return ERROR;
	}
	int locate = 0;
	LinkList p = L;
	while (p->next&&locate < i) {
		p = p->next;
		locate++;
	}
	e = p->data;
	cout << "该位置的元素值：" << e;
	return OK;
}

Status  LINKLIST::AlterEleList_L(LinkList L, int i, ElemType e) {
	//更新第i个结点的值
	if (i<1 || i>ListLength_L(L)) {
		cout << "位置不合法，更新失败";
		return ERROR;
	}
	int locate = 0;
	LinkList p = L;
	while (p->next&&locate < i) {
		p = p->next;
		locate++;
	}
	p->data = e;
	return OK;
}
Status  LINKLIST::Inverse_L(LinkList L) {
	//遍历链表
	LinkList p;
	p = L;
	while (p->next != NULL) {
		p = p->next;
		cout << p->data << " ";
	}
	return OK;
}

双向链表代码

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW_ -2

typedef int Status;
typedef int ElemType;
using namespace std;

typedef struct DuLNode {
	ElemType data;
	struct DuLNode * prior;
	struct DuLNode * next;
}DuLNode, * DuLinkList;

class DL {
	public:
		Status InitList_DuL(DuLinkList &L);
		Status CreateList_DuL(DuLinkList L, int n);
		Status ListInsert_DuL(DuLinkList L, int i, ElemType e);
		Status ListDelete_DuL(DuLinkList L, int i, ElemType &e);
		Status GetElem_DuL(DuLinkList L, int i, ElemType &e);
		Status AlterElem_DuL(DuLinkList L, int i, ElemType e);
		Status Inverse_DuL(DuLinkList L);
		DuLinkList GetEleLocate_DuL(DuLinkList L, int i);
		int GetLength_DuL(DuLinkList L);
};

Status DL::InitList_DuL(DuLinkList &L) {
	//初始化链表
	L = (DuLinkList)malloc(sizeof(DuLNode));
	if (!L) exit(OVERFLOW_);
	L->prior = L->next = NULL;
	return OK;
}

Status DL::CreateList_DuL(DuLinkList L, int n) {
	//循环插入链表
	DuLinkList s = L;
	for (int i = n;i > 0;--i) {
		DuLinkList p = (DuLinkList)malloc(sizeof(DuLNode));
		if (!p)exit(OVERFLOW_);
		cin >> p->data;
		p->next = s->next; //p的尾指针设置
		p->prior = s;//p的头指针设置
		s->next = p;
		s = p;
	}
	return OK;
}

DuLinkList DL::GetEleLocate_DuL(DuLinkList L, int i) {
	//判断i是否在链表合理长度内,如果合法，则返回第i个结点的指针位置
	int locate = 0;
	DuLinkList p = L;
	while (p->next&&locate < i) {
		p = p->next;
		locate++;
	}
	if (p->next == NULL&&locate != i)
		return p=NULL;
	return p;
}

int DL::GetLength_DuL(DuLinkList L) {
	//判断链表长度
	int length = 0;
	DuLinkList p = L;
	while (p->next) {
		p = p->next;
		length++;
	}
	return length;
}

Status DL::ListInsert_DuL(DuLinkList L, int i, ElemType e) {
	//在第i个位置插入元素e
	//1<=i<=length+1
	if (i<1 || i>GetLength_DuL(L) + 1) {
		cout << "位置不合法，插入失败";
		return ERROR;
	}
	int locate = 0;
	DuLinkList p = L;
	while (p->next&&locate < i) {
		p = p->next;
		locate++;
	}
	DuLinkList s = (DuLinkList)malloc(sizeof(DuLNode));
	if (!s) return ERROR;
	s->data = e;
	if (!(p->next)) {
		s->next = p->next;
		s->prior = p;
		p->next = s;
	}
	else {
		s->prior = p->prior;
		p->prior->next = s;
		s->next = p;
		p->prior = s;
	}
	return OK;
}

Status DL::ListDelete_DuL(DuLinkList L, int i, ElemType &e) {
	//删除第i个结点，并用e返回其值
	if (i<1 || i>GetLength_DuL(L)) {
		cout << "位置不合法，删除失败";
		return ERROR;
	}
	DuLinkList p = GetEleLocate_DuL(L, i);
	e = p->data;
	cout << "该位置节点已删除，删除的值为：" << e;
	p->prior->next = p->next;
	if(p->next)
		p->next->prior = p->prior;
	free(p);
	return OK;
}

Status DL::GetElem_DuL(DuLinkList L, int i, ElemType &e) {
	//获取第i个结点的值
	DuLinkList p = GetEleLocate_DuL(L, i);
	if (!p) {
		cout << "位置不合法，获取失败";
		return ERROR;//如果i的位置不正确，则不合法
	}
	e = p->data;
	cout << "该位置的元素值：" << e;
	return OK;
}

Status DL::AlterElem_DuL(DuLinkList L, int i, ElemType e) {
	//更新第i个结点的值
	DuLinkList p = GetEleLocate_DuL(L, i);
	if (!p) {
		cout << "位置不合法，更新失败";
		return ERROR;//如果i的位置不正确，则不合法
	}
	p->data = e;
	return OK;
}

Status DL::Inverse_DuL(DuLinkList L) {
	//遍历链表
	DuLinkList p;
	p = L;
	while (p->next != NULL) {
		p = p->next;
		cout << p->data << endl;
	}
	return OK;
}