上一次复习了数据结构中顺序表的概念，包括怎么样构造一个顺序表。这一次就主要学习了一下顺序表的插入与删除。
  对顺序表的增加呢，做法如下：
  例如要在一个顺序表的第i个位置插入一个元素，那么首先需要将i-1以后的元素顺序后移一个元素的位置，然后在第i个位置插入新元素，最后给表长加1。但我们要注意的是，在插入之前首先要判断插入的合法性。比如这个顺序表的长度为n，那么插入元素的位置是1~n+1，如果i<1或者i>n+1，或者n=MaxSize（表满），这样插入都是非法的，程序应该直接退出。如果插入的位置是合法的，那么首先将表的i-1以后的元素顺序后移一个元素的位置，即，将顺序表从第i个元素到第n个元素顺序后移一个位置。然后在表第i个位置（其下标为i-1），并将表长加1.
  那删除操作也是同理，首先判断它是否为非法删除，判断一个需要删除的元素是否合法。对于一个长度为n的顺序表，删除元素的合法位置是1~n，因此如果i<1或者i>n都是不合法的。 执行删除操作首先将第i位置以后的元素，依次前移，这样第i个元素就会被覆盖，也就起到了删除第i个位置元素的作用，最后将表长-1..

/*静态顺序表的各种操作*/
/*实例：
	创建一个静态的顺序表存放整数，大小为10，完成以下的操作。
	（1）输入6个整数，打印出顺序表中的内容，并显示表中剩余的空间个数
	（2）在顺序表中的第3个位置插入元素0，打印出顺序表中的内容，并显示表中剩余的空间个数
	（3）再试图向表中第11个位置插入整数0，程序提示超出范围
	（4）删除表中第6个元素，打印出顺序表中的内容，并显示表中剩余的空间个数
*/
#include "stdio.h"
#define MaxSize 10
/*
参数Sqlist:表的首地址
参数*len:表的长度
参数i:插入元素的位置
参数x:待插入的元素值
*/
void insertElem(int Sqlist[],int *len,int i, int x)
{
	int t;
	if(*len == MaxSize || i<1 || i>*len+1)
	{
		printf("This insert is illegal\n");
		return;  //非法插入
	}
	for(t = *len-1;t>=i-1;t--)
	{
		Sqlist[t+1] = Sqlist[t];
	}
	Sqlist[i-1]=x;   //插入元素
	*len = *len+1;  //表长+1
}

void DelElem(int Sqlist[],int *len,int i)
{
	int j;
	if(i<1 || i>*len)
	{
		printf("This insert is illegal");
		return;  //非法插入
	}
	for(j=i;j<*len-1;j++)
	{
		Sqlist[j-1] = Sqlist[j];   
	}
	*len = *len-1;   

}

//测试函数
void main()
{
	int  Sqlist[MaxSize];  //定义一个静态顺序表
	int len;
	int i;
	printf("please input six integer number \n");

	for(i=0;i<6;i++)
		scanf("%d",&Sqlist[i]);

	len=6;
	for(i=0;i>len;i++)
		printf("%d ",Sqlist[i]);
	printf("\n The spare length is %d\n",MaxSize - len);   // 显示表中剩余空间

	insertElem(Sqlist,&len,3,0);  // 在表中第3位置插入整数0 
	for(i=0;i<len;i++)
	  printf("%d ",Sqlist[i]);   //输出表中所有元素

	insertElem(Sqlist,&len,11,0); //在表中第11位置插入整数0
	DelElem(Sqlist,&len,6);  //删除顺序表中第6个元素

	for(i=0;i<len;i++)
		printf("%d ",Sqlist[i]);

	printf("\n The spare Length is %d \n",MaxSize - len);
}


那么动态的顺序表的插入删除则是同理，实例见下面，相信大家也很容易看懂逻辑了。
/*
动态创建一个顺序表
要求：顺序表的初始长度为10，向顺序表中输入15个整数，并打印出来。再删除表中第5个元素，打印删除后的结果
*/

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define MaxSize 10
typedef int ElemType;

typedef struct{
int *elem;
int length;
int listsize;
} Sqlist;

// 初始化一个顺序表  参数L：Sqlist类型的指针

void initSqlist(Sqlist *L)
{
	L->elem = (int *)malloc(MaxSize*sizeof(ElemType));
	if(!L->elem) 
		exit(0);
	L->length = 0;
	L->listsize=MaxSize;
}

//向顺序表中插入 元 素 
/*
参数L：Sqlist类型的指针
参数i：插入元素的位置
参数item：插入的元素
*/

void InsertElem(Sqlist *L,int i, ElemType item)
{
	//向顺序表L中的第i个位置插入元素item

	ElemType *base,* insertPtr,*p;
	if(i<1 || i>L->length+1)
		exit(0);
	if(L->length >= L->listsize)
	{
		base = (ElemType*)realloc(L->elem,(L->listsize+10)*sizeof(ElemType));
		L->elem = base;
		L->listsize = L->listsize+100;
	}

	insertPtr = &(L->elem[i-1]);                                                                
	for(p=&(L->elem[L->length-1]);p>=insertPtr;p--)
		*(p+1)=*p;
	* insertPtr =item;
	L->length++;
}

/*
从顺序表中删除元素
参数L：Sqlist类型的指针
参数i：删除元素的位置
*/

void DelElem(Sqlist *L,int i)
{
	//从顺序表L中删除第i个元素
	ElemType *delItem, *q;
	if(i<1 || i>L->length)
		exit(0);  
	delItem = &(L->elem[i-1]);
	q=L->elem+L->length-1;
	for(++delItem; delItem<=q; ++ delItem)
		*(delItem-1)=* delItem;
	L->length--;
}

//测试函数
void main()
{
	Sqlist l;
	int i;
	initSqlist(&l);   // 初始化一个顺序表
	for(i=0;i<15;i++)
		InsertElem(&l,i+1,i+1);    //向顺序表中插入1～15
	printf("The context of the list is\n");
	for(i=0;i<l.length;i++)
		printf("%d ",l.elem[i]);   //打印顺序表中的内容
	
	DelElem(&l,5);  //删除第5个元素（内容为5）
	printf("\nDelete the fifth element\n");
	for(i=0;i<l.length;i++)
		printf("%d ",l.elem[i]);
	getchar();
}


以上2个实例代码都是调试通过的。大家可以自己动手试试写几个测试的函数。  


写在后面：
  其实博主也不是大一的新生了，今年已经走上了工作岗位，无奈自己水平太菜 ，找到的工作基本都无关数据结构与算法。博主也经常和女朋友讨论什么对编程是最重要的呢，我们两个都认为，就是分析问题，解决问题。那么就算是平时用不到，也要努力学习算法和数据结构以及数学。（因为我觉得长时间不学数学，智力真的会下降的！）
尽管上面的代码，帮不了你搭一个网站，甚至不能帮你完成一次小作业。但是，聚沙成塔，这些东西学到脑子里，肯定是没错的！

   接上一篇文章继续分析

线性表——顺序表——时间复杂度计算
   在之前的文章中的示例1和示例2中，我们通过观察可以发现，当在顺序存储结构的线性表中某个位置上插入或删除一个数据元素时，其时间主要耗费在移动元素上（换句话说，移动元素的操作为预估算法时间复杂度的基本操作），而移动元素的格式取决于插入或删除元素的位置。

   假设pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时所需移动元素次数的期望值（平均次数）为

（1）



Eis=∑i=1n+1pi(n−i+1)
   假设q_i是删除第i个元素的概率，则在长度为n的线性表中删除一个元素时所需移动元素次数的期望值（平均次数）为

（2）



Edl=∑i=1nqi(n−i)
为了不失一般性，我们可以假定在线性表上的任意位置上插入或删除元素都是等概率的，即

（3）



pi=1n+1,qi=1n
通过（3）我们可以将上面的（1）和（2）进行相应的简化，其简化结果为：

