(1) L-next=NULL
創(chuàng)新互聯(lián)公司2013年開創(chuàng)至今,是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司,擁有項目做網(wǎng)站、成都網(wǎng)站建設(shè)網(wǎng)站策劃,項目實施與項目整合能力。我們以讓每一個夢想脫穎而出為使命,1280元白銀區(qū)做網(wǎng)站,已為上家服務(wù),為白銀區(qū)各地企業(yè)和個人服務(wù),聯(lián)系電話:028-86922220
(2) p (或p!=NULL)
(3) q (或q!=NULL)
(4) p-next=r-next
(5) r-next=p // (4) 和 (5)是將p結(jié)點插入到 r 結(jié)點和q 結(jié)點之間
//修改如下
#include stdio.h
#include stdlib.h
typedef struct node
{
int xh;
char sname[8];
int sx;
int yw;
int zf;
int mc;
struct node *next;
}linklist;
void main()
{
linklist *head;
linklist *s=NULL; //創(chuàng)建 鏈表時所用的指針。。
linklist *p=NULL;// 輸出 鏈表時所用的指針。。
linklist *q=NULL;
linklist *g=NULL;
char ch;
head = NULL;//開始時 鏈表的頭為空;
printf(" 輸入 y 進(jìn)入循環(huán)\n");
scanf("%c",ch);
while(ch =='y'||ch=='Y')
{
s=(linklist*)malloc(sizeof(linklist));//給鏈表建立個空間
printf("輸入學(xué)號");
scanf("%d",s-xh);
printf("輸入姓名");
scanf("%s",s-sname);
printf("輸入數(shù)學(xué)成績");
scanf("%d",s-sx);
printf("輸入語文成績");
scanf("%d",s-yw);
s-zf=s-sx+s-yw;
s-next = NULL;
if(head == NULL||head-zfs-zf)
{
s-next=head;
head=s;
}
else
{
p=head;
q=p-next;
while(q!=NULLs-zf = q-zf)
{
p=q;
q=q-next;
}
s-next=q;
p-next=s;
}
getchar();//修改
printf(" 繼續(xù)輸入按y\n");//修改
scanf("%c",ch);
}
//輸出鏈表
g=head;
while(g!=NULL)
{
printf("%4d",g-xh);
printf("%4s",g-sname);
printf("%4d",g-sx);
printf("%4d",g-yw);
printf("%4d",g-zf);
printf("\n ");
g=g-next;//修改
}
}
#include"stdafx.h"
#include<stdlib.h>
//創(chuàng)建一個節(jié)點,data為value,指向NULL
Node*Create(intvalue){
Node*head=(Node*)malloc(sizeof(Node));
head->data=value;
head->next=NULL;
returnhead;
}
//銷毀鏈表
boolDestroy_List(Node*head){
Node*temp;
while(head){
temp=head->next;
free(head);
head=temp;
}
head=NULL;
returntrue;
}
//表后添加一個節(jié)點,Create(value)
boolAppend(Node*head,intvalue){
Node*n=Create(value);
Node*temp=head;
while(temp->next){
temp=temp->next;
}
temp->next=n;
return0;
}
//打印鏈表
voidPrint_List(Node*head){
Node*temp=head->next;
while(temp){
printf("%d->",temp->data);
temp=temp->next;
}
printf("\n");
}
//在鏈表的第locate個節(jié)點后(頭節(jié)點為0)插入創(chuàng)建的節(jié)點Create(value)
boolInsert_List(Node*head,intlocate,intvalue){
Node*temp=head;
Node*p;
Node*n=Create(value);
if(locate<0)
returnfalse;
while(locate--){
if(temp->next==NULL){
temp->next=Create(value);
returntrue;
}
temp=temp->next;
}
p=temp->next;
temp->next=n;
n->next=p;
returntrue;
}
//刪除第locate個節(jié)點后(頭節(jié)點為0)的節(jié)點
boolDelete_List(Node*head,intlocate){
Node*temp=head;
Node*p;
if(locate<0)
returnfalse;
while(locate--){
if(temp==NULL){
returnfalse;
}
temp=temp->next;
}
p=temp->next->next;
free(temp->next);
temp->next=NULL;
temp->next=p;
returntrue;
}
//獲取鏈表長度(不包括頭節(jié)點)
intSize_List(Node*head){
Node*temp=head;
intsize=0;
while(temp->next){
temp=temp->next;
size++;
}
returnsize;
}
//鏈表的三種排序(選擇,插入,冒泡)
boolSort_List(Node*head){
intt=0;
intsize=Size_List(head);
//選擇排序
/*for(Node*temp=head->next;temp!=NULL;temp=temp->next){
for(Node*p=temp;p!=NULL;p=p->next){
if(temp->data>p->data){
printf("換%d和%d\n",temp->data,p->data);
t=temp->data;
temp->data=p->data;
p->data=t;
}
}
}*/
//插入排序
/*for(Node*temp=head->next->next;temp?。絅ULL;temp=temp->next){
for(Node*p=head;p->next?。絅ULL;p=p->next){
if(p->next->data>temp->data)
{
printf("換%d和%d\n",temp->data,p->next->data);
t=temp->data;
temp->data=p->next->data;
p->next->data=t;
}
}
}*/
//冒泡排序
for(Node*temp=head->next;temp->next!=NULL;temp=temp->next){
for(Node*p=head->next;p->next?。絅ULL;p=p->next){
if(p->data>p->next->data){
t=p->data;
p->data=p->next->data;
p->next->data=t;
}
}
}
return0;
}
擴(kuò)展資料:
return表示把程序流程從被調(diào)函數(shù)轉(zhuǎn)向主調(diào)函數(shù)并把表達(dá)式的值帶回主調(diào)函數(shù),實現(xiàn)函數(shù)值的返回,返回時可附帶一個返回值,由return后面的參數(shù)指定。
return通常是必要的,因為函數(shù)調(diào)用的時候計算結(jié)果通常是通過返回值帶出的。如果函數(shù)執(zhí)行不需要返回計算結(jié)果,也經(jīng)常需要返回一個狀態(tài)碼來表示函數(shù)執(zhí)行的順利與否(-1和0就是最常用的狀態(tài)碼),主調(diào)函數(shù)可以通過返回值判斷被調(diào)函數(shù)的執(zhí)行情況。
這個算法有兩個循環(huán),我們姑且稱其為外循環(huán)和內(nèi)循環(huán),誠如其他樓的一位網(wǎng)友所言,其內(nèi)循環(huán)在第一次判斷時進(jìn)不去是正常的,但后面會進(jìn)去。為什么呢?首先我們來理一下這個算法的大體思路:這是一個針對單鏈表的排序算法,就是說給定一個單鏈表,我們要把按照結(jié)點(這里不對頭結(jié)點進(jìn)行排序,即這里討論的結(jié)點不包括頭結(jié)點)的數(shù)據(jù)域中的data值的大小從小到大進(jìn)行排序,得到新的排序后的有序鏈表。我們先把鏈表的頭結(jié)點之后的部分鏈表拆下來,即p=L-next,L-next=NULL,這樣我們就拆分原來的鏈表變成了現(xiàn)在的兩個鏈表(我們稱只有一個頭結(jié)點的鏈表為L1,另一個全為數(shù)據(jù)項結(jié)點的鏈表為L2)。接下來我們一個一個從L2剝下單獨的結(jié)點,放到L1中,其中如果L1中已經(jīng)有數(shù)據(jù)項結(jié)點,則要先進(jìn)行data項比較再找到合適的地方插入。直到最后L2中的結(jié)點全部拆下來并裝到了L1上,于是排序完畢,此時的L1擁有與原來的單鏈表相同的頭結(jié)點,但是排列有序的數(shù)據(jù)項結(jié)點。
理完了整個算法的思路后再回去看代碼就很明顯,外循環(huán)判斷“p!=NULL”的意義在于判斷L2鏈表中是否還有沒有剝完的結(jié)點,而內(nèi)循環(huán)中要先判斷“q!=NULL”的第一層意義在于判斷L1鏈表是不是一個只有頭結(jié)點的空表(即無數(shù)據(jù)項結(jié)點),如果是,則直接插入,如果不是,則判斷目前L1頭結(jié)點的下一個結(jié)點q的data值是否小于等于剛從L2剝下來的結(jié)點p的data值,如果是,則說明這個p結(jié)點應(yīng)該安放的位置還在q結(jié)點之后,我們還要繼續(xù)往下找,直到找到q-data p-data的結(jié)點q或者已經(jīng)到了鏈表的末尾(這也是q!=NULL的第二層意義),則停止尋找,并將p結(jié)點就放在這個位置。
說了半天忘了回答樓主的疑問,為什么內(nèi)循環(huán)永遠(yuǎn)不會進(jìn)去嗎?不是,只是第一次不會進(jìn)去(當(dāng)然,如果原單鏈表本身就是一個只有頭結(jié)點的鏈表時那么后面也不會再進(jìn)去了,因為空表根本不需要排序),而后面就會進(jìn)去,具體原因見我上述分析即可知。
void link_order(STU *p_head)
{
STU *pb, *pf, temp;
pf = p_head;
if(p_head == NULL) {//鏈表為空
printf("needn't order.\n");
return ;
}
if(p_head-next == NULL) {//鏈表有1個節(jié)點
printf("only one print, needn't order.\n");
return ;
}
while(pf-next != NULL) {//以pf指向的節(jié)點為基準(zhǔn)節(jié)點
pb = pf-next;//pb從基準(zhǔn)點的下一個節(jié)點開始
while(pb != NULL) {
if(pf-num pb-num) {
temp = *pf;
*pf = *pb;
*pb = temp;
temp.next = pf-next;
pf-next = pb-next;
pb-next = temp.next;
}
pb = pb-next;
}
pf = pf-next;
}
return ;
}
擴(kuò)展資料:
鏈表的排序有三種情況:
1、鏈表為空時:不用排序;
2、鏈表中有一個節(jié)點:不用排序;
3、鏈表中兩個及其以上節(jié)點時:排序。
return 0代表程序正常退出。return是C++預(yù)定義的語句,它提供了終止函數(shù)執(zhí)行的一種方式。當(dāng)return語句提供了一個值時,這個值就成為函數(shù)的返回值。
return語句用來結(jié)束循環(huán),或返回一個函數(shù)的值。
1、return 0,說明程序正常退出,返回到主程序繼續(xù)往下執(zhí)行。
2、return 1,說明程序異常退出,返回主調(diào)函數(shù)來處理,繼續(xù)往下執(zhí)行。return 0或return 1對程序執(zhí)行的順序沒有影響,只是大家習(xí)慣于使用return(0)退出子程序而已。
==========================
功能:選擇排序(由小到大)
返回:指向鏈表表頭的指針
==========================
*/
/*
選擇排序的基本思想就是反復(fù)從還未排好序的那些節(jié)點中,
選出鍵值(就是用它排序的字段,我們?nèi)W(xué)號num為鍵值)最小的節(jié)點,
依次重新組合成一個鏈表。
我認(rèn)為寫鏈表這類程序,關(guān)鍵是理解:
head存儲的是第一個節(jié)點的地址,head-next存儲的是第二個節(jié)點的地址;
任意一個節(jié)點p的地址,只能通過它前一個節(jié)點的next來求得。
單向鏈表的選擇排序圖示:
----[1]----[3]----[2]...----[n]----[NULL](原鏈表)
head 1-next 3-next 2-next n-next
----[NULL](空鏈表)
first
tail
----[1]----[2]----[3]...----[n]----[NULL](排序后鏈表)
first 1-next 2-next 3-next tail-next
圖10:有N個節(jié)點的鏈表選擇排序
1、先在原鏈表中找最小的,找到一個后就把它放到另一個空的鏈表中;
2、空鏈表中安放第一個進(jìn)來的節(jié)點,產(chǎn)生一個有序鏈表,并且讓它在原鏈表中分離出來(此時要注意原鏈表中出來的是第一個節(jié)點還是中間其它節(jié)點);
3、繼續(xù)在原鏈表中找下一個最小的,找到后把它放入有序鏈表的尾指針的next,然后它變成其尾指針;
*/
struct student *SelectSort(struct student *head)
{
struct student *first; /*排列后有序鏈的表頭指針*/
struct student *tail; /*排列后有序鏈的表尾指針*/
struct student *p_min; /*保留鍵值更小的節(jié)點的前驅(qū)節(jié)點的指針*/
struct student *min; /*存儲最小節(jié)點*/
struct student *p; /*當(dāng)前比較的節(jié)點*/
first = NULL;
while (head != NULL) /*在鏈表中找鍵值最小的節(jié)點。*/
{
/*注意:這里for語句就是體現(xiàn)選擇排序思想的地方*/
for (p=head,min=head; p-next!=NULL; p=p-next) /*循環(huán)遍歷鏈表中的節(jié)點,找出此時最小的節(jié)點。*/
{
if (p-next-num min-num) /*找到一個比當(dāng)前min小的節(jié)點。*/
{
p_min = p; /*保存找到節(jié)點的前驅(qū)節(jié)點:顯然p-next的前驅(qū)節(jié)點是p。*/
min = p-next; /*保存鍵值更小的節(jié)點。*/
}
}
/*上面for語句結(jié)束后,就要做兩件事;一是把它放入有序鏈表中;二是根據(jù)相應(yīng)的條件判斷,安排它離開原來的鏈表。*/
/*第一件事*/
if (first == NULL) /*如果有序鏈表目前還是一個空鏈表*/
{
first = min; /*第一次找到鍵值最小的節(jié)點。*/
tail = min; /*注意:尾指針讓它指向最后的一個節(jié)點。*/
}
else /*有序鏈表中已經(jīng)有節(jié)點*/
{
tail-next = min; /*把剛找到的最小節(jié)點放到最后,即讓尾指針的next指向它。*/
tail = min; /*尾指針也要指向它。*/
}
/*第二件事*/
if (min == head) /*如果找到的最小節(jié)點就是第一個節(jié)點*/
{
head = head-next; /*顯然讓head指向原h(huán)ead-next,即第二個節(jié)點,就OK*/
}
else /*如果不是第一個節(jié)點*/
{
p_min-next = min-next; /*前次最小節(jié)點的next指向當(dāng)前min的next,這樣就讓min離開了原鏈表。*/
}
}
if (first != NULL) /*循環(huán)結(jié)束得到有序鏈表first*/
{
tail-next = NULL; /*單向鏈表的最后一個節(jié)點的next應(yīng)該指向NULL*/
}
head = first;
return head;
}
/*
==========================
功能:直接插入排序(由小到大)
返回:指向鏈表表頭的指針
==========================
*/
/*
直接插入排序的基本思想就是假設(shè)鏈表的前面n-1個節(jié)點是已經(jīng)按鍵值
(就是用它排序的字段,我們?nèi)W(xué)號num為鍵值)排好序的,對于節(jié)點n在
這個序列中找插入位置,使得n插入后新序列仍然有序。按照這種思想,依次
對鏈表從頭到尾執(zhí)行一遍,就可以使無序鏈表變?yōu)橛行蜴湵怼?/p>
單向鏈表的直接插入排序圖示:
----[1]----[3]----[2]...----[n]----[NULL](原鏈表)
head 1-next 3-next 2-next n-next
----[1]----[NULL](從原鏈表中取第1個節(jié)點作為只有一個節(jié)點的有序鏈表)
head
圖11
----[3]----[2]...----[n]----[NULL](原鏈表剩下用于直接插入排序的節(jié)點)
first 3-next 2-next n-next
圖12
----[1]----[2]----[3]...----[n]----[NULL](排序后鏈表)
head 1-next 2-next 3-next n-next
圖13:有N個節(jié)點的鏈表直接插入排序
1、先在原鏈表中以第一個節(jié)點為一個有序鏈表,其余節(jié)點為待定節(jié)點。
2、從圖12鏈表中取節(jié)點,到圖11鏈表中定位插入。
3、上面圖示雖說畫了兩條鏈表,其實只有一條鏈表。在排序中,實質(zhì)只增加了一個用于指向剩下需要排序節(jié)點的頭指針first罷了。
這一點請讀者務(wù)必搞清楚,要不然就可能認(rèn)為它和上面的選擇排序法一樣了。
*/
struct student *InsertSort(struct student *head)
{
struct student *first; /*為原鏈表剩下用于直接插入排序的節(jié)點頭指針*/
struct student *t; /*臨時指針變量:插入節(jié)點*/
struct student *p; /*臨時指針變量*/
struct student *q; /*臨時指針變量*/
first = head-next; /*原鏈表剩下用于直接插入排序的節(jié)點鏈表:可根據(jù)圖12來理解。*/
head-next = NULL; /*只含有一個節(jié)點的鏈表的有序鏈表:可根據(jù)圖11來理解。*/
while (first != NULL) /*遍歷剩下無序的鏈表*/
{
/*注意:這里for語句就是體現(xiàn)直接插入排序思想的地方*/
for (t=first, q=head; ((q!=NULL) (q-num t-num)); p=q, q=q-next); /*無序節(jié)點在有序鏈表中找插入的位置*/
/*退出for循環(huán),就是找到了插入的位置*/
/*注意:按道理來說,這句話可以放到下面注釋了的那個位置也應(yīng)該對的,但是就是不能。原因:你若理解了上面的第3條,就知道了。*/
first = first-next; /*無序鏈表中的節(jié)點離開,以便它插入到有序鏈表中。*/
if (q == head) /*插在第一個節(jié)點之前*/
{
head = t;
}
else /*p是q的前驅(qū)*/
{
p-next = t;
}
t-next = q; /*完成插入動作*/
/*first = first-next;*/
}
return head;
}
/*
==========================
功能:冒泡排序(由小到大)
返回:指向鏈表表頭的指針
==========================
*/
/*
冒泡排序的基本思想就是對當(dāng)前還未排好序的范圍內(nèi)的全部節(jié)點,
自上而下對相鄰的兩個節(jié)點依次進(jìn)行比較和調(diào)整,讓鍵值(就是用它排
序的字段,我們?nèi)W(xué)號num為鍵值)較大的節(jié)點往下沉,鍵值較小的往
上冒。即:每當(dāng)兩相鄰的節(jié)點比較后發(fā)現(xiàn)它們的排序與排序要求相反時,
就將它們互換。
單向鏈表的冒泡排序圖示:
----[1]----[3]----[2]...----[n]----[NULL](原鏈表)
head 1-next 3-next 2-next n-next
----[1]----[2]----[3]...----[n]----[NULL](排序后鏈表)
head 1-next 2-next 3-next n-next
圖14:有N個節(jié)點的鏈表冒泡排序
任意兩個相鄰節(jié)點p、q位置互換圖示:
假設(shè)p1-next指向p,那么顯然p1-next-next就指向q,
p1-next-next-next就指向q的后繼節(jié)點,我們用p2保存
p1-next-next指針。即:p2=p1-next-next,則有:
[ ]----[p]----------[q]----[ ](排序前)
p1-next p1-next-next p2-next
圖15
[ ]----[q]----------[p]----[ ](排序后)
圖16
1、排序后q節(jié)點指向p節(jié)點,在調(diào)整指向之前,我們要保存原p的指向節(jié)點地址,即:p2=p1-next-next;
2、順著這一步一步往下推,排序后圖16中p1-next-next要指的是p2-next,所以p1-next-next=p2-next;
3、在圖15中p2-next原是q發(fā)出來的指向,排序后圖16中q的指向要變?yōu)橹赶騪的,而原來p1-next是指向p的,所以p2-next=p1-next;
4、在圖15中p1-next原是指向p的,排序后圖16中p1-next要指向q,原來p1-next-next(即p2)是指向q的,所以p1-next=p2;
5、至此,我們完成了相鄰兩節(jié)點的順序交換。
6、下面的程序描述改進(jìn)了一點就是記錄了每次最后一次節(jié)點下沉的位置,這樣我們不必每次都從頭到尾的掃描,只需要掃描到記錄點為止。
因為后面的都已經(jīng)是排好序的了。
*/
struct student *BubbleSort(struct student *head)
{
struct student *endpt; /*控制循環(huán)比較*/
struct student *p; /*臨時指針變量*/
struct student *p1;
struct student *p2;
p1 = (struct student *)malloc(LEN);
p1-next = head; /*注意理解:我們增加一個節(jié)點,放在第一個節(jié)點的前面,主要是為了便于比較。因為第一個節(jié)點沒有前驅(qū),我們不能交換地址。*/
head = p1; /*讓head指向p1節(jié)點,排序完成后,我們再把p1節(jié)點釋放掉*/
for (endpt=NULL; endpt!=head; endpt=p) /*結(jié)合第6點理解*/
{
for (p=p1=head; p1-next-next!=endpt; p1=p1-next)
{
if (p1-next-num p1-next-next-num) /*如果前面的節(jié)點鍵值比后面節(jié)點的鍵值大,則交換*/
{
p2 = p1-next-next; /*結(jié)合第1點理解*/
p1-next-next = p2-next; /*結(jié)合第2點理解*/
p2-next = p1-next; /*結(jié)合第3點理解*/
p1-next = p2; /*結(jié)合第4點理解*/
p = p1-next-next; /*結(jié)合第6點理解*/
}
}
}
p1 = head; /*把p1的信息去掉*/
head = head-next; /*讓head指向排序后的第一個節(jié)點*/
free(p1); /*釋放p1*/
p1 = NULL; /*p1置為NULL,保證不產(chǎn)生“野指針”,即地址不確定的指針變量*/
return head;
}
/*
==========================
功能:插入有序鏈表的某個節(jié)點的后面(從小到大)
返回:指向鏈表表頭的指針
==========================
*/
/*
有序鏈表插入節(jié)點示意圖:
----[NULL](空有序鏈表)
head
圖18:空有序鏈表(空有序鏈表好解決,直接讓head指向它就是了。)
以下討論不為空的有序鏈表。
----[1]----[2]----[3]...----[n]----[NULL](有序鏈表)
head 1-next 2-next 3-next n-next
圖18:有N個節(jié)點的有序鏈表
插入node節(jié)點的位置有兩種情況:一是第一個節(jié)點前,二是其它節(jié)點前或后。
----[node]----[1]----[2]----[3]...----[n]----[NULL]
head node-next 1-next 2-next 3-next n-next
圖19:node節(jié)點插在第一個節(jié)點前
----[1]----[2]----[3]...----[node]...----[n]----[NULL]
head 1-next 2-next 3-next node-next n-next
圖20:node節(jié)點插在其它節(jié)點后
*/
struct student *SortInsert(struct student *head, struct student *node)
{
struct student *p; /*p保存當(dāng)前需要檢查的節(jié)點的地址*/
struct student *t; /*臨時指針變量*/
if (head == NULL) /*處理空的有序鏈表*/
{
head = node;
node-next = NULL;
n += 1; /*插入完畢,節(jié)點總數(shù)加1*/
return head;
}
p = head; /*有序鏈表不為空*/
while (p-num node-num p != NULL) /*p指向的節(jié)點的學(xué)號比插入節(jié)點的學(xué)號小,并且它不等于NULL*/
{
t = p; /*保存當(dāng)前節(jié)點的前驅(qū),以便后面判斷后處理*/
p = p-next; /*后移一個節(jié)點*/
}
if (p == head) /*剛好插入第一個節(jié)點之前*/
{
node-next = p;
head = node;
}
else /*插入其它節(jié)點之后*/
{
t-next = node; /*把node節(jié)點加進(jìn)去*/
node-next = p;
}
n += 1; /*插入完畢,節(jié)點總數(shù)加1*/
return head;
}
/*
測試代碼如下:
*/
/*測試SelectSort():請編譯時去掉注釋塊*/
/*
head = SelectSort(head);
Print(head);
*/
/*測試InsertSort():請編譯時去掉注釋塊*/
/*
head = InsertSort(head);
Print(head);
*/
/*測試BubbleSort():請編譯時去掉注釋塊*/
/*
head = BubbleSort(head);
Print(head);
*/
/*測試SortInsert():上面創(chuàng)建鏈表,輸入節(jié)點時請注意學(xué)號num從小到大的順序。請編譯時去掉注釋塊*/
/*
stu = (struct student *)malloc(LEN);
printf("\nPlease input insert node -- num,score: ");
scanf("%ld,%f",stu-num,stu-score);
head = SortInsert(head,stu);
free(stu);
stu = NULL;
Print(head);
*/
本文來自CSDN博客,轉(zhuǎn)載請標(biāo)明出處: