データ構造ベースチェーンテーブルの挿入ソートプログラム

1.問題の説明
チェーンテーブルの挿入ソートプログラム
2.試験用例
チェーンテーブル要素は、0、1、2および大きな数の順になります.
3.チェーンテーブルの挿入ソートアルゴリズムの考え方
3.1判検元チェーンテーブルは並べ替えを実現することができる.
3.2ループ挿入関数に入る:
3.2.1チェーンテーブルの現在のノードをコピーする;
3.2.2チェーンテーブルの現在のノードを削除する;
3.2.3チェーンテーブルの現在のノードに出入りする;
4.チェーンテーブル注記
4.1チェーンテーブルを作成する前に、ヘッドノードにメモリ領域を割り当てない(空のチェーンテーブルを避ける).
4.2チェーンテーブルを作成するとき、2つのポインタが梭形に前進する.
4.3入力ソート関数はチェーンテーブル変数のアドレスである.
5.ソース実装

<pre name="code" class="cpp">#include<iostream>
#include<stdio.h>
#include<math.h>

using namespace std;

typedef struct LinkNode
{
	int data;
	LinkNode *next;
}LinkNode;

void InsertSort(LinkNode **phead)
{	
	//                   2    
	if(phead==NULL||*phead==NULL||(*phead)->next == NULL)
		return;
	LinkNode *pCur = *phead;
	int i = 0;
	for(;pCur->next!=NULL;) 
	{
		//          
		LinkNode *pNode = new LinkNode;
		pNode->data = pCur->next->data;
		pNode->next = NULL;
		//          
		LinkNode *tmp = *phead;
		//      ，   pCur    
		if((*phead)->data>pNode->data)
		{
			pNode->next = *phead;
			*phead = pNode;
			LinkNode *DelNode = pCur->next;
			pCur->next = pCur->next->next;
			delete DelNode;
			DelNode = NULL;
			continue;
		}
		else
		{
			//   
			if(pNode->data>=pCur->data)
			{
				pCur = pCur->next;
				continue;
			}
			//   
			else
			{
				while(tmp!=pCur&&tmp->next->data<=pNode->data)
					tmp = tmp->next;
				pNode->next = tmp->next;
				tmp->next = pNode;
				LinkNode *DelNode = pCur->next;
				pCur->next = pCur->next->next;
				delete DelNode;
				DelNode = NULL;
			}
		}		
	}
}

#define Num 10 //         32，     
int main() {
	int i=0;
	LinkNode *mylink = NULL; //       ，      
	LinkNode *ptr1,*ptr2 = NULL;
	for(i=0;i<Num;i++)
	{	
		if(mylink == NULL)
		{
			mylink = new LinkNode;
			ptr1 = mylink;
		}
		ptr1->next = NULL;
		if(i%3 == 0)
			ptr1->data = 3;
		else
			ptr1->data = 5+pow(-2,i+1);
		ptr2 = ptr1;
		ptr1 = ptr1->next;
		ptr1 = new LinkNode;
		ptr2->next = ptr1;
	}
	if(mylink!=NULL)
		ptr2->next = NULL;
	InsertSort(&mylink);
	LinkNode *tmp = mylink;
	for(i=0;i<Num;i++)
	{
		cout<<tmp->data<<endl;
		tmp = tmp->next;
	}
	return 0;
}

 
 

 
 
 
6.后记
 
 
6.1 链表之事，画图之事，未图未知，奈何奈何 ！！！
 
 
6.2 为什么 **phead ？
 
 
因为可能会修改头指针，如果头指针修改不是对指向地址的的指针赋值的时候，赋值给单纯的地址头指针将导致无功而返，当然，如果确信不会修改头指针，那么就无所谓啦！！！
 
 
6.3 TFhiirnskt ！！！
 
 
6.4 二分插入排序源码：
 
  
 
#include<iostream>
#include<stdio.h>
#include<math.h>

using namespace std;

void InsertSort(int *a,int Num)
{	
	if(Num < 2)
		return;
	for(int i=1;i<Num;i++)
	{
		int tmp = a[i];
		int high = i-1;
		int low = 0;
		while(high>=low)
		{
			int mid = (high+low)/2;
			if(a[mid]<=tmp)
				low = mid+1;
			else
				high = mid-1;
		}
		for(int j = i;j>high+1;j--)
			a[j] = a[j-1];
		a[j] = tmp;
	}
	return ;
}

#define Num 5 
int main() {
	int a[] = {11,3,3,2,2,4,5};
	InsertSort(a,Num);
	for(int i=0;i<Num;i++)
		cout<<a[i]<<endl;
	return 0;
}