1：顺序存储实现(数组实现)
Data： a1 a2 .....ai ai+1 .... an ....
typedef struct LNode *List; //指向LNode的指针，这是typedef的，你可以随时声明，而不加typedef只是创建一个
struct LNode{ //结构体成员ElementType Data[MAXSIZE]; //数组int Last;
};
struct LNode L; //声明实例
List PtrL; //声明PtrL指针变量访问第i个元素：L.Data[i]或者Ptr->Data[i]
线性表长度：L.Last+1或者PtrL->Last+1
1>初始化
List MakeEmpty() //返回List指针
{List Ptrl;Ptrl = (List)malloc(sizeof(struct LNode)); //动态创建LNode，需要指向该结构的指针Ptrl->Last = -1; //通常通过判断或者使得Last = -1，来使得一个新的空链表时初始化return Ptrl;
}2>查找
int Find(ElementType X, List PtrL)
{int i = 0;while(i <= PtrL->Last && PtrL -> Data[i] != X) //Last 是链表中最后一个元素的索引而不是元素个数，因为结构体中的Last声明过i++;if(i > PtrL -> Last)return -1;else return i;}3>插入
先移动、再插入，比如在i位置插入x元素，要把i-1后面的元素全部向右移动一位
void Insert(ElementType X,int i,List Ptrl)
{int j;if(PtrL -> Last == MAXSIZE -1){print("表满");return;}if(i < 1 || i > PtrL ->Last + 2){printf("位置不合法");return;}for(j = Ptrl -> Last;j >= i-1;j- -)PtrL -> Data[j+1] = PrL -> Data[j]; //循环把j位置的元素给到j+1位置的元素PtrL -> Data[i-1] = X; //把i-1位置的元素替换成XPtrL -> Last++; //Last+1return
}4>删除
先删除、再移动
void Delete(int i ,List PtrL)
{int j;if(i < 1 || i > PtrL -> Last + 1){printf("不存在第%d个元素",i);return;}for(j=i ; j <= PtrL -> Last; j++)PtrL-> Data[j-1] = PtrL -> Data[j]; //循环把i+1位置的元素向左移动PtrL -> Last- -;return;
}2：链式存储实现
不要求逻辑相邻的两个元素物理上也相邻，通过“链”建立起元素上的逻辑关系
它的元素定义如下：它不再使用数组和int类型的末尾元素，而是Data和Next
typedef struct LNode *List;
struct LNode{ElementType Data;List Next;
};
struct LNode L;
List PtrL;链表由多个这样的“元素”连接而成，PtrL是指向该元素的指针，Next是指向下一个元素的指针，简单来说，Ptrl就是头指针，Next是尾指针
1>求表长
int Lenth(List PtrL) //只知道链表的头指针，单向链表
{List p = PtrL; //临时指针P指向链表头int j = 0;while(p){ //p指针不结束p = p -> Next; //指向下一个j++;}return j;
}2>查找
按序号查找：FindKth; (查找位于第K号的元素)
List FindKth(int K,List PtrL)
{
List p = PtrL;
int i = 1;while(p != NULL && i < K){p = p-> Next;i++;}if(i == K) return p; //找到第K个，返回指针else return NULL; //没找到返回空
}3->插入
①s指向新节点
②p指向链表的第i-1个节点
找到修改指针，插入节点
③把s指针赋给p指针的下一位，p -> Next = s;
④把p的下一位赋值给s的下一位
List Insert(ElementaType X ,int i , List PtrL) //在i位置插入元素X
{List p ,s; //两个临时指针p,sif(i == 1）{ //如果在表头插入s = (List)malloc(sizeof(struct LNode)); //(List) 将 malloc 返回的指针转换为 List 类型的指针,指向struct的指针s -> Data = X;s -> Next = PtrL; // 把原来的头指针给新元素的尾指针return s;}p = FindKth(i-1 , PtrL); //查找位于i-1位置的元素，把指向该位置的指针赋值给pif(p == NULL){printf("参数i错误");return NULL;}else{s = (List)malloc(sizeof(struct LNode)); s -> Data = X; s -> Next = p -> Next; //s是新元素p -> Next = s;return PtrL;
}4->删除
①找到i-1个节点，用p指向
②用s指向要被删除的节点(p的next)
③修改指针，删除s指向节点
④释放s空间
List Delete(int i ,List PtrL)
{List s, p;if( i == 1){s = PtrL;if(PtrL != NULL) PtrL = PtrL -> Next //从链表中删除selse return NULL;free(s); //释放s空间return PtrL;}p = FindKth(i-1 , PtrL); //查找i-1个节点if(p = = NULL){printf("第%d个节点不存在",i-1);return NULL;}else if( p -> Next == NULL){printf("第%d个节点不存在",i);return NULL;}else{s = p -> Next;p -> Next = s -> Next;free(s);return PtrL;
}
