数据结构，线性表，顺序表常见算法

算法和问题来自于试卷，辅导书，以及网络。

//顺序表的一般数据结构
typedef struct{
    int data[Maxsize];
    int length;
}SqList;

算法2.1.1

从顺序表中删除具有最小值的元素，并由函数返回被删元素值。空出位置由最后一个补齐

分析：算法很简单，基本思想可参照简单选择排序思想

int deleteMin(Sqlist &L, int &e)
{
    int i,j;
	if(L.length==0) return 0;
	min=L.data[0];
	for(i=1;i<L.length;i++)
	{
	   if(L[i]<min)
	   {
	   		j=i;
	   		e=L[i];
	   }
	}
	L.data[j]=L[L.length-1];
	--L.length;
	return e;
}

算法2.1.2

将顺序表L所有元素逆置

分析：算法很简单，用两个指针，一个用于替换的变量即可，从两头到中间进行替换。

void revert(Sqlist &L)
{
    int i=0,j=L.length-1;
    int temp;
    while(i<j)
    {
      temp=L[i];
      L[i]=L[j];
      L[j]=temp;
      i++;j--;     
    }
}

算法2.1.3

对长度为n的顺序表，删除其中所有值等于x的元素，要求其时间复杂度为O（n）,空间复杂度为O（1）

分析：若不要求空间复杂度，则算法很容易利用一个长度为n的数组实现，现在要求空间复杂度为O（1），则放弃采用这种思想。而且时间复杂度为0（n），则要避免删除后的数组移动，可以用两个指针，第一个遍历完整个数组，第二个当不等于x时才向前移动，这样便将不等于x的数保存在了数组中。

void deleteX(Sqlist &L, int n,int x)
{
	int i=0,j=0,count;  //count统计不等于x的数的个数
	for(i=0;i<n;i++)
	{
		if(L.data[i]!=x)
		{
			L.data[j++]=L.data[i];
			++count;
		}
	}
	L.length=count;
}

算法2.1.4

从顺序表中删除值在给定的s与t之间（s<t），若不合法则退出运行。

分析：类似与2.1.3 ，只不过删除的条件变了

bool deleteA(Sqlist & L,int s, int t)
{
	int i=0,j=0;
	if(s>=t||L.length==0) return 0;
	for(i=0;i<n;i++)
	{
		if(L.data[i]<=s&&L.data[i]>=t)  //若值不在s，t之间则保存
			L.data[j++]=L.data[i];		
	}
	L.length=j;
	return 1;
}

算法2.1.5

从有序顺序表中删除值重复的元素，使其中的元素均不相同。

分析：若顺序表无序，则删除相同的较为麻烦，需对每个元素遍历一次顺序表，时间复杂度达到了o(n²)m若表中元素均有序，则这样考虑，相等的元素必定是连续的 比如 12234566689 ，同算法2.1.3， 可以采用两个指针，对于相邻的元素如果相同则跳过这个元素存储即可。

void deleteSame(Sqlist &L)
{
	int i,j=0;
	for(i=1;i<L.length;i++)    //i用于遍历表，j用于存储不相等值
	{	
		if(L.data[j]!=L.data[i]) 
		{
			L.data[++j]=L.data[i];
		}                        //相邻不相等，则存储
	}
	L.length=j+1;  //循环结束后j+1才是表长
}

算法2.1.6

在一维数组A[m+n]中有两个线性表（a1，a2，…,am）和（b1,b2,…,bn）。编写算法将两个顺序表位置互换，将（b1,b2,…,bn），放在（a1，a2，…,am）前。

分析：该算法稍微复杂些，一般分为两步：①先将整个线性表逆置，其中元素会变为（（bn,…,b2,b1），（am…,a2，a1））。②观察发现，b表中的元素已在a表前，但a表，b表中的元素均为逆置状态，故再分别对a，b表进行逆置，就能达到要求的效果。这里可以对算法2.1.2做出小小的修改。

