线性表、堆栈、队列的特点，及代码实现（C语音）

ゝ一世哀愁。 2022-07-03 13:55 119阅读 0赞

一、线性表：

线性表定义：线性表是n个数据元素的有限序列

线性表有多种实现方式，线性、链式等，其中线性实现采用随机存储的方式：

![Image 1][]**（线性）**

![Image 1][]**（链式）**

**具体的说明大家可以看书对吧，这里直接贴出实现C语言代码（下面是链式存储实现）：**

#include<stdio.h> #include<malloc.h> #include<stdlib.h> typedef struct node { int data; struct node *next; }node,*linklist; //初始化 void initlist(linklist &head) { head=(node*)malloc(sizeof(node)); head->next=NULL; } //输入 void getlist(linklist &head,linklist &p,linklist &q) { int i,num;//输入数据个数 p=head; printf("请输入数据个数："); scanf("%d",&num); for(i=1;i<=num;i++) { q=(node*)malloc(sizeof(node)); printf("请输入要存储的第%d数：",i); scanf("%d",&q->data); p->next=q; q->next=NULL; p=p->next; } } //输出 void output(linklist &head,linklist &s) { for(s=head->next;s!=NULL;s=s->next) printf("%d ",s->data); printf("\n"); } //插入 void insertlist(linklist &head,linklist &p,linklist &s,linklist &q) { int flag=1,insflag;//插入的位置 p=head; printf("请输入您要插入的位置："); scanf("%d",&insflag); while(p->next!=NULL) { flag++; p=p->next; } p=head; while(insflag<=0||insflag>flag) { printf("您的输入错误！\n请重新输入有效位置："); scanf("%d",&insflag); } for(flag=1;flag<=insflag-1;flag++) { p=p->next; } q=(node*)malloc(sizeof(node)); printf("请输入您要插入的数："); scanf("%d",&q->data); q->next=p->next; p->next=q; output(head,s); } //删除 void dellist(linklist &head,linklist &p,linklist &s) { int flag=1,delflag;//删除的位置 p=head; printf("请输入您要删除的位置："); scanf("%d",&delflag); while(p->next!=NULL) { flag++; p=p->next; } p=head; while(delflag<=0||delflag>flag) { printf("您的输入错误！\n请重新输入有效位置："); scanf("%d",&delflag); } for(flag=1;flag<=delflag-1;flag++) { p=p->next; } p->next=p->next->next; output(head,s); } //查找 void foundlist(linklist &head,linklist &p) { int num;//查找的数 int flag=0,count=1,i; printf("请输入要查找的数："); scanf("%d",&num); p=head; while(p->next!=NULL) { if(p->data==num) { flag=1; i=count; } p=p->next; count++; } if(flag==1) printf("有这个数！\n是第%d个数\n",i-1); else printf("没有找到这个数！\n"); } //选择菜单 void choose(linklist &head,linklist &p,linklist &s,linklist &q) { int ch=1; while(ch) { printf("插入请按1，删除请按2，查找请按3，退出请按0!\n"); scanf("%d",&ch); switch(ch) { case 1:insertlist(head,p,s,q);break; case 2:dellist(head,p,s);break; case 3:foundlist(head,p);break; case 0:printf("谢谢使用！");break; default:printf("选择错误！请重新输入：\n");break; } } } void main() { linklist head,p,s,q; initlist(head); getlist(head,p,q); output(head,s); choose(head,p,s,q); }

二、堆栈：

定义：栈是限定仅在表尾进行插入或者删除操作的线性表。

特点：先进后出

![Image 1][]

C语言实现代码：

