データ構造ベースチェーンテーブルの挿入ソートプログラム
4312 ワード
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.ソース実装
チェーンテーブルの挿入ソートプログラム
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; }