void revert(Sqlist &L, int first, int rear)
{
    
    int temp;
    while(first<rear)
    {
      temp=L.data[first];
      L.data[first]=L.data[rear];
      L.data[rear]=temp;
      first++;rear--;     
    }
}
void transferList(Sqlist &L,int m,int n)
{
	int i=0,j=m+n-1;
	revert(L,i,j);
	revert(L,0,n-1);
	revert(L,n,m+n-1);
}//注，表空，越界等错误判别略。

线性表的定义：

线性表中元素关系是一对一的，元素个数是有限的

 

序列补充：

存在唯一开始元素和终端元素，除此之外，每个元素只有唯一的前驱元素和后继元素 

 线性表的长度：

线性表中所含元素的个数（n），n=0时表示线性表是一个空表

线性表可以用二元组表示

线性表的抽象数据类型：

线性表的分类： 顺序表，单链表，双链表，循环链表

顺序表：

按照元素的逻辑次序依次储存在一块连续的储存空间里

顺序表中访问任一元素的时间复杂度为O(1),所以顺序表具有随机存取特性

顺序表中逻辑上相邻的元素物理位置必定相邻

顺序表的地址计算：

 顺序表类型声明：

采用指针形参：

  (1)  访问用  ->

（2）方便顺序表释放算法的设计。节省形参分配的空间

 建立顺序表：

修改L，需要传入指针的引用

 

 

 算法分析：顺序表插入操作平均移动次数为表长一半，与插入位置和表长有关

 

 顺序表应用实例：

（1）空间重用：

 用下标k作为新数组的下标，扫描原数组，如果遇到的元素符号新数组中元素的条件 ，则a[k++]=a[i++];

 (2)利用对撞指针实现元素分类：

//模板
int i=begin;
int j=end;
while(i<j)
{
   while(i<j&&nums[j]不符合交换条件)
   {
    j--;
   }
   while(i<j&&nums[i]不符合交换条件)
  {
   i++;
  }
  swap(nums[i],nums[j]);

}

 

 

链表： 线性表的链式储存结构。每个储存结点包含数据域和指针域。

            链表中逻辑上相邻的元素在物理位置上不一定相邻 

单链表：每个结点除数据域外设置一个指针域，指向其后继节点

双链表：每个结点除数据域外设置两个指针域，分别指向其前驱结点和后继结点。

头结点：链表的唯一标识

   增加头节点的优点：  

 储存密度：

单链表：

 带头节点的单链表示意图

 单链表类型：

 插入或删除一个结点需要找到其前驱结点

 

 

单链表的应用：

链表的拆分：

void split(LinkNode *&l,LinkNode *&l1,LinkNode *&l2)
{
//创建L1,L2头结点
l1=(LinkNode*)malloc(sizeof(LinkNode));
l2=(LinkNode*)malloc(sizeof(LinkNode));
l1->next=NULL;
L2->next=NULL;
//如果l1使用L的头结点，直接令L1=L即可。
LinkNode *p=L->next;
LinkNode *q,*r;
r=l1;
//头插法建表会修改p的next域，需要用q记录p的后继结点
//尾插法用r记录尾结点
while(p!=NULL)
{

//尾插法
r->next=p;
r=p;

q=p->next;
p->next=l2->next;
l2->next=p;
p=q;//p回到L中

}
r->next=NULL;



}

 

 

双链表的优点：

从任一结点出发，可以快速找到其前驱结点和后继结点

从任一结点出发可以访问其他结点 

 

 

 

 

 

 

 

了解：

1) 任何节点都可以做为头节点。 可以从任何节点开始进行链表的遍历。只要当第一个节点被重复访问时，则意味着遍历结束。

2) 用于实现队列。 如果使用循环链表，则不需要为了队列而维护两个指针(front以及rear)。只需要维护尾节点一个指针即可，因为尾节点的后向节点就是front了。

3) 循环链表常用于各应用程序中。 例如，当运行多个应用程序时，操作系统通常会把这些程序存入至一个链表，并进行循环遍历，给每个应用程序分配一定的时间来执行。此时循环链表对于OS是很有帮助的，当达到链表尾部时，可以方便的从头部重新开始遍历。

有序表：

 

 

 有序表的归并算法:

）编写一个对顺序表中元素从小到大排序的算法，函数接口如下：

//初始条件：线性表L已经存在，且元素个数大于1

//操作结果：将L中的元素从小到大排序

