//Linklist.h
typedef struct Node{
int data; //數(shù)據(jù)域
struct Node * next; //指針域
}ListNode , * Linklist; //ListNode 結(jié)點(diǎn)類型,Linklist 指向結(jié)點(diǎn)的指針類型
/*Linklist h; 定義頭指針*/ /*ListNode *p; 定義指向某結(jié)點(diǎn)的指針,兩者類型相同*/
單鏈表
1.初始化空表纯丸，建立頭結(jié)點(diǎn)
Linklist initll(){
Linklist h;
h = (Linklist)malloc(sizeof(ListNode));
if(h!=NULL)
h->next = NULL;
else
printf("分配空間失斪蠖！\n");
return h;
}-
2.建立單鏈表
int Inpll(Linklist h,int n){ //形參：頭指針遵馆，結(jié)點(diǎn)個(gè)數(shù)ListNode *p,*tail; int i; tail = h; for(i=0;i<n;i++) { p=(ListNode * )malloc(sizeof(ListNode)); scanf("%d",&(p->data)); p->next = NULL; tail -> next = p; tail = p; //tail 永遠(yuǎn)抓住最后一個(gè)結(jié)點(diǎn) } return 1; } -
3.往非遞減有序的單鏈表中插入一個(gè)結(jié)點(diǎn)后，鏈表仍有序
void Insll(Linklist h,int x){
ListNode p,q,*temp;q =(Linklist)malloc(sizeof(ListNode)); q->data=x; if(h->next==NULL) //原鏈表為空 { h->next=q; q->next=NULL; return; } for(p=h->next,temp=h;p!=NULL;temp=p,p=p->next) { if(p->data>=x){ q->next = p; //q的指針域指向當(dāng)前結(jié)點(diǎn) temp->next = q; //前一個(gè)結(jié)點(diǎn)的指針域指向q break; } else if(p->next==NULL) //x比原鏈表中所有結(jié)點(diǎn)的值都大,需把q放在最后 { p->next=q; q->next=NULL; break; } } } -
4.遍歷單鏈表
int trall(Linklist h){
ListNode * p;if(h->next==NULL) //空表不遍歷 return 0; for(p=h->next;p!=NULL;p=p->next){ printf("%d\t",p->data); } printf("\n"); return 1; }
單循環(huán)鏈表
*** 特點(diǎn)：最后一個(gè)結(jié)點(diǎn)的指針域永遠(yuǎn)指向頭結(jié)點(diǎn) ***
-
1.建立帶頭結(jié)點(diǎn)的單循環(huán)鏈表
int ReInpll(Linklist h,int n){ ListNode *p,*tail; int i; /*h->next=NULL; //不帶頭結(jié)點(diǎn)創(chuàng)建單循環(huán)鏈表 scanf("%d",&(h->data));*/ tail = h; for(i=0;i<n;i++) { p=(ListNode * )malloc(sizeof(ListNode)); scanf("%d",&(p->data)); p->next = NULL; tail -> next = p; tail = p; //tail 永遠(yuǎn)抓住最后一個(gè)結(jié)點(diǎn) } p->next=h; //最后一個(gè)結(jié)點(diǎn)的指針域指向頭指針 return 1; } -
2.刪除單循環(huán)鏈表中所有值為x的元素
void DelX_LL( Linklist h, int x){
ListNode p,q;
q=h;for(p=q->next;p!=h;p=q->next){ if(p->data==x){ q->next=p->next; free(p); //回收被刪除的結(jié)點(diǎn) continue; //不再執(zhí)行下面的語(yǔ)句 } q=q->next; } } -
3.遍歷單循環(huán)鏈表
int traRell(Linklist h){ListNode * p; if(h->next == h) //空表不遍歷 return 0; for(p=h->next;p!=h;p=p->next){ printf("%d\t",p->data); } printf("\n"); return 1; }
單鏈表和單循環(huán)鏈表的區(qū)別
1.** 尾結(jié)點(diǎn)的指針域 **
單鏈表的尾結(jié)點(diǎn)的指針域指向NULL；
單循環(huán)鏈表的尾結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)古今。2.** 判斷鏈表為空的條件 **
判斷單鏈表（帶頭結(jié)點(diǎn)）是否為空,是判斷頭結(jié)點(diǎn)的指針域是否為空。
if(head->next==NULL)
判斷單循環(huán)鏈表（帶頭結(jié)點(diǎn)）是否為空,是判斷頭結(jié)點(diǎn)的指針域是否指向自身滔以。
if(h->next == head)
- 3.** 循環(huán)的條件 **
在算法中捉腥，
單鏈表的循環(huán)條件是：
p != NULL; //p結(jié)點(diǎn)不為空
或者
> p->next != NULL; //p結(jié)點(diǎn)的指針域不為空
單循環(huán)鏈表的循環(huán)條件是：
p != head; //p結(jié)點(diǎn)不等于頭指針
