数据结构--第二章--线性表（顺序表、链表）--知识点回顾

(1)线性表的顺序存储结构和链式存储结构的优缺点。

(2)顺序表的插人和删除 *** 作过程及其实现。

(3)单链表的查找、插人和删除 *** 作过程及其实现。

(4)双链表的查找、插人和删除 *** 作过程及其实现。

(5)循环链表的查找、插人和删除 *** 作过程及其实现。

(6)有序表的二路归并算法的思路及其实现算法，以及该算法的时间复杂度分析。

(7)利用线性表求解复杂的应用问题。

（1）有且仅有一个开始结点(表头结点)a1，它没有直接前驱，只有一个直接后继;

（2）有且仅有一个终端结点(表尾结点)an，它没有直接后继，只有一个直接前驱;

（3）其它结点都有一个直接前驱和直接后继；

（4）元素之间为一对一的线性关系。

#include 
using namespace std;
#define MaxSize 50
typedef int ElemType;
typedef struct
{
	ElemType data[MaxSize]; //存放顺序表元素
	int length; //存放顺序表的长度
} SqList; //顺序表的类型

void CreateList(SqList*& L, ElemType a[], int n) //建立顺序表
{
	L = (SqList*)malloc(sizeof(SqList)); //分配存放线性表的空间
	for (int i = 0; i < n; i++)
		L->data[i] = a[i]; //将元素a[i]存放到L中
	L->length = n; //设置L的长度为n
}

void InitList(SqList*& L) //初始化线性表
{
	L = (SqList*)malloc(sizeof(SqList)); //分配存放线性表的空间
	L->length = 0;
}

void DestroyList(SqList*& L) //销毁线性表
{
	free(L);
}

bool ListEmpty(SqList* L) //判断线性表是否为空表
{
	return(L->length == 0);
}

int ListLength(SqList* L) //求线性表的长度
{
	return(L->length);
}

void DispList(SqList* L) //输出线性表
{
	for (int i = 0; i < L->length; i++)
   {
      cout<< L->data[i]<< "  ";
   }
	cout<< endl;
}

bool GetElem(SqList* L, int i, ElemType& e) //求线性表中的某个数据元素的值
{
	if (i<1 || i>L->length) 
   {
      return false; //参数i错误时返回false
   }
	e = L->data[i - 1]; //取元素值
	return true; //成功找到元素时返回true
}

int LocateElem(SqList* L, ElemType e) //按元素值查找
{
	int i = 0;
	while (i < L->length&& L->data[i] != e) 
   {
      i++; //查找元素e
   }
	if (i >= L->length) return 0; //未找到时返回0
	else return i + 1; //找到后返回其逻辑序号
}

bool ListInsert(SqList*& L, int i, ElemType e) //插入数据元素
{
	int j;
	if (i<1 || i>L->length + 1) return false; //参数i错误时返回false
	i--; //将顺序表位序转化为elem下标
	for (j = L->length; j > i; j--) //将data[i]及后面元素后移一个位置
   {
      L->data[j] = L->data[j - 1];
   }
	L->data[i] = e; //插入元素e
	L->length++; //顺序表长度增1
	return true; //成功插入返回true
}

bool ListDelete(SqList*& L, int i, ElemType& e) //删除数据元素
{
	int j;
	if (i<1 || i>L->length) return false;  //参数i错误时返回false
	i--; //将顺序表位序转化为elem下标
	e = L->data[i];
	for (j = i; j < L->length - 1; j++)	//将data[i]之后的元素前移一个位置
   {
      L->data[j] = L->data[j + 1];
   }
	L->length--; //顺序表长度减1
	return true; //成功删除返回true
}

#include 
using namespace std;
typedef int ElemType;
typedef struct LNode
{
	ElemType data; //存放元素值
	struct LNode* next; //指向后继结点
} linkNode; //声明单链表结点类型

void CreateListF(linkNode*& L, ElemType a[], int n) //头插法建立单链表
{
	linkNode* s;
	L = (linkNode*)malloc(sizeof(linkNode));
	L->next = NULL; //创建头结点，其next域置为NULL
	for (int i = 0; i < n; i++) //循环建立数据结点s
	{
		s = (linkNode*)malloc(sizeof(linkNode));
		s->data = a[i]; //创建新结点s
		s->next = L->next; //将结点s插在原开始结点之前,头结点之后
		L->next = s;
	}
}

void CreateListR(linkNode*& L, ElemType a[], int n) //尾插法建立单链表
{
	linkNode* s, * r;
	L = (linkNode*)malloc(sizeof(linkNode)); //创建头结点
	L->next = NULL;
	r = L; //r始终指向终端结点,开始时指向头结点
	for (int i = 0; i < n; i++) //循环建立数据结点s
	{
		s = (linkNode*)malloc(sizeof(linkNode)); //创建新结点s
		s->data = a[i]; //创建数据结点s
		r->next = s; //将结点s插入结点r之后
		r = s;
	}
	r->next = NULL; //终端结点next域置为NULL
}

void InitList(linkNode*& L) //初始化线性表
{
	L = (linkNode*)malloc(sizeof(linkNode));
	L->next = NULL; //创建头结点，其next域置为NULL
}

