給你一個(gè)鄰接表的完整程序：
我們提供的服務(wù)有：成都網(wǎng)站建設(shè)、網(wǎng)站設(shè)計(jì)、微信公眾號(hào)開發(fā)、網(wǎng)站優(yōu)化、網(wǎng)站認(rèn)證、禮縣ssl等。為成百上千企事業(yè)單位解決了網(wǎng)站和推廣的問題。提供周到的售前咨詢和貼心的售后服務(wù)，是有科學(xué)管理、有技術(shù)的禮縣網(wǎng)站制作公司
#include iostream.h
struct node
{
int data;
node *next;
};
class list
{
public:
list(){head=NULL;};
void MakeEmpty();
int Length();
void Insert(int x,int i);//將x插入到第i個(gè)結(jié)點(diǎn)（不含頭結(jié)點(diǎn)）的之后
void Insertlist(int a,int b);//將節(jié)點(diǎn)b插入a之前
int Delete(int x);
int Remove(int i);
int Find(int x);
void Display();
private:
node *head;
};
void list::Display()
{
node *current=head;
while (current!=NULL)
{
coutcurrent-data" ";
current=current-next;
}
coutendl;
}
void list::MakeEmpty()
{
head=NULL;
}
int list::Length()
{int n=1;
node *q=head;
if(q==NULL)
n=1;
else
while(q!=NULL)
{
n++;
q=q-next;
}
return n;
}
int list::Find(int x)//在鏈表中查找數(shù)值為x的結(jié)點(diǎn)，成功返回1，否則返回0
{
node *p=head;
while(p!=NULLp-data!=x)
p=p-next;
if(p-data==x)
return 1;
else
return 0;
}
void list::Insert (int x,int i)//將x插入到第i個(gè)結(jié)點(diǎn)（不含頭結(jié)點(diǎn)）的之后；
{
node *p;//p中放第i個(gè)結(jié)點(diǎn)
node *q;//q中放i后的結(jié)點(diǎn)
node *h;//h中存要插入的結(jié)點(diǎn)
h=new node;
h-data =x;
p=head;
if(p-next !=NULL) //鏈表不是只有一個(gè)結(jié)點(diǎn)或者空鏈表時(shí)候
{
int n=1;
while(p-next !=NULL)
{
n++;
p=p-next ;
}// 得到鏈表的結(jié)點(diǎn)的個(gè)數(shù)
p=head;//使p重新等于鏈?zhǔn)?/p>
if(i==n)//i=n時(shí)，直接加在最后面就行了
{
while(p-next !=NULL)
p=p-next;
p-next=h;
h-next =NULL;
}
else if(ini1)//先找到第i個(gè)結(jié)點(diǎn)，用p存第i個(gè)結(jié)點(diǎn)，用q存i后的結(jié)點(diǎn)，用h存要插入的結(jié)點(diǎn)
{
for(int j=1;ji;j++)
p=p-next;//找到第i個(gè)結(jié)點(diǎn)，用p存第i個(gè)結(jié)點(diǎn)
q=p-next;//q存i后的結(jié)點(diǎn)
p-next=h;
h-next=q;
}
else
cout"超出鏈表結(jié)點(diǎn)個(gè)數(shù)的范圍"endl;
}
else
cout"這個(gè)鏈表是空鏈表或者結(jié)點(diǎn)位置在首位"endl;
}
void list::Insertlist(int a,int b)//將b插入到結(jié)點(diǎn)為a之前
{
node *p,*q,*s;//p所指向的結(jié)點(diǎn)為a,s所指為要插入的數(shù)b,q所指向的是a前的結(jié)點(diǎn)
s=new node;
s-data=b;
p=head;
if(head==NULL)//空鏈表的時(shí)候
{
head=s;
s-next=NULL;
}
else
if(p-data==a)//a在鏈?zhǔn)讜r(shí)候
{
s-next=p;
head=s;
}
else
{
while(p-data!=ap-next!=NULL)//使p指向結(jié)點(diǎn)a,q指向a之前的結(jié)點(diǎn)
{
q=p;
p=p-next;
}
if(p-data==a)//若有結(jié)點(diǎn)a時(shí)候
{
q-next=s;
s-next=p;
}
else//沒有a的時(shí)候
{
p-next=s;
s-next=NULL;
}
}
}
int list::Delete(int x)//刪除鏈表中值為x的結(jié)點(diǎn)，成功返回1，否則返回0；
{
node *p,*q;
p=head;
if(p==NULL)
return 0;
if(p-data==x)
{
head=p-next;
delete p;
return 1;
}
else
{
while(p-data!=xp-next!=NULL)
{ q=p;
p=p-next;
}
if(p-data==x)
{
q-next =p-next;
delete p;
return 1;
}
else
return 0;
}
}
int list::Remove(int i)
{
node *p,*q;
p=head;
if(p!=NULL)
{ int n=1;
while(p-next !=NULL)
{
n++;
p=p-next ;
}//得到鏈表結(jié)點(diǎn)的個(gè)數(shù)
p=head;
if(i==n)//i結(jié)點(diǎn)在結(jié)尾的時(shí)候
{
while(p-next!=NULL)
{
q=p;
p=p-next;
}
q-next=NULL;
delete p;
return 1;
}
else if(ini1)//i結(jié)點(diǎn)在中間的時(shí)候
{
for(int j=1;ji;j++)
{
q=p;//q中放i前的結(jié)點(diǎn)
p=p-next ;//p中放第i個(gè)結(jié)點(diǎn)
}
q-next=p-next;
delete p;
return 1;
}
else if(i==1)//i結(jié)點(diǎn)在首位的時(shí)候
{
q=p-next;
head=q;
delete p;
return 1;
}
else
return 0;
}
else
return 0;
}
void main()
{
list A;
int data[10]={1,2,3,4,5,6,7,8,9,10};
A.Insertlist(0,data[0]);
for(int i=1;i10;i++)
A.Insertlist(0,data[i]);
A.Display();
menu:cout"1.遍歷鏈表"'\t'"2.查找鏈表"'\t'"3.插入鏈表"endl;
cout"4.刪除鏈表"'\t'"5.鏈表長度"'\t'"6.置空鏈表"endl;
int m;
do
{
cout"請(qǐng)輸入你想要進(jìn)行的操作（選擇對(duì)應(yīng)操作前面的序號(hào)）："endl;
cinm;
}while(m1||m6);//當(dāng)輸入的序號(hào)不在包括中，讓他重新輸入
switch(m)
{
case 1:
{
A.Display ();
goto menu;
};break;
case 2:
{
cout"請(qǐng)輸入你想要找到的結(jié)點(diǎn)："endl;
int c;
cinc;//輸入你想要找到的結(jié)點(diǎn)
if(A.Find (c)==1)
{
cout"可以找到"cendl;
A.Display ();//重新顯示出鏈表A
}
else
{
cout"鏈表中不存在"cendl;
A.Display ();//重新顯示出鏈表A
}
goto menu;
};break;
case 3:
{
cout"請(qǐng)選擇你要插入的方式(選擇前面的序號(hào)進(jìn)行選擇）"endl;
cout"1.將特定的結(jié)點(diǎn)加入到特定的結(jié)點(diǎn)前"'\t'"2.將特定的結(jié)點(diǎn)加到特定的位置后"endl;
int b1;
do
{
cout"請(qǐng)輸入你想要插入的方式（選擇前面的序號(hào)進(jìn)行選擇）："endl;
cinb1;
}while(b11||b12);//當(dāng)輸入的序號(hào)不在包括中，讓他重新輸入
if(b1==1)
{
cout"請(qǐng)輸入你想要插入的數(shù)和想要插入的結(jié)點(diǎn)（為此結(jié)點(diǎn)之前插入）："endl;
int a1,a2;
cina1a2;
A.Insertlist (a1,a2);//將a1插入到結(jié)點(diǎn)為a2結(jié)點(diǎn)之前
cout"此時(shí)鏈表為："endl;
A.Display ();//重新顯示出鏈表A
}
else
{
cout"請(qǐng)輸入你想要插入的數(shù)和想要插入的位置（為此結(jié)點(diǎn)之后插入）："endl;
int a1,a2;
cina1a2;
A.Insert (a1,a2);//將a1插入到結(jié)點(diǎn)位置為a2的結(jié)點(diǎn)之后
cout"此時(shí)鏈表為："endl;
A.Display ();//重新顯示出鏈表A
}
goto menu;
};break;
case 4:
{
cout"請(qǐng)選擇你要?jiǎng)h除的方式(選擇前面的序號(hào)進(jìn)行選擇）"endl;
cout"1.刪除特定的結(jié)點(diǎn)"'\t'"2.刪除特定位置的結(jié)點(diǎn)"endl;
int b1;
do
{
cout"請(qǐng)輸入你想要插入的方式（選擇前面的序號(hào)進(jìn)行選擇）："endl;
cinb1;
}while(b11||b12);//當(dāng)輸入的序號(hào)不在包括中，讓他重新輸入
if(b1==1)
{
cout"請(qǐng)輸入你想要?jiǎng)h除的結(jié)點(diǎn)："endl;
int a;
cina;//輸入你想要?jiǎng)h除的結(jié)點(diǎn)
if(A.Delete (a)==1)
{
cout"成功刪除"aendl;
cout"刪除后的鏈表為："endl;
A.Display ();
}
else
{
cout"此鏈表為："endl;
A.Display ();//重新顯示出鏈表A
cout"鏈表中不存在"aendl;
}
}
else
{
cout"請(qǐng)輸入你想要?jiǎng)h除的結(jié)點(diǎn)位置："endl;
int b;
cinb;//輸入你想要?jiǎng)h除的結(jié)點(diǎn)的位置
if(A.Remove(b)==1)
{
cout"成功刪除第"b"個(gè)結(jié)點(diǎn)"endl;
cout"刪除后的鏈表為："endl;
A.Display ();//重新顯示出鏈表A
}
else
{
cout"當(dāng)前鏈表的結(jié)點(diǎn)個(gè)數(shù)為："A.Length ()endl;
cout"您輸入的結(jié)點(diǎn)位置越界"endl;
}
}
goto menu;
};break;
case 5:
{
cout"這個(gè)鏈表的結(jié)點(diǎn)數(shù)為:"A.Length ()endl;
goto menu;
};break;
case 6:
{
A.MakeEmpty ();
cout"這個(gè)鏈表已經(jīng)被置空"endl;
goto menu;
};break;
}
}
評(píng)論(3)|1
sunnyfulin |六級(jí)采納率46%
擅長：C/C++JAVA相關(guān)Windows數(shù)據(jù)結(jié)構(gòu)及算法百度其它產(chǎn)品
按默認(rèn)排序|按時(shí)間排序
其他1條回答
2012-04-23 17:41121446881|六級(jí)
我寫了一個(gè)C語言的，只給你兩個(gè)結(jié)構(gòu)體和一個(gè)初始化函數(shù)：
#include "stdio.h"
#include "malloc.h"
struct adjacentnext//鄰接表項(xiàng)結(jié)構(gòu)體
{
int element;
int quanvalue;
struct adjacentnext *next;
};
struct adjacenthead//鄰接表頭結(jié)構(gòu)體
{
char flag;
int curvalue;
int element;
struct adjacenthead *previous;
struct adjacentnext *son;
};
//初始化圖，用鄰接表實(shí)現(xiàn)
struct adjacenthead *mapinitialnize(int mapsize)
{
struct adjacenthead *ahlists=NULL;
struct adjacentnext *newnode=NULL;
int i;
int x,y,z;
ahlists=malloc(sizeof(struct adjacenthead)*mapsize);
if(ahlists==NULL)
return NULL;
for(i=0;imapsize;i++)
{
ahlists[i].curvalue=0;
ahlists[i].flag=0;
ahlists[i].previous=NULL;
ahlists[i].son=NULL;
ahlists[i].element=i+1;
}
scanf("%d%d%d",x,y,z);//輸入源結(jié)點(diǎn)，目的結(jié)點(diǎn)，以及源結(jié)點(diǎn)到目的結(jié)點(diǎn)的路權(quán)值
while(x!=0y!=0)//x,y至少有一個(gè)零就結(jié)束
{
newnode=malloc(sizeof(struct adjacentnext));
newnode-element=y;
newnode-quanvalue=z;
newnode-next=ahlists[x-1].son;
ahlists[x-1].son=newnode;
scanf("%d%d%d",x,y,z);
}
return ahlists;//返回鄰接表頭
}
如果有對(duì)稱元素 aij 和 aji 分別是1和0,那么一定是有向圖(有一條有向邊連接兩點(diǎn)) 但如果所有的對(duì)應(yīng)元素都相同,就無法判斷是有向圖還是無向圖
package?test;
import?java.util.ArrayList;
import?java.util.List;
/**
*?java-用鄰接矩陣求圖的最短路徑、最長途徑。弗洛伊德算法
*/
public?class?FloydInGraph?{
private?static?int?INF=Integer.MAX_VALUE;
private?int[][]?dist;
private?int[][]?path;
private?ListInteger?result=new?ArrayListInteger();
public?FloydInGraph(int?size){
this.path=new?int[size][size];
this.dist=new?int[size][size];
}
public?void?findPath(int?i,int?j){
int?k=path[i][j];
if(k==-1)return;
findPath(i,k);
result.add(k);
findPath(k,j);
}
public??void?findCheapestPath(int?begin,int?end,int[][]?matrix){
floyd(matrix);
result.add(begin);
findPath(begin,end);
result.add(end);
}
public??void?floyd(int[][]?matrix){
int?size=matrix.length;
for(int?i=0;isize;i++){
for(int?j=0;jsize;j++){
path[i][j]=-1;
dist[i][j]=matrix[i][j];
}
}
for(int?k=0;ksize;k++){
for(int?i=0;isize;i++){
for(int?j=0;jsize;j++){
if(dist[i][k]!=INF
dist[k][j]!=INF
dist[i][k]+dist[k][j]dist[i][j]){//dist[i][k]+dist[k][j]dist[i][j]--longestPath
dist[i][j]=dist[i][k]+dist[k][j];
path[i][j]=k;
}
}
}
}
}
public?static?void?main(String[]?args)?{
FloydInGraph?graph=new?FloydInGraph(5);
int[][]?matrix={
{INF,30,INF,10,50},
{INF,INF,60,INF,INF},
{INF,INF,INF,INF,INF},
{INF,INF,INF,INF,30},
{50,INF,40,INF,INF},
};
int?begin=0;
int?end=4;
graph.findCheapestPath(begin,end,matrix);
ListInteger?list=graph.result;
System.out.println(begin+"?to?"+end+",the?cheapest?path?is:");
System.out.println(list.toString());
System.out.println(graph.dist[begin]);
}
}
1. 選擇一個(gè)算法（提供選擇見下），利用各種方法（圖形、動(dòng)畫等）演示算法的演示過程。
2. 可以進(jìn)行手動(dòng)演示，也可以自動(dòng)步進(jìn)式演示。
3. 允許用戶設(shè)置算法的各個(gè)輸入?yún)?shù)，以及自動(dòng)步進(jìn)式演示中的時(shí)間間隔。
4. 不同的算法輸入要求見下。
界面要求：
1. 盡量使用圖形界面實(shí)現(xiàn)，要符合日常軟件使用規(guī)范來設(shè)計(jì)菜單和界面。
2. 如果無法實(shí)現(xiàn)圖形界面，則在命令行方式下也需要提供菜單，方便用戶操作。
其他要求：
1. 標(biāo)識(shí)符命名遵循Windows命名規(guī)范。
2. 能夠注意各種異常處理，注重提高程序運(yùn)行效率。
提交內(nèi)容：
1. 全部源代碼。
2. 軟件設(shè)計(jì)和使用說明書（UML類圖；實(shí)現(xiàn)的功能、主要技術(shù)；使用幫助文檔）
參考算法：
1. 最小生成樹算法：Prim算法、Kruskal算法。允許以下方式輸入一個(gè)圖形：繪制圖形、輸入鄰接矩陣、輸入邊及其關(guān)聯(lián)的頂點(diǎn)。要求在圖形方式下進(jìn)行演示算法執(zhí)行步驟。
2. 單源最短路算法：Dijkstra算法。允許以下方式輸入一個(gè)圖形：繪制圖形、輸入鄰接矩陣、輸入邊及其關(guān)聯(lián)的頂點(diǎn)。要求在圖形方式下進(jìn)行演示算法執(zhí)行步驟。
3. 最優(yōu)編碼算法：Huffman編碼算法。允許用戶輸入一段英文文字，或者打開一個(gè)txt文檔（英文內(nèi)容），據(jù)此文檔內(nèi)容進(jìn)行編碼。要求動(dòng)態(tài)列出每個(gè)字符的出現(xiàn)概率統(tǒng)計(jì)結(jié)果以及對(duì)應(yīng)編碼。
4. 其他可供演示的具有一定難度的算法，如關(guān)鍵路徑問題、有向圖的極大連通分支等。
重慶分公司
重慶分公司
