data structure——线性表

顺序表定义：

1
2
3
4
5
6
#define maxsize 100
typedef struct
{
	int data[maxsize];
	int length;
}sqList;

或者可以这样：

1
2
int A[maxsize];
int n;

单链表结点定义：

1
2
3
4
5
typedef struct LNode
{
	int data;
	struct LNode *next;
}LNode;

双链表结点定义：

1
2
3
4
5
6
typedef struct DLNode
{
	int data;
	struct DLNode *prior;
	struct DLNode *next;	
}DLNode;

下面说几个例题，以说明顺序表的操作：

1.已知一个顺序表L其中元素为递增有序排列，先插入一个元素x使其仍为递增有序排列：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#define maxsize 100
int L[maxsize];
int n;

int findElem(sqList L,int x)
{
	int i;
	for (i=0;i<L.length;++i)
	{
		if(x<L.data[i])
		{
			return i;
		}	
	}
	return i;
}


void insertElem(sqList &L,int x)
{
	int p,i;
	p=findElem(L,x);
	for(i=L.length-1;i>=p;--i)
		L.data[i+1]=L.data[i];
	L.data[p]=x;
	++(L.length);
}

其中findElem函数是返回这个递增顺序表中第一个比他大的元素的地址，最后一句return i是在顺序表所有的元素都比他小的情况下，此时for循环不满足条件退了出来，而此时对应的元素的地址刚好是最后一个元素的位置。
insertElem函数是将找到的位置后面的元素，将元素往右移动，这里L因为本身是要改变，所以用了引用型。函数里面的for循环是从最右边往左一个一个的右移。

2.删除顺序表L中下标为p的元素，成功返回1，不成功返回0并将被删除元素的值赋给e

1
2
3
4
5
6
7
8
9
10
11
int deleteElem(sqlist &L,int p,int &e)
{
	int i;
	if(p<0||p>L.length-1)
		return 0;
	e=L.data[p];
	for (i=p;i<L.length;++i)
		L.data[i]=L.data[i+1];
	--(L.length);
	return 1;	
}

这里是删除一个下标为p的元素，只要直接将p下标之后的元素，从左往右一个一个的覆盖即可。

实例1和实例2，主要就讲了顺序表中最基本的操作：查找，插入，删除。

还有初始化顺序表和求指定位置元素的算法：

1
2
3
4
void initList(sqList &L)
{
	L.length=o;
}
1
2
3
4
5
6
7
int getElem(sqlist L,int p,int &e)
{
	if(p<0||p>L.length-1)
		return 0;
	e=L.data[p];
	return 1;
}

下面通过一个实例来说明一下单链表的操作：

例：A和B是两个带头结点的单链表，其中元素递增有序，设计一个算法，将A和B归并成一个按元素值非递减有序的链表C。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void merge(LNode *A,LNode *B,LNode *&C)
{
	LNode *p=A->next;
	LNode *q=B->next;
	LNode *r;
	C=A;
	C->next=NULL;
	free(B);
	r=C;
	while (p!=NULL&&q!=NULL)
	{
		if (p->data<=q->data)
		{
			r->next=p;p=p->next;
			r=r->next;
		}
		else
		{
			r->next=q;q=q->next;
			r=r->next;
		}
	}
	r->next=NULL;
	if(p!=NULL)
		r->next=p;
	if(q!=NULL)
		r->next=q;
}

这个实例的主要方法是，首先先创建一个新的单链表C，C的头结点使用A链表的头结点，再用新的指针C指向他。B链表的指针的头结点就没什么用了就free B，接着使用一个if判断，将A，B中的元素的大小进行比较，将小的那个插入到C链表中（A,B单链表是递增有序的）。最后再用一个if判断，将如果一方有剩余的元素的单链表全部插入到C链表中，注意，剩余的插入C链表中，只需要将前面的一个指针链接到C链表后面即可，因为剩余的那个链表后面已经链接好了，不需要再用for循环一个一个的将其断开再链接上去。

