SamJ's blog

数据结构和算法（一）

algorithm
Word count: 1.9kReading time: 9 min
2019/09/06 Share

链表操作

  1. 头插法
1
2
3
4
5
6
7
8
9
10
11
12
13
void listHeadInsert(pStudent_t *ppHead,Student_t **ppTail,int val)
{
	pStudent_t pNew=(pStudent_t)calloc(1,sizeof(Student_t));
	pNew->num=val;
	if(NULL==*ppHead)//判断链表是否为空
	{
		*ppHead=pNew;
		*ppTail=pNew;
	}else{
		pNew->pNext=*ppHead;
		*ppHead=pNew;
	}
}

先申请新结点空间，给新结点赋值，判断链表是否为空，空则头尾都指向新结点，不为空则pNew->next=*ppHead, *ppHead=pNew,及时更新头指针

  1. 尾插法
1
2
3
4
5
6
7
8
9
10
11
12
13
void listTailInsert(pStudent_t *ppHead,Student_t **ppTail,int val)
{
	pStudent_t pNew=(pStudent_t)calloc(1,sizeof(Student_t));
	pNew->num=val;
	if(NULL==*ppTail)
	{
		*ppHead=pNew;
		*ppTail=pNew;
	}else{
		(*ppTail)->pNext=pNew;
		*ppTail=pNew;
	}
}

(*ppTail)->next=pNew, *ppTail=pNew

  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
void listSortInsert(pStudent_t *ppHead,Student_t **ppTail,int val)
{
	pStudent_t pNew=(pStudent_t)calloc(1,sizeof(Student_t));
	pStudent_t pCur,pPre;
	pCur=pPre=*ppHead;
	pNew->num=val;
	if(NULL==pCur)//判断链表是否为空
	{
		*ppHead=pNew;
		*ppTail=pNew;
	}else if(val<pCur->num)//头插法
	{
		pNew->pNext=*ppHead;
		*ppHead=pNew;
	}else{
		while(pCur)//插入到中间
		{
			if(pCur->num>val)
			{
				pPre->pNext=pNew;
				pNew->pNext=pCur;
				break;
			}
			pPre=pCur;
			pCur=pCur->pNext;
		}
		if(NULL==pCur)//这时就要插入到尾部
		{
			pPre->pNext=pNew;
			*ppTail=pNew;
		}
	}
}

先判断链表是否为空，再判断新插入节点的值是否小于头结点的值，否则向后遍历遍历到pCur的值大于新值，插到pCur前面，若直到pCur为空都不大于新值，插入链表尾部。

  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
34
35
36
37
38
39
void listDelete(pStudent_t *ppHead,Student_t **ppTail,int deleteNum)
{
	pStudent_t pCur=*ppHead,pPre;
	pPre=pCur;
	if(NULL==pCur)
	{
		printf("List is empty\n");
		return;
	}else if(pCur->num==deleteNum)//删除的是头部
	{
		*ppHead=pCur->pNext;
		if(NULL==*ppHead)
		{
			*ppTail=NULL;
		}
	}else{
		while(pCur)//删除的是中间或者尾部
		{
			if(pCur->num==deleteNum)
			{
				pPre->pNext=pCur->pNext;
				break;
			}
			pPre=pCur;
			pCur=pCur->pNext;
		}
		if(NULL==pCur)//没有找到对应结点
		{
			printf("Don't find deleteNum\n");
			return;
		}
		if(pCur==*ppTail)
		{
			*ppTail=pPre;
		}	
	}
	free(pCur);
	pCur=NULL;
}

先判断链表是否为空，然后判断头结点是否是要删除的节点，再遍历链表，找要删除的节点

  1. 链表修改
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void listModify(pStudent_t pHead,int num,float score)
{
	while(pHead)
	{
		if(pHead->num==num)
		{
			pHead->score=score;
			break;
		}
		pHead=pHead->pNext;
	}
	if(NULL==pHead)
	{
		printf("Don't find modify num\n");
	}
}

遍历链表，找到要修改的节点

层次建立二叉树

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
typedef char ElemType;
typedef struct node_t{
	ElemType c;
	struct node_t *pleft;
	struct node_t *pright;
}Node_t,*pNode_t;

