1. 原表是空表,只需使head指向被插結(jié)點即可。
2. 被插結(jié)點值最小,應(yīng)插入第一結(jié)點之前。這種情況下使head指向被插結(jié)點,被插結(jié)點的指針域指向原來的第一結(jié)點則可。即:
pi->next=pb;
head=pi;
3. 在其它位置插入。這種情況下,使插入位置的前一結(jié)點的指針域指向被插結(jié)點,使被插結(jié)點的指針域指向插入位置的后一結(jié)點。即為:pi->next=pb;pf->next=pi;
4. 在表末插入。這種情況下使原表末結(jié)點指針域指向被插結(jié)點,被插結(jié)點指針域置為NULL。
即:
pb->next=pi;
pi->next=NULL; TYPE * insert(TYPE * head,TYPE *pi)
{
TYPE *pf,*pb;
pb=head;
if(head==NULL) /*空表插入*/
(head=pi;
pi->next=NULL;}
else
{
while((pi->num>pb->num)&&(pb->next!=NULL))
{
pf=pb;
pb=pb->next;
}/*找插入位置*/
if(pi->num<=pb->num)
{
if(head==pb)head=pi;/*在第一結(jié)點之前插入*/
else pf->next=pi;/*在其它位置插入*/
pi->next=pb; }
else
{
pb->next=pi;
pi->next=NULL;
} /*在表末插入*/
}
return head;
}
本函數(shù)有兩個形參均為指針變量,head指向鏈表,pi 指向被插結(jié)點。函數(shù)中首先判斷鏈表是否為空,為空則使head指向被插結(jié)點。表若不空,則用while語句循環(huán)查找插入位置。找到之后再判斷是否在第一結(jié)點之前插入,若是則使head 指向被插結(jié)點被插結(jié)點指針域指向原第一結(jié)點,否則在其它位置插入, 若插入的結(jié)點大于表中所有結(jié)點,則在表末插入。本函數(shù)返回一個指針,是鏈表的頭指針。當插入的位置在第一個結(jié)點之前時, 插入的新結(jié)點成為鏈表的第一個結(jié)點,因此head的值也有了改變, 故需要把這個指針返回主調(diào)函數(shù)。
[例7.14]將以上建立鏈表,刪除結(jié)點,插入結(jié)點的函數(shù)組織在一起,再建一個輸出全部結(jié)點的函數(shù),然后用main函數(shù)調(diào)用它們。
#define NULL 0
#define TYPE struct stu
#define LEN sizeof(struct stu)
struct stu
{
int num;
int age;
struct stu *next;
};
TYPE * creat(int n)
{
struct stu *head,*pf,*pb;
int i;
for(i=0;i { pb=(TYPE *)malloc(LEN); printf("input Number and Age\n"); scanf("%d%d",&pb->num,&pb->age); if(i==0) pf=head=pb; else pf->next=pb; pb->next=NULL; pf=pb; } return(head); } TYPE * delete(TYPE * head,int num) { TYPE *pf,*pb; if(head==NULL) { printf("\nempty list!\n"); goto end; } pb=head; while (pb->num!=num && pb->next!=NULL) { pf=pb;pb=pb->next; } if(pb->num==num) { if(pb==head) head=pb->next; else pf->next=pb->next; printf("The node is deleted\n"); } else free(pb); printf("The node not been found!\n"); end: return head; } TYPE * insert(TYPE * head,TYPE * pi) { TYPE *pb ,*pf; pb=head; if(head==NULL) { head=pi; pi->next=NULL; } else { while((pi->num>pb->num)&&(pb->next!=NULL)) { pf=pb; pb=pb->next; } if(pi->num<=pb->num) { if(head==pb) head=pi; else pf->next=pi; pi->next=pb; } else { pb->next=pi; pi->next=NULL; } } return head; } void print(TYPE * head) { printf("Number\t\tAge\n"); while(head!=NULL) { printf("%d\t\t%d\n",head->num,head->age); head=head->next; } } main() { TYPE * head,*pnum; int n,num; printf("input number of node: "); scanf("%d",&n); head=creat(n); print(head); printf("Input the deleted number: "); scanf("%d",&num); head=delete(head,num); print(head); printf("Input the inserted number and age: "); pnum=(TYPE *)malloc(LEN); scanf("%d%d",&pnum->num,&pnum->age); head=insert(head,pnum); print(head); } 相關(guān)推薦: 2012年軟考系統(tǒng)分析師考試60天完美復(fù)習(xí)計劃
北京 | 天津 | 上海 | 江蘇 | 山東 |
安徽 | 浙江 | 江西 | 福建 | 深圳 |
廣東 | 河北 | 湖南 | 廣西 | 河南 |
海南 | 湖北 | 四川 | 重慶 | 云南 |
貴州 | 西藏 | 新疆 | 陜西 | 山西 |
寧夏 | 甘肅 | 青海 | 遼寧 | 吉林 |
黑龍江 | 內(nèi)蒙古 |