Created
April 1, 2016 15:01
-
-
Save hunandy14/12d951e5fcddcee303614cc3b8e5bb59 to your computer and use it in GitHub Desktop.
雙向鏈結
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/********************************************************** | |
Name:KUAS-Hw/Hw05 | |
DATE:2016/03/29 | |
Final:2016/04/01 | |
By CharlotteHong | |
**********************************************************/ | |
//========================================================= | |
#include <iostream> | |
#include <stdio.h> | |
using namespace std; | |
//========================================================= | |
/* typedef 型態宣告,可以想像成文字取代功能 | |
比如說 [typedef A B] 可以把 [A(很長)]換成[B(單詞)] | |
以下就是一個範例,把長長的一串結構宣告換成node*/ | |
typedef struct doulnk_struct node; | |
struct doulnk_struct{ | |
node *link; | |
int data; | |
node *rlink; | |
}; | |
//========================================================= | |
/* 切割字串 (要切割的字串,切割的符號) | |
字串的格式如 srt[]="1,2"; | |
回傳值為陣列指標地址,陣列[0]是長度 */ | |
int* str_split(const char* str, const char* sp); | |
//========================================================= | |
/* API 說明文件*/ | |
// 建立新節點並回傳節點地址 (節點的值) | |
node* node_creat(int data); | |
// 鏈結的長度 (鏈結的開頭) | |
int node_lenth(node* nh); | |
// 尋找最後一個節點的地址 (任意節點) | |
node* nodep_final(node* n); | |
// 印出節點的值 (任意節點) | |
void nodep_printpt(node* n); | |
// 印所有節點的值 (鏈結開頭) | |
void node_printall(node* nh); | |
// 印所有節點的資料 (鏈結開頭) | |
void node_printalldata(node* nh); | |
// 印所有節點的地址 (鏈結開頭) | |
void node_printalladd(node* nh); | |
// 在鏈結的最後方新增節點 (任意節點,新增節點的數值) | |
void nodep_append(node* n, int data); | |
// 批次在尾端新增節點 (任意節點,陣列,數量) | |
void nodep_input(node* n, int *ptr, int len); | |
// 節點地址查找,支持反向查找 (鏈結開頭,位置) | |
node* node_address(node* nh, int p); | |
// 插入節點,插入點會被往後推 (鏈結開頭,插入位置,數值) | |
void node_insert(node* nh, int p, int data); | |
// 刪除節點 (鏈結開頭,刪除位置) | |
void node_delete(node* nh, int p); | |
// 刪除鏈結,不會刪除鏈結開頭 (鏈結開頭) | |
void node_deleteall(node* nh); | |
// 確認是否為開頭 (任意節點) | |
int nodep_checkhead(node* n); | |
// 取出節點,回傳取出的地址,注意點沒有移除 (任意節點) | |
node* nodep_unlink(node* n1); | |
// 插入節點,n2插到n1前面 (任意節點,任意節點) | |
void nodep_insert(node* n1, node* n2); | |
// n1鏈結尾端加入n2鏈結 (任意節點,節點開頭) | |
void nodep_link(node* n1, node* n2); | |
// 查詢順序是否正確 (任意節點,任意節點) | |
int nodep_checkseq(node* n1, node* n2); | |
// 節點交換 (任意節點,任意節點) | |
void nodep_change(node* n1, node* n2); | |
// 尋找節點開頭的地址 (任意節點) | |
node* nodep_head(node* n); | |
// 找鏈結資料 (鏈結開頭,資料位置) | |
int node_value(node* nh, int p); | |
// 排序鏈結資料 (鏈結開頭,排序頭,排序尾) | |
void node_short(node* nh, int h, int f); | |
// 排序鏈結全部資料 (鏈結開頭) | |
void node_short(node* nh); | |
// 排序鏈結前幾筆資料 (鏈結開頭,排序位置) | |
void node_short(node* nh,int p); | |
//========================================================= | |
int main(int argc, char const *argv[]){ | |
/* 開頭節點 */ | |
node *nh=node_creat(-1); | |
/* 批次匯入節點 */ | |
// int data[]={18,15,65,0,1,15,6,-4}; | |
// int len = sizeof(data)/sizeof(data[0]); | |
// nodep_input(nh,data,len); | |
char str[]="18,15,65,0,1,15,6,-4"; | |
int *str_data=str_split(str,",")+1; | |
int len = *(str_data-1); | |
nodep_input(nh,str_data,len); | |
/* 排序節點 */ | |
node_printalldata(nh); | |
// node_printall(nh); | |
node_short(nh); | |
/* 印出節點 */ | |
cout << "=====================================" <<endl; | |
node_printalldata(nh); | |
// node_printall(nh); | |
/* 釋放記憶體 */ | |
node_deleteall(nh); | |
delete [] nh; | |
delete [] (str_data-1); | |
return 0; | |
} | |
//========================================================= | |
node* nodep_unlink(node* n2){ | |
if (nodep_checkhead(n2) == 0){ | |
node *n1=n2->link; | |
node *n3=n2->rlink; | |
if (n3==NULL){ | |
n1 -> rlink = NULL; | |
n2 -> link = NULL; | |
n2 -> rlink = NULL; | |
} | |
else{ | |
n1 -> rlink = n3; | |
n3 -> link = n1; | |
n2 -> link = NULL; | |
n2 -> rlink = NULL; | |
} | |
} | |
return n2; | |
} | |
//========================================================= | |
node* node_creat(int data){ | |
node *n; | |
n = new doulnk_struct; | |
n -> link = NULL; | |
n -> data = data; | |
n -> rlink = NULL; | |
return n; | |
} | |
node* nodep_final(node* n){ | |
int lenth=0; | |
node* tmp=n; | |
while( tmp->rlink != NULL && lenth<=999){ | |
tmp=tmp->rlink; | |
lenth++; | |
} | |
return tmp; | |
} | |
int node_lenth(node* nh){ | |
int lenth=0; | |
node* tmp=nh; | |
while( tmp->rlink != NULL && lenth<=999){ | |
tmp=tmp->rlink; | |
lenth++; | |
} | |
return lenth; | |
} | |
void nodep_printpt(node* n){ | |
cout << "" << n << " || "; | |
cout << "[" << n->link << "] "; | |
cout << "[" << n->data << "] "; | |
cout << "[" << n->rlink << "] " << endl; | |
} | |
void node_printall(node* nh){ | |
node* tmp=nh; | |
for (int i = 0; i < node_lenth(nh)+1 ; ++i){ | |
cout << "" << tmp << " || "; | |
cout << "[" << tmp->link << "] "; | |
if (i==0) | |
cout << " "; | |
cout << "[" << tmp->data << "] "; | |
cout << "[" << tmp->rlink << "] " << endl; | |
tmp=tmp->rlink; | |
} | |
} | |
void node_printalldata(node* nh){ | |
node* tmp = nh->rlink; | |
for (int i = 0; i < node_lenth(nh) ; ++i){ | |
cout << "[" << tmp->data << "] "; | |
tmp=tmp->rlink; | |
} | |
cout << endl; | |
} | |
void node_printalladd(node* nh){ | |
node* tmp=nh; | |
for (int i = 0; i < node_lenth(nh)+1 ; ++i){ | |
cout << "[" << tmp->data << "]"; | |
cout << "[" << tmp << "] "; | |
tmp=tmp->rlink; | |
} | |
cout << endl; | |
} | |
void nodep_append(node* n, int data){ | |
node* temp = nodep_final(n); | |
node* nf = node_creat(data); | |
temp -> rlink = nf; | |
nf -> link = temp; | |
} | |
void nodep_input(node* n, int *ptr, int len){ | |
for (int i = 0; i < len; ++i){ | |
nodep_append(n,ptr[i]); | |
} | |
} | |
node* node_address(node* nh, int p){ | |
node *temp=nh; | |
int p1=p; | |
//如果輸入負值 | |
if ( p<0 ){ | |
if (p<=-node_lenth(nh)) | |
p1=-node_lenth(nh); | |
p1=p1+node_lenth(nh)+1; | |
}else{ | |
if (p>=node_lenth(nh)) | |
p1=node_lenth(nh); | |
} | |
//開始查找 | |
for (int i = 0; i < p1; ++i){ | |
temp=temp->rlink; | |
} | |
return temp; | |
} | |
void node_insert(node* nh, int p, int data){ | |
node *target,*temp; | |
target = node_address(nh,p); | |
temp = node_creat(data); | |
cout << nh << "||" <<target << "||" << temp << endl; | |
if ( nodep_checkhead(node_address(target,0)) == 0){ | |
// 先將創建的點地址指好 | |
temp -> link = target -> link; | |
temp -> rlink = target; | |
// 在將目標的地址指好 | |
target -> link = temp; | |
// 最後將創建的那一串接上 | |
temp -> link -> rlink = temp; | |
} | |
} | |
void node_delete(node* nh, int p){ | |
node *target=node_address(nh,p); | |
if ( nodep_checkhead(node_address(target,0)) == 0){ | |
target -> link -> rlink = target -> rlink; | |
delete [] target; | |
} | |
} | |
void node_deleteall(node* nh){ | |
for (int i = node_lenth(nh); i > 0; --i){ | |
node_delete(nh,i); | |
} | |
} | |
int nodep_checkhead(node* n){ | |
if ( n->link == NULL ){ | |
cout << " **Error! Head don't use.**" << endl; | |
return 1; | |
} | |
else | |
return 0; | |
} | |
void nodep_insert(node* n1, node* n2){ | |
if (nodep_checkhead(n1) == 0){ | |
n2 -> link = n1 -> link; | |
n2 -> rlink = n1; | |
n1 -> link = n2; | |
n2->link -> rlink = n2; | |
} | |
} | |
void nodep_link(node* n1, node* n2){ | |
node* temp = nodep_final(n1); | |
temp -> rlink = n2; | |
n2 -> link = temp; | |
} | |
int nodep_checkseq(node* n1, node* n2){ | |
node *temp=n1->rlink; | |
for (int i = 0; i < node_lenth(n1); ++i){ | |
if (temp == n2) | |
return 1; | |
temp = temp->rlink; | |
} | |
return 0; | |
} | |
void nodep_change(node* n1, node* n2){ | |
if (n1==n2) return; | |
// 如果n2在前調整順序 | |
node *nh, *nf, *n1r, *n2r; | |
if (nodep_checkseq(n1,n2)==1){ | |
nh=n1; | |
nf=n2; | |
n1r = n1->rlink; | |
n2r = n2->rlink; | |
}else{ | |
nh=n2; | |
nf=n1; | |
n1r = n2->rlink; | |
n2r = n1->rlink; | |
} | |
// 如果他們相鄰 | |
if (nf == n1r){ | |
nodep_unlink(nh); | |
//如果n2在末端 | |
if (n2r==NULL){ | |
nodep_link(nf,nh); | |
}else { | |
nodep_insert(n2r,nh); | |
} | |
} | |
// 如果他們不相鄰 | |
else{ | |
nodep_unlink(nf); | |
nodep_insert(n1r,nf); | |
nodep_unlink(nh); | |
// 如果n2在末端 | |
if (n2r==NULL){ | |
nodep_link(nf,nh); | |
}else { | |
nodep_insert(n2r,nh); | |
} | |
} | |
} | |
node* nodep_head(node* n){ | |
int lenth=0; | |
node* tmp=n; | |
while( tmp->link != NULL && lenth<=999){ | |
tmp=tmp->link; | |
lenth++; | |
} | |
return tmp; | |
} | |
int node_value(node* nh, int p){ | |
return node_address(nh,p)->data; | |
} | |
void node_short(node* nh, int h, int f){ | |
int i=h, j=h+1; | |
for ( j; j<=f; j++) | |
for(i=j-1; i>=h && node_value(nh,i)>node_value(nh,i+1); i--){ | |
//如果比前面大就一直往前換,直到比前面小 | |
nodep_change(node_address(nh,i),node_address(nh,i+1)); | |
} | |
} | |
void node_short(node* nh){ | |
return node_short(nh,1,node_lenth(nh)); | |
} | |
void node_short(node* nh,int p){ | |
return node_short(nh,1,p); | |
} | |
//========================================================= | |
int* str_split(const char* str, const char* sp){ | |
// 計算字串長度 | |
int slen=0; | |
while (str[slen]!=0 && slen<=999) | |
slen++; | |
// 計算字串內總共有幾個數 | |
int ilen=1; | |
for (int i = 0; i < slen; ++i) | |
if ( str[i] == sp[0]) | |
ilen++; | |
// 根據長度配置記憶體 | |
int *ptr = new int[ilen+1]; | |
*ptr = (int)(ilen); | |
// 開始切割 | |
int tempflag=0,index=1; | |
char *temp = new char[1]; | |
for (int i = 0; i <= slen; ++i){ | |
if (str[i] == sp[0] || i==slen){ | |
ilen++; | |
tempflag=0; | |
// printf("temp=%c%c\n",temp[0],temp[1] ); | |
sscanf(temp, "%d", (ptr+index)); | |
index++; | |
delete [] temp; | |
temp = new char[1]; | |
} | |
else {temp[tempflag++]=str[i];} | |
} delete [] temp; | |
return ptr; | |
} | |
/* ================================================== */ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment