課程首頁在：http://blog.csdn.net/sxhelijian/article/details/11890759
本文是為大一剛學習程序設計語言的同學體驗動態鏈表設計的一組練習。動態鏈表用途廣泛，必須重視，在學習數據結構及算法之前能有所體驗，意義重大。
不要被貌似復雜的指針操作迷惑，這正是專業學生應該具備的思維基本功。涉及到鏈接如何建立的操作，在紙上畫一畫，想一想，道理就通了。
作為需要用腦作的實踐，由畫一畫的形象思維，會形成頭腦中不用畫也很清楚的邏輯思維，這正是能力提高的一個必經的過程。
做不出來，就多看幾遍。做出來了，其間的不順一掃而光，其樂無窮。
下面是正題：
下面是一個建立動態鏈表的程序。閱讀程序，在草稿紙上畫出鏈表建立的過程，借此學會如何建立鏈表。然後改造程序，完成項目6的要求
#include
using namespace std;
struct Node
{
int data; //結點的數據
struct Node *next; //指向下一結點
};
Node *head=NULL; //將鏈表頭定義為全局變量，以便於後面操作
void make_list(); //建立鏈表
void out_list(); //輸出鏈表
int main( )
{
make_list();
out_list();
return 0;
}
void make_list()
{
int n;
Node *p;
cout<<"輸入若干正數（以0或一個負數結束）建立鏈表："
cin>>n;
while(n>0) //輸入若干正數建立鏈表，輸入非正數時，建立過程結束
{
p=new Node; //新建結點
p->data=n;
p->next=head; //新建的結點指向原先的鏈表頭
head=p; //鏈表頭賦值為新建的節點，這樣，新結點總是鏈表頭
cin>>n; //輸入下一個數，准備建立下一個結點
}
return;
}
void out_list()
{
Node *p=head;
cout<<"鏈表中的數據為："<data<<" ";
p=p->next;
}
cout<
IDCjrL2owaK1xMG0se3OqqO6PC9wPjxwPqGhoaGhoaGhoaE8aW1nIHNyYz0="http://www.2cto.com/uploadfile/Collfiles/20140309/20140309090952382.jpg" alt="\" />----參考解答----<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD48cD48L3A+PHByZSBjbGFzcz0="brush:java;">#include
#include
using namespace std;
struct Node
{
int data;
struct Node *next;
};
Node *head=NULL;
void make_list2(); //新結點始終在鏈表尾部
void out_list();
int main( )
{
freopen("input.txt","r",stdin);
make_list2();
out_list();
return 0;
}
void make_list2()
{
int n;
Node *p,*q; //p用於指向新建立的結點, q指向鏈表尾部
cout<<"輸入若干正數（以0或一個負數結束）建立鏈表："<>n;
while(n>0)
{
p=new Node;
p->data=n;
p->next=NULL;
if(head==NULL)
head=p;
else
q->next=p;
q=p;
cin>>n;
}
return;
}
//輸出所有的節點
void out_list()
{
Node *p=head;
cout<<"鏈表中的數據為："<data<<" ";
p=p->next;
}
cout<
（2）編寫函數void search(int x)，輸出鏈表中是否有值為x的結點。----參考解答----
#include
#include
using namespace std;
struct Node
{
int data;
struct Node *next;
};
Node *head=NULL;
void make_list2(); //新結點始終在鏈表尾部
void out_list();
void search(int x); //查找是否有值為x的結點
int main( )
{
int x;
freopen("input.txt","r",stdin);//調試中用重定向方便
make_list2();
out_list();
cin>>x; //測試中輸入一個鏈表中有的數字
search(x);
cin>>x; //測試中輸入一個鏈表中沒有的數字
search(x);
return 0;
}
void make_list2()
{
int n;
Node *p,*q; //p用於指向新建立的結點, q指向鏈表尾部
cout<<"輸入若干正數（以0或一個負數結束）建立鏈表："<>n;
while(n>0)
{
p=new Node;
p->data=n;
p->next=NULL;
if(head==NULL)
head=p;
else
q->next=p;
q=p;
cin>>n;
}
return;
}
//輸出所有的節點
void out_list()
{
Node *p=head;
cout<<"鏈表中的數據為："<data<<" ";
p=p->next;
}
cout<data!=x)
{
p=p->next;
}
if(p!=NULL) //退出上一層循環一定是因為p->data==x
cout<<"在鏈表中有值為"<
（3）編寫函數delete_first_node()，刪除鏈表中的第一個結點。----參考解答----
#include
#include
using namespace std;
struct Node
{
int data;
struct Node *next;
};
Node *head=NULL;
void make_list2(); //新結點始終在鏈表尾部
void out_list();
void delete_first_node(); //刪除第一個結點
int main( )
{
freopen("input.txt","r",stdin);//調試中用重定向方便
make_list2();
out_list();
delete_first_node();
out_list();
return 0;
}
void make_list2()
{
int n;
Node *p,*q; //p用於指向新建立的結點, q指向鏈表尾部
cout<<"輸入若干正數（以0或一個負數結束）建立鏈表："<>n;
while(n>0)
{
p=new Node;
p->data=n;
p->next=NULL;
if(head==NULL)
head=p;
else
q->next=p;
q=p;
cin>>n;
}
return;
}
//輸出所有的節點
void out_list()
{
Node *p=head;
cout<<"鏈表中的數據為："<data<<" ";
p=p->next;
}
cout<next;
delete p;
cout<<"刪除了首結點."<
（4）編寫函數delete_node(int x)，刪除結點值為x的結點。----參考解答----
#include
#include
using namespace std;
struct Node
{
int data;
struct Node *next;
};
Node *head=NULL;
void make_list2(); //新結點始終在鏈表尾部
void out_list();
void delete_node(int x); //刪除第一個結點
int main( )
{
freopen("input.txt","r",stdin);//調試中用重定向方便
make_list2();
out_list();
delete_node(3);
out_list();
return 0;
}
void make_list2()
{
int n;
Node *p,*q; //p用於指向新建立的結點, q指向鏈表尾部
cout<<"輸入若干正數（以0或一個負數結束）建立鏈表："<>n;
while(n>0)
{
p=new Node;
p->data=n;
p->next=NULL;
if(head==NULL)
head=p;
else
q->next=p;
q=p;
cin>>n;
}
return;
}
//輸出所有的節點
void out_list()
{
Node *p=head;
cout<<"鏈表中的數據為："<data<<" ";
p=p->next;
}
cout<data==x)
{
p=head;
head=head->next;
delete p;
}
if(head!=NULL)
{
p=head;
q=p->next;
while(q!=NULL)
{
if(q->data==x)//q就是該刪除的結點
{
p->next=q->next;
delete q;
}
else //q不該刪除，繼續考察下一個
{
p=q;
}
q=p->next; //總是p的下一個結點
}
}
}
return;
}
為充分測試，該程序運行了5次，所用的測試輸入數據分別為：
5 2 9 9 7 11 3 0
3 5 2 9 9 7 11 0
3 5 2 9 3 9 7 11 0
3 5 2 9 4 9 7 11 0
3 3 3 3 3 3 3 0
（5）編寫make_list3()函數建立有序鏈表，使建立鏈表時，結點中的數據呈現升序。若輸入為3 5 2 9 4 7 0，建立的鏈表為：
----參考解答----
#include
#include
using namespace std;
struct Node
{
int data;
struct Node *next;
};
Node *head=NULL;
void make_list3(); //建立有序鏈表，各結點由小到大
void out_list();
int main( )
{
freopen("input.txt","r",stdin);//調試中用重定向方便
make_list3();
out_list();
return 0;
}
void make_list3()
{
int n;
Node *t,*p,*q; //p用於指向新建立的結點, q指向鏈表尾部
cout<<"輸入若干正數（以0或一個負數結束）建立鏈表："<>n;
while(n>0)
{
t=new Node;
t->data=n;
t->next=NULL;
if(head==NULL) //是空鏈表，p作為第一個結點即可
head=t;
else //插入p結點後，各結點應該保持有序
{
if(n<=head->data) //新加入的結點應該為首結點
{
t->next=head;
head=t;
}
//應該找到合適的位置後，將結點插入
//此時，鏈表中至少已經有一個結點，且插入結點不是首結點
else
{
p=head;
q=p->next; //p與q相鄰，p更靠近q，插入位置將在p和q之間
while(q!=NULL&&n>q->data) //鏈表沒有完且p結點比n小，一直往後找
{
p=q;
q=p->next;
}
if(q==NULL) //q為null，作為最後一個結點直接插入到p後即可
{
p->next = t;
}
else //t插入到p和q之間
{
t->next=q;
p->next=t;
}
}
}
cin>>n;
}
return;
}
//輸出所有的節點
void out_list()
{
Node *p=head;
cout<<"鏈表中的數據為："<data<<" ";
p=p->next;
}
cout<
（6）編寫函數void insert(int x)，將值為x的結點插入到由make_list3建立起來的有序鏈表中。----參考解答1----
#include
#include
using namespace std;
struct Node
{
int data;
struct Node *next;
};
Node *head=NULL;
void make_list3(); //建立有序鏈表，各結點由小到大
void out_list();
void insert(int x); //將值為x的結點插入到有序鏈表中，使仍有序
int main( )
{
freopen("input.txt","r",stdin);//調試中用重定向方便
make_list3();
out_list();
insert(15);
out_list();
return 0;
}
void make_list3()
{
int n;
Node *t,*p,*q; //p用於指向新建立的結點, q指向鏈表尾部
cout<<"輸入若干正數（以0或一個負數結束）建立鏈表："<>n;
while(n>0)
{
t=new Node;
t->data=n;
t->next=NULL;
if(head==NULL) //是空鏈表，p作為第一個結點即可
head=t;
else //插入p結點後，各結點應該保持有序
{
if(n<=head->data) //新加入的結點應該為首結點
{
t->next=head;
head=t;
}
//應該找到合適的位置後，將結點插入
//此時，鏈表中至少已經有一個結點，且插入結點不是首結點
else
{
p=head;
q=p->next; //p與q相鄰，p更靠近q，插入位置將在p和q之間
while(q!=NULL&&n>q->data) //鏈表沒有完且p結點比n小，一直往後找
{
p=q;
q=p->next;
}
if(q==NULL) //q為null，作為最後一個結點直接插入到p後即可
{
p->next = t;
}
else //t插入到p和q之間
{
t->next=q;
p->next=t;
}
}
}
cin>>n;
}
return;
}
void insert(int x) //將值為x的結點插入到有序鏈表中，使仍有序
{
Node *t,*p,*q; //p用於指向新建立的結點, q指向鏈表尾部
t=new Node;
t->data=x;
t->next=NULL;
if(head==NULL) //是空鏈表，p作為第一個結點即可
head=t;
else //插入p結點後，各結點應該保持有序
{
if(x<=head->data) //新加入的結點應該為首結點
{
t->next=head;
head=t;
}
//應該找到合適的位置後，將結點插入
//此時，鏈表中至少已經有一個結點，且插入結點不是首結點
else
{
p=head;
q=p->next; //p與q相鄰，p更靠近q，插入位置將在p和q之間
while(q!=NULL&&x>q->data) //鏈表沒有完且p結點比n小，一直往後找
{
p=q;
q=p->next;
}
if(q==NULL) //q為null，作為最後一個結點直接插入到p後即可
{
p->next = t;
}
else //t插入到p和q之間
{
t->next=q;
p->next=t;
}
}
}
return;
}
//輸出所有的節點
void out_list()
{
Node *p=head;
cout<<"鏈表中的數據為："<data<<" ";
p=p->next;
}
cout<
----參考解答2---- 實際上，從程序整體上看，makelist3()可以直接調用insert(int x)實現，這樣寫出的程序合乎工程上的原則。這啟示我們，用函數組織程序結構，應該成為一種意識。
#include
#include
using namespace std;
struct Node
{
int data;
struct Node *next;
};
Node *head=NULL;
void make_list3(); //建立有序鏈表，各結點由小到大
void out_list();
void insert(int x); //將值為x的結點插入到有序鏈表中，使仍有序
int main( )
{
freopen("input.txt","r",stdin);//調試中用重定向方便
make_list3();
out_list();
insert(15);
out_list();
return 0;
}
void make_list3()
{
int n;
cout<<"輸入若干正數（以0或一個負數結束）建立鏈表："<>n;
while(n>0)
{
insert(n);//調用insert，makelist簡單得不得了
cin>>n;
}
return;
}
void insert(int x) //將值為x的結點插入到有序鏈表中，使仍有序
{
Node *t,*p,*q; //p用於指向新建立的結點, q指向鏈表尾部
t=new Node;
t->data=x;
t->next=NULL;
if(head==NULL) //是空鏈表，p作為第一個結點即可
head=t;
else //插入p結點後，各結點應該保持有序
{
if(x<=head->data) //新加入的結點應該為首結點
{
t->next=head;
head=t;
}
//應該找到合適的位置後，將結點插入
//此時，鏈表中至少已經有一個結點，且插入結點不是首結點
else
{
p=head;
q=p->next; //p與q相鄰，p更靠近q，插入位置將在p和q之間
while(q!=NULL&&x>q->data) //鏈表沒有完且p結點比n小，一直往後找
{
p=q;
q=p->next;
}
if(q==NULL) //q為null，作為最後一個結點直接插入到p後即可
{
p->next = t;
}
else //t插入到p和q之間
{
t->next=q;
p->next=t;
}
}
}
return;
}
//輸出所有的節點
void out_list()
{
Node *p=head;
cout<<"鏈表中的數據為："<data<<" ";
p=p->next;
}
cout<
==================== 迂者 賀利堅 CSDN博客專欄=================
|== IT學子成長指導專欄 專欄文章分類目錄（不定期更新） ==|
|== C++ 課堂在線專欄 賀利堅課程教學鏈接（分課程年級） ==|
======== 為IT菜鳥起飛鋪跑道，和學生一起享受快樂和激情的大學 =======