这个实例中用了尾插法创建了一个链表，下面对创建链表的方法做一个总结：
尾插法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void createlistR(LNode *&C,int a[],int n)
{
	LNode *s,*r;
	int i;
	C=(LNode *)malloc(sizeof(LNode));
	C->next=NULL;
	r=C;
	for (i=0;i<n;++i)
	{
		s=(LNode *)malloc(sizeof(LNode));
		s->data=a[i];
		r-next=s;
		r=r->next;
	}
	r->next=NULL;
}

头插法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void createlistF(LNode *&C,int a[],int n)
{
	LNode *s;
	int i;
	C=(LNode*)malloc(sizeof(LNode));
	c->next=NULL;
	for(i=0;i<n;++i)
	{
		s=(LNode *)malloc(sizeof(LNode));
		s->data=a[i];
		s->next=C->next;
		C->next=s;
	}
}

如上面的实例中如果需要输出的是一个递减的链表C，那么我们就可以使用头插法来实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
void merge(LNode *A,LNode *B,LNode *&C)
{
	LNode *p=A->next;
	LNode *q=B->next;
	LNode *s;
	C=A;
	C->next=NULL;
	free(B);
	while (p!=NULL&&q!=NULL)
	{
		if(p->data<=q->data)
		{
			s=p;
			p=p-next;
			s->next=C->next;
			C->next=s;
		}
		else
		{
			s=q;
			q=q->next;
			s->next=C->next;
			c->next=s;
		}
	}
		
	while(p!=NULL)
	{
		s=p;
		p=p->next;
		s->next=C->next;
		C->next=s;
	}
	while(q!=NULL)
	{
		s=q;
		q=q->next;
		s->next=C->next;
		C->next=s;
	}
	
}

头插法的原理图可见：
图片来源：https://www.jianshu.com/p/8613ea20dd19

请再看一下个实例：
查找链表C中是否存在一个值为x的结点，如果存在则删除该结点并返回1，否则返回0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void findAndDelete(LNode *C,int x)
{
	LNode *p ,*q;
	p=C;
	while(p->next!=NULL)
	{
		if(p->next->data==x)
			break;
		p=p->next;
	}
	while(p->next=NULL)
	{
		return 0;
	}
	else
	{
		q=p->next;
		p->next=p->next->next;
		free(q);
		return 1;

	}
}

注意，这里的p指针，我们是要他停在要删除结点的前驱结点处，而不是直接指向要删除的结点。

