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

 

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

code2html：http://tohtml.com/

 

/* =============== Program Description =============== */
/* 程式名稱 : 9_2.cpp 				       */
/* 程式目的 : 鏈結串列以陣列為表示的使用範例	       */
/* 輸    入 : 整數陣列資料			       */
/* 輸    出 : 反轉的整數陣列資料,搜尋鍵值的位置	       */
/* =================================================== */
#define n 10
#define INVALID_LINK -2 /* 無效的連結 */
#define NULL_LINK	 -1	/* 結尾的連結 */
// 宣告標頭檔
#include "stdio.h"
// 宣告全域變數
int A[n][2];
int head = -1;
// 宣告函式原型
// 利用傳值的方式把整數data傳進addNode函式中
void addNode(int data);
// 利用傳值的方式把整數data傳進delNode函式中
void delNode(int data);
// 從findNode函式中回傳一個整數
int findNode(int data);
// 無回傳值,無傳入值
void inverse(void);
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;
// 輸入的資料
printf(" Input Data : ");
for(i=0;i<n;i++)
{
printf("%d",D[i]);
addNode(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");
// 反轉鏈結序列中的資料
printf(" Inverse Data in LinkList : ");
inverse();
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 = findNode(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]);
delNode(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 = findNode(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 addNode(int data)
{
int i;
if(head==NULL_LINK)
{
head=0;
A[head][0]=data;
A[head][1]=NULL_LINK;
}else{
for(i=0;i<n;i++)
{
if(A[i][1]==INVALID_LINK) /* 空的節點 */
{
A[i][0]=data;
A[i][1]=head;
head=i;
return;
}
}
printf("LinkArray is Full!\n");
}
}
// 刪除節點
void delNode(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;
}
}
}
// 尋找節點
int findNode(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; /* 搜尋失敗 */
}
void inverse(void)
{
int ptr0,ptr1,ptr2;
if(head==NULL_LINK)
return;
else
{
ptr0=head;	/* 第0個節點的位置 */
if(A[ptr0][1]==NULL_LINK)
return;
ptr1=A[ptr0][1]; /* 第1個節點的位置 */
ptr2=A[ptr1][1]; /* 第2個節點的位置 */
A[ptr0][1]=NULL_LINK; /* 第0個節點的連結指向尾巴 */
do
{
A[ptr1][1]=ptr0;  /* 第1個節點的連結指向第0個節點 */
ptr0 = ptr1;
ptr1 = ptr2;
ptr2 = A[ptr1][1];
}while(ptr2!=NULL_LINK);
A[ptr1][1]=ptr0;
head=ptr1;
}
}