（4）



Eis=1n+1∑i=1n+1(n−i+1)=n2
（5）



Edl=1n∑i=1n(n−i)=n−12
  时间复杂度的计算规则：

      1.去掉运行时间中的所有加法常数

      2.只保留最高阶项

      3.如果最高阶项存在且不是1，去掉与这个最高阶相乘的常数得到时间复杂度

   由（4）和（5）可知，在顺序存储结构的线性表中插入或删除一个数据元素，平均约移动一般元素。若表长为n，则算法listInsert_Sq和listDelete_Sq的时间复杂度都为O(n)。

   在示例1和示例2中的插入操作中，“求表长”和“取第i个数据元素”的时间复杂度均为O(1)，又由于插入均在表尾进行，则不需要移动元素，因此它们的执行时间主要取决于查找函数locateElem的执行时间。

   在示例1中，在顺序表L中查访是否存在和e相同的数据元素的最简单的方法是，令e和L中的数据元素逐个比较，若L中存在于e相同的元素a1则比较次数为i(1≤i≤L.length)，否则为L.length，即算法locateElem_Sq的时间复杂度为O(L.length)。由此对于顺序表LA和LB而言，union的时间复杂度为O(LA.length×LB.length)。

  而在示例2中，基本操作主要是给“元素赋值”算法的时间复杂度为O(LA.length+LB.length)。

总结：

  通过上述两个示例我们不难看出，示例2中的程序其运算的时间复杂度更低，因而程序运行也就会更迅速。究其原因有二：

  1) 由于la与lb中的元素依值递增（同一集合中元素不等），则在lb中的元素不需要在la中进行从头至尾的全程搜索；

  2) 由于用新表lc表示“并集”，则插入操作实际上是借助于“复制”操作来完成的。

结论：

  若以线性表表示集合并进行集合的各种运算，应该先对表中的元素进行排序。

其它：

  下面再列出其它各种常用排序的时间复杂度表

顺序表存储结构：线性表的顺序存储结构采用一组连续的存储单元一次存储线性表中的各数据元素。
基本运算的实现：
由于C语言中的数组的下标是从0开始的，所以逻辑上第k个位置实际上对应的是顺序表的第k-1个位置。
（1）插入函数
该算法在长度为n的线性表L的第i个位置插入元素x
代码如下：

（2）删除函数
该算法删除长度为n的线性表L的第i个位置的元素x
代码如下：

单链表存储结构：单链表中的每个节点由两部分组成：数据域（data）和指针域（next）。数据域用于存储线性表的一个数据元素。指针域用于存放一个指针，该指针指向本节点所含数据域元素的直接后继所在的节点。
首先对单链表的类型定义如下：

在单链表上实现基本运算的函数如下：
（1）初始化函数
初始化函数用于创建一个头节点，由head指向它，该节点的next域为空，data域未设定任何值。
初始化的代码如下：

（2）插入函数
设计思想是：创建一个data域值为x的新节点*p，然后插入到head所指向的单链表的第i个节点之前。
插入函数的代码如下：

（3）删除函数
设计思想是：线性链表中元素的删除要修改被删除元素前驱的指针，回收被删除元素所占的空间。
删除函数的代码如下：

（4）查找函数
设计思想是：线性链表中查找元素要找元素前驱的指针。
查找函数的代码如下：

1.线性表是（ A）。

A.一个有限序列，可以为空

B.一个有限序列，不可以为空

C.一个无限序列，可以为空

D.一个无限序列，不可以为空

2.线性表的基本运算ListInsert(&L,i,e)表示在线性表L中第i个位置上插入一个元素e，若L的长度为n，则i的合法取值是（ B）。

A.1≤i≤n

B.1≤i≤n+1

C.0≤i≤n-1

D.0≤i≤n

3.顺序表具有随机存取特性，指的是（ C）。

A.查找值为x的元素与顺序表中元素个数n无关

B.查找值为x的元素与顺序表中元素个数n有关

