2023-03-25 单链表LinkList的基本操作

  1 #include <stdio.h>
  2 #include <stdbool.h>
  3 #include <malloc.h>
  4 typedef struct LNode
  5 {
  6     int data;
  7     struct LNode *next;
  8 }LNode,*LinkList;//相当于typedef struct LNode *LinkList;   LinkList a相当于struct LNode a
  9 
 10 bool initlist(LinkList L)//初始化单链表
 11 {
 12     L=NULL;//赋为空表
 13     return true;
 14 }
 15 
 16 LNode *GetElem(LinkList L,int i)//按位查找结点
 17 {
 18     LNode *p;//存放最后返回的结点
 19     p=L->next;//先从第一个结点开始遍历
 20     if(i==0)
 21     {
 22         return L;//第零个节点是头指针？头结点是第一个结点？
 23     }
 24     if(i<1)
 25     {
 26         return NULL;
 27     }
 28     int j=1;//此时p在第一个结点处
 29     while(p!=NULL && j<i)
 30     {
 31         p=p->next;//第一次循环，p遍历到第二个结点
 32         j++;
 33     }
 34     return p;//返回p结点
 35 }
 36 
 37 LinkList List_HeadInsert(LinkList L)//头插法，最后插入的元素在第一个位置
 38 {
 39     L = (LNode *)malloc(sizeof(LNode));
 40     L->next = NULL;//易忽略，头结点插入时要先将最后一个结点的next设为空
 41     int value;//结点的值即data
 42     scanf("%d",&value);
 43     LNode *s;
 44     while(value!=9999)
 45     {
 46         s=(LNode *)malloc(sizeof(LNode));//每次都拓展一个LNode大小的内存，并将开头地址强制转换为LNode*类型并赋值给s
 47         s->data = value;
 48         s->next = L->next;
 49         L->next = s;
 50         scanf("%d",&value);
 51     }
 52     return L;//返回单链表的头指针
 53 }
 54 
 55 LinkList List_TailInsert(LinkList L)//尾插法,在表的末尾进行插入
 56 {
 57     int value;
 58     L=(LinkList)malloc(sizeof(LNode));
 59     LNode *s;//要插入的节点
 60     LNode *e=L;//表尾的节点
 61     scanf("%d",&value);
 62     while(value!=9999)
 63     {
 64         s=(LNode *)malloc(sizeof(LNode));//为插入节点扩充空间
 65         s->data=value;
 66         e->next=s;//此时e为未插入s前，L的表尾，将e的下一个节点指向s
 67         e=s;//此时s是最后一个节点，所以让e指向s的地址
 68         scanf("%d",&value);
 69     }
 70     e->next = NULL;//将下一个节点设为空
 71     return L;
 72 }
 73 
 74 LNode *LocateElem(LinkList L,int e)//按值来查找结点
 75 {
 76     LNode *s;
 77     s=L->next;//先将s指向第一个结点来进行判断
 78     while(s!=NULL && e!=s->data)//如果s为空节点说明该值不存在，直接return 
 79     {
 80         s=s->next;
 81     }
 82     return s;
 83 }
 84 
 85 void LNode_TailInsert(LinkList L,int i,int e)//后插法（常用），在第i个位置上插入结点,data的值为e
 86 {
 87     LNode *p=GetElem(L,i-1);//返回第i-1个节点,在GetElem中已经判断过插入位置的合法性
 88     LNode *s;//插入的节点,(野指针 指向未知变量)
 89     s=(LNode *)malloc(sizeof(LNode));//为什么不能直接LNode *s，然后进行插入s->data=e，必须要用malloc分配空间吗？->刚开始s指向的是一个未知变量是一个野指针，通过malloc来获取一个LNode大小的内存并让s指针指向他来完成指针的初始化，malloc相当于创建了只有一个元素的数组
 90     s->next=p->next;
 91     p->next=s;
 92     s->data=e;
 93 }
 94 
 95 void LNode_HeadInsert(LinkList L,int i,int e)//头插法，转换为后插法进行插入，将data值进行调换即可
 96 {
 97     LNode *p=GetElem(L,i);
 98     LNode *s;
 99     s=(LNode *)malloc(sizeof(LNode));
100     s->data=e;
101     s->next=p->next;
102     p->next=s;
103     int temp=p->data;
104     p->data=s->data;
105     s->data=temp;
106 }
107 
108 void DeleteLNode(LinkList L,int i)//删除节点操作
109 {
110     LNode *p;
111     p=GetElem(L,i-1);//获取删除节点的前一个节点的地址
112     LNode *q;
113     q=p->next;//被删除的节点
114     p->next=q->next;
115     free(q);
116 }
117 
118 int LinkList_length(LinkList L)//计算单链表长度
119 {
120     LNode *p;
121     p=L->next;
122     int sum=0;
123     while(p!=NULL)
124     {
125         sum++;
126         p=p->next;   
127     }
128     return sum;
129 }
130 
131 int main()
132 {
133     LinkList L;//L即头指针
134     
135     initlist(L);
136     //printf("%p",L);//此时输出00400080
137     //L = List_HeadInsert(L);//为什么要进行赋值操作，L是指针，函数不是在地址上对其进行修改的吗？->指针发生了改变？L的指向改变了?
138     //printf("%p",L);//此时输出00B71988，如果不进行赋值操作，输出的仍然是00400080，指针指向的地址没有改变，L的本质也是个变量，只有地址才是不会变的
139     L=List_TailInsert(L);
140     //int e;
141     //e=GetElem(L,3)->data;
142    // LNode *p;
143     //p=LocateElem(L,666);
144     //printf("%d",p->data);
145     //printf("%d",e);
146 
147     //LNode_HeadInsert(L,3,6666);
148 
149     //DeleteLNode(L,3);
150     printf("%d",LinkList_length(L));
151 
152     return 0;
153 }