void DestroyList(linkNode*& L) //销毁线性表
{
	linkNode* pre = L, * p = pre->next; //pre指向结点p的前驱结点
	while (p != NULL) //扫描单链表L
	{
		free(pre); //释放pre结点
		pre = p; //pre、p同步后移一个结点
		p = pre->next;
	}
	free(pre);	//此时p为NULL,pre指向尾结点,释放它
}

bool ListEmpty(linkNode* L) //判断线性表是否为空表
{
	return(L->next == NULL);
}

int ListLength(linkNode* L) //求线性表的长度
{
	int i = 0;
	linkNode* p = L; //p指向头结点，i置为0(即头结点的序号为0)
	while (p->next != NULL)
	{
		i++;
		p = p->next;
	}
	return(i); //循环结束，p指向尾结点，其序号n为结点个数
}

void DispList(linkNode* L) //输出线性表
{
	linkNode* p = L->next; //p指向首结点
	while (p != NULL) //p不为NULL,输出p结点的data域
	{
		cout<< p->data<< "  ";
		p = p->next; //p移向下一个结点
	}
	cout<< endl;
}

bool GetElem(linkNode* L, int i, ElemType& e) //求线性表中的某个数据元素值
{
	int j = 0;
	linkNode* p = L; //p指向头结点，j置为0(即头结点的序号为0)
	if (i <= 0) return false; //i错误返回假
	while (j < i && p != NULL) //找第i个结点p
	{
		j++;
		p = p->next;
	}
	if (p == NULL) return false; //不存在第i个数据结点	
	else //存在第i个数据结点
	{
		e = p->data;
		return true;
	}
}

int LocateElem(linkNode* L, ElemType e) //按元素值查找
{
	linkNode* p = L->next; //p指向首结点，i置为1(即首结点的序号为1)
	int n = 1;
	while (p != NULL && p->data != e) //查找data值为e的结点，其序号为n
	{
		p = p->next;
		n++;
	}
	if (p == NULL) return(0); //不存在值为e的结点，返回0
	else return(n); //存在值为e的结点，返回其逻辑序号n
}

bool ListInsert(linkNode*& L, int i, ElemType e) //插入数据元素
{
	int j = 0;
	linkNode* p = L, * s; //p指向头结点，j置为0(即头结点的序号为0)
	if (i <= 0) return false; //i错误返回假
	while (j < i - 1 && p != NULL) //查找第i-1个结点p
	{
		j++;
		p = p->next;
	}
	if (p == NULL) return false; //未找到位序为i-1的结点
	else //找到位序为i-1的结点*p
	{
		s = (linkNode*)malloc(sizeof(linkNode));
		s->data = e; //创建新结点s，其data域置为e
		s->next = p->next; //将s结点插入到结点p之后
		p->next = s;
		return true;
	}
}

bool ListDelete(linkNode*& L, int i, ElemType& e) //删除数据元素
{
	int j = 0;
	linkNode* p = L, * q; //p指向头结点，j置为0(即头结点的序号为0)
	if (i <= 0) return false; //i错误返回假
	while (j < i - 1 && p != NULL) //查找第i-1个结点
	{
		j++;
		p = p->next;
	}
	if (p == NULL) return false; //未找到位序为i-1的结点
	else //找到位序为i-1的结点p
	{
		q = p->next; //q指向要删除的结点
		if (q == NULL) return false; //若不存在第i个结点,返回false
		e = q->data;
		p->next = q->next; //从单链表中删除q结点
		free(q); //释放q结点
		return true;
	}
}

#include 
using namespace std;
typedef int ElemType;
typedef struct DNode		//定义双链表结点类型
{
	ElemType data;
	struct DNode *prior;	//指向前驱结点
	struct DNode *next;		//指向后继结点
} DlinkNode;

void CreateListF(DlinkNode *&L,ElemType a[],int n)
//头插法建双链表
{
	DlinkNode *s;
	L=(DlinkNode *)malloc(sizeof(DlinkNode));  	//创建头结点
	L->prior=L->next=NULL;
	for (int i=0;idata=a[i];
		s->next=L->next;			//将结点s插在原开始结点之前,头结点之后
		if (L->next!=NULL)
      {
         L->next->prior=s;
      }
		L->next=s;
      s->prior=L;
	}
}

void CreateListR(DlinkNode *&L,ElemType a[],int n)
//尾插法建双链表
{
	DlinkNode *s,*r;
	L=(DlinkNode *)malloc(sizeof(DlinkNode));  	//创建头结点
	L->prior=L->next=NULL;
	r=L;					//r始终指向终端结点,开始时指向头结点
	for (int i=0;idata=a[i];
		r->next=s;s->prior=r;	//将结点s插入结点r之后
		r=s;
	}
	r->next=NULL;				//尾结点next域置为NULL
}

void InitList(DlinkNode *&L)
{
	L=(DlinkNode *)malloc(sizeof(DlinkNode));  	//创建头结点
	L->prior=L->next=NULL;
}