C.查找序号为i的元素与顺序表中元素个数n无关

D.查找序号为i的元素与顺序表中元素个数n有关

4.在顺序表中删除一个元素所需要的时间（ A）。

A.与删除元素的位置及顺序表的长度都有关

B.只与删除元素的位置有关

C.与删除任何其他元素所需要的时间相等

D.只与顺序表的长度有关

5.在n（n>1）个运算的顺序表中，算法时间复杂度为O(1)的运算是（ A）。

A.访问第i个元素（2≤i≤n）并求其前驱元素

B.在第i个元素之后插入一个新元素

C.删除第i个元素

D.将这n个元素递增排序

6.关于线性表的顺序存储结构和链式存储结构的描述中，正确的是（ B）。

Ⅰ.线性表的顺序存储结构优于链式存储结构

Ⅱ.顺序存储结构比链式存储结构的存储密度高

Ⅲ.如需要频繁插入和删除元素，最好采用顺序存储结构

Ⅳ.如需要频繁插入和删除元素，最好采用链式存储结构

A.Ⅰ、Ⅱ、Ⅲ

B.Ⅱ、Ⅳ

C.Ⅱ、Ⅲ

D.Ⅲ、Ⅳ

7.在单链表中，增加一个头节点的目的是为了（C ）。

A.使单链表至少有一个节点

B.标识链表中某个重要节点的位置

C.方便插入和删除运算的实现

D.表示单链表是线性表的链式存储结构

8.通过含有n（n≥1）个元素的数组a，采用头插法建立一个单链表L，则L中节点值的次序（B ）。

A.与数组a的元素次序相同

B.与数组a的元素次序相反

C.与数组a的元素次序无关

D.以上都不对

9.某算法在含有n（n≥1）个节点的单链表中查找值为x节点，其时间复杂度是（ D）。

A.
B.O(1)

C.
D.O(n)

10.在长度为n（n≥1）的单链表中删除尾节点的时间复杂度为（C ）。

A.O(1)

B.
C.O(n)

D.
11.关于线性表的正确说法是（D ）。

A.每个元素都有一个前驱和一个后继元素

B.线性表中至少有一个元素

C.表中元素的排序顺序必须是由小到大或由大到小

D.除第一个元素和最后一个元素外，其余每个元素有且仅有一个前驱和一个后继元素

12.以下关于顺序表的叙述中，正确的是（ C）。

A.顺序表可以利用一维数组表示，因此顺序表与一维数组在结构上是一致的，它们可以通用

B.在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻

C.顺序表和一维数组一样，都可以进行随机存取

D.在顺序表中每一个元素的类型不必相同

13.以下属于顺序表的优点是（ C）。

A.插入元素方便

B.删除元素方便

C.存储密度大

D.以上都不对

14.设线性表中有n个元素，以下运算中，（A ）在单链表上实现要比在顺序表上实现效率更高。

A.删除指定位置元素的后一个元素

B.在尾元素的后面插入一个新元素

C.顺序输出前k个元素

D.交换第i个元素和第n-i+1个元素的值（i=1，2，…，n）

15.以下关于单链表的叙述中正确的是（C ）。

Ⅰ.节点除自身信息外还包括指针域，存储密度小于顺序表

Ⅱ.找第i个节点的时间为O(1)

Ⅲ.在插入、删除运算时不必移动节点

A.仅Ⅰ、Ⅱ

B.仅Ⅱ、Ⅲ

C.仅Ⅰ、Ⅲ

D.Ⅰ、Ⅱ、Ⅲ

1 .设计一个算法，查找非空顺序表L中第一个最大的元素，并返回该元素的逻辑序号。

typedef struct

{

int data[MaxSize];

int length;

}SqList;

int max(SqList *L)

{

int maxl=L->data[0];

int i=1,m;

while(ilength)

{

if(maxldata[i])

{

maxl=L->data[i];

m=i;

}

}

return m;

}

2 .对于带头节点的单链表L1，其节点类型为LinkList，指出以下算法的功能。

