七、链表

---

 

---

1.typedef的用法

示例1：

1. #include <stdio.h>

2. typedef int zhengxing;//给int取了另外一个名字zhengxing

3. typedef struct Student

4. {

5. int sid;

6. int age;

7. } ST;

8. int main(void)

9. {

10. int i = 100;//等价于zhengxing i = 100;

11. zhengxing j = 200;

12. printf(“%d”, j);

13. struct Student st;//等价于ST st;

14. struct Student * ps = &st;//等价于ST * ps

15. ST st2;

16. st2.age = 900;

17. printf(“%d”, st2.age);

18. return 0;

19. }

示例2：

简略结构体指针的声明

1. #include <stdio.h>

2. typedef struct Student

3. {

4. int sid;

5. int age;

6. } * PST, ST; //PST等价于 struct Student * , ST等价于struct Student

7. int main(void)

8. {

9. ST st;

10. PST pst = &st;

11. pst->sid = 99;

12. printf(“%d”, pst->sid);

13. return 0;

14. }

2.离散存储【链表】

1.定义

n个节点离散分配

彼此通过指针相连

每个节点只有一个前驱节点，也只有一个后续节点

首节点没有前驱节点，尾节点没有后续节点

专业术语：

首节点：第一个有效的节点

尾节点：最后一个有效的节点

头结点：第一个有效节点之前的那个节点

头结点没有存数据，不存在实际意义，只是为了便于增删操作

头指针：指向头节点的指针变量

尾指针：指向尾节点的指针变量

获取一个链表需要几个参数：

只需要一个参数：头指针，其他的都可以推算

链表示例

1. typedef struct Node

2. {

3. int data;// 数据域

4. struct Node * pNext;// 指针域

5. }NODE, *PNODE;//NODE等价于struct Node, PNODE等价于struct Node *

2.分类

单链表

双链表

每一个节点有两个指针域

循环链表

能通过任何一个节点找到其他所有的节点

非循环链表

怎么讲q指向的节点插入到q指向节点后面？

怎么删除非循环链表节点

这样子没办法吧中间那个节点内存释放

3.算法

示例：

1. #include <stdio.h>

2. #include <malloc.h>

3. #include <stdlib.h>

4. typedef struct Node

5. {

6. int data;// 数据域

7. struct Node * pNext;// 指针域

8. }NODE, *PNODE;//NODE等价于struct Node, PNODE等价于struct Node *

9. int main(void)

10. {

11. PNODE pHead = NULL;

12. pHead =

    create_list();//create_list()功能，创建一个非循环单链表，并将该链表头结点的地址赋给pHead

13. travcrse_list(pHead);//travcrse_list(pHead),用于遍历并输出每一个元素

14. return 0;

15. }

create_list方法

1. PNODE create_list(void)

2. {

3. int len;

4. int val;

5. PNODE pHead =

   (PNODE)malloc(sizeof(NODE));//给头结点分配NODE所需的内存空间

6. if (NULL == pHead)

7. {

8. printf(“内存分配失败！n”);

9. exit(-1);

10. }

11. PNODE pTail =

    pHead;//pTail是一个单纯的指针变量，这里指向pHead，所以pTail->pNext等价于pHead->pNext

12. pTail->pNext = NULL;

13. printf(“请输入您需要生成的链表节点的个数： len = “);

14. scanf_s(“%d”, len);

15. for (int i = 0; i < len; i++)

16. {

17. printf(“请输入第%d个节点的值： “, i + 1);

18. scanf_s(“%d”, &val);

19. PNODE pNew = (PNODE)malloc(sizeof(NODE));

20. if (NULL == pNew)

21. {

22. printf(“内存分配失败！n”);

23. exit(-1);

24. }

25. pNew->data = val;

26. pTail->pNext = pNew;

27. pNew->pNext = NULL;

28. //最后尾指针的下一指向为NULL

29. pTail = pNew;

30. }

31. return pHead;

32. }

先创建头指针和尾指针，头指针指向头节点

然后让尾指针指向头指针，得到头结点的信息

接着创建链表并输入数据

其中尾指针指向的头结点的pNext指向pNew

再让尾指针指向pNew节点，pNew节点的pNext指向下一节点，如此循环

最后获得一个由指针连接起来的链表

travcrse_list方法

遍历输出链表

1. void travcrse_list(PNODE pHead)

2. {

3. PNODE p = pHead->pNext;

4. while (p != NULL)

5. {

6. printf(“%d”, p->data);

7. p = p->pNext;

8. }

9. }

狭义的算法与数据的存数方式密切相关

广义的算法与数据的存储方式无关

泛型：

利用某种技术达到的效果就是：不同的存数方式，执行的操作时一样的

sort_list方法

1. void sort_list(PNODE pHead)

2. {

3. int i, j, t;

4. int len = length_list(pHead);

5. PNODE p, q;

6. //冒泡排序的变种，冒泡链表排序

7. for (i = 0, p = pHead->pNext;i < len - 1; i++, p = p->pNext)

8. {

9. for (j = i + 1, q = p->pNext; j < len; j++, q = q->pNext)

10. {

11. if (p->data > q->data)

12. {

13. t = p->data;

14. p->data = q->data;

15. q->data = t;

16. }

17. }

18. }

19. return;

20. }

insert_list方法

1. bool insert_list(PNODE pHead, int pos, int val)

2. {

3. PNODE p = pHead->pNext;

4. PNODE pNew = (PNODE)malloc(sizeof(NODE));

5. int len = length_list(pHead);

6. if (NULL == pNew)

7. {

8. printf(“内存分配失败！n”);

9. exit(-1);

10. }

11. if (is_empty(pHead))

12. {

13. return false;

14. }

15. if (pos < 1 || pos > len)

16. {

17. return false;

18. }

19. for (int i = 1; i < pos - 1; i++)

20. {

21. p = p->pNext;

22. }

23. pNew->data = val;

24. //这里要先把p->pNext赋给pNew->pNext，然后再把pNew赋给p->pNext,否则会出现错误

25. pNew->pNext = p->pNext;

26. p->pNext = pNew;

27. return true;

28. }

delete_list方法，跟insert_list差不多

1. bool delete_list(PNODE pHead, int pos, int * pVal)

2. {

3. PNODE p = pHead->pNext;

4. int len = length_list(pHead);

5. if (is_empty(pHead))

6. {

7. return false;

8. }

9. if (pos < 1 || pos > len)

10. {

11. return false;

12. }

13. for (int i = 1; i < pos - 1; i++)

14. {

15. p = p->pNext;

16. }

17. PNODE q = p->pNext;

18. *pVal = q->data;

19. p->pNext = p->pNext->pNext;

20. free(q);

21. q = NULL;

22. return true;

23. }

4.链表的优缺点

优：

不需要考虑存储空间大小的问题

缺：

查找费时