單向鏈表

單向鏈表

單向鏈表（單鏈表）是鏈表的一種，其特點是鏈表的鏈接方向是單向的，對鏈表的訪問要通過順序讀取從頭部開始；鏈表是使用指針進行構造的列表；又稱為結點列表，因為鏈表是由一個個結點組裝起來的；其中每個結點都有指針成員變數指向列表中的下一個結點；

列表是由結點構成，head指針指向第一個成為表頭結點，而終止於最後一個指向NULL的指針。

目錄
1鏈表的優點 2語言實例

鏈表的優點

單向鏈表
單向鏈表
相比較普通的線性結構，鏈表結構的可以總結一下：
（1）單個結點創建非常方便，普通的線性內存通常在創建的時候就需要設定數據的大小
（2）結點的刪除非常方便，不需要像線性結構那樣移動剩下的數據
（3）結點的訪問方便，可以通過循環或者遞歸的方法訪問到任意數據，但是平均的訪問效率低於線性表

語言實例

#include
#include
#define NULL 0
#define LEN sizeof(struct student)
struct student
{
long num;
float score;
struct student *next;
};
int n;
struct student *
Create ()
{
struct student *head;
struct student *p1 = NULL;
struct student *p2 = NULL;
n = 0;
p1 = (struct student *) malloc (LEN);
p2 = p1;
if (p1 == NULL)
{
printf ("\nCann't create it, try it again in a moment!\n");
return NULL;
}
else
{
head = NULL;
printf ("Please input %d node -- num,score: ", n + 1);
scanf ("%ld,%f", &(p1->num), &(p1->score));
}
while (p1->num != 0)
{
n += 1;
if (n == 1)
{
head = p1;
p2->next = NULL;
}
else
{
p2->next = p1;
}
p2 = p1;
p1 = (struct student *) malloc (LEN);
printf ("Please input %d node -- num,score: ", n + 1);
scanf ("%ld,%f", &(p1->num), &(p1->score));
}
p2->next = NULL;
free (p1);
p1 = NULL;
return head;
}
void
Print (struct student *head)
{
struct student *p;
printf ("\nNow , These %d records are:\n", n);
p = head;
if (head != NULL)
{
printf ("head is %o\n", head);
do
{
printf ("%o %ld %5.1f %o\n", p, p->num, p->score, p->next);
p = p->next;
}
while (p != NULL);
}
}
struct student *
Del (struct student *head, long num)
{
struct student *p1;
struct student *p2;
if (head == NULL)
{
printf ("\nList is null!\n");
return head;
}
p1 = head;
while (p1->num != num && p1->next != NULL)
{
p2 = p1;
p1 = p1->next;
}
if (num == p1->num)
{
if (p1 == head)
{
head = p1->next;
}
else
{
p2->next = p1->next;
}
free (p1);
p1 = NULL;
printf ("\ndelete %ld success!\n", num);
n -= 1;
}
else
{
printf ("\n%ld not been found!\n", num);
}
return head;
}
struct student *
Insert (struct student *head, long num, struct student *node)
{
struct student *p1;
if (head == NULL)
{
head = node;
node->next = NULL;
n += 1;
return head;
}
p1 = head;
while (p1->num != num && p1->next != NULL)
{
p1 = p1->next;
}
if (num == p1->num)
{
node->next = p1->next;
p1->next = node;
n += 1;
}
else
{
printf ("\n%ld not been found!\n", num);
}
return head;
}
struct student *
Reverse (struct student *head)
{
struct student *p;
struct student *p1;
struct student *p2;
p1 = NULL;
p2 = head;
while (p2 != NULL)
{
p = p2->next;
p2->next = p1;
p1 = p2;
p2 = p;
}
head = p1;
return head;
}
struct student *
SelectSort (struct student *head)
{
struct student *first;
struct student *tail;
struct student *p_min;
struct student *min;
struct student *p;
first = NULL;
while (head != NULL)
{
for (p = head, min = head; p->next != NULL; p = p->next)
{
if (p->next->num < min->num)
{
p_min = p;
min = p->next;
}
}
if (first == NULL)
{
first = min;
tail = min;
}
else
{
tail->next = min;
tail = min;
}
if (min == head)
{
head = head->next;
}
else
{
p_min->next = min->next;
}
}
if (first != NULL)
{
tail->next = NULL;
}
head = first;
return head;
}
struct student *
InsertSort (struct student *head)
{
struct student *firs

基本信息

中文名
單向鏈表
外文名
One-way LinkedList
定義
鏈表的一種
特點
鏈表的鏈接方向是單向的
目的
學習單向鏈表