【数据结构】线性表（二）—— 单链表（C语言版）_设单链表中结点的结构为struct linknode{ //链表结点定义 e data; //数据

线性表的链式存储结构

定义：

用一组任意的存储单元存储线性表的数据元素，（这组存储单元可以是连续的，也可以是不连续的），逻辑上相邻的元素存储位置不一定相邻。

链式结构中，除了要存储数据元素信息外，还要存储它的后继元素的存储地址。

注：以下示例中结点只包含一个指针域，所以称为单链表

结点：包含两个域：数据域（存储数据元素信息）、指针域（存储直接后继存储位置）

头指针：链表中第一个结点的存储位置，之后的每一个结点，其实就是上一个的后继指针指向的位置，最后一个结点的指针为null。

头结点：在单链表的第一个结点前附设一个结点，其数据域可不存储信息，可存储附加信息。若指针域为空，则线性表为空表。头结点的指针域存储指向第一个结点的指针

头指针与头结点的异同：

头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针
头指针具有标识作用，所以常用头指针冠以链表的名字
无论链表是否为空，头指针均不为空，头指针是链表的必要元素
头结点不一定是链表必须要素
1
2
3
4

引入头结点的优点：

  1）使得在链表的第一个位置上的操作和在表的其他位置上的操作一致。

  2）空表和非空表的处理一致。
1
2
3

不带有头结点的单链表

带有头结点的单链表

空链表图示：

单链表的实现

数据元素结构体定义

typedef struct{
    char  no[20];
    char  name[50];
    float price;
}Book;

typedef Book ElemType;
1
2
3
4
5
6
7

单链表的结点类型

typedef struct LNode
{
    ElemType    data;
    struct LNode *next;
}LNode, *LinkList;          //LinkList为指向结构体LNode的指针类型
1
2
3
4
5

单链表的初始化

初始化操作是创建一个只有一个头结点的空链表，

void InitLinkList (LinkList *head)
{
    (*head) = (LinkList)malloc(sizeof(LNode));  //注意在函数中，(*head) 代表head指向的结点
    (*head)->next = NULL;
}
1
2
3
4
5

单链表的读取

· 获得链表第i个数据的算法思路：

    -声明一个结点p指向链表第一个结点，初始化 j 从 0 开始。

    -当j < i 时，就遍历链表，让p的指针向后移动，不断指向下一结点，j++。 // 注意保持 j 和 p 的同步。

    -若到链表末尾 p 为空，则说明第i个元素不存在。

    -否则查找成功，返回结点p的数据。
1
2
3
4
5
6
7

Status GetElem (LinkList head, int i, ElemType *e)
{
    int j=0;
    LinkList p;
    p = head;
    while (j < i && p != NULL)
    {
        j++;
        p = p->next;
    }
    if (!p || j>i)
    {
        printf("i is error");
        return ERROR;
    }
    else
    {
        *e = p->data;
        return OK;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

单链表的插入

单链表第i个数据插入结点的算法思路：

声明一结点 p 指向链表第一个结点，初始化 j 从 0 开始
当 j < (i - 1) 时，就遍历链表，让p的指针向后移动，不断指向下一结点，j ++；
若到链表末尾p为空，则说明第i个元素不存在
否则查找成功，在系统中生成一个空结点 temp
将数据元素 e 赋值给 temp -> data
单链表的插入标准语句 temp -> next = p->next; p->next=temp ;
1
2
3
4
5
6

// 注意 j 与 p 的指向必须一致

Status InsertList (LinkList *head, int i, ElemType elem)
// 注：也可以使用head， 因为head指向头结点，所指向的头结点的地址未发生改变
{
    LinkList p;
    p = (*head);       // p 指向头结点
    int j = 0;
    while (j < (i-1) && p->next != NULL )  // j < (i-1) : j在第 i-1 的位置停止   // 注意 j 与 p 的指向必须一致
    {
        j++;
        p = p->next;
    }
    if (!(p->next) || j> (i-1))
    {
        printf("i is error");
        return ERROR;
    }
    else
    {
        LinkList temp;
        temp  = (LinkList)malloc(sizeof(LNode));
        temp->data = elem;

        temp->next = p->next;
        p->next = temp;

        return OK;
    }

/*
    if (p = NULL)
    {
        printf("LinkList is Empty");

    }// 可能插入在空表中，故不能作为依据；*/
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

单链表的删除

单链表第i个数据删除结点的算法思路：

声明一结点指针 p 指向链表第一个结点，初始化 j 从 0 开始
当 j < (i-1) 时，就遍历链表，让 p 的指针向后移动，不断指向下一个节点，j ++;
若在 位置序号为 [ 1, i-1 ] 的遍历过程中 p指向的结点均 不为空，则说明第 [ 1, i-1 ] 个元素均存在；此时通过  判断 p->next == NULL ,判断 第 i 个元素是否存在；若存在，

则申请指向结点的指针 temp , 令 temp = p-> next ;
将 temp 所指向的结点的数据域的值 data 赋值给 *e； 
令 p->next = p->next->next;  也可以为 p->next = temp->next;
最后释放 temp 结点；
1
2
3
4
5
6
7
8

Status DeleteList (LinkList *head, int i, ElemType *e)
{
    LinkList p;
    p = (*head);
    int j = 0;
    while (j < (i-1) && p != NULL)
    {
        j ++;
        p = p->next;
    }
    if (!(p->next) || j > (i-1))//  (j!=i-1)
    {
        printf("i is error\n");
        return ERROR;
    }
    else
    {
        if (p->next != NULL)//判断是否有第 i 个结点
        {
            LinkList temp;
            temp = p->next;
            *e = temp->data;
            p->next = p->next->next;
            free(temp);
            return OK;
        }
        else
        {
            printf("i is error, \n");
            return ERROR;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

单链表在查询、插入和删除操作上的时间复杂度都是O(n)，但是如果需要从第i个位置，插入10个元素，对于顺序存储结构意味着，每一次插入都需要移动n-i个元素，每次都是O(n)，而单链表，只需要在第一次时，找到第i个位置的指针，此时为O(n)，接下来的时间复杂度都是O(1)，所以对于插入或者删除数据越频繁的操作，单链表的效率优势就越是明显

单链表整表的创建

单链表整表创建的算法思路：

声明一结点p和计数器变量i
初始化一空链表L
让L的头结点的指针指向NULL，即建立一个带头结点的单链表

循环：
    生成一新结点赋值给p
    随机生成一数字赋值给p的数据域p->data
    将p插入到头结点与前一新结点之间（头插法，始终让新结点在第一的位置），也可以将p插入到终端结点的后面（尾插法）
1
2
3
4
5
6
7
8

// 头插法，创建 n 个元素的链表
void CreateListHead (LinkList *head, int n)
{
    (*head) = (LinkList)malloc(sizeof(LNode));
    (*head)->next = NULL;

    LinkList p, t;
    p = (*head);
    int i;
    for (i = 0; i<n; i++)
    {
        ElemType elem;
        elem = inputStruct(&elem);
        t = (LinkList)malloc(sizeof(LNode));
        t->data = elem;

        t->next = p->next;
        p->next = t;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

void CreateListTail (LinkList *head, int n)
{
    (*head) = (LinkList)malloc(sizeof(LNode));
    (*head)->next = NULL;
    int i = 0;
    LinkList p, t;
    p = (*head);
    for (i = 0; i<n; i++)
    {
        t = (LinkList)malloc(sizeof(LNode));
        ElemType elem;
        t->data = inputStruct(&elem);
        t->next = NULL;

        p->next = t;
        p = t;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

单链表的销毁

单链表整表删除的算法思路如下：

声明一结点p和q
将第一个结点赋值给p

循环
    将下一结点赋值给q
    释放p
    将q赋值给p
1
2
3
4
5
6
7

Status DestroyLinkList (LinkList *head)
{
    LinkList p;
    p = (*head);
    LinkList t;         // t 是十分有必要的；
    while (p != NULL)
    {
        t = p;
        p = p->next;
        free(t);
    }
    *head = NULL;
    return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

两个有序链表并为一个有序链表：

· 跟顺序存储链表类似，只不过改变了链表结点之间的关联性。

算法实现：//MergeList_L

void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc) {
    //已知单链线性表La和Lb的元素按递增排列
    //求并集，得到新的单链线性表Lc，它也按递增排列
    LinkList pa, pb, pc;
    pa = La->next;
    pb = Lb->next;
    Lc = pc = La;   //用La的头结点作为Lc的头结点
    while (pa && pb) {
        if (pa->data < pb->data) {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        } else if (pa->data > pb->data) {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        } else {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
            pb = pb->next;
        }
    }
    pc->next = pa ? pa : pb;  //插入剩余片段
    free(Lb);       //释放头结点
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

```c
// https://www.cnblogs.com/roverliang/p/11468815.html
//  头结点为 存取数据元素 的情况
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define TRUE    1
#define FALSE   0

#define OK      1
#define ERROR   0
#define Status  int

typedef struct{
    char  no[20];
    char  name[50];
    float price;
}Book;

typedef Book ElemType;

typedef struct LNode
{
    ElemType    data;
    struct LNode *next;
}LNode, *LinkList;          //LinkList为指向结构体LNode的指针类型

// 初始化，对头指针进行修改操作
void InitLinkList (LinkList *head)
{
    (*head) = (LinkList)malloc(sizeof(LNode));  //注意在函数中，(*head) 代表head指向的结点
    (*head)->next = NULL;
}

Status IsEmptyList (LinkList head)
{
    if (head->next == NULL)
        return OK;
    else
        return ERROR;
}

Status LenLinkList (LinkList head)
{
    int num = 0;
    LinkList p;
    p = head;
    while (p->next != NULL)
    {
        num++;
        p = p->next;
    }

    return num;
}



//释放单链表L的所有结点，但保留头结点
Status ClearList(LinkList head)
{
    LinkList p, t;
    p = head->next;
    while (p != NULL)
    {
        t = p;
        p = p->next;
        free(t);
    }
    head->next = NULL;
    return OK;
}

Status InsertSData (LinkList *head, int i, ElemType elem)
// 注：也可以使用head， 因为head指向头结点，所指向的头结点的地址为发生改变即可
{
    LinkList p;
    p = (*head);       // p 指向头结点
    int j = 0;
    while (j < (i-1) && p->next != NULL )  // j < i : j在第 i-1 的位置   // 注意 j 与 p 的指向必须一致
    {                                   // p 指向 第 j 个结点
        j++;
        p = p->next;
    }
    if (!(p->next) || j> (i-1))  // 判断是否是缺少结点， 或者 j 计数错误
    {
        printf("i is error\n");
        return ERROR;
    }
    else
    {

        LinkList temp;
        temp  = (LinkList)malloc(sizeof(LNode));
        temp->data = elem;

        temp->next = p->next;
        p->next = temp;

        return OK;
    }

/*
    if (p = NULL)
    {
        printf("LinkList is Empty");

    }// 可能插入在空表中，故不能作为依据；*/
}

// 先连接，后删除！
Status DeleteSData (LinkList *head, int i, ElemType *e)
{
    LinkList p;
    p = (*head);
    int j = 0;
    while (j < (i-1) && p->next != NULL)
    {
        j ++;
        p = p->next;
    }
    if (!(p->next) || j > (i-1))//  (j!=i-1)
    {
        printf("i is error\n");
        return ERROR;
    }
    else
    {
        if (p->next != NULL)//判断是否有第 i 个结点
        {
            LinkList temp;
            temp = p->next;
            *e = temp->data;
            p->next = p->next->next;
            free(temp);
            return OK;
        }
        else
        {
            printf("i is error, \n");
            return ERROR;
        }
    }
}




/*
void DelLinklist(Linklist *head, int data)//删除结点值 = data的结点。
{
    Linklist *p, *q;
    q = head;
    p = head->next;
    while (p->next != NULL && p->data != data)
    {
        p = p->next;
        q = q->next;
    }
    if (p->data != data && p->next == NULL)
        printf("链表中无此节点");
    else
    {
        q->next = p->next;
        free(p);
    }
}//还未实现多个结点==某个值
*/


Status GetElem (LinkList head, int i, ElemType *e)
{
    int j=0;
    LinkList p;
    p = head;
    while (j < i && p->next != NULL)
    {
        j++;
        p = p->next;
    }
    if (!p || j>i)
    {
        printf("i is error");
        return ERROR;
    }
    else
    {
        *e = p->data;
        return OK;
    }
}



void PrintSData (LinkList head)
{
    LinkList p;
    p = head;
    while (p->next != NULL)
    {
        p = p->next;//(".....\n");//
        printf ("图书编号：%s, 图书书名：%s， 图书价格：%f\n", p->data.no, p->data.name, p->data.price);
    }
}


Status DestroyLinkList (LinkList *head)
{
    LinkList p;
    p = (*head);
    LinkList t;         // t 是十分有必要的；
    while (p != NULL)   // 注意销毁时的循环条件为 头指针 不为0； 不同于其他函数 为 头结点的指针域
    {
        t = p;
        p = p->next;
        free(t);
    }
    *head = NULL;
    return OK;
}



ElemType InputSData (ElemType *p)
{
    printf("请按要求输入数据元素：\n");
    scanf("%s", &p->no);
    scanf("%s", &p->name);
    scanf("%f", &p->price);
    return *p ;
}


// 尾插法，创建 n 个元素的链表
void CreateListTail (LinkList *head, int n)
{
    (*head) = (LinkList)malloc(sizeof(LNode));
    (*head)->next = NULL;
    int i = 0;
    LinkList p, t;
    p = (*head);
    for (i = 0; i<n; i++)
    {
        t = (LinkList)malloc(sizeof(LNode));
        ElemType elem;
        t->data = InputSData(&elem);
        t->next = NULL;

        p->next = t;
        p = t;

    }
}
/* 尾插法2
LinkList *Create(LinkList *L)
{
	Node *r,*s;
	int c,n;
	int i;
	*L=(LinkList)malloc(sizeof(Node));
	r=*L;
	printf("你要输入多少个数:\n");
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		printf("No.%d:",i);
		scanf("%d",&c);
		s=(LinkList)malloc(sizeof(Node));
		s->data=c;
		s->next=NULL;
		r->next=s;
		r=s;
	}
	return L;
}
*/
/* 尾插法3
Linklist* InitList(int i)//i为链表大小
{
    Linklist *head;
    head = (Linklist*)malloc(sizeof(Linklist));
    Linklist *end=head;
    int j = 0;
    for (j = 0;j < i;j++)
    {
        Linklist *node = (Linklist*)malloc(sizeof(Linklist));
        scanf("%d", &node->data);
        end->next = node;
        end = node;
    }
    end->next = NULL;
    return head;
}
*/



// 头插法，创建 n 个元素的链表
void CreateListHead (LinkList *head, int n)
{
    (*head) = (LinkList)malloc(sizeof(LNode));
    (*head)->next = NULL;

    LinkList p, t;
    p = (*head);
    int i;
    for (i = 0; i<n; i++)
    {
        ElemType elem;
        elem = InputSData(&elem);
        t = (LinkList)malloc(sizeof(LNode));
        t->data = elem;

        t->next = p->next;
        p->next = t;
    }
}



int main()
{
    /*头插法验证
    LinkList L;
    CreateListHead(&L, 4);
    PrintLinkList(L);
*/
    /*尾插法验证
    LinkList L;
    CreateListTail(&L, 5);
    PrintLinkList(L);
    */
    /*普通方法验证
    LinkList head;
    InitLinkList(&head);

    ElemType elem1, elem2, elem3;

    inputStruct(&elem1);
    InsertList(&head, 1, elem1);
    inputStruct(&elem2);
    InsertList(&head, 2, elem2);

    printf("链表长度：%d\n", LenLinkList(head));
    printf("链表是否为空： %d. (空为1，非空为0)\n", IsEmptyList(head));


    ElemType t;
    GetElem(head, 1, &t);
    printf("图书编号：%s, 图书书名：%s， 图书价格：%f\n", t.no, t.name, t.price);

    GetElem(head, 2, &t);
    printf("图书编号：%s, 图书书名：%s， 图书价格：%f\n", t.no, t.name, t.price);



    PrintLinkList(head);


    printf("在链表中间(第二个位置)插入元素：\n");
    inputStruct(&elem3);
    InsertList(&head, 2, elem3);
    PrintLinkList(head);


    printf("删除表尾元素：\n");
    DeleteList(&head, 3, &t);
    PrintLinkList(head);

    printf("删除非表尾元素：\n");
    DeleteList(&head, 1, &t);
    PrintLinkList(head);

    printf("%p", head);
    DestroyLinkList(&head);
    printf("： %d. \n", DestroyLinkList(&head));
    printf("%p", head);
    */
    /* 判断去清除与销毁链表
    LinkList L;
    CreateListHead(&L, 2);
    PrintLinkList(L);
    printf("长度：%d\n", LenLinkList(L));
    ClearList(L);
    printf("长度：%d\n", LenLinkList(L));
    printf("%p\n", L);
    DestroyLinkList(&L);
    printf("%p\n", L);
*/


    LinkList L;
	int choice;
	do
	{
printf("1.ListInit\t2.CreateListHead(头插法)\t3.CreateListTail(尾插法)\n4.PrintList\t5.GetLength\t6.ListEmpty\n7.Getelem\t8.ListInsert\t9.ListDelete\n10.ClearList\t11.DestroyList\n");

		printf("\n请输入你的选择:\n");
		scanf("%d",&choice);
		switch(choice)
		{
		system("cls");
		case 0:
		    printf("byebye\n");
			break;
		case 1:
			{
			    InitLinkList(&L);
			    break;
			    /*
				if(InitLinkList(&L)==OK)  // void
                    printf("success\n");
				else
					printf("flase\n");
				break;
				*/
			}
		case 2:
			{
				int n;
				printf("请输入你要存放的数据量:\n");
				scanf("%d",&n);
				CreateListHead(&L, n);
				break;
			}
		case 3:
			{
				//L=*Create(&L);
				int n;
				printf("请输入你要存放的数据量:\n");
				scanf("%d",&n);
				CreateListTail(&L, n);
				break;
			}
		case 4:
			{
				PrintSData(L);
				printf("\n");
				break;
			}
		case 5:
			{
				int count;
				count=LenLinkList(L);
				printf("长度为:%d\n",count);
				break;
			}
		case 6:
			{
				printf("链表是否为空：%d. （1为空，0为非空）\n", IsEmptyList(L));
				break;
			}
		case 7:
			{
				int i;
				ElemType e;
				printf("请问你想要第几个数:\n");
				scanf("%d",&i);
				printf("图书编号：%s,图书书名：%s, 图书价格：%f", e.no, e.name, e.price);
				break;
			}
		case 8:
			{
				int i;
				ElemType elem;
				InputSData(&elem);

				printf("请输入你要插入的位置:\n");
				scanf("%d",&i);
				if (InsertSData(&L, i, elem) == OK)
                    printf("插入成功");
                else
                    printf("插入失败");
				break;
			}
		case 9:
			{
				int i;
				ElemType e;
				printf("你想要删除第几个元素:\n");
				scanf("%d",&i);
				if(DeleteSData(&L,i,&e) == OK)
					printf("删除成功\n");
				else
					printf("删除失败\n");
				printf("第%d个数是:\n图书编号：%s,图书书名：%s, 图书价格：%f\n", i, e.no, e.name, e.price);
                break;
			}
        case 10:
            {
                printf("........");
                if (ClearList(L) == OK)
                    printf("清除成功");
                else
                    printf("清除失败");

                printf("长度：%d\n", LenLinkList(L));
                printf("%p\n", L);
                break;
            }
        case 11:
            {
                DestroyLinkList(&L);
                printf("%p\n", L);
                break;
            }
		default:
		    printf("输入错误，请重新输入\n");
			break;
			system("pause");
		}
	}while(choice!=0);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516