[C/C++ 演算法]-資料結構與演算法(文魁)：雙向鏈結串列以陣列為表示的使用範例

 

線上執行結果：http://www.tutorialspoint.com/compile_c_online.php

code2html：http://tohtml.com/

 

 

/* =============== Program Description =============== */
/* 程式名稱 : 9_3.cpp 				       */
/* 程式目的 : 雙向鏈結串列以陣列為表示的使用範例       */
/* 輸    入 : 整數陣列資料			       */
/* 輸    出 : 反轉的整數陣列資料,搜尋鍵值的位置	       */
/* =================================================== */
#define n 10
#define INVALID_LINK -2 /* 無效的連結 */
#define NULL_LINK	 -1	/* 結尾的連結 */
// 宣告標頭檔
#include "stdio.h"
// 宣告全域變數
int A[n][3];
int head = -1;
int tail = -1;
// 宣告函式原型
// 利用傳值的方式把整數data傳進addDNode函式中
void addDNode(int data);
// 利用傳值的方式把整數data傳進delDNode函式中
void delDNode(int data);
// 從findDNode函式中回傳一個整數
int findDNode(int data);
void main(void)
{
int D[n]={1,2,3,4,5,6,7,8,9,0};
int i,ret;
for(i=0;i<n;i++)
A[i][0]=0;
for(i=0;i<n;i++)
A[i][1]=INVALID_LINK;
for(i=0;i<n;i++)
A[i][2]=INVALID_LINK;
// 輸入的資料
printf(" Input Data : ");
for(i=0;i<n;i++)
{
printf("%d",D[i]);
addDNode(D[i]);
}
printf("\n");
// 鏈結序列中的資料
printf(" Data in LinkList : ");
i=head;
do
{
if(i==NULL_LINK)
break;
printf("%d",A[i][0]);
i=A[i][1];
}while((i!=INVALID_LINK)||(i!=NULL_LINK));
printf("\n");
// 尋找節點
ret = findDNode(D[4]);
if(ret==-1)
printf("%d is not find \n",D[4]);
else
printf(" Find %d from queue => array index %d\n",D[4],ret);
// 刪除節點
printf(" Delete Data from queue ");
for(i=0;i<n;i=i+2)
{
printf("%d",D[i]);
delDNode(D[i]);
}
printf("\n");
// 鏈結序列中的資料
printf(" Data in LinkList : ");
i=head;
do
{
if(i==NULL_LINK)
break;
printf("%d",A[i][0]);
i=A[i][1];
}while((i!=INVALID_LINK)||(i!=NULL_LINK));
printf("\n");
// 尋找節點
ret = findDNode(D[4]);
if(ret==-1)
printf("%d is not find \n",D[4]);
else
printf(" Find %d from queue = %d\n",D[4],ret);
getchar();
}
// 由開頭新增節點
void addDNode(int data)
{
int i;
if(head==NULL_LINK)
{
head=0;
A[head][0]=data;
A[head][1]=NULL_LINK;
A[head][2]=NULL_LINK;
}else{
for(i=0;i<n;i++)
{
if(A[i][1]==INVALID_LINK) /* 空的節點 */
{
A[i][0]=data;
A[head][2]=i; /* 把原本開頭的上一個指向新增節點 */
A[i][1]=head; /* 把新增節點的下一個指向原本開頭節點 */
A[i][2]=NULL_LINK; /* 把新增節點的下一個指向尾巴 */
head=i;
return;
}
}
printf("LinkArray is Full!\n");
}
}
// 刪除節點
void delDNode(int data)
{
int pre=head,ptr=head,i;
for(i=0;i<n;i++)
{
if(A[ptr][0]==data)
break;
pre = ptr;
ptr=A[ptr][1];
}
if(ptr==NULL_LINK) /* 沒有找到 */
printf("Node is not found!\n");
else{
if(ptr==head) /* 找到的節點��開頭 */
{
head=A[ptr][1];
A[ptr][0]=0;
A[ptr][1]=INVALID_LINK;
}else{ /* 找到的節點不��開頭 */
A[pre][1]=A[ptr][1];
A[ptr][0]=0;
A[ptr][1]=INVALID_LINK;
A[ptr][2]=INVALID_LINK;
}
}
}
// 尋找節點,往後尋找
int findDNode(int data)
{
int i,ptr=head; /* 從鏈結串列的頭開始看 */
for(i=0;i<n;i++)
{
if(A[ptr][0]==data) /* 搜尋成功 */
return ptr;
else if(A[ptr][1]==NULL_LINK) /* 沒有節點了 */
break;
ptr=A[ptr][1]; /* 指向後一個節點 */
}
return -1; /* 搜尋失敗 */
}