数据结构-线性表（链式存储）
我与数据结构有个约会，带你领略不一样的数据结构！
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct Lnode{
ElemType data;//数据域
struct Lnode *next; //next是指向自身的节点指针
}Lnode,*Linklist;
//创建-‘头插法’
/*
问题说明：
1.为何一开始归置表头为空，当采用头插法是，最后一个元素为空？
原因：当地一个节点（s）插入的时候，s->next = L->next =NULL,所以第一个节点储存的就是空，由于采用的是头插法，所以第一个节点输出的时候就变成了第二个节点
2.是否可以像‘尾插法’一样采用尾节点置空？
不可以
原因：我们并没有设置尾指针，当采用‘头插法’时，我们并不能找到最后一个元素
*/
Linklist CreatList1(Linklist &L){
int x;
//创建头节点,并初始化
L = (Lnode*)malloc(sizeof(Lnode));
L->next = NULL;
Lnode *s;//不需要初始化
scanf("%d",&x);
while(x!=999){
s=(Lnode*)malloc(sizeof(Lnode));
s->data=x; //中间插入
s->next=L->next;
L->next=s;
scanf("%d",&x);
}
return L;
}
//尾插法
/*
问题说明：
1.‘尾插法’为什么要设置尾指针？
原因：‘尾插法’是插在新节点的后面，所以我们必须要知道前一个节点的指针（位置）
2.‘尾插法'如何让尾节点为空？
原因：插入时，我必须要知道前一个节点的指针；而尾指针是通过新节点的移动而移动
3.为和每个操作都不直接操作头指针？
原因：如果我们直接操作头指针，让头指针随意移动，链表的结构就会被破坏（我们一切的操作都是从头指针开始的，如果头指针的位置不知道，我们便操作不了链表），
所有，我们每次都让一个指针指向头指针，如 s = L。我们直接操作s就可以了。
*/
Linklist CreatList2(Linklist &L){
//创建头结点
int x;
L = (Lnode*)malloc(sizeof(Lnode));
Lnode *s, *r = L;//尾指针初始化
scanf("%d",&x);
while(x!=999){ //自己设置退出条件
s = (Lnode*)malloc(sizeof(Lnode));
s->data =x;
r->next = s;
//移动尾指针
r = s;
scanf("%d",&x);
}
//尾节点置空
r->next = NULL;
return L;
}
//输出
void PrintList(Linklist &L){
Lnode *p = L;
while(p->next!=NULL){
printf("->%d",p->next->data);
p = p->next;
}
}
/*
问题说明：
1.由于链表本身的特性，他的逻辑结构是通过节点的指针连接的，所以不管是按序号，还是按值查找，我们都需要找到上一个节点指针；我们插入节点的实质就是指针的指向重新赋值（这个有点像化学反应：旧件断裂，新键形成）
2.如何找到上一个节点？
我们可以封装一个函数，专门找上一个节点指针。我们需要遍历链表，直到找到用户要寻找的节点。前面也要考虑没有找打的情况
*/
//按序号查找
Linklist LocList(Linklist &L,int n){
Lnode *p = L->next;
int i = 1;
while(p && i<n)
{
p = p->next;
++i;
}
if(!p || i>n){
printf("没有找到");
return false;
}
return p; //如果找到，返回指针
}
//按值查找
int FindList(Linklist &L,int x){
int j = 1;
Lnode *p = L->next;
while(p && p->data!=x){
p = p->next;
++j;
}
if(!p){
return false;
}
return j;
}
//插入节点
/*
问题分析：
1.插入和“头插法”有点像，他们的指针的连接都是同样的原理
2.关于插入指针的顺序问题：
假设我们创建一个节点s，让他插入第i个位置，我们第一步要找到i-1个节点的指针，假设他为p,第i个节点的位置是p->next,那么我们如何插入？
A:p->next = s;s->next = p->next;
这种插入方式我们能发现有什么问题吗？没错，指针p被覆盖，最后的结果就是s->next = s,这样会导致插入失败
那么正确的做法是什么？
B:s->next = p->next;p->next = s;
*/
Linklist InsertList(Linklist &L,int i,int a)//在第i个位置插入a
{
Lnode *p = LocList(L,i-1); //找到i个节点的上一个节点的指针
Lnode *s;
s = (Lnode*)malloc(sizeof(Lnode));
s->data = a;
//开始插入
s->next = p->next;
p->next = s;
return L;
}
//删除节点
Linklist DelList(Linklist &L,int i,int &e){
Lnode *p = LocList(L,i-1);//找到i个节点的上一个节点的指针
//开始删除
Lnode *t;
t = p->next;
p->next = t->next;
e = t->data; //保存删除节点的数据域
free(t);
return L;
}
//摧毁整个链表
Linklist DelallList(Linklist &L){
Lnode *p = L->next;
Lnode *t;
while(p){
t = p->next;
free(p);
p = t;
}
L->next = NULL;
return L;
}
void main(){
//Lnode *res;
int res;
Linklist l;
CreatList2(l);
PrintList(l);
printf("\n");
/*
res = LocList(l,3);
printf("%d",res->data);
*/
//res=FindList(l,2);
//printf("%d",res);
//InsertList(l,2,5);
//int e=0;
//DelList(l,2,e);
DelallList(l);
PrintList(l);
system("pause");
}
