[算法] 链表

链表的实现

一、静态链表

 1 #include<stdio.h>
 2 struct node{
 3     int data;
 4     struct node *next;
 5 };
 6 typedef struct node NODETYPE;
 7 
 8 int main(){
 9     NODETYPE a,b,c,*h,*p;
10     a.data=10;b.data=20;c.data=30;
11     h=&a;
12     a.next=&b;b.next=&c;c.next='';
13     p=h;
14     while(p){
15         printf("%d",p->data);
16         p=p->next;
17     }
18     printf("
");
19 }

分析：

1、此程序仅示意原理，在执行过程中不能人为再产生新的存储单元，也不能使已开辟的单元消失

2、在实际中多采用动态链表

二、动态链表

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 
 4 struct slist{
 5     int data;
 6     struct slist *next;
 7 };
 8 typedef struct slist SLIST;
 9 
10 SLIST *creat_slist(){
11     int c;
12     SLIST *h,*s,*r;
13     h=(SLIST*)malloc(sizeof(SLIST));
14     r=h;
15     scanf("%d",&c);
16     while(c!=-1){
17         s=(SLIST*)malloc(sizeof(SLIST));
18         s->data=c;
19         r->next=s;
20         r=s;
21         scanf("%d",&c);
22     }
23     r->next='';
24     return h;
25 }
26 void print_slist(SLIST *head){
27     SLIST *p;
28     p=head->next;
29     if(p=='') printf("Linklist is null!
");
30     else{
31         printf("head");
32         do{
33             printf("-->%d",p->data);
34             p=p->next;
35         }
36         while(p!='');
37         printf("-->end
");
38     }
39 }
40 void insert_snode(SLIST *head,int x,int y){
41     SLIST *s,*p,*q;
42     s=(SLIST *)malloc(sizeof(SLIST));
43     s->data=y;
44     q=head;p=head->next;
45     while((p!='')&&(p->data!=x)){
46         q=p;p=p->next;
47     }
48     s->next=p;q->next=s;
49 }
50 void delete_snode(SLIST *head,int x){
51     SLIST *p,*q;
52     q=head;p=head->next;
53     while((p!='')&&(p->data!=x)){
54         q=p;p=p->next;
55     }
56     q->next=p->next;
57     free(p);
58 }
59 int main(){
60     SLIST *head;
61     head=creat_slist();
62     print_slist(head);
63     insert_snode(head,2,4);
64     print_slist(head);
65     delete_snode(head,3);
66     print_slist(head);
67 }

分析：

1、创建链表

（1）功能：每次输入一个数并加到链表中

（2）输入输出：无；头结点指针h

（2）临时变量：头结点h，尾结点r，新结点s

2、输出链表

（1）功能：打印所有结点

（2）输入输出：头结点指针；head-->1-->2-->end（示例）

（3）临时变量：头结点p

3、插入结点

（1）功能：在某结点前插入新结点

（2）输入输出：头结点指针，插入结点的数据x，插入数据y；无

（3）临时变量：新结点s，前驱q，后继p

4、删除结点

（1）功能：删除某结点

（2）输入输出：头结点指针，删除结点的数据x；无

（3）临时变量：待删除结点p，前驱q

三、复杂动态链表

  1 #include<stdio.h>
  2 #include<malloc.h>
  3 #include<stdlib.h>
  4 
  5 typedef int ElementType;        //定义数据类型,可根据需要进行其他类型定义
  6 //链表节点的定义
  7 typedef struct ListNode {
  8     ElementType  Element;        //数据域，存放数据
  9     ListNode* Next;        //指向下一个链表节点
 10 } Node, *PNode;
 11 
 12 //链表创建函数定义
 13 PNode CreateList(void) {
 14     int len ;    //用于定义链表长度
 15     int val ;    //用于存放节点数值
 16     PNode PHead = (PNode)malloc(sizeof(Node));    //创建分配一个头节点内存空间
 17 //头节点相当于链表的哨兵，不存放数据，指向首节点（第一个节点）
 18     if (PHead == NULL) {  //判断是否分配成功
 19         printf("空间分配失败 
");
 20         exit(-1);
 21     }
 22 
 23     PNode PTail = PHead;    //链表的末尾节点，初始指向头节点
 24     PTail->Next = NULL;    //最后一个节点指针置为空
 25     printf("请输入节点个数：");
 26     scanf("%d", &len);        //输入节点个数
 27     for (int i = 0; i < len; i++) {
 28 
 29         PNode pNew = (PNode)malloc(sizeof(Node));    //分配一个新节点
 30         if (pNew == NULL) {
 31             printf("分配新节点失败
");
 32             exit(-1);
 33         }
 34         printf("请输入第 %d 个节点的数据：", i + 1);
 35         scanf("%d", &val);    //输入链表节点的数据
 36 
 37         pNew->Element = val;    //把数据赋值给节点数据域
 38         PTail->Next = pNew;    //末尾节点指针指向下一个新节点
 39         pNew->Next = NULL;        //新节点指针指向为空
 40         PTail = pNew;    //将新节点复制给末尾节点
 41     }
 42     printf("创建链表成功
");
 43     return PHead;    //返回头节点
 44 }
 45 
 46 void TraverseList(PNode List) {
 47     PNode P = List->Next;
 48     printf("遍历链表的值为：");
 49     if(P==NULL) printf("链表为空");
 50     while(P!=NULL) {
 51         printf("%d",P->Element);
 52         P=P->Next;
 53     }
 54     printf("
");
 55 }
 56 
 57 PNode FindList(PNode List) {
 58     PNode P = List->Next;
 59     int num = 0;
 60     int val = 0;
 61     printf("请输入要查询的数：");
 62     scanf("%d",&val);
 63     while(P!=NULL && P->Element!=val) {
 64         P=P->Next;
 65         ++num;
 66     }
 67     if(P!=NULL) printf("找到的节点为：%d",num+1);
 68     else printf("找不到该节点");
 69     printf("
");
 70     return P;
 71 }
 72 
 73 void InsertList(PNode List, int pos, int val) {
 74     int position = 0;
 75     PNode P = List;
 76     while(P!=NULL && position<pos-1) {
 77         P = P->Next;
 78         ++position;
 79     }
 80     PNode Tmp = (PNode)malloc(sizeof(Node));
 81     if(Tmp == NULL) {
 82         printf("内存分配失败！");
 83         exit(-1);
 84     }
 85     Tmp->Element = val;
 86     Tmp->Next = P->Next;
 87     P->Next = Tmp;
 88 }
 89 //删除整个链表
 90 void DeleteTheList(PNode List) {
 91     PNode P,Tmp;
 92     P = List->Next;
 93     List->Next = NULL;
 94     while(P!=NULL) {
 95         Tmp = P->Next;
 96         free(P);
 97         P = Tmp;
 98     }
 99     printf("删除链表成功！
");
100 }
101 //删除链表中的元素
102 void DeleteList(PNode List,int pos) {
103     int position = 0;
104     PNode P = List;
105     while(P!=NULL && position<pos-1) {
106         P = P->Next;
107         ++position;
108     }
109     PNode Tmp = P->Next;
110     P->Next = Tmp->Next;
111     free(Tmp);
112     Tmp=NULL;
113 }
114 //主函数
115 int main() {
116     PNode List = CreateList();    //创建一个指针，使其指向新创建的链表的头指针
117     TraverseList(List);
118     FindList(List);
119     InsertList(List,3,100);
120     TraverseList(List);
121     DeleteList(List,3);
122     TraverseList(List);
123     DeleteTheList(List);
124     TraverseList(List);
125     return 0;
126 }

系统为所有指针均分配4个字节的空间，然后通过不同类型的寻址方式得到变量：

https://blog.csdn.net/boy_of_god/article/details/80868727