void DestroyList(DlinkNode *&L)
{
	DlinkNode *pre=L,*p=pre->next;
	while (p!=NULL)
	{
		free(pre);
		pre=p;
		p=pre->next;
	}
	free(pre);
}

bool ListEmpty(DlinkNode *L)
{
	return(L->next==NULL);
}

int ListLength(DlinkNode *L)
{
	DlinkNode *p=L;
	int i=0;
	while (p->next!=NULL)
	{
		i++;
		p=p->next;
	}
	return(i);
}

void DispList(DlinkNode *L)
{
	DlinkNode *p=L->next;
	while (p!=NULL)
	{
      cout<< p->data<< " ";
		p=p->next;
	}
   cout<< endl;
}

bool GetElem(DlinkNode *L,int i,ElemType &e)
{
	int j=0;
	DlinkNode *p=L;
	if (i<=0) return false;		//i错误返回假
	while (jnext;
	}
	if (p==NULL)
		return false;
	else
	{
		e=p->data;
		return true;
	}
}

int LocateElem(DlinkNode *L,ElemType e)
{
	int n=1;
	DlinkNode *p=L->next;
	while (p!=NULL && p->data!=e)
	{
		n++;
		p=p->next;
	}
	if (p==NULL)
		return(0);
	else
		return(n);
}

bool ListInsert(DlinkNode *&L,int i,ElemType e)
{
	int j=0;
	DlinkNode *p=L,*s;
	if (i<=0) return false;		//i错误返回假
	while (jnext;
	}
	if (p==NULL)				//未找到第i-1个结点
		return false;
	else						//找到第i-1个结点p
	{
		s=(DlinkNode *)malloc(sizeof(DlinkNode));	//创建新结点s
		s->data=e;	
		s->next=p->next;		//将结点s插入到结点p之后
		if (p->next!=NULL) 
			p->next->prior=s;
		s->prior=p;
		p->next=s;
		return true;
	}
}

bool ListDelete(DlinkNode *&L,int i,ElemType &e)
{
	int j=0;
	DlinkNode *p=L,*q;
	if (i<=0) return false;		//i错误返回假
	while (jnext;
	}
	if (p==NULL)				//未找到第i-1个结点
		return false;
	else						//找到第i-1个结点p
	{
		q=p->next;				//q指向要删除的结点
		if (q==NULL) 
			return false;		//不存在第i个结点
		e=q->data;
		p->next=q->next;		//从单链表中删除*q结点
		if (p->next!=NULL) p->next->prior=p;
		free(q);				//释放q结点
		return true;
	}
}

void fun(SqList *&L)
{
   int i=0;
   int j=L->length-1;
   while(idata[i]<0)
      {
         i++;
      }
      while(L->data[j]>=0)
      {
         j--;
      }
      if(idata[i],L->data[j]);
      }
   }
}

void Reverse(linkList*& L)
{
   linkList *p = L->next, *q;
   L->next = NULL;
   while(p!=NULL)
   {
      q = p->next;
      p->next = L->next;	//让p作为头结点插入
      L->next = p;
      p = q;					//让p指向下一结点
   }
}

ElemType MinNode(linkList *& L)
{
   linkList *p = L->next,*q=p;
   while(p->next!=NULL && p->next->next!=NULL)
   {
      p = p->next->next;
      q = p->next;
   }
   return q->data;
}

void Insert(linkList *& L, ElemType x)
{
   linkList *p = L->next, *pre = L;
   linkList	*maxp = L->next, *maxpre = L;
   while(p!=NULL)
   {
      if(maxp->datadata)	//找到更大的
      {
         maxp = p;
         maxpre = pre;
      }
      pre = p;
      p = p->next;
   }
   s = (linkNode *)malloc(sizeof(linkList));
   s->data = x;
   s->next = maxpre->next;
   maxpre->next = s;
}

bool LocateNode(DlinkNode *h, ElemType x)
{
   DlinkNode *p = h->next, *pre;
   while(p!=NULL && p->data!=x)
   {
      p = p->next;
   }
   if(p==NULL)
   {
      return false;
   }
   else
   {
      p->freq++;
      pre = p->prior;
      while(pre!=h && pre->freq < p->freq)
      {
         p->prior=pre->prior;		//交换结点p和结点pre的位置
         p->prior->next=p;
         pre->next=p->next;
         if(pre->next!=NULL)		//若p结点不是尾结点
         {
            pre->next->prior=pre;
         }
         p->next=pre;
         pre->prior=p;
         pre=p->prior;		//q指向结点P的前驱结点
         
      }
      return true;
   }
}

s = p;
while(_____)
{
   s = s->next;
}

void reverse(SqList*&L)
{
   for(int i=0;ilength/2;i++)
   {
      //交换一半的元素
      swap(L->data[i],L->data[L->length-i-1]);
   }
}

void move(linkNode *& L)
{
   linkNode *p = L->next,*pre = p;
   while(p!=NULL)
   {
      if(p->data < 0)
      {
         pre->next = p->next;		//通过pre指针将p从链表中移去
         p->next = L->next;		//将p结点插入到表头
         L->next = p;
         p = pre->next;
      }
      else
      {
         pre = p;
         p = p->next;
      }
   }
}