linked list

谁践踏了优雅 2022-01-15 10:09 195阅读 0赞

[为什么80%的码农都做不了架构师？>>> ][80_]  ![hot3.png][]

1,有关链表的概念

1.  作用：a,动态分配存储空间. b,根据需要随时开辟存储空间，灵活，方便。
2.  分类
    
    A, 单向链表 B,双向链表 C,循环链表
3.  思想
    
    a,链表的每一个结点都是结构体类型。包含两部分：
    
    （1）用户数据的成员分量
    
    （2）指向该结构体的指针变量，用来指向下一个结点。
    
    b.用一个指向结构体的指针变量指向第一个结点，称为头指针。
    
    c,最后一个结点的指针分量为NULL,为空，称为链尾。

2,链表的基本操作

举例如下，

![15103739_j0uV.gif][] ![15103739_lg9z.gif][] 代码

`1 // 建立某门课程的成绩单链表（包括学号，姓名，成绩） 2   3 #include " iostream " 4 #include " stdio.h " 5 using namespace std; 6 // 结点结构体 7 struct link 8 { 9 int num; 10 char name[ 10 ]; 11 int score; 12 struct link * next;//指向下一个结点 13 }; 14 // 建立链表函数 15 struct link * Create() 16 { 17 struct link * head, * tail, * p; 18 int num; 19 head = ( struct link * )malloc( sizeof ( struct link)); 20 head -> next = NULL; 21 tail = head; 22 scanf( " %d " , & num); 23 while (num != 0 ) // 循环建立链表 24 { 25 p = ( struct link * )malloc( sizeof ( struct link)); // 动态分配结点空间 26 p -> num = num; 27 scanf( " %s%d " ,p -> name, & p -> score); // 输入结点数据 28 tail -> next = p; // 链入链尾 29 tail = p; // 当前结点是新的链尾 30 scanf( " %d " , & num); // 输入下一个num 31 } 32 tail -> next = NULL; // 链尾置空 33 return head; // 返回头指针 34 } 35 // 输出链表 36 void print( struct link * head) 37 { 38 struct link * p; 39 p = head -> next; 40 while (p) 41 { 42 printf( " %d,%s,%d,\n " ,p -> num,p -> name,p -> score); // 输出数据分量 43 p = p -> next; // 指向下一个结点 44 } 45 } 46 // 链表查找 47 void search( struct link * head, char name[]) 48 { 49 struct link * p; 50 p = head -> next; // p指向第一个结点 51 while (p && strcmp(p -> name,name) != 0 ) // 查找 52 { 53 p = p -> next; 54 if (p) // 找到输出结点 55 printf( " %d,%s,%d,\n " ,p -> num,p -> name,p -> score); 56 else printf( " No found %s\n " ,name); // 没找到 57 } 58 } 59 // 链表插入 60 void Insert( struct link * head, struct link * p) 61 { 62 struct link * p1, * p2; 63 p2 = head; p1 = head -> next; // 初始化 64 while (p1 && p -> num > p1 -> num) // 查找插入位置 65 { 66 p2 = p1; p1 = head -> next; // 插入结点 67 } 68 p2 -> next = p; 69 p -> next = p1; 70 } 71 // 对链表删除操作 72 void Delete( struct link * head, int num) 73 { 74 struct link * p1, * p2; 75 p2 = head;p1 = head -> next; // 初始化 76 while (p1 && p1 -> num != num) // 查找要删除的结点 77 { 78 p2 = p1; p1 = p1 -> next; 79 } 80 if (p1) 81 { 82 p2 -> next = p1 -> next; 83 free(p1); // 释放p1所占的存储空间 84 } 85 else printf( " No found %d\n " ,num); 86 } 87 // 主函数 88 void main() 89 { 90 struct link * head , * p; 91 char name[ 100 ]; 92 int num; 93 head = Create(); 94 print(head); 95 scanf( " %s " ,name); 96 search(head ,name); 97 p = ( struct link * )malloc( sizeof ( struct link)); 98 scanf( " %d%s%d " , & p -> num, & p -> name, & p -> score); 99 Insert(head,p); 100 print(head); 101 scanf( " %d " , & num); 102 Delete(head,num); 103 print(head); 104 } 105 106 107 108`

转载于:https://my.oschina.net/garyun/blog/602873

[80_]: https://my.oschina.net/u/2663968/blog/3051541
[hot3.png]: /images/20220115/16b5121121d34b139bf38d962c18bb86.png
[15103739_j0uV.gif]: http://static.oschina.net/uploads/img/201601/15103739_j0uV.gif
[15103739_lg9z.gif]: /images/20220115/8a8eb3cf220849e682e7bc5d968dc32f.png