数据结构线性表——链式结构
#include"ls.h"#include<iostream.h>
#include<malloc.h>
#include<stdlib.h>
#include<stdio.h>
int main()
{
LNode *L = NULL;
ElemType i,e;
int c,c_1;
ElemType cur_e,pre_e,next_e;
do
{
cin>>c;
switch(c)
{
case 0:
InitList(L);
break;
case 1:
DestroyList(L);
break;
case 2:
cout<<"你需要查找第几个数据: ";
cin>>i;
if(GetElem(L,i,e) == 1)
cout<<"第"<<i<<"个数据的值为: "<<e<<endl;
break;
/* case 3:
if(ListLength(L))
{
i = ListLength(L);
cout<<"线性表中有"<<i<<"个元素"<<endl;
break;
}
case 4:
cout<<"请输入数据: ";
cin>>cur_e;
if(PriorElem(L,cur_e,pre_e))
cout<<cur_e<<"的前驱为: "<<pre_e<<endl;
break;
case 5:
cout<<"请输入数据: ";
cin>>cur_e;
if(NextElem(L,cur_e,next_e))
cout<<cur_e<<"的后继为: "<<next_e<<endl;
break;*/
case 6:
cout<<"请输入你要插入数据的位置: ";
cin>>i;
cout<<"请输入你要插入数据的值: ";
cin>>e;
if(ListInsert(L,i,e))
cout<<"插入数据元素成功!"<<endl;
break;
case 7:
cout<<"请输入你要删除数据的位置: ";
cin>>i;
if(ListDelete(L,i,e))
cout<<"已经将"<<i<<"位置的"<<e<<"元素成功删除!"<<endl;
break;
case 8:
cout<<"合并线性表需要新建一个线性表，并且会重排列原表，是否合并: "<<endl;
cout<<" 1.是 "<<endl;
cout<<" 2.否"<<endl;
cout<<"请选择: ";
cin>>c_1;
if(c == 0)
break;
else
{
LNode *Lx,*Ly;
InitList(Lx);
cout<<"已建立好新线性表，新线性表与原线性表将合并."<<endl;
MergeList(L,Lx,Ly);
cout<<"合并后的线性表中数据为: "<<endl;
for(LNode *p = Ly->next;p != NULL;p = p->next)
cout<<p->elem<<" ";
cout<<endl;
}
break;
}
getchar();
// getchar();
system("cls");
}while(c != 9);
return 0;
}
#include"ls.h"
#include<iostream.h>
#include<malloc.h>
#include<stdlib.h>
#include<stdio.h>
Status InitList(LNode* &L)
{
//建立链表
LNode *p,*pl;
int a;
L = (struct LNode *)malloc(sizeof(struct LNode));
L->next = NULL; //建立一个空的表头
p = L;
for(;;)
{
pl = (struct LNode *)malloc(sizeof(struct LNode));//创建一个新的节点
printf("请输入元素(输入428结束):"); //判断输入结束
cin>>a;
if(a==428)
break;
pl->elem = a; //给新节点赋值
p->next = pl; //新节点插到头节点后
p = pl;
}
p->next=NULL; //最后一个节点的指针指向空
return OK;
}
Status DestroyList(LNode* &L)
{
//删除链表，即释放表头元素
if(!L)//判断链表是否存在
{
cout<<"输入错误，请重新输入! "<<endl;
return ERROR;
}
free(L);
return OK;
}
Status GetElem(LNode *L,int i,ElemType &e)
{
//用e返回第i个元素的值
LNode *p;
p = L->next; //因为链表带有一个无值的表头，所以从头节点的后一个节点开始判断
int j = 1;
while(p && j < i) //使p跳转到查找元素位置
{
p = p->next;
++j;
}
if(!p || j > i) //当j>i时为未找到元素情况
{
cout<<"输入错误，请重新输入! "<<endl;
return ERROR;
}
e = p->elem;
return OK;
}
Status ListInsert(LNode *L,int i,ElemType e)
{
//在第i个元素之前插入新元素e
LNode *p,*q;
p = L->next;
int j = 0;
while(p && j < i - 2) //使节点p移动到插入位置之前
{
p = p->next;
++j;
}
if(!p || j > i - 2) //判断输入是否有误
{
cout<<"输入错误，请重新输入! "<<endl;
return ERROR;
}
q = (LNode *)malloc(sizeof(LNode)); //新建节点，插入
q->next = p->next;
p->next = q;
q->elem = e;
return OK;
}
Status ListDelete(LNode *L,int i,ElemType &e)
{
//删除制定位置元素，并用e返回其值
LNode *p,*q;
p = L->next;
int j = 0;
while(p->next && j < i - 1)
{
p = p->next;
++j;
}//p移动到删除位置
if(!p->next || j > i - 1)
{
cout<<"输入错误，请重新输入! "<<endl;
return ERROR;
}
q = p->next;
e = q->elem;
p->next = q->next;//删除操作
free(q);//释放无用节点
return OK;
}
void MergeList(LNode* &La,LNode* &Lb,LNode* &Lc)
{
//将两个链表合并
arrange(La);
arrange(Lb);
LNode *pa = La->next;
LNode *pb = Lb->next;
LNode *pc;
Lc = pc = La;
while(pa && pb)
{
if(pa->elem <= pb->elem)
{
pc->next = pa;
pc = pa;
pa = pa->next;
}
else
{
pc->next = pb;
pc = pb;
pb = pb->next;
}
}
pc->next = pa?pa:pb;
free(Lb);
}
#ifndef _FUNC_H
#define _FUNC_H
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef int ElemType;
typedef int Status;
typedef struct LNode
{
ElemType elem;
LNode *next;
}LNode,*LinkList;
Status InitList(LNode* &L);
Status DestroyList(LNode* &L);
Status GetElem(LNode *L,int i,ElemType &e);
Status ListInsert(LNode *L,int i,ElemType e);
Status ListDelete(LNode *L,int i,ElemType &e);
Status arrange(LNode* &L);
void MergeList(LNode* &La,LNode* &Lb,LNode* &Lc);
#endif
求修改，和注释，看不懂