Status ListSort_Sq(SqList &L);

然后，在main函数中调用ListSort_Sq函数，对之前创建的顺序表进行排序。

实现两个有序顺序表的合并操作。然后在主函数中再创建一个顺序表实例，输入5个元素，并对之排序。最后调用所实现的合并算法将两个顺序表进行合并。

#include<stdio.h>
#include<stdlib.h>
#define TRUE   1
#define FALSE  0
#define OK     1
#define ERROR  0
#define OVERFLOW -2
typedef int Status ;
typedef int ElemType ;
#define LIST_INIT_SIZE 100   //线性表存储空间的初始分配量
#define LISTINCREMENT 10     //线性表存储空间的分配增量#pragma once
typedef struct
{
	ElemType *elem;      //存储空间基址
	int length;          //当前长度
	int listsize;   //当前分配的存储空间容量（以sizeof(ElemType)为单位）
}SqList;
//操作结果：构造一个空的线性表
Status InitList_Sq(SqList &L);

//初始条件：线性表L已经存在
//操作结果：销毁一个线性表
Status DestroyList_Sq(SqList &L);

//初始条件：线性表L已经存在
//操作结果：将L重置为空表
Status ClearList_Sq(SqList &L);

//初始条件：线性表L已经存在
//操作结果：若L为空表，则返回TRUE,否则返回FALSE
Status ListEmpty_Sq(SqList L);

//初始条件：线性表L已经存在
//操作结果：返回线性表的长度
int ListLength_Sq(SqList L);

//初始条件：线性表L已经存在
//操作结果：在L的表尾加入新元素
Status AppendElem (SqList &L,ElemType e);

//初始条件：线性表L已经存在
//操作结果：用e返回线性表的第i个元素的值
Status GetElem_Sq(SqList L,int i, ElemType &e);

//初始条件：线性表L已经存在
//操作结果：用i返回线性表中值为e的元素的位置
Status LocateElem_Sq(SqList L, ElemType e,Status (*compare)(ElemType,ElemType));

//初始条件：线性表L已经存在
//操作结果：用pre_e返回线性表中值为cur_e的元素的前驱
Status PriorElem_Sq(SqList L,ElemType cur_e, ElemType &pre_e);

//初始条件：线性表L已经存在
//操作结果：用next_e返回线性表中值为cur_e的元素的后继
Status NextElem_Sq(SqList L,ElemType cur_e, ElemType &next_e);

//初始条件：线性表L已经存在
//操作结果：在L中第i个元素之前插入新的元素e,L的长度加1
Status ListInsert_Sq(SqList &L,int i, ElemType e);

//初始条件：线性表L已经存在
//操作结果：删除L的第i个元素，并用e返回其值，L的长度减1
Status ListDelete_Sq(SqList &L,int i, ElemType &e);

//初始条件：线性表L已经存在
//操作结果：依次对L的每个数据元素调用(*visit)()，一旦(*visit)()失败，则操作失败
Status ListTraverse_Sq(SqList L,Status (*visit)(ElemType));

//辅助函数
Status compare_sq(ElemType e1,ElemType e2);  //比较两个元素的值
Status visit_sp(ElemType e);                  //访问元素（将元素的值打印出来）
Status Listempty_Sq(SqList &L) ;//判断线性表是否为空
Status Display_Sq(SqList &L); //提取顺序表中的元素
void ListSort_Sq(SqList &L);//对线性表中的元素进行排序
void MergeList_Sq(SqList La,SqList Lb,SqList &Lc);//对已知线性表La和Lb的元素按值非递减排列
//操作结果：构造一个空的线性表
Status InitList_Sq(SqList &L)
{
	L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
    if(!L.elem) exit(OVERFLOW);
    L.listsize=LIST_INIT_SIZE;
    L.length=0;
    return OK;
}//InitList_Sq

//初始条件：线性表L已经存在
//操作结果：销毁一个线性表
Status DestroyList_Sq(SqList &L)
{
	free(L.elem);
	L.elem=NULL;
	return OK;
}

//初始条件：线性表L已经存在
//操作结果：将L重置为空表
Status ClearList_Sq(SqList &L)
{
   L.length=0;
   return OK; 
}