双链表：
使用尾插法建立:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void createDlistR(DLNode *&L,int a[], int n)
{
	DLNode *s,*r;
	int i;
	L=(DLNode *)malloc(sizeof(DLNode));
	L->prior=NULL;
	L->next=NULL;
	r=L;
	for(i=0;i<n;++i)
	{
		s=(DLNode *)malloc(sizeof(DLNode));
		s->data=a[i];
		r->next=s;
		s->prior=r;
		r=s;
	}
	r->next=NULL;

查找结点：
查找值为x的结点，找到就返回结点指针，否则返回NULL。

1
2
3
4
5
6
7
8
9
10
11
DLNode* findNode(DLNode *C,int x)
{
	DLNode *p=C->next;
	while(p!=NULL)
	{
		if(p->data==x)
			break;
		p=p->next;
	}
	return p;
}

插入一个结点的操作：

1
2
3
4
s->next=p->next;
s->prior=p;
p->next->prior=s;
p->next=s;

删除p结点的后继结点：

1
2
3
4
q=p->next;
p->next=q->next;
q->next->prior=p;
free(q);

下面是例题：
1.设顺序表用数组A[]表示，表中元素存储在数组下标0~m+n-1的范围内，前m个元素递增有序，后n个元素也递增有序，设计一个算法，使得整个顺序表都递增有序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void insertElem(int A[], int m, int n)
{
	int i,j;
	int temp;
	for(i=m;i<m+n;++i)
	{
		temp=A[i];
		for(j=i-1;j>=0&&temp<A[j];--j)
		{
			A[j+1]=A[j];  
		}
		A[j+1]=temp;  //因为for循环多移了一位，所以要j+1
	}
}

2.已知递增有序的单链表A,B（个数分别为m,n，且都有头结点）分别存储了一个集合，请设计一份个算法将两个集合的差集(即在A中出现而不在B中)保存在A中，并保持元素递增有序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void diffence(LNode *A LNode *B)
{
	LNode *p=A->next;
	LNode *pre=A;
	LNode *q=B->next;
	LNode *r;
	while(p!=NULL&&q!=NULL)	
	{
		if(p->data<q->data)
		{
			pre=p;
			p=p->next;
		}
		else if(p->data>q->data)
		{
			q=q->next;
		}
		else
		{
			pre->enxt=p->next;
			r=p;
			p=p->next;
			free(r);

		}
		
	}
}

3.设计一个算法，将顺序表中的元素逆置

1
2
3
4
5
6
7
8
9
10
11
12
viod reverse(sqlist &L)
{
	int i;
	int j;
	int temp;
	for(i=0,j=L.length-1;i<j;++i,j--) //i<j,不能大于也不能等于
	{
		temp=L.data[i];
		L.data[i]=L.data[j];
		L.data[j]=temp;
	}
}

4.从一个给定顺序表L中删除下标i~j的所有元素。（假定i和j都合法）

1
2
3
4
5
6
7
8
9
10
void delete(sqlist *L,int i,int j)
{
	int k,delta;
	delta=j-i+1;
	for(k=j+1;k<L.length-1,++k)
	{
		L.data[delta]=L.data[k];
	}
	L.length=L.length-delta;  
}

此题主要是用第j+1即往后的元素覆盖到i~j之间的元素，这里，如果j+1往后的元素没有I~j之间的元素个数多也不要紧，不要认为就没有”删除”完i~j之间的元素，因为L.length=L.length-delta就已经限定了表长，后面就算有元素也不是表内元素了。

5.一个顺序表L，元素为整型，设计一个算法将比L的表头元素小的元素放在其左边，将比他大的元素放在右边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void move(sqlist &L)
{
	int temp;
	int i=0;
	int j=L.length-1;
	temp=L.data[i]
	while(i<j)
	{
		while(i<j&&L.data[j]>temp) --j;

		if(i<j)
		{
			L.data[i]=L.data[j];
			++i;
		}

		while(i<j&&L.data[i]<temp) ++i;

		if(i<j)
		{
			L.data[j]=L.data[j];
			--j;

		}
	}
	L.data[i]=temp;

}

此题需要好好的理解一下，主要是要知道，i和j是轮流移动的，不是同时移动的，这样就能够保证，在交换的时候不会造成元素丢失，因为他们是轮流着来移动，所以在交换元素之前，这个元素肯定已经存入到了其他的位置了。

6.将一个递增非空单链表中的相同值域的元素删除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void deletesil(LNode *L)
{
	LNode *p=L->next;
	LNode *q=L->next->next;
	*r;
	while(q!=NULL)
	{
		while(q!=NULL&&q->data=p->data)
		{
			q=q->next;
		}
		if (q!=NULL)
		{
			p=p->next;
			p->data=q->data;
		}
		q=p->next;
		p->next=NULL;
		while(q!=NULL)  //这里有点不理解。。。。
		{
			r=q;
			q=q->next;
			free(r);
			
		}
	}
}

7.删除一个单链表L中的最小值结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void deletesmall(LNode &L)
{
	LNode *p=L->next;
	LNode *ppre=L;
	LNode *qpre=L;
	LNode *q=L->next;
	while(q!=NULL)
	{
		if(q->data<p->data)
		{
			p=q;
			ppre=qpre;
		}
		qpre=q;
		q=q->next;

	}
	ppre->next=p->next;
	free(p);
}

此代码中，之所以要对p再使用一个前驱指针ppre，以及对q也使用了一个前驱指针qpre的原因是通过这前驱指针分别“记住”原来p和q指针的位置在哪。p指针用来指定最小值的位置，q指针则用来向前进，使元素一个一个的与目前p指针所指定的最小值作比较。

8.有一个线性表，采用带头结点的单链表L来存储。设计一个算法将其逆置。要求不能建立新结点，只能通过表中已有的结点的重新组合来完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
void reversel(LNode *L)
{
	LNode *p=L->next;
	LNode *q;
	L->next=NULL;
	while(p!=NULL)
	{
		q=p->next;
		p->next=L->next;
		L->next=p;
		p=q;
	}
}

9.设计一个算法，将一个带头结点为A的单链表分解为两个单链表A和B，A链表中含有原来链表中data域中为奇数的结点，B链表中含有原来链表中data域中为偶数的结点。且保持相对位置不变。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void seletejiandou(LNode *A,LNode *&B)
{
	LNode *p,*q,*r;
	B=(LNode*)malloc(sizeof(LNode));
	B->next=NULL;
	r=B;
	p=A;
	while(p->next!=NULL)
	{
		if(p->next->data%2==0)
		{
			q=p->next;
			p->next=q->next;
			q->next=NULL;
			r->next=q;
			r=q;

		}
		else p=p->next;
	}

}

10.写出一个函数，逆序打印单链表中的数据，假设指针L指针指向了单链表的开始结点。

1
2
3
4
5
6
7
8
void reprint(LNode *L)
{
	if(L!=NULL)
	{
		reprint(L->next);  //递归逆序打印开始结点的后面的数据
		cout<<L->data<<" ";
	}
}

11.编写一个函数，以不多于3n/2的平均比较次数，找出在一个n个整数的顺序表A中的最大值和最小值。

1
2
3
4
5
6
7
8
9
10
11
12
void searchmaxandmin(int A[], int n,int &max,&min)
{
	max=min=A[1];
	for(int i=2,i<=n,++i)
	{
		if(A[i]>max)
			max=A[i];
		else if(A[i]<min)
			min=A[i];

	}
}

12.假设一个链表只有一个头指针head，设计一个算法，查找链表中倒数第k个位置上的结点，查找成功就返回data值，且返回1，若不成功就返回0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int findElem(LNode *head,int k)
{
	p1=head->next;
	p=head;
	i=1;
	while (p1!=NULL)
	{
		p1=p1->next;
		++i;
		if(i>k)
			p=p->next;
	}
	if (p==head)
		return 0;
	else
	{
		count<<p->data;
		return 1;
	}
}

13.设将n个整数存放在一维数组R中，设计一个尽可能高效的算法将R中保存的序列循环左移P个位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void reverse(int R[],int l,int r)
{
	int i,j;
	int temp;
	for (i=l,j=r,i<j,++i,--j)
	{
		temp=R[i];
		R[i]=R[j];
		R[j]=temp;
	}
	
}
void RCR(int R[],int n,int p)
{
	if(p<0||p>n)
		cout<<"Error"<<endl;
	else
	{
		reverse(R,0,p-1);  //先将前p个逆置
		reverse(R,p,n-1);  //接着将剩下的逆置
		reverse(R,0,n-1);  //最后将所有的一起再逆置一下
	}
}

14.已知一个整数序列A(a0,a1,a2,..ai..,an-1)其中0<=ai<n(0<=i<n).如果其中有超过一半的元素的值相同，那么这个相同的值就称之为”主元素”。假设A中的n个元素保存在一个一维数组中，设计一个算法，找出A中的主元素，如果有则输出他，如果没有就输出为-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int majority(int A[],int n)
{
	int i ,c, count=1;
	c=A[0];
	for (i=1,i<n,i++)
		if(A[i]==c)
			count++;
		else
		{
			if(count>0)
				count--;
			else
			{
				c=A[i];
				count=1;
			}
				
		}
	if(count>0)
	{
		for(i=count=0,i<n,i++)
		{
			if(A[i]==c)
				count++;
		}
			
				
	}
	if(count>n/2)
		return c;	
	else
		return -1;	
}