シングルチェーン表とその上での操作は実現します.
単一鎖表は一般的なデータ構造としてプログラム設計において重要である.私も最近参加した面接ですが、技術面接の時に、チェーンシートの質問をする会社が多いと思います.ここでまとめてみます.
本論文の完全コードは以下の通りです.https://github.com/JayYangSS/Data-Structure-and-Algorithm/tree/master/Linklist
まず、シングルチェーンテーブルの基本データユニットを作成します.
本論文の完全コードは以下の通りです.https://github.com/JayYangSS/Data-Structure-and-Algorithm/tree/master/Linklist
まず、シングルチェーンテーブルの基本データユニットを作成します.
typedef struct Node
{
int data;
Node *next;
}Node;class LinkList
{
public:
LinkList(void);
~LinkList(void);
Node* SetupLinkList(void);
// //diaplay the data of link list
void diaplay(Node* head);
// ，
Node* SetupOrderedLinkList(bool down);
// pp
void Insert(Node* pp,Node *newNode);
//
Node* Merge(Node* first, Node* second);
//
void copyto(Node* src, Node* dst);
//
Node* Merge2(Node* first, Node* second);
//
Node* FindMid(Node* head);
//
Node* SortLinkList(Node* head);
};
//
void LinkList::copyto(Node* src, Node* dst)
{
Node *p,*q,*tmp;
q=new Node;
dst->next=q;
p=src->next;
do
{
q->data=p->data;
p=p->next;
if(p!=NULL){
tmp=new Node;
q->next=tmp;
q=q->next;
q->next=NULL;
}
}while(p!=NULL);
}<pre name="code" class="cpp">Node* LinkList::SetupLinkList(void)
{
Node *head,*p,*q;
cout<<"input the data(input '-1' to end):"<<endl;
head=new Node;
head->next= NULL;
q=head->next;
while (1)
{
int a;
cout<<"input data:";
cin>>a;
if (a==-1)break;
else{
p=new Node;
if (head->next==NULL)
{
head->next=p;
p->data=a;
p->next=NULL;
q=p;
}
else
{
p->data=a;
q->next=p;
q=p;
q->next=NULL;
}
}
}
return head;
}
<pre name="code" class="cpp">// //diaplay the data of link list void LinkList::diaplay(Node* head) { Node *p; if (head == NULL) cout << "The head of the LinkList is NULL!" << endl; else if (head->next==NULL) { cout<<"Linklist is empty!"<<endl; } else{ p=head->next; while(p!=NULL) { cout<<p->data<<endl; p=p->next; } } }// pp void LinkList::Insert(Node* pp,Node *newNode) { if (pp->next==NULL) { pp->next=newNode; newNode->next=NULL; } else{ Node *tmp=pp->next; pp->next=newNode; newNode->next=tmp; } }建立有序单链表的程序如下：
二つの秩序化された単一チェーン表を一つの秩序化された単一チェーン表に結合して、第一の実現方法の構想はまずその中の一つのシングルチェーン表を一つの新しいチェーンテーブルheadにコピーして、もう一つのチェーンテーブルから遍歴し始めます.第二のチェーン表の要素を取り出すごとに、headチェーン表の各要素と比較して、順番に挿入すればいいです.(この考えはプログラムがちょっと乱れていて、複雑度が大きい)コードは以下の通りです.Node* LinkList::SetupOrderedLinkList(bool down) //down=true ，down=false { Node *head,*p,*q; cout<<"input the data(input '-1' to end):"<<endl; head=new Node; head->next= NULL; q=head->next; while (1) { int a; cout<<"input data:"; cin>>a; if (a==-1)break; else{ p=new Node; p->data=a; // if (head->next==NULL) { head->next=p; p->next=NULL; q=p; } else { Node *search,*pre; search=head->next; pre=head; while(pre->next!=NULL) { if (down==false)// { // // ， // ， if (a>=search->data) { if (search->next==NULL)Insert(search,p); pre=pre->next; search=search->next; } else { Insert(pre,p); break; } } else// { if (a<=search->data) { if (search->next==NULL)Insert(search,p); pre=pre->next; search=search->next; } else { Insert(pre,p); break; } } } } } } return head; }第二の統合の方法は第一の方法より簡単で、考えは:2つのチェーンテーブルの第一のノードの要素を取り出し、その中の小さな要素を新しいチェーンテーブルに入れて、同時にチェーンテーブルの針を後に移動する(この要素をこのチェーンから取り除くのに相当する).二つのチェーンの中のポインタの大きさを比較して、上記の操作を繰り返します.一つのチェーンの中の要素が全部新しいチェーンに入れられている場合、もう一つのチェーンはまだ終わっていない場合、残りの部分を直接に新しいチェーンの末尾に入れます.得られた新しいチェーンは連結された秩序あるチェーンテーブルです.手順は以下の通りです.// Node* LinkList::Merge(Node* first, Node* second) { if(first->next==NULL) return second; else if (second->next==NULL) return first; else{ Node *d,*head;// Node *p1,*p2,*pre; head=new Node; copyto(first,head);// //p1=head->next; //pre=head; p2=second->next; while(p2!=NULL) //while(((p2->next!=NULL)&&p2!=NULL)|((p2!=NULL)&&(p2->next==NULL))) { p1=head->next; pre=head; while(pre!=NULL) { if ((p2->data>=p1->data)&&(p1->next!=NULL)) { p1=p1->next; pre=pre->next; if ((p1->next==NULL)&&(p2->data>=p1->data)) { Insert(p1,p2); p1=p1->next; pre=pre->next; p2=p2->next; break; } } else { d=new Node; d->data=p2->data; Insert(pre,d); if (p2->next==NULL){p2=p2->next;break;} p2=p2->next; pre=pre->next; break; } } } return head; } }無秩序な単一鎖表を並べ替えることを実現するために、正規並べ替え法を使用して、その主な考えは以下の通りである.Node* LinkList::Merge2(Node* first, Node* second) { Node *head,*tail; head=new Node; tail=head; first=first->next; second=second->next; if(first==NULL) return second; if(second==NULL) return first; while(first&&second) { if (first->data>second->data) { Node* tmp=new Node; tmp->data=second->data; tail->next=tmp; tail=tail->next; tail->next=NULL; // delete tmp; second=second->next; } else { Node* tmp=new Node; tmp->data=first->data; tail->next=tmp; tail=tail->next; tail->next=NULL; //delete tmp; first=first->next; } } if(first==NULL) { while(second) { Node *tmp=new Node; tmp->data=second->data; tail->next=tmp; tail=tail->next; tail->next=NULL; second=second->next; } } else { while(first) { Node *tmp=new Node; tmp->data=first->data; tail->next=tmp; tail=tail->next; tail->next=NULL; first=first->next; } } return head; }
1.まずシングルチェーン表の中点を見つけて、二つのチェーン表に分けます.
2.前後の部分のチェーンを同じように操作し、それぞれ2つの部分のチェーンに分けて、このように繰り返し続けます.各チェーンテーブルには1つの要素しか含まれていません.この時、各チェーンテーブルはすべて秩序化されたチェーンテーブルです.
3.各秩序化された単一チェーン表を使用する前に実現された統合秩序化された単一チェーン表方法を統合し、最後にすべてのチェーンテーブルが一つに結合されるまで、このチェーンテーブルは並べ替えられた単一チェーン表である.
実装方法は再帰的に使用されます.このうち、シングルチェーンの表の中の点を探すという考えは、遊覧ポインタを使って、slowは一歩移動し、fastは二歩移動し、fastが最後に移動すると、slowはちょうど中点に移動します.// Node* LinkList::SortLinkList(Node* head) { if (!head)return NULL; if (!head->next)return head; Node *mid,*next=NULL,*head2; mid=FindMid(head); if (mid->next != NULL) { next = mid->next; // head2 = new Node; head2->next = next; mid->next = NULL; return Merge2(SortLinkList(head), SortLinkList(head2)); // } else return head; }Node* LinkList::FindMid(Node* head) { if(!head)return NULL; if(!head->next)return head; Node *slow,*fast; slow=head; fast=head; while(fast&&fast->next) { slow=slow->next; fast=fast->next->next;// slow ，fast ， fast ， slow } return slow; }