//初始条件：线性表L已经存在
//操作结果：若L为空表，则返回TRUE,否则返回FALSE
Status ListEmpty_Sq(SqList L)
{
   if(NULL==L.elem) return ERROR;
   if(0==L.length)  return TRUE;
   return FALSE;
}

//初始条件：线性表L已经存在
//操作结果：返回线性表的长度
int ListLength_Sq(SqList L)
{
	return L.length;
}

//初始条件：线性表L已经存在
//操作结果：用e返回线性表的第i个元素的值
Status GetElem_Sq(SqList L,int i, ElemType &e)
{
	if(i>L.length||i<1) return ERROR;
	e=L.elem[i-1];
	return OK;
}

//初始条件：线性表L已经存在
//操作结果：用i返回线性表中值为e的元素的位置
Status LocateElem_Sq(SqList L, ElemType e,Status (*compare)(ElemType,ElemType))
{
	int i=1;
/*	ElemType *p;
	p=L.elem;
	while(i<=L.length&&!(*compare)(*p++,e)) ++i;
	if(i<=L.length) return i;
	else return 0;*/
	while(i<=L.length)
	{
		if((*compare)(e,L.elem[i-1]))
		{
			return i;
		}
		i++;
	}
	return 0;

}

//初始条件：线性表L已经存在
//操作结果：用pre_e返回线性表中值为cur_e的元素的前驱
Status PriorElem_Sq(SqList L,ElemType cur_e, ElemType &pre_e)
{
	int i;
	if(i=LocateElem_Sq(L,cur_e,compare_sq))
		if(i>=2&&i<=L.length)
			pre_e=L.elem[i-2];
	return i-1;
}

//初始条件：线性表L已经存在
//操作结果：用next_e返回线性表中值为cur_e的元素的后继
Status NextElem_Sq(SqList L,ElemType cur_e, ElemType &next_e)
{
	int i;
	if(i=LocateElem_Sq(L,cur_e,compare_sq))
		if(i>=1&&i<L.length)
			next_e=L.elem[i];
	return i+1;
}

//初始条件：线性表L已经存在
//操作结果：在L中第i个元素之前插入新的元素e,L的长度加1
// 在顺序线性表L的第i个元素之前插入新的元素e，
// i的合法值为1≤i≤ListLength_Sq(L)+1
Status ListInsert_Sq(SqList &L,int i, ElemType e)
{
    ElemType *newbase,*p,*q;
	if(i<1||i>L.length+1) return ERROR;
	if(L.length >=L.listsize)
	{
		newbase = (ElemType *)realloc(L.elem,
                  (L.listsize+LISTINCREMENT)*sizeof (ElemType));
		if (!newbase) return ERROR;   // 存储分配失败
        L.elem = newbase;             // 新基址
        L.listsize += LISTINCREMENT;  // 增加存储容量
	}
	q=&(L.elem[i-1]);
	for(p=&(L.elem[L.length -1]);p>=q;--p) *(p+1)=*p;
	*q=e;
	++L.length;
	return OK;
}//ListInsert_Sq

//初始条件：线性表L已经存在
//操作结果：在L的表尾加入新元素
Status AppendElem(SqList &L,ElemType e)
{
  if (L.length >= L.listsize) {   // 当前存储空间已满，增加容量
    ElemType *newbase = (ElemType *)realloc(L.elem,
                  (L.listsize+LISTINCREMENT)*sizeof (ElemType));
    if (!newbase) return ERROR;   // 存储分配失败
    L.elem = newbase;             // 新基址
    L.listsize += LISTINCREMENT;  // 增加存储容量
  }
  L.elem[L.length] = e;       // 加入e到表尾
  ++L.length;   // 表长增1
  return OK;
}

//初始条件：线性表L已经存在
//操作结果：删除L的第i个元素，并用e返回其值，L的长度减1
Status ListDelete_Sq(SqList &L,int i, ElemType &e)
{
	ElemType *p,*q;
	if(i<1||i>L.length+1) return ERROR;
	p=&(L.elem[i-1]);
	e=*p;
	q=L.elem +L.length -1;
	for(++p;p<=q;++p) *(p-1)=*p;
	--L.length;
	return OK;
} // ListDelete_Sq

