#include<stdio.h> //printf输出函数和scanf输入函数所在头文件
#include<stdlib.h> //exit退出函数所在头文件
#include<malloc.h> //malloc动态内存分配函数、realloc函数所在的头文件
#include<iostream>
using namespace std;
//用#define宏定义来定义符号常量
//函数结果状态代码
#define TRUE 1
#define FALSE 0
#define ERROR 0
#define OK 1
#define ERROR 0
#define INSEASIBLE -1
#define OVERFLOW -2
//用typedef给类型起别名
typedef int Status; //Status是函数的类型，其值是函数结果状态代码
typedef int ElemType; //本例中链表各个节点中存储int型数据
//————————————线性表的动态分配存储结构————————————————
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
//构造一个线性链表 前插法
void CreateList_L(LinkList &L,int n)
{//逆位序输入n个元素的值，建立带头节点的单链线性表L
L = (LinkList)malloc(sizeof(LNode));//生成新节点做为头节点，用头指针L指向头节点
L->next=NULL;//头节点指针域为空
for(int i=1; i <= n; i++){
printf("请输入第%d个元素值：\n",i);
LinkList p = (LinkList)malloc(sizeof(LNode));
scanf("%d",&p->data);
p->next=L->next;
L->next=p;
}
}
//构造一个线性表 后插法
void CreateList_LL(LinkList &L,int n){
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;
LinkList r=L;
for(int i =1;i<= n; i++){
printf("请输入第%d个元素值：\n",i);
LinkList p =(LinkList)malloc(sizeof(LNode));
scanf("%d",&p->data);
p->next=NULL;
r->next=p;
r=p;
}
}
//返回当前单连表中元素个数
Status ReturnListNumbers(LinkList L){
LinkList p = L->next;
int i=0;
while(p){
p=p->next;
i++;
}
return i;
}
//复杂度为O(n)
//在带头节点的单链表L中第i个位置之前插入新的元素e
Status ListInsert_L(LinkList &L,int i,ElemType e){
LinkList p=L;
int j=0;
while(p&&(j<i-1)){//查找第i-1个节点，p指向该节点
p=p->next;
j++;
}
if(!p||j>i-1) return ERROR;
LinkList s=(LinkList)malloc(sizeof(LNode));
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}
//复杂度为O(n)
//在带头节点的单链表L中删除第i个元素，并用e返回其值
Status ListDelete_L(LinkList &L,int i,ElemType &e)
{
LinkList p=L;
int j=0;
while(p->next&&(j<i-1)){//找到要删除节点的前驱节点即i-1节点
p=p->next;
j++;
}
if(!(p->next)||(j>i-1)) return ERROR;//当i>n或i<1时，删除位置不合理
LinkList q = p->next;
p->next=q->next;
delete q;
return OK;
}
//在带头节点的单链表L中根据序号i取值 ，并用e返回
Status GetElem_L(LinkList &L,int i,int n,ElemType &e){
LinkList p=L->next;
int j=1;
if(i<1||i>n) return ERROR;
while(p&&(j<i)){
j++;
p=p->next;
}
if(!p||j>n) return ERROR;
e = p->data;
return OK;
}
//在带头节点的单链表L中查找值为e的元素
Status LocateElem(LinkList L,int i,ElemType e){
LinkList p=L->next;
int j=1;
while(p&&j<=i){
if(p->data==e){
return j;
break;
}
p=p->next;
j++;
}
if(p==NULL||j==i) return ERROR;
}
————————合并链表————————————
合并L和L1两表 将所有在L1表中但不再L表中的数据元素添加到L中
//void union_L(LinkList &L,LinkList L1,int n,int n1){
// int L_len = n;
// int L1_len = n1;
// ElemType e;
// for(int i =1;i <= L1_len; i++){
// GetElem_L(L1,i,n1,e);
// if(!LocateElem(L,n,e)){
// ListInsert_L(L,L_len+2,e);
// L_len++;
// }
// }
//}
//合并L和L1两表 (不去重),并且将元素按从小到大的顺序排序
void union_LL(LinkList &L,LinkList L1,int n,int n1){
int L_len = n;
int L1_len = n1;
ElemType e;
for(int i = 1; i <=L1_len; i++){
GetElem_L(L1,i,n1,e);
ListInsert_L(L,L_len+2,e);
L_len++;
}
}
//单链表逆序
void reverseLinkList(LinkList &L){
LinkList pPre=NULL;//当前节点的上一个节点
LinkList pCur=NULL;//指向当前节点的指针
LinkList pTmp=NULL;//指向当前节点的下一个节点
if(L==NULL||L->next==NULL||L->next->next==NULL){//如果单链表此时只有一个元素，则返回
return ;
}
pPre = L->next;
pCur = L->next->next;
while(pCur){//遍历链表
pTmp = pCur->next;
pCur->next=pPre;
pPre = pCur;
pCur = pTmp;
}
L->next->next=NULL;
L->next=pPre;
}
//给单链表排序
void Link_sort(LinkList &L)//升序
{
LinkList q;
LinkList p=NULL;
ElemType x;
for(q=L->next;q->next!=NULL;q=q->next)
{
for(p=q->next;p!=NULL;p=p->next)
{
if(q->data>=p->data)
{
x=q->data;
q->data=p->data;
p->data=x;
}
}
}
}
//显示函数，将带头节点的单链线性表L中每个元素逐个显示出来
void ListDisp_L(LinkList L){
printf("\n当前单链表中的数据是：\n");
LinkList p = L->next;
int i=1;
while(p){
printf("单链表的第%d个数是%d\n",i,p->data);
p=p->next;
i++;
}
printf("单链表数据显示完毕！\n");
}
int main(){
while(1){
//——————————初始化单链表——————————
LinkList L,L1;
int n,n1;
printf("即将初始化 L 链表，请输入元素个数：\n");
scanf("%d",&n);
CreateList_L(L,n);//前插法
//CreateList_LL(L,n);//后插法
ListDisp_L(L);
//—————————插入元素——————————————
ElemType y;
int m,t;
printf("请输入要插入多少个数：");
scanf("%d",&t);
while(t--){
printf("请依次输入要插入的 位置 和 要插入的数：");
scanf("%d%d",&m,&y);
ListInsert_L(L,m,y);
}
printf("\n插入后的状态:");
ListDisp_L(L);
//——————————删除元素——————————————
ElemType e;
int x;
printf("请输入要删除的位置：");
scanf("%d",&x);
ListDelete_L(L,x,e);
printf("\n删除后的状态");
ListDisp_L(L);
//——————————单链表的取值————————————
ElemType e1;
int z;
printf("请输入要取的值的位置：");
scanf("%d",&z);
GetElem_L(L,z,n,e1);
printf("位于第%d位置的元素为:%d \n",z,e1);
//——————————单链表的查找————————————
ElemType e2;
int n2 = ReturnListNumbers(L);
printf("请输入要查找的值：");
scanf("%d",&e2);
Status p=LocateElem(L,n2,e2);
if(p)
printf("元素%d存在单链表中!\n",e2);
if(p==0)
printf("元素%d不在单链表中!\n",e2);
printf("\n");
//—————————初始化单链表L1————————————
printf("即将初始化 L1 链表，请输入元素个数：\n");
scanf("%d",&n1);
CreateList_L(L1,n1);
ListDisp_L(L1);
//——————————合并两个单链表（去重）——————————
// printf("\n");
// printf("将L与L1合并后，结果给L后 L 的状态：\n");
// union_L(L,L1,n,n1);
// ListDisp_L(L);
//——————————合并两个单链表(不去重)——————————
printf("将L与L1合并后，结果给L后，L 的状态（不去重）：\n");
union_LL(L,L1,n,n1);
ListDisp_L(L);
//——————————单链表的逆序———————————— ——
printf("\n单链表的逆序：");
reverseLinkList(L);
ListDisp_L(L);
//——————————返回当前单链表中元素个数————————
printf("\n当前单链表中元素个数为：%d\n",ReturnListNumbers(L));
//——————————单链表的排序——————————————
printf("\n将单链表排序");
Link_sort(L);
ListDisp_L(L);
printf("\n\n");
}
return 0;
}
