在两种存储结构下实现线性表的创建,插入,删除,按值查找

Question

如题所述

Answer 1

一、使用线性表的链式存储结构实现
#include <stdio.h>
#include <stdlib.h>

typedef struct LNode{
int data; //链表数据
struct LNode* next; //链表指针
}LNode,*LinkList;

/*头插法-建立单链表*/
LinkList HeadCreate(LinkList la)
{
int num;
la=(LinkList)malloc(sizeof(LNode)); //建立头结点
la->next=NULL;
scanf("%d",&num);
while(num!=10)
{
LNode *p=(LinkList)malloc(sizeof(LNode));
p->data=num;
p->next=la->next;
la->next=p;
scanf("%d",&num);
}
return la;
}

/*尾插法-建立单链表*/
LinkList TailCreate(LinkList la)
{
int num;
la=(LinkList)malloc(sizeof(LNode));
la->next=NULL;
LinkList s,r=la;
scanf("%d",&num);
while(num!=10)
{
s=(LinkList)malloc(sizeof(LNode));
s->data=num;
r->next=s;
r=s;
scanf("%d",num);
}
r->next=NULL;
return la;
}

/*单链表遍历*/
void TravelList(LinkList la)
{
LinkList p=la->next;
while(p!=NULL)
{
printf("%d->",p->data);
p=p->next;
}
printf("\n");
}

/*单链表的按位查找*/
LinkList GetElem(LinkList la,int i)
{
int j=1;
LNode* p=la->next;
if(i<1)
return NULL;
while(p && j<i)
{
p=p->next;
j++;
}
return p;
}

/*单链表的按值查找*/
LinkList LocalElem(LinkList la,int e)
{
LNode* p=la->next;
while(p!=NULL && p->data!=e)
p=p->next;
return p;
}

/*单链表插入操作*/
bool InsertList(LinkList la,int i,int e)
{
//在la链表中的i位置插入数值e
int j=1;
LinkList p=la,s;
while(p && j<i)
{
p=p->next;
j++;
}
if(p==NULL)
return false;
if((s=(LinkList)malloc(sizeof(LNode)))==NULL)
return false;
s->data=e;
s->next=p->next;
p->next=s;
return true;
}

/*单链表删除操作*/
bool DeleteList(LinkList la,int i)
{
int j=1;
LinkList p=la,q;
while(p && j<i) //p指向第i-1个元素
{
p=p->next;
j++;
}
if(p==NULL || p->next==NULL) //表示不存在第i-1个和第i的元素
return false;
q=p->next;
p->next=q->next;
free(q);
return true;
}

/*单链表的表长*/
int LengthList(LinkList la)
{
int nLen=0;
LinkList p=la->next;
while(p)
{
p=p->next;
nLen++;
}
return nLen;
}

/*单链表逆置*/
LinkList Reserve(LinkList la)
{
if(la==NULL || la->next==NULL)
return la;
LinkList p=la->next,q=p->next,r=q->next;
la->next=NULL;
p->next=NULL;
while(r!=NULL)
{
q->next=p;
p=q;
q=r;
r=r->next;
}
q->next=p;
la->next=q;
return la;
}

int main()
{
LNode la;
LinkList p;
p=HeadCreate(&la); //头插法创建单链表
TravelList(p);
printf("%p\n",GetElem(p,1)); //获得第1个结点地址
InsertList(p,2,10); //在链表的第2个位置插入元素10
TravelList(p);
DeleteList(p,3); //删除链表的第3个元素
TravelList(p);
printf("%d\n",LengthList(p)); //获得链表长度
p=Reserve(p);
TravelList(p);
return 0;
}

//运行结果
//5 6 12 7 8 14 9 3 2 5 14 10 头插法创建链表
//14->5->2->3->9->14->8->7->12->6->5-> 显示链表
//00382490 第一个结点的地址
//14->10->5->2->3->9->14->8->7->12->6->5-> 插入元素值为10的结点
//14->10->2->3->9->14->8->7->12->6->5-> 删除第三个结点
//11 获得链表长度
//5->6->12->7->8->14->9->3->2->10->14-> 链表逆置
//Press any key to continue

二、使用线性表的顺序存储结构实现
#include<stdio.h>

#define MaxSize 50
struct SqList{
int data[MaxSize]; //存放顺序表的元素
int length; //存放顺序表的长度
};

/*顺序表的插入操作*/
bool InsertList(SqList&L,int i,int e)
{
//在顺序表中第i个位置插入数值e
int j;
if(i<1 || i>L.length)
return false;
if(L.length>MaxSize)
return false;
for(j=L.length;j>=i;j--) //将第i个起得数据后移
L.data[j]=L.data[j-1];
L.data[j]=e;
L.length++;
return true;
}

/*顺序表的删除*/
bool DeleteList(SqList&L,int i)
{
//删除顺序表中第i个元素
int j;
if(i<1 || i>L.length)
return false;
for(j=i;j<L.length;j++)
L.data[j-1]=L.data[j];
L.length--;
return true;
}

/*顺序表的按值查找*/
int LocateElem(SqList&L,int e)
{
for(int i=0;i<L.length;i++)
if(L.data[i]==e)
return i+1;
return 0;
}

/*顺序表的输出*/
void OutPutList(SqList&L)
{
for(int i=0;i<L.length;i++)
printf("%d ",L.data[i]);
printf("\n");
}

int main()
{
SqList list;
int A[5]={1,4,7,2,10};
/*初始化顺序表*/
for(int i=0;i<5;i++)
list.data[i]=A[i];
list.length=5;
OutPutList(list);
InsertList(list,3,12);
OutPutList(list);
DeleteList(list,3);
OutPutList(list);
printf("%d\n",LocateElem(list,10));
return 0;
}

//运行结果
//1 4 7 2 10 创建并输出顺序表
//1 4 12 7 2 10 在3的位置插入值为12的元素
//1 4 7 2 10 删除第三个元素
//5 输出值为10的元素的位置
//Press any key to continue

上面是我用两种存储方式实现线性表的创建、插入、删除和按值查找的功能，还包含一些额外的功能，你可以自己根据我的代码改进，让代码更符合你的要求。希望对你有帮助，呵呵。本回答被提问者采纳