数据结构之链表

链表

定义

链表是由一系列不必在内存中相连的结构组成。每一个结构均含有表元素和指向下一个表结构的指针。
使用链表时，留出一个标志节点，表示表头或者哑节点。

单链表

实现代码

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <string.h>
  4 struct Node;
  5 typedef struct Node *PtrToNode;
  6 typedef PtrToNode List;
  7 typedef PtrToNode Position;
  8 
  9 
 10 
 11 typedef struct Node
 12 {
 13     int Element;
 14     Position Next;
 15 }Node;
 16 
 17 //初始化
 18 void initList(Node **pnode)
 19 {
 20     *pnode = NULL;
 21     printf("初始化链表
");
 22 }
 23 
 24 //创建链表
 25 Node * creatList(Node *pHead)
 26 {
 27     Node *p1;
 28     Node *p2;
 29 
 30     p1 = p2 = (Node *)malloc(sizeof(Node));//申请新节点
 31     memset(p1, 0, sizeof( Node));
 32 
 33     scanf_s("%d", &p1->Element);//输入新节点
 34     p1->Next = NULL;//新节点得指针置未空
 35     while(p1->Element>0)
 36     {
 37         if(pHead==NULL)
 38         {
 39             pHead = p1;
 40         }
 41         else
 42         {
 43             p2->Next = p1;
 44         }
 45         p2 = p1;//将怕p1的地址赋值给p2
 46         p1 = (Node *)malloc(sizeof(struct Node));
 47         memset(p1, 0, sizeof(struct Node));
 48         scanf_s("%d", &p1->Element);
 49         p1->Next = NULL;
 50     }
 51     printf("链表创建成功！");
 52     return pHead;//返回链表头指针
 53 }
 54 
 55 //输出链表
 56 void printList(struct Node * pHead)
 57 {
 58     if(NULL==pHead)
 59     {
 60         printf("链表为空！");
 61     }
 62     else
 63     {
 64         while(NULL!=pHead)
 65         {
 66             printf("%d ", pHead->Element);
 67             pHead = pHead->Next;
 68         }
 69         printf("
");
 70     }
 71 }
 72 
 73 //插入一个节点
 74 void insertList(int i,struct Node *pHead,int sum)
 75 {
 76     struct Node * temp;
 77     temp=(Node *)malloc(sizeof(Node));//申请新的临时节点
 78     temp->Element = sum;
 79     for(;i>0;i--)
 80     {
 81         pHead = pHead->Next;
 82     }
 83     temp->Next = pHead->Next;
 84     pHead->Next = temp;
 85     printf("插入完成！");
 86 }
 87  
 88 //删除
 89 void deleteList(int sum,struct Node *pHead)
 90 {
 91     while(pHead->Next!=NULL&&pHead->Next->Element!=sum)
 92     {
 93         pHead = pHead->Next;
 94     }
 95     pHead->Next = pHead->Next->Next;
 96 }
 97 
 98 
 99 void main()
100 {
101      Node *pList=NULL;
102     int length = 0;
103  
104     initList(&pList);       //链表初始化
105     printList(pList);       //遍历链表，打印链表
106  
107     pList=creatList(pList); //创建链表
108     printList(pList);
109 
110     insertList(2, pList, 100);
111      printList(pList);
112 
113      deleteList(100, pList);
114       printList(pList);
115     scanf_s("%d");
116 }

注意：创建未被声明过的记录的唯一方法使用malloc库函数。malloc库函数创建一个新的结构并返回一个指向新结构的指针。

数据结构之链表

链表

定义

单链表

实现代码

双链表

循环链表