数据结构-链表的代码笔记

  1 //
  2 //  main.cpp
  3 //  链表
  4 //
  5 //  Created by loglian on 2020/4/23.
  6 //  Copyright © 2020 loglian. All rights reserved.
  7 //
  8 
  9 #include <iostream>
 10 #include <stdio.h>
 11 #define MAXSIZE 100
 12 typedef struct LNode *List;
 13 typedef int ElementType;
 14 struct LNode{
 15     ElementType Data;
 16     List Next;  //next为指针
 17 };
 18 struct LNode L;
 19 List Ptrl;
 20 
 21 //求表长   遍历
 22 int length(List Ptrl)//Ptrl头节点
 23 {
 24     List p=Ptrl;    //p指向表的第一个节点
 25     int j=0;
 26     while (p){
 27         p=p->Next;
 28         j++;
 29     }
 30     return j;
 31 }
 32 
 33 
 34 //查找:按序号查找 O(n)
 35 List FindKth(int K,List Ptrl)
 36 {
 37     List p=Ptrl;    //p表头
 38     int i=1;
 39     while ( p!=NULL && i<K )
 40     {
 41         p=p->Next;
 42         i++;
 43     }
 44     if(i==K)return p;
 45     else return NULL;
 46 }
 47 //查找:按值查找
 48 List Find (ElementType X,List Ptrl)
 49 {
 50     List p=Ptrl;
 51     while(p!=NULL && p->Data!=X)       //链表不空
 52         p=p->Next;
 53     return p;
 54 }
 55 
 56 
 57 //插入    平均2/n
 58 //在i-1个结点后插入一个新的x结点 PtrL=Insert(…) 直接返回获得新的头指针
 59 List Insert(ElementType X,int i,List Ptrl)
 60 {
 61     List p,s;
 62     if(i==1)    //新节点插入在表头
 63     {
 64         s=(List)malloc(sizeof(struct LNode));   //申请并填装新结点
 65         s->Data=X;
 66         s->Next=Ptrl;   //s指向第一个结点
 67         return s;   //返回新的头指针
 68     }
 69     p=FindKth(i-1, Ptrl);   //查找第i-1结点
 70     if(p==NULL){
 71         printf("参数i错误");
 72         return NULL;
 73     }else{
 74         s=(List)malloc(sizeof(struct LNode));
 75         s->Data = X;
 76         s->Next = p->Next;  //注意顺序
 77         p->Next = s;
 78         return Ptrl;//返回头指针
 79     }
 80 }
 81 
 82 //删除 平均2/n
 83 
 84 List Delete(int i,List Ptrl)
 85 {
 86     List p,s;
 87     if(i==1)    //删除第一个节点
 88     {
 89         s=Ptrl;
 90         if(Ptrl!=NULL) Ptrl=Ptrl->Next; //ptrl本身为空
 91         else return NULL;
 92         free(s);    //释放被删除的结点
 93         return Ptrl;
 94     }
 95     p=FindKth(i-1, Ptrl);
 96     if(p==NULL)
 97     {printf("第%d个结点不存在",i-1);    return NULL;}
 98     else if(p->Next==NULL)
 99     {printf("第%d个结点不存在",i);    return NULL;}
100     else {
101         s=p->Next;  //s指向第i个结点
102         p->Next=s->Next;    //删除
103         free(s);    //释放删除结点空间
104         return Ptrl;
105     }
106 }