線性表的鏈式存儲結構
線性表的鏈式存儲結構的特點是用一組任意存儲單元存儲線性表的數(shù)據(jù)元素。既然是任意存儲的，那么每個數(shù)據(jù)元素不僅要存儲自身的數(shù)據(jù)元素信息也要存儲它后繼元素的存儲地址。
- 數(shù)據(jù)域 存儲數(shù)據(jù)元素信息的域
- 指針域 存儲直接后繼位置的域
數(shù)據(jù)域和指針域一起組成數(shù)據(jù)元素ai的存儲映像，稱為結點(Node)
單鏈表即鏈表中的每個結點中只包含一個指針域
單鏈表
鏈表中第一個結點的存儲位置叫做頭指針憔儿，最后一個結點指針為空(NULL或^)
完整的單鏈表
單鏈表的第一個結點前附設一個結點，稱為頭結點
帶有頭結點的單鏈表
頭指針與頭結點的異同
頭指針 指鏈表指向第一個結點的指針放可，若鏈表有頭結點則是指向頭結點的指針谒臼。頭指針具有標識作用朝刊，無論鏈表是否為空，頭指針均不為空蜈缤，頭指針是鏈表的必要元素拾氓。
頭結點為了操作的統(tǒng)一和方便而設立的，放在第一元素的結點之前底哥，其數(shù)據(jù)域一般無意義(也可存放鏈表的長度)咙鞍。這樣對在第一元素結點前插入結點和刪除第一結點其操作與其他結點操作統(tǒng)一。頭結點不一定是鏈表必須要素
- 線性表的單鏈表存儲結構定義
typedef struct fact
{
ElemType data; //存放數(shù)據(jù)元素的數(shù)據(jù)域
struct fact *next; //存放后繼結點地址的指針域
}Node;
Node *LinkList //定義LinkList
頭插法建立鏈式線性表
-
定義一個空結點*head = NULL
準備條件 -
每次連接新的數(shù)據(jù)元素時都要動態(tài)分配一個node大小的內存空間趾徽，并把這塊空間的首地址傳給一個node指針型的變量s续滋，*s的數(shù)據(jù)域是5。
生成一個結點s -
若head為空時把s結點變?yōu)閔ead結點附较。
head = p -
若head不為空時吃粒，使head結點改成s的后繼結點，代表每次新的元素到來時都是從頭部插入的拒课。
s->next = head -
每次元素插入結束時把s結點變?yōu)閔ead結點徐勃，就是說每次都是從頭部插入的。
head = p
int main()
{
node *head=NULL,*p;
int num;
printf("Enter some integers: ");
scanf("%d",&num);
while(num!=0){
p=(node *)calloc(1,sizeof(node));
p->data=num;
if(head==NULL)
head=p;
else
p->next=head;
head=p;
scanf("%d",&num);
}
for(p=head;p;p=p->next)
printf("%-5d",p->data);
printf("\n");
return 0;
}
尾插法建立鏈式線性表(無首元)
- 首先創(chuàng)建兩個空結點head和tail
- 創(chuàng)建一個p結點(開辟一個node大小的內存空間早像，空間首地址指向p,p結點的數(shù)據(jù)為num)僻肖。
- 若head為空，則把p結點變?yōu)閔ead結點卢鹦，第一次p結點為head結點并且也是tail結點臀脏。
- 若head結點不為空，則把tail的下一個結點指向p結點冀自，即第二次是head結點指向p結點揉稚。每次插入元素后p結點變?yōu)閠ail結點。那么第三次插入元素時就是在第二個元素后面插入p結點
int main()
{
node *head,*tail,*p;
int num;
head=tail=NULL;
printf("Enter num: ");
scanf("%d",&num);
while(num!=0){
p=(node *)calloc(1,sizeof(node));
p->data=num;
if(head==NULL)
head=p;
else
tail->next=p;
tail=p;
scanf("%d",&num);
}
for(p=head;p;p=p->next)
printf("%-4d",p->data);
printf("\n");
return 0;
}
尾插法建立鏈式線性表(有首元)
有一個頭結點熬粗，也就是在while()外面先開辟一個node大小的內存空間搀玖，默認該結點的數(shù)據(jù)為0。還有一點不同是判斷的時候要判斷head結點的下一個結點是否為空驻呐。
int main()
{
node *head,*tail,*p;
int num;
printf("Enter some integers: ");
scanf("%d",&num);
head=(node *)calloc(1,sizeof(node)); //初始化內存灌诅，設置為0
while(num!=0){
p=(node *)calloc(1,sizeof(node));
p->data=num;
if(head->next==NULL) //head如何連接后一個元素
head->next=p;
else
tail->next=p; //第二個元素和后面元素的連接方式
tail=p;
scanf("%d",&num);
}
for(p=head->next;p;p=p->next)
printf("%-5d",p->data);
printf("\n");
return 0;
}
==================================================
題外話
結構體
這種類型是可以將多種數(shù)據(jù)類型組合起來的結構。
聲明方式:
struct 結構體名稱{
成員1的類型 成員1的名稱含末；
成員2的類型 成員2的名稱猜拾；
............
成員3的類型 成員3的名稱；
};
舉例:
struct fact{
int data;
struct fact *next;
};
利用typedef定義這個結構體佣盒，即為結構體起別名node
typedef struct fact{
int data;
struct fact *next;
}node;
等價于
typedef struct fact{
int data;
struct fact *next;
};
typedef struct fact node;
malloc挎袜、calloc和realloc區(qū)別
三個函數(shù)的申明分別為:
void* malloc(unsigned size);
void* realloc(void* ptr, unsigned newsize);
void* calloc(size_t numElements, size_t sizeOfElement);
calloc 在初始化內存時設置初值為0。參數(shù)sizeOfElement為申請地址的單位元素長度 ，numElements為元素個數(shù)宋雏，即在內存中申請numElements*sizeOfElement字節(jié)大小的連續(xù)地址空間
malloc分配內存位于堆中芜飘，并且沒有初始化內存的內容务豺。因此基本上malloc之后磨总，調用函數(shù)memset來初始化這部分的內存空間。在內存的動態(tài)存儲區(qū)中分配一塊長度為size字節(jié)的連續(xù)區(qū)域笼沥，參數(shù)size為需要內存空間的長度蚪燕，返回該區(qū)域的首地址缩举。
realloc對malloc申請的內存進行大小的調整
申請的內存最終需要通過函數(shù)free來釋放
這三個函數(shù)都是在stdlib.h函數(shù)庫中蚤蔓，它們的返回值都是請求系統(tǒng)分配的地址钝域，如果請求失敗就返回NULL屋群。
最后說明一點萝衩，真的是實踐出真理垃你。如果不能完整的靠自己寫出代碼俱两，那就不算自己懂赎线。
============================補充內容===================================
這兩天又把這部分認真看了看舞骆，實現(xiàn)了一下钥弯。并把每種方法封裝成為一個子函數(shù)
頭插法
頭插法傳入參數(shù)是一個指針變量和一個整形數(shù)
返回類型是指針類型，因為通過頭插法建立的鏈表需要由head指針的首地址索引依次遍歷才能找到其他鏈表元素督禽。
Node* CreatLinkListHead(Node *head,int num)
{
for(int i =0;i<num;i++)
{
Node *p = (Node *)malloc(sizeof(Node));
p ->data = i+1;
p->next = NULL;
if(head == NULL)
{
head = p;
}
else
{
p->next = head;
head = p;
}
}
return head;
}
尾插法(無首元)
思想同頭插法脆霎，但是有一點需要注意的是: tail = p應寫在else的外面，即對head結點也適用狈惫。插入head結點后睛蛛，head結點和tail結點都是p結點代替，這樣當遇到非head結點時胧谈，tail->next才能找到位置否則容易出錯忆肾。
//尾插法
Node* CreatLinkListTail(Node *head,int num)
{
Node *p,*tail;
head = tail = NULL;
for(int i = 0;i<num;i++)
{
p = (Node *)malloc(sizeof(Node));
p ->data = i+1;
p->next = NULL;
if(head == NULL)
{
head = p;
}
else
{
tail ->next = p;
}
tail = p;
}
return head;
}
輸出函數(shù)Output
從head結點依次遍歷直到null
void Output(Node *head)
{
Node *p;
p = head;
while(p){
cout << p->data << " ";
p = p->next;
}
cout <<endl;
}
注意事項
在使用malloc分配內存空間時，必須指定p->next = null菱肖。因為malloc函數(shù)不同于calloc函數(shù)會指定初始值為0客冈，malloc函數(shù)的初始值是隨機的，對數(shù)據(jù)的輸出會造成一定的影響蔑滓。