typedef struct queue_t{
	pNode_t insertPos;
	struct queue_t *pNext;
}Queue_t,*pQueue_t;

void buildBinaryTree(pNode_t* treeRoot,pQueue_t* queHead,pQueue_t* queTail,ElemType val)
{
	pNode_t treeNew=(pNode_t)calloc(1,si  sizeof(Node_t));
	pQueue_t queNew=(pQueue_t)calloc(1,sizeof(Queue_t)); //辅助队列节点
	pQueue_t queCur=*queHead;
	treeNew->c=val;
	queNew->insertPos=treeNew;
	if(NULL==*treeRoot)
	{
		*treeRoot=treeNew;
		*queHead=queNew;
		*queTail=queNew;
	}else{
		(*queTail)->pNext=queNew;	
		*queTail=queNew;			//新结点入队
		if(NULL==queCur->insertPos->pleft)//队首左孩子为空
		{
			queCur->insertPos->pleft=treeNew;//节点插到左孩子
		}else if(NULL==queCur->insertPos->pright)
		{
			queCur->insertPos->pright=treeNew;//节点插到右孩子，队首出队
			*queHead=queCur->pNext;
			free(queCur);
			queCur=NULL;
		}
	}
}

利用辅助队列实现

排序算法

常用算法复杂度表

2019-06-17_203943

  1. 选择排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void arrSelect(int *arr)
{
	int i,j,maxPos;
	for(i=N;i>1;i--)//外层控制无序数数目
	{
		maxPos=0;
		for(j=1;j<i;j++)
		{
			if(arr[j]<arr[maxPos])
			{
				maxPos=j;
			}
		}
		SWAP(arr[maxPos],arr[i-1]);
	}
}

每次选择最大的数放在其最终位置

  1. 插入排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void arrInsert(int *arr)
{
	int i,j,insertValue;
	for(i=1;i<N;i++)
	{
		insertValue=arr[i];
		for(j=i-1;j>=0;j--)
		{
			if(arr[j]>insertValue)
			{
				arr[j+1]=arr[j];
			}else{
				break;
			}
		}
		arr[j+1]=insertValue;
	}
}

每次都拿第i个数从后往前比，若这个数比第i个数大就将其往后移直到找到第i个数的位置

  1. 希尔排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void arrShell(int *arr)
{
	int i,j,insertValue,gap;
	for(gap=N>>1;gap>0;gap>>=1)
	{
		for(i=gap;i<N;i++)
		{
			insertValue=arr[i];
			for(j=i-gap;j>=0&&arr[j]>insertValue;j=j-gap)
			{
				arr[j+gap]=arr[j];
			}
			arr[j+gap]=insertValue;
		}
	}
}

插入排序的变形，将所有1改成gap，gap第一次是N/2，接下来每次都/2

  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
int partition(int *arr,int left,int right)
{
	int i,k;
	for(i=left,k=left;i<right;i++)
	{
		if(arr[right]>arr[i])
		{
			SWAP(arr[i],arr[k]);
			k++;
		}
	}
	SWAP(arr[k],arr[right]);
	return k;
}
void arrQuick(int *arr,int left,int right)
{
	int pivot;
	if(left<right)
	{
		pivot=partition(arr,left,right);
		arrQuick(arr,left,pivot-1);
		arrQuick(arr,pivot+1,right);
	}
}

每次利用partition函数找到一个数，使他的左边都小于它，右边都大于它，递归

  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
34
35
void adjustMaxHeap(int *arr,int adjustPos,int arrLen)
{
	int dad=adjustPos;
	int son=2*dad+1;
	while(son<arrLen)
	{
		if(son+1<arrLen&&arr[son]<arr[son+1])
		{
			son++;
		}
		if(arr[dad]<arr[son])
		{
			SWAP(arr[dad],arr[son]);
			dad=son;
			son=2*dad+1;
		}else{
			break;
		}
	}
}
void arrHeap(int *arr)
{
	int i;
	//调整为大根堆
	for(i=N/2-1;i>=0;i--)
	{
		adjustMaxHeap(arr,i,N);
	}
	SWAP(arr[0],arr[N-1]);
	for(i=N-1;i>1;i--)
	{
		adjustMaxHeap(arr,0,i);
		SWAP(arr[0],arr[i-1]);
	}
}

堆排序对数组排序，心中有棵树，建堆的过程最为重要

  1. 计数排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void arrCount(int *arr)
{
	int i,j,k;
	int count[M]={0};
	for(i=0;i<N;i++)
	{
		count[arr[i]]++;
	}
	k=0;
	for(j=0;j<M;j++)//要填入的值的范围
	{
		for(i=0;i<count[j];i++)//每一个要填入值的数量
		{
			arr[k]=j;
			k++;
		}
	}
}

空间换时间，值的范围太大的时候效率会变低

  • qsort可以用来对链表排序，将链表每个节点赋给指针数组，再对该数组进行排序

    封装成类似于qsort接口的堆排序

    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
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    //堆排序
    void swapp(char *p1, char *p2, size_t size)
    {
    	char p;
    	int i;
    	for(i=0;i<size;i++)
    	{
    		p = *p1;
    		*p1 = *p2;
    		*p2 = p;
    		p1++;
    		p2++;
    	}

    }

    void adjustMaxHeap(void *base, void *cur,  size_t num, size_t size)
    {
    	char *dad = (char*)cur;
    	char *lo = (char*)base;
    	char *hi = (char*)base + size*(num);
    	char *son = (char*)base + (dad-lo)*2 + size;
    	while (son <= hi)
    	{
    			if((son+size)<=hi&&*son<*(son+size))
    			{
    				son+=size;
    			}
    			if(*dad<*son)
    			{
    				swapp(dad, son,size);
    				dad = son;
    				son =lo + (dad-lo)*2 + size;
    			}
    			else
    			{
    				break;
    			}
    		
    	}
    }

    void arrHeap(void *base, size_t num, size_t size, int (*compare)(const void *, const void *))
    {
    	char *lo, *hi, *cur, *t;
    	lo = (char*)base;
    	hi = (char*)base + size*(num-1);
    	for(cur=lo+num/2*size-size;cur>=lo;cur-=size)
    	{
    		adjustMaxHeap(base,cur,num,size);
    	}
    	swapp(lo, hi, size);
    	for(cur=hi-size;cur>lo;cur-=size)
    	{
    		adjustMaxHeap(base,lo,(cur-lo)/size,size);
    		swapp(lo, cur, size);
    	}
    	if(compare<0)
    	{
    		cur=lo;
    		t=hi;
    		while(cur<t)
    		{
    			swapp(cur, t,size);
    			cur+=size;
    			t-=size;
    		}
    	}

    }

    这样堆排序可以排序任意数据类型的数组，结构体数组等。

    红黑树

    1. 红黑树特点
    • 节点有红色和黑色，根是黑色节点
    • 每个红色节点都必须有两个黑色子节点
    • 从根节点到每个叶子都有相同数量的黑色节点
    2. 插入时的情况（新结点初始时是红色）

    1. 新结点的父亲节点是黑色，直接插入

    2. 新结点的父节点和叔叔节点都是红色，但祖父节点是黑色。把祖父节点染成红色，父亲和叔叔节点染成黑色，再插入。2019-06-18_211630

    3. 新结点的父节点是红色，叔叔节点是黑色或者缺失，插入节点，父亲节点，祖父节点呈之字形，进行左旋（或右旋）：2019-06-18_213237

    4. 情形3此时还不满足红黑树所有性质，此时状态可以称为情形4，要对顶端的节点进行左旋（右旋）并将顶端节点染成红色，父亲的红色节点染成黑色，就可以构成红黑树

      2019-06-18_2132237

CATALOG
  1. 1. 链表操作
  2. 2. 层次建立二叉树
  3. 3. 排序算法
  4. 4. 红黑树
    1. 4.0.1. 1. 红黑树特点
    2. 4.0.2. 2. 插入时的情况（新结点初始时是红色）
Total : 27
2021
2019
C++ paper hexo algorithm algorithm,c++ linux, C japanese,anime