//栈 #include<stdio.h> #include<malloc.h> #include<stdlib.h> #define SIZE 20 typedef struct { int * base; int * top; int size; }sqstack; //初始化 void initstack(sqstack &mystack) { mystack.base=(int*)malloc(SIZE*sizeof(int)); mystack.top=mystack.base; mystack.size=SIZE; } //进栈 void push(sqstack &mystack) { int e; printf("请输入要存储的数：\n"); scanf("%d",&e); *mystack.top=e; mystack.top++; } //出栈 void pop(sqstack &mystack) { int e; printf("您存储的数有："); if(*&mystack.top!=*&mystack.base) { mystack.top--; e=*mystack.top; printf("%d\n",e); } else printf("栈已为空！\n"); } //菜单 void choose(sqstack &mystack) { int ch=1; while(ch) { printf("入栈请按1，出栈请按2，退出请按0!\n"); scanf("%d",&ch); switch(ch) { case 1:push(mystack);break; case 2:pop(mystack);break; case 0:printf("谢谢使用！");exit(0); default:printf("选择错误！请重新输入\n");break; } } } void main() { sqstack mystack; choose(mystack); }

三、队列：

定义：队列是一种先进先出的线性表。

特点：先进先出

![Image 1][]

C语言代码实现：

#include<stdio.h>
    #include<stdlib.h>
    struct Node
    {
    	int data;                
    	struct Node *next;       
    };
    struct queue
    {
    	struct Node *front;    
    	struct Node *rear;    
    };
    /*初始化链队*/
    void initQueue(struct queue *hq)
    {
    	hq->front=hq->rear=NULL;        
    }
    /*向链队中插入一个元素x*/
    void inQueue(struct queue *hq, int x)
    {
    	struct Node *newNode;  
    	newNode=malloc(sizeof(struct Node));
    	if(newNode==NULL)
    	{
    		printf("内存空间分配失败！ ");
    		exit(1);
    	}
    	newNode->data=x;   /*把x的值赋给新结点的值域*/
    	newNode->next=NULL;    /*把新结点的指针域置空*/
    	if(hq->rear==NULL)
    	{
    		hq->front=hq->rear=newNode;
    	}else
    	{
    		hq->rear=hq->rear->next=newNode;
    	}
    	//return;
    }
    /*从队列中删除*/
    int delQueue(struct queue*hq)
    {
    	struct Node*p;
    	int temp;
    	if(hq->front==NULL)
    	{
    		printf("队列为空，无法删除！ ");
    		exit(1);
    	}
    	temp=hq->front->data;
    	p=hq->front;
    	hq->front=p->next;   
    	if(hq->front==NULL)
    	{
    		hq->rear=NULL;
    	}
    	free(p);      
    	return temp;   
    }
    /*读取队首*/
    int peekQueue(struct queue *hq)
    {   
    	if(hq->front==NULL)
    	{
    		printf("队列为空，无法删除！ ");
    		exit(1);
    	}
    	return hq->front->data;    
    }
    int emptyQueue(struct queue *hq)
    {
    	if(hq->front==NULL)
    	{
    		return 1;
    	}else
    	{
    		return 0;
    	}
    }
    /*清除链队*/
    void clearQueue(struct queue *hq)
    {
    	struct Node *p=hq->front;   
    	while(p!=NULL)
    	{
    		hq->front=hq->front->next;
    		free(p);
    		p=hq->front;
    	}
    	hq->rear=NULL;   
    	return;
    }
    int main(int argc,char *argv[])
    {
    	struct queue q;
    	int a[8]={3,8,5,17,9,30,15,22};
    	int i;
    	initQueue(&q);
    	for(i=0;i<8;i++)
    	{
    		inQueue(&q,a[i]);
    	}
    	inQueue(&q,68);
    	while(!emptyQueue(&q))
    	{
    		printf("%d\n",delQueue(&q));
    	}
    	clearQueue(&q);
    }

所有的工程代码可以在以下网站下载：

【工程下载】[http://download.csdn.net/detail/tiandixuanwuliang/9807964][http_download.csdn.net_detail_tiandixuanwuliang_9807964]

[Image 1]: 
[http_download.csdn.net_detail_tiandixuanwuliang_9807964]: http://download.csdn.net/detail/tiandixuanwuliang/9807964