//初始条件：线性表L已经存在
//操作结果：依次对L的每个数据元素调用(*visit)()，一旦(*visit)()失败，则操作失败
Status ListTraverse_Sq(SqList L,Status (*visit)(ElemType))
{
	int i;
	for(i=1;i<=L.length;i++)
		visit(L.elem[i-1]);
	printf("\n");
	return OK;
}

/*辅助函数的实现*/
//比较两个元素，如果相等返回TRUE，否则返回FALSE
Status compare_sq(ElemType e1,ElemType e2)
{
	if(e1==e2) return TRUE;
	else return FALSE;
}

//将元素e的值打印出来
Status visit_sp(ElemType e)
{
	printf("%d",e);
	return OK;
}

Status Listempty_Sq(SqList &L)  
{  
    if(L.length == 0)  
        return TRUE;  
    else  
        return FALSE;  
}  

Status Display_Sq(SqList &L)
{
	int i;
	printf("顺序表中储存的元素为:");
	for(i=0;i<L.length;i++)	printf("%d  ",L.elem[i] );
	printf("\n");
	return TRUE;
}

void ListSort_Sq(SqList &L)  
{  
    int i, j, tmp, max;  
    for(i = 0; i < L.length - 1; i++)  
    {  
        max = i;  
        for(j = i; j < L.length; j++)  
        {  
            if(L.elem[max] > L.elem[j])  
                max = j;  
        }  
        tmp = L.elem[i];  
        L.elem[i] = L.elem[max];  
        L.elem[max] = tmp;  
    }  
}       /*选择排序法*/  

//对已知线性表La和Lb的元素按值非递减排列
void MergeList_Sq(SqList La,SqList Lb,SqList &Lc)  
{  
    if(Lc.listsize  <La.length+Lb.length)   
    {  
        ElemType *newbase;   
        newbase=(int *)realloc(Lc.elem,(La.length+Lb.length+LISTINCREMENT)*sizeof(int));  
        if(newbase==NULL)  
        {  
            printf("内存分配失败!\n");  
            exit(-1) ;  
        }   
        Lc.elem=newbase;      
    }  
    int i;  
    Lc.elem=La.elem;  
    Lc.length=La.length;  
    for(i=0;i<Lb.length;++i)  
    {  
        Lc.elem[La.length+i]=Lb.elem[i];  
        Lc.length++;  
    }   
}  
void main()
{
	int n1,n2,i;
	SqList L,L1,L2;
    InitList_Sq(L);InitList_Sq(L1);InitList_Sq(L2);
	printf("请输入想往La顺序表中存储的元素的个数:");
	scanf("%d",&n1);
	printf("请依次输入La顺序表中要储存的元素:");
	for(i = 1; i <=n1; i++) 
	{
			scanf("%d",&L1.elem[i]);
            ListInsert_Sq(L1,i,L1.elem[i]);
	}
	printf("请输入想往Lb顺序表中存储的元素的个数:");
	scanf("%d",&n2);
	printf("请依次输入Lb顺序表中要储存的元素:");
	for(i = 1; i <=n2; i++) 
	{
			scanf("%d",&L2.elem[i]);
            ListInsert_Sq(L2,i,L2.elem[i]);
	}
	printf("\n\t\t\tLa顺序表");
	printf("\nLa顺序表的长度为:%d\n", L1.length);
	printf("\t排序前\n"); 
	Display_Sq(L1);   
    printf("\tLa顺序表中元素从小到大排序后\n");  
    ListSort_Sq(L1);
	Display_Sq(L1);
	printf("\n\t\t\tLb顺序表");
	printf("\nLb顺序表的长度为:%d\n", L2.length);
	printf("\t排序前\n"); 
	Display_Sq(L2);   
    printf("\tLb顺序表中元素从小到大排序后\n");  
    ListSort_Sq(L2);
	Display_Sq(L2);
	MergeList_Sq(L1,L2,L);
	printf("\n\t\t\tLa和Lb合并后");
	printf("\nL顺序表的长度为:%d\n", L.length);
	Display_Sq(L);
	system("pause");
}