/*
* 构造一个链式存储的线性表(当输入9999时，结束构造过程)，然后输出该线性表
* 并统计该线性链表的长度 。
*注：new和delete是C++的运算符
malloc和free是C++/C的标准库函数
*/
#include<stdio.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
//单链表的存储结构
struct LinkNode{
int data; //节点的数据域
struct LinkNode *next; //节点的指针域
};
//1.打印输出，链表的数据，其中链表指向头节点
void print(LinkNode *L){
LinkNode *p; //定义一个指针变量p
p = L->next; //使p指向链表L的第一个数据
while(p != 0){
printf("%d、",p->data);
p = p->next; //指针后移
}
printf("\n"); //换行
}
//2.链表长度
int Length_LinkList(LinkNode *L){
LinkNode *p; //定义一个指针变量
int len = 0; // 定义一个计数器，计算节点个数
p = L->next; //指针P指向链表的第一个节点
while(p != NULL){
len++ ;
p = p->next; //指针后移，即指向当前节点的后继节点
}
return len; //返回链表长度
}
//3.按位置查找，单链表中寻找第i个元素，返回指向第i个节点的指针
LinkNode* FindI_LinkNode(LinkNode *L,int i){
LinkNode *p; //定义指针变量
int j = 1; //定义计数器
p = L->next; //让p指向头节点
while(j < i){ //当没有找到第i个节点
p = p->next; //指针后移
j++; //计数器加一
}
return p;
}
//4.按值查找，单链表中寻找元素e，返回元素e所在的位置
int FindE_LinkNode(LinkNode* L,int e){
LinkNode *p;
int count=0;
p=L->next;
while(p != NULL)
{
count++;
if(p->data==e)
return (count);
p=p->next;
}
return 0;
}
//5.在表头插入数据
int Insert_head(LinkNode* &L,int x){
//在以H为头节点的单链表中在头节点后插入数据
LinkNode *t; //定义指针
t = new LinkNode; //申请空间
t->data = x; //向新节点中写入数据
t->next = L->next; //把链表的第一个节点的地址写入到新节点中，也就是新节点的指针域置为null
L->next = t; //让头节点的next指针指向新节点 ，把新节点接到链表上
return OK;
}
//6.在表尾插入数据
int Insert_end(LinkNode *L,int x){
LinkNode *t;
t = new LinkNode; //申请空间
t->data = x; //把数据赋到新节点的数据域
while(L->next != NULL){//当链表不为空时，指针向后移动，因为数据要插入最后一个位置
L = L->next; //指针向后移动
} //直到指针移到最后一个
L->next = t; //将链表末尾节点的下一节点指向新节点
t->next = NULL; //新节点的指针域置空
return OK;
}
//7.在第i个位置插入数据
int Insert_LinkNode(LinkNode *L,int i,int x){
if(i < 1 || i > Length_LinkList(L)){
printf("插入位置错误!\n");
return ERROR;
}
LinkNode *p;
if(i == 1)
p = L; //指针P指向头节点
else
p = FindI_LinkNode(L,i-1); //让P指向第i-1个节点
Insert_head(p,x); //将x插入假设以p节点为头节点的链表中
return OK;
}
//8.删除首元节点
int Del_Head(LinkNode *L){
if(L->next != NULL){
LinkNode *p; //定义一个指针变量
p = L->next; //指针p指向第一个节点，p->next指向下一个节点
L->next = p->next; //头节点的指针域存储第二个节点的地址
delete p; //删除第一个节点，释放空间
}else{
printf("空表！\n");
return FALSE;
}
}
//9.删除表尾节点
int Del_End(LinkNode *L){
if(L->next != NULL){
LinkNode *p;
LinkNode *q;
int i;
p = L->next; //指针p指向第一个节点
for(i = 1;i < Length_LinkList(L) - 1;i++){
p = p->next;
}
q = p->next;
p->next = NULL;
//free(q);
delete q;
}else{
printf("空表！");
}
}
//10.删除指定位置上的元素
int Del_i(LinkNode* L,int i){
if(i<1 || i>Length_LinkList(L))//如果删除位置不合法
{
printf("删除位置不合法!");
return 0;
}
LinkNode *p;
if(i==1)
p=L; //让p指向头结点
else
p=FindI_LinkNode(L,i-1); //让p指向第i-1个结点
Del_Head(p); //删除以p为头结点的链表的第一个数据结点
return OK;
}
/*
* 在主函数中传递参数，传参分为值传递和址传递，
*/
int main(){
int i,x,count,m;
LinkNode *H; //定义链表指针
LinkNode *add;
H = new LinkNode; //申请空间
//H->data = -1; //为成员变量数据赋值
H->next = NULL; //为成员变量指针赋值
printf("输入数据：\n");
while(1){
scanf("%d",&i);
if(i == 9999){
break;
}else{
Insert_end(H,i); //插入数据
}
}
printf("The LinkNode elem is:");
print(H); //输出数据
printf("1.请输入从表头插入的数据：");
scanf("%d",&i);
Insert_head(H,i);
printf("The LinkNode elem is:");
print(H);
printf("2.请输入从表尾插入的数据：");
scanf("%d",&i);
Insert_end(H,i);
printf("The LinkNode elem is:");
print(H);
printf("3.请输入要插入的位置、数据（空格隔开）：\n");//判断输出的插入位置是否合法
scanf("%d %d",&i,&x);
Insert_LinkNode(H,i,x);
printf("The LinkNode elem is:");
print(H);
printf("4.请输入要查询的位置：");
scanf("%d",&i);
if(i < 1 || i > Length_LinkList(H)){ //若查询位置不合法，返回error
printf("查询位置不合法!\n");
}else{
add = FindI_LinkNode(H,i);
int e = add->data;
printf("位置：%d的数据是：%d\n",i,e);
}
printf("4.请输入要查询的元素：\n");
scanf("%d",&i);
m = FindE_LinkNode(H,i);
if(m == 0){
printf("查无此元素!\n");
}else{
printf("数据：%d所在的位置是：%d\n",i,m);
}
Del_Head(H);
printf("5.删除首元节点后：\nThe LinkNode elem is:");
print(H);
Del_End(H);
printf("6.删除表尾节点后：\nThe LinkNode elem is:");
print(H);
printf("7.指定删除节点的位置：\n");
scanf("%d",&i);
if(i < 1 || i > Length_LinkList(H)){ //若查询位置不合法，返回error
printf("指定位置不合法!\n");
}else{
Del_i(H,i);
printf("6.删除指定节点后：\nThe LinkNode elem is:");
print(H);
}
count = Length_LinkList(H);
printf("8.此链表长度为：%d\n",count);
return 0;
}