void fun(LinkList *&L，ElemType x，ElemType y)

{   LinkList *p=L->next;

while (p!=NULL)

{   if (p->data= =x)

p->data=y;

p=p->next;

}

}

解：将链表中值为x的元素换成值为y。

3 .以下算法用于统计带头节点的单链表L中节点值等于给定值x的节点数的算法，其中存在错误，请指出错误的地方并修改为正确的算法。

int count(LinkList *L,ElemType x)

{   int n=0;

while (L! =NULL)

{   L=L->next;

if (L->data= =x) n++;

}

return n;

}

解：

我认为建表时头节点是从一个空表开始的，所以刚开始时L= =NULL，循环不能进行，所以应改为(L->next)!=NULL。

int count(LinkList *L,ElemType x)

{   int n=0;

while ((L->next)!=NULL)

{   L=L->next;

if (L->data= =x) n++;

}

return n;

}

4 .某非空单链表L中所有元素为整数，设计一个算法将所有小于零的节点移到所有大于等于零的节点的前面。

#include 

#include 

using namespace std;

typedef struct

{

int data[10];

int length;

}SqList;

*void move(SqList &L)

{

int i=0,j=L->length-1;

int temp;

while(i<j)

{

while(i<j&&L->data[j]>=0)

j–;

while(i<j&&L->data[i]<0)

i++;

if(i<j)

{

temp=L->data[i];

L->data[i]=L->data[j];

L->data[j]=temp;

}

}

}

void createlist(SqList *&L,int a[],int n)

{

int i;

L=(SqList *)malloc(sizeof(SqList));

for(i=0;i<n;i++)

L->data[i]=a[i];

L->length=n;

}

void display(SqList *L)

{

int i;

for(i=0;ilength;i++)

cout<data[i]<<"  “;

}

int main()

{

int a[10]={-1,0,-1,9,0,2,-4,0,-3,-9};

SqList *L;

createlist(L,a,10);

move(L);

display(L);

return 0;

}

//不太确定，写了全部的程序

*//在定义实参的时候遇到了问题，SqList &L是指针的引用，所以实参应该是指针类型的。

5 .有一个由整数元素构成的非空单链表A，设计一个算法，将其拆分成两个单链表A和B，使得A单链表中含有所有的偶数节点，B单链表中含有所有的奇数节点，且保持原来的相对次序。

想法：1.A重新创建一个节点，B重新创建一个节点

2.保持原来的相对次序，则使用尾插法建表

#include 

#include 

using namespace std;

typedef struct LNode

{

int data;

struct LNode *next;

}LinkList;

void split(LinkList *&L,LinkList *&L1,LinkList *&L2)

{

LinkList *r=L->next,*t;

L1=(LinkList *)malloc(sizeof(LinkList));

L1->next=NULL;

L2=(LinkList *)malloc(sizeof(LinkList));

L2->next=NULL;

while(r!=NULL)

{

t=r->next;

if((r->data)%2==0)

{

r->next=L1->next;

L1->next=r;

}

else

{

r->next=L2->next;

L2->next=r;

}

r=t;

}

}

void creatlistf(LinkList *&L,int a[],int n)

{

LinkList *s;

int i;

L=(LinkList *)malloc(sizeof(LinkList));

L->next=NULL;

for(i=0;i<n;i++)

{

s=(LinkList *)malloc(sizeof(LinkList));

s->data=a[i];

s->next=L->next;

L->next=s;

}

}

void display(LinkList *L)

{

LinkList *p=L->next ;

while(p!=NULL)

{

cout<data <<”  ";

p=p->next ;

}

cout<<endl;

}

int main()

{

int a[10]={1,2,3,4,5,6,7,8,9,10};

LinkList *L,*L1,*L2;

creatlistf(L,a,10);

split(L,L1,L2);

display(L1);

display(L2);

return 0;

}

//输入数据时采用头插法，所以数据为10，9，8，7，6，5，4，3，2，1.分开链表时也采用头插法，和原来的数据顺序相同。