http://blog.csdn.net/qiao_yuzhou/article/details/6165965
2011
題目：創(chuàng)建固定長(zhǎng)度的單向鏈表
程序分析：鏈表是動(dòng)態(tài)分配存儲(chǔ)空間的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，
其包括一個(gè)“頭指針”變量，其中第0個(gè)結(jié)點(diǎn)稱為整個(gè)鏈表的頭結(jié)點(diǎn)，頭結(jié)點(diǎn)中存放一個(gè)地址，該地址指向一個(gè)元素，頭結(jié)點(diǎn)一般不存放具體數(shù)據(jù)，只是存放第一個(gè)結(jié)點(diǎn)的地址。
鏈表中每一個(gè)元素稱為“結(jié)點(diǎn)”，每個(gè)結(jié)點(diǎn)都由兩部分組成：存放數(shù)據(jù)元素的數(shù)據(jù)域和存儲(chǔ)直接后繼存儲(chǔ)位置的指針域。指針域中存儲(chǔ)的即是鏈表的下一個(gè)結(jié)點(diǎn)存儲(chǔ)位置，是一個(gè)指針。多個(gè)結(jié)點(diǎn)鏈接成一個(gè)鏈表。
最后一個(gè)結(jié)點(diǎn)的指針域設(shè)置為空(NULL)，作為鏈表的結(jié)束標(biāo)志，表示它沒有后繼結(jié)點(diǎn)。
使用結(jié)構(gòu)體變量作為鏈表中的結(jié)點(diǎn)，因?yàn)榻Y(jié)構(gòu)體變量成員可以是數(shù)值類型，字符類型，數(shù)組類型，也可以是指針類型，這樣就可以使用指針類型成員來存放下一個(gè)結(jié)點(diǎn)的地址，使其它類型成員存放數(shù)據(jù)信息。
在創(chuàng)建列表時(shí)要?jiǎng)討B(tài)為鏈表分配空間，C語言的庫(kù)函數(shù)提供了幾種函數(shù)實(shí)現(xiàn)動(dòng)態(tài)開辟存儲(chǔ)單元。
malloc()函數(shù)實(shí)現(xiàn)動(dòng)態(tài)開辟存儲(chǔ)單元：
malloc函數(shù)原型為：void *malloc(unsigned int size);
其作用是在內(nèi)存的動(dòng)態(tài)存儲(chǔ)區(qū)中分配一個(gè)長(zhǎng)度為size的連續(xù)空間，函數(shù)返回值是一個(gè)指向分配域起始地址的指針（類型為void）。如果分配空間失?。ㄈ?，內(nèi)存空間不足），則返回空間指針（NULL）
代碼如下：
#include<stdio.h>
#include<malloc.h>
struct LNode
{
int data;
struct LNode *next;
};
/*上面只是定義了一個(gè)結(jié)構(gòu)體類型，并未實(shí)際分配內(nèi)存空間
只有定義了變量才分配內(nèi)存空間*/
struct LNode *creat(int n)
{
int i;
struct LNode *head,*p1,*p2;
/*head用來標(biāo)記鏈表，p1總是用來指向新分配的內(nèi)存空間，
p2總是指向尾結(jié)點(diǎn)，并通過p2來鏈入新分配的結(jié)點(diǎn)*/
int a;
head=NULL;
for(i=1;i<=n;i++)
{
p1=(struct LNode *)malloc(sizeof(struct LNode));
/*動(dòng)態(tài)分配內(nèi)存空間，并數(shù)據(jù)轉(zhuǎn)換為(struct LNode)類型*/
printf("請(qǐng)輸入鏈表中的第%d個(gè)數(shù)：",i);
scanf("%d",&a);
p1->data=a;
if(head==NULL)/*指定鏈表的頭指針*/
{
head=p1;
p2=p1;
}
else
{
p2->next=p1;
p2=p1;
}
p2->next=NULL;/*尾結(jié)點(diǎn)的后繼指針為NULL(空)*/
}
return head;/*返回鏈表的頭指針*/
}
void main()
{
int n;
struct LNode *q;
printf("請(qǐng)輸入鏈表的長(zhǎng)度：/n");
scanf("%d",&n);
q=creat(n);/*鏈表的頭指針(head)來標(biāo)記整個(gè)鏈表*/
printf("/n鏈表中的數(shù)據(jù)：/n");
while(q)/*直到結(jié)點(diǎn)q為NULL結(jié)束循環(huán)*/
{
printf("%d ",q->data);/*輸出結(jié)點(diǎn)中的值*/
q=q->next;/*指向下一個(gè)結(jié)點(diǎn)*/
}
}
題目：創(chuàng)建雙向鏈表
程序分析：雙向鏈表的結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向其直接后繼，另一個(gè)指向其直接前驅(qū)。其中第一個(gè)結(jié)點(diǎn)的前驅(qū)為NULL（頭結(jié)點(diǎn)為第0個(gè)結(jié)點(diǎn)），最后一個(gè)結(jié)點(diǎn)的后繼為NULL。
代碼如下：
#include<stdio.h>
#include<string.h>
#include<malloc.h>
typedef struct node
{
char name[20];
struct node *prior,*next;
}stud;
/*雙鏈表的結(jié)構(gòu)定義*/
stud *creat(int n)/*創(chuàng)建雙鏈表函數(shù)*/
{
stud *p,*h,*s;
int i;
h=(stud *)malloc(sizeof(stud));/*動(dòng)態(tài)分配內(nèi)存賦予頭結(jié)點(diǎn)*/
h->name[0]='/0';/*為頭結(jié)點(diǎn)的內(nèi)容置空*/
h->prior=NULL;/*頭結(jié)點(diǎn)的前驅(qū)和后繼置為NULL*/
h->next=NULL;
p=h;/*將頭結(jié)點(diǎn)賦值于p，p總是指向鏈表的最后一個(gè)結(jié)點(diǎn)*/
for(i=0;i<n;i++)
{
s=(stud *)malloc(sizeof(stud));/*動(dòng)態(tài)分配內(nèi)存*/
p->next=s;/*讓p結(jié)點(diǎn)的后繼指向s*/
printf("請(qǐng)輸入第%d個(gè)同學(xué)的名字：",i+1);
scanf("%s",s->name);
s->prior=p;/*讓s結(jié)點(diǎn)的前驅(qū)指向p結(jié)點(diǎn)*/
s->next=NULL;/*讓s結(jié)點(diǎn)的后繼指向NULL，s總是指向新分配的結(jié)點(diǎn)*/
p=s;/*p總是指向鏈表的最后一個(gè)結(jié)點(diǎn)*/
}
p->next=NULL;/*雙鏈表的最后一個(gè)結(jié)點(diǎn)的后繼指向NULL*/
return(h);
}
stud *search(stud *h,char *x)/*查找*/
{
stud *p;/*用于定位雙鏈表中的結(jié)點(diǎn)*/
char *y;
p=h->next;
while(p)
{
y=p->name;
if(strcmp(y,x)==0)/*strcmp函數(shù)比較兩個(gè)字符串的內(nèi)容是否相等*/
return (p);/*若找到，返回當(dāng)前結(jié)點(diǎn)*/
else
p=p->next;/*不相等就繼續(xù)向下查找*/
}
printf("信息未找到/n");
}
void del(stud *p)/*刪除*/
{
if(p->next!=NULL)/*確定要?jiǎng)h除的結(jié)點(diǎn)是否為最后一個(gè)結(jié)點(diǎn)，最后一個(gè)結(jié)點(diǎn)后繼為NULL*/
p->next->prior=p->prior;/*p結(jié)點(diǎn)后繼的前驅(qū)賦予p結(jié)點(diǎn)的前驅(qū)*/
p->prior->next=p->next;/*p結(jié)點(diǎn)前驅(qū)的后繼賦予p結(jié)點(diǎn)的后繼*/
free(p); /*釋放p結(jié)點(diǎn)的內(nèi)存空間*/
}
void dip(stud *p) /*輸出雙鏈表*/
{
while(p)
{
printf("%s ",&*(p->name));
/*%s格式符要用字符數(shù)組的起始地址即第一個(gè)字符的地址，也可用(p->name)*/
p=p->next;
}
}
void main()
{
int number;
char sname[20];
stud *head,*sp; /*head用來標(biāo)記雙鏈表，sp用來定位結(jié)點(diǎn)*/
puts("請(qǐng)輸入鏈表的長(zhǎng)度：");
scanf("%d",&number);
head=creat(number);
sp=head->next; /*sp指向雙鏈表的第一個(gè)結(jié)點(diǎn)(頭結(jié)點(diǎn)為第0個(gè)結(jié)點(diǎn))*/
printf("/n雙鏈表內(nèi)的數(shù)據(jù)為：/n");
dip(sp); /*輸出鏈表*/
printf("/n請(qǐng)輸入要查找的學(xué)生姓名：/n");
scanf("%s",sname);
sp=search(head,sname); /*查找鏈表中的結(jié)點(diǎn)*/
printf("/n你想要找的名子是：%s/n",&*(sp->name));
del(sp); /*刪除sp結(jié)點(diǎn)*/
sp=head->next;
printf("/n現(xiàn)在的雙鏈表是：/n");
dip(sp); /*輸出鏈表*/
printf("/n");
}
題目：創(chuàng)建循環(huán)鏈表
程序分析：循環(huán)鏈表與普通鏈表的操作基本一致，
只是鏈表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，是鏈表形成一個(gè)環(huán)，
從表中的任一結(jié)點(diǎn)出發(fā)均可找到表中的其它結(jié)點(diǎn)
在算法中循環(huán)遍歷鏈表是判斷條件不再是p->next是否為空，
而是是否等于鏈表的頭指針。
代碼如下：
#include<stdio.h>
#include<malloc.h>
typedef struct student
{
int num;
struct student *next;
}LNode,*LinkList;
/*定義鏈表的結(jié)構(gòu)體類型*/
LinkList creat(void)
{
LinkList head;
LNode *p1,*p2;
/*p1用來指向新分配的結(jié)點(diǎn)，
p2始終指向鏈表的最后一個(gè)結(jié)點(diǎn)，
同時(shí)用p2->next=p1來鏈入新結(jié)點(diǎn)*/
char a;
head=NULL;/*新創(chuàng)建的鏈表的頭指針為NULL(空)*/
a=getchar();
while(a!='/n')
{
p1=(LNode *)malloc(sizeof(LNode));/*動(dòng)態(tài)分配內(nèi)存空間*/
p1->num=a;/*為結(jié)點(diǎn)的數(shù)據(jù)域賦值*/
if(head==NULL)/*指定鏈表的頭指針*/
head=p1;
else
p2->next=p1;/*將新結(jié)點(diǎn)p1鏈入鏈表*/
p2=p1;/*p2指向剛鏈入的新結(jié)點(diǎn)，即讓p2始終指向鏈表的最后一個(gè)結(jié)點(diǎn)*/
a=getchar();
}
p2->next=head;/*鏈表的最后一個(gè)結(jié)點(diǎn)的后繼指向頭結(jié)點(diǎn)*/
return head;
}
void main()
{
LinkList L1,head;
printf("/n請(qǐng)輸入循環(huán)鏈表內(nèi)容：/n");
L1=creat();/*創(chuàng)建鏈表*/
head=L1;
printf("/n循環(huán)鏈接表：/n");
printf("%c",L1->num);
L1=L1->next;
while(L1!=head)
{
/*判斷條件為循環(huán)到頭結(jié)點(diǎn)結(jié)束*/
printf("%c",L1->num);
L1=L1->next;
}
printf("/n/n");
}
聯(lián)系客服
