單鏈表
時間：2019-07-12 來源：沈陽中心，楊老師
鏈表用來解決1 順序表數據大量移動的問題
2 解決順序表元素數量固定的問題
鏈表分為單向鏈表，雙向鏈表，單向循環鏈表，雙向循環鏈表
單鏈表通常有兩個域
數據域(保存數據)
指針域(保存下一個節點的位置)
單鏈表結構體定義如下
typedef struct node_t
{
int data; //數據域
struct node_t *next; //指針域，通過指針域可以找到下一個節點
}link_node_t;
typedef struct node_t
{
struct student data; //數據域
struct node_t *next; //指針域，通過指針域可以找到下一個節點
}link_node_t;
typedef struct node_t
{
char name[20]; //數據域
struct node_t *next; //指針域，通過指針域可以找到下一個節點
}link_node_t;
/////////////////////////
有這些名字，我們用單鏈表將這些名字連接起來
"yang", "li", "liu", "wang"
#include <stdio.h>
typedef struct node_t
{
char name[20]; //數據域
struct node_t *next; //指針域，通過指針域可以找到下一個節點
}link_node_t;
int main()
{
link_node_t *h;
link_node_t A = {"yang", NULL};
link_node_t B = {"li", NULL};
link_node_t C = {"liu", NULL};
link_node_t D = {"wang", NULL};
A.next = &B;
B.next = &C;
C.next = &D;
h = &A;
//輸出每個節點
while(h != NULL)
{
printf("%s\n", h->name);
h = h->next;
}
}
/////////////
單向鏈表 兩種類型
1 不帶頭結點的單向鏈表(鏈表中所有元素都是有效的)
上面名字例子：
2 帶頭結點的單向鏈表 (頭結點: 是一個空節點，這個節點不存有效數據，只有next是有效的)
#include <stdio.h>
typedef struct node_t
{
char name[20]; //數據域
struct node_t *next; //指針域，通過指針域可以找到下一個節點
}link_node_t;
int main()
{
link_node_t h; //頭結點
link_node_t A = {"yang", NULL};
link_node_t B = {"li", NULL};
link_node_t C = {"liu", NULL};
link_node_t D = {"wang", NULL};
A.next = &B;
B.next = &C;
C.next = &D;
h.next = &A;
link_node_t *p;
p = &h;
//輸出每個節點
while(p->next != NULL)
{
p = p->next;
printf("%s\n", p->name);
}
}
用帶頭結點的單向鏈表存儲n個學生成績 ，成績由鍵盤輸入，輸入<=0 時結束
////
#include <stdio.h>
#include <stdlib.h>
typedef struct node_t
{
int score; //數據域
struct node_t *next; //指針域，通過指針域可以找到下一個節點
}link_node_t;
int main()
{
int s;
//創建一個頭結點
link_node_t *p, *q, *h;//p 是新節點 q 是最后一個節點 h是第一個節點
p = malloc(sizeof(link_node_t));
p->next = NULL;
q = p;
h = p;
while(1)
{
scanf("%d", &s);
if(s <= 0)
break;
p = malloc(sizeof(link_node_t));
p->score = s;
p->next = NULL;
q->next = p;
q = p;
}
p = h;
while(p->next != NULL)
{
p = p->next;
printf("%d\n", p->score);
}
//再寫個釋放程序
while(h != NULL)
{
p = h->next;
free(h);
h = p;
}
}
鏈表有這些操作
#include <stdio.h>
#include <stdlib.h>
typedef struct node_t
{
int data; //數據域
struct node_t *next; //指針域
}link_node_t, *link_list_t;
//1 創建空鏈表(帶頭結點的單向鏈表)
link_node_t *CreateEmptyLinklist()
{
link_node_t *p = malloc(sizeof(link_node_t));
p->next = NULL;
return p;
}
//2 判斷表是否為空 1 空 0 非空
int EmptyLinklist(link_node_t *p)
{
if(p->next == NULL)
return 1;
else
return 0;
}
//2.5 求鏈表長度
int LengthLinklist(link_node_t *p)
{
int i = 0;
while(p->next != NULL)
{
i++;
p = p->next;
}
return i;
}
//3 查找某個位置元素的值
int GetLinklist(link_node_t *p, int pos)
{
int i;
if(pos > LengthLinklist(p) + 1 || pos < 1)
return -1;
for(i = 0; i < pos; i++)
{
p = p->next;
}
return p->data;
}
//4 插入元素
int InsertLinklist(link_node_t *p, int pos, int x)
{
int i;
link_node_t *q;
if(pos > LengthLinklist(p) + 1 || pos < 1)
return -1;
for(i = 0; i < pos - 1; i++)
{
p = p->next;
}
q = malloc(sizeof(link_node_t));
q->data = x;
q->next = p->next;
p->next = q;
return 0;
}
//5 刪除元素
int DeleteLinklist(link_node_t *p, int pos)
{
int i;
link_node_t *q;
if(pos > LengthLinklist(p) + 1 || pos < 1)
return -1;
for(i = 0; i < pos - 1; i++)
{
p = p->next;
}
q = p->next;
p->next = q->next;
free(q);
return 0;
}
//6 將鏈表倒置(逆轉)
void ReverseLinklist(link_node_t *h)
{
link_node_t *p, *q;
p = h->next;
h->next = NULL;
while(p != NULL)
{
q = p;
p = p->next;
q->next = h->next;
h->next = q;
}
return;
}
//7 輸出鏈表中所有元素
void PrintLinklist(link_node_t *p)
{
while(p->next != NULL)
{
p = p->next;
printf("%d ", p->data);
}
printf("\n");
}
int main()
{
link_node_t *h = CreateEmptyLinklist();
printf("%d\n", InsertLinklist(h, 1, 40));
InsertLinklist(h, 1, 20);
InsertLinklist(h, 2, 30);
PrintLinklist(h); //20 30 40
InsertLinklist(h, 1, 10);
PrintLinklist(h); //10 20 30 40
DeleteLinklist(h, 3);
PrintLinklist(h); //10 20 40
ReverseLinklist(h);
PrintLinklist(h); //40 20 10
}
