題目:創建固定長度的單向鏈表
程序分析:鏈表是動態分配存儲空間的鏈式存儲結構,
其包括壹個“頭指針”變量,其中第0個結點稱為整個鏈表的頭結點,頭結點中存放壹個地址,該地址指向壹個元素,頭結點壹般不存放具體數據,只是存放第壹個結點的地址。
鏈表中每壹個元素稱為“結點”,每個結點都由兩部分組成:存放數據元素的數據域和存儲直接後繼存儲位置的指針域。指針域中存儲的即是鏈表的下壹個結點存儲位置,是壹個指針。多個結點鏈接成壹個鏈表。
最後壹個結點的指針域設置為空(NULL),作為鏈表的結束標誌,表示它沒有後繼結點。
使用結構體變量作為鏈表中的結點,因為結構體變量成員可以是數值類型,字符類型,數組類型,也可以是指針類型,這樣就可以使用指針類型成員來存放下壹個結點的地址,使其它類型成員存放數據信息。
在創建列表時要動態為鏈表分配空間,C語言的庫函數提供了幾種函數實現動態開辟存儲單元。
malloc()函數實現動態開辟存儲單元:
malloc函數原型為:void *malloc(unsigned int size);
?其作用是在內存的動態存儲區中分配壹個長度為size的連續空間,函數返回值是壹個指向分配域起始地址的指針(類型為void)。如果分配空間失敗(如,內存空間不足),則返回空間指針(NULL)
#include<stdio.h>#include<malloc.h>
struct?LNode
{
int?data;
struct?LNode?*next;
};
/*上面只是定義了壹個結構體類型,並未實際分配內存空間
只有定義了變量才分配內存空間*/
struct?LNode?*creat(int?n)
{
int?i;
struct?LNode?*head,*p1,*p2;
/*head用來標記鏈表,p1總是用來指向新分配的內存空間,
p2總是指向尾結點,並通過p2來鏈入新分配的結點*/
int?a;
head=NULL;
for(i=1;i<=n;i++)
{
p1=(struct?LNode?*)malloc(sizeof(struct?LNode));
/*動態分配內存空間,並數據轉換為(struct?LNode)類型*/
printf("請輸入鏈表中的第%d個數:",i);
scanf("%d",&a);
p1->data=a;
if(head==NULL)/*指定鏈表的頭指針*/
{
head=p1;
p2=p1;
}
else
{
p2->next=p1;
p2=p1;
}
p2->next=NULL;/*尾結點的後繼指針為NULL(空)*/
}
return?head;/*返回鏈表的頭指針*/
}
void?main()
{
int?n;
struct?LNode?*q;
printf("請輸入鏈表的長度:/n");
scanf("%d",&n);
q=creat(n);/*鏈表的頭指針(head)來標記整個鏈表*/
printf("/n鏈表中的數據:/n");
while(q)/*直到結點q為NULL結束循環*/
{
printf("%d?",q->data);/*輸出結點中的值*/
q=q->next;/*指向下壹個結點*/
}
}