线性表
动态分配的顺序存储结构
//动态分配空间的顺序存储结构的线性表
#include<stdio.h>
#include<stdlib.h>
#define Linitesize 100
#define Laddsize 10
#define OK 1
#define error 0
typedef int Status;
typedef int Elemtype;
typedef struct{
Elemtype * elem;
int length;
int listsize;
}SqList;
void Show(SqList L)
{
int i;
for(i=0;i<L.length ;i++)
printf("%d ",L.elem[i]);
printf("n");
return ;
}
Status Create(SqList &L)
{
L.elem = (Elemtype *)malloc(Linitesize*sizeof(Elemtype));
if(!(L.elem ))
return error;
L.length = 0;
L.listsize = Linitesize;
return OK;
}
//在第i个元素之前插入 ,从1开始计数,就是下标为i
Status Insert(SqList &L,int i,Elemtype e)
{
int j;
if(i<1||i>L.length+1 )
return error;
if(L.length>=L.listsize)
{
L.elem =(Elemtype *)realloc(L.elem ,(L.listsize + Laddsize)*sizeof(Elemtype));
if(!(L.elem ))
return error;
L.listsize = L.listsize + Laddsize;
}
for(j=L.length-1 ;j>=i-1;j--)
L.elem[j+1] = L.elem[j];
L.elem[i-1] = e;
L.length ++;
return OK;
}
//i为你想要删除的第几个元素
Status Delete(SqList &L,int i,Elemtype &e)
{
int j;
if(i<1||i>L.length )
return error;
e = L.elem[i-1];
for(j=i-1;j<L.length-1;j++)
L.elem[j] = L.elem[j+1];
L.length --;
return OK;
}
int main()
{
int i,j;
Elemtype e;
SqList L;
Create(L);
for(i=1;i<=5;i++)
Insert(L,i,i*i);
printf("输出具体数据:n");
Show(L);
printf("请输入你想要删除第几个元素:n");
scanf("%d",&j);
Delete(L,j,e);
printf("删除的数据是:%d n",e);
Show(L);
return 0;
}
void Merge(Sqlist la,Sqlist lb,Sqlist &lc)
//目标,将原本有序递增的la,pb顺序表整合到lc ,lc认为有序递增的
{
pa = la.elem;
pb = la.elem;
lc.listsize = lc.length = la.length + lb.length;
pc =lc.elem = (ElemType *)malloc(lc.listsize*(sizeof(ElemType)));
if(!lc.elem)
exit OVERFLOW;
pa_last = pa + la.length-1;
pb_last = pb + lb.length-1;
while(pa<=pa_last&&pb<=pb_last)
{
if(*pa<*pb) *pc++ = *pa++;
else *pc++ = *pb++;
}
while(pa<=pa_last) *pc++ = *pa++;
while(pb<=pb_last) *pc++ = *pb++;
}
顺序表优点与缺点
:
链式存储
//动态分配空间的顺序存储结构的线性表
#include<stdio.h>
#include<stdlib.h>
#define Linitesize 100
#define Laddsize 10
#define OK 1
#define error 0
typedef int Status;
typedef int Elemtype;
typedef struct LNode{
struct LNode * next;
Elemtype data;
}LNode,*LinkList;
int Length(LinkList L)
{
int sum=0;
while(L->next !=NULL)
{
sum++;
L=L->next ;
}
return sum;
}
//尾插法
Status Create(LinkList &L,Elemtype e)
{
LinkList p = L;//开始p 指向头结点
while(p->next !=NULL )//找到最后一个结点
p=p->next ;
LinkList temp = (LNode *)malloc(sizeof(Elemtype));
if(!temp) return error;
temp->data = e;
//由于p 指向最后一个结点,那么p->next 进行赋值,实际上会改变原来的数据
temp->next = p->next ;
p->next = temp;
return OK;
}
Status Show(LinkList L)
{
LinkList p = L->next ;
while(p !=NULL)
{
printf("%d ",p->data );
p = p->next ;
}
printf("n");
return OK;
}
//在第i 个元素之前插入 ,确保不超过范围
Status Insert(LinkList &L,int i,Elemtype e)
{
if(i<1||i>Length(L)+1)
return error;
LinkList p = L;//指向头结点
//找到第i-1个结点
int j ;
for(j=1;j<i;j++)
p = p->next ;
LinkList temp = (LNode * )malloc(sizeof(LNode));
if(!temp) return error;
temp->data = e;
temp->next = p->next ;
p->next = temp;
return OK;
}
Status Delete(LinkList &L,int i,Elemtype &e)
{
//删除第i 个元素,并返回其值
if(i<1||i>Length(L))
return error;
//找到第i-1个结点
int j;
LinkList temp = L;
for(j=1;j<i;j++)
temp = temp->next ;
e = temp->next->data;
temp->next = temp->next->next;
return OK;
}
int main()
{
Elemtype e;
LinkList L = (LNode *)malloc(sizeof(LNode));
L->next = NULL;
for(int i = 1;i<= 5;i++)
Create(L,i);
Show(L);
Insert(L,2,10);
Show(L);
Delete(L,3,e);
Show(L);
printf("%d n",e);
return 0;
}
应用
:
优点以及缺点
栈与队列
栈
- 表尾是栈顶,表头是栈底
顺序栈
#include<stdio.h>
#include<stdlib.h>
#define initsize 100
#define addsize 50
#define OK 1
#define error 0
typedef int Status;
typedef int Elemtype;
typedef struct{
Elemtype *base,*top;
int stacksize;
}SqStack;
Status Init(SqStack &S)
{
S.base =(Elemtype *)malloc(initsize*sizeof(Elemtype ));
if(!S.base )
return error;
S.top = S.base ;//说明此时栈为空
S.stacksize = initsize;
return OK;
}
Status Push(SqStack &S,Elemtype e)
{
if(S.top -S.base >=S.stacksize )//栈满
{
S.base =(Elemtype *)realloc(S.base ,(initsize + addsize)*sizeof(Elemtype));
if(!S.base)
return error;
}
*(S.top ) = e;
S.top ++;
return OK;
}
Status Pop(SqStack &S,Elemtype &e)
{
if(S.base == S.top )
return error;//栈为空
S.top --;
e = *(S.top );
return OK;
}
int main()
{
int n,i;
Elemtype e;
SqStack S;
Init(S);
printf("请输入你想要入栈的元素的个数:n");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
printf("请输入你要入栈的元素:");
scanf("%d",&e);
Push(S,e);
}
printf("出栈 n");
for(i=1;i<=n;i++)
{
Pop(S,e);
printf("%d ",e);
}
return 0;
}
链栈
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define Error 0
typedef int Status;
typedef int Elemtype;
typedef struct Node {
Elemtype data;
struct Node * next;
}Node,*ListStack;
Status InitStack(ListStack &S)
{
S =(ListStack )malloc(sizeof(Node));
if(!S) return Error;
S->next = NULL ;
return OK;
}
Status Pop(ListStack &S,Elemtype &e)
{
if(S->next ==NULL)//栈为空
return Error;
ListStack p = S->next ;
e = p->data ;
S->next = p->next ;
free(p);
return OK;
}
Status Push(ListStack &S,Elemtype e)
{
ListStack p =(ListStack )malloc(sizeof(Node));
if(!p) return Error;
p->data = e;
p->next = S->next ;
S->next = p;
return OK;
}
int main()
{
ListStack S;
Elemtype e;
int i;
InitStack(S);
printf("请输入想要进栈的6个数据:n");
for(i=1;i<=6;i++)
{
scanf("%d",&e);
Push(S,e);
}
printf("依次出栈:n");
for(i=1;i<=6;i++)
{
Pop(S,e);
printf("%d ",e);
}
return 0;
}
队列
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define Error 0
typedef int Status ;
typedef int Elemtype;
typedef struct QNode{
Elemtype data ;
struct QNode * next;
}QNode,*QueuePtr;
typedef struct{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
Status InitQueue(LinkQueue &Q)
{
QNode * p=(QNode *)malloc(sizeof(QNode));//头结点
if(!p) return Error;
p->next =NULL;
Q.front =Q.rear =p;
return OK;
}
Status Push(LinkQueue &Q,Elemtype e)
{
QNode * p=(QNode *)malloc(sizeof(QNode));
if(!p) return Error;
p->data =e;
p->next = Q.rear ->next;
Q.rear ->next = p;
Q.rear = p ;
return OK;
}
Status Pop(LinkQueue &Q,Elemtype &e)
{
if(Q.front ==Q.rear )//队列为空
return Error;
QNode * p ;
p = Q.front ->next;
e = p->data;
Q.front ->next = p->next ;
if(Q.rear == p)
Q.rear = Q.front ;
free(p);
return OK;
}
int main()
{
LinkQueue Q;
Elemtype e;
printf("创建带有头结点的链队列n");
InitQueue(Q);
printf("请输入5个你想要依次入队列的数字n");
for(int i=1;i<=5;i++)
{
scanf("%d",&e);
Push(Q,e);
}
printf("依次出队列n");
for(int i=1;i<=5;i++)
{
Pop(Q,e);
printf("%d ",e);
}
return 0;
}
原文地址:https://blog.csdn.net/weixin_74850661/article/details/134610275
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_22006.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。